まず、連結リストの定義と基本的な操作について説明します。連結リストはノードの集合体であり、各ノードはデータ部とポインタ部から構成されています。ポインタ部は次のノードを指すポインタを持っており、最後のノードのポインタはNULLになります。
逆順化のアルゴリズムは、スタックを使用して実装できます。以下に逆順化の手順を示します。
- 空のスタックを作成します。
- 連結リストを先頭から順に辿りながら、各ノードをスタックにプッシュします。
- 連結リストの末尾に到達したら、スタックからポップして新しい連結リストを作成します。ポップしたノードは新しい連結リストの先頭ノードとなります。
- スタックが空になるまで、スタックからノードをポップして新しい連結リストの次のノードとして追加します。
- 新しい連結リストを出力します。
以下に、上記のアルゴリズムをC言語で実装したコード例を示します。
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// スタックの要素を表す構造体
struct Stack {
struct Node* top;
};
// スタックの初期化
void initialize(struct Stack* stack) {
stack->top = NULL;
}
// スタックが空かどうかを判定する
int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}
// スタックに要素を追加する
void push(struct Stack* stack, struct Node* node) {
node->next = stack->top;
stack->top = node;
}
// スタックから要素を取り出す
struct Node* pop(struct Stack* stack) {
if (isEmpty(stack)) {
return NULL;
}
struct Node* poppedNode = stack->top;
stack->top = stack->top->next;
poppedNode->next = NULL;
return poppedNode;
}
// 連結リストを逆順化する
struct Node* reverseLinkedList(struct Node* head) {
struct Stack stack;
initialize(&stack);
// 連結リストをスタックにプッシュする
struct Node* currentNode = head;
while (currentNode != NULL) {
push(&stack, currentNode);
currentNode = currentNode->next;
}
// スタックからポップして新しい連結リストを作成する
struct Node* newHead = pop(&stack);
currentNode = newHead;
while (!isEmpty(&stack)) {
currentNode->next = pop(&stack);
currentNode = currentNode->next;
}
return newHead;
}
// 連結リストを表示する
void printLinkedList(struct Node* head) {
struct Node* currentNode = head;
while (currentNode != NULL) {
printf("%d ", currentNode->data);
currentNode = currentNode->next;
}
printf("\n");
}
int main() {
// 連結リストの作成
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printf("Original linked list: ");
printLinkedList(head);
// 連結リストを逆順にする
struct Node* reversedHead = reverseLinkedList(head);
printf("Reversed linked list: ");
printLinkedList(reversedHead);
// メモリの解放
free(head);
free(second);
free(third);
return 0;
}上記のコードでは、initialize関数でスタックを初期化し、isEmpty関数でスタックが空かどうかを判定します。push関数ではスタックに要素を追加し、pop関数ではスタックから要素を取り出します。reverseLinkedList関数では連結リストを逆順化し、新しい連結リストの先頭ノードを返します。printLinkedList関数では連結リストの内容を表示します。
このコードを実行すると、連結リストが逆順になった結果が表示されます。連結リストの逆順化はスタックを使用することでシンプルに実装できます。