A
B
C
D
F
G
E
H
K
C U TRÚC D LI U VÀ Ấ Ữ Ệ
C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU T (501040)Ả Ậ
GI I THU T (501040)Ả Ậ
Ch ng 6: Danh sách và chu iươ ỗ
Ch ng 6: Danh sách và chu iươ ỗ
ĐH Bách Khoa Tp.HCM Ch ng 6. Danh sách và chu iươ ỗ 2
Khoa Công ngh Thông tinệ
Danh sách tr u t ngừ ượ
M t danh sách (list) ki u Tộ ể
M t dãy h u h n ki u Tộ ữ ạ ể
M t s tác v :ộ ố ụ
1. Kh i t o danh sách r ng (ở ạ ỗ create)
2. Ki m tra r ng (ể ỗ empty)
3. Ki m tra đ y (ể ầ full)
4. Tính kích th c (ướ size)
5. Xóa r ng danh sách (ỗclear)
6. Thêm m t giá tr vào danh sách t i m t ví trí c th (ộ ị ạ ộ ụ ể insert)
7. L y m t giá tr t i m t v trí c th ra kh i danh sách (ấ ộ ị ạ ộ ị ụ ể ỏ remove)
8. Nh n v giá tr t i m t v trí c th (ậ ề ị ạ ộ ị ụ ể retrieve)
9. Thay th m t giá tr t i m t v trí c th (ế ộ ị ạ ộ ị ụ ể replace)
10. Duy t danh sách và thi hành m t tác v t i m i v trí (ệ ộ ụ ạ ỗ ị traverse)
ĐH Bách Khoa Tp.HCM Ch ng 6. Danh sách và chu iươ ỗ 3
Khoa Công ngh Thông tinệ
Thi t k các ph ng th cế ế ươ ứ
ĐH Bách Khoa Tp.HCM Ch ng 6. Danh sách và chu iươ ỗ 4
Khoa Công ngh Thông tinệ
Ch s các ph n tỉ ố ầ ử
Đánh ch s m t danh sách có n ph n t :ỉ ố ộ ầ ử
Đánh ch s t 0, 1, … các ph n tỉ ố ừ ầ ử
Ví d : aụ0, a1, a2, …, an-1
Ph n t aầ ử idx đ ng sau aứidx-1 và tr c aướ idx+1 (n u có)ế
Dùng ch s :ỉ ố
Tìm th y m t ph n t , tr v v trí (ch s ) c a nó.ấ ộ ầ ử ả ề ị ỉ ố ủ
Thêm vào m t ph n t t i v trí ộ ầ ử ạ ị idx thì ch s các ỉ ố
ph n t cũ t ầ ử ừ idx tr v sau đ u tăng lên 1.ở ề ề
Ch s này đ c dùng b t k danh sách đ c hi n ỉ ố ượ ấ ể ượ ệ
th c th nào c p v t lý.ự ế ở ấ ậ
ĐH Bách Khoa Tp.HCM Ch ng 6. Danh sách và chu iươ ỗ 5
Khoa Công ngh Thông tinệ
Ph ng th c insert và removeươ ứ
