自己参照構造体
======================================================================================
構造体のメンバーとして、自分自身の構造体を入れてしまったものが”自己参照構造体”です。
ちょっとややこしくて、理解しにくい（これがすんなり理解できる人は、ＩＱ高いんでしょうね）のですが、
線形リストのプログラムを組むときの肝になりますので、頑張って下さい。
おじさんも、なんとなくこんなもんかなあ理解してから実際使えるようになるまで、結構苦労しました。
A "self-referential structure" is one that includes its own structure
as a member of the structure.
That will be an important point when you make the linear list program.
======================================================================================
１ 自己参照構造体
とりあえず、自己参照構造体てのが何の役にたつか講釈する前に、そやつがいったい何者なのかを
見てみましょう。後ほどサンプルプログラムで使う personal構造体を見てください。
これは、名前と年齢からなるシンプルな構造体ですが、最後に自分自身のpersonal構造体をメンバー
として持っています。
struct person{
char name[30];
int age;
struct person *next;
};
最後のメンバー struct person *next; はpersonal構造体へのポインタです（すなわちpersonal構造体の
先頭アドレス）。従って、nextに次ぎのpersonal構造体のポインタを代入していくことで、構造体を次々に
つなげていくことができるわけです。
例えば、以下のようです。
|<------ |
struct perosnal a name Ken age 18 next b |
| |-----> |<------ |
struct personal b name Jim age 20 next c |
| |-----> |<------ |
struct personal c name Taro age 15 next d |
| |-----> |<------ |
struct personal d name Tom age 15 next e |
なんとなく、自己参照構造体が何者かおわかりいただけたでしょうか。とりあえず、今のところはなんとなくで
いいと思います。ちなみに、このようなデータ構造を線形リストと呼びます。
では、次にこの自己参照構造体がどんな時に役にたつのかを簡単に説明いたします。
自己参照構造体では、上の図表のように構造体を次々とつなげてチェーンを作れるところに特徴があります。
後で説明しますが、このチェーンのつながり（すなわち next にセットするポインタ）を変更することで、チェーンの
順番の入れ替えや削除、追加が柔軟にできます。
例えば、1 -->2-->3-->4-->5 というチェーンがあった時、
順番を入れ替えて、1-->2-->4-->3-->5 にすることも簡単にできますし、
3を削除して1-->2-->4-->5とすることも、
途中に6を追加して、1-->2-->3-->6-->4-->-->5とすることも柔軟にできます。
配列を使用しても同様なことを実現することは不可能ではありませんが、配列と異なり以下のような利点があります。
① データ数を固定しなくてよい（配列ではあらかじめデータ数を固定して宣言しておかねばならない）
－＞すなわち、自己参照構造体を使えばデータの追加、削除が自由にできる
② 挿入、削除、入れ替えが物理的な移動を伴わずにできる。
－＞例えば、x{1],x[2],x[3],x[4],x[5]という配列でx[3],x[4]を入れ替える、x[3]を削除するといった操作をする
となると、配列の中のデータを入れ替えたり、x[3]<-x[4] x[4]<-x[5]
.....というような操作が必要になりますよね
自己参照構造体なら、変更のある構造体のチェーンの部分(next)を変更するだけでいいので、効率が
よくなります。
ただし、特定のデータを検索したい場合、必ずチェーンの最初から１つづつポインタをたどって探していくことに
なるので、データ数が多くなった場合は検索効率は落ちます。
２ 自己参照構造体プログラム例
（１） 基本例
では、自己参照構造体を使って実際にプログラムを作ってみましょう。
まずは、名前と年齢を順次登録し、登録した順に表示するプログラムです。
personal構造体変数として、以下の４つの変数を使っています。
・dmyは初期化用です。
・startは最初のpersonal構造体ですが、このプログラムではstartのデータはstart->nextだけで、name,ageは空です。
・wpは作業用です。
・wkdataは最新のデータ用です。
※以下のプログラムに、start->next, wakdata->name, wkdata->age などという変数が出てきますが、
これは構造体のポインタ変数でその構造体ノメンバを参照する方法です。詳しくは構造体のポインタ変数
#include <stdio.h> #include <stdlib.h> #include <string.h> struct person{ char name[30]; int age; struct person *next; }; main() { struct person dmy; struct person *start=&dmy; struct person *wkdata; struct person *wp; char name[30]=" ",buf[10]; int tosi; start=&dmy; start->next=NULL; wp=start; while(1){ printf("name:"); gets(name); if(strcmp(name,"")==0)break; printf("age:"); gets(buf); tosi=atoi(buf); wkdata=(struct person *)malloc(sizeof(struct person)); /* ① */ strcpy(wkdata->name,name); /* ② */ wkdata->age=tosi; wkdata->next=NULL; /* ③ */ wp->next=wkdata; /* ④ */ wp=wkdata; /* ⑤ */ } for(wp=start->next;wp !=NULL;wp=wp->next){ printf("%s %d\n",wp->name,wp->age);} } |
① wkdata=(struct person *)malloc(sizeof(struct person)); mallocで次のデータに必要な領域を確保します。変数名wkdata
② strcpy(wkdata->name,name); wkdata->age=tosi; wkdataというpersonal構造体に名前、年齢を代入します
③ wkdata->next=NULL; wkdata->next をNULLにします。NULLは最後のデータの印とします。
④ wp->next=wkdata; wpはwkdataよりひとつ前のpersonal構造体変数なので、ひとつ前のnextにwkdataを設定し、
チェーンを作る。（ポインタ変数wkdataはmallocで確保した領域の先頭アドレスを保持している。）
⑤ wp=wkdata; wpの指し示すポインタをwkdataにする。すなわちwpを最新のpersonal構造体を指し示すようにする。
この説明で理解できる人はかなりＩＱ高いかもしれません。おじさんは初めて自己参照構造体に出会った時、何をやっている
のかわかりそうで、わからずかなりキレました。下の実行例のkyoko入力のターンの時の①～⑤の時の動きを克明に記して
みましたので、じっくりみて理解して下さい。wp(3),wkdata, wp(4)の項をみて下さい。
| ① | ②、③ | ④ | ⑤ |
| start start->name start->age start->next = wp(1) |
start start->name start->age start->next = wp(1) |
start start->name start->age start->next = wp(1) |
start start->name start->age start->next = wp(1) |
| wp(1) wp->name = taro wp->age = 20 wp->next = wp(2) |
wp(1) wp->name = taro wp->age = 20 wp->next = wp(2) |
wp(1) wp->name = taro wp->age = 20 wp->next = wp(2) |
wp(1) wp->name = taro wp->age = 20 wp->next = wp(2) |
| wp(2) wp->name = jiro wp->age = 18 wp->next = wp(3) |
wp(2) wp->name = jiro wp->age = 18 wp->next = wp(3) |
wp(2) wp->name = jiro wp->age = 18 wp->next = wp(3) |
wp(2) wp->name = jiro wp->age = 18 wp->next = wp(3) |
| wp(3) wp->name = ken wp->age =14 wp->next = NULL |
wp(3) wp->name = ken wp->age =14 wp->next = NULL |
wp(3) wp->name = ken wp->age =14 wp->next = wkdata |
wp(3) wp->name = ken wp->age =14 wp->next = wp(4) (=wkdata) |
| wkdata wkdata->name wakdata->age wkdata->next |
wkdata wkdata->name = kyoko wakdata->age = 25 wkdata->next = NULL |
wkdata wkdata->name = kyoko wakdata->age = 25 wkdata->next = NULL |
wp(4) (=wkdata) wp->name = kyoko wp->age = 25 wp->next =NULL |
| (次のwkdataはまだ領域確保されていない 次のターンの①で確保される） |
実行例です。
nameの入力時に何も入力せずリターンキーを押すと、それまでの入力データを順に表示します。
| D:\win95\c>selfref name:taro age:20 name:jiro age:18 name:ken age:14 name:kyouko age:25 name: taro 20 jiro 18 ken 14 kyouko 25 D:\win95\C> |
（２） ちょっと工夫したプログラム
上の例は、あまり自己参照構造体の特長を生かしていないので、次にもう少しひねってみました。入力されたデータが
年齢順につなぎかえられるように工夫したものです。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct person{
char name[30];
int age;
struct person *next;
};
main()
{
struct person dmy;
struct person *start=&dmy;
struct person *wkdata;
struct person *wp,*oldwp;
char name[30]=" ",buf[10];
int tosi;
start=&dmy; oldwp=&dmy;
start->next=NULL; start->age=0;
wp=start;
while(1){
printf("name:");
gets(name);
if(strcmp(name,"")==0)break;
printf("age:");
gets(buf);tosi=atoi(buf);
wkdata=(struct person *)malloc(sizeof(struct person));
strcpy(wkdata->name,name);
wkdata->age=tosi;
/* ① */
for(wp=start;wp != NULL;wp=wp->next){
if(wkdata->age <= wp->age){
wkdata->next = wp;
oldwp->next = wkdata;
break;}
oldwp=wp;}
if(wp == NULL){
wkdata->next=NULL;
oldwp->next=wkdata;
}
}
for(wp=start->next;wp !=NULL;wp=wp->next){
printf("%s %d\n",wp->name,wp->age);}
} |
最初の基本例と違うのは、①以降のforループのところです。データは入力されると、年齢順に並びかえらえるようになっています。
今、wp(1)->wp(2)->wp(3)という順にデータが並んでいたところに、新たなデータwkdataが入力されたとします。
wkdataは、wp(2) < wkdata <wp(3)という大きさだったとします。
この場合、wp(1),wp(2)では何も操作されずforループを回り、wp(3)のところで、
wkdata->next = wp(3)
oldwp(すなわちwp(2))->next =wkdata
とチェーンをつなぎかえ、wp(1)->wp(2)->wkdata->wp(3) という順にします。（その後、oldwp=wp(3)となります。）
wkdataが最大値だった場合は、チェーンの最後に組み込まれます。
すごくわかりにくいかもしれませんが、じっくり理解して下さい。これがわかればＣ言語のすばらしい世界が目の前に
広がりますので（ホントか）
実行例です
D:\win95\C>selfref3 name:taro age:20 name:jiro age:18 name:ken age:15 name:kyoko age:25 name: ken 15 jiro 18 taro 20 kyoko 25 D:\win95\C> |
同じような機能をBasicで記述してみると、次のようです。配列を使うので、様子はかなり違いますが、
こっちの方がわかりやすいでしょう。(でもないか）
10 cls
20 dim name$(10),age(10)
30 input name$(0),age(0)
40 num=num+1
50 input name$(num),age(num)
60 if name$(num)="" then goto 160
70 for i=0 to num
80 if age(num) < age(i) then n$=name$(num):a=age(num):goto 110
90 next
100 goto 40
110 for j=num to i+1 step -1
120 name$(j)=name$(j-1): age(j)=age(j-1)
130 next
140 name$(i)=n$: age(i)=a
150 goto 40
160 for i=0 to num
170 print name$(i),age(i)
180 next
おじさんの見た解説書は、すごくわかりにくくて、えらくアタマにきましたので、今回は、かなり丁寧に説明して
みましたが、いかがでしょうか。