Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách xóa tất cả các nút chính khỏi danh sách được liên kết kép.
Hãy xem các bước để giải quyết vấn đề.
-
Viết cấu trúc với dữ liệu, con trỏ trước và tiếp theo.
-
Viết một hàm để chèn nút vào danh sách được liên kết kép.
-
Khởi tạo danh sách được liên kết kép với dữ liệu giả.
-
Lặp lại danh sách được liên kết kép. Tìm xem dữ liệu nút hiện tại có nhỏ hơn giá trị đã cho hay không.
-
Nếu dữ liệu hiện tại nhỏ hơn giá trị đã cho, hãy xóa nút.
-
Viết hàm xóa nút. Hãy xem xét ba trường hợp sau khi xóa nút.
-
Nếu nút là nút đầu, thì hãy chuyển phần đầu sang nút tiếp theo.
-
Nếu nút là nút giữa, thì hãy liên kết nút tiếp theo với nút trước đó
-
Nếu nút là nút kết thúc, hãy xóa liên kết nút trước đó.
-
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *prev, *next;
};
void insertNode(Node** head_ref, int new_data) {
Node* new_node = (Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL) {
(*head_ref)->prev = new_node;
}
(*head_ref) = new_node;
}
void deleteNode(Node** head_ref, Node* del) {
if (*head_ref == NULL || del == NULL) {
return;
}
if (*head_ref == del) {
*head_ref = del->next;
}
if (del->next != NULL) {
del->next->prev = del->prev;
}
if (del->prev != NULL) {
del->prev->next = del->next;
}
free(del);
return;
}
void deleteSmallerNodes(Node** head_ref, int K) {
Node* temp = *head_ref;
Node* next;
while (temp != NULL) {
next = temp->next;
if (temp->data < K) {
deleteNode(head_ref, temp);
}
temp = next;
}
}
void printLinkedList(Node* head) {
while (head != NULL) {
cout << head->data << " -> ";
head = head->next;
}
}
int main() {
Node* head = NULL;
insertNode(&head, 1);
insertNode(&head, 2);
insertNode(&head, 3);
insertNode(&head, 4);
insertNode(&head, 10);
insertNode(&head, 11);
insertNode(&head, 12);
int K = 10;
cout << "Linked List before deletion:" << endl;
printLinkedList(head);
deleteSmallerNodes(&head, K);
cout << "\nLinked List after deletion:" << endl;
printLinkedList(head);
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
Linked List before deletion: 12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 -> Linked List after deletion: 12 -> 11 -> 10 ->
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.