Cấu Truúc Dữ Liệu LVH
Ch ng 1ươ
T NG QUAN V C U TRÚC D LI U VÀ GI I THU TỔ Ề Ấ Ữ Ệ Ả Ậ
I-GI I THI U Ớ Ệ :
• Vi c vi t m t ch ng trình đ đi u khi n máy tính th c hi n các công vi c qu n lýệ ế ộ ươ ể ề ể ự ệ ệ ả
c a ng i s d ng, đáp ng các yêu c u tính toán , tìm ki m , th ng kê , l u tr v…ủ ườ ử ụ ứ ầ ế ố ư ữ
v… là m t v n đ không ph i đ n gi n . ộ ấ ề ả ơ ả
• Vi c đ u tiên ng i s d ng ph i d a trên yêu c u th c t , thông qua các thông tinệ ầ ườ ử ụ ả ự ầ ự ế
c a đ i t ng và các nghi p v chuyên môn x lý trong h th ng c n qu n lý, đ đápủ ố ượ ệ ụ ử ệ ố ầ ả ể
ng yêu c u l u tr , tính toán và x lý tìm ki m thông kê v…v…Thông tin c a h th ngứ ầ ư ữ ữ ế ủ ệ ố
s đ c t ch c thành các c u trúc d li u phù h p, các gi i thu t t i u , sau đó v nẽ ượ ổ ứ ấ ữ ệ ợ ả ậ ố ư ậ
d ng các k thu t , k năng đ chuy n hóa các yêu c u trên thành các ch ng trìnhụ ỹ ậ ỹ ể ể ầ ươ
thông qua m t s ngôn ng l p trình, đ có th x lý đ c trên máy tính đáp ng đ cộ ố ữ ậ ể ể ử ượ ứ ượ
các yêu c u qu n lý thông tin c a ng i s d ng. ầ ả ủ ườ ử ụ
II-C U TRÚC D LI U Ấ Ữ Ệ :
1. KHÁI NI M:Ệ
• C u trúc d li u là mô hình thông tin d li u bi u di n thông tin các đ iấ ữ ệ ữ ệ ể ễ ố
t ng d liêu trong h th ng th c t . Tùy theo tính ch t x lý, thu c tính mô t c a m iượ ữ ệ ố ự ế ấ ử ộ ả ủ ỗ
đ i t ng, mà c u trúc d li u có th đ c t ch c khác nhau. ố ượ ấ ữ ệ ể ượ ổ ứ
• C u trúc d li u đ c t ch c tuân th theo các qui t c v ki u d li u , kíchấ ữ ệ ượ ổ ứ ủ ắ ề ể ữ ệ
th c và ràng bu c d li u, đ có th t ch c l u tr và x lý trên máy tính m t cáchướ ộ ữ ệ ể ể ổ ứ ư ữ ử ộ
t i u.ố ư
• Ví d : Đ qu n lý thông tin nhân viên ta t ch c c u trúc d li u nh sau:ụ ể ả ổ ứ ấ ữ ệ ư
struct sinhvien
{
char tensv[10],lop[10];
int tuoi;
float hocbong;
};
int i,siso;
sinhvien sv[20];

Có nhi u bi n d li u có th phù h p trong hi n t i, nh ng khi m r ng ch ng trình đề ế ữ ệ ể ợ ệ ạ ư ở ộ ươ ễ
đáp ng cho yêu c u phát tri n c a h th ng các bi n này tr nên không phù h p.ứ ầ ể ủ ệ ố ế ở ợ
• Phù h p v i các thao tác trên đó : Tiêu chu n này giúp tăng tính hi u qu c a bài toán,ợ ớ ẩ ệ ả ủ
vi c xây d ng và phát tri n các gi i thu t đ n gi n, t nhi n h n, ch ng trình đ t hi uệ ự ể ả ậ ơ ả ự ệ ơ ươ ạ ệ
qu cao h n v t c đ x lý .ả ơ ề ố ộ ử
Ch ng h n ch ng trình qu n lý nhân viên có liên quan đ n l u tr ( ki u file) , các thao tácẳ ạ ươ ả ế ư ữ ể
c a ch ng trình là các vi c th ng xuyên là : Thêm, Xóa , S a , Tìm , Duy t danh sách …ủ ươ ệ ươ ử ệ
Do đó n u t ch c c u trúc d li u x lý tr c ti p các công vi c trên ki u FILE thì gi iế ổ ứ ấ ữ ệ ử ự ế ệ ể ả
thu t s ph c t p, t c đ x lý ch m vì luôn ph i làm vi c trên b nh ngoài . Trongậ ẽ ứ ạ ố ộ ử ậ ả ệ ộ ớ
tr ng h p này k t h p v i t ch c d li u là danh sách (dãy c u trúc , danh sách liên k t )ườ ợ ế ợ ớ ổ ứ ữ ệ ấ ế
s d ng b nh trong , vi c x lí s nhanh h n , danh sách s nh n thông tin b t đ uử ụ ộ ớ ệ ử ẽ ơ ẽ ậ ắ ầ
ch ng trình t danh sách FILE và x lý cho đ n khi k t thúc ch ng trình danh sách sươ ừ ử ế ế ươ ẽ
đ c t ch c l u l i trên file tr c khi k t thúc.ượ ổ ứ ư ạ ướ ế
• Ti t ki m tài nguyên h th ng : Khi xây d ng c u trúc d li u ch nên s d ng tàiế ệ ệ ố ự ấ ữ ệ ỉ ử ụ
nguyên h th ng v a đ đ m nhi m đ c ch c năng c a nó. Thông th ng có 2 lo i tàiệ ố ừ ủ ả ệ ượ ứ ủ ườ ạ
nguyên th ng đ c l u tâm đó là CPU và b nh . Tùy theo yêu c u x lý, n u y u tườ ượ ư ộ ớ ầ ử ế ế ố
x lý c n nhanh ti t ki m th i gian thì tài nguyên b nh c n s d ng t i u và ng cử ầ ế ệ ờ ộ ớ ầ ử ụ ố ư ượ
l i.ạ
III-KI U D LI U Ể Ữ Ệ :
1. KHÁI NI M:Ệ
• Ki u d li u là thành ph n đ c tr ng cho t ch c, hình d ng, kích th cể ữ ệ ầ ặ ư ổ ứ ạ ướ
c a các thành ph n nh p xu t tính toán trong ch ng trình . Trong các ngôn ng l pủ ầ ậ ấ ươ ữ ậ
trình m i ki u thành ph n này s đ c c p phát v i kích th c ô nh khác nhau tùyỗ ể ầ ẽ ượ ấ ớ ướ ớ
theo ki u đ ch a giá tr đáp ng vi c l u tr và x lý trên máy tính.ể ể ứ ị ứ ệ ư ữ ử
• Ki u d li u đ c xác đ nh là m t b <V,O> v i : V là t p các giá tr h pể ữ ệ ượ ị ộ ộ ớ ậ ị ợ
l mà đ i t ng có th l u tr và O là t p các thao tác x lý có th th c thi trên đ iệ ố ượ ể ư ữ ậ ử ể ự ố
t ng.ượ
Ví d : Ki u s nguyên int : Trong đó s g m m t t p các giá tr nguyên có giá tr t -32768ụ ể ố ẽ ồ ộ ậ ị ị ừ
cho đ n +32767 và t p này cho phép th c hi n đ c các phép tóan s h c + - * / %, cácế ậ ự ệ ượ ố ọ
phép tóan quan h < <= > >= != == . Trong khi đó ki u chu i không cho phép s d ng cácệ ể ỗ ử ụ

2
unsigned int S nguyênố
không d u ấ
0  65535
2
long S nguyên dàiố
-2.147483648 
+2.147483647
4
unsigned long S nguyên dàiố
không d u ấ
04.294967295
4
char
Kí t A ự  Z ,
az ,
09 , .,’”{]+*
…
-128  +127
1
unsinged char Kí t khôngự
d u ấ
0  255
1
float S th cố ự
-3.4*10
-38
 +3.4*10
+38
4

khác nhau.
• Đ vi t m t ch ng trình ng d ng hi u qu vi c xác đ nh c u trúc d li u và gi iể ế ộ ươ ứ ụ ệ ả ệ ị ấ ữ ệ ả
thu t t i u là v n đ quan tr ng . Gi i thu t có th ph thu c vào c u trúc d li u t ch c,ậ ố ư ấ ề ọ ả ậ ể ụ ộ ấ ữ ệ ổ ứ
tuy nhiên vi c l a ch n gi i thu t phù h p tùy theo yêu c u th c t .ệ ự ọ ả ậ ợ ầ ự ế
• Trong vi c phân tích và thi t k h th ng , qua vi c kh o sát phân tích các gi i thu t cóệ ế ế ệ ố ệ ả ả ậ
th đ c bi u di n b ng các l u đ đ l u l i k t qu phân tích, đ ng th i làm n n t ngể ượ ể ễ ằ ư ồ ể ư ạ ế ả ồ ờ ề ả
cho vi c xây d ng ch ng trình.ệ ự ươ
2. Các b c phân tích gi i thu t::ướ ả ậ
• Xác đ nh các đ c tr ng d li u s đ c làm d li u nh p xu t tính toán .ị ặ ư ữ ệ ẽ ượ ữ ệ ậ ấ
• Xác đ nh các thao tác c n x lý , các thao tác tr u t ng có th đ tách bi t vi cị ầ ử ừ ượ ể ể ệ ệ
phân tích v i vi c cài đ t.ớ ệ ặ
• Phân tích toán h c các gi i thu t nh m tìm ra các giá tr trung bình v th i gian vàọ ả ậ ằ ị ề ờ
tr ng h p x u nh t cho các đ i l ng c b n. Nghĩa là th i gian x u nh t và t i u nh tườ ợ ấ ấ ạ ượ ơ ả ờ ấ ấ ố ư ấ
trong các tr ng h p.ườ ợ
TRANG 4
Cấu Truúc Dữ Liệu LVH
Ch ng 2ươ
CÁC KI U D LI U CÓ C U TRÚCỂ Ữ Ệ Ấ
I. KI U M NGỂ Ả :
1. Khái ni mệ :
 M ng là m t ki u d li u bao g m nhi u ph n t có cùng ki u , khi l u tr m ngả ộ ể ữ ệ ồ ề ầ ử ể ư ữ ả
đ c l u trên m t dãy các ô nh k ti p nhau , do đó thông qua v trí ô nh (ch s ) ta có thượ ư ộ ớ ế ế ị ớ ỉ ố ể
truy xu t 1 ph n t c a dãy .ấ ầ ử ủ
 Cú pháp khai báo : Khai báo tr c ti p ( không có tên ki u ):ự ế ể
<Tên ki u c s > <tên bi n m ng> [ đ l n ]ể ơ ở ế ả ộ ớ ;
Khai báo gián ti p : ế typedef <tên ki u c s > <tên bi n m ng> [ đ l n ] ;ể ơ ở ế ả ộ ớ
 Truy xu t giá tr bi n m ng s d ng cú pháp ấ ị ế ả ử ụ <Tên bi n>(ch s )ế ỉ ố
 Ví d ụ : typedef int day[50] ;
int a[5] ;
day h ;

for (i=1;i<=n;i++)
{
printf("Nhap phan tu thu a[%d]= ",i);
scanf("%d",&a[i]);
}
printf("Day phan tu da nhap : ");
for (i=1;i<=n;i++) printf("%4d",a[i]);
printf("\n");
tongchan=0;
printf("Day phan tu chan da nhap : ");
for (i=1;i<=n;i++)
if (a[i] % 2==0 )
{ printf("%4d",a[i]);
tongchan=tongchan + a[i];
}
printf("\n");
printf("Tong cac so chan: %d
\n",tongchan);
tongle=0;
printf("Day phan tu le da nhap : ");
for (i=1;i<=n;i++)
if (a[i] % 2!=0 )
{ printf("%4d",a[i]);
tongle=tongle + a[i];
}
printf("\n");
printf("Tong cac so le: %d \n",tongle);
getch();
}
Ch ng 3ươ

scanf(“%d”,&a.tuoi);
2. Dãy d li u c u trúcữ ệ ấ :
• Ki u dãy là ki u d li u mà m t bi n bao g m nhi u ph n t cùng ki u , ki u c u trúc làể ể ữ ệ ộ ế ồ ề ầ ử ể ể ấ
ki u mà bi n là m t ph n t g m nhi u thành ph n thu c các ki u khác nhau . Trong th c t m tể ế ộ ầ ử ồ ề ầ ộ ể ự ế ộ
danh sách bao g m nhi u đ i t ng , thông tin m i đ i t ng g m nhi u thành ph n là công vi cồ ề ố ượ ỗ ố ượ ồ ề ầ ệ
qu n lý c a ng i s d ng .ả ủ ườ ử ụ
Ch ng h n qu n lý danh sách thông tin v nhân viên ( tennv , tuoi , luong …) ,qu n lý thôngẳ ạ ả ề ả
tin v sinh viên (tensv , tuoi , lop, hocbong , diem ….)ề
• Đ t ch c qu n lý lo i thông tin danh sách trên ta t ch c ki u d li u là dãy c u trúc,ể ổ ứ ả ạ ổ ứ ể ữ ệ ấ
nghĩa là ki u k t qu c a dãy thu c ki u c u trúc.ể ế ả ủ ộ ể ấ
• Chú ý : Khi nh p d li u cho dãy c u trúc , đ i v i các thành ph n thu c ki u nguyên vàậ ữ ệ ấ ố ớ ầ ộ ể
th c, ta không th nh p tr c ti p thông qua &<tên bi n c u trúc>.<tên bi n tp> , mà ph iự ể ậ ự ế ế ấ ế ả
nh p thông qua bi n trung gian trung gian, sau đó gán l i .ậ ế ạ
• Ví d :ụ
Struct nhanvien /* khai báo c u trúc nhanvien */ấ
{ char tennv[30];
Int tuoi;
Float luongcb;
};
nhanvien nv[20]; /* khai báo bi n nv là dãy nhan vien *ế
TRANG 6
Cấu Truúc Dữ Liệu LVH
III. KI U H P (UNION)Ể Ợ
1. Khái ni m ệ :
 Ki u h p là ki u d li u đ c bi t c a ngôn ng C, ki u h p có ý nghĩa s d ng gi ngể ợ ể ữ ệ ặ ệ ủ ữ ể ợ ử ụ ố
nh ki u c u trúc , nghĩa là ki u d li u bao g m nhi u thành ph n , m i thành ph n có thư ể ấ ể ữ ệ ồ ề ầ ỗ ầ ể
thu c các ki u khác nhau . Ch ng h n mô t v đ i t ng sinh viên : h tên , tu i , đ a ch ,ộ ể ẳ ạ ả ề ố ượ ọ ổ ị ỉ
h c b ng ….ọ ổ
 Ki u h p đ c khai báo và s d ng hoàn toàn gi ng nh ki u c u trúc . Tuy nhiênể ợ ượ ử ụ ố ư ể ấ
khác nhau c b n gi a 2 ki u này là : Ki u c u trúc có kích th c là t ng kích th c c a cácơ ả ữ ể ể ấ ướ ổ ướ ủ

Char hoten[30]; Int namsinh; Char noisinh[50];
Char gioitinh; //0 :N , 1 :Namữ
Char ttgd; //0 :Không có gia đình, 1 :Có gia đình
Union {
Char tenvo[30]; Char tenchong[30];
}
};
Hoso nguoi;
Nh v y tùy theo ng i mà ta xét là nam hay n mà ta s truy xu t thông tin qua thành ph nư ậ ườ ữ ẽ ấ ầ
có tên là tenvo hay tenchong
TRANG 7
Cấu Truúc Dữ Liệu LVH
TRANG 8
Cấu Truúc Dữ Liệu LVH
IV. KI U T P TINỂ Ậ
1. KHÁI NI M:Ệ
• Ki u t p tin là ki u d li u mà d li u là m t t p các ph n t cùng ki u , đ c t ch cể ậ ể ữ ệ ữ ệ ộ ậ ầ ử ể ượ ổ ứ
l u tr b nh ngoài (thi t b l u tr : Đĩa t , quang … ) .ư ữ ở ộ ớ ế ị ư ữ ừ
• Khai báo : Có th khai báo tr c ti p ho c gián ti p ể ự ế ặ ế
- Tr c ti p : ự ế FILE *<Bi n t p tin> ;ế ậ
- Gián ti p : ế typedef FILE *<ki u t p tin> ;ể ậ
<ki u t p tin> <bi n t p tin> ; ể ậ ế ậ
Ví d : FILE *f1,*f2 ; /* Khai báo 2 bi n file f1,f2 */ụ ế
typedef FILE *taptin ; /* Khai báo ki u file taptin */ể
taptin f1,f2; /* Khai báo 2 bi n file f1,f2 */ế
• Ki u t p tin g m 2 lo i : file văn b n và file nh phân (c u trúc)ể ậ ồ ạ ả ị ấ
• Ki u file văn b n là lo i ki u file mà d li u là m t văn b n g m nhi u dòng m i dòngể ả ạ ể ữ ệ ộ ả ồ ề ỗ
là m t chu i kí t . Đ c l u tr d i d ng mã Ascii do đó có th truy xu t đ c b ng b t kìộ ỗ ự ượ ư ữ ướ ạ ể ấ ượ ằ ấ
ph n m m văn b n nào.ầ ề ả
• Ki u file nh phân (còn g i là file có c u trúc ) là ki u file mà d li u bao g m nhi uể ị ọ ấ ể ữ ệ ồ ề

 “w+t” : M t p tin ki u văn b n đ đ c/ghi n i dung , n u t p tin đã t n t i sở ậ ể ả ể ọ ộ ế ậ ồ ạ ẽ
b xóa đ ghi m i .ị ể ớ
 “a+t” : M t p tin ki u văn b n đ đ c/ghi n i dung b sung , n u t p tin ch aở ậ ể ả ể ọ ộ ổ ế ậ ư
t n t i s đ c t o m i .ồ ạ ẽ ượ ạ ớ
 “r+b” : M t p tin ki u nh phân đ đ c/ghi n i dung , n u t p tin ch a t n t iở ậ ể ị ể ọ ộ ế ậ ư ồ ạ
s có l i .ẽ ỗ
 “w+b” : M t p tin ki u nh phân đ đ c/ghi n i dung , n u t p tin đã t n t iở ậ ể ị ể ọ ộ ế ậ ồ ạ
s b xóa đ ghi m i .ẽ ị ể ớ
 “a+b” : M t p tin ki u nh phân đ đ c/ghi n i dung b sung , n u t p tinở ậ ể ị ể ọ ộ ổ ế ậ
ch a t n t i s đ c t o m i .ư ồ ạ ẽ ượ ạ ớ
Ví d : FILE *f1,*f2 ; char tenfile1[30],tenfile2[30];ụ
Printf(“nhap ten file van ban : “); gets(tenfile1) ;
f1=fopen(tenfile1,”rt”) ;
Printf(“nhap ten file sinh vien : “); gets(tenfile2) ;
f1=fopen(tenfile2,”rb”) ;
b) Hàm ghi n i dung lên fileộ :
• Ghi n i dung lên file văn b n : ộ ả
fputc( <bi n kí t > , <bi n file>)ế ự ế
Ví d : FILE *f ; char c; ụ
f=fopen(“c:\vanban.txt”,”wt”) ; c=getchar(); fput(c,f );
• Ghi n i dung lên file nh phân :ộ ị
fwrite(&<bi n>, <kich thuoc bien> , <n> , <bi n file>)ế ế
&<bi n> : Là bi n tr ch đ n vùng nh ch a n i dung ghi vào file .ế ế ỏ ỉ ế ớ ứ ộ
<kich thuoc bien> : Là kích th c bi n ghi file .ướ ế
<n> : S c u trúc c n ghi .ố ấ ầ
 Hàm s tr v giá tr b ng s c u trúc th c s ghi đ c .ẽ ả ề ị ằ ố ấ ự ự ượ
Ví d : fwrite(&nv,sizeof(nv),1,f ) ; ụ
c) Hàm đ c n i dung vào fileọ ộ :
• Đ c n i dung t file văn b n ra bi n kí t : ọ ộ ừ ả ế ự
<bi n kí t > = fgetc( <bi n file>)ế ự ế

SEEK_CUR (ho c 1) :Xu t phát t v trí hi n t i c a con tr , đi xu ng cu iặ ấ ừ ị ệ ạ ủ ỏ ố ố
file n u <so byte> d ng , ng c l i đ u file n u <so byte> âm - SEEK_ENDế ươ ượ ạ ầ ế
(ho c 2) :Xu t phát t cu i file .ặ ấ ừ ố
i) Hàm đóng t p tinậ :
1. Hàm đóng t p tin đang m :ậ ở fclose (<bi n file>) ;ế
2. Hàm đóng t t c các t p tin đang m :ấ ả ậ ở fcloseall () ;
j) Hàm xóa t p tinậ : unlink(<tên file>) ;
Bài t p ậ :
Vi t ch ng trình qu n lí h s và l ng c a nhân viên . ế ươ ả ồ ơ ươ ủ
Thông tin yêu c u g m : ầ ồ
 Lý l ch nhân viên : ị
Mã nhân viên (8 ký t ) – Tên nhân viên (30 kí t ) – Tình tr ng gia đình ( 1 kí t D:đãự ự ạ ự
có gia đình, C:ch a có gia đình ) – S con ( nguyên <=20) – Trình đ văn hóa ( 2 kí t :ư ố ộ ự
C1:c p 1, C2:c p 2, C3:c p 3, DH:đ i h c, CH:cao h c) – L ng c b n (nguyênấ ấ ấ ạ ọ ọ ư ơ ơ ả
<=1000000)
 B ng ch m công_l ng: ả ấ ươ
Tháng (nguyên <20) – Năm ( nguyên <10000) – S ngày nghĩ có phép ( nguyênố
<28) – S ngày nghĩ không phép (nguyên <28) – S ngày làm thêm (nguyên <28) –ố ố
K t qu công vi c (2 kí t : T:T t, TB:Đ t , K:Kém) – L ng th c lãnh trong thángế ả ệ ự ố ạ ươ ự
(th c ).ự
Quy t c tính l ng nh sau:ắ ươ ư
L ng th c lãnh=L ng căn b n + Ph tr iươ ự ươ ả ụ ộ
Trong đó n u:ế
- S con >2 Ph tr i=+5% l ng c b nố ụ ộ ươ ơ ả
- Trình đ văn hóa =DH (CH) Ph tr i=+5%(10%) l ng c b nộ ụ ộ ươ ơ ả
- Làm thêm Ph tr i=+4% l ng c b n / ngàyụ ộ ươ ơ ả
- Nghĩ không phép Ph tr i=-5% l ng c b n / ngàyụ ộ ươ ơ ả
- S con >2 Ph tr i=5% l ng c b nố ụ ộ ươ ơ ả
Công vi c yêu c u :ệ ầ
- C p nh t lý l ch , b ng ch m công ( thêm, xóa , s a, tìm, in danh sách)ậ ậ ị ả ấ ữ

Lênh *px+=1 ho c *px++ t ng đ ng x=x+1 ho c x++ặ ươ ươ ặ
• Ví d : ụ
#include <stdio.h>
#include <conio.h>
#include <string.h>
main()
{
int a,b;
float c;
int *pa,*pb;
float *pc;
printf("chuong trinh minh hoa truy cap gia tri kieu con tro\n");
printf("nhap so nguyen a :"); scanf("%d",&a);
printf("nhap so nguyen b :"); scanf("%d",&b);
printf("nhap so thuc c :"); scanf("%f",&c);
printf("gia tri bien a=%d , dia chi bien a=%d \n",a,&a);
pa=&a;
printf("gia tri bien a=%d , dia chi bien a=%d \n",*pa,pa);
pb=&b;
TRANG 37
Cấu Truúc Dữ Liệu LVH
printf("gia tri bien b=%d , dia chi bien b=%d \n",*pb,pb);
pc=&c;
printf("gia tri bien c=%f , dia chi bien c=%d \n",*pc,pc);
*pc=*pa+*pb;
printf("gia tri bien c= a+b %f , dia chi bien c=%d \n",*pc,pc);
c=*pc;
printf("gia tri moi bien c=%f , dia chi bien c=%d \n",*pc,&c);
printf("gia tri moi bien c=%f \n",c);
getch();

printf("\n");
tong=0;
for (i=1 ;i<=n;i++)
tong=tong+tro[i]; /* co the viet tong=tong + *(tro + i ) ; */
printf("tong cac phan tu Day da nhap :%6.2f",tong);
getch();
}
TRANG 38
Cấu Truúc Dữ Liệu LVH
IV. BI N CON TR VÀ M U TINẾ Ỏ Ẫ :
• Tr ng h p s d ng bi n con tr là c u trúc thì vi c truy xu t m t thành ph n trongườ ợ ử ụ ế ỏ ấ ệ ấ ộ ầ
c u trúc không s d ng cú pháp : <tên bi n>. <tên thành ph n> nh tr c mà ph i s d ng d uấ ử ụ ế ầ ư ướ ả ử ụ ấ
mũi tên (k t h p d u –(tr ) và >(l n)) thay th d u ch m (.) , v i cú pháp truy xu t nh sau : ế ợ ấ ừ ớ ế ấ ấ ớ ấ ư
<tên bi n tr > -> <tên thành ph n>ế ỏ ầ .
• Ví d : struct sinhvienụ
{ char hoten[30];
int tuoi ;
float hocbong; } ;
sinhvien a;
sinhvien *tro;
Trong tr ng h p này mu n truy xu t các thành ph n c a bi n a ta s d ng cú pháp :ườ ợ ố ấ ầ ủ ế ử ụ
a.hoten ; a.tuoi ; a.hocbong .
Đ truy xu t các thành ph n c a bi n tr ta s d ng cú pháp :ể ấ ầ ủ ế ỏ ử ụ
tro->hoten ; tro->tuoi ; tro->hocbong .
V. KH I T O VÀ GI I PHÓNG BI N CON TRỞ Ạ Ả Ế Ỏ :
1. KH I T OỞ Ạ : <Bi n tr > = new <Tên ki u bi n tr ch đ n >ế ỏ ể ế ỏ ỉ ế
Cho phép kh i t o m t vùng nh cho <bi n tr > có kích th c theo kích th c c a ki u d li uở ạ ộ ớ ế ỏ ướ ướ ủ ể ữ ệ
mà con tr ch đ n. ỏ ỉ ế
2. GIAI PHÓNG VÙNG NHỚ : delete <Bi n tr > ế ỏ
Cho phép xóa b vùng nh c a <bi n tr > đã đ c kh i t o tr c đó b ng new . ỏ ớ ủ ế ỏ ượ ở ạ ướ ằ

v i ch c năng qu n lí th c t . Bao g m các phép toán nh : Tìm ki m – thêm – xóa – hi uớ ứ ả ự ế ồ ư ế ệ
ch nh – tách – ghép – sao chép – duy t in danh sách , s p th t ….ỉ ệ ắ ứ ự
II. DANH SÁCH Đ CẶ :
1. KHÁI NI MỆ :
 Danh sách đ c là danh sách mà các ph n t đ c s p x p liên t c k ti p nhauặ ầ ử ượ ắ ế ụ ế ế
trong b nh . ộ ớ
 Danh sách đ c đ c t ch c d a trên ki u d li u c s là ki u dãy c u trúc .ặ ượ ổ ứ ự ể ữ ệ ơ ở ể ấ
 C u trúc d li u đ c khai báo nh sau :ấ ữ ệ ượ ư
struct data
{
int key; ( khóa)
<Ki u> info… ; (các thành ph n thông tin)ể ầ
}
typedef data list[n] ;
TRANG 40
Cấu Truúc Dữ Liệu LVH
list a;
int i,n ;
Khai báo bi n danh sách a có n ph n t , m i ph n t a[i] có các thành ph n thôngế ầ ử ỗ ầ ử ầ
tin a[i].key th hi n khóa chính , a[i].info các thông tin mô t .ể ệ ả
 Ví d : struct sinhvienụ
{ char hoten[30];
int tuoi;
float hocbong;
}
typedef sinhvien danhsach_sv [50];
danhsach_sv a;
int i,n ;
Khai báo danh sách sinh viên v i bi n a có n ph n t sinh viên , trong đó m i ph n t a[i]ớ ế ầ ử ỗ ầ ử
có các thành ph n thông tin a[i].hoten , a[i].tuoi, a[i].hocbong th hi n các thông tin môầ ể ệ

if (i>n) return(0);
TRANG 41
Cấu Truúc Dữ Liệu LVH
else return(i) ;
}
c) Lo i b m t ph n tạ ỏ ộ ầ ử :
Th c hi n tìm ph n t c n xóa , n u tìm th y xóa b ng cách lùi các ph n t đ ng sauự ệ ầ ử ầ ế ấ ằ ầ ử ứ
nó v tr c m t v trí và gi m s ph n t dãy xu ng 1.ề ướ ộ ị ả ố ầ ử ố
void xoa_pt(list a, int *n, data pt_xoa)
{
int i,j ;
i=tim_pt(a,*n, pt_xoa);
if (i!=0)
{ for (j=i;j<=*n;j++) a[j]=a[j+1];
*n=*n-1 ; printf("Da xoa xong\n");
} else printf ("khong tim thay phan tu can xoa \n");
}
d) Hi u ch nh m t ph n tệ ỉ ộ ầ ử :
Th c hi n tìm ph n t c n hi u ch nh , n u tìm th y d ng l i hi u ch nh t ng thànhự ệ ầ ử ầ ệ ỉ ế ấ ừ ạ ệ ỉ ừ
ph n theo yêu c u.ầ ầ
void hieuchinh_pt(list a, int *n, data pt_hieuchinh)
{
int i,j ;
i=tim_pt(a,*n, pt_hieuchinh);
if (i=0) printf(“khong co phan tu can hieu chinh \n”);
else { printf (“da tim thay phan tu can hieu chinh-lan luot hieu chinh\n”);
printf(“Nhap khoa moi :”);
scanf(“%d”,a[i].key);
printf(“Nhap thong tin moi :”);
scanf(“% ”,a[i].info);

void xuat_ds(list a ,int n)
{
int i ;
for (i=1; i<=n ;i++) printf("%d",a[i]);
printf("\n");
}
g) Chuy n t danh sách sang t p tin:ể ừ ậ
L n l t duy t qua danh sách và chuy n t ng ph n t t danh sách vào fileầ ượ ệ ể ừ ầ ử ừ
void list_file(list a ,int n)
{
Char tenfile[30];
File *f ;
int i ;
printf(“nhap tên tap tin can luu :”);
gets(tenfile);
f=fopen(tenfile,”wb”);
for (i=1; i<=n ;i++) fwrire(&a[i],sizeof(a[i]),1,f);
fclose(f);
}
h) Chuy n t t p tin vào danh sách:ể ừ ậ
L n l t duy t qua các ph n t trong file và chuy n t ng ph n t vào danh sách thôngầ ượ ệ ầ ử ể ừ ầ ử
qua vi c s d ng hàm thêm ph n t .ệ ử ụ ầ ử
void file_list(list a ,int* n)
{
Char tenfile[30];
File *f ;
Data p_tu;
int i ;
printf(“nhap tên tap tin can doc :”);
gets(tenfile);

t th nh t s ch a đ a ch c a ph n t th hai, vùng liên k t c a ph n t th hai sử ứ ấ ẽ ứ ị ỉ ủ ầ ử ứ ế ủ ầ ử ứ ẽ
ch a đ a ch ph n t th ba và ti p t c nh v y ….và vùng liên k t c a ph n t cu iứ ị ỉ ầ ử ứ ế ụ ư ậ ế ủ ầ ử ố
cùng s ch a giá tr null.ẽ ứ ị
 Danh sách phù h p v i các phép thêm vào lo i b , ghép danh sách .ợ ớ ạ ỏ
 C u trúc d li u đ c khai báo nh sau :ấ ữ ệ ượ ư
M t ph n t c a danh sách liên k t bao g m 2 thành ph n :ộ ầ ử ủ ế ồ ầ
+ Thành ph n d li u :L u tr thông tin ph n t .ầ ữ ệ ư ữ ầ ử
+ thành ph n liên k t :L u tr đ a ch c a ph n t k ti p trong danh sách . ầ ế ư ữ ị ỉ ủ ầ ử ế ế
+ Bi n ch đi m đ u ế ỉ ể ầ first thu c ki u con tr ch a đ a ch ph n t đ u c a danh sách. ộ ể ỏ ứ ị ỉ ầ ử ầ ủ
typedef struct data
{
<CácKi u> nameinfo… ; (các thành ph n thông tin)ể ầ
};
typedef struct list
{
data info;
struct list *link; //Con tr ch đ n c u trúc elementỏ ỉ ế ấ
};
typedef list *pointer;
pointer first;
Khai báo bi n con tr first tr đ n danh sách liên k t ch a đ a ch là đ a ch c aế ỏ ỏ ế ế ứ ị ỉ ị ỉ ủ
ph n t đ u tiên c a danh sách. Đ u tiên danh sách r ng giá tr c a first là r ngầ ử ầ ủ ầ ỗ ị ủ ỗ
(NULL) .
TRANG 45
Cấu Truúc Dữ Liệu LVH
 Ví d : struct sinhvienụ
{ char hoten[30];
int tuoi;
float hocbong;
}

{
point p,n;
n=new dssv;
n->info=ptu_them;
p=*first; first
if (p==NULL)
{ n->link=*first;
*first=n;
}
Else p
TRANG 46
Cấu Truúc Dữ Liệu LVH
{
while (p->link !=NULL) NULL
p=p->link;
n->link=p->link;
p->link=n;
}
}
c) Tìm ki m ph n t trên danh sáchế ầ ử :
Gi s c n tìm ph n t theo m t khóa (key) nào đó, vi c tìm ki m s l n l t duy tả ử ầ ầ ử ộ ệ ế ẽ ầ ượ ệ
qua các ph n t trên danh sách và so sánh v i giá tr tìm. Hàm tìm ki m s tr v đ a chầ ử ớ ị ế ẽ ả ề ị ỉ
c a ph n t c n tìm n u tìm th y , ho c tr v tr NULL n u không tìm th y.ủ ầ ử ầ ế ấ ặ ả ề ị ế ấ
Gi i thu t hàm tìm ki m nh sau :ả ậ ế ư
point search(point first, data ptu_tim)
{
point p;
p=first;
while (p!=NULL && strcmp(p->info.key,ptu_tim.key)!=0)
p=p->link;

TRANG 47
Cấu Truúc Dữ Liệu LVH
*first=NULL;
}
else
{ /* Tr ng h p ph n t c n xóa v trí khác ph n t đ u */ườ ợ ầ ử ầ ở ị ầ ử ầ
while (p!=NULL)
{ q=p;
p=p->link;
if (strcmp(p->info.hoten,x.hoten)==0) break;
}
if (p!=NULL)
{
q->link=p->link;
delete p;
}
}
}
e) S p x p danh sáchắ ế :
D a trên m t khóa nào đó đ s p x p, ta s d ng ph ng pháp đ i ch gi a các ph nự ộ ể ắ ế ử ụ ươ ổ ổ ữ ầ
t . Dùng 2 con tr p và q đ u tiên cho p tr vào ph n t đ u , q tr vào ph n t k sau,ử ỏ ầ ỏ ầ ử ầ ỏ ầ ử ế
so sánh p và q theo khóa và đ i ch gi a chúng cho nhau khi ch a th a đi u ki n s pổ ổ ữ ư ỏ ề ệ ắ
x p, sau đó tăng bi n tr q đ n ph n t k ti p, ti p t c so sánh v i p và đ i ch khiế ế ỏ ế ầ ử ế ế ế ụ ớ ổ ổ
ch a th a, quá trình này ti p t c cho đ n khi q duy t đ n ph n t cu i cùng, ti p t cư ỏ ế ụ ế ệ ế ầ ử ố ế ụ
tăng con tr p lên ph n t k sau, quá trình ti p t c t ng t v i q, cho đ n khi danhỏ ầ ử ế ế ụ ươ ự ớ ế
sách đ c s p x p hoàn toàn.ượ ắ ế
Gi i thu t nh sau :ả ậ ư
void sort_list(point *first)
{
point p,q;

{ printf(……………………………………………………………);
p=p->link;
}
}
}
g) Chuy n t danh sách vào fileể ừ :
Ch c năng này đáp ng vi c l u tr d li u trên đĩa sau khi x lý xong .ứ ứ ệ ư ữ ữ ệ ử
Gi i thu t nh sau :ả ậ ư
void list_file(point first,char tenf[30])
{
FILE *f ; data x; point p;
f=fopen(tenf,"wb");
p=first;
while (p!=NULL)
{
x=p->info;
fwrite(&x,sizeof(x),1,f);
p=p->link;
}
fclose(f);
}
h) Chuy n t file vào danh sáchể ừ :
Ch c năng này đáp ng vi c đ a d li u l u tr t file trên đĩa ra danh sách đ x lý .ứ ứ ệ ư ữ ệ ư ữ ừ ể ử
Gi i thu t nh sau :ả ậ ư
void file_list(point *first,char tenf[30])
{
FILE *f ; data x;
f=fopen(tenf,"rb");
while (fread(&x,sizeof(x),1,f)==1)
{

void in_dssv(point first);
void sapxep_dssv(point *first);
void dssv_file(point first, char
tenf[30]);
void file_dssv(point *first,char
tenf[30]);
void them_dau(point *first ,sinhvien x)
{ point p;
p=new dssv;
p->info=x;
p->link=*first;
*first=p;
}
void them_cuoi(point *first,sinhvien x)
{
point p,n;
n=new dssv;
n->info=x;
p=*first;
if (p==NULL)
{ n->link=*first;
*first=n;
}
else
{
while (p->link !=NULL)
p=p->link;
n->link=p->link;
p->link=n;
}

}
}
}
void xoa_ptu_dau(point *first)
{
point p;
if (first!=NULL)
{
p=*first;
*first=p->link;
delete p;
}
}
void in_dssv(point first)
{ point p;
p=first;
printf(" HO TEN TUOI
HOC BONG \n");
TRANG 50