用 C++ 刪除連結串列中的節點
Jinku Hu
2023年10月12日
本文將討論如何在連結串列 C++ 中實現刪除給定節點的函式的方法。
實現刪除連結串列中給定節點的函式
在本文中，我們從頭開始實現一個單向連結串列，而不使用 STL 中的容器。因此，我們需要定義一些必要的函式來管理連結串列中的節點。
insertNode 元素是建立新連結串列需要呼叫的核心函式。由於我們需要儲存列表的頭部，insertNode 返回指向 ListNode 型別節點的指標。後者是連結串列節點的最小表示。它只包含一個指向下一個節點的指標和 string 資料物件。
在程式的測試和演示過程中，重要的是要有一些實用函式來向使用者控制檯顯示一些訊息。在這種情況下，printNodes 元素用於列印給定列表結構中的所有節點。此外，在動態記憶體上分配新節點時，我們需要使用 freeNodes 函式在程式退出時釋放列表中的每個現有節點。
一旦我們構建了一個包含任意資料的列表，如以下程式碼片段的 main 函式所示，我們就可以呼叫 deleteNode，它實現節點刪除操作。節點的移除需要在其中處理幾個極端情況。即，當給定節點與列表的頭部相同時的場景，當給定節點是列表中的唯一節點時的另一個場景。
在後一種情況下，我們可以在節點指標上呼叫 delete 運算子並從函式返回。儘管將 nullptr 分配給地址很重要，因為這將幫助我們將新元素新增到 main 函式中的同一個 head 變數中。
另一方面，當連結串列中還有其他節點時，移除頭節點是比較棘手的。我們必須將第二個節點的內容複製到頭節點並刪除前一個。請注意，每個案例都返回 EXIT_SUCCESS 值以指示成功的函式呼叫。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
其餘的函式程式碼實現了常規情況，其中給定節點從列表鏈中解開，然後使用 delete 運算子解除分配。但是請注意，此操作需要找到前一個節點，這是對除列表頭部之外的每個節點的線性時間操作。通常，為了保證連結串列末尾的恆定時間移除，應該將連結串列的末尾儲存在連結串列結構中。
下面的程式碼片段演示了一個不同的 main 函式場景，其中從列表中間刪除了一個節點。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
-----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
作者： Jinku Hu
