第二週 構造体とポインタ(1)，線形リスト
計算機序論２,
www.kameda-lab.org
2004/09/27, 10/24
今週はC言語の習得のための課題です．
とはいえ、意味のないプログラムを書くのは身が入らない作業になるので，
グラフィックスの課題に絡めてみました．
構造体を使った不定長データ構造(線形リスト)
今週は，構造体を使って，不定長(データの数や長さが可変であること)の
データ構造を作ってみましょう．
そのために最も簡単で良く使われる方法が
線形リスト
です．
線形リストの構造は以下の図のようになります．
次のデータへのポインタをメンバ変数として用意すると，
これを使って，順にデータをたどることができるようになります．
このメンバ変数が空アドレス（NULL）であれば、
リストの最後まで到達したことになります。
実際のサンプルプログラムを見てみよう
以下のLINE構造体は、線分を表現するためのデータ構造体です。
start 〜 widthは，線分自身のデータを表わし、
nextは上で説明した「次のデータへのポインタ」です。
見ればわかるように、３次元データにも対応できるように、
このデータ書式は，ｚ座標もすでに含んでいます．
z座標に関する部分は，今回は使わず，４回目の演習以降で使います．
// 点のための構造体
struct POINT{
float x;
float y;
float z;
float w;
};
// 線分のための構造体 (この構造体の線形リストで各文字や図形を表す).
// 次の線分へのポインタを持つ．最初の線分にアクセスできれば, 数珠繋ぎに
// 最後までアクセスできる．LINE->next → LINE, ....
struct LINE {
struct POINT *start; // 始点
struct POINT *end; // 終点
float r; // 赤色の強度
float g; // 緑色の強度
float b; // 青色の強度
float width; // 線の太さ
struct LINE *next; // 次の線分
};
このようなデータ構造体を繋げて線形リストを作るわけですが，
可変長のリストを作るためには，
プログラムの中でデータ構造体を順次作っていかなければ
なりません。
そのために，malloc, calloc等を使って，メモリを確保していきます．
以下のコードを良く見てください．
ここでは，calloc関数に対して確保するデータの数【ここでは１つ】と
サイズ【sizeof (struct LINE)】を与え，
返ってきたデータをstruct LINE 型として，そこへのポインタを張ります。
// 新しい線分構造体を作り, 前準備をしておく
struct LINE *new_LINE(){
struct LINE *newline = NULL;
newline = (struct LINE *)calloc(1, sizeof(struct LINE));
// 始点, 終点を格納するための構造体もメモリ上に確保する
newline->start = new_POINT();
newline->end = new_POINT();
newline->r = 0.0; newline->g = 0.0; newline->b = 0.0;
newline->width = 1.0;
newline->next = NULL;
return (newline);
}
void ある関数 (引数) {
.....(中略).....
struct LINE *newline = NULL;
.....(中略).....
newline = new_LINE();
.....(中略).....
linked_list_end->next = newline;
}
確保したデータが不要になったら，そのデータに対応するメモリを
解放することもできます．
free(ポインタ変数)とすれば，
ポインタが参照している先のメモリを解放します．
これが簡単にできるように，
free_LINE(), free_FIGURE()
等の関数を用意しています．
ただし，一旦解放した部分にもう一度アクセスしようとすると
エラーになるので，注意すること．
// 線分データのメモリを解放
void free_LINE (struct LINE *line) {
free (line->start);
free (line->end);
free (line);
}
データを読み込みながら線形リストを作る
データはファイルに格納します．
プログラム中にデータを長々と書くのは初心者しか使わないテクニックです．
プログラムが煩雑になるし，
データを変更する度にコンパイルし直さなければならないですから、
はやくそういうことはしないような習慣をつけましょう．
今回の演習では、ファイル中のデータは，以下のような書式とします．
"#" で始まる行は，そこがコメント行として扱われる【読み捨てられる】
"L" で始まる行は線分のデータを表わす．
始点(x, y, z)，終点(x, y, z)，色(r, g, b)，太さの順に書く．
"F" はひとまとまりの図形がそこで終わることを表わす．
# 文字Yのデータ
L 50 350 0 100 200 0 1.0 0.5 0.5 4.0
L 150 350 0 100 200 0 1.0 0.5 0.5 3.5
L 100 200 0 100 50 0 1.0 0.5 0.5 5.0
F
# 文字Kのデータ
L 250 350 0 250 50 0 0.0 1.0 0.2 6.0
L 350 350 0 250 150 0 0.0 1.0 0.2 4.2
L 290 230 0 350 50 0 0.0 1.0 0.2 4.4
F
# 以上
load_LINE(), attach_new_FIGURE() 等は，ファイルからデータを
読み込みながら線形リストを作っていく関数です．
大まかには，順次データを読み込みながら，
構造体を作り(メモリを確保し)，前のデータとつなげて行きます．
この部分はかなりわかりにくいので，各自，その働きを理解し，
コメント文を付加してください【レポートの課題の一つです！】．
// 線分データをコマンドラインから読み込む
void load_LINE (char *command) {
struct LINE *newline;
int number_of_element = 0;
char tag[128];
newline = new_LINE();
// ここで値を代入している！
number_of_element =
sscanf(command, "%128s %f %f %f %f %f %f %f %f %f %f",
tag,
&newline->start->x, &newline->start->y, &newline->start->z,
&newline->end ->x, &newline->end ->y, &newline->end ->z,
&newline->r, &newline->g, &newline->b,
&newline->width);
if (number_of_element != 11) {
fprintf(stdout, "load_LINE: format error (%d elements found)\n",
number_of_element);
return;
}
if (Lines_on_reading == NULL) {
Lines_on_reading = newline;
} else {
Line_at_end->next = newline;
}
Line_at_end = newline;
}
次に，以下の関数を良く見てみましょう．
まず，引数 "line"はポインタ変数であり，
このポインタの先に実際の構造体(LINE)があります．
関数が呼び出されるときは，最初の線分データへのポインタを
含む変数figureが渡されます．
その最初の線分データを描画した後，ポインタの先を次の線分にします．
これをやるのが下記で日本語表記した部分です．
線分リストの終りかどうかをチェックは、ポインタが次に繋がっているか
どうかで判定できます．
// 図形(線分リスト)を描画
void draw_FIGURE (struct FIGURE *figure) {
struct LINE *line = NULL;
if (figure == NULL) return;
line = figure->first_line;
変数lineがNULLでない【＝まだ次がある】うちは
その変数lineによって線を描画し、
さらにその次の線を変数lineにセットして
どんどん線形リスト内を辿っていく
}
関数の戻り値を構造体とする
上記の関数【new_LINE()】のように，戻値【関数の値】を構造体への
ポインタとしている部分がいくつかあります．
以前は，このような動作が保証されていない処理系【Ｃコンパイラ】が
あり，安易には使えませんでしたが，現在はほぼ標準になったと考えて
良いでしょう．
構造体へのポインタを使いこなすと，プログラムが簡潔になるため，
中級テクニックとして是非とも身に付けておきましょう．
プログラム例
ここに，
プログラム例
と
サンプルデータ
を置いておきます．
残念ながら、そのままコンパイルしても何も表示されませんが、
あとちょっと書き加えれば動くはずです．
コンパイルする前に、先週と同じくMakefileを用意するのを
忘れないように。
課題
-
今週の課題を完全に理解するのは少し難しいかもしれません．
しかし，
load_LINE(), attach_new_FIGURE()
がわかれば，ほとんどの部分はそれと同じ考え方で理解できるでしょう．
load_LINE(), attach_new_FIGURE()
の動作の理解と自分なりのコメントを付加することを課題とします．
フローチャートが付いていれば，ボーナス点を加算します．
-
次に，自分なりのデータファイルを用意して下さい．
サンプルプログラム中では，"fig-data.dat" というファイル名に
なっています．
-
プログラムを完成させ，思った通りの動作をするようにして下さい．
図形が順番にかわっていけばOKです．
-
各自の工夫を加えてみてください．
キーボード入力をうまく使えば，
スロットマシンのようなものができるかもしれません
【ただし，これはあくまでも一つの例で，
実際にはどんなものを作っても構いません】．
キーボード入力を随時受け付けるようにするためには，
プログラムの後半部分を
この
ように変更する必要があります．
ただ、この変更を理解するには、GLUTの制御構造
【一週目参照】を
よく理解する必要があります。
Yoshinari Kameda: 2004/09/17-
Yuichi Nakamura: Sun Aug 11 21:08:05 JST 2002