Bài tập danh sách liên kết đôi C++
Danh sách liên kết képTrongbài trước về danh sách liên kết đơn đã đề cập, nó có điểm yếu là chỉ có liên kết tới node kế tiếp mà không có liên kết tới node đứng trước. Do vậy ta luôn phải duyệt toàn bộ danh sách từ node gốc để tìm kiếm dữ liệu tai một vị trí bất kì. Show
Một node trong danh sách liên kết kép được cấu thành từ ba thành phần là dữ liệu và phần kết nối tới node kế tiếp và node trước nó.
Prev: Là con trỏ tới node trước. Next: Là con trỏ tới node kế tiếp. Xây dựng danh sách liên kết kép bởi liên kết các node với nhau.
Việc chèn dữ liệu trong danh sách liên kết képGiả sử trước khi chèn dữ liệu ta có một node riêng biệt và một danh sách liên kết kép.
Trường hợp ta muốn chèn vào vị trí giữa danh sách liên kết ở trên sẽ được mô tả như sau:
So sánh với danh sách liên kết đơnƯu điểm:
Nhược điểm:
Xây dựng danh sách liên kết kép với C/C++Các thành phần của danh sách liên kết kép bao gồm:
Các thao tác chính với danh sách liên kết kép:
Trong phần này ta có thể tách ra làm hai hàm riêng biệt. Hàm deleteNode : Dùng để xóa một node ra khỏi danh sách với điều kiện là ta đã biết địa chỉ của node cần xóa. Có ba trường hợp cho việc xóa node là: xóa node ở vị trí đầu của danh sách, xóa node ở vị trí cuối của danh sách và xóa node ở vị trí giữa của dah sách. Với việc xóa node ở vị trí đầu, ta chỉ việc chuyển con trỏ head để trỏ vào vị trí kế tiếp của node đầu tiên và giải phóng bộ nhớ đã cấp cho node đầu tiên đó. Để xóa node ở vị trí cuối cùng của danh sách ta duyệt đến vị trí của node đứng ngay trước node cuối cùng, sau đó gán cho con trỏ next của node đó trỏ tới NULL và giải phóng bộ nhớ đã cấp cho node cuối cùng. Việc xóa node ở giữa danh sách phức tạp hơn một chút bao gồm các bước:
Hàm delNodeAtPos: Hàm này được dùng để xóa một node ở một vị trí đã cho trong danh sách. nhiệm vụ của hàm này là tìm ra địa chỉ của node tại vị trí đã cho, sau đó truyền địa chỉ đó vào hàm deleteNode ở trên. Các công việc còn lại sẽ do hàm deleteNode đảm nhiệm. /* Hàm dùng để xóa một node khỏi Doubly Linked List. head_ref : Con trỏ tới head node. del : Con trỏ tới node cần xóa */ void deleteNode(struct node** head_ref, struct node* del) { /* Điều kiện cơ sở, thoát khỏi hàm nếu danh sách rỗng hoặc địa chỉ của node cần xóa là NULL (không xóa node nào) */ if (*head_ref == NULL || del == NULL) return; /* Nếu node cần xóa là head node */ if (*head_ref == del) *head_ref = del->next; /* Thay đổi node kế tiếp chỉ khi node cần xóa không phải node cuối cùng trong danh sách */ if (del->next != NULL) del->next->prev = del->prev; /* Thay đổi node trước chỉ khi node cần xóa không phải node đầu tiên trong danh sách */ if (del->prev != NULL) del->prev->next = del->next; /* Cuối cùng, giải phóng bộ nhớ đã được chiếm giữ bởi del*/ free(del); } /* Hàm để xóa một node ở một vị trí đã cho (int n) trong doubly linked list */ void delNodeAtPos(struct node** head_ref, int n) { /* Thoát khỏi hàm nếu danh sách là rỗng hoặc vị trí truyền vào là không đúng (vị trí âm) */ if (*head_ref == NULL || n <= 0) return; struct node* current = *head_ref; int i; /* Duyệt danh sách từ node đầu tiên cho tới khi gặp node ở vị trí đã cho */ for (int i = 1; current != NULL && i < n; i++) current = current->next; /* Nếu vị trí đã cho lớn hớn số node tối đa của danh sách, ta thoát khỏi hàm */ if (current == NULL) return; /* Thực hiện việc xóa node mà ta đã tìm thấy tại vị trí đã cho */ deleteNode(head_ref, current); }
Ứng dụng của danh sách liên kết kép trong thực tếTa có thể ứng dụng danh sách liên kết kép trong khá nhiều trường hợp, ví dụ:
|