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 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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu giải thuật: Bài 5 - Danh sách liên kếtBài 5: Danh sách liên k tGi ng viên: Hoàng Th i pKhoa Công ngh Thông tin –i h c Công Ngh3 cáchliê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 trdiepht@vnu2Các KDLTT ã h c• KDLTT danh sách– Phép toán••••••– Càiinsertdeleteappendatlengthemptyt• m ng tĩnh• m ng ngdiepht@vnu• KDLTT t png– Phép toán•••••••– Càiinsertdeletesearchmaxminemptylengtht• m ngs p• m ngng không ư cng ư c s p3Nh n xét•ph c t p khi cài––––t danh sách b ng m ngtruy 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ơndiepht@vnu4KDLTT 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ênk t5