ĐẠI CƯƠNG VỀ LẬP TRÌNH

K THUT LP TRNH NGN NG LP TRNH C
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

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

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 )

P
a
g
e
4

Begin
Nhap (a, b, c)
Xuat ( X
1
= ,(-b + SQRT(Delta)) / (2*a))
Xuat ( X
2
= ,(-b - SQRT(Delta)) / (2*a))
End
a = 0
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

P
a
g
e
5

V d 4: Tnh S=
i
i
n
x
=
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

P
a
g
e
6

ngn ng cp cao phi c bin dch sang ngn ng m|y. Cng c thc hin vic bin
dch c gi l{ chng trnh dch.
III.2. Chng trnh dch:
Chng trnh dch c chia ra l{m 2 loi : trnh bin dch (compiler) v{ trnh thng
dch (interpreter)
III.2.1. Trnh bin dch: l{ vic chuyn mt chng trnh trong ngn ng cp cao
n{o (chng trnh ngun) sang ngn ng m|y (chng trnh ch).
- Thi gian chuyn mt chng trnh ngun sang chng trnh ch c gi l{
thi gian dch.
- Thi gian m{ chng trnh ch thc thi c gi l{ thi gian thc thi.
Nh vy, chng trnh ngun v{ d liu chng trnh thc thi c x l
trong c|c thi im kh|c nhau, c gi l{ thi gian dch (compile time) v{ thi gian
thc thi (run-time)

Hnh I.1. Chng trnh thc thi theo c ch dch ca trnh bin dch
III.2.2. Trnh thng dch: qu| trnh dch v{ thc thi xy ra cng 1 thi gian, dch
n }u thi h{nh lnh n .

Hnh I.2. Chng trnh thc thi theo c ch dch ca trnh thng dch
Chng trnh
nguon
Trnh bien
dch
Chng trnh
ch
May tnh
thc hien
Ket qua
Dlieu
Chng trnh
nguon
Chng trnh
thong dch
Ket qua
Dlieu

P
a
g
e
7

CHNG 2 LM QUEN VI NGN NG C

* GII THIU NGN NG C
Ngn ng C do Dennis Ritchie l{ ngi u tin xut, ~ thit k v{ c{i t C
trong mi trng UNIX. N c ngun gc t ngn ng BCPL do Martin Richards a ra
v{o nm 1967 v{ ngn ng B do Ken Thompson ph|t trin t ngn ng BCPL nm 1970
khi vit h iu h{nh Unix.
C l{ ngn ng lp trnh a dng, cp cao nhng li c kh nng thc hin c|c thao
t|c nh ca ngn ng Assembly. V th ngn ng C nhanh chng c c{i t, s dng
trn m|y vi tnh v{ ~ tr th{nh mt cng c lp trnh kh| mnh, hin nay ang c
khuynh hng tr th{nh mt ngn ng lp trnh chnh cho m|y vi tnh trn th gii.
* c im ngn ng C
Ngn ng C c nhng c im c bn sau :
- Tnh c ng (compact) : Ngn ng C ch c 32 t kho| chun, 40 to|n t chun
m{ hu ht c biu din bi c|c d~y k t ngn gn.
- Tnh cu trc (structured) : Ngn ng C c mt tp hp c|c ph|t biu lp trnh
cu trc nh ph|t biu quyt nh hoc lp. Do , n cho php chng ta vit chng
trnh c t chc v{ d hiu.
- Tnh tng thch (compactable) : Ngn ng C c b lnh tin x l v{ c|c th
vin chun l{m cho c|c chng trnh vit bng ngn ng C c th tng thch khi chuyn
t m|y tnh n{y sang m|y tnh kiu ho{n to{n kh|c.
- Tnh linh ng (flexible) : Ngn ng C l{ mt ngn ng rt linh ng v ng
ph|p, n c th chp nhn rt nhiu c|ch th hin m{ khng c ngn ng kh|c nh
Pascal, n gip cho kch thc m~ lnh c th thu gn li chng trnh thc thi nhanh
chng hn.
- Bin dch : Ngn ng C c bin dch bng nhiu bc v{ cho php bin dch
nhiu tp tin chng trnh ring r th{nh c|c tp tin i tng (object) v{ ni c|c i
tng li vi nhau (link) th{nh mt chng trnh thc thi thng nht.
I. CC KHI NIM C BN
I.1. Cu trc c bn ca mt chng trnh C
[tin x l]
[Cc hm]
void main()
{ [khai b|o bin;]
[nhp d liu ;]
[x l ;]
[xut ;]
}
V d : Chng trnh hin trn m{n hnh c}u Chao cac ban
void main()

P
a
g
e
8

{ printf(Chao cac ban\n);
}
Mt v{i nhn xt quan trng :
- Chng trnh C bao gi cng c mt hay nhiu h{m, trong c mt h{m chnh
bt buc phi c l{ h{m main(). }y chnh l{ h{m c thc hin u tin trong chng
trnh.
- Cp du { } x|c nh mt khi lnh.
- H{m printf( Chao cac ban \n) l{ h{m chun ca C dng xut c}u thng b|o
Chao cac ban ra m{n hnh. K t \n l{ k t c bit dng xung dng.
- Du ; chm dt mt lnh.
- Chng trnh C c ph}n bit ch thng vi ch hoa. a s c|c t kho| ca C
c vit bng ch thng, cn mt s t c vit bng ch hoa m{ ta phi tu}n th
cht ch, nu khng th chng trnh dch s khng hiu.
* Mt v{i v d
V d 1: In bng ly tha 2 ca c|c s nguyn t 10 n 50
/* Chng trnh in bnh phng c|c s t 10 n 50*/
#include <stdio.h>
void main()
{int n; /*Khai b|o bin n kiu nguyn */
n=10; /*Gn n=10 */
while (n<=50) /*Lp t 10 n 50 bng while */
{ printf(%3d \t %5d\n,n,n*n); /*in dng 5d l{ d{nh 5 v tr in n v{ n
2
*/
n++; /* Tng n ln 1 */
} /*Ht while*/
} /*Ht main*/

P
a
g
e
9

V d 2 : Tng t nh v d 1 nhng vit c|ch kh|c :
#include <stdio.h>
#define max 50 /*Tin x l, nh ngha max =50*/
void main()
{ int n; /*Khai b|o bin n kiu nguyn*/
for (n=10; n<=max; n++) /*Lp t 10 n 50 bng for*/
printf(%3d \t %5d\n,n,n*n); /*in n v n
2
dng 5d l{ nm ch s*/
} /*Ht main*/
V d 3 : Chng trnh in ly tha 2, 3, 4, 5; c dng h{m tnh ly tha :
#include <stdio.h>
#define max 50 /*Tin x l, nh ngha max =50*/
float luythua(int n, int m) /*H{m luythua vi 2 thng s*/
{ float s=1; /*Khai b|o v{ khi to bin s*/
for ( ;m>0;m--) /*Lp gim dn t m ti 1*/
s=s*n;
return s; /*Tr kt qu v*/
}
void main()
{ int n,n2,n3,n4,n5; /*Khai b|o bin kiu nguyn*/
for (n=10;n<=50;n++) /*Lp t 10 n 50 bng for*/
{ n2= luythua(n,2); /*Gi h{m luythua*/
n3= luythua(n,3);
n4= luythua(n,4);
n5= luythua(n,5);
printf(%3d \t %5.2f \t %5.2f\t %5.2f\t %5.2f\t %5.2f\n, n,n2,n3,n4,n5);
/*in n v n
m
dng 5 ch s vi 2 s l */
}
} /*Ht main*/
* H{m xut chun printf()
C php :
printf(chui-nhdng,thamso1,thamso2,...)
ngha :
Hm printf() s xem xt chui-nhdng, ly gi| tr c|c tham s (nu cn) t
v{o theo yu cu ca chui-nhdng v{ gi ra thit b chun.
Chui-nhdng l{ mt chui k t, trong c nhng k t xut ra nguyn vn
hoc xut dng c bit, v{ c th c nhng chui iu khin cn ly gi| tr ca
c|c tham s thay v{o khi in ra.
- Nhng k t c bit :
K t T|c dng M ASCII

P
a
g
e
1
0

\n Xung h{ng mi 10
\t Tab 9
\b Xa k t bn tr|i 8
\r Con tr tr v u h{ng 13
\f Sang trang 12
\a Ph|t ting ci 7
\\ Xut du cho ngc 92
\ Xut du nh|y n 39
\ Xut du nh|y kp 34
\xdd Xut k t c m~ ASCII dng Hex l{ dd
\ddd Xut k t c m~ ASCII dng Dec l{ ddd
\0 K t NULL 0
- Chui nh dng :
% [ flag][width][.prec][F|N|h|l] type
Type : nh kiu ca tham s theo sau chui-nhdng ly gi| tr ra
Type ngha
d,i S nguyn c s 10
U S nguyn c s 10 khng du
O S nguyn c s 8
X S nguyn c s 16, ch thng(a,b,...,f)
X S nguyn c s 16, ch in (A,B,...,F)
F S thc dng [-]dddd.ddd...
E S thc dng [-]d.ddd e[+/-]ddd
E S thc dng [-]d.ddd E[+/-]ddd
g,G S thc dng e(E) hay f ty theo chnh x|c
C K t
S Chui k t tn cng bng \0
% Du % cn in


P
a
g
e
1
1

Flag : Dng iu chnh
Flag ngha
nu khng c in d liu ra vi canh phi
- in d liu ra vi canh tr|i
+ Lun bt u s bng + hay -
# in ra ty theo type, nu:
0 : Chn thm 0 ng trc gi| tr >0
x,X : Chn thm 0x hay 0X ng trc s n{y
e,E,f : Lun lun c du chm thp ph}n
G,g : Nh trn nhng khng c s 0 i sau
Width : nh kch thc in ra
Width ngha
n D{nh t nht n k t , in khong trng c|c k t cn trng
0n D{nh t nht n k t , in s 0 c|c k t cn trng
* S k t t nht cn in nm tham s tng ng
Prec : nh kch thc phn l in ra
Prec ngha
khng c chnh x|c nh bnh thng
0 d,i,o,u,x chnh x|c nh c
e,E,f Khng c du chm thp ph}n
n nhiu nht l{ n k t (s)
* S k t t nht cn in nm tham s tng ng
C|c ch b sung :
F Tham s l{ con tr xa XXXX:YYYY
N Tham s l{ con tr gn YYYY
h Tham s l{ short int
l Tham s l{ long int (d,i,o,u,x,X)
double (e,E,f,g,G)
V d 1: char c=A;
char s[]=Blue moon! ;
Dng Thng s
tng ng
Xut Nhn xt
%c c A rng 1

P
a
g
e
1
2

%2c c A rng 2, canh phi
%-3c c A rng 3, canh tr|i
%d c 65 M~ ASCII ca A
%s s Blue moon! rng 10
%3s s Blue moon! Nhiu k t hn cn thit
%.6s s Blue m Chnh x|c 6 k t
%-11.8s s Blue moo Chnh xc 8, canh tri
V d 2: int i = 123;
float x = 0.123456789;
Dng Thng s
tng ng
Xut Nhn xt
%d i 123 rng 3
%05d i 00123 Thm 2 s 0
%7o i 123 H 8, canh phi
%-9x i 7b H 16, canh tr|i
%c i { K t c m~ ASCII 123
%-#9x i 0x7b H 16, canh tr|i
%10.5f x 0.12346 rng 10, c 5 ch s thp
phn
%-12.5e x 1.23457e-01 Canh tr|i, in ra di dng khoa
hc
V d 3: Vit chng trnh in hnh ch nht kp bng c|c k t ASCII
C9 CD BB

C8 CD BC
void main()
{ printf(\n\xC9\xCD\xBB);
printf(\n\xC8\xCD\xBC\n);
}

P
a
g
e
1
3

I.2. Kiu d liu c bn
I.2.1. nh ngha:
Kiu d liu c bn l{ kiu d liu c gi| tr n, khng ph}n chia c na nh
s, k t
I.2.2. Phn loi:
Tn kiu ngha Kch
thc
Phm vi
char K t 1 byte -128 127
unsigned char K t khng du 1 byte 0255
unsigned short S nguyn ngn khng du 2 bytes 065535
Enum S nguyn c du 2 bytes -3276832767
short int S nguyn c du 2 bytes -3276832767
Int S nguyn c du 2 bytes -3276832767
unsigned int S nguyn khng du 2 bytes 0 65535
long S nguyn d{i c du 4 bytes -2147483648
2147483647
unsigned long S nguyn d{i khng du 4 bytes 04294967295
float S thc chnh x|c n 4 bytes 3.4 E-383.4 E+38
Double S thc chnh x|c kp 8 bytes 1.7 E-308 1.7
E+308
long double S thc chnh x|c hn
double
10 bytes 3.4 E-4932 1.1
E+4932
Ch :
1. Ngn ng C khng c kiu logic (boolean nh Pascal) m{ quan nim
0 l false ; Khc 0 l true
2. Ngn ng C khng c kiu chui nh kiu string trong Pascal
3. C|c kiu ng nht:
int = short int = short = signed int = signed short int
long int = long
signed long int = long
unsigned int = unsigned = unsigned short = unsigned short int
unsigned long int = unsigned long

P
a
g
e
1
4

I.3. Bin
I.3.1. Tn bin : Tn bin l{ mt chui k t bt u bng k t ch, k t k tip
l{ k t ch (du gch di _ c xem l{ k t ch) hoc s v{ khng c trng vi
c|c t kha ca C.
Ch : - Ngn ng C ph}n bit ch thng vi ch hoa nn bin ch thng vi
ch hoa l{ kh|c nhau.
V d : Bien_1 _bien2 l{ hp l
bi&en 2a a b l{ khng hp l
- Ngn ng C ch ph}n bit hai tn hp l vi nhau bng n k t u tin ca chng.
Thng thng n=8, nhng hin nay nhiu chng trnh dch cho php n=32, nh Turbo
C cho php thay i s k t ph}n bit t 8-32)
V d : Hai bin sau b xem l{ cng tn
bien_ten_dai_hon_32_ky_tu_dau_tien_1
bien_ten_dai_hon_32_ky_tu_dau_tien_2
I.3.2. Khai bo bin
C|c bin phi c khai b|o trc khi s dng nhm gip cho chng trnh dch
c th x l chng.
Khai b|o bin c dng :
Kiudliu tnbin1 [,tenbin2 ...] ;
V d: int a=0,b=1,c;
float x,y,delta;
char c;
* Khai b|o v{ khi to bin:
Kiu d liu tnbin = gi|tr ;
I.3.3. Hm nhp d liu chun
a) Hm scanf()
C php: scanf(chui-nhdng,ichthams1, ichthams2,...)
- Chui-nhdng ca scanf() gm c ba loi k t :
+ Chui iu khin
+ K t trng
+ K t kh|c trng
Chui iu khin c dng :
%[width][h/l] type
Vi type: x|c nh kiu ca bin a ch tham s s nhn gi| tr nhp v{o
Type ngha
d,i S nguyn c s 10 (int)
o S nguyn c s 8 (int)

P
a
g
e
1
5

u S nguyn c s 10 khng du (unsigned)
x S nguyn c s 16 (int)
f,e S thc (float)
c K t (char)
s Chui k t
p Con tr (pointer)
lf S thc (double)
Lf S thc (long double)
Width : x|c nh s k t ti a s nhn v{o cho vng .
H{m scanf() ch nhn cho width k t hoc cho n khi gp k t trng u tin.
Nu chui nhp v{o nhiu hn th phn cn li s d{nh li cho ln gi scanf() k tip.
V d 1: scanf(%3s,str);
Nu nhp chui ABCDEFG .
th scanf() s nhn ti a 3 k t ct v{o mng str, cn DEFG s c ly nu sau
c ln gi sanf(%s,str) kh|c.
V d 2: unsigned long money;
scanf(%lu,&money);
Lu : Nu scanf(%ul, &money) th gi| tr nhp v{o s khng c lu tr trong
bin money, nhng chng trnh dch khng b|o li.
V d 3: Nhp v{o tn v{ b gii hn trong khong [A-Z,a-z]
char name[20];
printf(Name : ) ;
scanf(%[A-Za-z],&name);
Trong trng hp n{y, nu ta g sai dng th name =
K t trng: nu c trong chui-dng s yu cu scanf() b qua mt hay nhiu
k t trng trong chui nhp v{o. K t trng l{ k t khong trng ( ), tab (\t), xung
h{ng (\n). Mt k t trng trong chui-nhdng s c hiu l{ ch nhp n k t
kh|c trng tip theo.
V d 4: scanf(%d ,&num);
H{m scanf() cho ta nhp mt k t kh|c trng na th mi tho|t ra. K t s
nm trong vng m v{ s c ly bi h{m scanf() hoc gets() tip theo.
K t kh|c trng: nu c trong chui-nhdng s khin cho scanf() nhn v{o
ng k t nh th.
V d 5: scanf(%d/%d/%d,&d,&m,&y);
H{m scanf() ch nhn mt s nguyn, ct v{o d, k n l{ du /, b du n{y i v{
ch nhn s nguyn k tip ct v{o m. Nu khng gp du / k tip s nguyn th
scanf() chm dt.
Ch : H{m scanf() i hi c|c tham s phi l{ c|c a ch ca c|c bin hoc l{ mt
con tr.

P
a
g
e
1
6

* To|n t a ch & : Ly a ch ca mt bin
V d 6: int n; bin n
&n; a ch ca n
printf(tr = %d, a ch = %d,n,&n);
b) Hm getch():
H{m getch() dng nhn mt k t do ta nhp trn b{n phm m{ khng cn g
Enter vi c ph|p :
ch = getch(); Khng hin k t nhp trn m{n hnh
ch = getche(); Hin k t nhp trn m{n hnh
Vi ch l{ bin kiu char.
V d 7:
void main()
{ char ch;
printf(Go vao ky tu bat ky : );
ch = getche();
printf(\n Ban vua go %c,ch);
getch();
}
V d 8: Bn nhp v{o 1 ch c|i. Nu ch c|i nhp v{o l{ 'd' th chng trnh s kt
thc, ngc li chng trnh s b|o li v{ bt nhp li.
#include <stdio.h>
#include <conio.h>
void main()
{ char ch;
printf("\nBan nhap vao 1 chu cai tu a den e: ");
while ((ch=getche()) != 'd')
{ printf("\nXin loi, %c la sai roi",ch);
printf("\n Thu lai lan nua. \n");
}
}
Lu : H{m getch() cn cho php ta nhp v{o 1 k t m rng nh c|c phm F1,
F2,.., c|c phm di chuyn cursor. C|c phm n{y lun c 2 bytes: byte th nht bng 0, cn
byte 2 l{ m~ scancode ca phm . nhn bit ta ~ g phm k t hay phm m rng,
ta c chng trnh sau:
void main()
{
int c;
int extended = 0;
c = getch();
if (!c)

P
a
g
e
1
7

extended = getch();
if (extended)
printf("The character is extended\n");
else
printf("The character isn't extended\n");
}
Phm M scancode
F1 59
F2 60
F3 61
F4 62
F5 63
F6 64
F7 65
F8 66
F9 67
F10 68
Home 71
72
80
75
77
PgUp 73
PgDn 81
End 79
Ins 82
Del 83
Bng m~ scancode ca c|c phm m rng
c. Hm kbhit(): Hm int kbhit() s kim tra xem c phm n{o c g v{o hay
khng. Nu c, h{m kbhit s tr v mt s nguyn kh|c 0, v{ ngc li.
K t m{ ta nhp v{o qua h{m kbhit() c th ly c qua h{m getch() hoc
getche().
V d:
void main()
{
printf("Press any key to continue:");
while (!kbhit()) /* do nothing */ ;
char kytu=getch();
printf("\nKy tu vua an : %c",kytu);
}

P
a
g
e
1
8

I.4 Hng: Hng l{ c|c i lng m{ gi| tr ca n khng thay i trong qu| trnh
chng trnh thc hin.
I.4.1. Phn loi :
a. Hng s : l{ c|c gi| tr s ~ x|c nh v{ khng i.
int unsigned long h 8 h 16 float/double
Dng nnnn
-nnnn
nnnnU/u

nnnnL/l
-nnnnl/L
0nnnn 0xnnnn nnnn.nnnn
nnnn.nnnE/ennn
V d 4567
-12
123U
12uL
456789L
-1234L
0345 0x1AB 123.654
123.234E-4
Ch :
- C|c hng s vit khng du hoc khng s m c hiu l{ s nguyn, ngc li
l double.
- C|c hng s nguyn ln hn int s c lu tr theo kiu long, cn ln hn long
th c lu tr theo kiu double.
- C|c hng s nguyn dng ln hn long s c lu tr theo kiu double
- Mt hng s c lu tr theo dng long nu theo s c k t l (L), dng
unsigned nu sau c ch u (U), dng thp lc ph}n nu trc s c 0x v{
dng b|t ph}n nu trc s c 0
V d: 50000; 10 L; Long
5U, 100u unsigned
0x10 h 16 = 1610
010 h 8 = 810
b. Hng k t : l{ k t ring bit c vit trong hai du nh|y n : A
Gi| tr ca hng k t l{ m~ ASCII ca n.
V d : printf(%c c gi| tr l{ %d,A,A);
A c gi| tr l{ 65
Hng k t c th tham gia v{o c|c php to|n nh mi s nguyn khc.
V d : 9-0=57-48=9
Hng k t c th l{ c|c k t c bit dng \c1 m{ ta ~ xt h{m printf() nh
\n,\a,\t ...
c. Hng chui : L{ mt chui k t nm trong hai du nh|y kp .
V d : Day la mot chuoi
Hang chuoi co ky tu c bit nh \ \n \248
chui rng.
Ch :
- Ph}n bit A = A
Hng: Chui K t
Dng lu tr :

P
a
g
e
1
9

A \0 A
- Nhn xt: dng lu tr, ta thy tn cng ca chui c k t NULL \0 m{ khng
c dng k t. Chnh v vy m{ khng c k t rng .
- Mt chui c th c vit trn nhiu h{ng vi iu kin h{ng trn phi c du
\.
V d : Day la mot chuoi duoc viet tren \
nhieu hang \n
d. Hng biu thc : L{ mt biu thc m{ trong c|c to|n hng u l{ c|c hng.
Khi chng trnh dch s tnh to|n biu thc trc, v{ kt qu c lu tr thng
bng mt hng s tng ng.
V d : 8*20-13 kt qu lu tr l{ 173
a -A l 97-65 = 32
1<8 l 0 (sai)
I.4.2. Khai bo hng:
C php: const tnhng = biuthc;
V d : const MAX = 50;
const PI = 3.141593;
Ch : - Ta c th khai b|o hng bng c|ch nh ngha 1 macro nh sau:
#define tnhng gi|tr
- Lnh #define phi c khai b|o ngo{i h{m v{ sau n khng c du ;
I.5. Php ton
I.5.1. Php gn:
C php: bin = biu thc;
Ch : Php g|n trong ngn ng C tr v mt kt qu l{ tr ca biu thc
V d 1 : c = 10;
a = b = c;
printf(a=%d , b=%d,a,b); a=10,b=10
V d 2 : x = b + 2*c; y= a + (x= b + 2*c)
y = a + x;
V d 3 : (n+3) = 4+z; (khng hp l v bn tr|i l{ biu thc)
= c +o; (khng hp l v bn tr|i l{ hng)
I.5.2. Cc php ton s hc :
a. Php ton hai ton hng : +, -, *, /, %
Php ton Kiu to|n hng Kiu kt qu
+, -, * char, int, long, float,
double
Kiu ca to|n hng c kiu cao nht
/ nguyn/nguyn Kiu nguyn v{ l{ php chia nguyn
thc(nguyn)/thc Kiu thc v{ l{ php chia thc

P
a
g
e
2
0

(nguyn)
% nguyn/nguyn Kiu nguyn v{ l{ php chia ly phn d
V d :
#include <stdio.h>
void main()
{ char cv;
int iv = 121;
float fv1,fv2;
printf( Chuyn kiu :\n\n);
cv = iv;
printf(int c g|n cho char : %d %d (%c)\n\n,iv,cv,cv);
fv1 = iv/50;
printf( int : %d / 50 = %f \n\n,iv,fv1);
fv1 = iv/50.0;
printf( float : %d / 50.0 = %f \n\n,iv,fv1);
fv1 = 1028.75;
fv2 = fv1 +iv ;
printf( %f + %d = %f \n\n,fv1,iv,fv2);
getch();
}
b. Php ton mt ton hng : php tng ++, php gim --
a++ hoc ++a a = a+1
a-- hoc --a a = a-1
Ch : Tuy nhin a++ s kh|c ++a khi chng ng trong biu thc (c php g|n).
a++ : Tng a sau khi gi| tr ca n c s dng.
++a : Tng a trc khi gi| tr ca n c s dng.
V d :
main() a b n
{ int a=4 , b=6, n;
n = a + b;
n = a++ + b;
n = ++a + b;
n = --a + b;
n = a-- + b;
n = a+ b;
}
4
4
5
6
5
4
4
6
6
6
6
6
6
6

10
10
12
11
11
10
I.5.3. Php gn phc hp:
C php: bin op= <biuthc> bin = bin op <biuthc>
Vi op l{ php to|n.

P
a
g
e
2
1

C|c php g|n phc hp : += , -= , *= , /= , %= , <<= , >>=
V d : n = n*(10+x) n *= (10 +x)
n = n % 10 n %= 10
I = I +3 I += 3
<< : l{ php dch chuyn bit qua tr|i .
>> : l{ php dch chuyn bit qua phi .
I.5.4. Php ton quan h:
< : nh hn
> : ln hn
>= : ln hn hoc bng
<= : nh hn hoc bng
!= : khc
== : bng
Ch :
- Ph}n bit to|n t so s|nh == vi php g|n =
- C khng c kiu d liu boolean m{ qui c : Gi| tr 0 l{ sai
Gi| tr !=0 l{ ng
V d:
a=10;
b= (a>6)*(a-6) b = 4
c= (a< 5)*(a-5) c = 0
V d: Tm s ln nht trong 3 s nguyn a, b, c
#include <stdio.h>
#include <conio.h>
void main ()
{ int a, b, c, max;
printf(Chng trnh tm s ln nht trong 3 s);
printf(Nhp a, b, c);
scanf(%d %d %d , &a, &b, &c);
max = a;
if (max<b) max = b;
if (max<c) max = c;
printf(S ln nht = %d, max);
getch();
}
I.5.5.Ton t logic:
To|n t ngha
NOT ! Ph nh
AND && Giao, v

P
a
g
e
2
2

OR || Hi
Th t tnh to|n t trn xung.
Bng ch}n tr:
x ! x x y x && y
true false true true true
false true true false false
false true false
false false false

x y x || y
true true true
false true true
false true true
false false false
V d 1: Xt k t c c phi l{ k s hay khng?
char c;
if (c >= 0 && c <= 9)
printf (% c l{ k t s , c);
V d 2: Xt k t ch l{ ch c|i hay khng?
if ((ch> =a) and (ch< =z)) or ((ch> =A) and (ch< =Z))
printf(%c l{ chu cai \n,ch);
V d 3:
int a=10, b=5, c=0;
a && b 1
a && c 0
a | | c 1

V d 4:
int a=10, b=5;
int i=2, j=0;
(a>b) && (i<j) 0
(a<b) | | (i>j) 1
V d 5:
n=5;
while (n)
{ printf("\nS n = %d",n);
n--;
}

P
a
g
e
2
3

I.5.6. Ton t phy:
C php:
T = (exp1, exp2, exp3 ); // T = kt qu ca exp3
V d: m= (t=2, t*t+3) m=7; t=2
c= (a=10,b=5,a+b); a=10, b=5, c=15
I.5.7. Ton t iu kin:
C php :
T = <iu kin> ? <bt1> : <bt2>;
Nu <iu kin> l{ ng th T = <bt1> , ngc li T = <bt2>
V d: A = i>= MAX ? 1: 0;
printf ( max (a,b) = %d , (a>b) ? a:b);
lower = (c > = A && c< = Z) ? c - A + a :c;
I.5.8. Ton t trn bit (bit wise) :
Dng K hiu ngha
NOT bit ~ ly b 1
AND bit & giao
OR bit | hi
XOR bit ^ hi loi tr
dch tr|i << nhn 2
dch phi >> chia 2


P
a
g
e
2
4

Bng ch}n tr:
Bit Bit Bit kt qu
A B ~ A A & B A | B A ^ B
0 0 1 0 0 0
0 1 1 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0
V d:
a= 4564 0001 0001 1101 0100
b= 13667 0011 0101 0110 0011
a & b 0001 0001 0100 0000
a | b 0011 0101 1111 0111
a ^ b 0010 0100 1011 0111
ngha:
1. Php AND bit thng c dng kim tra mt bit c th n{o trong th{nh
phn d liu x c tr 0 hay 1. Vic n{y thc hin bng c|ch s dng mt mt n (mask)
vi bit cn quan t}m bng 1 cn c|c bit kh|c bng 0. Ta ly mask AND vi gi| tr x. Nu
kt qu thu c bng mask th l{ bit cn quan t}m l{ 1, ngc li l{ 0.
V d 1:
void main()
{ unsigned x1; x2;
printf (\n cho 2 s hex(2 s) );
scanf (%x %x , &x1, &x2);
printf (% 02x & % 02x = % 02x\n, x1, x2, x1& x2);
}
V d 2: Ta mun bit bit th 3 ca s hexa ch l{ 1 hay 0 :
void main()
{ unsigned char ch, kq;
printf ( \n cho 1 s hex 2 s :);
scanf ( %x, &ch);
kq= ch & 0x08;
if (kq== 0x08) printf (bit 3 = 1);
else printf (bit 3 = 0);
}
2. Php OR dng bt c|c bit cn thit ln cng nh v{o mt mt n. Chng hn
nh ta mun bt bit th 7 ca bin ch (unsigned char ch) ln 1:
ch = ch | 0x80;
V d 3:

P
a
g
e
2
5

void main()
{ unsigned char x1,x2;
printf (\n cho 2 s hex (ff hay nh hn) :);
scanf (%x %x, &x1, &x2);
printf ( %02x | %02x %02x \n, x1, x2, x1| x2);
}
3. Php XOR dng lt bit ngha l{ ho|n chuyn 01
V d 4: lt bit 3 ta c chng trnh:
void main()
{ unsigned char ch;
printf ( nhp 1 s hex < = ff :);
scanf (%x, &ch);
printf (%02x ^ 0x08 = %02x \n , ch, ch ^ 0x08);
}
4. To|n t << , >>
<< dch sang tr|i (nh}n 2)
>> dch sang phi (chia 2)
V d 5: num = 201 (0x00c9)
num : 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1

num << 2 : 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0
Kt qu = 0x0324 804 ngha l{ 201* 4
V d 6:
void main()
{ unsigned char x1, x2 ;
printf ( nhp 1 s hex < = ff v{ s bit : );
scanf ( %x %d , &x1, &x2);
printf ( %02x >> %d = %02x \n, x1, x2, x1>> x2);
}
Ch : Trong php dch phi C l{m theo 2 c|ch kh|c nhau ty thuc v{o kiu d
liu ca to|n hng bn tr|i.
- Nu to|n hng bn tr|i kiu unsigned th php dch s in 0 v{o c|c bit bn tr|i.
- Nu to|n hng bn tr|i kiu signed th php dch s in bit du v{o c|c bit bn
tri
V d 7: unsigned int num;
num = 39470; // 9A2E hexa
num =
num >> 2
1 0 0 1
9867 = 0x268B
1 0 1 0

0 0 1 0

1 1 1 0


P
a
g
e
2
6

=
0
0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 1
V d 8 : int num; // 9A2E hexa
num = -26066
num =
num >> 2
=
1
1 0 0 1
-6517 = 0xE68B
1 1 1 0
1 0 1 0

0 1 1 0
0 0 1 0

1 0 0 0
1 1 1 0

1 0 1 1
V d 8: Chng trnh i s hex ra s nh ph}n :
#include <stdio.h>
#include <conio.h>
void main()
{ int num;
unsigned int mask;
clrscr();
printf ("Chuong trinh doi so hexa sang nhi phan\n");
printf ("Nhap vao so hexa :");
scanf("%x",&num);
mask = 0x8000;
printf("\n Dang nhi phan cua so %x la ",num);
for (int j=1; j<=16; j++)
{ printf("%d",mask & num?1:0);
if (j==4 || j==8 || j==12) printf("-");
mask >>=1;
}
getch();
}
V d 9: Chng trnh m|y tnh bitwise
}y l{ chng trnh gi lp mt m|y tnh thc hin c|c to|n t bitwise.
#define TRUE 1
main()
{ char op[10];
int x1, x2;
while (TRUE)
{ printf (\n \n Cho biu thc ( vd ffoo & f11) : );
printf (\n);
switch ( op[0])
{ case &:
pbin (x1); printf (& (and) \n );
pbin (x2);

P
a
g
e
2
7

pline (); pbin (x1 & x2);
break;
case |:
pbin (x1); printf (| \n );
pbin (x2);
pline (); pbin (x1 | x2);
break;
case ^:
pbin (x1); printf (^ \n);
pbin (x2);
pline (); pbin (x1 ^ x2);
break;
case >:
pbin (x1); printf ( >>); printf (%d \n ,x2);
pline (); pbin (x1 >> x2);
break;
case <:
pbin (x1); printf (<<); printf (%d \n, x2);
pline (); pbin (x1 << x2);
break;
case ~:
pbin (x1); printf (~ \n);
pline (); pbin (~ x1);
break;
default : printf (To|n t khng hp l /n );
}
}
}
pbin (num)
int num;
{ unsigned int mask;
int j, bit;
mask = 0x8000;
printf (%04x, num);
for(j=0; j<16; j++)
{ bit = ( mask & num ) ? 1:0;
printf (%d, bit);
if (j= = 7) printf (- -);
mask >> = 1;
}
printf (- -);
mask >> 1;
}
pline ()

P
a
g
e
2
8

{ printf (- - - - - - - - \n);
}
* S chuyn kiu bt buc:
Trong C c 2 trng hp chuyn kiu: chuyn kiu t ng v{ chuyn kiu bt
buc.
Chuyn kiu bt buc: c |p dng khi chuyn kiu t ng khng c.
C php: (Type) biu thc
V d: d = (float) (f - 32)
int a= 100, b=6;
double f;
f =a/b // kt qu f=16
f= a/ (double)b // kt qu f= 100.0 / 6.0= 16.666.
* Mc u tin ca c|c php to|n:
u tin Php ton Th t kt hp
1 () [ ]
2 ! ~ ++ - - (type) * & size of
3 * / %
4 + -
5 << >>
6 < <= > >=
7 = = !=
8 &
9 ^
10 |
11 &&
12 | |
13 ?
14 = + = - = ..
V d 1: 3/4 * 6 # 3*6 /4
0 * 6 18 /4
0 4
V d 2: (float) 2 /4 # (float) (2/4)
2.0 /4 (float) 0
0.5 0.0
I.6. Chui
I.6.1. nh ngha :Chui l{ mt mng m{ c|c phn t ca n c kiu k t.

P
a
g
e
2
9

Khai b|o mt chui k t cha ti a 49 k t
char chui[50];
* Lu : Tt c c|c chui u c kt thc bng k t NULL (\0). Do , nu
chui d{i 50 th ta ch c th cha ti a 49 k t.
I.6.2. Khi ng tr:
char chui[ ] = {A, N, H, \0};
char chui[ ] = "ANH";
I.6.3. Nhp / xut chui:
a. Nhp chui:
gets (chui)
b. Xut chui:
puts (chui)
Ch :
- Khi nhp chui th khng c dng h{m scanf v h{m scanf khng chp nhn
khong trng.
V d: scanf(%s, chui); // ta nhp v{o Nguyn Vn \i th
// chui = Nguyn v h{m scanf ct khong trng
- Khi dng hm gets trong chng trnh th khng nn dng h{m scanf bt k }u
d rng dng h{m scanf nhp s m{ ta nn dng h{m gets v{ h{m atoi, atof nhp
s.
V :
scanf(%d, &n); // ta nhp s 5 .
gets (chui); // lc ny chui = (chui rng)
I.6.4. Hm chuyn i s sang chui v ngc li
sint = atoi (chuis) // chuyn chui s sang s nguyn
sf = atof (chuis) // chuyn chui s sang s thc
* Hai h{m n{y nm trong < stdlib .h >
I.6.5. Cc hm v chui: (# include < string. h> )
- int strlen(S) : tr v chiu d{i chui S.
- int strcmp(S1, S2): so s|nh chui S1 vi S2. Nu chui S1 ging S2 kt qu bng
0. Nu chui S1< S2 kt qu l{ }m, nu chui S1> S2 kt qu > 0.
- int stricmp(S1, S2): so s|nh chui S1, S2 khng ph}n bit ch thng hay ch
hoa
- int strncmp(S1, S2, n): ch so s|nh n k t u ca 2 chui S1, S2 vi nhau.
- int strnicmp(S1, S2, n): ch so s|nh n k t u ca 2 chui S1, S2 vi nhau,
khng ph}n bit ch thng, ch hoa
- strcpy(dest, source): chp chui t ngun source sang ch dest
V d: char string[10];
char *str1 = "abcdefghi";
strcpy(string, str1);

P
a
g
e
3
0

printf("%s\n", string); // "abcdefghi"
- strncpy(dest, source, n): chp chui t ngun sang ch vi nhiu nht l{ n k
t.
V d:
char string[10];
char *str1 = "abcdefghi";
strncpy(string, str1, 3); // string = "abcx1zwe12"
string[3] = '\0'; // t k t kt thc chui v{o cui chui.
printf("%s\n", string); // "abc"
- strcat(dest, src): ni chui src v{o sau chui dest. Chiu d{i ca chui kt qu
bng strlen(dest) + strlen(src)
V d:
char destination[25];
char *blank = " ", *c = "C++", *turbo = "Turbo";
strcpy(destination, turbo); // destination = "Turbo"
strcat(destination, blank); // destination = "Turbo "
strcat(destination, c); // destination = "Turbo C++"
- strncat(dest, src, n): ni nhiu nht l{ n k t ca src v{o cui chui dest, sau
thm k t null v{o cui chui kt qu.
V d:
char destination[25];
char *source = " States";
strcpy(destination, "United");
strncat(destination, source, 6);
printf("%s\n", destination); // destination = "United State"
- char * strchr(s, ch): tr v a ch ca k t ch u tin c trong chui S; nu
khng c th tr v NULL (thng dng ly h)
V d:
char string[15];
char *ptr, c = 'r';
strcpy(string, "This is a string");
ptr = strchr(string, c);
if (ptr)
printf("K t %c v tr: %d\n", c, ptr-string);
else
printf("Khng tm thy k t %c\n",c);
- char * strstr(S1, S2): tr v v tr ca chui S2 trong chui S1; nu S2 khng c
trong S1 th h{m strstr tr v tr NULL.
I.6.6. Mng cc chui
*Khai bo: Khai b|o bin ds cha ti a 50 chui k t, mi chui k t c ti a

P
a
g
e
3
1

30 k t.
char ds[50 ] [30];
Ch :
- Khng nn g|n chui vi chui (s1= s2) m{ phi dng h{m strcpy(S1,S2)
- Khng c so s|nh 2 chui bng c|c to|n t quan h (S1== S2, S1>S2,
S1>= S2), m{ phi dng h{m strcmp(S1,S2).
V d: Vit chng trnh tm kim 1 t trong 1 c}u
# include < string.h>
# include < stdio.h>
void main ()
{ char cau[80], t[7], *ptr;
printf(Nhp c}u :);
gets(cu);
printf(Nhp t :);
gets(t);
ptr = strstr(c}u, t);
if (ptr == NULL) printf(Khng c t);
else printf(c t);
}
II. CC CU TRC IU KHIN TRONG C:
Ngn ng C l{ ngn ng lp trnh cp cao c cu trc, gm: cu trc tun t, chn, v{
lp.
II.1 Cu trc tun t (Sequence) :
C|c lnh trong chng trnh c thc hin tun t t lnh n{y n lnh kh|c cho
n khi ht chng trnh.
V du : Vit chng trnh tnh v{ in ra din tch ca hai ng trn b|n knh ln lt
l{ 3m v{ 4.5m cng vi hiu s ca 2 din tch.
#define PI 3.14159
#include <stdio.h>
#include <conio.h>
void main()
{
float r1, r2, hieuso;
clrscr();
printf("\nCHUONG TRINH TINH DIEN TICH 2 HINH TRON VA HIEU SO\n");
printf("Ban kinh hinh tron thu nhat : ");
scanf("%f",&r1);
printf("Ban kinh hinh tron thu hai : ");

P
a
g
e
3
2

scanf("%f",&r2);
printf ("Dien tich hinh tron 1 = %.2f\n",PI*r1*r1);
printf ("Dien tich hinh tron 2 = %.2f\n",PI*r2*r2);
hieuso = PI*r1*r1 - PI*r2*r2;
printf ("Hieu so dien tich 2 hinh tron = %.2f\n",hieuso);
getch();
}
II.2. Cu trc chn
K hiu : k l{ biu thc Logic
S1, S2 l{ c|c ph|t biu hay 1 nhm c|c ph|t biu (lnh)
II.2.1. Lnh if else:
C php:
if (k) S1;

if (k) S1;
else S2;

Ch : C|c lnh if else lng nhau
if (k1) S1;
else if (k2) S2;
else if (k3) S3;
S4;
V d 1: Tm max(a,b,c)
K
NO
YES
S1
K S1
S2
NO
YES

P
a
g
e
3
3

if (a>b)
if (a>c) max=a;
else max=c;
else if (b>c) max =b;
else max= c;
V d 2: Tnh hm f(x) :
f(x) = x
2
, nu -2 < = x< 2
4 , x > = 2
if (x>=-2 && x<2)
fx= x*x;
else if (x>=2)
fx= 4;
else { printf("\n Khong xac dinh") ; exit(0) ;}
II.2.2. Lnh chn la: switch_case
C php:
switch (biu thc)
{ case hng 1: S1;
case hng 2: S2; break;
.
.
.
case hng 3: Sn; break;
default: S0;
}
Cch hot ng:
- (biuthc) c kt qu nguyn
- Hng: k t, s nguyn, biu thc c s nguyn
- Nu kt qu bng hng I n{o th n s l{m lnh Si v{ tun t thc hin ht c|c
lnh di cho n khi ht lnh switch.
- Mun ngt s tun t trn th phi dng lnh break.
V d: Nhp 1 k t s dng hex i ra s thp ph}n
#include <stdio.h>
#include <conio.h>
void main()
{
unsignedchar ch;
int k;
clrscr();
printf("Nhap 1 ky tu so hex : ");
ch=getche();

P
a
g
e
3
4

switch (ch)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': k=ch-'0'; break;
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
case 'F':k=ch-'A'+10; break;
case 'a':
case 'b':
case 'c':
case 'd':
case 'e':
case 'f': k= ch-'a'+10; break;
default: k=0;
}
printf ("\nSo thap phan cua ky tu hexa %c la %d ",ch,k);
getch();
}
V d: Vit chng trnh to 1 m|y tnh c 4 php to|n + , - , * , /
#include <stdio.h>
#include <conio.h>
void main()
{
float num1, num2;
char op;
clrscr();
printf ("Go vao so, toan tu, so \n");
scanf("%f %c %f", &num1, &op, &num2);
switch (op)
{
case '+': printf("= %f",num1+num2);
break;

P
a
g
e
3
5

case '-': printf("= %f",num1-num2);
break;
case '*': printf("= %f",num1*num2);
break;
case '/': printf("= %f",num1/num2);
break;
default : printf("To|n t l, khng bit");
}
}
II.3. Cu trc lp
II.3.1. Lnh while:
C php:
while (bt)
S;

Ch : Trong phn th}n lnh phi c bin iu khin vng lp.
V d 1: Vit chng trnh in ra bng m~ ASCII
void main ()
{ int n=0;
while (n <= 255)
{ printf(%c c m~ ASCII l{ %d, n, n);
n ++
}
}
V d 2: Nhp mt chui k t, v{ kt thc nhp bng ESC
#define ESC \ 0x1b
#include <stdio.h>
#include <conio.h>
void main()
{ char c;
while (1)
K
NO
YES
S

P
a
g
e
3
6

if ((c = getche() ) == ESC ) break;
}
V d 3: Vit chng trnh in bng cu chng
void main ()
{ int a, b;
b = 1;
while (b < = 9)
{ a = 2;
while (a < = 9)
{ printf(%d * %d = %d \t, a, b, a*b);
a++;
}
b ++;
printf(\n);
}
}
II.3.2. Lnh do while:
C php:
do
S
while (bt);

V d 1: Vit chng trnh in bng m~ ASCII
#include <stdio.h>
main ()
{ int n=0;
do
{ printf(%c c m~ ASCII %d\n, n, n);
n ++;
} while (n <= 255);
}
II.3.3. Lnh for:
C php:
for ([bt_khi ng] ; [bt_k] ; [btlp])
S ;
V d 1: Lp lnh S t 1 n 10
for (int I=1; I== 10; I++) sai
S;
S
k
No
Yes

P
a
g
e
3
7

for (int I=10; I>= 1; I--) ng
S ;
V d 2: for ( ; 1 ; )
{ c = getch()
if (c == ESC) break;
}
So s|nh vng lp while - for:
bt_khi ng;
while (BiuThc_K)
{ S;
BT_lp;
}
for ( bt_khi ng; bt_k; bt_lp)
S;
V d 3: Vit chng trnh in ra bng cu chng bng vng for
void main ()
{ int a;
for (a=2; a<= 9; a++)
{ for (b =1; b <= 9; b++)
printf(%d* %d = %d \t, a, b, a*b);
printf(\n);
}
}
V d 4: Vit chng trnh tnh n giai tha
void main ()
{ long gt = 1;
for (int i =1; i<= n; i++)
gt = gt * i;
printf(%d! = %u \n, n, gt);
}
V d 5: Vit chng trnh tnh biu thc:
(1 + 1/1
2
) * (1 + 1/2
2
) *......... (1 + 1/ n
2
)
void main ()
{ int i, n;
float S;
printf(Nhp s :);
scanf(%d, &n);
S = 1;
for (i= 1;i<= n; i++)
S = S*(1+1.0 / (i*i));
printf(\nKet qua = %f, S)

P
a
g
e
3
8

}
* Ph|t biu break, continue, goto:
1. Break:
Lnh break cho php tho|t ra sm khi vng lp ( whiledo , for, dowhile), lnh
switch.
2. Lnh continue:
Lnh continue ch dng trong vng lp l{m cho chng trnh nhy tt v iu kin
kim tra ca vng lp bt u mt vng lp mi.
V d: Vit chng trnh nhp mt c}u ch thng kt thc bng du chm, xut
ra bng ch hoa
void main ()
{ char ch;
while (1)
{ ch = getch ();
if ((ch> = a) && (ch< = z))
printf(%c, ch - a + A);
if (ch == ) continue;
if (ch == .) break;
}
}
3. Lnh goto: dng chuyn iu khin chng trnh v mt v tr n{o .
C php: Goto nhn;
Lnh goto s chuyn iu khin chng trnh ngay lp tc v v tr t nh~n.
V d:
Again:
;
.
.
goto Again;

B{i tp:
1. Vit chng trnh tnh din tch
- Hnh vung
- Hnh thang
- Tam gi|c thng
- Tam gic vung
- Hnh trn
2. Tnh khong c|ch mt im (X0, Y0) ti mt ng thng Ax + By + C = 0

P
a
g
e
3
9

B A
C By
Ax
S
2 2
0
0
+
+ +
=
, nhp A, B, C, X0, Y0
3. Cho 3 s thc x, y, z. Tm
a. Max(x+y+z, x*y*z)
b. Min
2
((x+y+z) / 2, x*y*z) +1
4. Vit chng trnh tm s ln nht trong 3 s nguyn a,b, c
5. Gii phng trnh bc 2 Ax
2
+Bx+C = 0 trn trng s thc.
6. Vit chng trnh tnh din tch hnh trn, bit b|n knh r dng; Chng trnh c
kim tra s liu nhp v{o, nu r <=0 th chng trnh b|o li v{ bt nhp li.
7. Vit chng trnh nhp s thp lc ph}n in ra s nh ph}n, c 4 s th c|ch mt
khong trng.
8. Vit chng trnh to 1 m|y tnh gm c|c php to|n sau : + , - , * , / , ^ (a
x
vi x
nguyn dng), @ (e
x
)
9. Vit chng trnh kim tra 1 bit bt k ca s bng 0 hay 1
10. Vit chng trnh tnh kt qu ca mt s sau khi dch phi hoc dch tr|i n ln.
11. m s ln xut hin ca t mt trong 1 c}u
12. Thay th 1 t trong 1 c}u bng 1 t kh|c.
13. Nhp h tn, t|ch hoten ra l{m 2 phn h v{ tn ring.
14. Vit chng trnh i c|c k t u ca c|c t ra ch in, c|c k t cn li ra ch
thng.
15. Vit chng trnh cho php ta kim tra mt password l{ ng hay sai (nhp ti a
password 3 ln).
16. Cho chui s, vit chng trnh di chuyn ch t bn tr|i qua bn phi ca m{n hnh
ti dng 5. Qu| trnh di chuyn dng li khi ta n phm ESC.
17. Bn h~y vit chng trnh tnh gi| tr tng cng ca mt sn phm c k c thu, bit
rng t sut thu l{ 13.6% tnh trn gi| gc. Gi| gc ca sn phm va so luong cua
san pham c c v{o, v{ cn in ra:
- Tin thu
- Gi| ~ c thu
18. Trong mt k thi cui kha, c|c hc vin phi thi 4 mn : mn I h s 2, mn II h s
4, mn III h s 1, mn IV h s 2, im c|c mn cho ti a l{ 10 im. Vit chng
trnh nhp im ca 4 mn v{ tnh im trung bnh.
19. Mt ngi b|n ru b|n N chai ru c n gi| l{ P. Nu tng s tin vt qu|
5000000 th vic chuyn ch l{ min ph, nu khng ph chuyn ch thng c
tnh bng 1% tng tr gi| h{ng. Vit chng trnh nhp v{o N, P. In ra c|c chi tit
Tng tr gi| h{ng, tin chuyn ch, v{ tng s tin phi tr.
20. Mt sinh vin d tuyn c c|c chi tit sau : h tn, im L1 ca ln 1, im L2 ca ln
2, im thi cui k CK. Vit chng trnh x|c nh xem mt sinh vin c c tuyn
hay b loi, bit rng s c tuyn nu im c tnh theo cng thc sau ln hn
hay bng 7 : Max( (L1+L2+CK)/3, CK).

P
a
g
e
4
0

21. Vit chng trnh cho bit tin lng h{ng ng{y ca mt ngi gi tr. C|ch tnh l{
15000/gi cho mi gi trc 14 gi v{ 25000 /gi cho mi gi sau 14 gi. Gi bt
u v{ gi kt thc cng vic c nhp t b{n phm.
22. Cho 3 s thc x, y z
a. Tn ti hay khng mt tam gi|c c 3 cnh c d{i x, y, z ?
b. Nu l{ tam gi|c th n vung, c}n, u hay thng
23. Gii h phng trnh bc nht:
ax+by = c
ax+by = c
Hng dn:
D = a b
a b
= ab - ab
Dx= c b
c b
= cb - cb
Dy= a c
a c
= ac - ac
if D!= 0 x= Dx/D; y= Dy/ D
else if (( Dx != 0) | | ( Dy != 0)) pt v nghim
else pt v nh
24. Gii h phng trnh 3 n s bc nht
a1 x + b1 y + c1 z = d1
a2 x + b2 y + c2 z = d2
a3 x + b3 y + c3 z = d3
25. Vit chng trnh gii phng trnh trng phng ax
4
+ bx
2
+ c = 0
26. Ngi ta mun lp ha n cho kh|ch h{ng ca Cng ty in lc. Ch s u v{ ch s
cui k s c cho bit. Bit rng biu gi| c tnh ty theo in nng tiu th.
- Nu in nng tiu th nh hn 100Kwh, gi| mi Kwh l{ 500.
- Nu in nng tiu th t 100Kwh tr ln, th mi Kwh di ra s c tnh gi| l{
800
- Ph khu vc l{ 5000 cho mi kh|ch h{ng. Vit chng trnh tnh tin phi tr
tng cng gm tin in, v{ ph khu vc
27. Bit 2 s X, Y biu din thi gian tnh theo gi}y. Ngi ta mun vit chng trnh :
- c 2 s n{y v{ in ra tng ca chng
- Chuyn c|c s n{y v{ tng ra dng gi, pht, gi}y ca chng ri in ra. Kim xem kt
qu ca 2 c|ch tnh c nh nhau khng?
28. Vit chng trnh in bng cu chng t 2 9 theo hng ngang
29. In tam gi|c *, hnh ch nht *, rng - c
30. V lu v{ vit chng trnh tnh :
a. 1+2+...+n

P
a
g
e
4
1

b. 1+3+5+...+2n-1
c. 2+4+6+...+2n
d. 1
2
+ 2
2
+ 3
2
+...+n
2

e. 1/1+ 1/2+ 1/3+...+ 1/n
f. 2+4+8+...+2
n

g. 1+ 1/2
2
+ 1/3
2
+....+ 1/n
2

31. Cho epsilon = 0.000001, x|c nh c|c tng sau }y sao cho s hng cui cng ca
tng l{ khng |ng k (s hng cui cng < epsilon )
a. 1/1+ 1/2+ 1/3+1/4+.....
b. 1+ 1/2
2
+ 1/3
2
+....+...
32. Vit chng trnh in ra bng m~ ASCII, 16 k t trn 1 dng.
33. V lu v{ vit chng trnh :
a. Xt mt s c phi l{ s nguyn t hay khng ?
b. In trn m{n hnh 100 s nguyn t u tin
34. Vit chng trnh cho php mt k t ngu nhin ri trn m{n hnh. Nu ngi s
dng khng kp n phm tng ng v{ chm |y m{n hnh th thua cuc.
35. Cho hm Fibonacci:

Fn =
{
1 ; n=0,1
Fn-1 + Fn-2 ; n>=2
a. Tm Fn, vi n do ta nhp
b. In ra N phn t u tin ca d~y Fibonacci
36. Vit chng trnh c v{o s nguyn N v{ in ra 1*2*3*..*N cho n khi N <=0.
37. Cho 1 d~y gm mt triu t 32 bit, h~y m s bit 1 trong mi t.
38. Vit chng trnh o|n s : ngi chi s o|n 1 s trong phm vi t 0 n 100, ti
a 5 ln. Chng trnh kim tra kt qu v{ xut thng b|o hng dn:
- S bn o|n ln hn
- S bn o|n nh hn
- Bn o|n ng
- M|y thng cuc

P
a
g
e
4
2

III. HM - QUY:
III.1. Hm:
III.1.1. Mc ch: Hm l mt chng trnh con ca chng trnh chnh, vi c|c
mc ch sau:
* Tr|nh vic lp i lp li c|c on chng trnh ging nhau, nh , ta s tit
kim lc lp trnh.
* T chc chng trnh: Dng h{m ta s ph}n mnh chng trnh th{nh nhng
khi nh c lp, mi khi l{ mt h{m thc hin mt cng vic n{o . Tng h{m s
c lp trnh, kim tra ho{n chnh; Sau , ta kt li to chng trnh ho{n chnh.
Nh vy, chng trnh v sau d hiu v{ d sa.
* Tnh c lp: cho php h{m c lp vi chng trnh chnh. V d h{m c nhng
bin cc b m{ chng trnh chnh v{ c|c h{m kh|c khng th ng ti. Do , nu ta c
khai b|o c|c bin trng tn vi c|c h{m kh|c th cng khng s nh hng ti c|c bin
trng tn .
Ch :
- C khng cho php c|c h{m lng nhau ngha l{ c|c h{m u ngang cp nhau (c th
gi ln nhau).
- C khng ph}n bit th tc hay h{m, m{ ch quan t}m n kt qu tr v ca h{m.
Nu h{m khng tr v kt qu g c th c th xem l{ th tc.
V d: V hnh ch nht c bng du *:
#include <stdio.h>
#include <conio.h>
void ve_hcn(int d,int r) // khai b|o void cho bit h{m khng tr v tr n{o c
{ int i,j ; // i, j l{ 2 bin cc b trong h{m ve_hcn
for (i=1;i<=r;i++)
{
for (j=1;j<=d; ++j)
printf("*");
printf("\n");
}
}
void main()
{ int d=20, r=5;
clrscr();
ve_hcn(d,r); // li gi h{m
getch();
}
III.1.2. C php nh ngha hm
C php:
Kiu tnh{m (ds i s)
{ Khai b|o bin cc b;
lnh;

P
a
g
e
4
3

[ return (expr);]
}
- Kiu: L{ kt qu tr v ca h{m. Nu khng ghi kiu, C s t hiu l{ kiu int. Nu
khng mun c kt qu tr v th ghi kiu void.
- Danh s|ch i s: Lit k c|c i s v{ kiu ca i s gi n h{m, c|ch nhau
bi du ','. Nu khng c i s ta ch cn ghi()
- Lnh return: c c|c dng sau:
return;
return (expr);
return expr;
V d: H{m chuyn ch thng sang ch hoa
#include <stdio.h>
#include <conio.h>
Get_upper(char ch)
{ return (ch >='a' && ch <='z')? ch-'a'+'A':ch;
}
void main()
{ char ch;
printf("\nNhap vao ky tu bat ky ");
ch=getche();
printf("\nKy tu %c qua ham Get_upper tro thanh %c",ch,Get_upper(ch));
getch();
}
Lu :
- Hn ch ca lnh return l{ ch tr v mt kt qu.
- Lnh return khng nht thit phi cui h{m. N c th xut hin bt k ni
no trong hm. Khi gp lnh return, quyn iu khin s chuyn ngay v chng
trnh gi.
III.1.3. Cc loi truyn i s
a. Truyn theo tr
#include <stdio.h>
#include <conio.h>
int max (int a,int b)
{ int m= a>b?a:b;
a=a*100;
b=b*100;
return m;
}
void main()
{ int a,b,c;

P
a
g
e
4
4

clrscr();
printf("\nChuong trinh tim Max(a,b)\n");
printf("Nhap a b : ");
scanf("%d %d",&a,&b);
c=max(a,b);
printf("\nGia tri lon nhat =%d",c);
printf("\nGia tri a =%d",a);
printf("\nGia tri b =%d",b);
getch();
}
Gi s ta chy chng trnh trn:
Nhap a b : 12 24
Gia tri lon nhat =24
Gia tri a =12
Gia tri b=24
Nhn xt:
- Ta nhn thy rng gi| tr hai bin a, b trc v{ sau khi v{o h{m max l{ khng thay
i (mc d trong h{m max, c hai bin a v{ b u thay i); l{ c ch ca s truyn
i s theo tr.
Li gi h{m: tnhm (ds isthc);
- Nu truyn i s theo tr th i s thc c th l{ bin, hoc c th l{ biu thc.
V d: c = max(1000,b);
b. Truyn theo a ch: i s thc l{ a ch ca bin
#include <stdio.h>
#include <conio.h>
max (int &a,int b)
{ int m= a>b? a : b;
a=a *100;
b=b*100;
return m;
}
void main()
{ int a,b,c;
clrscr();
printf("\nChuong trinh tim Max(a,b)\n");
printf("Nhap a b : ");
scanf("%d %d",&a,&b);
c=max(a,b); // a l{ tham s thc bin
printf("\nGia tri lon nhat =%d",c);
printf("\nGia tri a =%d",a);

P
a
g
e
4
5

printf("\nGia tri b =%d",b);
getch();
}
Gi s ta chy chng trnh trn:
Nhap a b : 12 24
Gia tri lon nhat =24
Gia tri a =1200
Gia tri b=24
Nhn xt:
- Ta nhn thy rng gi| tr bin a trc v{ sau khi v{o h{m max ~ thay i; l{
c ch ca s truyn i s theo a ch.
Li gi h{m: tnhm (tnbin);
- Nu truyn i s theo a ch th tham s thc bt buc phi l{ mt tn bin.
V d: c = max(1000,b); l sai
V d: Vit h{m giaoho|n ho|n i gi| tr ca 2 bin nguyn a,b.
void giaohoan (int &a, int &b)
{ int tam;
tam = a;
a = b;
b = tam;
}
void main()
{ int a,b;
printf ("a, b = ");
scanf ("%d %d", &a, &b); // a=10 , b=20
giaohoan(a, b);
}
* Truyn i s l{ mng gih{m (mang)
h{m (kiu mang[]) hoc h{m(kiu *mang)
V d: Cng thm mt hng s v{o mng tn l{ dayso.
#define SIZE 5 // d~y s c 5 s
#include <stdio.h>
#include <conio.h>
void add_const(int *a, int n, int con) // int *a int a[]
{ for (int i=0; i<n; i++)
*a = *(a++) + con;
}
void main()
{ int dayso [SIZE] = {3,5,7,9,11};

P
a
g
e
4
6

int konst = 10;
add_const(dayso, SIZE, konst);
printf("\nDay so sau khi cong them hang so :");
for (int i=0; i<SIZE; i++)
printf("%d ", *(dayso+i)); // *(dayso+i) dayso[i]
getch();
}
III.1.4. Khai bo nguyn mu ca hm
- Khai b|o h{m theo nguyn mu i hi phi khai b|o kiu d liu ca i s nm
trong nh ngha h{m ch khng t chng trn c|c dng ring.
- C khng nht thit phi khai b|o h{m theo nguyn mu. Tuy nhin, nn c v n
cho php chng trnh dch ph|t hin c li do khng ng kiu d liu gia tr truyn
n h{m v{ tr m{ h{m mong mun.
V d:
float dinhthuc (float a, float b, float c, float d)
{ return (a*d- b*c);
}
void main()
{ float a ,b, a1, b1;
printf(Nhap a,b,a1,b1:);
scanf(%f %f %f %f,&a,&b,&a1,&b1);
printf(Dinh thuc = %f,dinhthuc(a,b,a1,b1);
getch();
}
III.1.5. Phm vi tn ti ca bin:
a. Bin ton cc: l{ bin c khai b|o ngo{i c|c h{m ( k c h{m main). N
c php truy nhp n t tt c c|c h{m trong sut thi gian chng trnh hot ng.
V d: Khai bo ngoi hm main
Kiu tn bin; // bin to{n cc
void main()
{
}
b. Bin cc b: l{ bin c khai b|o trong c|c h{m, k c trong h{m main. N
khng cho php c|c h{m kh|c truy nhp n n. N tn ti trong thi gian sng
ca h{m cha n.
void main()
{ kiu tn bin; bin cc b trong h{m main()
}
c. Bin ngoi : l{ bin m{ c|c h{m c th truy xut ti m{ khng phi ph}n phi
b nh. N c dng c|c h{m trn c|c tp tin kh|c nhau lin kt li.

P
a
g
e
4
7

External Kiu tn bin;
void main()
{
}
d. Bin tnh : l{ mt bin cc b ca mt h{m nhng vn gi gi| tr ca ln gi
h{m cui cng
void main()
{ static Kiu tnbin;
}
e. Bin thanh ghi : l{ mt bin s dng c|c thanh ghi ca CPU tng tc truy
xut
register Kiu tnbin ;
III.1.6. Cc dn hng tin x l
III.1.6.1. #define
a. nh ngha hng:
#define tn hng gi| tr
V d: #define PI 3.14
#define MAX 100
#define THONGBAO Ht Gi|"
#define khoangtrang
b. nh ngha Macro:
#define tnmacro (i s ) thao tc
V d: #define sqr (x) x*x
#define sum (x,y) x+y
a = b * sum (x,y); // a = b * x+y;
#define sum (x,y) (x+y)
a = b * sum (x,y); // a = b * (x+y);
*Ch : Trong c|c thao t|c Macro nn s dng c|c du ngoc tr|nh dn ra mt
kt qu sai
V d: #define max (a,b) ((a) > (b) ? (a) : (b))
#define ho|nv (a,b) { int tm =a; a= b; b= tm;}
#define error (n) printf ( error %d, n)
Di }y mt s Macro ph}n tch k t, tt c u trong <ctype. h>. C|c macro n{y
tr v tr kh|c 0 nu th{nh cng. i vi mi macro, th{nh cng c nh ngha nh
sau:
Macro K t
isalpha (c) c l{ k t a z, A Z
isupper (c) c l{ k t A Z
islower (c) c l{ k t a z

P
a
g
e
4
8

isdigit (c) c l{ k s 0 9
isxdigit (c) 0 9, A F, a z
iscntrl(c) c l{ k t xa hoc k t iu khin (0x7F
hoc 0x00 n 0x1F)
ispace (c) c l{ k t space, tab, carriage return, new
line (0x09 n 0x0D, 0x20)
Khai bo: char c;
* Ph}n bit Macro vi h{m:
- Dng Macro: truy xut nhanh, tn b nh.
- Dng h{m: ngc li
III.1.6.2. #include
L{ tin x l dng kt ni tp trung khai b|o trong include vi tp tin ang l{m
vic.
# include < tn tp tin.h>
# include tn tp tin.h
Dng < > : i tm tp tin.h trong th mc ~ c ch nh trong Include
Directories.
Dng : tm tp tin.h trong th mc Source Directories, nu khng c, n i tm
trong th mc ~ c ch nh trong Include Directories.
III.2. qui (Recursion):
III.2.1. Khi nim: qui l{ 1 cng c rt thng dng trong khoa hc m|y tnh
v{ trong to|n hc gii quyt c|c vn . Trc ht, chng ta h~y kho s|t th n{o l{
mt vn c qui qua v d sau:
Tnh S(n) = 1 +2 +3 +4+ ...+n
Ta nhn thy rng, cng thc trn c th din t li nh sau:
S(n) = S(n-1) + n, v
S(n-1) = S(n-2) + (n-1)
.....
S(2) = S(1) + 2
S(1) = 1
Nh vy, mt vn c qui l vn c nh ngha li bng chnh n.
tnh S(n): ta c kt qu ca S(1), thay n v{o S(2), c S(2) ta thay n v{o S(3) ....,
c nh vy c S(n-1) ta s tnh c S(n)
*Mt s v d
1. H{m giai tha:
n! = { 1*2*3*......*(n-1)*n , n>0
1 , n=0
= { n*(n-1)! , n>0
1 , n=0

P
a
g
e
4
9


P
a
g
e
5
0

Nhn xt:
- Theo cng thc trn, ta nhn thy trong nh ngha ca n giai tha (n!) c nh
ngha li chnh n nn h{m giai tha c qui.
- Vi n >=0 , iu kin dng tnh h{m giai tha l{ n=1
2. Hm FIBONACCI:

Fn =
1 ; n =0,1
Fn-1 + Fn-2 ; n>1
- Theo nh ngha trn, h{m Fibonacci c li gi qui.
- Qu| trnh tnh dng li khi n= 1
III.2.2. Hm qui trong ngn ng C:
Ngn ng C c trang b c ch gi h{m qui. H{m qui l{ h{m gi n chnh
h{m mt c|ch trc tip hay gi|n tip.
V d 1: Vit h{m qui tnh S(n) = 1 + 2 + 3 +...+n
#include <stdio.h>
#include <conio.h>
int S(int n)
{ if (n==1) // iu kin dng
return 1;
else // bc qui
return (S(n-1) + n);
}
void main()
{ int n;
printf("\n Nhap n = ");
scanf("%d",&n);
printf("Tong S = 1 + 2 + ...+ %d = %d",n, S(n));
getch();
}
V d 2 : Vit h{m qui tnh h{m giai tha n.
long giaithua(int n)
{ return ((n==0) ? 1 : n*giaithua(n-1));
}
III.2.3. Hm qui v Stack:
Mt chng trnh C thng gm c h{m main() v{ c|c h{m kh|c. Khi chy chng
trnh C th h{m main() s c gi chy trc, sau h{m main() gi c|c h{m kh|c, c|c
hm ny trong khi chy c th gi c|c h{m kh|c na. Khi mt h{m c gi, th mt
khung kch hot ca n c to ra trong b nh stack. Khung kch hot n{y cha c|c
bin cc b ca h{m v{ mu tin hot ng ca h{m. Mu tin hot ng cha a ch tr
v ca h{m gi n v{ c|c tham s kh|c.

Bin cc b

P
a
g
e
5
1

Mu tin
hot ng
a ch tr v
Thng s kh|c
Khung kch hot
Sau khi h{m c gi ~ thi h{nh xong th chng trnh s thc hin tip dng
lnh a ch tr v ca h{m gi n, ng thi xa khung kch hot ca h{m khi b
nh.
Gi s ta c c ch gi h{m trong mt chng trnh C nh sau:
main()
{ ......
A();
.....;
B();
....;
}
A()
{.....;
C();
....;
D();
}
B()
{.....;
D();
}
C()
{......;
D();
.....;
}
D()
{........;
........;
}
Hnh sau }y cho ta thy s chim dng b nh stack khi chy chng trnh C nh
m t trn.
b nh
Stack
D
C C C D D
A A A A A A A B B B
M M M M M M M M M M M M M
thi gian
Tng t vi trng hp h{m qui, khi gi qui ln nhau th mt lot c|c
khung kch hot s c to ra v{ np v{o b nh Stack. Cp qui c{ng cao th s
khung kch hot trong Stack c{ng nhiu, do , c kh nng dn n tr{n Stack (Stack
overflow). Trong nhiu trng hp khi lp trnh, nu c th c ta nn g qui cho
cc bi ton.
IV. STRUCTURE:
C|c kiu n gin ti mt thi im ch lu gi c mt gi| tr duy nht. Cn mt
bin kiu mng dng lu tr c|c gi| tr cng kiu d liu vi nhau, chng hn nh
mt d~y s, mt d~y c|c k t,...Nhng trong thc t, iu n{y vn cha v c|c th{nh
phn m{ ta lu gi thng l{ kh|c kiu d liu vi nhau.
V d : Ta mun lu gi c|c thng tin v mt sinh vin nh sau : MASO, HO, TEN,
NGAYSINH, NOISINH, PHAI, DIACHI, LOP . Vi c|c th{nh phn nh vy, th r r{ng c|c
th{nh phn ca 1 sinh vin khng th cng kiu m{ phi thuc c|c kiu kh|c nhau, c th
l:
- MASO, HO, TEN : mng ch

P
a
g
e
5
2

- NGAYSINH : int ng{y , th|ng , nm ;
- NOISINH : mng ch
- PHAI : unsigned int;
- LOP : mng ch;
Do , lu tr c c|c th{nh phn kh|c nhau ca mt i tng ta phi s
dng mt kiu d liu trong C l{ Structure. (tng t nh record trong Pascal)
IV.1. nh ngha:
Mt bin c kiu structure c dng lu tr mt i tng c nhiu th{nh
phn. C|c th{nh phn c th thuc c|c kiu d liu kh|c nhau.
IV.2. Khai bo: Mun khai b|o kiu hocvien dng lu tr h, tn, im mn
TOAN,LY,HOA, TB, Xp loi ca mt hc vin, ta c :
typedef struct hocvien
{ char ho[30];
char ten[7];
float toan, ly, hoa , dtb;
char xeploai[10];
} ;
- khai b|o bin hv c kiu hocvien :
hocvien hv;
- truy xut ti mt th{nh phn, ta dng du chm, v d nh: hv->ho truy
xut ti h ca hc vin.
* Khai b|o kt hp: va khai b|o kiu structure va khai b|o bin c kiu .
struct hocvien
{ char ho[30];
char ten[7];
float toan, ly, hoa , dtb;
char xeploai[10];
} hv1, hv2; // khai b|o 2 bin hv1, hv2 cng kiu hocvien
- Khai b|o structure lng nhau:
V d:
void main()
{ struct ngaysinh
{ unsigned int ngay, thang, nam;
};
struct hocvien
{ char ho[30];
char ten[7];
struct ngaysinh ngsinh;
float toan, ly, hoa, dtb;
char xeploai[10];

P
a
g
e
5
3

} ;
struct hocvien hv;
}
Trong trng hp n{y, truy xut ti th|ng sinh ca hc vin hv, ta vit nh sau:
hv.ngsinh.thang.
V. FILE:
V.1. File vn bn:
- File vn bn l{ file c lu tr di dng kiu k t
C 2 c|ch truy xut theo kiu k t.
- Truy xut theo tng k t
- Truy xut theo tng dng
V.1.1. Khai bo tp tin:
Khai b|o bin kiu file:
FILE *fptr;
V.1.2. M tp tin:
fptr = fopen (tn file, kiu);
- Trong "tnfile" , ta c th ch nh mt ng dn y nh sau
"C:\THU\KTLT\VIDU.TXT". H{m fopen nu m file th{nh cng s tr v mt con tr file
cho tp tin "tn file", v{ con tr n{y c ct gi trong bin fptr (bin kiu FILE).
Nu khng c file "tn file" trn da th h{m fopen s tr v tr NULL
( nu fptr == NULL ngha l{ khng c file )
- Kiu: gm c:
r : c ( file phi c sn, nu khng c file, h{m fopen tr v tr NULL)
w : ghi ( nu c file s xa file c )
a : ni v{o cui tp tin
r +: c / ghi, tp tin phi c sn trn da
a+: c, ghi v{o cui tp tin, nu trn da cha c tp tin th n s c to ra.
V d: m s k t trong file VB.TXT.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ FILE *fptr;
int dem=0;
char ch;
if ((fptr = fopen("VB.txt", "r")) == NULL) // m file c
{
printf("File nay khong the mo\n");
return ; // kt thc chng trnh, hm exit thuc v stdlib.h

P
a
g
e
5
4

}
while (!feof(fptr))
{ ch=fgetc(fptr); // c 1 k t trong file fptr ra
dem++;
}
fclose(fptr);
printf("\nSo ky tu trong file VB.TXT =%d",dem);
getch();
}
V.1.3. ng file:
fclose (fptr)
V.1.4. c / ghi k t: Cho bin k t char ch;
- c k t t tp tin
ch = getc (fptr)
- Ghi k t ln tp tin
putc (ch, fptr)
V d 1: To 1 file trc tip t b{n phm. Qu| trnh to s dng li khi ta n phm
Enter.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ FILE *fptr;
char tenfile[67];
char ch;
clrscr();
printf("Cho biet ten file :");
gets(tenfile);
if ((fptr=fopen(tenfile,"w"))==NULL) // m file mi ghi
{ printf("Viec tao file co loi\n");
exit(0);
}
while ((ch=getche()) !='\r')
putc(ch,fptr);
fclose(fptr);
}
V d 2: In ni dung tp tin ra mn hnh
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

P
a
g
e
5
5

void main()
{ FILE *fptr;
char tenfile[67];
char ch;
clrscr();
gets(tenfile);
if ((fptr=fopen(tenfile,"r"))==NULL)
{ printf("Viec mo file co loi\n");
exit(0);
}
while ((ch=getc(fptr)) !=EOF)
printf("%c",ch);
fclose(fptr);
}

P
a
g
e
5
6

V d 3: Chng trnh m s t trong file
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ FILE *fptr;
char tenfile[67];
int ch;
int dem=0, tu=0;
clrscr();
gets(tenfile);
if ((fptr=fopen(tenfile,"r"))==NULL) // m file c
{ printf("Viec mo file co loi\n");
exit(0);
}
while ((ch=getc(fptr)) !=EOF)
{ if ((ch>='a' && ch <='z') || (ch>='A' && ch<='Z'))
tu=1;
if ((ch==' ' || ch=='\n' || ch=='\t') && tu)
{ dem++;
tu=0;
}
}
printf("So tu trong file =%d",dem);
fclose(fptr);
}
V.1.5. c / ghi chui k t:
* Hm fgets (chui, chiud{i, fptr);
H{m fgets c 1 chui k t t trong file fptr v{o bin <chui> vi chiu d{i ti a l{
<chiud{i>. H{m n{y tr v NULL khi ~ c ht file
* Hm fputs (chui, fptr): ghi 1 chui k t trong <chui> v{o file fptr. H{m n{y
khng t ng thm v{o m~ kt thc chuyn dng mi, do ta phi ghi thm m~ n{y
v{o tp tin bng lnh fputs ("\n", fptr);
V d 1: Chng trnh ghi chui ln file, cho n khi chui nhp v{o l{ rng th kt
thc.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
void main()

P
a
g
e
5
7

{ FILE *fptr;
char tenfile[67];
char chuoi[80];
clrscr();
gets(tenfile);
if ((fptr=fopen(tenfile,"w"))==NULL) // to file mi
exit(0);
}
while (strlen(gets(chuoi)) > 0) // hm strlen() trong <string.h>
{ fputs(chuoi,fptr);
fputs("\n",fptr);
}
fclose(fptr);
}
V d 2: c c|c chui k t t tp tin, v{ in n trn m{n hnh.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{ FILE *fptr;
char tenfile[67];
char chuoi[81];
clrscr();
gets(tenfile);
if ((fptr=fopen(tenfile,"r"))==NULL)
exit(0);
}
while (fgets(chuoi,80,fptr)!= NULL)
printf("%s",chuoi);
fclose(fptr); getch();
}
V.1.6. Xa file: Lnh remove xo| file c ch nh qua <tnfile>
C php: remove (tn file)
Hm remove tr v 0 : xa th{nh cng
tr v -1 : c li khi xa file, v{ lc n{y bin errno c 1 trong 2 gi
tr sau:
ENOENT : khng tm thy file mun xa
EACCES : khng cho php xa file m{ bn ch nh
Lu : File nn ng trc khi xa.

P
a
g
e
5
8

V d: Xa file do ta ch nh.
#include <stdio.h>
void main()
{ char filename[80];
/* prompt for file name to delete */
printf("File muon xoa: ");
gets(filename);
/* delete the file */
if (remove(filename) == 0)
printf("Removed %s.\n",filename);
else
perror("remove"); // in thng b|o li m{ h{m remove g}y ra
}
V.2. File nh phn (file c cu trc)
File nh ph}n l{ file dng lu tr c|c cu trc di dng struct hoc union
V.2.1. Khai bo:
FILE * fptr;
V.2.2. M file:
fptr = fopen (tnfile, kiu);
. rb ( b: binary): m ch c
. wb : ghi. Nu file ~ c th xa trc khi m.
. ab : ni thm; m ghi thm v{o cui file, nu file cha c th to
mi
. rb+ : m file ~ c cp nht (c/ghi)
. wb+ : to file mi cho php c/ghi
. ab+ : m ni thm v cui file, cho php c/ghi
V.2.3. ng file:
fclose (fptr)
V.2.4. c/ghi file: Hm fread : c s mu tin(cu trc) trong file fptr v{o <bin
cu trc>.
fread (& bin cu trc, sizeof (bin cu trc) , s cu trc, fptr);
H{m fread tr v s cu trc c c
Hm fwrite ghi d liu trong <bin cu trc> v{o file fptr.
int fwrite (&bin cu trc, sizeof (bin cu trc) , s cu trc, fptr);
Hm fwrite tr v s cu trc ghi c ln file
Ch :
- kim tra vic c file ta kim tra s cu trc c c. Nu s cu trc tr v
bng 0 m{ ta cn c l{ 1 cu trc th iu chng t ~ ht file.
* Ghi mt mng cu trc ln file
fwrite(tnmng, sizeof (tnmng), 1, fptr);

P
a
g
e
5
9

for (i= 0; i< n; i++)
fwrite (&tnmng[i], sizeof (tnmng[i]) , 1, fptr);
V d 1: Chng trnh ghi ln file nh ph}n
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main()
{ struct hocvien
{ char hoten[30];
int tuoi;
} hv;
FILE *fptr;
char tenfile[67];
char tuoi[3];
printf("Nhap ten file :");
gets(tenfile);
if ((fptr=fopen(tenfile,"wb")) == NULL) // m file nh ph}n ghi
{ printf ("Khong the tao file\n"); exit(0);
}

do
{ printf("Nhap ho ten hoc vien :");
gets(hv.hoten);
if (strlen(hv.hoten) !=0)
{ printf("Nhap tuoi :");
gets(tuoi);
hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen
fwrite(&hv, sizeof(hv), 1, fptr) ; // ghi noi dung 1 mau tin trong bien hv
// vao file fptr
}
}
while (strlen(hv.hoten)!=0);
fclose (fptr);
}
V d 2: Ghi d liu mng v{o file nh ph}n
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main()
{ struct hocvien

P
a
g
e
6
0

{ char hoten[30];
int tuoi;
} hv;
struct hocvien table[3];
FILE *fptr;
char tenfile[67];
char tuoi[3];
int i=0;
gets(tenfile);
if ((fptr=fopen(tenfile,"wb")) == NULL)
{ printf ("Khong the tao file\n"); exit(0);
}
do
{ printf("Nhap ho ten hoc vien :");
gets(hv.hoten);
printf("Nhap tuoi :");
gets(tuoi);
hv.tuoi = atoi(tuoi); // macro doi chuoi qua so nguyen
table[i++]=hv;
}
while (i<3);
fwrite(table, sizeof(table), 1, fptr) ; // ghi noi dung toan bo hoc vien trong
// table vao file fptr
// hoc for (i=0; i<3; i++)
// fwrite(&table[i], sizeof(table[i]), 1, fptr)
fclose (fptr);
}
V d 3: Chng trnh c file nh ph}n, v{ in danh s|ch hc vin ra m{n hnh.
// In danh s|ch hc vin ra m{n hnh
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main()
{ struct hocvien
{ char hoten[30];
int tuoi;
} hv;
FILE *fptr;
char tenfile[67];
char tuoi[3];

P
a
g
e
6
1

gets(tenfile);
if ((fptr=fopen(tenfile,"rb")) == NULL) // M file c
{ printf ("Khong the mo file\n"); exit(0);
}
clrscr();
printf(" Ho va ten Tuoi");
while (fread(&hv,sizeof(hv),1,fptr) ==1)
{
printf("\n%-20s",hv.hoten);
printf("%3d",hv.tuoi);
}
fclose (fptr);
}
V.2.5. Truy xut tp tin ngu nhin: (iu khin con tr tp tin trn file nh
phn)
* Con tr file: Mi tp tin u c con tr file sau khi c m. Con tr file l{ con tr
ch n tng byte trn file. Khi c hay ghi d liu trn tp tin, ta ~ l{m dch chuyn con
tr file mt s byte, }y chnh l{ s byte m{ kiu d liu ~ chim. Khi ng ri m tp
tin, con tr file lun u tp tin ; ngoi tr trng hp ta m bng ty chn 'a' th con
tr file s cui tp tin ghi thm d liu v{o cui tp tin. H{m fseek cho php ta di
chuyn con tr file n v tr mong mun.
C php:
int fseek (FILE * fptr, long nbytes, kiu)
+ nbytes : s bytes tnh t v tr kiu cho n v tr cn ti
+ kiu l{ s nguyn :
kiu = 0 (tnh t u tp tin)
kiu = 1 (tnh t v tr hin ti)
kiu = 2 (tnh t cui tp tin)
Nu fseek tr v 0 ngha l{ n ~ di chuyn ti v tr .
Lu : s th t trn tp tin tnh t 0.
V d: Vit chng trnh truy xut ngu nhin mt mu tin theo s th t ca n
trong file nh ph}n
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main()
{ struct hocvien
{ char hoten[30];
int tuoi;

P
a
g
e
6
2

} hv;
FILE *fptr;
char tenfile[67];
int stt, sobytes;

gets(tenfile);
if ((fptr=fopen(tenfile,"rb")) == NULL)
{ printf ("Khong the mo file\n"); exit(0);
}
clrscr();
printf("Cho biet so thu tu mau tin can di chuyen den :");
scanf("%d",&stt);
sobytes = stt * sizeof(hv);
if (fseek(fptr,sobytes,0)!=0)
{ printf ("Khong the di chuyen con tro file toi vi tri ban chi dinh duoc");
exit(0);
}
fread(&hv,sizeof(hv),1,fptr) ;
printf("\n%-20s",hv.hoten);
printf("%3d",hv.tuoi);
fclose (fptr);
getch();
}
V.3. Pht hin li khi truy xut tp tin
Phn ln nhng h{m xut, nhp tp tin chun khng thng b|o r ni dung ca li.
Chng hn nh:
- putc () s tr v EOF khi c li hoc cui tp tin
- fgets () s tr v l{ NULL khi c ht file hoc khi c li
Do , ph|t hin li khi truy xut tp tin, ta dng macro ferror (FILE *fptr)
int ferror (file * ptr)
Macro ferror tr v mt tr kh|c 0 nu ph|t hin ra li trn file fptr.
* xut c}u thng b|o li ta dng h{m perror ()
void perror (const char * str)
vi str : chui k t cha c}u thng b|o
* Hai h{m n{y thng c s dng ngay sau khi s dng c|c h{m c / ghi file
V d: fwrite (&table, sizeof (table), 1, fptr);
if (ferror (fptr) != 0)
{ perror (Loi ghi du lieu);

P
a
g
e
6
3

exit (0);
}
V d :
#include <stdio.h>
void main()
{
FILE *fp;
fp = fopen("perror.dat", "r");
if (!fp)
perror("Khng th m file c");
}
Khi chy chng trnh n{y, nu trn da cha c tp tin perror.dat th s hin thng b|o
li: Khng th m file c: No such file or directory.
Bi tp
1. To tp tin din tch.h
#define Pi 3.14
#define dthv (x) x*x
#define dtht (x) (Pi*x*x)
2. Vit chng trnh tnh din tch da v{o file dientich.h trn
3. Vit h{m qui tnh tch P(n) = 1 * 2 * 3* ....* n , n>0
4. Vit h{m qui tnh h{m m x
n
, vi n nguyn.
5. Vit h{m qui tnh phn t th n ca h{m Fibonacci.
6. Vit h{m qui gii quyt b{i to|n Th|p H{ ni.
C 3 ct A, B, C. Ct A hin ang c n da kch thc kh|c nhau, da nh trn da ln
di. H~y di n da t ct A sang ct C (xem ct B l{ ct trung gian) vi iu kin
mi ln ch c di 1 da v{ da t trn bao gi cng nh hn da t di.
7. Vit chng trnh m~ ha v{ gii m~ mt file vn bn sao cho nu ta ~ m~ ha ri th
chng trnh khng m~ ha na, v{ nu file cha m~ ha th khng c gii m~.
8. Cho bit trong mt file vn bn do ta nhp v{o c bao nhiu k t, bao nhiu t, v{
bao nhiu dng; bit rng c|c t c|ch nhau khong trng, du tab, du chm.
9. Vit chng trnh to mt menu thc hin c|c chc nng sau trn file vn bn:
- To file mi
- c file
- Xa file
- Ghi ni ui file
- Copy file
- Di chuyn file t th mc n{y sang th mc kh|c
- Tm mt t xut hin bao nhiu ln trong file (khng ph}n bit ch in, ch
thng)
- Thay th t n{y bng t kh|c

P
a
g
e
6
4

10. To menu thc hin c|c cng vic sau:
- Nhp danh s|ch c kiu hc vin v{o mt file tn 'HOSO.TXT', mi hc vin c c|c
thng tin sau: maso (int), hoten (chui ti a 30 k t), ph|i (NAM/NU), tui (int).
- Lit k danh s|ch hc vin ra m{n hnh theo dng sau:
M~ s H v{ tn Phi Tui
- Truy xut ngu nhin theo th t mu tin
- Tm kim mt ngi trong file theo m~ s
- Cp nht sa i c|c mu tin theo m~ s (Nhp m~ s, sau hiu chnh li hoten,
phai, v{ tui).
- Xa mt ngi trong file theo m~ s.

P
a
g
e
6
5

CHNG 3 CC THUT TON TRN CU TRC D LIU MNG

I. MNG KHNG SP XP V THUT TON TM KIM TRN MNG CHA C TH
T
I.1. Mt s khi nim v mng:
I.1.1. nh ngha:
Mng l{ 1 d~y c|c phn t c cng kiu d liu c sp xp lin tip nhau trong
b nh
0100
0102 1 int
0104 2 Mng n phn t

n-1
B nh
Khai bo:
C php: Khai b|o mng 1 chiu
Kiu_DL Tnmng [kch thc];
Kiu_DL : l{ 1 trong c|c kiu d liu c bn, l{ kiu ca phn t ca mng
Tnmng: l{ tn ca mng c t 1 c|ch hp l
Kch thc: l{ 1 hng nguyn cho bit s phn t ti a ca mng
V d 1: Khai b|o 1 mng s nguyn
int n ;
int M[n] ; SAI
int M[10] ; ng v kch thc mng phi l{ hng khng phi l{ bin
#define max 100
int M[max] ;
V d 2: Khai b|o 1 danh s|ch h tn hc vin ca 1 lp hc
char dshv[50][30]; // dshv c th cha ti a h tn 50 hc vin,
// chiu d{i h tn mi hc vin ti a l{ 30 k t
C php: Khai b|o mng 2 chiu
Kiu_DL Tnmng [kch thc 1][kch thc 2]
Ch : Mt mng trong C, c|c phn t c |nh s t 0 ti n-1
V d: Vi M[10]
th th{nh phn th 1 l{ M[0]
th{nh phn cui cng M[9]
* C khng bt b, khng kim tra xem bin m c vt ra khi gii hn cho php
ca mng cha. Do , chng ta phi kim tra bin m trong chng trnh (phi nh

P
a
g
e
6
6

hn n)
I.1.2. Khi ng tr cho mng:
Ta khi ng c tr cho mng trong 2 trng hp sau:
Mng c khai b|o l{ bin ngo{i (main) ngha l{ bin to{n cc
Mng c khai b|o cc b
V d 1 : int M[3] = {10,11,12}
main()
{
}
V d 2:
main()
{ static int M[ ]={10,22,30};
............
}
Ta c th g|n 1 hng cho c mng nh sau:
memset (M,0,sizeof(int) *3) ; // g|n 0 cho mng M vi M c 3 phn t
T kha static dng khai b|o 1 bin cc b thng trc cho php duy tr gi|
tr ring ca n nhng ln gi h{m sau n{y.
Khi to mng 2 chiu:
int M[2][3]= {{1,2,3},
{0,1,0}};
I.1.3.Truy xut thnh phn ca mng: M[ch s]
Truy xut th{nh phn th 2 ca mng 1 chiu: M[1]
Truy xut th{nh phn th i ca mng 1 chiu: M[i-1]
Truy xut th{nh phn dng 2, ct 3 ca mng 2 chiu M[1][2]
I.1.4. c (nhp) d liu cho mng:
- nhp d liu cho mng ta phi nhp d liu cho tng th{nh phn ca mng.
V d 1:
int n,i;
float M[10];
printf("\nCho biet so phan tu cua mang:")
scanf (%d,&n);
for ( i=0; i< n; i++)
{ printf(a[%d]= ,i+1);
scanf (%f,&M[i]);
}
V d 2: Nhp v{o mng 2 chiu.
int m, n, i, j;
float M[10] [10];
printf("So dong ="); scanf("%d",&n);

P
a
g
e
6
7

printf("So cot ="); scanf("%d",&m);
for(i= 0; i< n; i++)
for(j= 0; j<m; j++)
{ printf(M[%d] [%d] = ,i,j);
scanf(%f, &M[i][j]);
}
I.1.5. Xut d liu kiu mng: xut d liu mng ta cng phi xut d liu ca
tng th{nh phn mng
V d:
int i, n;
float M[10];
for(i = 0; i< n; i++)
printf(a[%d] = %f,i+1, M[i]);
I.2. Thut ton tm kim trn mng cha c th t:
Do mng cha c th t nn ta |p dng phng ph|p tm kim tuyn tnh tm t u
mng cho n cui mng. Trong chng trnh sau }y, h{m Timkim s tr v tr -1 nu
khng c m~ sinh vin trong danh s|ch ds, ngc li h{m s tr v v tr ca m~ s
trong danh sch ds.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SOSV 100 // s sinh vin ti a trong danh s|ch
typedef struct sinhvien // nh ngha kiu sinhvien
{ char maso[6];
char hoten[30];
};

typedef struct danhsach_sv // nh ngha kiu danhsach_sv
{ int tssv;
sinhvien sv[MAX_SOSV];
} ;

void Nhap_ds (struct danhsach_sv *psv)
{ char sosv[4];
printf("So sinh vien muon nhap :");
gets(sosv);
psv->tssv=atoi(sosv);
for (int i=0; i<psv->tssv; i++)
{ printf("Ma so :");

P
a
g
e
6
8

gets(psv->sv[i].maso);
printf("Ho ten :");
gets(psv->sv[i].hoten);
}
}

void Lietke_ds (struct danhsach_sv *psv)
{ int i=0;
clrscr();
printf (" Ma so Ho & ten \n");
while (i < psv->tssv)
{ printf ("%8s %-s\n", psv->sv[i].maso,psv->sv[i].hoten);
i++;
}
getch();
}
/* Hm Timkiem tm maso trong danhsach *psv */
int Timkiem(danhsach_sv *psv, char maso[])
{ int i=0;
while ((i<psv->tssv) && (strcmp(psv->sv[i].maso, maso)!=0))
i++;
return (i==psv->tssv ? -1 : i) ;
}
void main()
{ struct danhsach_sv ds;
char maso[6];
int vitri;
Nhap_ds(&ds); // Gi h{m Nhap_ds vi tham s l{ ds
Lietke_ds(&ds);
printf("Ma so sinh vien ban can tim :");
gets(maso);
vitri = Timkiem(&ds, maso);
if (vitri !=-1)
printf("Ho ten cua sinh vien la %s",ds.sv[vitri].hoten);
else printf(" Khong co sinh vien voi ma ban nhap vao");
getch();
}
II. CC THUT TON SP XP:
Trong thc t cuc sng cng nh trong lnh vc lp trnh, vic qun l d liu
thng i hi s tm kim c|c d liu cn thit; thun tin cho vic tm kim, d liu

P
a
g
e
6
9

thng c sp xp theo mt th t n{o .
C rt nhiu phng ph|p sp th t, trong b{i ging n{y ta ch kho s|t hai phng
ph|p sp xp l{ Bubble_Sort v{ Quick_Sort.
thun tin ta gi s mng l{ d~y s c ti a 100 s, v{ c|c thut to|n di }y
dng sp xp d~y s theo th t tng dn.
II.1. Sp xp theo phng php Bubble_Sort (phng ph|p ni bt)
- Ni dung : Ta cho i duyt d~y a[0], .. ,a[n-1]; nu a[i-1] ln hn a[i] th ta ho|n i
(a[i-1],a[i]). Lp li qu| trnh duyt d~y n{y cho n khi khng c xy ra vic i ch ca
hai phn t.
V d: Ta sp th t d~y s sau : 26 33 35 29 19 12 32
Bc 0 1 2 3 4 5 6
26 12 12 12 12 12 12
33 26 19 19 19 19 19
35 33 26 26 26 26 26
29 35 33 29 29 29 29
19 29 35 33 32 32 32
12 19 29 35 33 33 33
32 32 32 32 35 35 35
- Chng trnh:
#include <stdio.h>
#include <conio.h>
int mang[100]; // bin to{n cc
int size ;
void Bubble_Sort(int A[100], int n)
{ int i,j,temp;
for (i=1; i<n; i++)
for (j=n-1;j>=i; j--)
if (A[j-1] > A[j])
{ temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;
}
}
int Nhap_day_so (int A[])
{ int i,n;
printf("\nSo phan tu cua mang :"); scanf("%d",&n);
for (i=0; i<n; i++)
{ printf ("A[%d] = ",i+1);
scanf("%d",&A[i]);
}

P
a
g
e
7
0

return n;
}
void Liet_ke (int A[], int n)
{ int i;
printf("\n Gia tri mang da duoc sap : \n");
for (i=0; i<n; i++)
printf ("%5d",A[i]);
getch();
}

void main()
{
size= Nhap_day_so(mang);
Bubble_Sort(mang,size);
Liet_ke(mang,size);
}
Ta nhn thy phng ph|p n{y c th c ci tin d d{ng. Nu ln duyt d~y
n{o m{ khng c c s i ch gia hai phn t th d~y ~ c th t v{ gii thut kt
thc. Trong trng hp n{y, ta dng mt c hiu flag ghi nhn iu n{y, v{ gii thut
Bubble Sort c ci tin nh sau:
#define FALSE 0
#define TRUE 1

void Bubble_Sort_Ad(int A[], int n)
{ int i,temp;
unsigned char flag=TRUE;
while (flag)
{ flag = FALSE ;
for (i=0; i<n-1; i++)
if (A[i] > A[i+1])
{ temp = A[i];
A[i] = A[i+1];
A[i+1] = temp;
flag=TRUE;
}
}
}
II.2. Sp xp theo phng php Quick_Sort
II.2.1. Ni dung: Chn mt phn t bt k trong danh s|ch l{m im cht x, so
s|nh v{ i ch nhng phn t trong danh s|ch n{y to ra 3 phn: phn c gi| tr nh
hn x, phn c gi| tr bng x, v{ phn c gi| tr ln hn x. Li tip tc chia 2 phn c gi|

P
a
g
e
7
1

tr nh hn v{ ln hn x theo nguyn tc nh trn; qu| trnh chia phn s kt thc khi
mi phn ch cn li mt phn t, lc n{y ta ~ c mt danh s|ch c th t.
V d: Xt dy 26 33 35 29 19 12 32
Ln chia phn th nht : Chn phn t cht c kha l{ 29, t l{ x
26 33 35 29 19 12 32
i j
Dng hai bin ch s i v{ j duyt t hai u danh s|ch n x. Nu i gp phn t
ln hn hay bng x s dng li, j gp phn t nh hn hay bng x s dng li, ri i ch
hai phn t n{y; sau tip tc duyt cho n khi i>j th ngng li.
Lc n{y d~y s c 3 phn kh|c nhau nh hnh v sau :
26 33 35 29 19 12 32
i j
26 12 35 29 19 33 32
i j
26 12 19 29 35 33 32
ij
26 12 19 29 35 33 32
j i
Ln chia phn th hai cho d~y con 26 12 19, chn cht x=12
26 12 19 12 26 19
i j j i
Kt thc ta s c hai phn : 12 ; 26 19
Ln chia phn th 3 cho d~y con 26 19, chn cht x=26
26 19 19 26 Kt thc qu| trnh chia nh d~y con 26 12 19
i j j i
- Ln chia phn th 4 cho d~y con 35 33 32, chn cht x= 33
35 33 32 32 33 35 32 33 35
i j ij j i
Kt thc ta s c ba phn : 32 ; 33 ; 35
n }y qu| trnh chia phn kt thc v tt c c|c phn ch c mt phn t, lc n{y
ta s c mt danh s|ch c th t l{ :
12 19 26 29 32 33 35
II.2.2. Gii thut:
a. Gii thut khng quy:
- Ta to mt Stack , mi phn t ca Stack c 2 th{nh phn l{ q, r cha ch s u
v{ ch s cui ca d~y cn sp. Ban u, Stack[0].q = 0 v{ Stack[0].r =n-1
- Tin h{nh ph}n hoch d~y s gm c|c s bt u t ch s q n ch s r
- Sau mi ln chia phn, ta kim tra xem phn c gi| tr nh hn cht v{ phn c
gi| tr ln hn cht nu c t 2 phn t tr ln th a v{o Stack. Sau mi ln ph}n
hoch, ta li ly d~y s mi t Stack ra ph}n hoch tip.

P
a
g
e
7
2

- Qu| trnh c nh th cho ti khi Stack rng th kt thc.
* Chng trnh:
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
int mang[100];
int size ;
void Quick_Sort(int A[100], int n)
{ struct Element_Stack // kiu phn t trong Stack
{
int q, r;
} ;
Element_Stack Stack[50]; // Stack c ti a 50 phn t
int sp=0; // con tr Stack, khi to sp=0
int i,j,x,q,r,temp;
Stack[0].q =0 ; // ch s u ca mng cn sp
Stack[0].r =n-1; // ch s cui ca mng cn sp

do
{ // Ly mt ph}n hoch ra t Stack
q = Stack[sp].q ; r =Stack[sp].r ;
sp--; // Xa 1 phn t khi Stack
do
{ // Ph}n on d~y con a[q] ,..., a[r]
i = q; j =r;
x = A[(q+r) / 2] ; // Ly phn t gia ca d~y cn sp th t l{m cht
do
{ while (A[i] < x) i++; //Tm phn t u tin c tr ln hn hay bng x
while (A[j] > x) j--; //Tm phn t u tin c tr nh hn hay bng x
if (i<=j) // i ch A[i] vi A[j]
{ temp = A[i];
A[i] =A[j];
A[j] = temp;
i++ ; j--;
}
} while (i<=j);

if (i<r) // phn th ba c t 2 phn t tr ln
{ // a v{o Stack ch s u v{ ch s cui ca phn th ba
sp++;

P
a
g
e
7
3

Stack[sp].q=i;
Stack[sp].r=r;
}
r = j ; // Chun b v tr ph}n hoch phn c gi| tr nh hn cht
} while (q< r);
} while (sp!=-1); // Ket thuc khi Stack rong
}

int Nhap_day_so (int A[])
/* To d~y n s ngu nhin t 0 n 9999 a v{o mng A */
{ int i,n;
printf("\nSo phan tu cua mang :"); scanf("%d",&n);
randomize(); // dng <time.h> v <stdlib.h>
for (i=0; i<n; i++)
A[i]= rand() % 10000; // Ph|t sinh c|c s ngu nhin t 0 n 9999
return n;
}

void Liet_ke (char str[],int A[], int n)
{ int i;
printf("\n%s\n",str);
for (i=0; i<n; i++)
printf ("%5d",A[i]);
getch();
}

void main()
{
Liet_ke("Day so ngau nhien :",mang,size);
Quick_Sort(mang,size);
Liet_ke("Gia tri mang da duoc sap :",mang,size);
}
b. Gii thut Quick Sort qui: v c ch thc hin th cng ging nh gii thut
khng qui, nhng ta khng kim so|t Stack m{ cho qu| trnh gi qui t to ra
Stack.
* Chng trnh:
void Sort(int A[], int q,int r)
{ int temp;
int i=q;
int j=r;

P
a
g
e
7
4

int x = A[(q+r) / 2] ; // Ly phn t gia ca d~y cn sp th t l{m cht
do
{ // Ph}n on d~y con a[q] ,..., a[r]
while (A[i] < x) i++; //Tm phn t u tin c tr ln hn hay bng x
while (A[j] > x) j--; //Tm phn t u tin c tr nh hn hay bng x
if (i<=j) // Doi cho A[i] voi A[j]
{ temp = A[i];
A[i] =A[j];
A[j] = temp;
i++ ; j--;
}
} while (i<=j);
if (q<j) // phn th nht c t 2 phn t tr ln
Sort(A,q,j);
if (i<r) // phn th ba c t 2 phn t tr ln
Sort (A,i,r);
}
void Quick_Sort(int A[], int n)
{ Sort( A,0,n-1); // Gi h{m Sort vi phn t u c ch s 0 n //
phn t cui cng c ch s n-1
}
III. TM KIM TRN MNG C TH T:
Gi s d~y s ca ta l{ d~y s ~ c th t tng dn, v{ x l{ gi| tr cn tm. C|c h{m
tm kim s tr v tr -1 nu khng c x trong d~y, ngc li c|c h{m tm kim s tr v
ch s ca x trong d~y.
III.1. Tm kim nhanh bng phng php lp:
- Ni dung: Do d~y s ~ c th t tng dn, nn nu ta tm c phn t u tin
c tr va ln hn x th ta c th kt lun d~y s khng cha tr x. V vy, ta s rt ngn
thi gian tm kim.
- Gii thut:

int Search(int A[], int n, int x)
{ int i=0;
while (i<n && A[i] < x)
i++;
return (i<n && A[i]==x ? i : -1) ;
}
void main()
{ int so,vitri;

P
a
g
e
7
5

Quick_Sort(mang,size);
Liet_ke("Gia tri mang da duoc sap :",mang,size);
printf("\nGia tri muon tim :");
scanf("%d",&so);
vitri = Search(mang,size, so);
if (vitri !=-1)
printf("Vi tri cua so %d trong day = %d",so,vitri);
else printf(" Khong co so %d trong day",so);
getch();
}
III.2. Php tm kim nh phn:
- Ni dung:
Bc 1: Phm vi tm kim ban u l{ to{n b danh s|ch.
Bc 2: Ly phn t chnh gia ca phm vi tm kim (gi l{ y) so s|nh vi x.
Nu x=y th ta ~ tm thy, tr v ch s. Gii thut kt thc
Nu x < y th phm vi tm kim mi l{ c|c phn t nm pha trc ca
y.
Nu x > y th phm vi tm kim mi l{ c|c phn t nm pha sau ca y.
Bc 3: Nu cn tn ti phm vi tm kim th lp li bc 2, ngc li gii thut
kt thc vi kt qu l{ khng c x trong d~y s.
- Gii thut:
int Binary_Search(int A[], int n, int x)
{ unsigned char found=FALSE; // Gi s ban u ta cha tm thy x trong d~y
// Phm vi ban u tm kim l{ t k=0 m = n-1
int k=0;
int m=n-1;
int j;
while (k<=m && !found)
{ j=(k+m) /2; //ch s phn t gia
if (A[j]==x)
found=TRUE;
else if (x>A[j]) k=j+1; // Phm vi tm mi l{ (j+1, m)
else m=j-1; // Phm vi tm mi l{ (k, j-1)
}
return (found ? j : -1) ;
}
III.3. Php tm kim nh phn qui:
- Ni dung: tng t nh trn
Bc 1: Phm vi tm kim ban u l{ to{n b danh s|ch (k=0m=n-1).
Bc 2: Ly phn t chnh gia ca phm vi tm kim (gi l{ y) so s|nh vi x.

P
a
g
e
7
6

Nu x=y th ta ~ tm thy, tr v ch s. Gii thut kt thc
Nu x < y th phm vi tm kim mi l{ c|c phn t nm pha trc ca
y, nn ta gi qui vi phm vi mi l{ (k,j-1)
Nu x > y th phm vi tm kim mi l{ c|c phn t nm pha sau ca y, nn ta
gi qui vi phm vi mi l{ (j+1,m )
iu kin dng: x=y hoc k > m.
- Gii thut:
int Binary_Search2(int A[], int k,int m, int x)
{ int j=(k+m) /2;
if (k>m) return -1 ;
else if (A[j]==x) return j ;
else Binary_Search2(A, (A[j]<x ? j+1:k), (A[j] > x ?j-1:m),x);
}

P
a
g
e
7
7

B{i tp:
1. Cho mt d~y n s thc A :
a) Tm phn t nh nht ca d~y s A
b) Tm phn t ln nht ca d~y s A
c) Tnh gi| tr trung bnh ca d~y s A.
2. Hin ang lu h{nh c|c t giy bc 50000, 20000, 10000, 5000, 2000, 1000,
500, 200, 100. Nu c x ng, hi rng nn chn c|c t giy bc n{o s lng c|c t
giy bc l{ t nht.
3. Vit chng trnh nhp mt ma trn s nguyn c kch thc M x N. In ra:
- Tng c|c phn t ca ma trn
- S c|c phn t dng, phn t }m, phn t 0 ca ma trn
- Phn t ln nht, nh nht ca ma trn
- C|c phn t trn ng cho chnh ca ma trn (vi M = N )
- Tng c|c phn t trn ng cho chnh ca ma trn (vi M = N )
4. Cho 2 ma trn vung A(n,n) v{ B (n,n) :
- Tnh ma trn tng C = A+ B,
bit C[i,j] = A[i,j] + B[i,j] , i,j e[1,m]
- Tnh ma trn tch D = A * B,
bit D [i,j] = A i k B k j
k
n
[ , ]* [ , ]
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

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.

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.

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

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 = &num;
*p2 = (float ) *p1; // * p2 = 5.0
V d: int num, *p, n;
char c;
p = &num;
*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:

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;

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]

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;

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);
}

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 ;
}
char *strcat (char *s1, const char *s2)
{ char *p;
p=s1;
while ( *s1!='\0' )
s1 ++;
while ( (*s1=*s2) !='\0' )
{ s1 ++; s2 ++;

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] ;
}
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

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;

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.


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


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()
{

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;
}
}

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

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

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;
}
}


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).

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.


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

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

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

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

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

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)
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.
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

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;

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
}

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

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

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 :

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);
}
}
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

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

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

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

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

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.

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)

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

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;
}

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;

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);
}

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)
{
Preorder(root->left);
Preorder (root->right);
}
}
b. Duyt cy theo th t LNR (Inorder):
void Inorder(NODEPTR root)
{
if(root != NULL)
{
Inorder(root->left);
Inorder(root->right);

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);
}
}

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{: + -
* / ^ % !


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

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

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

ĐẠI CƯƠNG VỀ LẬP TRÌNH

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ĐẠI CƯƠNG VỀ LẬP TRÌNH

Uploaded by

Copyright:

Available Formats

K THUT LP TRNH NGN NG LP TRNH C

K THUT LP TRNH NGN NG LP TRNH C

K THUT LP TRNH NGN NG LP TRNH C

K THUT LP TRNH NGN NG LP TRNH C

You might also like