Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Danh sách liên kết" cung cấp cho người học các kiến thức: Danh sách liên kết, danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng trò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: Danh sách liên kết - Nguyễn Mạnh Hiển (HKI năm 2020-2021)Danh sách liên kết(Linked Lists)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnNội dung1. Danh sách liên kết2. Danh sách liên kết đơn3. Danh sách liên kết đôi4. Danh sách liên kết vòng tròn1. Danh sách liên kếtDanh sách liên kết• Là một tập nút liên kết với nhau theo trật tự tuyến tính (có trước có sau).• Mỗi nút chứa: − một phần tử; − một hoặc hai liên kết tới nút lân cận.• Các nút nằm rải rác trong bộ nhớ máy tính (trong khi các phần tử của mảng và vector nằm liên tục).Các kiểu danh sách liên kết Danh sách liên kết đơn Danh sách liên kết đôi Danh sách liên kết vòng tròn2. Danh sách liên kết đơnDanh sách liên kết đơn• Mỗi nút chỉ có một liên kết trỏ tới nút kế tiếp. − Riêng nút cuối cùng không có nút kế tiếp, vì vậy con trỏ của nó bằng NULL.• Các thao tác chính: − Chèn phần tử mới vào đầu danh sách; − Xóa phần tử đầu danh sách; − Lấy phần tử đầu danh sách.Cài đặt danh sách liên kết đơntemplate class SingleList { public: Hàm tạo, hàm hủy; Chèn/xóa ở đầu danh sách; Lấy phần tử đầu danh sách; ... private: struct Node { ... }; // Kiểu dữ liệu của các nút Node * head; // Con trỏ tới nút đầu danh sách};Kiểu dữ liệu của các nútstruct Node { T elem; // Phần tử Node * next; // Liên kết tới nút kế tiếp // Hàm tạo. // (e: phần tử; n: địa chỉ của nút kế tiếp) Node(T e, Node * n) { elem = e; next = n; }};Hàm tạo và hàm hủySingleList() { head = NULL; // Ban đầu danh sách rỗng}// Hàm hủy dùng hàm empty để kiểm tra danh sách// rỗng, dùng hàm popFront để xóa phần tử đầu// danh sách (hai hàm đó ta sẽ lập trình sau).~SingleList() { while (!empty()) // Cứ xóa phần tử đầu tiên popFront(); // cho đến khi danh sách} // rỗng thì thôi.Các hàm khác// Kiểm tra danh sách có rỗng hay không.bool empty() { return (head == NULL);}// Lấy phần tử đầu danh sách (có kiểu là T).T front() { return head->elem; // head trỏ tới nút đầu,} // còn elem là tên // trường chứa phần tử.Chèn vào đầu danh sáchChèn vào đầu danh sách (tiếp)// e (element) là phần tử cần chèn.void pushFront(T e) { // Tạo nút mới (v): // - chứa phần tử cần chèn (e) // - trỏ tới nút đầu danh sách (head) Node * v = new Node(e, head); // Vì nút mới sẽ thành nút đầu danh sách, // phải cập nhật head cho trỏ tới nút mới. head = v;}Xóa phần tử đầu danh sáchXóa phần tử đầu danh sách (tiếp)void popFront() { // Giữ lại địa chỉ của nút đầu danh sách (head) // (sẽ cần địa chỉ này khi xóa). Node * old = head; // Vì nút thứ hai sẽ trở thành nút đầu, phải cập nhật // head cho trỏ tới nút thứ hai (head->next). head = head->next; // Xóa nút đầu cũ dùng địa chỉ đã giữ lại bên trên. delete old;}Phân tích thời gian chạy• Hàm tạo: O(1)• Hàm hủy: O(n)  vì phải xóa n phần tử/nút.• Kiểm tra rỗng: O(1)• Lấy phần tử đầu danh sách: O(1)• Chèn/xóa ở đầu danh sách: O(1)3. Danh sách liên kết đôiDanh sách liên kết đôi• Mỗi nút chứa một phần tử và hai liên kết: − một liên kết tới nút kế tiếp (next); − một liên kết về nút liền trước (previous).• Các thao tác chính: − Chèn/xóa ở đầu, ở cuối hoặc ở vị trí hiện hành; − Lấy phần tử ở đầu, ở cuối hoặc ở vị trí hiện hành; − Duyệt danh sách tiến hoặc lùi.• Chú ý: header và trailer là những nút đầu/cuối giả (không chứa phần tử), được dùng để thuận tiện cho việc lập trình.Cài đặt danh sách liên kết đôitemplate Chú ý: Lớp list trong thư viện chuẩnclass DoubleList { C++ thực thi danh sách liên kết đôi. public: Hàm tạo, hàm hủy, kiểm tra rỗng; Các thao tác chèn/xóa; Các thao tác lấy phần tử; Các thao tác duyệt danh sách; private: struct DNode { ... }; // Kiểu của các nút DNode * header; // Đầu danh sách (nút giả) DNode * trailer; // Cuối danh sách (nút giả) DNode * currentPos; // Vị trí hiện hành};Kiểu dữ liệu của các nútstruct DNode { T elem; // Phần tử DNode * next; // Liên kết về phía sau DNode * prev; // Liên kết về phía trước};Chú ý: Vì cấu trúc DNode không có hàm tạo, khi tạo nút mới thìphải khởi tạo giá trị cho các trường (elem, next, prev) thôngqua các câu lệnh gán riêng biệt. ...