C++ でリンクリストを逆にする
この記事では、C++ でリンクリストのデータ構造を逆にする方法を説明します。
C++ で反復関数を使用してリンクリストを逆にする
ターゲットオブジェクトが単一リンクリストであると想定し、それに応じてコードスニペットを実装します。最初に、例を示すために実装されたドライバーコードの基本的な関数ユーティリティを確認する必要があります。
リンクリストノードは、単一の文字列データオブジェクトと次のノードへのポインタを持つ単純な構造体です。また、Node*と string への参照という 2つの引数を取る addNewNode 関数もあります。addNewNode 関数は、main ルーチンで複数回呼び出され、新しいリストオブジェクトを作成し、data_set ベクトルから文字列を格納します。この関数は、動的メモリに各ノードを割り当て、新しく作成されたノードへのポインタを返します。
リンクリストデータ構造のもう 1つの便利な関数は、printNodes です。これは、すべてのノードから cout ストリームにデータを出力するために使用されます。後者は、反転関数の正しさを大まかに検証するのに役立ちます。printNodes は、リストの走査中にノードの数を保持し、各要素のインデックスを出力することに注意してください。最後に、プログラムが終了する前に、すべてのノードの割り当てを解除する必要があります。この手順は、反転機能のデモンストレーションには必要ありませんが、実際のプロジェクトでは、実行時に割り当てられたすべてのメモリをクリーンアップすることが重要です。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
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
新しいリンクリストを初期化し、リストの先頭を別のポインタに格納したら、それを使用して内容を逆にすることができます。この場合、単一の Node*引数を受け入れ、新しいルートノードを返す reverseList 関数を実装しました。最初に、渡されたポインタを複製し、それを head 変数として格納します。また、while ループ中に内部の簿記を行うために、2つの追加の Node タイプのポインターが必要です。
反転アルゴリズムは次のように説明できます。次のノードポインタを一時変数（next）に格納し、nullptr 値を元の値に割り当てます。その結果、元の head ノードは、リスト内の次のノードとして nullptr を指します。次に、head 変数を更新して、次の（2 番目の）ノードを元のリストに格納し、元のヘッドノードのアドレスを別の一時変数に保存します。
head ポインタが nullptr と評価されるまで、前の手順を繰り返します。これは、リストの最後に到達したことを意味します。最後に、n 一時変数に格納されている新しいヘッドノードのアドレスを返します。その結果、main プログラムは、ユーザーが変更されたリンクリストの内容を比較するために printNodes 関数を呼び出します。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
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
