Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 6: Danh sách liên kết (Linked List)

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 6: Danh sách liên kết (Linked List)

1. Danh sách liên kết (Linked List) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Các yêu cầu đối với danh sách liên kết • Chèn và xóa phần tử một cách hiệu quả • Xóa tất cả các phần tử • Toán tử gán • Các toán tử so sánh • Hàm tạo/hàm hủy • Lớp mẫu (dùng chung cho nhiều kiểu phần tử) • Cơ chế hiệu quả để duyệt các phần tử
3. Danh sách liên kết đơn Đầu DS Cuối DS Thời gian chạy cho các thao tác ? • push_front / push_back (thêm vào đầu/cuối DS) • pop_front / pop_back (xóa khỏi đầu/cuối DS) • insert / erase (chèn/xóa ở giữa DS)
4. Danh sách liên kết đơn insert erase
5. Danh sách liên kết đôi
6. Cài đặt danh sách bằng C++ • Thư viện chuẩn C++ có lớp list: − định nghĩa trong tệp tiêu đề “list” #include − cài đặt dưới dạng danh sách liên kết đôi • Sau đây chúng ta sẽ tự cài đặt danh sách: − cũng dưới dạng danh sách liên kết đôi − nhưng đặt tên là List (chữ “L” hoa) để phân biệt với list trong thư viện chuẩn C++
7. Giao diện “public” của List (1) • Hàm tạo, hàm hủy, toán tử gán: List(); // hàm tạo List(const List &rhs); // hàm tạo sao chép ~List(); // hàm hủy const List & operator= (const List &rhs); • Các phương thức chỉ đọc (read-only): int size() const; // số phần tử bool empty() const; // danh sách rỗng?
8. Giao diện “public” của List (2) • Truy nhập phần tử: Object & front(); // phần tử đầu Object & back(); // phần tử cuối const Object & front() const; // phiên bản hằng const Object & back() const; // phiên bản hằng • Truy nhập vị trí dùng iterator: iterator begin(); // vị trí phần tử đầu iterator end(); // vị trí sau phần tử cuối const_iterator begin() const; // phiên bản hằng const_iterator end() const; // phiên bản hằng
9. Giao diện “public” của List (3) • Các phương thức xử lý danh sách: int push_front(const Object & x); // thêm vào đầu int push_back(const Object & x); // thêm vào cuối int pop_front(); // xóa ở đầu int pop_back(); // xóa ở cuối // chèn x vào trước phần tử xác định bởi itr iterator insert(iterator & itr, const Object &x); iterator erase(iterator itr); //xóa ở vị trí itr // xóa từ start đến trước end (không tính end) iterator erase(iterator start, iterator end); void clear(); // xóa rỗng danh sách
10. Yêu cầu thời gian chạy (1) • Thời gian chạy O(1): − Hàm tạo ngầm định − push_front(x), push_back(x) − pop_front(), pop_back() − insert(itr, x), erase(itr) − begin(), end() − front(), back() − size(), empty()
11. Yêu cầu thời gian chạy (2) • Thời gian chạy O(n): − Hàm tạo sao chép − Hàm hủy − clear() − erase(start, end)
12. Giao diện “public” của iterator • Các toán tử chỉ đọc (bằng/khác/lấy tham chiếu) int operator== (const iterator & rhs) const; int operator!= (const iterator & rhs) const; Object & operator* ( ) const; • Các toán tử ghi (tăng/giảm iterator) iterator & operator++ ( ); // tiền tố iterator operator++ (int); // hậu tố iterator & operator ( ); // tiền tố iterator operator (int); // hậu tố • Yêu cầu thời gian chạy O(1)
13. Các nút (node) trong danh sách data data data struct Node prev prev prev { next next next Object data; Node *prev; Không cần cấp phát Node *next; bộ nhớ liên tục Node(const Object &d = Object(), Node * p = NULL, Node * n = NULL) : data(d), prev(p), next(n) { } };
14. Thao tác chèn (insert)
15. Thao tác xóa (erase)