Danh Sách Liên Kết Kép - Tài Liệu Text - 123doc

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Kỹ thuật lập trình >

Danh sách liên kết kép

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.6 MB, 426 trang )

Giáo trình Cấu trúc dữ liệu và Giải thuật63 nhất, nếu cần phải bắt đầu từ đầu danh sách, hàm cũng sẽ làm việc giống nhưcách chúng ta đã hiện thực trước đây.

4.3.4. Danh sách liên kết kép

Một vài ứng dụng thường xuyên yêu cầu dòch chuyển tới và lui trên danh sách. Trong phần trước chúng ta đã giải quyết việc dòch chuyển theo một chiều trongquá trình duyệt danh sách. Nhưng việc lập trình hơi khó khăn và thời gian chạy chương trình phụ thuộc vào danh sách, nhất là khi danh sách có nhiều phần tử.Để khắc phục vấn đề này, có nhiều chiến lược khác nhằm giải quyết việc tìm phần tử nằm trước phần tử hiện tại trong danh sách. Trong phần này chúng tatìm hiểu một chiến lược đơn giản nhất nhưng cũng linh động và phù hợp trong rất nhiều trường hợp.

4.3.4.1. Các khai báo cho danh sách liên kết kép

Như hình 4.3 minh họa, ý tưởng ở đây là việc lưu cả hai con trỏ chỉ hai hướng ngược nhau trong cùng một node của danh sách. Bằng cách dòch chuyểntheo tham chiếu thích hợp chúng ta có thể duyệt danh sách theo hướng mong muốn. CTDL này được gọi là danh sách liên kết kép doubly linked list.template class Node_entry struct Node {Các thuộc tính Node_entry entry;NodeNode_entry next; NodeNode_entry back;constructors Node;NodeNode_entry, NodeNode_entry link_back = NULL, NodeNode_entry link_next = NULL;};Constructor cho Node của danh sách liên kết kép gần giống constructor cho Nodecủa danh sách liên kết đơn. Dưới đây là đặc tả cho lớp danh sách liên kết kép:Hình 4.3- Danh sách liên kết kép.Giáo trình Cấu trúc dữ liệu và Giải thuật64template class Entry class List {public: Các phương thức thông thường của danh sách.C ác phương thức bảo đảm tính an toàn cho CTDL có thuộc tính con trỏ.protected: Các thuộc tínhint count; mutable int current_position;mutable NodeEntry current;Hàm phụ trợ để tìm đến một phần tử trong danh sách void set_positionint position const;};Trong cách hiện thực này chúng ta chỉ cần giữ một con trỏ tham chiếu đến một phần tử nào đó trong danh sách là chúng ta có thể duyệt danh sách theohướng này hoặc hướng kia. Như vậy, chúng ta dùng luôn con trỏ current chỉ đến phần tử hiện tại để làm nhiệm vụ này, và chúng ta không cần giữ con trỏ chỉ đếnđầu hoặc cuối danh sách.

4.3.4.2. Các tác vụ trên danh sách liên kết kép

Trong danh sách liên kết kép, việc duyệt danh sách theo cả hai hướng để tìm một phần tử, việc thêm hoặc loại phần tử tại vò trí nào đó có thể được thực hiệndễ dàng. Một vài tác vụ có thay đổi chút ít so với danh sách liên kết đơn, như insertvà delete, do phải cập nhật đầy đủ cả hai con trỏ theo hai hướng của danh sách .Trước hết, để tìm một vò trí nào đó, chúng ta chỉ cần quyết đònh nên duyệt theo hướng nào trong danh sách bắt đầu từ con trỏ current.template class Entry void ListEntry::set_positionint position constpre: position hợp lệ: 0 = position count.post: thuộc tính current chứa đòa chỉ của phần tử tại position.{ if current_position = positionfor ; current_position = position; current_position++ current = current-next;else for ; current_position = position; current_position--current = current-back; }Với hàm này chúng ta viết tác vụ insert sau đây. Hình 4.4 minh họa các con trỏ cần phải cập nhật. Chúng ta cũng đặc biệt chú ý hai trường hợp hơi đặc biệt,Giáo trình Cấu trúc dữ liệu và Giải thuật65 đó là khi thêm phần tử vào một trong hai đầu của danh sách hoặc thêm vào mộtdanh sách rỗng.template class Entry ErrorCode ListEntry::insertint position, const Entry xpost: Nếu danh sách chưa đầy và 0 ≤ position ≤ n, n là số phần tử hiện có của danh sách,phương thức trả về success: mọi phần tử từ position đến cuối danh sách sẽ có vò trí tăng lên 1, x được thêm vào tại position; ngược lại, danh sách không đổi, ErrorCode sẽcho biết lỗi cụ thể.{ NodeEntry new_node, following, preceding;if position 0 || position count return range_error; if position == 0 {if count == 0 following = NULL;Trường hợp đặc biệt: danh sách đang rỗng.else { set_position0;following = current; }preceding = NULL;Trường hợp đặc biệt: thêm phần tử mới vào đầu danh sách, không có phần tửđứng trước. }else { set_positionposition - 1;preceding = current;following = preceding-next; Trường hợp tổng quát: thêm phần tửvào giữa, nhưng gộp cả trường hợp thêm vào cuối position = nfollowing sẽ nhận trò NULL.} new_node = new NodeEntryx, preceding, following;if new_node == NULL return overflow; if preceding = NULL preceding-next = new_node;if following = NULL following-back = new_node; current = new_node;Hình 4.4- Thêm phần tử và danh sách liên kết kép.Giáo trình Cấu trúc dữ liệu và Giải thuật66current_position = position; count++;return success; }Giá phải trả đối với danh sách liên kết kép là vùng nhớ cho tham chiếu thứhai trong mỗi Node. Với phần lớn ứng dụng, do vùng entry cần chứa thông tin trong Node lớn hơn nhiều vùng nhớ dành cho các con trỏ, nên tổng dung lượng bộnhớ tăng không đáng kể.

4.4. So sánh các cách hiện thực của danh sách

Xem Thêm

Tài liệu liên quan

• Giáo trình cấu trúc dữ liệu và giải thuật
  • 426
  • 3,717
  • 59

Tải bản đầy đủ (.pdf) (426 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(2.6 MB) - Giáo trình cấu trúc dữ liệu và giải thuật-426 (trang) Tải bản đầy đủ ngay ×