Bài giảng Cơ sở dữ liệu giải thuật: Bài 5 - Danh sách liên kết

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 />