第34章 リスト構造  


今回は、前回のメモリの動的確保と、構造体の 少し進んだ使い方の解説です。と、言ってもこれも どんな入門書にも必ず出ているものです。じっくり読めば 必ずわかります。ここで、構造体に関して1つ重要な ことを追加します。

構造体は、自分自身と同じ型の構造体へのポインタを メンバに持つことができます!

突然そんなこと言われても・・・・

と、お思いのあなたにこの例を示します。案ずるより 例を見た方がはやいでしょう。

struct list { int age; char name[32]; struct list *nextlist; //自分自身と同じ構造体へのポインタ };

こういう構造体を自己参照構造体(self-referential structure)といいます。

書き方は、わかったけどこんなものどうするの?

はい。では例によってサンプルプログラムを作ってみましょう。

#include <stdio.h> #include <stdlib.h> #include <string.h> struct list { int num_data; struct list *nextlist; }; int main() { struct list *a, *b; char str[16]; b = NULL; printf("整数を入力(Eで終了)-->"); scanf("%s", str); while(1) { if(strcmp(str, "E") != 0)     //strcmpは文字列の比較 a = (struct list *)malloc(sizeof(struct list)); else break; a->num_data = atoi(str);  //atoiは文字列をint型に変換する a->nextlist = b;  b = a; printf("整数を入力(Eで終了)-->"); scanf("%s", str); } printf("入力された整数は"); a = b; while (1) { if (a == NULL) break; printf("%d, ", a->num_data); a = a->nextlist; } return 0; }

上のプログラムの意味がおわかりいただけたでしょうか。 最初に整数を1個入力します。すると最初のwhileループの中で 入力されたものが「E」でないために、list型構造体の大きさ分だけ 動的にメモリが確保されます。このアドレスがポインタaに代入されます。 次に、入力されたデータを構造体メンバに代入します。 そして、nextlistメンバにbを代入します。従って最初の構造体の nextlistメンバにはNULLが入っています。そして、aをbに 代入します。bには、今値を代入した構造体のアドレスが入っています。 そして、もう一度入力を促します。そうするとループの最初に戻ります。 また、aに新しく確保したメモリのアドレスが入ります。新しいデータを メンバに代入します。・・・を繰り返します。従ってbには、最後から 2番目にデータを代入した構造体のアドレスが入っています。

次に「E」が入力されると、最初のwhileループを抜けます。 そして、bをaに代入します。aには最後の代入を行った構造体のアドレスが 入ります。そして2番目のループに入ります。 そして、最後の構造体のデータを表示します。次に、aにnextlistの値を 代入します。すなわちaには一つ前の構造体のアドレスが代入されます。 また、ループの最初に戻って今度は1つ前の構造体のデータを表示します。 次にnextlistの値をaに代入します。・・・を繰り返します。最初の 構造体まで行ったらaにNULLが代入されますのでループを抜け プログラムを終了します。

ややっこやしいのですが、おわかりいただけたでしょうか。 では、実行結果を見てみましょう。いや、その前に上のプログラムでは 省略されていることがあります。それは何でしょうか?実はmalloc関数 が失敗したときの対策が書かれていません。メモリ確保のプログラムでは 必ず確保に失敗したときの対策を書いておいてください。

表示は、入力されたのとは逆の順序ですね。

もう一度確保された構造体に何が入っているのかをまとめます。

最初の構造体
nextlist・・・NULL

2番目の構造体
nextlist・・・最初の構造体のアドレス

3番目の構造体
nextlist・・・2番目の構造体のアドレス

という具合になっています。具体的にアドレスを表示するよう にプログラムを書き換えてみるとわかりやすいかもしれません。 上のプログラムをいろいろ作り替えて研究してみてください。 このような、データ構造のことをリスト構造といいます。 また、この例のように1方向に構造体がつながって見える?リスト 構造を線形リスト(linear list)といいます。さらに、ここでいう それぞれの構造体をノード(node)と呼んだりする事もあります。 リスト構造については、まだまだやらなくてはいけないことが 山のようにありますが、超初心者の範囲を超えるので初心者に なってから参考書などで勉強してください。初心者への道はまだまだ 遠く険しいですね。でも、「猫でもわかる」式にやっていきますので 心配はいりません。


[Index][総合Index] [Previous Chapter] [Next Chapter]

Update Nov/28/1996 By Y.Kumei
当ホーム・ページの一部または全部を無断で複写、複製、 転載あるいはコンピュータ等のファイルに保存することを禁じます。