今回は、構造体の応用的な使い方として自己参照構造体について説明していきます。
1.自己参照構造体とは
自己参照構造体とは、自己参照をする構造体のことを言います。
これだと何もわからないと思うので、コードと図を使って説明していきます。
まずはコードから、
|
1 2 3 4 5 6 7 |
typedef struct hogehoge { int hoge; int fuga; struct hogehoge *next; } hogehoge; |
これが自己参照構造体を定義した時のコードになります。
自己参照を図で説明してみました。
いったいどうなっているかというとstruct型があって（大きい長方形）、その中にstruct型のポインタがあります（長方形の中にある正方形）。
つまり、構造体が自身と同じ型のデータへのポインタをメンバとしているということです。
これによってリストなどの再帰的なデータ構造を作る事ができるようになります。
2.リスト構造
自己参照構造体について説明しましたが、
実際に自己参照構造体を使うことによって、リスト構造という、とても重要なデータ構造を実装してみましょう。
リストはリスト構造という仕組みでできていて、リスト構造というのはあるデータをポインタで結んだデータ構造のことを言います。
また、リストには以下の３種類があります。
- 片方向リスト: リストに含まれる各要素（今回の場合は自己参照構造体）をポインタによってつないで実現したリスト。一番最後の要素は次を指すものがないのでNULLを代入しておく。
- 双方向リスト: 前の要素と後の要素へのポインタを持っている。片方向リストでは後の要素にしか辿ることができなかったが、双方向リストは前にも後にも行くことができる。
- 循環リスト: 先頭と末尾がつないてあるリスト。
今回は最も基本的で、簡単に実装することができる片方向リストを紹介します。
片方向リストのソースコード
ソースコードは以下のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <stdio.h>; #include <stdlib.h>; // リストの要素 typedef struct listNode { int hoge; struct listNode *next; } listNode; // リストの最前列に新しい要素を追加してそのアドレスを返す関数 /* hoge: リストの要素 node: いまの要素のアドレス */ listNode *addNode(int hoge, listNode *node) { listNode *new = (listNode*)malloc(sizeof(listNode)); if(new == NULL) exit(1); // メモリ領域が確保できなかった場合はプログラムを終了する new->hoge = hoge; // 新しい要素に入れたい値を入れる new->next = node; // 新しい要素にいまの要素のアドレスを入れる（繋げる） return new; } // リストの要素をプリントする関数 void printList(listNode *node) { while (node != NULL) { printf("%d\n", node->hoge); node = node->next; } } // メイン関数 int main(void) { listNode *node = NULL; //[] node = addNode(5, node); //[5] node = addNode(10, node); //[10,5] node = addNode(7, node); //[7,10,5] printList(node); return 0; } |
・5~8行ではリストを構成するノードを定義しています。int型のhogeはリストを使う際に挿入するデータ、struct listNodeのポインタ型であるnextは次のノードを指すために使われます。
・16~21行はリストにノードを追加する関数を定義しています。
・24~29行はリストの要素をprintf()で標準出力に書き出しています。
