パソコン活用研究シリコンバレー(C、C++、の活用研究)


自己参照構造体

======================================================================================
構造体のメンバーとして、自分自身の構造体を入れてしまったものが”自己参照構造体”です。
ちょっとややこしくて、理解しにくい(これがすんなり理解できる人は、IQ高いんでしょうね)のですが、
線形リストのプログラムを組むときの肝になりますので、頑張って下さい。
おじさんも、なんとなくこんなもんかなあ理解してから実際使えるようになるまで、結構苦労しました。
======================================================================================

1 自己参照構造体

とりあえず、自己参照構造体てのが何の役にたつか講釈する前に、そやつがいったい何者なのかを
見てみましょう。後ほどサンプルプログラムで使う 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とすることも柔軟にできます。
配列を使用しても同様なことを実現することは不可能ではありませんが、配列と異なり以下のような利点があります。
@ データ数を固定しなくてよい(配列ではあらかじめデータ数を固定して宣言しておかねばならない)
  −>すなわち、追加、削除が自由にできる
A 挿入、削除、入れ替えが物理的な移動を伴わずにできる。
  −>例えば、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)を変更するだけでいいので、効率が
     よくなります。

ただし、特定のデータを検索したい場合、必ずチェーンの最初から1つづつポインタをたどって探していくことに
なるので、データ数が多くなった場合は検索効率は落ちます。

2 自己参照構造体プログラム例

(1) 基本例
では、自己参照構造体を使って実際にプログラムを作ってみましょう。
まずは、名前と年齢を順次登録し、登録した順に表示するプログラムです。
personal構造体変数として、4つの変数を使っています。
dmyは初期化用です。
startは最初のpersonal構造体ですが、このプログラムではstartのデータはstart->nextだけで、name,ageは空です。
wpは作業用です。
wkdataは最新のデータ用です。


#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); /* A */
wkdata->age=tosi;
wkdata->next=NULL; /* B */
wp->next=wkdata; /* C */
wp=wkdata; /* D */
}

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
A strcpy(wkdata->name,name);  wkdata->age=tosi; wkdataというpersonal構造体に名前、年齢を代入します
B wkdata->next=NULL; wkdata->next をNULLにします。NULLは最後のデータの印とします。
C wp->next=wkdata; wpはwkdataよりひとつ前のpersonal構造体変数なので、ひとつ前のnextにwkdataを設定し、
  チェーンを作る。
D wp=wkdata;  wpの指し示すポインタをwkdataにする。すなわちwpを最新のpersonal構造体を指し示すようにする。

この説明で理解できる人はかなりIQ高いかもしれません。おじさんは初めて自己参照構造体に出会った時、何をやっている
のかわかりそうで、わからずかなりキレました。下の実行例のkyoko入力のターンの時の@〜Dの時の動きを克明に記して
みましたので、じっくりみて理解して下さい。wp(3),wkdata, wp(4)の項をみて下さい。

@ A、B C D
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はまだ領域確保されていない
次のターンの@で確保される)

実行例です

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>


(2) ちょっと工夫したプログラム
上の例は、あまり自己参照構造体の特長を生かしていないので、次にもう少しひねってみました。入力されたデータが
年齢順につなぎかえられるように工夫したものです。

#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が最大値だった場合は、チェーンの最後に組み込まれます。

すごくわかりにくいかもしれませんが、じっくり理解して下さい。これがわかればC言語のすばらしい世界が目の前に
広がりますので(ホントか)

実行例です


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


おじさんの見た解説書は、すごくわかりにくくて、えらくアタマにきましたので、今回は、かなり丁寧に説明して
みましたが、いかがでしょうか。


TopPage