在 C++ 中反轉連結串列
本文將演示如何在 C++ 中反轉連結串列資料結構。
C++ 中使用迭代函式反轉連結串列
我們假設目標物件是一個單向連結串列並相應地實現程式碼片段。首先，我們需要檢視為演示示例而實現的驅動程式程式碼中的基本功能實用程式。
連結串列節點是一個簡單的 struct，帶有一個 string 資料物件和一個指向下一個節點的指標。我們還有 addNewNode 函式，它接受兩個引數，Node* 和對 string 的引用。在 main 例程中多次呼叫 addNewNode 函式以構造一個新的列表物件並儲存來自 data_set 向量的字串。該函式在動態記憶體上分配每個節點並返回指向新建立節點的指標。
我們的連結串列資料結構的另一個有用函式是 printNodes，它用於將資料從每個節點輸出到 cout 流。後一個將幫助我們粗略地驗證反轉函式的正確性。請注意，printNodes 在列表遍歷期間保持節點數並列印每個元素的索引。最後，我們需要在程式退出之前釋放所有節點。這一步對於反轉函式演示不是必需的，但對於任何實際專案來說，清理執行時分配的所有記憶體都很重要。
#include<iostream>
#include<string>
#include<vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node)
node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node){
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = { "Rocket Lake", "Alder Lake",
"Tiger Lake", "Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
一旦我們初始化了一個新的連結串列並將連結串列的頭部儲存在一個單獨的指標中，我們就可以使用它來反轉內容。在這種情況下，我們實現了 reverseList 函式，它接受單個 Node* 引數並返回一個新的根節點。首先，我們複製傳遞的指標並將其儲存為 head 變數。我們還需要兩個額外的 Node 型別指標在 while 迴圈期間進行內部簿記。
反轉演算法可以描述如下：我們將下一個節點指標儲存在一個臨時變數（next）中，並將 nullptr 值分配給原始變數。因此，原始 head 節點將指向 nullptr 作為其在列表中的下一個節點。接下來，我們更新 head 變數以儲存原始列表中的下一個（第二個）節點，並將原始頭節點的地址儲存在一個單獨的臨時變數中。
我們重複前面的步驟，直到 head 指標的計算結果為 nullptr，這意味著到達列表的末尾。最後，我們返回儲存在 n 臨時變數中的新頭節點的地址。因此，main 程式呼叫 printNodes 函式供使用者比較修改後的連結串列內容。
#include<iostream>
#include<string>
#include<vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node)
node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node){
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
Node *reverseList(struct Node *node) {
auto head = node;
Node *n = nullptr;
Node *next = nullptr;
while (head){
next = head->next;
head->next = n;
n = head;
head = next;
}
return n;
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = { "Rocket Lake", "Alder Lake",
"Tiger Lake", "Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
printNodes(reverseList(head));
freeNodes(head);
return EXIT_SUCCESS;
}
輸出：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
-----------------------------------
node 0 - data: Meteor Lake
node 1 - data: Tiger Lake
node 2 - data: Alder Lake
node 3 - data: Rocket Lake
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