在 C++ 中實現迴圈連結列表的資料結構
本文將講解如何用 C++ 實現一個迴圈連結串列資料結構。
在 C++ 中用成員函式實現迴圈單連結串列，在末端新增新元素並列印元素
迴圈連結串列可以表徵為一個連結串列，其中最後一個節點指向連結串列的頭部。本質上，列表中的節點形成一個圓圈，並且沒有 nullptr 來劃分列表的末尾。你可以利用迴圈連結串列來構建佇列樣式的資料結構。迴圈特徵可以新增到雙向連結串列和單連結串列中。
在這種情況下，我們將實現後一個。請記住，我們需要定義一個節點結構，其中包含一個指向下一個節點的指標和一個資料元素來構造一個單向連結串列。struct ListNode 物件代表我們實現的單個節點，並儲存名為 data 的單個 string 物件，該物件將用作本示例的元素資料。請注意，可以在節點中儲存任何自定義物件，如果物件相對較大，最好將其包含為指標。
一旦我們有了單個節點的結構，我們就可以定義一個 CircularList 類，它只有兩個用於初學者的成員函式。通常，迴圈連結串列應該跟蹤連結串列的頭部或尾部；然而，實現者通常可以根據他們的需要自由地做出類設計決策。此外，CircularList 類儲存兩個單獨的指標來表示列表的頭部和結尾。
儲存列表頭/尾的指標可以是一個虛擬節點，也可以是一個帶有資料的實際節點。在這個例子中，我們選擇將 CircularList 類設計為沒有虛擬指標。我們定義了一個建構函式來接受一個 string 引數來初始化迴圈列表中的第一個節點。請注意，類定義期間的設計選擇通常會影響不同的變數，應根據潛在問題進行考慮。因此，下面的實現只是為了解釋迴圈連結串列的概念的簡單實現。
一旦使用建構函式初始化 CircularList 物件，我們就可以使用 insertNodeEnd 成員函式新增新元素。後者接受 string 引數並在列表末尾構造一個新元素。insertNodeEnd 函式使用 new 運算子分配新元素並相應地修改指標以在列表末尾插入節點。它還更新 end 資料成員以指向新分配的節點。
下一個示例中定義的另一個成員函式是 printNodes，它遍歷列表以列印其內容，並且不接受任何引數。現在，為了更好地演示這個結構的用法，我們需要在 main 函式中新增一些驅動程式程式碼。我們選擇初始化任意字串的 vector，然後使用 for 迴圈將其插入到 CircularList 物件中。最後，我們呼叫 printNodes 函式將列表內容顯示到終端。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
void printNodes();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
C++ 中實現在 List 開頭插入新元素的解構函式和成員函式
請注意，前面的程式碼片段有一個巨大的問題，即沒有定義解構函式；這意味著使用 CircularList 類的程式將洩漏記憶體，因為在程式退出之前不會釋放在動態記憶體上建立的節點。
這個問題的解決方案是實現一個解構函式，該解構函式將遍歷整個列表並使用 delete 運算子解除分配所有節點。因此，我們無需擔心手動釋放列表記憶體。一旦 CircularList 物件到達作用域末尾，它將被自動釋放。
另一個要實現的有用函式是在列表的頭部插入一個新元素； insertNodeHead 命令就是為了做到這一點而設計的。它只需要儲存一個 string 引數並返回指向新分配節點的指標。請注意，insertNodeEnd 和 insertNodeHead 函式的返回值是另一種設計選擇，其實現方式因程式設計師的決定而異。以下程式碼片段在 main 函式中包含類似的驅動程式程式碼，以測試和展示 CircularList 類的用法。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
head = end->next;
return new_node;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.insertNodeEnd("Zeisty");
clist.printNodes();
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Xenial
node 2 - data: Precise
node 3 - data: Quantal
node 4 - data: Saucy
node 5 - data: Raring
node 6 - data: Zeisty
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn