Bài giảng Cơ sở dữ liệu giải thuật: Bài 5 - Danh sách liên kết cung cấp cho các bạn những kiến thức về 3 cách để liên kết dữ liệu, KDLTT danh sách, DSLK bằng C++, các phép toán trên DSLK, các dạng DSLK và một số kiến thức khác. | Bài 5: Danh sách liên k t Gi ng viên: Hoàng Th i p Khoa Công ngh Thông tin – i h c Công Ngh 3 cách liên k t d li u • M ng: t p h p các ph n t cùng ki u • struct/class: t p h p các thành ph n có ki u (có th ) khác nhau • Con tr diepht@vnu 2 Các KDLTT ã h c • KDLTT danh sách – Phép toán • • • • • • – Cài insert delete append at length empty t • m ng tĩnh • m ng ng diepht@vnu • KDLTT t p ng – Phép toán • • • • • • • – Cài insert delete search max min empty length t • m ng s p • m ng ng không ư c ng ư c s p 3 Nh n xét • ph c t p khi cài – – – – t danh sách b ng m ng truy c p: getElement(A, i) c p nh t: update(A, i) xen thêm giá tr x: insert(A, i, x) xóa b t: del(A, i) • Danh sách liên k t giúp insert và del hi u qu hơn diepht@vnu 4 KDLTT danh sách • Cài b ng m ng – at: O(1) – insert: O(N) – delete: O(N) diepht@vnu • Cài b ng danh sách liên k .
