Professional Documents
Culture Documents
ĐẠI CƯƠNG VỀ LẬP TRÌNH
ĐẠI CƯƠNG VỀ LẬP TRÌNH
P
a
g
e
1
CHNG I I CNG V LP TRNH
I. KHI NIM THUT TON:
I.1. Khi nim:
Thut to|n l{ tp hp c|c quy tc c logic nhm gii mt lp b{i to|n n{o
c mt kt qu x|c nh.
I.2. Cc tnh cht c trng ca thut ton :
I.2.1. Tnh tng qut :
Thut to|n c lp khng phi ch gii mt b{i to|n c th m{ thi m{ cn phi
gii c mt lp c|c b{i to|n c dng tng t.
I.2.2. Tnh gii hn :
Thut to|n gii mt b{i to|n phi c thc hin qua mt s gii hn c|c thao t|c
t n kt qu.
I.2.3. Tnh duy nht :
Ton b qu| trnh bin i, cng nh trt t thc hin phi c x|c nh v{ l{
duy nht. Nh vy khi dng thut to|n cng mt d liu ban u phi cho cng mt kt
qu.
I.3. Phn loi:
Theo cu trc, ta c th ph}n th{nh ba loi thut to|n c bn sau :
- Thut to|n khng ph}n nh|nh.
- Thut to|n c ph}n nh|nh.
- Thut to|n theo chu trnh c bc lp x|c nh v{ c bc lp khng x|c nh.
II. M T THUT TON BNG LU :
II.1. Lu :
Lu l{ mt dng th dng m t qu| trnh tnh to|n mt c|ch c h
thng. Ngi ta thng th hin thut to|n bng lu .
II.2. Cc k hiu trn lu :
Tn khi K hiu ngha
Khi m u hoc kt thc
Dng m u hoc kt thc
chng trnh
Khi v{o ra
a s liu v{o hoc in kt
qu
Khi tnh to|n
Biu din c|c cng thc tnh
to|n v{ thay i gi| tr ca
c|c bin
Khi iu kin
Dng ph}n nh|nh chng
trnh
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
2
Chng trnh con
Dng gi chng trnh
con
Mi tn
Ch hng truyn thng tin,
lin h c|c khi
II.3. Mt s v d biu din thut ton bng lu
II.3.1. Thut ton khng phn nhnh:
V d 1: Tnh A = x
2
+ y
2
V d 2 : Tnh
y
x
C By Ax
S
2
2
+
+ +
= ; bit A,B,C,x,y pow(x,n)
II.3.2. Thut ton c phn nhnh:
V d 1: Tm gi| tr max ca ba s thc a,b,c
Begin
Nhap (x,y)
A = x
2
+ y
2
Xuat (A)
End
Begin
Nhap (A, B, C, x,y)
S = (Ax + By + C) / SQRT (x*x + y*y)
Xuat S
End
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
3
V d 2: Gii phng trnh bc nht Ax+B =0 vi c|c nghim thc.
V d 3 : Gii phng trnh bc hai Ax
2
+Bx+C =0 vi c|c nghim thc.
Begin
Nhap (a, b, c)
Max = a
Xuat (Max)
End
a > b
Max < c
Max = c
S
S
Max = b
Begin
Nhap (a, b)
Xuat ( PTV )
End
a = 0
S
S
Xuat (-b/a)
b = 0 Xuat ( PTVN )
PTB1 (b, c)
Delta < 0 Xuat ( PTVN )
S
S
Delta = b*b - 4*a*c
Delta = 0
Xuat (-b / (2*a))
S
II.3.3. Thut ton c chu trnh:
Thut to|n c chu trnh vi c|c bc lp x|c nh thng c th hin bng lu
sau :
vi n l{ gi| tr kt thc.
i = giatrban au
Lenh S;
Tang i
i <= n
S
1
, vi c|c xi do ta nhp v{o.
III. CC NGN NG LP TRNH & CHNG TRNH DCH:
III.1. Ngn ng lp trnh:
III.1.1. Gii thiu: Con ngi mun giao tip vi m|y tnh phi thng qua ngn
ng. Con ngi mun m|y tnh thc hin cng vic, phi vit c|c yu cu a cho m|y
bng ngn ng m|y hiu c. Vic vit c|c yu cu ta gi l{ lp trnh (programming).
Ngn ng dng lp trnh c gi l{ ngn ng lp trnh.
Nu ngn ng lp trnh gn vi vn cn gii quyt, gn vi ngn ng t nhin
th vic lp trnh s n gin hn nhiu. Nhng ngn ng lp trnh c tnh cht nh trn
c gi l{ ngn ng cp cao. Nhng m|y tnh ch hiu c ngn ng ring ca mnh,
l{ c|c chui s 0 vi 1 v{ nh vy r r{ng l{ kh khn cho lp trnh vin, v n khng
gn gi vi con ngi.
Hin ti, ngn ng lp trnh c chia ra l{m c|c loi sau:
III.1.2. Phn loi ngn ng lp trnh:
- Ngn ng m|y (machine language)
- Hp ng (assembly language)
- Ngn ng cp cao (higher-level language)
Do m|y tnh ch hiu c ngn ng m|y, cho nn mt chng trnh vit trong
Begin
Nhap (n)
i = 1
S = 0
Nhap (x
i
)
End
i = i+1
S = S+x
i
i <= n
Xuat (S)
S
1
; i, j = 1..n
5. To mt menu thc hin c|c cng vic sau:
a. Nhp danh s|ch c kiu hc vin v{o mt mng, mi hc vin c cc thng tin sau:
maso (int), hoten (chui ti a 30 k t), ph|i(NAM/NU), im (float), hng
(unsigned char). Qu| trnh nhp s dng li khi m~ s nhp v{o l{ 0.
b. Lit k danh s|ch hc vin ra m{n hnh theo dng sau:
M~ s H v{ tn Phi im Hng
c. Tm kim mt hc vin trong danh s|ch theo m~ s, v{ in ra c|c thng tin cn li
ca hc vin .
d. Sp xp danh s|ch hc vin theo im tng dn.
e. Xp hng danh s|ch hc vin theo qui tc cng im th cng hng, hng ca hc
vin sau bng hng ca nhm hc vin trc cng s ngi ca nhm hc vin trc
cng im.
f. Gi s danh s|ch hc vin ~ c th t tng dn theo im; Nhp thm 1 hc vin
sao cho sau khi nhp th danh s|ch vn cn c th t.
g. Cp nht sa i c|c mu tin theo m~ s (Nhp m~ s, sau hiu chnh li hoten,
phai, im).
h. Loi b 1 hc vin ra khi danh s|ch da v{o m~ s.
6. a) Vit chng trnh to ngu nhin mt d~y s 20000 s nguyn c gi| tr t 0 n
9999.
b) m s ln so s|nh ca 2 gii thut tm kim tun t (trn d~y s cha c th t)
v{ tm kim nh ph}n (trn d~y s ~ c sp th t).
c) Trong trng hp d~y s trn l{ 200000 s nguyn ph}n bit kh|c nhau trong
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
7
8
min gi| tr [1..300000] th ta ti u gii thut sp xp v mt khng gian v{ thi
gian nh th n{o? Cho bit thi gian thc thi ca gii thut Quick Sort v{ gii thut
bn c{i t.
7. Cho bit thi gian thc thi ca 2 gii thut Bubble Sort v{ Quick Sort trn d~y s c s
phn t kh| ln.
8. Gi s ta ~ c 1 d~y s thc A tng dn. Vit gii thut thm 1 s thc x v{o d~y A sao
cho sau khi thm x th d~y vn tng dn ?
9. Vit h{m xa tt c c|c phn t c tr bng x trong d~y s A.
10. Vit chng trnh tnh im ca mt lp:
- Nhp c|c thng tin sau cho mi hc vin : hoten, namsinh, trung bnh HK1,
trung bnh HK2
- In ra danh s|ch c|c hc vin ca lp theo th t gim dn ca TB to{n nm
TB to{n nm = (TB HK1 + TB HK2)/2
theo mu sau:
DANH SCH IM LP ......
STT H & Tn TB HK1 TB HK2 TB ton
nm
Hng
1
2
3
Lu :- C|c hc vin cng TB th cng hng
- In 17 hc vin trn mt trang m{n hnh
11. Cho 2 d~y s A c n phn t v{ B c m phn t vi th t tng dn. H~y trn 2 d~y s
trn th{nh 1 d~y mi C sao cho sau khi trn th C cng tng dn.
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
7
9
CHNG 4 CON TR (POINTER)
I. NH NGHA
Con tr l{ mt kiu d liu dng cha a ch. Bin con tr l{ mt bin cha a ch
ca mt thc th n{o , thc th l{ bin hoc l{ h{m.
Con tr thng c dng :
- Tr v nhiu tr t h{m qua c ch truyn theo tham s theo a ch trong h{m
(tham s hnh thc bin).
- To c|c cu trc d liu phc tp nh danh s|ch lin kt v{ c}y nh ph}n.
- Truyn mng v{ chui gia c|c h{m kh| thun li.
I.1. Khai bo: Khai b|o bin pi l{ con tr tr n mt s nguyn.
int *pi;
Lc n{y, pi chim 2 bytes cha a ch ca s nguyn m{ n ang ch n, ng
thi trnh bin dch ca C cng bit pi ang ch n mt s nguyn (do khai b|o).
a mt gi| tr nguyn v{o vng nh m{ pi ang tr n, ta dng lnh: *pi = 1;
V d:
void main()
{ int x=4, y=10;
int *px, *py ; // px, py l{ c|c bin con tr
px = &x ; // a a ch ca x,y v{o px v{ py
py = &y;
*px = *px + *py; // tng gi| tr ca vng nh m{ px ang tr ti
// thm y , tng ng vi x = x+y
}
Minh ha chng trnh trn trong b nh:
Bin int x=4, y=10;
int *px, *py;
px=&x;
py=&y;
*px = *px + *py;
x 950 4 4 14
951
y 952 10 10 10
953
px 950 950
py 952 952
Hnh 7.1. C ch truy xut gi| tr qua bin con tr.
Tng qu|t: Kiu *bin;
I.2. Truyn a ch cho hm: Trong 1 s trng hp ta mun gi a ch ca 1 bin x
cho h{m. Nh v{o c ch truyn theo a ch n{y m{ h{m c th tr v nhiu gi| tr cho
chng trnh gi.
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
0
V d: H{m ho|n i gi| tr ca 2 bin x, y
void hoandoi (int *a, int *b)
{ int tam;
tam = *a;
*a = *b;
*b = tam;
}
void main()
{ int x,y;
printf ("x, y = ");
scanf ("%d %d", &x, &y);
giaohoan(&x, &y); // Truyn a ch ca 2 bin x,y cho h{m hoandoi
}
II CC PHP TON TRN BIN CON TR:
II.1. Ton t a ch &:
Nu x l{ bin thng thng, &x s l{ a ch ca bin x
V d: float x, *pf;
x = 50;
pf = x; // sai v pf l{ bin con tr nn ta vit pf = & x;
x = pf; // sai ; ta vit x = *pf; { ly ni dung ca pf }
II.2. Ton t ni dung * :
Nu p l{ pointer th *p l{ ni dung ca n.
V d: int x,y, *p;
x = 50;
p = &x; // p cha a ch ca vng nh x
y = *p; // y= *p = 50 v p cha a ch ca vng nh x
V d: a =2;
p = & a;
b = (*p) + + + 3; // b =5, *p = 3, a= 3.
( v p tr ti a ch a nn *p tng th a tng)
Tm li: *x l{ bin m{ x gi a ch
&x l{ a ch ca x nu x l{ bin thng thng
II.3. Php cng tr bin con tr vi mt s nguyn:
Nu p l{ bin pointer th p+n l{ a ch ca mt bin mi c|ch n n bin theo chiu
tng, cn p-n th ngc li.
Ch :
- Php cng con tr vi mt s nguyn ch c |p dng trn mt d~y bin cng
kiu
- Khng c cng 2 pointer vi nhau
- Khng c nh}n, chia, ly d bin con tr vi bt k s n{o
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
1
V d: Gi s ta c mng nums[]= {10,20,30,40,50}. Vic tham kho ti nums[i]
thc cht l{ dng dng k hiu con tr, v khi bin dch, trnh bin dch s chuyn i k
hiu mng th{nh k hiu con tr.
void main()
{ static int nums [] = {10,20,30,40,50};
for (int i =0; i<5; i++)
printf (%d\n, *(nums + i));
}
Lu : *(nums+i) tng ng vi nums[i]
II.4. Php gn v php so snh:
- Php gn: c|c bin con tr c th g|n cho nhau vi iu kin phi cng kiu
V d: int *p1, *p2;
*p1 = 10;
p2 = p1; // lc ny *p2 = 10;
- Php so snh: ta c th so s|nh 2 bin con tr xem c cng a ch hay khng,
ng nhin 2 bin con tr phi cng kiu vi nhau.
II.5. S chuyn kiu:
C php: ( Kiu) *tnbin
V d: int *p1, num ;
float *p2;
num =5;
p1 = #
*p2 = (float ) *p1; // * p2 = 5.0
V d: int num, *p, n;
char c;
p = #
*p = 97; // num =97
n = *p; // n=97
c = (char) *p; // c = a
Ch : a ch ca mt bin c xem nh mt con tr hng, do n khng c
php g|n, tng hoc gim.
V d: int num, *p, n;
p = & num;
p ++; // ng
( & num) ++; // sai
con tr hng
II.6. Khai bo mt con tr hng v con tr ch n i tng hng:
a. Con tr hng:
Kiu * const p = gi| tr;
b. Con tr ch n i tng hng:
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
2
Kiu const *p = gi| tr hng;
hoc Const kiu *p = gi| tr hng;
V d: char *const p2 = ABCD
const char *p1= ABCD
p2 + + ; // sai
p1 + + ; // ng; *p1= B ; p1 = "BCD"
III. S TNG QUAN GIA CON TR V MNG
V d: Ta c mng A nh sau:
int A[10] , *p;
th A = &A[0]
Nu p = A th truy xut ti phn t th i ca mng A, ta c c|c c|ch sau:
A[i] *(A + i) *( p + i)
& A[i] (A + i) (p +i )
V d: Nhp mng A:
int A[10] , *p, i;
p = A;
for (i = 0; i< 9; i++)
scanf (%d, p+i );
Xut mng A:
for (i = 0; i< 9;i++)
printf (%d, *(p+i));
V d: Sp xp mng bng c|ch tham kho con tr.
const n =10 ;
int a[n], *p;
void main()
{ int j,temp;
clrscr();
p=a;
printf("\Nhap day so A :\n");
for (int i=0; i<n; i++)
{ printf("A[%d] = ",i+1);
scanf("%d",p+i);
}
// Sap xep mang A theo giai thuat Bubble Sort
for ( i=1; i<n; i++)
for (j=n-1; j>=i; j--)
if (*(p+j-1) > *(p+j))
{ temp = *(p+j);
*(p+j) = *(p+j-1);
*(p+j-1) = temp;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
3
}
printf("\n Mang A sau khi sap xep :\n");
for ( i=0; i<n; i++)
printf("%8d",*(p+i));
}
* i vi mng 2 chiu:
Nu ta khai b|o : Kiu a [10] [20] , *p; th mng a c dng:
a 0 1 2 3 ..... 18 19
0
1
2
3
a[i]
.
9
Nhn xt:
a = &a[0][0] = &a[0]
a[i] = &a[i][0]
a[i][j] ni dung ca i.j
Vi p = a th truy xut ti a[i][j] :
a[i][j] = *(*(p+i) +j)
& a[i][j] = (*(p+i) +j)
V d:Nu ta c int a[4][5] =
{ {1,2,3,4,5}, {2,3,4,5,6}, {3,4,5,6,7} , {4,5,6,7,8}} ;
th :
- a l{ a ch ca to{n b mng (gi s l{ 1000)
- Do a l{ mng nguyn nn mi phn t chim 2 bytes, v{ mi dng ca mng s
chim 10 bytes.
- Trnh bin dch ca C bit s ct (do khai b|o) nn n s hiu a+1 l{ em 1000 +
10 bytes, kt qu l{ 1010 l{ a ch ca dng th 2 trong a. Tng t, 1020 l{ l{ a
ch ca dng th 3 trong a.
a 0 1 2 3 4
1000 1 2 3 4 5
1010 2 3 4 5 6
1020 3 4 5 6 7
1030 4 5 6 7 8
Lc n{y: a[1] hay a+1 l{ a ch ca dng th 2 trong mng 2 chiu a.
Ta c : *(a+1) == 1010 // a ch ca phn t u tin trn dng 1
*(a+1)+3 == 1016 // a ch ca phn t c ch s 3 trn dng 1
*(*(a+1)+3)==5 // ni dung ca phn t a[1][3]
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
4
Tm li: a[i][j] = *(*(a+i)+j)
Ta cn c mt c|ch kh|c truy xut ti a[i][j] :
Nu : Kiu a[n0 ] [n1 ] ... [nm] , *p;
p = a;
th a [i0] [i1]... [im] = *(*(*(p+i0) + i1) + ...im)
Ch :
1. S khc nhau gia con tr v mng:
- Bin con tr th c th tng, gim hoc g|n cn bin mng l{ mt con tr hng do
khng th tng, gim hoc g|n.
- Ta c th ly a ch ca con tr nhng khng th ly a ch ca mng v bn th}n
mng ~ l{ a ch.
- Khi ta khai b|o mt mng th chng trnh dch s cp ph|t mt vng nh cho n.
V d 1: Kiu a[50]
Trong b nh :
0 1 2 49
a
- Bin con tr khi c khai b|o th ch c cp mt nh m{ ni dung ca n
chng bit ch n }u
V d 2: a[1] x|c nh th{nh phn th 2
p+1 : ni dung khng x|c nh
phi c p = a p ch ti a
- Nu ta mun to mt mng bng con tr th ta phi xin cp ph|t mt vng nh
bng h{m malloc ()
V d: int *p;
p = (int) maloc ( 10* sizeof(int));
Trong b nh:
0 1 2 9
p
V d: int *p;
p = malloc (10* sizeof (int));
for(i=0; i< 10; i++)
scanf (%d, p+i)
- loi b vng nh c cp cho con tr ta dng h{m free (p)
2. S khc nhau gia tham s ca hm l mng v i s l pointer:
H{m (kiu a[]) H{m (kiu *p)
Ch :
Nu: Kiu a[50][30], *p;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
5
p= a;
th H{m (Kiu a[][30]) H{m (Kiu *p)
3. H{m tr v kiu con tr:
Kiu *h{m (is)
V d:
char *strcat (char s1[], char s2[])
{ int i=0,j=0;
while ( s1[i]!='\0' ) i++;
while ( (s1[i++] = s2[j++]) !='\0' ) ;
return s1 ;
}
IV. CON TR V CHUI
IV.1. Khai bo: khai b|o s l{ 1 chui k t v{ p l{ con tr tr n 1 chui k t, ta
vit nh sau:
char s [50];
char *p;
khi to 1 chui trong c 2 trng hp:
static char s[] = ABCD;
char *p = ABCD;
Lc n{y, nu ta: puts (p) ; // ABCD
puts (++p) ; // BCD
IV.2. Xt mt s v d v cc hm x l chui
a. Hm Strcpy: Sao chp chui k t t source qua dest.
0 1 2 3 4 5
source A B C D E F \0
dest
#include <stdio.h>
#include <conio.h>
void strcpy (char dest[], char source[])
{ int i=0;
while ((dest[i++] = source[i]) !='\0');
}
void main()
{ char src_str[]="Hoang Van";
char dst_str[20];
strcpy(dst_str,src_str);
printf("\n%s", dst_str);
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
6
Vit li h{m strcpy bng con tr:
void strcpy (char *dest, const char *source)
{ while (( *dest = *source) !=\0)
{ dest ++;
source ++;
}
}
b. Hm Strcmp () : dng so s|nh 2 chui s1, s2 vi nhau.
int strcmp (char s1[] , char s2 []);
{ int i= 0;
while (s1[i] == s2[i])
{ if (s1[i] == \0)
return 0;
i++;
}
return (s1[i]- s2[i]);
}
C{i t li bng con tr:
int strcmp (char *s1, const char *s2);
{ while (*s1 == *s2)
{ if (*s1 == \0) return 0;
*s1++;
*s2++;
}
return (*s1 - *s2)
}
c. Hm strcat: ni chui s2 sau chui s1
char *strcat (char s1[],char s2[])
{ int i=0,j=0;
while ( s1[i]!='\0' ) i++;
while ( (s1[i++] = s2[j++]) !='\0' ) ;
return s1 ;
}
C{i t li bng con tr:
char *strcat (char *s1, const char *s2)
{ char *p;
p=s1;
while ( *s1!='\0' )
s1 ++;
while ( (*s1=*s2) !='\0' )
{ s1 ++; s2 ++;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
7
}
return p ;
}
d. Hm strchr: tr v a ch ca k t c tromg chui s.
#include <stdio.h>
#include <conio.h>
char *strchr (char s[], char c)
{ int i=0;
while ( s[i]!=c && s[i]!='\0' )
i++;
if ( s[i] != c) return (char *)0;
else return &s[i] ;
}
C{i t li bng con tr:
char *strchr (char *s, char c)
{
while ( *s !=c && *s!='\0' )
s++;
if ( *s != c) return (char *)0;
else return s ;
}
char str[]="Ky ";
void main()
{ char *vt;
vt=strchr(str ,'y');
if (vt==NULL )
printf("Khong co ky tu trong chuoi" );
else printf("\nVi tri =%d", vt-str+1);
getch();
}
IV.3. Mng con tr ch n chui
- Khai bo: khai b|o 1 mng con tr ch n chui, v d nh danh s|ch h tn,
ta vit nh sau:
char * ds[5]= // mng chui ds[5][7]
{ "Hoang", "Van", "Chi", "Ngoc", "Nguyet" }
Nu ta khi to mng m{ khng dng con tr th lng nh cp ph|t cho mi
phn t ca mng u bng vi s k t ca chui d{i nht; Trong khi , nu khi to
bng mng con tr nh trn th lng nh s cp ph|t va cho tng phn t ca
mng.
ds[0] H o a n g \0
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
8
ds[1] V a n \0
ds[2] C h i \0
ds[3] N g o c \0
ds[4] N g u y e t \0
Hnh 3.2. Mng con tr tr n chui
ds[0] H o a n g \0
ds[1] V a n \0
ds[2] C h i \0
ds[3] N g o c \0
ds[4] N g u y e t \0
Hnh 3.3. Mng c|c chui
* X l con tr n chui: xt v d sp xp danh s|ch h tn theo ch mc:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main()
{ const SISO_MAX = 50;
char ds[SISO_MAX][30]; // mang chuoi
char *p[SISO_MAX]; //mang con tro den chuoi
char *tam;
char siso[2];
int i,j,n;
clrscr();
gotoxy(10,2); printf("Nhap si so lop:");
gets(siso);
n= atoi(siso);
for (i=0; i<n; i++)
{ printf("Ho ten hoc vien thu %d :",i+1);
gets(ds[i]);
p[i] = ds[i]; // ly a ch ca chui h tn trong ds a
// v{o mng con tr p
}
for (i=0; i<n-1;i++)
for (j=i+1; j<n; j++)
if ( strcmp(p[i],p[j]) >0)
{ tam = p[i];
p[i] = p[j];
p[j] = tam;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
8
9
}
printf("\n Danh sach ho ten sau khi sap xep\n");
for (i=0; i<n;i++)
printf("%s\n", p[i]);
}
Lu : Chng trnh trn thc cht ta ch ho|n i gi| tr ca mng con tr p ch
mng chui ds vn nh c.
B{i tp:
1. Sp xp li danh s|ch hc vin theo th t h tng dn bng con tr.
2. Sp xp li danh s|ch hc vin theo th t tn tng dn, nu trng tn th sp
theo h bng con tr.
3. Sp xp li danh s|ch hc vin theo th t tn tng dn, nu trng tn th sp
theo h bng mng chui.
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
0
CHNG 5 CC THUT TON TRN CU TRC
DANH SCH LIN KT (LINKED LIST)
I. KHI NIM:
Cu trc danh s|ch lin kt l{ cu trc ng, vic cp ph|t nt v{ gii phng nt
trn danh s|ch xy ra khi chng trnh ang chy. Ta thng cp ph|t nt cho danh s|ch
lin kt bng bin ng.
C|c phn t s c cp ph|t vng nh trong qu| trnh thc thi chng trnh, do
chng c th nm ri r|c nhiu ni kh|c nhau trong b nh (khng lin tc) .
3
First 1
2
4
C|c phn t trong danh s|ch c kt ni vi nhau theo chm lin kt nh hnh
trn:
- First l{ con tr ch n phn t u ca danh s|ch lin kt
- Phn t cui ca danh s|ch lin kt vi vng lin kt c gi| tr NULL
-Mi nt ca danh s|ch c trng info cha ni dung ca nt v{ trng next l{ con
tr ch n nt k tip trong danh s|ch.
* Lu :
- Cu trc danh s|ch lin kt l{ cu trc ng, c|c nt c cp ph|t hoc b gii
phng khi chng trnh ang chy.
- Danh s|ch lin kt rt thch hp khi thc hin c|c php to|n trn danh s|ch
thng b bin ng. Trong trng hp xa hay thm phn t trong danh s|ch lin kt
th ta khng di c|c phn t i nh trong mng m{ ch vic hiu chnh li trng next ti
c|c nt ang thao t|c. Thi gian thc hin c|c php to|n thm v{o v{ loi b khng ph
thuc v{o s phn t ca danh s|ch lin kt.
- Tuy nhin, danh s|ch lin kt cng c c|c im hn ch sau:
+ V mi nt ca danh s|ch lin kt phi cha thm trng next nn danh s|ch
lin kt phi tn thm b nh.
+ Tm kim trn danh s|ch lin kt khng nhanh v ta ch c truy xut tun t
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
1
t u danh s|ch.
Khai bo : Mt phn t ca danh s|ch lin kt t nht phi c hai th{nh phn : ni
dung ca phn t (info) v{ th{nh phn next lin kt phn t n{y vi phn t kh|c.
Gi s ta khai b|o kiu NODEPTR l{ kiu con tr ch n nt trong 1 danh s|ch lin
kt, mi phn t c 2 th{nh phn : info (int) v next .
struct node
{ int info ;
struct node *next ;
};
typedef struct node *NODEPTR;
- khai b|o bin First qun l danh s|ch lin kt ta vit nh sau:
NODEPTR First;
- Khi to danh s|ch lin kt : First = NULL;
- Ghi ch :
Th{nh phn cha ni dung c th gm nhiu vng vi c|c kiu d liu kh|c
nhau.
Th{nh phn lin kt cng c th nhiu hn mt nu l{ danh s|ch a lin kt hoc
danh s|ch lin kt kp.
First l{ con tr tr n phn t u tin ca danh s|ch lin kt, n c th l{ kiu
con tr (nh khai b|o trn), v{ cng c th l{ mt struct c hai th{nh phn:
First tr n phn t u tin ca danh s|ch lin kt, v{ Last tr n phn t
cui ca danh s|ch lin kt.
struct Linked_List;
{ First NODEPTR;
Last NODEPTR;
};
II. CC PHP TON TRN DANH SCH LIN KT:
II.1. To danh sch:
a. Khi to danh s|ch (Initialize): dng khi ng mt danh s|ch lin kt, cho
chng trnh hiu l{ hin ti danh s|ch lin kt cha c phn t.
void Initialize(NODEPTR &First)
{
First = NULL;
}
b. Cp ph|t vng nh (New_Node): cp ph|t mt nt cho danh s|ch lin kt. H{m
New_Node n{y tr v a ch ca nt va cp ph|t.
Trong chng trnh c s dng h{m malloc (trong <alloc.h>) , h{m n{y cp ph|t
mt khi nh tnh theo byte t b nh heap. Nu cp ph|t th{nh cng, h{m malloc tr v
a ch ca vng nh va cp ph|t, ngc li n s tr v NULL.
NODEPTR New_Node()
{
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
2
NODEPTR p;
p = (NODEPTR)malloc(sizeof(struct node));
return (p);
}
c. Thm v{o u danh s|ch (Insert_First): thm mt nt c ni dung x v{o u
danh s|ch lin kt.
void Insert_First (NODEPTR &First, int x)
{
NODEPTR p;
p = New_Node();
p->info = x;
p->next = First;
First = p;
}
d. Thm nt mi v{o sau nt c a ch p (Insert_After): thm mt nt c ni dung
x v{o sau nt c a ch p trong danh s|ch lin kt First.
void Insert_After(NODEPTR p, int x)
{
NODEPTR q;
if(p == NULL)
printf("khong them nut moi vao danh sach duoc");
else
{
q = New_Node();
q->info = x;
q->next = p->next;
p->next = q;
}
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
3
II.2. Cp nht danh sch:
a. Gii phng vng nh(Free_Node): H{m n{y dng hy nt ~ cp ph|t, v{ tr
vng nh v li cho memory heap.
void Free_Node(NODEPTR p)
{
free(p);
}
b. Kim tra danh s|ch lin kt rng hay khng (Empty): h{m Empty tr v TRUE
nu danh s|ch lin kt rng, v{ ngc li.
int Empty(NODEPTR First)
{
return(First == NULL);
}
c. Xa phn t u ca danh s|ch (Delete_First): mun xa 1 phn t khi danh
s|ch lin kt th ta phi kim tra xem danh s|ch c rng hay khng. Nu danh s|ch c
phn t th mi xa c.
int Delete_First (NODEPTR &First)
{ NODEPTR p;
if (Empty(First))
return 0;
else
{
p = First; // nut can xoa la nut dau
First = p->next;
Free_Node(p);
return 1;
}
}
d. Xa phn t ng sau nt c a ch p (Delete_After):
int Delete_After(NODEPTR First, NODEPTR &Last, NODEPTR p)
{ NODEPTR q;
// nu p l{ NULL hoc sau p khng c nt
if((p == NULL) || (p->next == NULL))
return 0;
q = p->next; // q chi nut can xoa
p->next = q->next;
Free_Node(q);
if (p->next==NULL) Last=p;
}
e. Xa to{n b danh s|ch (Delete_All): ta c th s dng lnh *First = NULL xa
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
4
to{n b danh s|ch, nhng trong b nh, c|c vng nh ~ cp ph|t cho c|c nt khng gii
phng v li cho memory heap, nn s l~ng ph vng nh. Do , ta s dng gii thut
sau:
void Delete_All (NODEPTR &First)
{ NODEPTR p;
while (First != NULL)
{ p=First;
First = First->next; // hoc First = p->next
Free_Node(p);
}
}
II.3. Duyt danh sch: Thng thng ta hay duyt danh s|ch lin kt thc hin
mt cng vic g , nh lit k d liu trong danh s|ch hay m s nt trong danh
sch...
void Traverse(NODEPTR First)
{ NODEPTR p;
int stt = 0;
p = First;
if(p == NULL)
printf("\n (Khong co sinh vien trong danh sach)");
while(p != NULL)
{
printf("\n %5d%8d", stt++, p->info);
p = p->next;
}
}
II.4. Tm kim (Search): Tm nt u tin trong danh s|ch c info bng vi x. Do }y
l{ danh s|ch lin kt nn ta phi tm t u danh s|ch.
H{m Search nu tm thy x trong danh s|ch th tr v a ch ca nt c tr bng x
trong danh s|ch, nu khng c th tr v tr NULL.
NODEPTR Search(NODEPTR First, int x)
{
NODEPTR p;
p = First;
while(p != NULL && p->info != x )
p = p->next;
return (p);
}
II.5. Sp xp (Selection_Sort): sp xp danh s|ch lin kt theo th t info tng dn.
- Ni dung: Ta so s|nh tt c c|c phn t ca danh s|ch chn ra mt phn t nh
nht a v u danh s|ch; sau , tip tc chn phn t nh nht trong c|c phn t cn
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
5
li a v phn t th hai trong danh s|ch. Qu| trnh n{y lp li cho n khi chn ra
c phn t nh th (n-1).
- Gii thut:
void Selection_Sort(NODEPTR First)
{ NODEPTR p, q, pmin;
int min;
for(p = First; p->next != NULL; p = p->next)
{ min = p->info;
pmin = p;
for(q = p->next; q != NULL; q = q->next)
if(min > q->info)
{
min = q->info;
pmin = q;
}
// hoan doi truong info cua hai nut p va pmin
pmin->info = p->info;
p->info = min;
}
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
6
B{i tp:
1. Vit chng trnh to mt menu thc hin c|c cng vic sau:
a. Nhp danh s|ch lin kt theo gii thut thm v u danh s|ch, mi phn t gm c
cc thng tin sau: mssv (int), v hoten ( char hoten[30] ).
b. Lit k danh s|ch ra m{n hnh
c. Cho bit tng s nt trong danh s|ch lin kt, t tn h{m l Reccount
( int Reccount(NODEPTR First) )
d. Thm 1 phn t c ni dung info (mssv, hoten) v{o sau phn t c th t th i
trong danh sch.
Ghi ch: - Th t theo qui c bt u l{ 1
- Nu (i <= 0) thm v{o u danh s|ch
Nu i > Reccount(&First) th thm v{o cui danh s|ch.
e. In ra h tn ca sinh vin c m~ do ta nhp v{o.
f. Loi b nt c m~ do ta nhp v{o, trc khi xa hi li "Bn tht s mun xa (Y/N)
? "
g. Sp xp li danh s|ch theo th t m~ s gim dn.
h.Ghi to{n b danh s|ch v{o file tn 'DSSV.DAT'
i. Np danh s|ch t file 'DSSV.DAT' v{o danh s|ch lin kt. Nu trong danh s|ch lin
kt ~ c nt th xa tt c d liu hin c trong danh s|ch lin kt trc khi a
d liu t file v{o.
2. Vit chng trnh to mt danh s|ch lin kt theo gii thut thm v{o cui danh s|ch,
mi nt cha mt s nguyn.
3. -Vit h{m tn Delete_Node xa nt c a ch p.
- Vit mt h{m loi b tt c c|c nt c ni dung x trong danh s|ch lin kt First.
4. Vit h{m Copy_List trn danh s|ch lin kt to ra mt danh s|ch lin kt mi ging
danh s|ch lin kt c.
5. Ghp mt danh s|ch lin kt c a ch u l{ First2 v{o mt danh s|ch lin kt c a
ch u l{ First1 ngay sau phn t th i trong danh s|ch lin kt First1.
6. Vit h{m lc danh s|ch lin kt tr|nh trng hp c|c nt trong danh s|ch lin kt
b trng info.
7. o ngc vng lin kt ca mt danh s|ch lin kt sao cho:
- First s ch n phn t cui
- Phn t u c lin kt l{ NULL.
8. Vit h{m Left_Traverse (NODEPTR &First) duyt ngc danh s|ch lin kt.
9. Vit gii thut t|ch mt danh s|ch lin kt th{nh hai danh s|ch lin kt, trong mt
danh s|ch lin kt cha c|c phn t c s th t l v{ mt danh s|ch lin kt cha c|c
phn t c s th t chn trong danh s|ch lin kt c.
10. - To mt danh s|ch lin kt cha tn hc vin, im trung bnh, hng ca hc vin
(vi iu kin ch nhp tn v{ im trung bnh). Qu| trnh nhp s dng li khi tn
nhp v{o l{ rng.
- Xp hng cho c|c hc vin. In ra danh s|ch hc vin th t hng tng dn (Ghi ch :
Cng im trung bnh th cng hng).
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
7
11. Nhp hai a thc theo danh s|ch lin kt. In ra tch ca hai a thc n{y.
V d: a thc First1 : 2x
5
+4x
2
-1
a thc First2 : 10x
7
-3x
4
+x
2
Kt qu in ra : 20x
12
+ 34x
9
- 8x
7
- 12x
6
+ 7x
4
- x
2
(Ghi ch : Khng nhp v{ in ra c|c s hng c h s bng 0)
12. Vit gii thut thm phn t c ni dung x v{o danh s|ch lin kt c th t tng dn
sao cho sau khi thm danh s|ch lin kt vn c th t tng.
13. Loi b phn t c ni dung l{ x trong danh s|ch lin kt c th t tng dn.
14. Cho 2 danh s|ch lin kt First1, First2 c th t tng dn theo info. Vit gii thut
Merge trn 2 danh s|ch lin kt n{y li sao cho danh s|ch lin kt sau khi trn
cng c th t tng dn.
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
8
CHNG 6 CC THUT TON TRN CU TRC CY
(Tree)
C}y l{ mt cu trc d liu rt thng dng v{ quan trng trong nhiu phm vi kh|c
nhau ca k thut m|y tnh.
V d : T chc c|c quan h h h{ng trong mt gia ph, mc lc ca mt cun s|ch,
x}y dng cu trc v c ph|p trong c|c trnh bin dch.
Trong chng trnh n{y, chng ta kho s|t c|c kh|i nim c bn v c}y, c|c php
to|n trn c}y nh ph}n, cng nh c|c php to|n trn c}y nh ph}n c}n bng ( AVL tree)
v{ ng dng ca hai loi c}y nh ph}n tm kim (BST), c}y nh ph}n c}n bng ( AVL tree).
I. PHN LOI CY:
I.1. Mt s khi nim c bn:
1. Cy: C}y l{ tp hp c|c phn t gi l{ nt, mt nt (tng t nh mt phn t
ca d~y) c th c kiu bt k. C|c nt c biu din bi 1 k t ch, mt chui, mt s
ghi trong mt vng trn.
Mt s nh ngha theo quy
Mt nt n cng chnh l{ mt c}y.
C|c nt c gi l{ cng mt c}y khi c ng i gia c|c nt n{y.
Mt c}y s bao gm mt nt gc (Root) v{ m c}y con, trong mi c}y con li c
mt nt gc v{ m1 c}y con nh hn v.v.
Mt c}y khng c mt nt n{o c gi l{ c}y rng.
V d 1 :
Hnh 5.1. C}y vi nt gc l{ A
- A l{ nt gc vi 3 c}y con ln lt
c 3 nt gc ring l{ B, C, D
- Nt cha (ancestor)
Nt con (descendent)
A l nt cha ca B, C, D
G, H l{ nt con ca C
G, H khng quan h cha con vi A
V d 2 : Vi cng mt mn hc T, ta c th biu din dng c}y nh sau :
A
B C
G H E
J
D
F
K I
1
2
3
4
Nu t goc
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
9
9
Hnh 5.2
CHNG I
I.1
I.2
CHNG II
II.1
II.1.1
II.1.2
II.2
II.3
CHNG III
2. Nt cha (Ancestor) : Nt ng trn ca mt nt c gi l{ nt cha
C l{ nt cha ca G, H
Nt con (descendent) : Nt ng sau mt nt kh|c c gi l{ nt con ca nt .
Nt I, J, K l{ nt con ca nt E
3. Bc (degree) :
- Bc ca nt l{ s c}y con ca nt .
C c bc l{ 2, E c bc l{ 3 (Hnh 5.1)
- Bc ca c}y l{ bc ln nht ca c|c nt trong c}y.
Cy trong hnh 5.1 c bc l{ 3.
C}y bc n c gi l{ c}y n ph}n nh c}y nh ph}n, c}y tam ph}n.
4. Nt l v nt trung gian:
- Nt l| l{ nt c bc bng 0 (tc l{ khng c c}y con n{o) :
- Nt trung gian: l{ mt nt c bc kh|c 0 v{ khng phi l{ nt gc.
V d: Trong hnh 5.1, B, G, H, I, J, K, F l nt l
C, D, E l nt trung gian.
5. Mc ca nt (level) : Nt gc c mc l{ 1
Mc ca nt con = mc ca nt cha + 1
V d: trong hnh 5.1,
A c mc l{ 1
B, C, D c mc l{ 2
G, H, E, F c mc l{ 3
I, J, K c mc l 4
6. Chiu cao ca c}y (height) : l{ mc ln nht ca c|c nt l| trong c}y.
V d: C}y trong hnh 5.1 c chiu cao l{ 4
T
CHNG I CHNG I I CHNG I I I
I .1 I .2 I I .1 I I .3 I I .2
I I .1.1 I I .1.2
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
0
7. Th t ca c|c nt (order of nodes) : Nu c}y c gi l{ c th t th phi
m bo v tr ca c|c nt con t tr|i qua phi, tc l{ nu thay i v tr ca mt nt con
bt k th ta ~ c mt c}y mi.
V d :
Hnh 5.3: Sau khi i v tr ca 2 nt B, C ta ~ c c}y mi.
8. Chiu d{i ng i (Path length):
- Chiu d{i ng i ca nt x: l{ s c|c cnh i t nt gc n nt x.
V d: Trong hnh 5.1:
Nt gc A c chiu d{i ng i l{ 1
Nt B, C, D c chiu d{i ng i l{ 2
Tng qu|t: mt nt ti mc i c chiu d{i ng i l{ i
- Chiu d{i ng i ca c}y: l{ tng ca c|c chiu d{i ng i ca tt c c|c nt
trong cy.
V d: Chiu d{i ng i ca c}y trong hnh 5.1 l{ 31.
Chiu d{i ng i trung bnh ca c}y:
n / ) i .
n
(
P
i
i i
=
trong ni l{ s c|c nt mc i v{ n l{ tng s c|c nt trong c}y.
I.2. Cch biu din cy: biu din 1 c}y, ta c nhiu c|ch nh biu din bng
th,bng gin , bng ch s.. Nhng thng thng, ta hay dng dng th biu din
1 cy nh hnh 5.1
I.3. Biu din th t cc nt trong cy :
Mt c}y thng t chc c|c nt theo mt th t nht nh cn c v{o mt ni dung
gi l{ kha ca c|c nt. C th t chc c}y c kha tng dn theo mc t tr|i qua phi
nh v d sau :
A
B C
A
C B
cay khac
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
1
ROOT
123456789
Nh vy khi duyt li c}y theo mc
tng dn v{ t tr|i qua phi ta s li c
c th t c|c nt nh trn.
Hnh 5.4. C}y c th t tng dn theo mc t tr|i qua phi
II. CY NH PHN (BINARY TREE)
II.1. nh ngha :
1. C}y nh ph}n l{ c}y c bc bng 2, tc l{ s nt con ti a ca mt nt bt k
trong cy l 2.
C}y nh ph}n c th l{ mt c}y rng (khng c nt n{o) hoc c}y ch c mt nt,
hoc c}y ch c c|c nt con bn tr|i (Left Child) hoc nt con bn phi (Right Child) hoc
c hai.
V d: Hnh 5.4 l{ c}y nh ph}n.
2. C|c c}y nh ph}n c bit:
- Cy nh ph}n ng: Mt c}y nh ph}n c gi l{ c}y nh ph}n ng nu nt gc
v{ tt c c|c nt trung gian u c 2 nt con.
Hnh 5.5. C}y nh ph}n ng
Ghi ch: nu c}y nh ph}n ng c n nt l| th c}y n{y s c tt c 2n-1 nt.
- C}y nh ph}n y: Mt c}y nh ph}n gi l{ c}y nh ph}n y vi chiu cao d th:
. N phi l{ c}y nh ph}n ng v{
. Tt c c|c nt l| u c mc l{ d.
Hnh 5.5 khng phi l{ c}y nh ph}n y
1
2 3
4
Root
7 6 8
5
9
A
B
D E
G Y
C
X F
H I
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
2
Hnh 5.6. C}y nh ph}n y.
Ghi ch: C}y nh ph}n y l{ c}y nh ph}n c s nt ti a mi mc.
- C}y nh ph}n tm kim (Binary Search Tree): Mt c}y nh ph}n gi l{ c}y nh ph}n
tm kim nu v{ ch nu i vi mi nt ca c}y th kha ca mt nt bt k phi ln hn
kha ca tt c c|c nt trong c}y con bn tr|i ca n v{ phi nh hn kha ca tt c c|c
nt trong c}y con bn phi ca n.
V d:
Hnh 5.7. C}y nh ph}n tm kim (BST)
- C}y nh ph}n c}n bng (AVL): Mt c}y nh ph}n c gi l{ c}y nh ph}n c}n bng
nu v{ ch nu i vi mi nt ca c}y th chiu cao ca c}y con bn tr|i v{ chiu cao ca
c}y con bn phi hn km nhau nhiu nht l{ 1. (Theo Adelson-Velski v Landis).
A
B
D
H
I
E
J K
C
F
L M
G
N O
8
7 9
3
12
11
10 2
1
5
4 6
k
1
<k
1
<k
1
A
C
E
F
B
D
G
I J H
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
3
Hnh 5.8. C}y nh ph}n c}n bng
- C}y nh ph}n c}n bng ho{n to{n: Mt c}y nh ph}n c gi l{ c}y nh ph}n c}n
bng ho{n to{n nu v{ ch nu i vi mi nt ca c}y th s nt ca c}y con bn tr|i v{
s nt ca c}y con bn phi hn km nhau nhiu nht l{ 1.
Hnh5.9. C}y nh ph}n c}n bng ho{n to{n
3. C|c php duyt c}y nh ph}n (Traverse) : l{ qu| trnh i qua c|c nt ng mt
ln. Khi duyt c}y, ta thng dng 3 c|ch duyt c bn sau :
Preorder - Tin t (NLR) duyt qua nt gc trc, sau i qua c}y con bn tr|i
li |p dng Preorder cho c}y con bn tr|i. Cui cng qua c}y con bn phi, |p dng
Preorder cho c}y con bn phi.
V d: Theo c}y nh ph}n 5.4, ta c:
ROOT 1 2 3 4 6 7 5 8 9
Inorder - Trung t (LNR) : qua c}y con bn tr|i duyt trc (theo th t LNR),
sau thm nt gc. Cui cng qua c}y con bn phi (theo th t LNR)
V d: Theo c}y nh ph}n 5.4, ta c:
ROOT 2 1 6 4 7 3 8 5 9
Postorder - Hu t (LRN) : qua c}y con bn tr|i duyt trc (theo th t LRN),
sau qua c}y con bn phi (theo th t LRN). Cui cng thm nt gc.
V d: Theo c}y nh ph}n 5.4, ta c:
ROOT 2 6 7 4 8 9 5 3 1
Ghi ch : i vi c}y ta c th t chc th t theo kha l{ mt ni dung ca nt
hoc ta t thm 1 field gi l{ kha ca nt .
II.2. Cc php ton trn cy nh phn:
- Khai bo: t chc d liu theo c}y nh ph}n, ta c th dng mt ni dung ca
d liu l{m kha sp xp v{ t chc c}y theo nhiu c|ch kh|c nhau. Nhng thng
thng thun tin cho vic tm kim v{ thc hin c|c php to|n kh|c trn c}y, ngi
ta to thm mt kha ring trong c|c phn t v{ to ra c}y nh ph}n tm kim.
khai b|o bin tree qun l mt c}y nh ph}n, vi ni dung info cha s nguyn,
ta khai bo nh sau:
struct nodetype
{
int key;
int info;
struct nodetype *left;
A
C
E
F
B
D
I H
E
H
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
4
struct nodetype *right;
};
typedef struct nodetype *NODEPTR;
NODEPTR tree;
1. To cy:
a. Khi to c}y(Initialize): dng khi ng c}y nh ph}n, cho chng trnh hiu
l{ hin ti c}y nh ph}n rng.
void Initialize(NODEPTR &root)
{
root = NULL;
}
Li gi h{m: Initialize(tree);
b. Cp ph|t vng nh (New_Node): cp ph|t mt nt cho c}y nh ph}n. H{m
New_Node n{y tr v a ch ca nt va cp ph|t.
NODEPTR New_Node(void)
{
NODEPTR p;
p = (NODEPTR)malloc(sizeof(struct nodetype));
return(p);
}
Li gi h{m: p= New_Node();
c. To c}y BST (Create_Tree): Trong gii thut to c}y BST, ta c dng h{m Insert.
Hm Insert: dng phng ph|p qui thm nt c kha x, ni dung a v{o c}y c
nt gc root . C}y nh ph}n to c qua gii thut Create_Tree l{ c}y nh ph}n tm kim
(BST).
void Insert(NODEPTR root, int x, int a)
{ NODEPTR p;
if(x == root->key) // kha b trng, dng chng trnh
{
printf("bi trung khoa, khong them nut nay duoc");
return;
}
if(x < root->info && root->left == NULL) // iu kin dng gii thut qui
{
p = New_Node(); // cp ph|t vng nh
p->key =x;
p->info = a;
p->left = NULL;
p->right = NULL;
root->left=p;
return;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
5
}
if(x > root->info && root->right == NULL) //iu kin dng gii thut qui
{
p = New_Node();
p->key =x;
p->info = a;
p->left = NULL;
p->right = NULL;
root->right=p ;
return;
}
if(x < root->info) // bc qui
Insert(root->left, x,a); // gi qui qua nh|nh tr|i
else
Insert(root->right, x,a); // gi qui qua nh|nh phi
}
void Create_Tree(NODEPTR &root)
{ int khoa, noidung;
char so[10];
NODEPTR p;
do
{ printf("Nhap khoa :");
gets(so) ;
khoa = atoi(so);
if (khoa !=0)
{ printf("Nhap noi dung :");
gets(so) ;
noidung = atoi(so);
if (root==NULL)
{ p = New_Node();
p->key = khoa;
p->info = noidung;
p->left = NULL;
p->right = NULL;
root =p;
}
else Insert(root,khoa,noidung);
}
} while (khoa!=0); // kha =0 th dng nhp
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
6
Ghi ch : to c}y nh ph}n do bin tree qun l, ta gi:
Create_Tree(tree);
2. Cp nht cy:
a. Gii phng vng nh(Free_Node): gii phng vng nh m{ p ang tr n.
void Free_Node(NODEPTR p)
{
free(p);
}
Li gi h{m: Free_Node (p);
b. Kim tra c}y nh ph}n rng hay khng (Empty): h{m Empty tr v TRUE nu c}y
nh ph}n rng, v{ ngc li.
int Empty(NODEPTR root)
return(root == NULL ? TRUE : FALSE);
}
Li gi h{m: Empty(tree)
c. Hy b mt nt trong c}y nh ph}n BST (Remove):
Xa nt c kha l{ x trong c}y nh ph}n tm kim sao cho sau khi xa th c}y nh
ph}n vn l{ c}y nh ph}n tm kim. Ta c 3 trng hp :
- Trng hp 1: nt p cn xa l{ nt l|. Vic xa nt p ch n gin l{ hy nt p
- Trng hp 2: Nt p cn xa c 1 c}y con, th ta cho rp ch ti nt p. Sau , ta to
lin kt t nt cha ca p ti nt con ca rp, cui cng hy nt p.
Hnh 5.10. Xa nt p trong trng hp nt n{y c 1 c}y con bn tr|i.
p1
p
p1
p1
p
p1
10
5
3
15
12
20
2 4
p
xoa nut p
10
3 15
12 20 2
4
rp
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
7
Hnh 5.11. Xa nt p trong trng hp nt n{y c 1 c}y con bn phi.
- Trng hp 3: Nt p cn xa c 2 c}y con. Ta cho rp ch ti nt p. Do tnh cht nt
cc tr|i ca c}y con bn phi ca p c kha va ln hn kha ca p, nn loi p th ta
s cho r ch ti nt cc tr|i . Sau , ta sao chp ni dung v{ kha ca nt r v{o nt m{
rp ang ch ti. Ta to lin kt thch hp bt nt rp ra khi c}y nh ph}n v{ cui cng
xa nt rp.
Hnh 5.12. Xa nt p trong trng hp nt n{y c 2 c}y con.
Hm Remove xa nt c kha l x:
NODEPTR rp;
void remove_case_3 ( NODEPTR &r )
{
if (r->left != NULL)
remove_case_3 (r->left);
//den day r la nut cuc trai cua cay con ben phai co nut goc la rp}
else
{
rp->key = r->key; //Chep noi dung cua r sang rp ";
rp->info =r->info; // de lat nua free(rp)
rp = r;
r = r->right;
}
}
2
10
5
3
15
4
20
18 25
rp
p
xoa nut p
10
5
3
20
18 25
2 4
10
5 20
15 30
12 18
28
25 35
p
nut trai nhat cua
cay con ben phai
10
5 25
15 30
12 18 28 35
r
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
8
void remove (int x , NODEPTR &p )
{
if (p == NULL) printf ("Khong tm thay");
else
if (x < p->key) remove (x, p->left);
else if (x > p->key)
remove (x, p->right);
else // p^.key = x
{
rp = p;
if (rp->right == NULL) p = rp->left;
// p l nt l hoac la nut chi co cay con ben trai
else if (rp->left == NULL)
p = rp->right; // p l nut co cay con ben phai
else remove_case_3 (rp->right);
free (rp);
}
}
Li gi h{m: Remove(x, tree); // x l{ kha ca nt mun xa
d. Tm kim (Search): Tm nt c kha bng x trn c}y nh ph}n BST c gc l{ root.
Nu tm thy x trong c}y th tr v a ch ca nt c tr bng x trong c}y, nu khng c
th tr v tr NULL.
Do c}y nh ph}n l{ BST nn ta c th tm kim nhanh bng phng ph|p tm kim
nh ph}n.
NODEPTR Search(NODEPTR root, int x)
{
NODEPTR p;
p = root;
while(p != NULL && x!=p->key)
if(x < p->key)
p = p->left;
else
p = p->right;
return(p);
}
Li gi h{m: p=Search(tree, x);
3. Cc php duyt cy: C 3 c|ch duyt c bn l{ NLR, LNR, LRN v{ mt c|ch c
bit l{ duyt c}y theo mc. }y, ta ch xt 3 phng ph|p duyt NLR, LNR v{ LRN. Xt
cy sau :
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
0
9
a. Duyt cy theo th t NLR (Preorder):
void Preorder (NODEPTR root)
{ if(root != NULL)
{ printf("%d ", root->info);
Preorder(root->left);
Preorder (root->right);
}
}
b. Duyt cy theo th t LNR (Inorder):
void Inorder(NODEPTR root)
{ if(root != NULL)
{ Inorder(root->left);
printf("%d ", root->info);
Inorder(root->right);
}
}
c. Duyt cy theo th t LRN (Posorder):
void Posorder(NODEPTR root)
{ if(root != NULL)
{ Posorder(root->left);
Posorder(root->right);
printf("%d ", root->info);
}
}
III. C]Y NH PH]N TM KIM C]N BNG (AVL):
Chng ta to c}y nh ph}n tm kim mc ch l{ tm kha cho nhanh, tuy nhin
tng tc tm kim th c}y cn phi c}n i v 2 nh|nh theo tng nt trong c}y. Do vy,
ta s tm c|ch t chc li c}y BST sao cho n c}n bng.
III.1. nh ngha:
4
2
1
5
3 6
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
0
- C}y nh ph}n tm kim c}n bng (AVL) l{ c}y nh ph}n tm kim m{ ti tt c c|c
nt ca n chiu cao ca c}y con bn tr|i ca n v{ chiu cao ca c}y con bn tr|i chnh
lch nhau khng qu| mt.
Hnh 5.14. C}y nh ph}n tm kim c}n bng
Lu : Vi c}y AVL, vic thm v{o hay loi b 1 nt trn c}y c th l{m c}y mt c}n
bng, khi ta phi c}n bng li c}y. Tuy nhin vic c}n bng li trn c}y AVL ch xy ra
phm vi cc b bng c|ch xoay tr|i hoc xoay phi mt v{i nh|nh c}y con nn gim
thiu chi ph c}n bng.
- Ch s c}n bng (balance factor) ca mt nt p trn cy AVL= lh(p) - rh(p)
Trong : lh (p) l{ chiu cao ca c}y con bn tr|i ca p
rh(p) l{ chiu cao ca c}y con bn phi ca p
Ta c c|c trng hp sau:
bf(p) = 0 nu lh(p) = rh(p) nt p c}n bng
bf(p) = 1 nu lh(p) = rh(p) +1 nt p b lch v tr|i
bf(p) = -1 nu lh(p) = rh(p) -1 nt p b lch v phi
Hnh 5.15. Minh ha c|c v tr c th thm nt l| v{o c}y AVL, khi thm nt l| v{o 1 trong
c|c v tr B th c}y vn c}n bng, khi thm nt l| v{o 1 trong c|c v tr U th c}y s mt c}n
bng. C|c s trn c}y l{ ch s c}n bng ca c|c nt trc khi thm nt
III.2. Cc php ton trn cy AVL:
* Khai bo: Ta khai b|o c}y AVL vi mi nt c thm trng bf cho bit ch s c}n
bng ca nt .
10
20
15
30
6
8
12
25 40 18
-1
1
0
B
0
B
0
1
-1
0
0
U
4
0
U
3
U
2
0
U
1 B
0
B B
0
B
U
8
0
U
7
U
6
0
U
5
U
10
0
U
9
U
12
0
U
11
A
B C
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
1
struct nodetype
{
int key;
int info;
int bf;
struct nodetype *left, *right;
};
typedef struct nodetype *NODEPTR;
III.2.1. Thm nt:
- Ni dung: Thm 1 nt c kha x, ni dung a v{o c}y nh ph}n tm kim c}n bng
sao cho sau khi thm th c}y nh ph}n vn l{ c}y nh ph}n tm kim c}n bng.
- Gii thut:
Thm nt vo cy nh bnh thng, ngha l{ nt va thm s l{ nt l|.
Tnh li ch s c}n bng ca c|c nt c b nh hng
Kim tra xem c}y c b mt c}n bng hay khng? Nu c}y b mt c}n bng th ta
c}n bng li c}y.
* Trc ht, ta hy xt xem cc trng hp no khi thm nt lm cy b mt
cn bng.
Xem c}y hnh 5.15, ta nhn thy:
- Nu thm nt v{o 1 trong 6 v tr B trn c}y th c}y vn c}n bng.
- Nu thm nt v{o 1 trong c|c v tr U1U12 trn c}y th c}y s mt c}n bng.
+ Thm c|c nt v{o sau bn tr|i ca nt A (cfA = 1) th c}y s b mt c}n
bng v nt A ang b lch tr|i. l{ c|c v tr U1, U2, U3, U4.
+ Thm c|c nt v{o sau bn phi ca nt C (cfC = -1) th c}y s b mt c}n
bng v nt C ang b lch phi. l{ c|c v tr U9, U10, U11, U12.
Tm li: Ta c 2 trng hp khi thm nt x vo cy AVL lm cy mt cn bng,
l thm cc nt vo sau bn tri ca nt c cf = 1, v thm cc nt vo sau bn phi ca nt
c cf = -1.
* Cn bng li cy: Gi ya l{ nt trc gn nht b mt c}n bng khi thm nt x v{o
c}y AVL. Do c 2 trng hp b mt c}n bng khi thm nt x l{ tng t nhau nn ta ch
xt trng hp bfya=1 v{ nt l| thm v{o l{ nt sau bn tr|i ca nt ya.
Hnh 5.16. Nh|nh c}y con nt gc ya trc khi thm nt.
1
0
T3
chieu
cao
n
T1
chieu
cao
n
T2
chieu
cao
n
S
ya
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
2
Nhn xt:
- V nt ya c bfya = 1 nn nt ya chc chn c nt con bn tr|i s vi bfs = 0
- V ya l{ nt gn nht c bf l{ 1 nn nt s v{ c|c nt trc kh|c ca nt x (s thm
vo) c bf l 0.
-cao (T1) = cao(T2) = cao(T3)
Trng hp 1a: Nu thm nt mi x v{o v tr nt sau bn tr|i ca s (thuc nh|nh
T1) ta xoay phi quanh nt ya
- Nt s s l{ nt gc mi ca nh|nh c}y n{y vi bfs = 0
- Nt ya l nt con bn phi ca s vi bfya = 0.
Hnh 5.17. Xoay phi quanh nt ya c}n bng li c}y.
Trng hp 1b: Nu thm nt mi x v{o v tr nt sau bn phi ca s (thuc
nh|nh T2) ta xoay 2 ln (xoay kp): xoay tr|i quanh nt s v{ xoay phi quanh nt ya
- Nt p s l{ nt gc mi ca nh|nh c}y n{y vi bfp = 0
- Nt ya l{ nt con bn phi ca p vi bfya = -1
- Nt s l{ nt con bn tr|i ca p vi bfs = 0
0
T1
chieu
sau
n
0
T2
chieu
sau
n
T3
chieu
sau
n
S
ya
x
2
1
T3
chieu
sau
n
T1
chieu
sau
n
T2
chieu
sau
n
S
ya
x
xoay phai
quanh nut ya
2
-1
T3
chieu
sau
n
T1
chieu
sau
n
S
ya
1
T2-1
chieu
sau
n-1
T2-2
chieu
sau
n-1
x
p
Cy AVL sau khi thm nt x
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
3
Hnh 5.18. Xoay kp (xoay tr|i quanh nt s, xoay phi quanh nt ya) c}n bng li c}y.
Bng sau }y ph}n bit c|c trng hp c}y b mt c}n bng khi thm nt v{ c|c
php xoay c}y tng ng c}n bng li c}y:
Trng hp Trc khi thm
nt x
Sau khi thm
nt x
C|c php xoay c}y v{ ch s
c}n bng mi
1.a bfya = 1
bfs = 0
bfya = 2
bfs = 1
Xoay phi quanh nt ya
bfs=0, bf ya = 0
1.b bfya = 1
bfs = 0
bfya = 2
bfs = -1
Xoay kp
1. Xoay tri quanh nt s
2. Xoay phi quanh nt ya
bfs=0, bf ya = -1
2.a bfya = -1
bfs = 0
bfya = -2
bfs = -1
Xoay tri quanh nt ya
bfs=0, bf ya = 0
2.b bfya = -1
bfs = 0
bfya = -2
bfs = 1
Xoay kp
1. Xoay phi quanh nt s
2. Xoay tri quanh nt ya
x
T2-1
chieu
sau
n-1
2
0
T1
chieu
sau
n
S
p
T2-2
chieu
sau
n-1
T3
chieu
sau
n
ya
2
xoay trai
quanh nut S
xoay phai
quanh nut ya
x
T2-1
chieu
sau
n-1
0
0
T1
chieu
sau
n
S
p
-1
T2-2
chieu
sau
n-1
T3
chieu
sau
n
ya
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
4
bfs=0, bf ya = 1
- Gii thut:
Php xoay tri (Rotate_Left): xoay tr|i c}y nh ph}n tm kim c nt gc l{ root,
yu cu root phi c nt con bn phi (gi l{ nt p). Sau khi xoay tr|i th nt p tr th{nh
nt gc, nt gc c tr th{nh nt con bn tr|i ca nt gc mi.
Php xoay tr|i tr v con tr ch nt gc mi.
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
5
NODEPTR Rotate_Left(NODEPTR root)
{
NODEPTR p;
if(root == NULL)
printf("Khong the xoay trai vi cay bi rong.");
else
if(root->right == NULL)
printf("Khong the xoay trai vi khong co nut con ben phai.");
else
{
p = root->right;
root->right = p->left;
p->left = root;
}
return p;
}
Php xoay phi (Rotate_Right): xoay phi c}y nh ph}n tm kim c nt gc l{
root, yu cu root phi c nt con bn tr|i (gi l{ nt p). Sau khi xoay phi th nt p tr
thnh nt gc, nt gc c tr th{nh nt con bn phi ca nt gc mi.
Php xoay phi tr v con tr ch nt gc mi.
NODEPTR Rotate_Right(NODEPTR root)
{
NODEPTR p;
if(root == NULL)
printf("Khong the xoay phai vi cay bi rong.");
else
if(root->left == NULL)
printf("Khong the xoay phai vi khong co nut con ben trai.");
else
{
p = root->left;
root->left = p->right;
p->right = root;
}
return p;
}
Thm nt (Insert): thm nt c kha x, ni dung a v{o c}y AVL:
- Thm nt theo gii thut thm nt v{o c}y nh ph}n tm kim .
- C}n bng li c}y bng c|ch xoay n hay xoay kp
void Insert(NODEPTR &pavltree, int x, int a)
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
6
{
NODEPTR fp, p, q, // fp l nt cha ca p, q l{ con ca p
fya, ya, /* ya l{ nt trc gn nht c th mt c}n bng
fya l{ nt cha ca ya */
s; // s l{ nt con ca ya theo hng mt c}n bng
int imbal; /* imbal = 1 nu b lch v nh|nh tr|i
= -1 nu b lch v nh|nh phi */
// Khi ng c|c gi| tr
fp = NULL;
p = pavltree;
fya = NULL;
ya = p;
// tim nut fp, ya va fya, nut moi them vao la nut la con cua nut fp
while(p != NULL)
{
if(x == p->info) // bi trung noi dung
return;
if (x < p->info)
q = p->left;
else
q = p->right;
if(q != NULL)
if(q->bf != 0) // truong hop chi so can bang cua q la 1 hay -1
{
fya = p;
ya = q;
}
fp = p;
p = q;
}
// Them nut moi (nut la) la con cua nut fp
q = New_Node(); // cp ph|t vng nh
q->key =x;
q->info = a;
q->bf = 0;
q->left = NULL;
q->right = NULL;
if(x < fp->info)
fp->left = q;
else
fp->right = q;
/* Hieu chinh chi so can bang cua tat ca cac nut giua ya va q, neu bi lech
ve phia trai thi chi so can bang cua tat ca cac nut giua ya va q deu la
1, neu bi lech ve phia phai thi chi so can bang cua tat ca cac nut giua
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
7
ya va q deu la -1 */
if(x < ya->info)
p = ya->left;
else
p = ya->right;
s = p; // s la con nut ya
while(p != q)
{
if(x < p->info)
{
p->bf = 1;
p = p->left;
}
else
{
p->bf = -1;
p = p->right;
}
}
// xac dinh huong lech
if(x < ya->info)
imbal = 1;
else
imbal = -1;
if(ya->bf == 0)
{
ya->bf = imbal;
return;
}
if(ya->bf != imbal)
{
ya->bf = 0;
return;
}
if(s->bf == imbal) // Truong hop xoay don
{
if(imbal == 1) // xoay phai
p = Rotate_Right(ya);
else // xoay trai
p = Rotate_Left(ya);
ya->bf = 0;
s->bf = 0;
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
8
else // Truong hop xoay kep
{
if(imbal == 1) // xoay kep trai-phai
{
ya->left = Rotate_Left(s);
p = Rotate_Right(ya);
}
else // xoay kep phai-trai -
{
ya->right = Rotate_Right(s);
p = Rotate_Left(ya);
}
if(p->bf == 0) // truong hop p la nut moi them vao
{
ya->bf = 0;
s->bf = 0;
}
else
if(p->bf == imbal)
{
ya->bf = -imbal;
s->bf = 0;
}
else
{
ya->bf = 0;
s->bf = imbal;
}
p->bf = 0;
}
if(fya == NULL)
pavltree = p;
else
if(ya == fya->right)
fya->right = p;
else
fya->left = p;
}
* to c}y nh ph}n tm kim c}n bng, ta s dng gii thut sau:
void Create_AVLTree(NODEPTR &root)
{ int khoa, noidung;
char so[10];
NODEPTR p;
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
1
9
do
{ printf("Nhap khoa :");
gets(so) ;
khoa = atoi(so);
if (khoa !=0)
{ printf("Nhap noi dung :");
gets(so) ;
noidung = atoi(so);
if (root==NULL)
{ p = New_Node();
p->key = khoa;
p->info = noidung;
p->bf = 0 ;
p->left = NULL;
p->right = NULL;
root =p;
}
else Insert(root,khoa,noidung);
}
} while (khoa!=0); // kha =0 th dng nhp
}
Ghi ch : to c}y nh ph}n do bin tree qun l, ta gi:
Create_AVLTree(tree);
III.2.2. Cp nht cy:
1. Tm kim (Search): Tm nt c kha bng x trn c}y nh ph}n AVL c gc l{
root. Nu tm thy x trong c}y th tr v a ch ca nt c tr bng x trongc}y, nu khng
c th tr v tr NULL.
Do AVL l{ c}y nh ph}n BST nn ta c th tm kim nhanh bng phng php tm
kim nh ph}n, v{ do tnh cht lc n{y c}y c}n bng nn thi gian tm kim s nhanh hn
rt nhiu.
NODEPTR search(NODEPTR root, int x)
{
NODEPTR p;
p = root;
while(p != NULL && x!=p->key)
if(x < p->key)
p = p->left;
else
p = p->right;
return(p);
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
0
2. Xa nt: Remove(root, x):
- Ni dung: xa nt c kha x trn c}y AVL vi a ch sao u root sao cho sau khi
xa th c}y vn l{ AVL.
- Gii thut:
Nu root == NULL th Thngb|o ("Khng th xa c nt x trn cy")
Nu root != NULL th
Nu x< root->info th:
+ Gi qui xa nt x nh|nh bn tr|i ca root :
Remove(root->left, x)
+ Gi balance_left c}n bng li c}y nt gc root nu nh|nh c}y con bn
tr|i b gim cao.
Nu x > root->info th:
+ Gi qui xa nt x nh|nh bn phi ca root :
Remove(root->right, x)
+ Gi balance_right c}n bng li c}y nt gc root nu nh|nh c}y con bn
phi b gim cao.
Nu x==root->info th:
Xa nt root nh php to|n xa trn c}y nh ph}n BST.
- Chng trnh : t c{i t.
III.2.3. Cc php duyt cy:
Do c}y AVL cng l{ c}y nh ph}n nn ta s |p dng li c|c phng ph|p duyt
Preorder, Inorder v Postorder vo cy AVL.
a. Duyt cy theo th t NLR (Preorder):
void Preorder (NODEPTR root)
{
if(root != NULL)
{
printf("%d ", root->info);
Preorder(root->left);
Preorder (root->right);
}
}
b. Duyt cy theo th t LNR (Inorder):
void Inorder(NODEPTR root)
{
if(root != NULL)
{
Inorder(root->left);
printf("%d ", root->info);
Inorder(root->right);
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
1
}
}
c. Duyt cy theo th t LRN (Posorder):
void Posorder(NODEPTR root)
{
if(root != NULL)
{
Posorder(root->left);
Posorder(root->right);
printf("%d ", root->info);
}
}
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
2
B{i tp:
1. Vit li c|c chng trnh duyt c}y nh ph}n theo phng ph|p khng qui.
2. Vit chng trnh to mt menu thc hin c|c mc sau:
a. To c}y nh ph}n tm kim vi ni dung l{ s nguyn (khng trng nhau).
b. Lit k c}y nh ph}n ra m{n hnh theo th t NLR
c. m tng s nt, s nt l|, v{ s nt trung gian ca c}y.
d. Tnh cao ca c}y.
e. Loi b nt c ni dung l{ x trong c}y nh ph}n BST.
f. Thm nt c ni dung x v{o c}y nh ph}n BST sao cho sau khi thm th c}y vn l{
BST.
3. Cho mt c}y nh ph}n tree, h~y vit chng trnh sao chp n th{nh mt c}y mi
tree2, vi kha, ni dung, v{ lin kt ging nh c}y tree.
4. Vit c|c h{m kim tra xem c}y nh ph}n:
a. C phi l{ c}y nh ph}n ng khng.
b. C phi l{ c}y nh ph}n y khng.
5. Vit h{m kim tra nt x v{ y c trn c}y hay khng, nu c c x ln y trn c}y th x|c
nh nt gc ca c}y con nh nht c cha x v{ y.
6. Cho mt c}y biu thc, h~y vit h{m Calculate (NODEPTR root) tnh gi| tr ca c}y
biu thc , bit rng c|c to|n t c dng trong biu thc l{:
+ - * / ^ % !
7. V li hnh nh c}y nh ph}n tm kim, c}y nh ph}n tm kim c}n bng nu c|c nt
thm v{o c}y theo th t nh sau:
8 3 5 2 20 11 30 9 18 4
8. Nhp v{o 1 biu thc s hc, chuyn biu thc th{nh c}y nh ph}n, nt gc l{ to|n
t, nt l| l{ c|c to|n hng, bit rng c|c to|n t c dng trong biu thc l{: + -
* / ^ % !
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
3
MC LC
CHNG I I CNG V LP TRNH -------------------------------------------------------- 1
I. KH\I NIM THUT TO\N ------------------------------------------------------------------------ 1
I.1. Kh|i nim --------------------------------------------------------------------------------------- 1
I.2. C|c tnh cht c trng ca thut to|n -------------------------------------------------- 1
I.3. Ph}n loi ---------------------------------------------------------------------------------------- 1
II. M T THUT TO\N BNG LU --------------------------------------------------------- 1
II.1. Lu ----------------------------------------------------------------------------------------- 1
II.2. C|c k hiu trn lu -------------------------------------------------------------------- 1
II.3. Mt s v d biu din thut to|n bng lu ---------------------------------------- 2
III. C\C NGN NG LP TRNH & CHNG TRNH DCH ----------------------------------- 5
III.1. Ngn ng lp trnh-------------------------------------------------------------------------- 5
III.2. Chng trnh dch -------------------------------------------------------------------------- 6
CHNG 2 L[M QUEN VI NGN NG C ---------------------------------------------------- 7
* GII THIU NGN NG C ------------------------------------------------------------------------ 7
I. C\C KH\I NIM C BN -------------------------------------------------------------------------- 7
I.1. Cu trc c bn ca mt chng trnh C ------------------------------------------------- 7
I.2. Kiu d liu c bn -------------------------------------------------------------------------- 13
I.3. Bin --------------------------------------------------------------------------------------------- 14
I.4 Hng --------------------------------------------------------------------------------------------- 18
I.5. Php ton -------------------------------------------------------------------------------------- 20
* S chuyn kiu ------------------------------------------------------------------------------ 29
* Mc u tin ca c|c php to|n ------------------------------------------------------- 29
I.6. Chui ------------------------------------------------------------------------------------------- 30
II. C\C CU TRC IU KHIN TRONG C ------------------------------------------------------- 33
II.1 Cu trc tun t (Sequence) ------------------------------------------------------------- 33
II.2. Cu trc chn -------------------------------------------------------------------------------- 34
II.2.1. Lnh if else ----------------------------------------------------------------------------- 34
II.2.2. Lnh switch_case ---------------------------------------------------------------------- 35
II.3. Cu trc lp ---------------------------------------------------------------------------------- 37
II.3.1. Lnh while ------------------------------------------------------------------------------ 37
II.3.2. Lnh do while -------------------------------------------------------------------------- 38
II.3.3. Lnh for --------------------------------------------------------------------------------- 39
* Ph|t biu break, continue, goto ---------------------------------------------------------- 40
B{i tp -------------------------------------------------------------------------------------------------- 41
III. HM - QUY ------------------------------------------------------------------------------------ 45
III.1. Hm ------------------------------------------------------------------------------------------- 45
III.2. qui (Recursion) ------------------------------------------------------------------------- 52
IV. STRUCTURE --------------------------------------------------------------------------------------- 54
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
4
IV.1. nh ngha ----------------------------------------------------------------------------------- 55
IV.2. Khai bo -------------------------------------------------------------------------------------- 55
V. FILE -------------------------------------------------------------------------------------------------- 56
V.1. File vn bn ---------------------------------------------------------------------------------- 56
V.2. File nh ph}n (file c cu trc) ----------------------------------------------------------- 61
V.3. Ph|t hin li khi truy xut tp tin -------------------------------------------------------- 66
B{i tp -------------------------------------------------------------------------------------------------- 67
CHNG 3. C\C THUT TO\N TRN CU TRC D LIU MNG ----------------------- 69
I. MNG KHNG SP XP V[ THUT TO\N TM KIM ------------------------------------- 69
TRN MNG CHA C TH T
I.1. Mt s kh|i nim v mng ----------------------------------------------------------------- 69
I.2. Thut to|n tm kim trn mng cha c th t --------------------------------------- 71
II. C\C THUT TO\N SP XP -------------------------------------------------------------------- 73
II.1. Sp xp theo phng ph|p Bubble_Sort ----------------------------------------------- 73
II.2. Sp xp theo phng ph|p Quick_Sort ------------------------------------------------- 75
III. TM KIM TRN MNG ^ C TH T ---------------------------------------------------- 79
III.1. Tm kim nhanh bng phng ph|p lp ---------------------------------------------- 79
III.2. Php tm kim nh ph}n ------------------------------------------------------------------ 80
III.3. Php tm kim nh ph}n qui --------------------------------------------------------- 81
B{i tp -------------------------------------------------------------------------------------------------- 82
CHNG 4 CON TR (POINTER) ------------------------------------------------------------- 84
I. NH NGHA ---------------------------------------------------------------------------------------- 84
I.1. Khai bo ---------------------------------------------------------------------------------------- 84
I.2. Truyn a ch cho h{m --------------------------------------------------------------------- 85
II C\C PHP TO\N TRN BIN CON TR ------------------------------------------------------- 85
II.1. To|n t a ch & --------------------------------------------------------------------------- 85
II.2. To|n t ni dung * ------------------------------------------------------------------------- 85
II.3. Php cng tr bin con tr vi mt s nguyn --------------------------------------- 86
II.4. Php gn v php so snh ----------------------------------------------------------------- 86
II.5. S chuyn kiu ------------------------------------------------------------------------------ 86
II.6. Khai b|o mt con tr hng v{ con tr ch n i tng hng -------------------- 87
III. S TNG QUAN GIA CON TR V[ MNG ---------------------------------------------- 87
IV. CON TR V[ CHUI ----------------------------------------------------------------------------- 91
IV.1. Khai bo -------------------------------------------------------------------------------------- 91
IV.2. Xt mt s v d v c|c h{m x l chui ----------------------------------------------- 91
IV.3. Mng con tr ch n chui -------------------------------------------------------------- 93
B{i tp -------------------------------------------------------------------------------------------------- 95
CHNG 5 C\C THUT TO\N TRN CU TRC ----------------------------------------- 96
DANH SCH LIN KT (LINKED LIST).
I. KH\I NIM ------------------------------------------------------------------------------------------ 96
II. C\C PHP TO\N TRN DANH S\CH LIN KT -------------------------------------------- 97
K THUT LP TRNH NGN NG LP TRNH C
P
a
g
e
1
2
5
II.1. To danh s|ch ------------------------------------------------------------------------------- 97
II.2. Cp nht danh s|ch ------------------------------------------------------------------------- 99
II.3. Duyt danh s|ch --------------------------------------------------------------------------- 100
II.4. Tm kim ------------------------------------------------------------------------------------ 100
II.5. Sp xp -------------------------------------------------------------------------------------- 101
B{i tp ------------------------------------------------------------------------------------------------ 102
CHNG 6 C\C THUT TO\N TRN CU TRC C]Y ------------------------------------ 104
I. PH]N LOI C]Y ---------------------------------------------------------------------------------- 104
I.1. Mt s kh|i nim c bn ----------------------------------------------------------------- 104
I.2. C|ch biu din c}y ------------------------------------------------------------------------- 106
I.3. Biu din th t c|c nt trong c}y ----------------------------------------------------- 106
II. C]Y NH PH]N (BINARY TREE) ------------------------------------------------------------- 107
II.1. nh ngha ---------------------------------------------------------------------------------- 107
II.2. C|c php to|n trn c}y nh ph}n------------------------------------------------------- 110
1. To c}y ------------------------------------------------------------------------------------- 110
2. Cp nht cy ------------------------------------------------------------------------------ 112
3. C|c php duyt c}y ---------------------------------------------------------------------- 116
III. C]Y NH PH]N TM KIM C]N BNG (AVL) --------------------------------------------- 117
III.1. nh ngha --------------------------------------------------------------------------------- 117
III.2. Cc php ton trn cy AVL ------------------------------------------------------------ 118
III.2.1. Thm nt----------------------------------------------------------------------------- 118
III.2.2. Cp nht c}y ------------------------------------------------------------------------- 126
III.2.3. C|c php duyt c}y ---------------------------------------------------------------- 127
B{i tp ------------------------------------------------------------------------------------------------ 129
TI LIU THAM KHO
1. K thut lp trnh Turbo C Phc, Nguyn Phi Kh, 1992
T Minh Ch}u,
Nguyn nh T
2. Cu trc d liu ng dng Nguyn Hng Chng 1999
v{ c{i t bng C
3. Nhng vin ngc K thut JohnBentley
lp trnh