Upload
long-trieu-tu
View
234
Download
0
Embed Size (px)
Citation preview
8/3/2019 GT Cau truc du lieu
1/64
Cu trc d liu v gii thut Ng Hu Phc
MN HCCU TRC D LIU V GII THUT
Bi 1: GII THIU V THUT TON V CU TRC D LIU1.1. Khi nim thut ton
1.1.1. nh ngha:
Thut ton l mt s hu hn cc bc thc hin tnh ton theo mt trnh t
xc nh bin i cc gi tr u vo (Input) thnh cc gi tr u ra mong mun
(Output).
VD: Bi ton gii phng trnh bc nht ax + b=0
Thut ton:Kim tra gi tr ca a;
Nu =0 th
Nu b=0 th VSN
Ngc li th VN
Ngc li
X=-b/a;
1.1.2. Cc c trng ca thut ton
1. u vo (Input), ra (Output) : mi thut ton cn phi c b d liu u
vo v d liu u ra (kt qu tnh ton).
2. Tnh xc nh: mi bc ca thut ton cn phi m t chnh xc, r
rng.
3. Tnh kh thi: tt c cc php ton trong thut ton phi n gin
thc thi c.
4. Tnh dng: vi mi b s liu u vo tha mn iu kin ban u th
thut ton phi dng sau hu hn bc.
5. Tnh ph dng: Thut ton c th p dng i vi cc d liu u vo
khc nhau trong mt min xc nh.
1.2. Biu din thut ton.
1. Biu bng cch lit k cc bc
Lit k ra cc bc cn phi thc hin bng ngn ng t nhin.VD 1: Thut ton tm s ln nht trong 3 s a,b,c
1
8/3/2019 GT Cau truc du lieu
2/64
Cu trc d liu v gii thut Ng Hu Phc
Gi thit s ln nht l a: Max=a
Nu Max
8/3/2019 GT Cau truc du lieu
3/64
Cu trc d liu v gii thut Ng Hu Phc Nt ch cc iu kin c dng hnh thoi. Trong cc ng ni vi
nt iu kin ny c hai ng i ra ng vi hai trng hp iu kin nghoc iu kin sai:
Khi hnh bnh hnh in cc gi tr. Cc ng ni cc nt vi nhau.
V d 1: s khi sau y m t thut ton tm gi tr ln nht trong mng s A
c n phn t. Thut ton ny c m t trong v d 1.
S khi thut ton tm max trong mng A
3. Biu din thut ton bng m gi
Vi nhng thut ton phc tp, vic v v theo di s khi thng l khngthun tin. Trong mt s trng hp ngi ta s dng ngn ng gi m (gi ngnng lp trnh) m t thut ton.
Cc cu trc c bn c dng trong ngn ng gi m cng nh trong bt kngn ng no khc l cu trc tun t, cu trc r nhnh v cu trc lp.
a) Cu trc tun t: Lit k cc cng vic, cc thao tc theo th t. h tr cho vic theo di c thun tin cng c th thm s th t.
b) Cu trc r nhnh:
If (iu kin) Then (cng vic);
If (iu kin) Then (cng vic 1) Else (cng vic 2);
c) Cu trc lp:
For (bin):= (gi tr u) to (gi tr cui) do (cng vic); For (bin):= (gi tr u) downto (gi tr cui) do (cng
vic);
While (iu kin) do (cng vic);
Repeat- (cng vic 1);- (cng vic 2);- ....
- (cng vic k);Until (iu kin);
3
8/3/2019 GT Cau truc du lieu
4/64
Cu trc d liu v gii thut Ng Hu Phc
VD: Thut ton tm s ln nht trong 3 s a,b,c
*) Lit k cc bc:
Max:=a;
If Max
8/3/2019 GT Cau truc du lieu
5/64
Cu trc d liu v gii thut Ng Hu Phcelse
return F(n-1) + F(n-2);}
Cch thc hat ng nh sau:
F4/ \
F3 F2/ \ / \
F2 F1 F1 F0/ \
F1 F0Trong v d trn, ta thy ta phi tnh 2 ln F2, 3 ln F1 v 2 ln F0.
Do phng php ny chy rt chm khi n ln, thm ch c th b trnstack.
Cc thut ton Quick Sort, Merge Sort thit k theo phng php ny
1.3.2. QUY HOCH NG.
Nguyn l quy hoch ng cng da theo nguyn l chia tr nhng khc
ch l phng php ny tip cn theo hng bottom-up (t di ln).u tin, chng ta xut pht t nhng bi ton c s, d dng c ngay li gii.
T tp nhng li gii ca cc bi ton con nh th, ta tm c li gii ca bi ton
ln hn. V c thc hin nh th cho n khi thu c bi ton cui cng mong
mun.
VD: Xt l bi ton s FibonaciBi ton trn c gii theo phng php quy hoch ng nh sau:
int F(int n){int Fi[100];int i;Fi[0] = Fi[1] = 1;for (i = 2; i
8/3/2019 GT Cau truc du lieu
6/64
Cu trc d liu v gii thut Ng Hu Phc{
int f, f1, f2, i;f1 = f2 = 1;for (i = 2; i
8/3/2019 GT Cau truc du lieu
7/64
Cu trc d liu v gii thut Ng Hu Phcthi im ch c th thc hin mt cng vic. Mi cng vic i c thi gian bt u lsi v thi gian kt thc l i, vi si i.
Nu c chn, cng vic i chim ht khong thi gian [si,i].
Hy chn ra phng n thc hin cc cng vic trn sao cho s cng vic thc
hin c l ln nht trong mt khong thi gian nht nh.Thut ton tham lam: u tin ta sp xp cc cng vic trn tng dn theo thi
gian kt thc.
Thc hin cng vic u tin.
I=1
Cho j=i+1 to n
Nu sj>ai th
Chn tip j
I=j;
p dng k thut tham n s cho mt gii thut thi gian a thc, tuy nhin ni
chung chng ta ch t c mt phng n tt ch khng phi l ti u.
1.3.5. K THUT QUI v QUI QUAY LUI
VD : Bi ton xp 8 hu ln bn c.
1.4. Quan h gia cu trc d liu v thut ton.
- Thut ton ch ch ra cc bc tnh ton, cn i tng c dng tnh
ton chnh l d liu.
- D liu biu din cc thng tin cn thit cho bi ton: cc d liu u vo,
trung gian, kt qu. Nu bit t chc d liu theo cu trc thch hp th vic x l s
thun tin hn v t c hiu qu cao hn.
- Vi mt cu trc d liu chn ta s c gii thut tng ng. Cu trc d
liu thay i th gii thut cng thay i theo.
Xt v d sau: Gi s u vo chng ta c mt cp danh sch: Tn n v, sin thoi. (a1,b1),(a2,b2), Ta mun c chng trnh tm s in thoi theo tn
7
8/3/2019 GT Cau truc du lieu
8/64
Cu trc d liu v gii thut Ng Hu Phc
n v.
Gii thut 1: Tm kim tun t t u danh sch tn cc n v c trong danh
sch cho n khi tm thy hoc ht danh sch.
Gii thut 2: Trc khi tm kim, ta t chc li d liu bng cc sp xp danh
sch tng dn theo t in. Vic tm kim s thc hin t u danh sach cho n khi
tm thy hoc tnnvcntm
8/3/2019 GT Cau truc du lieu
9/64
Cu trc d liu v gii thut Ng Hu Phc
VD3: Ch ra hm n! l O(nn) v log(n!) l O(nlogn)
Ta c n!
8/3/2019 GT Cau truc du lieu
10/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 2 : QUY
2.1. Khi nim v quy.
Ta ni mt i tng l qui nu i tng ny bao gm chnh n nh mt
b phn hoc i tng c nh ngha di dng ca chnh n.
V d 1: giai tha
+ 0!=1
+ n !=n*(n-1) !
V d 2 : Cu trc th mc l mt dng nh ngha qui : th mc cha th
mc con.
2.2. Gii thut qui v th tc qui- Nu li gii ca bi ton T c thc hin thng qua li gii ca mt bi ton
T c kch thc nh hn T v c dng ging nh T, th l mt li gii qui.
Gii thut tng ng vi li gii nh vy gi l gii thut qui.
- Trong th tc c li gi n chnh n gi l th tc qui.
2.3. Thit k gii thut quy
Khi bi ton c nh ngha di dng qui th ta rt d thit k gii thut
.V d 1 : Hm giai tha n !
nh ngha n!
n! =1 nu n=0
= n(n-1) ! nu n>0
#include
int f(int n)
{ if (n==0) return 1;
else
return n*f(n-1);
}
void main()
{ int fb;
fb=f(4);
printf("F=%d",fb);
10
8/3/2019 GT Cau truc du lieu
11/64
Cu trc d liu v gii thut Ng Hu Phc
}
v d 2 : Dy Fibonacci
fib(n)=fib(n-2)+fib(n-1) nu n>2
fib(n)=1; nu n
8/3/2019 GT Cau truc du lieu
12/64
Cu trc d liu v gii thut Ng Hu Phc
4. Tng t ta dng mng dcp vi ngha: dcp[k]=1 nu ng cho ph th
k c mt con hu c t.
Gi m ca thut ton xp hu nh sau:
procedure Try(i);
var j;
begin
for j := 1 to n do
if (cot[j]=0) and (dcc[i-j]=0) and (dcp[i+j]=0) then
begin
x[i] := j; cot[j]:=1; dcc[i-j]:=1; dcp[i+j]:=1;{ghi nhn trng thi mi}
if i=n then Updateelse Try(i+1);
cot[j]:=0; dcc[i-j]:=0; dcp[i+j]:=0; {phc hi trng thi c}
end;
end;
procedure Update;
begin
count := count + 1;print(x);
end;
{tng cng c 92 cch xp 8 hu}
2.4. Kh qui.
C nhng bi ton bn cnh gii thut qui vn c nhng gii thut lp kh
n gin v hiu qu.
Vd 1: n!
int F(int n)
{int tg;
if ((n==0)||(n==1)) { return 1; }
else
{ tg=1;
for (int i=2;i
8/3/2019 GT Cau truc du lieu
13/64
Cu trc d liu v gii thut Ng Hu Phc
return tg;
} }
VD2: Fibonacci
Function Fibo (n:byte):double;
Begin
If n
8/3/2019 GT Cau truc du lieu
14/64
Cu trc d liu v gii thut Ng Hu Phc
2.6. Tnh ng n ca cc gii thut quy
chng minh tnh ng n ca mt gii thut qui ngi ta s dng
phng php qui np ton hc.
Vd: Chng minh gii thut qui tnh giai tha F(n).
Gii thut:
F(0)=1
F(n)=n(n-1)(n-2)2*1;(n>0)
CM:
+Nu n=0; theo gii thut f:=1 (nh vy gii thut ng khi n=0)
+ Gi s gii thut ng vi n=k, ngha l F(k)=k*(k-1)*2*1.
+ Ta phi chng minh gii thut ng vi n=k+1;Ta thy vi n=k+1 th F:=n*f(n-1) s c thc hin. Thay n=k+1 ta c
F(k+1)=(k+1)F(k)=(k+1)*k*(k-1)*2*1.(dpcm)
2.7. Bi tp
1) Xt tnh qui:
n+1 nu m=0
A(m,n) = A(m-1,1) nu n=0A(m-1,A(m,n-1)) vi cc trng hp cn li.
2) Bi ton 8 qun hu v gii thut quay lui
Bn c vua gm 8 hng, 8 ct. Qun hu l qun c c th n c bt k qun
no nm trn cng hng, ct, ng cho. Bi ton: hy xp 8 con hu ln trn bn
c sao cho cc qun hu khng th n c nhau.
3) Din tch bn c
Cho bng ch nht A gm M dng v N ct. Trn mi ghi cc gi tr 0 v 1:
gi tr 0 c hiu l nc, gi tr 1 c hiu l t. Hai t c cnh lin nhau
c xem nh nm trong cng mt bn c. Hy xc nh din tch ca bn c ln
nht (mi c xem nh 1 n v o).
Nhn xt:
- Mi c nh s 1 c xem nh l mt nh ca th.
- Hai nh c gi l lin thng nu c chung cnh. Nh vy yu cu ca bi
ton chnh l tm thnh phn lin thng c s nh ln nht.
14
8/3/2019 GT Cau truc du lieu
15/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 3: MNG V DANH SCH.
3.1. Cc khi nim.
Mng: l mt tp hp c th t cc phn t. Vector c lu trong mng mt
chiu, mi phn t ca n ng vi mt ch s i. Ma trn c lu trong mt mng 2
chiu, mi phn t ng vi 2 ch s i,j. S phn t ca mng l c nh, c xc
inh khi khai bo.
Danh sch: l mt tp hp c th t cc phn t. S phn t ca danh sch
khng c nh, c th thm hoc xa i.
3.2. Cc thao tc trn mng.
3.2.1. Truy cp cc phn t ca mng.Trong C++, khai bo mng nh sau:
type name [elements]; VD: int billy [5];Khi to mng: int billy [5] = { 16, 2, 77, 40, 12071 };Cc phn t ca mng trong C++ c nh s t 0:
Truy cp n phn t ca mng: Billy[2]=100; x=Billy[1];Mng nhiu chiu: int jimmy [3][5];
jimmy[n][m]=(n+1)*(m+1);
3.2.2. Chn thm phn t vo gia mng.
chn mt phn t vo mng, ta cn phi xt xem mng cn ch trng
khng? Nu cn, ta s y cc phn t t v tr cn chn i mt nh v cui mng
ri t gi tr mi vo v tr cn chn.V d:
a[1] a[2] a[3] a[4] a[5] a[6]
Gi s ta mun chn vo v tr s 4 ca mng ta thc hin nh sau:a[1] A[2] a[3] a[4] a[5] a[6] a[7]
Thut ton:
Cc tham s: mng A; S phn t, Kch thc mng, v tr chn, gi tr cn
chn. void Insert(int *A, int N , int Size, int k, int x){
15
8/3/2019 GT Cau truc du lieu
16/64
Cu trc d liu v gii thut Ng Hu Phcif (N
8/3/2019 GT Cau truc du lieu
17/64
Cu trc d liu v gii thut Ng Hu Phc
3.3. DANH SCH LIN KT.
3.3.1. Mt s php ton trn danh sch
1. Khi to danh sch rng:Initialize(var L: List)
2. Xc nh di ca danh sch:Length(L: List)
3. Loi phn t v tr th p ca danh sch: Delete(var L:List, p:
position)
4. Chn phn t x vo v tr p ca danh sch: Insert(var L: List, p:
position, x: item)
5. Tm x c trong danh sch L khng? Search(x:item, L: List, var p:
position)
6. Kim tra danh sch c rng khng?IsEmpty(L:List)
3.3.2. Khi nim v cch s dng con tr.
Khi nim
Con tr l mt khi nim c trong mt s ngn ng lp trnh nh c, c++,
pascal dng qun l b nh ng.
Bin tnh: l bin c xc nh vng nh khi chng trnh bt u chy v
b hy khi chng trnh kt thc.
Bin ng: l bin c to ra v c th hy b khi chng trnh ang thc
hin.
Bin con tr dng qun l b nh ng.
Khai bo v s dng con tr C++
- Khai bo:
type * pointer_name;
VD:
int * i;char * c; float * f;
- Cp pht vng nh v dng con tr p qun l
Pointer_name = new type ([Init_value])
int *i;
17
8/3/2019 GT Cau truc du lieu
18/64
Cu trc d liu v gii thut Ng Hu Phc
i= new int(1012);
printf("i=%d",*i);
- Thao tc trn vng nh cp pht thng qua con tr p
+ Gn gi tr cho vng nh: *pointer_name:=x;
+ Ly gi tr ca vng nh: y:=*pointer_name;
+ Hai con tr cng kiu c th thc hin php gn, php so snh
q=p;==, !=,>=,...
- Hy vng nh
deletepointer_name;
3.3.3. Danh sch lin kt n.
Mi phn t ca danh sch n l mt cu trc cha 2 thng tin:
- Thnh phn d liu: lu tr cc thng tin v bn thn phn t .
- Thnh phn mi lin kt: lu tr a ch ca phn t k tip trong danh
sch, hoc lu tr gi tr NULL nu l phn t cui danh sch.
Cch qun l: Nu bit c a ch ca phn t u tin trong danh sch n
th c th da vo con tr Next truy xut n phn t th 2 trong xu, v li da
vo con tr Next ca phn t th 2 truy xut n phn t th 3...
Khai bo tng qut
struct NODE{
int Info;
struct NODE * pNext;};
NODE* Head;NODE *xNew;int x;
18
aan
Head
8/3/2019 GT Cau truc du lieu
19/64
Cu trc d liu v gii thut Ng Hu Phc
Khi to danh sch rng: Head=NULL;
To mt phn t cho danh sch
NODE* GetNode(int x)
{ NODE *p;
p=new NODE();
if (p==NULL)
{
printf("Khng ?? b? nh?.");
return NULL;
}
p->Info=x;
p->pNext=NULL;
return p;
}
Kim tra danh sch c rng hay khng
bool Empty(NODE *h)
{
return (h==NULL);
}
Thm mt phn t vo u danh sch
Thut ton thm phn t p vo u danh sch :
Bt u:
B11 : p=GetNode(x); p->Next = Head;B12 : Head = p ;
an-1
a1
an
X
Head
an-2
p
19
8/3/2019 GT Cau truc du lieu
20/64
Cu trc d liu v gii thut Ng Hu Phc
NODE* InsertHead(NODE **h, int x)
{ NODE* xNew = GetNode(x);
if (xNew ==NULL) return NULL;
if (*h==NULL)
{
*h = xNew;
}
else
{
xNew->pNext = *h;
*h = xNew;}
return xNew;
}
Chn mt phn t vo sau phn t q trong danh sch
Thut ton chn phn t p:
Bt u :
Nu ( p != NULL) th
B1 : p -> Next = q->Next;
B2 : q->Next = p ;
NODE * InsertAfter(NODE **q, int x)
{
NODE* new_ele = GetNode(x);
x
a1an-1an
Head
an-2
q
p
20
8/3/2019 GT Cau truc du lieu
21/64
Cu trc d liu v gii thut Ng Hu Phc
if (new_ele ==NULL) return NULL;
if ( *q!=NULL)
{
new_ele->pNext = (*q)->pNext;
(*q)->pNext = new_ele;
}
else //chn vo ??u danh sch
InsertHead(&Head, x);
}
Chn phn t vo cui danh sch
Thut ton chn p vo cui danh sch:
Bt u :Nu danh sch rng th
Head = p;
Ngc li
B21 : q:=head;
B22 : trong khi p nil th
Before:=q;q:=q^.next;
B23:before^.next:=p;
NODE* InsertTail(NODE **h, int x)
{
NODE* new_ele = GetNode(x);
if (new_ele ==NULL) return NULL;
if (*h==NULL)
{
an-1
a1
an
X
Head
an-2
pq
21
8/3/2019 GT Cau truc du lieu
22/64
Cu trc d liu v gii thut Ng Hu Phc
*h = new_ele;
}
else
{
NODE *p;
p=*h;
while (p->pNext !=NULL) p=p->pNext ;
p->pNext = new_ele;
}
return new_ele;
}
Th tc xa mt phn t ra khi danh sch
Hy phn t u xu:
Bt u:
Nu (Head != NULL) th
B1: p = Head; // p l phn t cn hy
B2:
B21 : Head = Head->Next; // tch p ra khi xu
B22 : delete p; // Hy bin ng do p tr n
Pr
bool RemoveHead(NODE **h){
NODE *p;
if ( *h != NULL){
p = *h;*h= (*h)->pNext;delete p;
an-2
a1
an-1
an
Head
an-3
P q
22
8/3/2019 GT Cau truc du lieu
23/64
Cu trc d liu v gii thut Ng Hu Phc
}return true;
}
Hy mt phn t ng sau phn t q
Thut ton :
Bt u:
Nu (q!= NULL) th
B1: p = q->Next; // p l phn t cn hy
B2: Nu (p != NULL) th // q khng phi l cui xu
B21 : q->Next = p->Next; // tch p ra khi xu
B22 : dispose(p); // Hy bin ng do p tr n
bool RemoveAfter ( NODE *q)
{ NODE *p;
if ( q != NULL)
{ p = q ->pNext ;
if ( p != NULL)
{ q->pNext = p->pNext;delete p;
}
}
}
Hy mt phn t c kho k Thut ton :
Bc 1:Tm phn t p c kha k v phn t q ng trc n
Bc 2:
Nu (p!= NULL) th // tm thy k
Hy p ra khi danh sch tng t hy phn t sau q;
Ngc li
Bo khng c k;
bool RemoveNode(NODE *h, int k){
NODE *p = h;
23
8/3/2019 GT Cau truc du lieu
24/64
Cu trc d liu v gii thut Ng Hu PhcNODE *q = NULL;
while( p != NULL){
if(p->Info == k) break;q = p; p = p->pNext;
}
if(p == NULL) return false; //Khng tm th?y k
if(q != NULL){
q->pNext = p->pNext;delete p;
}else //p l ph?n t? ??u xu{
RemoveHead(&Head);}
return true;}
X l danh sch
- m cc phn t ca danh sch,
- Tm phn t tho iu kin,
- Hu ton b danh sch (v gii phng b nh) duyt danh sch (v x l tng phn t) ta thc hin cc thao tc sau:
Thut ton :
Bc 1:
p = Head; //Cho p tr n phn t u danh sch
Bc 2:
Trong khi (Danh sch cha ht) thc hin
B21 : X l phn t p;
B22 : p:=p->Next; // Cho p tr ti phn t k
Hy ton b danh sch void RemoveList(NODE **h){ NODE *p;
while ( (*h) != NULL){
p=*h;(*h) = (*h)->pNext;
delete p;
}
}
In tan b danh schvoid ProcessList (NODE *h)
24
8/3/2019 GT Cau truc du lieu
25/64
Cu trc d liu v gii thut Ng Hu Phc{ NODE *p;
p = h;while (p!= NULL){
printf("%d == ",p->Info );p = p->pNext;
}printf("\n");
}Tm kim
NODE *Search(NODE *h, int k){
NODE *p;p = h;
while((p!= NULL)&&(p->Info != k))p = p->pNext;
return p;
}
3.3.4. Cc loi danh sch lin kt khc.
Danh sch lin kt vng
Con tr ca phn t u tin tr v phn t t cui danh sch.
Khi x l danh sch ni vng nu khng cn thn s dn ti mt chu trnh (ko
kt thc c). d dng cho vic x l ngi ta thng a vo mt nt c bit
gi l nt u danh sch khng cha d liu v con tr pNext tr n chnh n.
struct NODE{ int info;
Struct NODE *pNext;
}
Khi to:
NODE *Head;
Head=new NODE(); Head->info=0; Head->pNext=Head;
InsertHead
p=GetNode(x);p->pNext=Head->pNext;
25
an-1an
Head
8/3/2019 GT Cau truc du lieu
26/64
Cu trc d liu v gii thut Ng Hu Phc
Head->pNext=p;
DeleteHead
p=Head->pNext;
if (p!=NULL)
{
Head->pNext=p->pNext;
Delete p;
}
Danh sch lin kt i
Danh sch lin kt i ni vng
3.4. Bi tp.
1. Thit k cu trc d liu biu din ma trn tha.
2. S dng danh sch lin kt vng gii bi ton Joesphus.3. S dng cu trc danh sch biu din a thc hai bin s x v y.
4. Vit hm m s phn t trong mt danh sch lin kt ni vng.
5. Vit mt hm o ngc lin kt ca mt danh sch lin kt n.
6. Sp xp danh sch lin kt n theo trt t tng dn.
7. S dng cu trc danh sch lin kt biu din hai a thc P(x) v Q(x).
a. Vit th tc cng hai a thc ny
b. Vit th tc nhn hai a thc ny
LinkH s
S m
26
8/3/2019 GT Cau truc du lieu
27/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 4. NGN XP V HNG I.
4.1. Ngn xp.
4.1.1. Khi nim v ngn xp.
Ngn xp (Stack) l mt dng ca danh sch lin kt hot ng theo nguyn
tc vo trc ra sau (First in last out- FILO). Phn t ph trn gi l nh ngn xp,
pha di gi l y ngn xp.
- V d: p dng Stack trong bi ton i c s ca mt s t h thp phn
sang h nh phn.
(m t thut ton i c s ng dng cu trc d liu Stack cho thut ton ny )V d : (10)10=(1010)2
4.1.2. Ci t Stack bng mng.
Ta c th to mt stack bng cch khai bo mt mng 1 chiu vi kch thc
ti a l N (v d, N c th bng 1000).VD:
To stack S v qun l nh stack bng bin t ch s ca phn t trn cng
trong stack:
Khao bo int S[N]; t=-1;B sung vo Stack void Push (int S[], t,x)
27
0 0
1
01
8/3/2019 GT Cau truc du lieu
28/64
Cu trc d liu v gii thut Ng Hu Phc
if (t=0)
(Pop=S[t];t-=1;)
4.1.3. Ci t ngn xp bng danh sch lin kt.
Khai bo
struct NODE
{ int info;
struct NODE *pNext;
};
NODE *S;
1. Khi to
S=NULL;
2. Kim tra Stack rng
bool IsEmpty(NODE *s)
{
return (s==NULL);
}
3. Thm phn t mi
void Push(NODE **s, int x)
{NODE *tg;tg=GetNode(x);
tg->pNext=*s;
*s=tg;
}
4. Ly ra mt phn t
int Pop(NODE **s)
{NODE *tg;
28
8/3/2019 GT Cau truc du lieu
29/64
Cu trc d liu v gii thut Ng Hu Phc
int x;
if (!IsEmpty(*s))
{
x=(*s)->info;
tg=*s;
*s=(*s)->pNext;
delete tg;
return x;
}
return 0;
}4.1.4. ng dng ca ngn xp: tnh gi tr ca biu thc
1. Biu thc trung t: a*(b+c)-d/e
2. Bin i biu thc trung t sang dng hu t
Biu thc s dng k php Balan l mt biu thc khng c ngoc php ton
trong biu thc Balan t sau cc ton hng:
Dng trung t
a+b
a*b
a*(b+c)-d/e
Dng hu t
ab+
ab*
abc+*de-/
Di y l thut ton bin i t dng trung t sang dng hu t
V d :
E=a*(b+c)-d/e#E S E1
$a $ a* $* a( $*( a
b $*( ab+ $*(+ abc $*(+ abc) $*( abc+
$* abc+- $ abc+*
$- abc+*
29
8/3/2019 GT Cau truc du lieu
30/64
Cu trc d liu v gii thut Ng Hu PhcD $- abc+*d/ $-/ abc+*dE $-/ abc+*de# $- abc+*de/
$ abc+*de/-
Thut ton 1
Bc 1 : c mt thnh phn ca biu thc E (dng trung t biu din bng
xu, c t tri qua phi). Gi s thnh phn c c l x
1.1Nu x l ton hng th vit n vo bn phi biu thc E1
1.2Nu x l du ( th y n vo ngn xp
1.3Nu x l mt trong cc php ton +, -, *, / th
1.3.1 Xt phn t y nh ngn xp
1.3.2 Nu Pri(y)>=Pri(x) l mt php ton th loi y ra khi
ngn xp v vit y vo bn phi ca E1 v quay li
bc 1.3.1
1.3.3 Nu Pri(y)
8/3/2019 GT Cau truc du lieu
31/64
Cu trc d liu v gii thut Ng Hu Phc
hin php ton, kt qu c y vo trong ngn xp
Bc 2 : Lp li bc 1 cho n khi ht tt c cc phn t trong biu thc E1.
lc nh ca ngn xp cha gi tr ca biu thc caanf tnh
Bc 3. Kt thc
4.1.5. Bi tp
1. Hy ch ra ni dung ca ngn xp sau mi thao tc trong chui sau
E A S*Y**Q U E***S T***I*ON** . y cc k t ch c ngha
l Push v cc k t * c ngha l Pop.
2. Gii thch cc php PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S),
PUSH(S, 8), v POP(S) trn cu trc Stack S rng.
3. Hy ci t hai Stck da trn mng mt chiu. Stack c gi l
y khi tng s phn t ca hai Stack bng s phn t ca mng.
4. Vit th tc bng ngn ng Pascal chuyn biu thc t dng
trung t sang dng hu t.
5. Vit th tc tnh gi tr ca biu thc dng hu t
vd : 2 3 4 + *
6. Vit chng trnh i mt s t h thp phn sang h nh phn
s dng cu trc d liu Stack.
4.2. HNG I
4.2.1. Khi nim v hng i
Hng i l mt cu trc d kiu hot ng theo nguyn tc vo trc ra
trc -FIFO.
Trn cu trc ny c hai thao tc c bn l :
1. Thm mi AddQUEUE
2. Loi b -RemoveQUEUE
3. Kim tra hng rng
u vo u ra
31
8/3/2019 GT Cau truc du lieu
32/64
Cu trc d liu v gii thut Ng Hu Phc
4.2.2. Ci t hng i bng mng:
Ta c th to mt hng i bng cch s dng mt mng 1 chiu vi
kch thc ti a l N (v d, N c th bng 1000) theo kiu xoay vng (coi phn t
an-1 k vi phn t a0).Ta k hiu n l NULLDATA nh nhng phn trc.
Trng thi hng i lc bnh thng:
Q bin hng i, f qun l u hng i, r qun l phn t cui hng i.
Trng thi hng i lc xoay vng (mng rng gia):
Cu hi t ra: khi gi tr f=r cho ta iu g ? Ta thy rng, lc ny hng
i ch c th mt trong hai trng thi l rng hoc y.
Hng i c th c khai bo c th nh sau:
int Q[N];
int F, R;
void init()
{
F=-1;R=-1;
}
void Insert(int *f, int *r, int x)
{
if (*f==-1)
{
*f=0; *r=0;
Q[*r]=x;
}
else
{ if (*f==((*r+1)%N)){
32
8/3/2019 GT Cau truc du lieu
33/64
Cu trc d liu v gii thut Ng Hu Phc
printf("tran queue");
exit;
}
else
{*r=(*r+1)%N;
Q[*r]=x;
}
}
}int Remove(int *f, int *r)
{ int x;
if (*f==-1) return -1;
x=Q[*f];
if (*f==*r)
{
*f=-1;*r=-1;}
else
*f=(*f+1)%N;
return x;
}
4.2.3. Ci t hng i bng hng danh sch lin kt.
- Khai bostruct Node{
int info;struct Node *next;
a1
an-1
an
.
Front Rear
33
8/3/2019 GT Cau truc du lieu
34/64
Cu trc d liu v gii thut Ng Hu Phc};
Node *F, *R;
- Khi to hng i : F=NULL; R=NULL;
- Thm mt phn t p vo hng i
void Insert(Node **f,Node **r, int x){
Node *p;
p=new Node(); p->info=x; p->next=NULL;
if (*f==NULL)
{ *f=p;*r=p;
}else{
(*r)->next=p;*r=p;
}}
a1
Front
Rear
an-1
a1
an
X
Front
an-2
pRear
34
8/3/2019 GT Cau truc du lieu
35/64
Cu trc d liu v gii thut Ng Hu Phc
- Loi mt phn t khi hng i
int Remove (Node **f, Node **r)
{Node *p;int x;if (*f==NULL) return 0;
p=*f;x=p->info ;(*f)=(*f)->next ;if (*f==NULL) *r=NULL;
delete p;
return x;
}
4.2.4. Bi ton m phng s dng hng i
Bi ton qun l kho hng :(qun l phiu nhp hng, qun l phiu xut, qun
l hng tn kho, lng tin tn). qun tin tn, hng tn th ngi ta thng s
dng hng i hng nhp trc s c bn trc.M phng my ch phc v cc yu cu t my gi n s dng cc dch v
khc nhau. M phng trung tm thng tin phc v khch hng. M phng truyn tin
gia hai my tnh.
4.2.5. Bi tp
1. Xy dng mt hng i m cc phn t l cc nhn vin trong mt cng ty.
Yu cu : Nhn vin : h tn, tui, qu quan. Tm kim nhn vin theo hoten,
tuoi, quequan.
2. Dng cc php ton c bn ca hng i v ngn xp, vit mt thut ton
o ngc cc phn t ca hng i.
3. M phng trung tm thng tin phc v khch hng.
4.3. Hng i u tin
Hng u tin l mt kiu d liu tru tng trn tp hp cng vi cc php
ton : thm (INSERT) v xo phn t b nht (DELETEMIN), MAKENULL khito.
35
8/3/2019 GT Cau truc du lieu
36/64
Cu trc d liu v gii thut Ng Hu Phc
Mi phn t a trong hng i c u tin l p(a).
Php ton DELETEMIN s cho ra kt qu l phn t c u tin nh nht
trong tp hp v xa n khi tp hp ny. Nh vy ta c th coi DELETEMIN l t
hp ca th tc DELETE v hm MIN tho lun trong chng.
Thut ng hng gi cho chng ta hnh dung cc phn t ca tp hp ang
xp hng ch phc v, thut ng u tin gi cho ta hiu rng khng phi l " n
trc- c phc v trc".
V d ti bnh vin, cc bnh nhn xp hng ch phc v nhng khng phi
ngi n trc th c phc v trc m h c u tin theo tnh trng khn cp
ca bnh.
C th ci t hng i u tin bng danh sch lin kt hoc cu trc cy.
36
8/3/2019 GT Cau truc du lieu
37/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 5. CC THUT TON SP XP.5.1. Bi ton sp xp.
Sp xp l qu trnh b tr li cc phn t ca mt tp hp no (hoc cc
mu tin) theo mt th t xc nh. V d th t tng dn (gim dn) i vi mt dy
s, theo th t t in i vi mt dy k t,
5.2. Sp xp chn.
tng ca thut ton chn trc tip m phng mt trong nhng cch sp xp
t nhin nht trong thc t:
Chn phn t nh nht trong N phn t ban u, a phn t ny v v tr ng
l u dy hin hnh; sau khng quan tm n n na, xem dy hin hnh ch cn
N-1 phn t ca dy ban u, bt u t v tr th 2; lp li qu trnh trn cho dyhin hnh... n khi dy hin hnh ch cn 1 phn t. Dy ban u c N phn t, vy
tm tt tng thut ton l thc hin N-1 lt vic a phn t nh nht trong dy
hin hnh v v tr ng u dy. Cc bc tin hnh nh sau : Bc 1 : i = 1; Bc 2 : Tm phn t a[min] nh nht trong dy hin hnh t a[i] n a[N] Bc 3 : Hon v a[min] v a[i] Bc 4 : Nu i
8/3/2019 GT Cau truc du lieu
38/64
Cu trc d liu v gii thut Ng Hu Phc nh gi gii thut
i vi gii thut chn trc tip, c th thy rng bc th i, bao gi cng
cn (n-i) php so snh xc nh phn t nh nht hin hnh. S lng php so
snh ny khng ph thuc vo tnh trng ca dy s ban u, do vy trong mitrng hp c th kt lun :
S ln so snh =
S ln hon v (mt hon v bng 3 php gn) li ph thuc vo tnh trng ban
u ca dy s, ta ch c th c lc trong tng trng hp nh sau :
Trng hp S ln so snh S php gn
Tt nht n(n-1)/2 0Xu nht n(n-1)/2 3n(n-1)/2
5.3. Sp xp chn.
Gii thut
Gi s c mt dy a1 , a2 ,... ,an trong iphn t u tin a1 , a2 ,... ,ai-1 c
th t. tng chnh ca gii thut sp xp bng phng php chn trc tip l tm
cch chn phn t ai vo v tr thch hp ca on c sp c dy mi a1 , a2
,... ,ai tr nn c th t. V tr ny chnh l v tr gia hai phn t ak-1v ak tha ak-1 = 0) and (a[pos] > x)) do
Begina[pos+1] := a[pos];
pos:=pos -1;end;a[pos+1] := x;
end;End;
Ci tin thut ton : khi tm v tr thch hp chn a[i] vo on a[0] n
a[i-1], do on c sp, nn c th s dng gii thut tm nh phn thc hin
vic tm v tr pos, khi c gii thut sp xp chn nh phn :
nh gi gii thut
i vi gii thut chn trc tip, cc php so snh xy ra trong
mi vng lp while tm v tr thch hp pos, v mi ln xc nh v tr
ang xt khng thch hp, s di ch phn t a[pos] tng ng. Giithut thc hin tt c N-1 vng lp while , do s lng php so snh
v di ch ny ph thuc vo tnh trng ca dy s ban u, nn ch
c th c lc trong tng trng hp nh sau :
Trng hp S php so snh S php gn
Tt nht
39
8/3/2019 GT Cau truc du lieu
40/64
Cu trc d liu v gii thut Ng Hu Phc
Xu nht
5.4. Sp xp ni bt.
Gii thut
tng chnh ca gii thut l xut pht t cui (u) dy, i ch cc cp
phn t k cn a phn t nh (ln) hn trong cp phn t v v tr ng u
(cui) dy hin hnh, sau s khng xt n n bc tip theo, do vy ln x l
th i s c v tr u dy l i. Lp li x l trn cho n khi khng cn cp phn t
no xt. Cc bc tin hnh nh sau : Bc 1 : i = 1; // ln x l u tin
Bc 2 : j = N; //Duyt t cui dy ngc v v tr i
Trong khi (j < i) thc hin:
Nu a[j]N-1: Ht dy. Dng
Ngc li : Lp li Bc 2.
V d
Cho dy s a: 12 2 8 5 1 6 4 15
40
8/3/2019 GT Cau truc du lieu
41/64
Cu trc d liu v gii thut Ng Hu Phc
Ci t
Procedure BubleSort(var a:m1c; N:integer );var i, j,tg:integer;Begin
for i:= 2 to N-1 dofor j :=N-1 downto i do
if (a[j]< a[j-1]) thenbegin tg:=a[j];a[j]:=a[j-1];a[j-1]:=tg; end;
End;
nh gi gii thut
i vi gii thut ni bt, s lng cc php so snh xy ra
khng ph thuc vo tnh trng ca dy s ban u, nhng s lng
php hon v thc hin ty thuc vo kt qa so snh, c th c lc
trong tng trng hp nh sau:
Trng hp S ln so snh S ln hon v
Tt nht 0
Xu nht
5.5. Sp xp nhanh.
sp xp dy a1, a2, ..., an gii thut QuickSort da trn vic phn hoch dy
ban u thnh hai phn:
Dy con 1:Gm cc phn t a1.. ai c gi tr khng ln hn x
Dy con 2:Gm cc phn t ai .. an c gi tr khng nh hn x
vi x l gi tr ca mt phn t ty trong dy ban u. Sau khi thc hin
phn hoch, dy ban u c phn thnh 3 phn:
1. ak< x , vi k = 1..i
2. ak= x , vi k = i..j
3. ak> x , vi k = j..N
41
8/3/2019 GT Cau truc du lieu
42/64
Cu trc d liu v gii thut Ng Hu Phc
Trong dy con th 2 c th t, nu cc dy con 1 v 3 ch c 1 phn t
th chng cng c th t, khi dy ban u c sp. Ngc li, nu cc dy
con 1 v 3 c nhiu hn 1 phn t th dy ban u ch c th t khi cc dy con 1, 3
c sp. sp xp dy con 1 v 3, ta ln lt tin hnh vic phn hoch tng dy
con theo cng phng php phn hoch dy ban u va trnh by .
Ci t
void QuickSort(int *a, int trai, int phai)
{
int i,j;int x;
x = a[(trai+phai)/2]; // ch?n ph?n t? gi?a lm gi tr? m?c
i =trai; j = phai;
do {
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i
8/3/2019 GT Cau truc du lieu
43/64
Cu trc d liu v gii thut Ng Hu Phc
nhng n gin, d din t gii thut, phn t c v tr gia thng
c chn, khi k = (l +r)/ 2
Gi tr mc x c chn s c tc ng n hiu qu thc hin thut ton v
n quyt nh s ln phn hoch. S ln phn hoch s t nht nu ta chonc x l phn t median ca dy. Tuy nhin do chi ph xc nh phn t
median qu cao nn trong thc t ngi ta khng chn phn t ny m chn
phn t nm chnh gia dy lm mc vi hy vng n c th gn vi gi tr
median
nh gi gii thut
Hiu qa thc hin ca gii thut QuickSort ph thuc vo vic chn gi tr
mc. Trng hp tt nht xy ra nu mi ln phn hoch u chn c phn t
median (phn t ln hn (hay bng) na s phn t, v nh hn (hay bng) na s
phn t cn li) lm mc, khi dy c phn chia thnh 2 phn bng nhau v
cn log2(n) ln phn hoch th sp xp xong. Nhng nu mi ln phn hoch li
chn nhm phn t c gi tr cc i (hay cc tiu) l mc, dy s b phn chia
thnh 2 phn khng u: mt phn ch c 1 phn t, phn cn li gm (n-1) phnt, do vy cn phn hoch n ln mi sp xp xong. Ta c bng tng kt
Trng hp phc tp
Tt nht n*log(n)
Xu nht n2
5.6. Heap Sort.5.6.1. tng:
Nhn xt: Khi tm phn t nh nht bc i, phng php sp xp chn
trc tip khng tn dng c cc thng tin c c do cc php so snh bc i-
1.
V l do trn ngi ta tm cch xy dng mt thut ton sp xp c th
khc phc nhc im ny.
Mu cht gii quyt vn va nu l phi tm ra c mt cu trc
d liu cho php tch ly cc thng tin v s so snh gi tr cc phn t trong qua
43
8/3/2019 GT Cau truc du lieu
44/64
Cu trc d liu v gii thut Ng Hu Phc
trnh sp xp.
Gi s d liu cn sp xp l dy s : 5 2 6 4 8 1 c b tr theo quan
h so snh v to thnh s dng cy nh sau :
Trong mt phn t mc i chnh l phn t ln trong cp phn t mc
i+1, do phn t mc 0 (nt gc ca cy) lun l phn t ln nht ca dy.Nu loi b phn t gc ra khi cy (ngha l a phn t ln nht v
ng v tr), th vic cp nht cy ch xy ra trn nhng nhnh lin quan n phn t
mi loi b, cn cc nhnh khc c bo ton, ngha l bc k tip c th s dng
li cc kt qu so snh bc hin ti.
5.6.2. nh ngha Heap:
Heap c nh ngha l mt dy cc phn t ap, a2 ,... , aq tho cc quanh sau vi mi i thuc [p, q]:
1/. ai >= a2i
2/.ai >= a2i+1
{(ai , a2i), (ai ,a2i+1) l cc cp phn t lin i }
5.6.3. Tnh cht ca Heap :
Mi dy a1 , a2 ,... , an, dy con aj, aj+1,, an to thnh mt heap vij=(n div 2 +1).
5.6.4. Gii thut Heapsort :
Gii thut Heapsort tri qua 2 giai on :
Giai on 1 :Hiu chnh dy s ban u thnh heap;
Giai on 2: Sp xp dy s da trn heap:
Bc 1: a phn t ln nht v v tr ng cui dy:
r = n; Honv (a1 , ar );
Bc 2: Loi b phn t ln nht ra khi heap: r = r-1;
44
8/3/2019 GT Cau truc du lieu
45/64
Cu trc d liu v gii thut Ng Hu Phc
Hiu chnh phn cn li ca dy t a1 , a2 ... ar thnh mt heap.
Bc 3: Nu r>1 (heap cn phn t ): Lp li Bc 2
Ngc li : Dng
Da trn tnh cht ca Heap ta c th thc hin giai on 1 bng cch
bt u t heap mc nhin an/2+1 , an/2+2 ... an, sau thm dn cc phn t an/2,
an/2-1, ., a1 ta s nhn c heap theo mong mun.
// Heap sort Mang a bat dau tu 1
void Shift (int *a, int trai, int phai )// hieu chinh
{ int x,i,j;
i = trai; j =2*i; // (ai , aj ), (ai , aj+1) l cc ph?n t? lin ??i
x = a[i];
while (j
8/3/2019 GT Cau truc du lieu
46/64
Cu trc d liu v gii thut Ng Hu Phc
}
void HeapSort (int *a, int N)// N chi so ben phai cung
{ int r;
CreateHeap(a,N);
r = N; // r l v? tr ?ng cho ph?n t? nh? nh?t
while(r > 0)
{
Hoanvi(&a[1],&a[r]);
r = r -1;
Shift(a,1,r);}
}
46
8/3/2019 GT Cau truc du lieu
47/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 6. CU TRC CY.6.1. Khi nim v cy.
6.1.1. nh ngha:
Mt cy l mt tp hp hu hn cc nt, trong c mt nt c bit gi l nt gc,
gia cc nt c quan h phn cp cha-con.
C th nh ngha cy mt cch qui nh sau:
1/ Mt nt l mt cy v chnh l nt gc ca cy ny.
2/ Nu T1, T2,Tk l cc cy vi cc nt gc l n1, n2,, nk. Gi s n0 l
mt nt c cc nt con l n1, n2,, nk th ta s c cy T vi nt gc l n0.
Qui c cy khng c mt nt no c l cy rng
Cc ng dng ca cy:
+ Biu din cy th mc
+ Biu din cc tp bao nhau
+ Biu din biu thc s hc
6.1.2. Cc khi nim:
Bc ca mt nt : l s con ca nt .
Bc ca mt cy : l bc ln nht ca cc nt trong cy ( s cy con ti a ca
47
8/3/2019 GT Cau truc du lieu
48/64
Cu trc d liu v gii thut Ng Hu Phc
mt nt trong cy ). Cy c bc n th gi l cy n-phn.
Nt gc : nt khng c nt cha
Nt l : khng c nt con - nt bc 0.
Nt nhnh : l nt c bc khc 0 v khng phi l gc.
Mc ca mt nt :
+ Mc (gc(T))=0.
+ Gi T1,T2,T3,.,Tn l cy con ca T0.
Mc (T1)=Mc(T2)=Mc(T3)=.=Mc(Tn)=Mc(T0)+1.
Chiu cao ca mt nt: L di ng i t nt n nt l xa nht.
su ca mt nt (mc ca mt nt): L chiu di ng i t nt gc nnt .
Chiu cao ca mt cy: L chiu cao ca nt gc.
Nhn xt
Trong cu trc cy khng tn t chu trnh.
T chc mt cu trc cy cho php truy cp nhanh n cc phn t ca
n.
6.1.3. Cy c gc:
nh ngha: Trong mt cy, nu ta chn mt nh c bit gi l gc ca
cy v nh hng cc cnh trn cy c hng t gc i ra th ta c mt th c
hng gi l cy c gc.
Ch : Cng mt cy, nu ta chn gc khc nhau th cy c gc thu c s
khc nhau.V d
a
b
df
g
h
a
a
b b
c
cc
d
d
f
f
g gh h
ee
e
48
8/3/2019 GT Cau truc du lieu
49/64
Cu trc d liu v gii thut Ng Hu Phc
T1 T2 T3
6.1.4. Cy c th t:
Nu ta phn bit th t cc nt con ca cng mt nt th cy gi l cy c th
t, th t qui c t tri sang phi. Nh vy, nu k th t th hai cy sau l hai cykhc nhau:
Trong trng hp ta khng phn bit r rng th t cc nt th ta gi l cy
khng c th t. Cc nt con cng mt nt cha gi l cc nt anh em rut (siblings).
Quan h "tri sang phi" ca cc anh em rut c th m rng cho hai nt bt k theo
qui tc: nu a, b l hai anh em rut v a bn tri b th cc hu du ca a l "bn tri"
mi hu du ca b.
6.2. Cy nh phn.
6.2.1. Cc khi nim c bn.
nh ngha:
Cy nh phn l mt cu trc cy c c im mi nt c ti a 2 nt con.
Tnh cht:
(1) S lng ti a cc nt mc i trn cy NP l 2i
CM: i=0 => c ti a 1 nt ng
I=1 => c ti a 2 nt ng
Gi s ng vi i-1 => c 2i-1 nt
Cn chng minh ng vi i: mc i -1 c 2 i-1 nt, vi cy NP mi nt c ti a
2 nt con => mc i c ti a 2.2i-1 = 2i (pcm)
(2) S lng ti a cc nt trn cy NP c chiu cao h l 2(h+1)-1 (h>=0)
T (1)=> s nt ti a trn cy c chiu cao h l
20+21+ ...+ 2h=a1* (1-qn)/(1-q)=20*(1-2h+1)/(1-2)=2(h+1)-1
49
8/3/2019 GT Cau truc du lieu
50/64
Cu trc d liu v gii thut Ng Hu Phc
6.2.2. Biu din cy nh phn.
+) Dng mng biu din cy nh phn
nh s cc nt theo chiu t tri sang phi, t trn xung di ta thy xut
hin qui lut sau: Con ca nt th i l cc nt v tr 2*i v 2*i+1.Cha ca nt j l nt v tr j div 2
=> c th lu tr cy NP bng mng
VD:
Hn ch: vi cy NP khng y mng s rng nhiu.
+) Dng danh sch mc ni
struct NODE
{ int Key;
struct NODE *pLeft, *pRight;
};
NODE *Root;void init(NODE **Root)
50
8/3/2019 GT Cau truc du lieu
51/64
Cu trc d liu v gii thut Ng Hu Phc
{
*Root=NULL;
}
6.3. Thm cc nt trn cy.
6.3.1. Thm cc nt trn cy theo th t trc (Node-Left-Right).
void NLR(NODE *r)
{ if (r != NULL)
{ printf ("%d--",r->Key );
NLR(r->pLeft);
NLR(r->pRight);
}
}
6.3.2. Thm cc nt trn cy theo th t gia (Left- Node -Right).
void LNR(NODE *r)
{ if (r != NULL)
{ LNR(r->pLeft);printf ("%d--",r->Key );
LNR(r->pRight);
}
}
6.3.3. Thm cc nt trn cy theo th t sau (Left-Right-Node).
void LRN(NODE *r){ if (r != NULL)
{ LRN(r->pLeft);
LRN(r->pRight);
printf ("%d--",r->Key );
}
}
6.4. Bi tp.
51
8/3/2019 GT Cau truc du lieu
52/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 7. CY NH PHN TM KIM.7.1. Khi nim cy nh phn tm kim.
nh ngha: Cy nh phn tm kim (CNPTK) l cy nh phn trong ti mi nt, kha ca ntang xt ln hn kha ca tt c cc nt thuc cy con tri v nh hn kha ca tt c cc ntthuc cy con phi.
Di y l mt v d v cy nh phn tm kim:
Nh rng buc v kha trn CNPTK, vic tm kim tr nn c nh hng.
Hn na, do cu trc cy vic tm kim tr nn nhanh ng k. Nu s nt trn cy l
N th chi ph tm kim trung bnh ch khong log2N.
Trong thc t, khi xt n cy nh phn ch yu ngi ta xt CNPTK.
7.2. Tm mt phn t x trong cy.
NODE* searchNode(NODE *r, int X)
{
if(r!=NULL){
if(r->Key == X) return r;
if(r->Key > X)
return searchNode(r->pLeft, X);
else
return searchNode(r->pRight, X);
}return NULL;
52
8/3/2019 GT Cau truc du lieu
53/64
Cu trc d liu v gii thut Ng Hu Phc
}
Kh qui
NODE *searchNode1(NODE *r, int x)
{ NODE *p;
p = r;
while (p != NULL)
{
if(x == p->Key) return p;
else
if(x < p->Key) p = p->pLeft;
else p = p->pRight;}
return NULL;
}
D dng thy rng s ln so snh ti a phi thc hin tm phn t X l h, vi h l chiucao ca cy. Nh vy thao tc tm kim trn CNPTK c n nt tn chi ph trung bnh khongO(log2n) .
V d: Tm phn t 55
7.3. Thm mt phn t x vo cy.
Vic thm mt phn t X vo cy phi bo m iu kin rng buc ca
CNPTK. Ta c th thm vo nhiu ch khc nhau trn cy, tuy nhin thm vo mt
nt l s l d thc hin nht, do ta c th thc hin qu trnh tng t thao tc tmkim. Khi chm dt qu trnh tm kim cng chnh l lc tm c ch cn thm.
53
8/3/2019 GT Cau truc du lieu
54/64
Cu trc d liu v gii thut Ng Hu Phc
Hm insert tr v gi tr 1, 0, 1 khi khng b nh, gp nt c hay thnh
cng:
int insertNode(NODE **r, int X)
{ if((*r)!=NULL){ if((*r)->Key == X)return 0;
if((*r)->Key > X)
return insertNode(&((*r)->pLeft), X);
else
return insertNode(&((*r)->pRight), X);
}
(*r) = new NODE();
if((*r) == NULL) return -1;
(*r)->Key = X;
(*r)->pLeft =NULL; (*r)->pRight = NULL;
return 1;
}
7.4. Xa nt trn cy.Vic hy mt phn t X ra khi cy phi bo m iu kin rng buc ca
CNPTK.
C 3 trng hp khi hy nt X c th xy ra:
X - nt l.
X - ch c 1 cy con (tri hoc phi).
X c c 2 cy con
Trng hp th nht: ch n gin hy X v n khng mc ni n phn t no khc.
Trng hp th hai: trc khi hy X ta mc ni cha ca X vi con duy nht ca n.
Trng hp cui cng: ta khng th hy trc tip do X c 2 con Ta s hy gin
tip. Thay v hy X, ta s tm mt phn t th mng Y. Phn t ny c ti a mt con.
Thng tin lu ti Y s c chuyn ln lu ti X. Sau , nt b hy tht s s l Y
ging nh 2 trng hp u.
Vn l phi chn Y sao cho khi lu Y vo v tr ca X, cy vn l CNPTK.
C 2 phn t tha mn yu cu:
54
8/3/2019 GT Cau truc du lieu
55/64
Cu trc d liu v gii thut Ng Hu Phc
Phn t nh nht (tri nht) trn cy con phi.
Phn t ln nht (phi nht) trn cy con tri.
// Remove mot nut
void searchFor(NODE **p, NODE **q)
{
if( (*q)->pLeft!=NULL )
searchFor(p, &((*q)->pLeft) );
else
{ (*p)->Key= (*q)->Key;
*p=*q;// nut can xoa
*q = (*q)->pRight;}
}
int delNode(NODE **r, int X)
{
if((*r)==NULL) return 0;
if((*r)->Key > X)
return delNode ( &((*r)->pLeft), X);if((*r)->Key < X)
return delNode (&((*r)->pRight), X);
else
{ //T->Key == X
NODE *p = *r;
if((*r)->pLeft == NULL)
(*r) = (*r)->pRight;
else if((*r)->pRight == NULL)
(*r) = (*r)->pLeft;
else
{ searchFor(&p, &((*r)->pRight)); }
delete p;
}
}
55
8/3/2019 GT Cau truc du lieu
56/64
Cu trc d liu v gii thut Ng Hu Phc
7.5. Cy biu thc.
V d : Cy sau y s biu din cho biu thc (a + b) * (a - c)
Trong cy trn th n1, n2,..., n7 l cc tn nt cn *, +, -, a, b, c l cc
nhn ca nt.
Mi nt l s biu din cho mt ton hng n c.
Mi nt trung gian s biu din cho mt ton t. Gi s nt n biu din
cho ton t 2 ngi, nt con bn tri biu din cho biu thc E1, nt con bn
phi biu din cho biu thc E2 th nt n s biu din cho biu thc E E2
Thm cc nt trn cy theo th t trc cho chng ta biu thc tin t (Prefix),
Theo th t gia cho chng ta biu thc trung t (Infix)
V theo th t sau cho chng ta biu thc hu t (Postfix) ca biu thc ton
hc ban u.
V d: i vi cy biu thc c cho v d trn, ta c:
+ Biu thc tin t : * + a b - a c.
+ Biu thc trung t : a + b * a - c.
+ Biu thc hu t : a b + a c - *.
7.6. Cy quyt nh:
Cy biu din li gii ca bi ton thng qua nhiu la chn gi l cy quyt
nh. V d:
56
8/3/2019 GT Cau truc du lieu
57/64
Cu trc d liu v gii thut Ng Hu Phc
57
8/3/2019 GT Cau truc du lieu
58/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 8. CC PHNG PHP TM KIM8.1. Bi ton tm kim.
Bi ton tm kim c m t nh sau: Hy xc nh v tr ca phn t x trong
mt bng lit k cc phn t phn bit x1, x2, x3, , xn hoc xc nh n khng c
mt trong bng lit k .
Li gii ca bi ton l v tr xut hin ca x trong bng lit k hoc a ra
thng bo l x khng c trong bng.
8.2. Tm kim tun t.
Tm kim tun t l phng php tm kim n gin v t nhin nht, phng
php ny thng c nhiu ngi s dng, nht l trong trng hp tm kim trn
file. Tuy vy tc tm kim ca phng php ny thng rt chm.TTon: TTon bt u bng vic so snh phn t cn xc nh Item vi phn
u tin x1, nu cha thy th so snh vi cc phn t k tip cho n khi tm ra phn
t cho hoc l t n phn t cui cng ca danh sch.
8.3. Tm kim nh phn.
8.3.1. Tm kim nh phn trn cu trc mng
Mun thc hin tm kim nh phn th trc ht chng ta phi sp xp d liuu vo (gi s sp xp tng dn).
TTon:
B1: Phm vi tm kim l ton b danh sch.
B2: So snh phn t cn xc nh Item vi phn t chnh gia ca phm vi
tm kim (gi l x).
Nu: Item> x th phm vi tm kim mi s l cc phn t sau ca x.
Nu: Item< x th phm vi tm kim mi s l cc phn t trc ca x.
Nu: Item=x th thng bo l tm thy, kt thc chng trnh.
B3: Nu tn ti phm vi tm kim th lp li bc 2, ngc li th kt thc
chng trnh v thng bo l khng tm thy.
int Binary_Search(int *a, int n, int Item)
{ int last, first, mid;
bool found;
found=false;
58
8/3/2019 GT Cau truc du lieu
59/64
Cu trc d liu v gii thut Ng Hu Phc
first=0; last=N-1;
while ((!found)&&(firstItem)
last=mid-1;
else
if (Item>a[mid])
first =mid+1;
else
{ found=true;
return mid;
}
}
return -1;
}
BT1: Lit k cc bc tm kim s 9 trong dy:
1, 3, 4, 5, 6, 8, 9, 11
8.3.2. Tm kim trn cy nh phn (trong phn CNPT)
8.4. Tm kim da vo gi tr kha
8.4.1. Hm bm.
Trong hu ht cc ng dng, kho c dng nh mt phng thc truy
xut d liu mt cch gin tip. Hm bm l hm c dng nh x mt kho vo
mt a ch trn bng bm.
Chng ta gi h(k) l gi tr hm bm ca kha k. Trng hp h(ki) =h(kj) th
hm bm b ng , khi ta phi x l thm sao cho vn lu tr c ia ch
ring bit ca cc bn ghi c kha ki v kj.
8.4.2. Hm bm kiu chia
L hm c tnh ton d trn pha chia ly phn d h(k)= k mod m, m l mts nguyn t.
59
8/3/2019 GT Cau truc du lieu
60/64
Cu trc d liu v gii thut Ng Hu Phc
Nh vy k s nhn cc gi tr 0, 1, 2,, m-1.Vd: m=7; k=10-> h(k)= 10 mod
7= 3
8.4.3. Hm bm kiu nhn
Gi tr kha c nhn vi chnh n.Vd:
S th t K H(k) Ly 3 ch s u tin
1 11 121
2 111 123
8.5. Cc phng php khc phc ng
C nhiu phng php khc nhau khc phc ng , tuy nhin chung ta c
th chia chng thnh 2 loi:
(1) Phng php a ch m: Da trn nguyn tc nh sau: vi a ch bn
th ngi ta tm cc a ch cn trng ngay tip sau thay th.
(2) Phng php mc xch: Cc bn ghi xy ra ng c lu vo mt danh
sch tuyn tnh.8.5.1. Phng php a ch m
*) Phng php th tuyn tnh
Gi s x l kha m ta cn xc nh a ch trong bng bm.
h0 = h(x) nu h0 bn th ta tm cc a ch tip theo hi=(h0+i) mod m vi
i=1,2,..
Khi n cui bng m vn cha tm c a ch trng th quay v u
bng, tm tip cho n khi thy a ch trng hoc quay v ng a ch ban u =>
bng bm trn.
vd: cho cc kha k[i]=140, 122, 178, 110, 160, 147, 291, 182,300,305
m=7
h(ki) mod 7 =0, 3, 3, 5,6,0,4,0,6,4
0 140
1 1472 182
60
8/3/2019 GT Cau truc du lieu
61/64
Cu trc d liu v gii thut Ng Hu Phc
3 122
4 178
5 110
6 1607 291
8 300
9 305
Nxt:
Bng bm ny ch ti u khi bm u, ngha l, trn bng bm cc khi ccha vi phn t v cc khi cha s dng xen k nhau, tc truy xut lc ny c
bc 0(1). Trng hp xu nht l bm khng u hoc bng bm y, lc ny hnh
thnh mt khi c c n phn t, nn tc truy xut lc ny c bc 0(n).
*) Phng php cu phng
h0=h(x) = x mod m;
Nu h0bn th cc a ch tip theo s c xt: hi=( h0+i) mod m;i =1,2,.., m
div 2.Nhc im:
C th xy ra trng hp c (m div 2) a ch th u bn => bng bm trn,
tuy nhin l trong bng bm vn cn a ch trng.
8.5.2. Phng php mc xch
*) Phng php mc ni ngoi
#define M 100struct node
{
int key;
struct node *next
};
//khai bao kieu con tro chi nut
Node * hashTable[M]
61
8/3/2019 GT Cau truc du lieu
62/64
Cu trc d liu v gii thut Ng Hu Phc
*) Phng php mc ni trong
Ch dng khng gian a ch c ca bng bm (khng cp php thm nh
trong phng php mc ni ngoi).
Thm kha x: nu h(x) cn trng th thm vo a ch ny v n s l a ch
u tin ca danh sch mc ni.
Nu h(x) bn th xy ra 2 kh nng:
(gi k l kha hin din ti a ch h(x))
- Nu h(k)=h(x) => kha x s thuc danh sch lin kt c nt u tinti h(k). Tm kha x trong danh sch ny: Nu thy php tm kim
tha mn. Nu khng thy x th phi tm mt a ch trng (d tun t)
thm kha x vo v b sung x vo danh sch lin kt.
- Nu h(k)h(x) => Ta phi tm trng a kha k sang . Ch
phi iu chnh cc con tr ti n v xut pht t n. a kha x vo
v tr h(x).
8.6. ng dng ca hm bm- Trong bo mt thng tin: M ha RSA, ch k s
PP m ho RSA:
Chn 2 s nguyn t p,q ln, N=p*q;
Chn s nguyn t E (1
8/3/2019 GT Cau truc du lieu
63/64
Cu trc d liu v gii thut Ng Hu Phc
P=5; Q=11; chn E=7; Tnh D theo cng thc
E*D=1 (mod (p1-)*(q-1))= 1 (mod 40)
7 * D = 1 (mod 40)
7 * D = K * 40 + 1, K l mt s no
Chn K=4 -> D=23
7 * 23 = 161 = 4 * 40 + 1
E l kha cng khai dng m ha, D l kha ring (b mt) dng gii m
Tin hnh m ha, gii m hai s 31 v 7
M ha: 31^7 (mod 55) = 27512614111 (mod 55) =26
7^7 (mod 55) = 823543 (mod 55) =28
Gii m:26^23 (mod 55) =
350257144982200575261531309080576 (mod 55) =31
28^23 (mod 55) =
1925904380037276068854119113162752 (mod 55) = 7
Ch k s:
Gi s c mt cng ty bun bn qu cho php nhn n hng qua Internet,
c cc yu cu sau:+Ch cng ty mi c kh nng nhn n hng. (khch hng mun n hng
ca h c gi b mt)
+Cng ty c th kim tra chnh xc mt n hng c phi ca khch hng X
hay khng.
Cch thc hin:
Mi khch hng X chn mt eX lm m cng khai, dX m b mt.
Cng ty cng chn eC v dC
Vi yu cu 1: X s m ha H bng eC Cty gii m bng dC
Vi yu cu th 2: X s m ha bng dX, sau li m tip bng eC Cty
gii m bng dC, sau bng eX.
- S dng hm bm to cc file ch s trong h qun tr CSDL SQL Server v
Oracle.
63
8/3/2019 GT Cau truc du lieu
64/64
Cu trc d liu v gii thut Ng Hu Phc
Bi 9. Cy cn bng
Bi 10. Mt s thut ton nn
10.1. Run Length
10.2. Huffman
10.3. LZ77,LZ78
10.4. LZW