C++ 中的迴圈雙向連結串列
Jinku Hu
2023年10月12日
本文將演示如何在 C++ 中實現迴圈雙向連結串列。
C++ 中從頭開始的迴圈雙向連結串列資料結構
雙向連結串列是一種資料結構，其中每個節點都儲存指向下一個和前一個節點的指標。這使其成為實現 std::deque 類容器的最佳選擇。最好製作一個雙向連結串列迴圈，以便最後一個節點的 next 成員指向列表的開頭，第一個節點也指向最後一個節點作為它的前一個節點。
首先，我們需要宣告一個名為 ListNode 的 struct，用於構造一個列表。接下來，我們定義一個 CircularList 類，其中包含兩個型別為 ListNode* 的資料成員和三個成員函式。
請注意，我們決定只包含一個接受 string 值並初始化第一個節點的建構函式，但這部分可以根據程式設計師的需要進行修改。兩個資料成員 - head 和 end - 儲存第一個和最後一個節點。我們還有單獨的函式來在列表的每一側新增元素。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
struct ListNode *prev = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->prev = 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 = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
end = end->next;
return end;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
head = new_node;
return head;
}
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() {
CircularList clist("Xenial");
clist.insertNodeHead("Saucy");
clist.insertNodeEnd("Quantal");
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.printNodes();
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
-----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal
元素插入的一般演算法需要分配一個新的 ListNode 物件，將相應的節點指標分配給其成員，然後根據需要修改 head/end 成員。我們還包括一個 printNodes 函式來顯示列表內容，因為我們可能需要檢查程式碼的正確性。請注意，在列表物件超出範圍後，一定不要忘記釋放所有記憶體。後一個函式是作為解構函式實現的。
作者： Jinku Hu
