C++ で循環リンクリストデータ構造を実装する
この記事では、C++ で循環リンクリストデータ構造を実装する方法について説明します。
最後に新しい要素を追加し、C++ で要素を出力するために、メンバー関数を使用して循環単一リンクリストを実装する
循環リンクリストは、最後のノードがリストの先頭を指すリンクリストとして特徴付けることができます。基本的に、リスト内のノードは円を形成し、リストの終わりを区切る nullptr はありません。循環リンクリストを利用して、キュースタイルのデータ構造を構築できます。循環機能は、二重リンクリストと単一リンクリストの両方に追加できます。
この場合、後者を実装します。次のノードへのポインタを含むノード構造と、単一リンクリストを作成するためのデータ要素を定義する必要があることに注意してください。struct ListNode オブジェクトは、実装の単一ノードを表し、data という名前の単一の string オブジェクトを格納します。これは、この例の要素データとして機能します。カスタム定義のオブジェクトはノードに格納できます。オブジェクトが比較的大きい場合は、ポインターとして含めることをお勧めします。
単一ノードの構造ができたら、スターター用のメンバー関数が 2つしかない CircularList クラスを定義できます。一般に、循環リンクリストは、リストの先頭または末尾を追跡する必要があります。ただし、実装者は通常、ニーズに基づいてクラス設計を自由に決定できます。さらに、CircularList クラスは、リストの先頭と末尾を表す 2つの別個のポインターを格納します。
リストの先頭/末尾を格納するポインタは、ダミーノードまたはデータを含む実際のノードにすることができます。この例では、ダミーポインタを持たないように CircularList クラスを設計することを選択しました。循環リストの最初のノードを初期化するための string パラメーターを受け入れるコンストラクターを定義しました。クラス定義中の設計の選択は通常、さまざまな変数に影響を与えることに注意してください。これは、根本的な問題に基づいて検討する必要があります。したがって、次の実装は、循環リンクリストの概念を説明するための単純な実装にすぎません。
コンストラクターを使用して CircularList オブジェクトが初期化されたら、insertNodeEnd メンバー関数を使用して新しい要素を追加できます。後者は string パラメーターを受け入れ、リストの最後に新しい要素を作成します。insertNodeEnd 関数は、new 演算子を使用して新しい要素を割り当て、それに応じてポインターを変更して、リストの終わりの直後にノードを挿入します。また、新しく割り当てられたノードを指すように end データメンバーを更新します。
次のサンプルで定義されているもう 1つのメンバー関数は、printNodes です。これは、リストを反復処理してその内容を出力し、引数を取りません。ここで、この構造の使用法をよりよく示すために、main 関数にいくつかのドライバーコードが必要です。後で任意の文字列のベクトルを初期化して、for ループを使用して CircularList オブジェクトに挿入することを選択しました。最後に、printNodes 関数を呼び出して、リストの内容を端末に表示します。
#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;
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++ のリストの先頭に新しい要素を挿入する
前のコードスニペットには、デストラクタが定義されていないという大きな問題があることに注意してください。これは、動的メモリ上に作成されたノードがプログラムが終了するまで解放されないため、CircularList クラスを利用するプログラムがメモリをリークすることを意味します。
この問題の解決策は、リスト全体をトラバースし、delete 演算子を使用してすべてのノードの割り当てを解除するデストラクタを実装することです。したがって、リストメモリを手動で解放することを心配する必要はありません。CircularList オブジェクトがスコープの最後に到達すると、自動的に解放されます。
実装するもう 1つの便利な機能は、リストの先頭に新しい要素を挿入する機能です。insertNodeHead コマンドはまさにそれを行うように設計されています。保存されるのは string 引数のみで、新しく割り当てられたノードへのポインタを返します。insertNodeEnd および insertNodeHead 関数の戻り値は別の設計上の選択であり、プログラマーの決定に応じて異なる方法で実装されることに注意してください。次のコードスニペットには、main 関数に同様のドライバーコードが含まれており、CircularList クラスの使用法をテストして紹介しています。
#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;
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
