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

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 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ử Danh sách liên kết đơn 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) Đầu DS Cuối DS Danh sách liên kết đơn insert erase Danh sách liên kết đôi 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++ 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? 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 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 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() 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) 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) Các nút (node) trong danh sách struct Node { Object data; Node *prev; Node *next; Node(const Object &d = Object(), Node * p = NULL, Node * n = NULL) : data(d), prev(p), next(n) { } }; data prev next data prev next data prev next Không cần cấp phát bộ nhớ liên tục Thao tác chèn (insert) Thao tác xóa (erase)