HOWTO · C++
C++ でリンクリストを並べ替える
このプログラミングチュートリアルでは、C++ のリンクリストデータ構造での並べ替え操作の実装について説明します。
このページの内容
この簡単なプログラミングチュートリアルは、C++ のリンクリストデータ構造での並べ替え操作の実装を示しています。
C++ でのリスト
リストまたはリンクリストは、データコンテナとして機能し、データをメモリに格納できる線形データ構造です。ベクトルや配列とは異なり、リスト内のデータは連続したメモリ位置を必要としません。代わりに、データを動的に拡張して、任意のヒープメモリ位置に割り当てることができます。
リスト内の各要素はノードと呼ばれます。リスト内の各ノードには、リストの次のノードを指すポインターが含まれています。
各ノードに次の要素へのポインタを含めると、前のノードを介してすべての次の要素にアクセスできる線形チェーンが容易になります。ノード間のこの線形チェーンは、この構造にリンクリストの名前を付ける主な理由です。
リンクリストでは、挿入、削除、検索、さらには並べ替えなど、いくつかの ADT（抽象データタイプ）操作を実行できます。リンクリストの基本的な構造の実装から始めて、そのクラスに並べ替えアルゴリズムを実装します。
C++ でリンクリストを実装する
次に、リンクリストの実装を開始します。そのためには、まず、次のようなノードのクラスを作成する必要があります。
template <class T>
class Node {
public:
T data;
Node<T>* next;
Node() { next = 0; }
};
このクラスには 2つのメンバーがあり、1つはデータ、つまり info を格納するためのもので、もう 1つは次のノードのアドレスを格納するためのクラスのポインターです。クラスはテンプレート化されているため、任意のデータタイプのリストを作成できます。
次に、次のようなリンクリストクラスを作成します。
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
void insertAtHead(T val) {
Node<T>* x = new Node<T>(val);
x->next = head;
head = x;
}
void displayAll() {
Node<T>* x = head;
{
while (x != 0) {
cout << x->info << endl;
x = x->next;
}
}
}
};
このクラスには、リストノードを挿入および表示するためのコンストラクターと他の 2つのメンバー関数があります。
C++ でリンクリストを並べ替える
リンクリストを昇順で並べ替えるために、最も単純な並べ替えアルゴリズムであるバブル並べ替えを実装します。この並べ替えアルゴリズムは、並べ替えられていない順序で配置されている場合、隣接する要素を繰り返し交換します。
この操作は、すべての要素が正しいソート位置になるまで繰り返し実行されます。これは次のように実装されます。
-
後で使用するために新しいノード
tempを作成し、headをcurrノードにします。 -
headが NULL の場合に戻ります。 -
それ以外の場合は、
endノードに到達するまでループを作成します（つまり、NULL）。 -
手順 5〜6 は、繰り返しごとに繰り返す必要があります。
-
tempに、currノードの次のノードを保存します。 -
currノードのデータが次のノードのデータよりも大きいかどうかを確認します。大きい場合は、currとtempを入れ替えます。
void sortLinkedList() {
Node<T> *curr = head, *temp = NULL;
int t;
if (head == NULL) {
return;
} else {
while (curr != NULL) {
temp = curr->next;
while (temp != NULL) {
if (curr->info > temp->info) {
t = curr->info;
curr->info = temp->info;
temp->info = t;
}
temp = temp->next;
}
curr = curr->next;
}
}
}
ドライバープログラムは次のようになります。
int main() {
LSLL<int> list;
list.insertAtHead(50);
list.insertAtHead(45);
list.insertAtHead(16);
cout << "Before sorting" << endl;
list.displayAll();
cout << "After Sorting: " << endl;
list.sortLinkedList();
list.displayAll();
return 0;
}
出力：
Before sorting
43
65
13
After Sorting:
13
43
65
