M C L CỤ Ụ
M C L CỤ Ụ ...................................................................................................01
PH N I: GI I THI U CHUNGẦ Ớ Ệ ................................................................02
1. Khái ni m v danh sách móc n iệ ề ố ...........................................................02
2. Các phép toán trên danh sách..................................................................02
3. Gi i thi u v ch ng trình qu n lý sinh viênớ ệ ề ươ ả .......................................02
PH N II: GI I THI U CÁC THÀNH PH N CHÍNH C A CH NGẦ Ớ Ệ Ầ Ủ ƯƠ
TRÌNH.........................................................................................................03
1. S đ các l p đ i t ngơ ồ ớ ố ượ ........................................................................03
2. Mô t các l p đ i t ngả ớ ố ượ ........................................................................04
PH N III: GI I THI U CÁC CH C NĂNG TRONG CH NG Ầ Ớ Ệ Ứ ƯƠ
TRÌNH.........................................................................................................08
PH N IV: MÃ NGU N CH NG TRÌNHẦ Ồ ƯƠ ............................................09
PH N V: K T LU N VÀ H NG PHÁT TRI N CH NGẦ Ế Ậ ƯỚ Ể ƯƠ
TRÌNH.........................................................................................................22
PH N 1: GI I THI U CHUNGẦ Ớ Ệ
1.Khái ni m v danh sách móc n iệ ề ố
Danh sách là t p h p các nút (ô nh ) không li n k , có ki u d li uậ ợ ớ ề ề ể ữ ệ
xác đ nh và gi a chúng có liên l c v i nhau b i con tr đ a ch .ị ữ ạ ớ ở ỏ ị ỉ
S nút c a danh sách g i là chi u dài c a danh sách. M t danh sáchố ủ ọ ề ủ ộ
có chi u dài b ng 0 là m t danh sách r ng.ề ằ ộ ỗ
1
Danh sách móc n i kép là t p h p các nút mà m i nút có 2 m i liênố ậ ợ ỗ ố
k t v i 2 ph n t khác trong danh sách.ế ớ ầ ử
M t nút trong danh sách móc n i kép có d ng:ộ ố ạ
Trong đó:
LEFT: con tr trái: l u tr đ a ch nút tr cỏ ư ữ ị ỉ ướ
RIGHT: con tr ph i: L u tr đ a ch nút sauỏ ả ư ữ ị ỉ
Danh sách móc n i kép có d ng:ố ạ
2.Các phép toán trên danh sách
•T o m i m t danh sáchạ ớ ộ
•Thêm 1 nút vào danh sách
•Tìm ki m 1 nút trong danh sáchế
•Xóa 1 nút kh i danh sáchỏ
•S p x p th t các danh sáchắ ế ứ ự
•H y danh sáchủ
3.Gi i thi u v ch ng trình qu n lý sinh viênớ ệ ề ươ ả
Ch ng trình giúp qu n lý d li u cũng nh thông tin c a sinh viênươ ả ữ ệ ư ủ
nh : mã s sinh viên, h tên, năm sinh, l p, đi m trung bình….ư ố ọ ớ ể
Ch ng trình có các ch c năng chình nh :ươ ứ ư
•T o 1 danh sách sinh viênạ
•Thêm 1 sinh viên vào danh sách
•Xóa 1 sinh viên
•Tìm ki m 1 sinh viênế
•S p x p danh sách sinh viênắ ế
PH N II: GI I THI U CÁC THÀNH PH N CHÍNH C A CH NGẦ Ớ Ệ Ầ Ủ ƯƠ
TRÌNH
2
LEFT INFO RIGHT
S Đ CÁC L P Đ I T NGƠ Ồ Ớ Ố ƯỢ
MÔ T CÁC L P Đ I T NGẢ Ớ Ố ƯỢ
L p SV:ớ
1. Thu c tính:ộ
•Ki u d li u char:ể ữ ệ
maso: Mã s sinh viênố
hoten: H và tên sinh viênọ
lop: L p sinh viên đang h cớ ọ
gioitinh: Gi i tính sinh viênớ
quequan: Quê quán sinh viên
•Ki u d li u int:ể ữ ệ
ns: Năm sinh
•Ki u d li u float:ể ữ ệ
3
SINHVIEN info (đ i t ngố ượ
thành ph n); * left, * rightầ
getnode
freenode Createlist
Nhaplist
Showlist
Listsize
Push_first
Push_last
Push_after
Search_name
Search_maso
Del_first
Del_last
Del_node_name
Del_node_maso
Clear_list
Sort_list_dtb
Ghi_file
Doc_file
*first, *last
Maso,hoten,namsinh,gio
itinh,quequan,lop,dtb
Nh pậ
Hi nệ
NODE LIST
SINHVIEN
MENU
LIST a (đttp)
Hien
Xuly
dtb: đi m trung bìnhể
2. Ph ng th c:ươ ứ
•Nhap: Hàm nh p 1 sinh viênậ
•Hien: Hàm hi n sinh viênệ
I. L p NODE:ớ
1. Thu c tính:ộ
•Đ i t ng thành ph n:ố ượ ầ
Info: ch a thông tin sinh viênứ
•*l: Con tr trái, tr t i nút đ ng tr cỏ ỏ ớ ứ ướ
•*r: Con tr ph i, tr t i nút đ ng sauỏ ả ỏ ớ ứ
2. Ph ng th c:ươ ứ
•Getnode: Hàm c p phát 1 nút m i cho danh sách móc n iấ ớ ố
Thu t toán:ậ
B1: Kh i t o 1 nút m i , c p phát b nh cho nút đóở ạ ớ ấ ộ ớ
B2: N u nút đó khác NULL ế
p->right=NULL;
p->left=NULL;
B3: Nh p d li u info cho nút đóậ ữ ệ
Hàm tr v con tr tr t i đ a ch nút m i t o. N u không đ b nh đ t o, hàm trả ề ỏ ỏ ớ ị ỉ ớ ạ ế ủ ộ ớ ể ạ ả
v giá tr NULL.ề ị
•Freenode: Hàm gi i phóng b nh nút v a c p phátả ộ ớ ừ ấ
II. L p LINKLIST th a k t l p NODEớ ừ ế ừ ớ
1. Thu c tính ki u NODEộ ể
•*first: tr t i ph n t đ u danh sáchỏ ớ ầ ử ầ
•*last: tr t i ph n t cu i danh sáchỏ ớ ầ ử ố
2. Ph ng th c:ươ ứ
•Createlist: Hàm kh i t o 1 danh sách m iở ạ ớ
Cho giá tr các con tr qu n lý đ a ch hai nút đ u và cu i danh sáchị ỏ ả ị ỉ ầ ố
móc n i kép v con tr NULL.ố ề ỏ
•Nhaplist: Hàm nh p n sinh viên vào danh sáchậ
Thu t toán:ậ
B1: Nh p s l ng sinh viên c n nh p vào danh sách (n)ậ ố ượ ầ ậ
B2: Kh i t o bi n đ m i, i=0ở ạ ế ế
B3: So sánh i v i n. N u i<n -> B4, n u i>=n -> B6ớ ế ế
B4: Thêm 1 nút vào danh sách (push_last())
B5: Tăng i lên 1 -> Quay l i b c 2ạ ướ
B6: K t thúc.ế
•Showlist: Hàm hi n danh sách sinh viênệ
Thu t toán:ậ
4
B1: Kh i t o 1 con tr tr vào nút đ u tiênở ạ ỏ ỏ ầ
B2: N u nút đó khác NULL->B3, ng c l i ->k t thúcế ượ ạ ế
B3: Hi n nút đóệ
B4: D ch con tr sang ph i 1 nút->B2ị ỏ ả
•Listsize: Hàm đ m s l ng nút trong danh sáchế ố ượ
Thu t toán:ậ
B1: Kh i t o 1 con tr , bi n đ m I (i=0)ở ạ ỏ ế ế
B2: Cho con tr tr vào nút đ u tiênỏ ỏ ầ
B3: N u nút đó khác NULL ->B4, ng c l i->B6ế ượ ạ
B4: d ch con tr sang ph i 1 nútị ỏ ả
B5: Tăng i lên 1->B3
B6: Tr v i;ả ề
•Push_first: Hàm thêm 1 nút vào đ u danh sách.ầ
Thu t toán:ậ
B1: Kh i t o con tr , t o 1 nút.ở ạ ỏ ạ
B2: Neu nút đó =NULL ->B3.
B3: N u danh sách r ng->B4.ế ỗ
N u danh sách không r ng-> B5.ế ỗ
B4: đ t nút m i làm nút đ u và nút cu i.ặ ớ ầ ố
B5: Liên k t ph i nút m i tr đ n nút đ u tiên hi n th i trong danhế ả ớ ỏ ế ầ ệ ở
sách.
B6: Liên k t trái nút đ u tiên hi n th i tr đ n nút m i.ế ầ ệ ờ ỏ ế ớ
B7: Đ t nút m i làm nút đ u tiên.ặ ớ ầ
•Push_last: Hàm thêm 1 nút vào cu i danh sách.ố
Thu t toán:ậ
B1: Kh i t o con tr , t o 1 nútở ạ ỏ ạ
B2: N u nút đó =NULL ->B3ế
B3: N u danh sách r ng->B4ế ỗ
N u danh sách không r ng-> B5ế ỗ
B4: đ t nút m i làm nút đ u và nút cu i.ặ ớ ầ ố
B5: Liên k t ph i nút cu i cùng hi n th i tr đ n nút m i.ế ả ố ệ ờ ỏ ế ớ
B6: Liên k t trái m i tr đ n nút cu i cùng hi n th i trong danhế ớ ỏ ế ố ệ ờ
sách.
B7: Đ t nút m i làm nút cu i cùng.ặ ớ ố
•Push_after: Hàm thêm 1 nút vào sau 1 v trí trong danh sáchị
Thu t toán:ậ
B1: Kh i t o con tr p tr đ n m i, con tr q đ duy t, kh i t oở ạ ỏ ỏ ế ớ ỏ ể ệ ở ạ
bi n vt đ xác đ nh v trí c n chèn sau, i là bi n đ m(i=0).ế ể ị ị ầ ế ế
B2: Nh p v trí c n chèn (vt).ậ ị ầ
B3: So sánh vt v i s nút trong danh sáchớ ố
5