Bài 5: Danh sách liên k t<br />
Gi ng viên: Hoàng Th i p<br />
Khoa Công ngh Thông tin –<br />
i h c Công Ngh<br />
<br />
3 cách<br />
<br />
liên k t d li u<br />
<br />
• M ng: t p h p các ph n t cùng ki u<br />
• struct/class: t p h p các thành ph n có ki u (có th )<br />
khác nhau<br />
• Con tr<br />
<br />
diepht@vnu<br />
<br />
2<br />
<br />
Các KDLTT ã h c<br />
• KDLTT danh sách<br />
– Phép toán<br />
•<br />
•<br />
•<br />
•<br />
•<br />
•<br />
<br />
– Cài<br />
<br />
insert<br />
delete<br />
append<br />
at<br />
length<br />
empty<br />
<br />
t<br />
<br />
• m ng tĩnh<br />
• m ng ng<br />
<br />
diepht@vnu<br />
<br />
• KDLTT t p<br />
<br />
ng<br />
<br />
– Phép toán<br />
•<br />
•<br />
•<br />
•<br />
•<br />
•<br />
•<br />
<br />
– Cài<br />
<br />
insert<br />
delete<br />
search<br />
max<br />
min<br />
empty<br />
length<br />
<br />
t<br />
<br />
• m ng<br />
s p<br />
• m ng<br />
<br />
ng không ư c<br />
ng ư c s p<br />
3<br />
<br />
Nh n xét<br />
•<br />
<br />
ph c t p khi cài<br />
–<br />
–<br />
–<br />
–<br />
<br />
t danh sách b ng m ng<br />
<br />
truy c p: getElement(A, i)<br />
c p nh t: update(A, i)<br />
xen thêm giá tr x: insert(A, i, x)<br />
xóa b t: del(A, i)<br />
<br />
• Danh sách liên k t giúp insert và del hi u qu hơn<br />
<br />
diepht@vnu<br />
<br />
4<br />
<br />
KDLTT danh sách<br />
• Cài b ng m ng<br />
– at: O(1)<br />
– insert: O(N)<br />
– delete: O(N)<br />
<br />
diepht@vnu<br />
<br />
• Cài b ng danh sách liên<br />
k t<br />
<br />
5<br />
<br />