第二週 構造体とポインタ・線形リスト
計算機序論２,
www.kameda-lab.org
2005/10/03
構造体を使った不定長データ構造(線形リスト)
構造体については講義や以前の課題で説明した通りです。
今週は，構造体を使って，不定長(データの数や長さが可変であること)の
データ構造を作ってみましょう．
そのために最も簡単で良く使われる方法が
線形リスト
です．
線形リストの構造は以下の図のようになります．
次のデータへのポインタをメンバ変数として用意すると，
これを使って，順にデータをたどることができるようになります．
このメンバ変数が空アドレス（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));
if (newline != NULL) {
// 始点, 終点を格納するための構造体もメモリ上に確保する
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;
if (newline->start == NULL || newline->end == NULL) {
free_LINE(newline);
newline = 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) {
if (line == NULL)
return;
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() 等は，ファイルからデータを
読み込みながら線形リストを作っていく関数です．
大まかには，順次データを読み込みながら，
構造体を作り(メモリを確保し)，前のデータとつなげて行きます．
この部分はかなりわかりにくいので，各自，その働きを理解し，
コメント文を付加してください【レポートの課題の一つです！】．
// LINE構造体の生成, 読み込み
// 線分データをコマンドラインから読み込む
void load_LINE (char *command) {
struct LINE *newline = NULL;
int number_of_element = 0;
char tag[CMDSTRLEN];
newline = new_LINE();
if (newline == NULL) {
fprintf(stderr, "Memory allocation failed at load_LINE()\n");
return;
}
// ここで値を代入している！
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()】のように，戻値【関数の値】を構造体への
ポインタとしている部分がいくつかあります．
以前は，このような動作が保証されていない処理系【Ｃコンパイラ】が
あり，安易には使えませんでしたが，現在はほぼ標準になったと考えて
良いでしょう．
構造体へのポインタを使いこなすと，プログラムが簡潔になるため，
中級テクニックとして是非とも身に付けておきましょう．
Yoshinari Kameda: 2004/10/02-
Yuichi Nakamura: Sun Aug 11 21:08:05 JST 2002