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

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: Các yêu cầu đối với danh sách liên kết, danh sách liên kết đơn, cài đặt danh sách bằng C++, yêu cầu thời gian chạy, thao tác chèn,... Mời các bạn tham khảo.
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ểnDanh sách liên kết(Linked List)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnCá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 Đầu DS Cuối DSThờ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)Danh sách liên kết đơn insert eraseDanh sách liên kết đôiCà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ằngGiao 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 đầuint push_back(const Object & x); // thêm vào cuốiint pop_front(); // xóa ở đầuint pop_back(); // xóa ở cuối// chèn x vào trước phần tử xác định bởi itriterator 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áchYê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 data data datastruct 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) { }};Thao tác chèn (insert)Thao tác xóa (erase)