|
|
【課題 2】 |
例題 2
次のイメージ図に対応したリスト構造をプログラムで実現しなさい．なお，各のノードのデータには 2 次元ベクトル（x, y いずれも整数値） を使用せよ．
コーディング例
1 /*
2 * プログラミング演習 第 9 回
3 * [例題 2]
4 * (C) 2006 Hirohisa AMAN <aman@cs.ehime-u.ac.jp, aman@computer.org>
5 */
6 #include <stdio.h>
7
8 /* 構造体 vnode の宣言 */
9 struct vnode {
10 int x;
11 int y;
12 struct vnode* next;
13 };
14
15 int main(void){
16 struct vnode sample[3];
17 struct vnode* head;
18 struct vnode* p;
19
20 /* 各データを格納 */
21 sample[0].x = 2; sample[0].y = 3;
22 sample[1].x = 1; sample[1].y = -1;
23 sample[2].x = 7; sample[2].y = 2;
24
25 /* 各ノードを連結 */
26 head = &sample[0];
27 sample[0].next = &sample[1];
28 sample[1].next = &sample[2];
29 sample[2].next = head;
30
31 /* リストの内容を表示 */
32 p = head;
33 while ( p != NULL ){
34 printf("(%d,%d)\n", p->x, p->y);
35 p = p->next;
36 }
37
38 return 0;
39 }
※左端の数字は行番号であり，ソースコードには含まれない点に注意！
コンパイル & 実行例
$ gcc example9_2.c [Enter]
$ ./a.out [Enter]
(2,3)
(1,-1)
(7,2)
(2,3)
(1,-1)
(7,2)
(2,3)
... ← 無限に繰り返される [Ctrl] + [c] で停止させる．
解説
プログラムの内容でいえば 例題1 と大きな違いはありません．構造体の宣言がわずかに変更されて （無用な混乱を避けるため，構造体名を vnode にしています） おり， それに合わせてデータへのアクセス方法が少しだけ変更されているだけです．
例えば，
21 sample[0].x = 2; sample[0].y = 3;
や
34 printf("(%d,%d)\n", p->x, p->y);
がこれに該当します．
（例題1
では，data の一種類でした．）
強いて違いを挙げるとすると，
25 /* 各ノードを連結 */
26 head = &sample[0];
27 sample[0].next = &sample[1];
28 sample[1].next = &sample[2];
29 sample[2].next = head;
という部分が大きな意味を持ちます．例題1 では，head ではなく NULL になっていました．
つまり，sample[2] のノードが末端となっていたのですが，
今度の場合は
sample[2] の隣のノードは先頭（head）と同じ
という構造になっています．
すなわち 循環構造です．
リストが循環した構造になっているため， データ表示のループ
31 /* リストの内容を表示 */
32 p = head;
33 while ( p != NULL ){
34 printf("(%d,%d)\n", p->x, p->y);
35 p = p->next;
36 }
において，ポインタを順に隣へ移していく p = p->next
は際限なく繰り返されることになります．
なぜなら，sample[2] の後ろに続く次のノードは再び sample[0]
になっているからです．
このように， 循環構造を容易に作れるということもポインタを使ったリストの特長です． 例えば，電車の環状線のモデル， 処理のローテーションのモデル等をプログラム上で扱う場合には， まさにこの構造が活きてくることになります．