C言語における自己参照構造

こんにちは、未来のプログラミング魔術師たち!今日は、C言語における自己参照構造の世界への興奮的な旅に出発します。その名前が少し脅威のように聞こえるかもしれませんが、心配しないでください。私たちはそれをバイトサイズのチャンクに分解し、私の祖母でも理解できるようにします(そして、彼女はまだマウスを小さな毛皮動物だと思っています)。

C - Self-Referential Structures

自己参照構造とは?

パーティーで友達を誰かに紹介するとき、あなたはこう言うかもしれません。「これは私の友達のアレックスで、アレックスもソフトウェア開発者です。」この紹介では、アレックスに二度参照しています。一度は名前で、もう一度は職業でです。これがC言語における自己参照構造の動作に似ています!

自己参照構造は、その定義内に同じ型の構造体へのポインタを含む構造体です。ロシアのナショナルドールのように、中に小さなドールがあるのではなく、同じ型の構造体が全部の段階にあります。

自己参照構造の定義

これらの興味深い構造体を実際にどのように定義するかを見てみましょう。以下は簡単な例です:

struct Node {
int data;
struct Node* next;
};

この例では、Nodeという構造体を定義しています。それには以下の2つのメンバーがあります:

  1. 情報を保存するための整数data
  2. 他のNode構造体を指すポインタnext

これが自己参照構造の本質です。それは自分自身をその定義内で参照します。

自己参照構造の例

では、自己参照構造を実際にどこで使うかの具体的な例を見てみましょう。

1. リンクリストのノード

これをすでに見てきましたが、さらに詳しく見てみましょう:

struct ListNode {
int data;
struct ListNode* next;
};

この構造体はリンクリストを作成するのに最適です。各ノードにはデータとリストの次のノードを指すポインタがあります。

2. 木のノード

木も自己参照構造の一般的な使用例です:

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

ここでは、木の各ノードは最大で2つの子供(左と右)を持つことができます。

3. グラフのノード

冒険心が強いあなたたち向けに、グラフのノードを表す方法を示します:

struct GraphNode {
int data;
struct GraphNode** neighbors;
int neighborCount;
};

この場合、他のGraphNode構造体へのポインタの配列を持ち、グラフ内の接続を表現しています。

自己参照構造を使ったリンクリストの作成

基本を理解したので、自己参照構造を使って簡単なリンクリストを作成してみましょう。すぐに全てを理解できない場合は、気にしないでください。ローマは一日に建てられませんし、コードのスキルも然りです!

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

// 新しいノードを作成する関数
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// リンクリストを印刷する関数
void printList(struct Node* head) {
struct Node* current = head;
printf("%d -> ", current->data);
current = current->next;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);

printf("私たちのリンクリスト: ");
printList(head);

return 0;
}

以下のように分解します:

  1. Node構造体を先ほどと同じように定義します。
  2. createNode関数を作成し、新しいノードを割り当てて初期化します。
  3. printList関数を作成し、リストを巡回して各ノードのデータを印刷します。
  4. main関数で、3つのノードを持つリンクリストを作成し、印刷します。

このプログラムを実行すると以下のように表示されます:

私たちのリンクリスト: 1 -> 2 -> 3 -> NULL

自己参照構造を使った二重リンクリストの作成

次に、レベルアップして二重リンクリストを作成してみましょう。これは通常のリンクリストと似ていますが、各ノードには前のノードを指すポインタもあります。一方通行の道ではなく、双方通行の道のようになります!

#include <stdio.h>
#include <stdlib.h>

struct DoubleNode {
int data;
struct DoubleNode* next;
struct DoubleNode* prev;
};

// 新しいノードを作成する関数
struct DoubleNode* createDoubleNode(int data) {
struct DoubleNode* newNode = (struct DoubleNode*)malloc(sizeof(struct DoubleNode));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// 前方に印刷する関数
void printForward(struct DoubleNode* head) {
struct DoubleNode* current = head;
printf("前方: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// 後方に印刷する関数
void printBackward(struct DoubleNode* tail) {
struct DoubleNode* current = tail;
printf("后方: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->prev;
}
printf("NULL\n");
}

int main() {
struct DoubleNode* head = createDoubleNode(1);
head->next = createDoubleNode(2);
head->next->prev = head;
head->next->next = createDoubleNode(3);
head->next->next->prev = head->next;

struct DoubleNode* tail = head->next->next;

printForward(head);
printBackward(tail);

return 0;
}

この例では:

  1. DoubleNode構造体にはnextprevのポインタが含まれています。
  2. 前方と後方に印刷する関数を作成します。
  3. main関数で、二重リンクリストを作成し、ポインタを設定します。

このプログラムを実行すると以下のように表示されます:

前方: 1 <-> 2 <-> 3 <-> NULL
後方: 3 <-> 2 <-> 1 <-> NULL

自己参照構造を使った木の作成

最後に、自己参照構造を使って簡単な二分木を作成してみましょう。これを家族の系図として考えると、各人物は最大で2人の子供を持つことができます。

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

// 新しいノードを作成する関数
struct TreeNode* createTreeNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// 中間順巡回を行う関数
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

int main() {
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);

printf("木の中間順巡回: ");
inOrderTraversal(root);
printf("\n");

return 0;
}

この最後の例では:

  1. TreeNode構造体にはleftrightのポインタが含まれています。
  2. 中間順巡回を行う関数を作成します。
  3. main関数で、簡単な二分木を作成し、中間順巡回を行います。

このプログラムを実行すると以下のように表示されます:

木の中間順巡回: 4 2 5 1 3

そして、皆さん!私たちは自己参照構造の世界を旅しました。シンプルなリンクリストから二重リンクリスト乃至於は二分木までです。練習が完璧にするものだと思い、これらの構造体を自由に実験し、自分独自のバージョンを作成してみてください。誰かが次に革新的なデータ構造を発明するかもしれない的就是あなたかもしれません!

ハッピーコーディング、そして自己参照構造があなたと共にありますように!

Credits: Image by storyset