第 9 回 - 構造体（3）

[5/22, 2006 H.Aman]

例題 1

下図のようにデータが数珠つなぎに連なった構造をリスト構造という． 340x61(6187bytes)

ここでの矢印による連結をポインタによって実現する．
この構造を次の構造体 node を使って実現し，データの格納と表示を行いなさい．

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

なお，この構造体と上のイメージ図との対応は次の通りとする：

コーディング例

example9_1.c

     1	/*
     2	 * プログラミング演習 第 9 回
     3	 * [例題 1]
     4	 * (C) 2006 Hirohisa AMAN <aman@cs.ehime-u.ac.jp, aman@computer.org>
     5	 */
     6	#include <stdio.h>
     7	
     8	/* 構造体 node の宣言 */
     9	struct node {
    10	  int data;
    11	  struct node* next;
    12	};
    13	
    14	int main(void){
    15	  struct node sample[3];
    16	  struct node* head;
    17	  struct node* p;
    18	  
    19	  /* 各データを格納 */
    20	  sample[0].data = 2;
    21	  sample[1].data = 3;
    22	  sample[2].data = 5;
    23	
    24	  /* 各ノードを連結 */
    25	  head = &sample[0];
    26	  sample[0].next = &sample[1];
    27	  sample[1].next = &sample[2];
    28	  sample[2].next = NULL;
    29	
    30	  /* リストの内容を表示 */
    31	  p = head;
    32	  while ( p != NULL ){
    33	    printf("%d ", p->data);
    34	    p = p->next;
    35	  }
    36	  printf("\n");
    37	
    38	  return 0;
    39	}

※左端の数字は行番号であり，ソースコードには含まれない点に注意！

コンパイル & 実行例

     $ gcc example9_1.c [Enter]
     $ ./a.out [Enter]
     2 3 5

解説

まず，データを格納するために構造体 node 型の変数を 3 つ用意します．ここでは配列としてまとめて用意しています．

    15	  struct node sample[3];

つまり，sample[0], sample[1], sample[2] という 3 つの変数を用意します．
あわせて，ポインタ変数も 2 つ（head と p）用意しておきます．

    16	  struct node* head;
    17	  struct node* p;

次に，各ノードに整数値 2, 3, 5 を代入します：

    19	  /* 各データを格納 */
    20	  sample[0].data = 2;
    21	  sample[1].data = 3;
    22	  sample[2].data = 5;

この次がポイントです！
sample[0] をポインタ変数 head に連結させます．
言い換えると，sample[0] の番地を head に格納することで，head から sample[0] の内容にアクセスできるようにします．

    24	  /* 各ノードを連結 */
    25	  head = &sample[0];

アンパサンド（&）を変数名の前に書くと，その変数の番地が調べられることは既に学んだ通りです．
これにより，次のようなリンクが形成されます．

同様にして，

    26	  sample[0].next = &sample[1];
    27	  sample[1].next = &sample[2];

によって，次のようなリンクが形成されます．

最後に，sample[3] が末端であること，即ち，次に続くノードはないことを書き込みます．
具体的には隣のノードを指し示すためのポインタ変数（sample[2].next）に NULL という特別な値を書き込みます．これは「どこも指していない」ことを意味します．

    28	  sample[2].next = NULL;

これで目的のリスト構造は完成です．

あとはこの内容を順に表示していくだけです．
表示にもポインタ変数を使います．先頭から順に末尾までたどっていって，順次データを表示させていきます．

    30	  /* リストの内容を表示 */
    31	  p = head;
    32	  while ( p != NULL ){
    33	    printf("%d ", p->data);
    34	    p = p->next;
    35	  }
    36	  printf("\n");

これ以上の細かい説明は省略しますが，34 行目の持つ効果のみ説明しておきます．最初の段階（31行目）では

という状態なのですが，ここで 34 行目のコードを実行すると

という状態に移行します．

同様の処理が p == NULL となるまで繰り返されることにより，全データが順に表示されていきます．