Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 7: Danh sách liên kết

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 7: Danh sách liên kết" cung cấp cho người học các kiến thức: Vấn đề của Mảng, danh sách liên kết, cấu trúc của một Node, cấu trúc danh sách liên kết đơn,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 7: Danh sách liên kết Bài 7Danh sách liên kết (Linked List) 1 Vấn đề của MảngXét lại vấn đề sử dụng mảng để tạo danh sách : Thêm phần tử : O(n) Xoá phần tử : O(n) Số phần tử mảng cố định!!! 2 Vấn đề của Mảng Làm sao có thể thêm (hay xoá) một phần tử mà không phải di chuyển các phần tủ khác? Làm sao để danh sách “động” hơn? Cần dùng một cấu trúc lưu trữ mới với các yêu cầu Các phần tử phải được tách rời ra Và được nối với nhau bằng “dây liên kết” Khi thêm phần tử chỉ cần thay đổi mối đây liên kết  chi phí xử lý sẽ thấp hơn 3 DANH SÁCH LIÊN KẾT Mô hình cấu trúc dữ liệu trừu tượng Linked Listlà một dãy các vị trí lữu trữ các đối tượng với sốlượng tùy ý. Nó thiết lập một mối quan hệ trước/sau giữa cácvị trí Danh sách liên kết đơn Danh sách liên kết kép 4Danh sách liên kết đơnCác nút (node) được cài đặt baogồm: next Phần tử lưu trữ trong nó Một liên kết đến nút kế tiếpSử dụng môt con trỏ header, trỏ vàonode đầu danh sách và con trỏ elem nodetrailer trỏ vào node cuối danh sách. trailerheader node NULL elem 5Cấu trúc của một NodeCác thuộc tính  Element *elem;  Node *next;Các phương thức  Node *getnext() - Trả lại địa chỉ của nút kế tiếp  Element *getElem() - Trả lại địa chỉ của phần tử mà nút trỏ tới trong nút  void setNext(Node *) - Đặt thuộc tính next trỏ đến đ/c phần tử là đối của phương thức  void setElem(Element e) - Đặt phần tử e vào nút 6Cấu trúc danh sách liên kết đơn Các thuộc tính: Các phương thức cập nhật:  Node *header  void replace(Node *p, Element e)  Node *trailer  Node *insertAfter(Node *p, Element e) Các phương thức  Node * insertFirst(Element e) chung:  Node * insertLast(Element e)  long size(),  Node * getNode(int i)  int isEmpty()  void remove(Node *p) Các phương thức truy cập:  Node *first()  Node *last() 7Insertion First Hình ảnh phép toán insertFirst(), phép toán trả lại vị trí q trailer header NULL A B C trailerheader NULL A B C X q trailerheader NULL X A B C 8Insertion Last Hình ảnh phép toán insertLast(), phép toán trả lại vị trí q trailer header NULL A B C trailerheader NULL C NULL A B X q trailerheader NULL A B C X 9Insertion After Hình ảnh phép toán insertAfter(p, X), phép toán trả lại vị trí q trailer header p NULL A B C trailerheader NULL A B C X trailerheader NULL A B X C ...