6 リスト構造

リスト構造
データベースのようなプログラムでは、データの追加や削除が頻繁に行われるため、プログラム
の実行時においても必要なデータ数を決定することが難しい。このような場合、図 $( に示すよう
にデータを必要な個数だけポインタでつなぐリスト構造を用いることが考えられる。
first
data3
data2
data1
図 ) リスト構造
ここで、次のような簡単なデータベースのプログラムを考える。
レコード
件のレコードは、「名前」.文字列/ と「点」.整数/ からなる。
プログラムを簡単にするために、ここでは異なるレコードの「名前」は全て異なるものと仮
定する。
コマンド
.**# レコードの追加/、*.*
!
# 指定した名前を持つレコードの削除/、
.
# 指定した名前を持つレコードを検索し、その点を出力/、."# レコード数
を出力/、!.!# 全レコードの出力/、
.
"*# 終了/ が使える。
このプログラムでは、"# "# !!# # 等の関数を用いるため、最初
に * # *! # " の３つのヘッダファイルをインクルードしておく。
L
に必要 ) に必要 ) に必要レコードを格納するための構造体 * を次のように定義する。
*
)
,
「名前」を格納する領域への文字型ポインタ「点」を格納する次のレコードへのポインタこの構造体 * に、新たなデータ型として !
" という名前を付ける。
$ )
データ型 ) の定義これにより、以降は、「 *」の代わりに、「
!
"」を用いることが出来る。
先頭のエレメント .レコード/ へのポインタをグローバル変数として宣言する。
) リストの先頭の要素へのポインタまた、キーボードから文字列を入力するためのバッファとして文字型配列
領域に確保する。
をグローバル
例えば、構造体 ' を値として持つ変数 44 は、
「$3$ ' 44*」のように宣言すればよいが、変数の宣言の
たびに「$3$ ' ‥‥」などと長々書くのは面倒である。0 言語では、
「$.5'%」を用いて、データ型の定義という
形で、データ型に別名を付けることが出来る。
G@H .;
G@H"
キーボードから文字列を入力するためのバッファ領域 " 関数では、を JKK に初期化 .空リストの作成/ した後、「コマンドを読み込み対
応する処理を実行する」を繰り返す。
)&#'
*
+ HIGG
空リストの作成 J&'*
以下を繰り返す &3>)) 3'
&34
3'
コマンド入力 J& "'*
コマンドの先頭文字で必要な処理を選択 22
))<&'
コマンドの実行 %
22
))<&'
コマンドの実行 %
2
2
))<
&'
コマンドの実行 %
22
))<&'
コマンドの実行 %
22
))<
&'
コマンドの実行 %
22
&'
コマンドの実行 &プログラム終了' それ以外 &3DL >))553'
,
,
,
関数の処理の概略は次のようになる .図 $M 参照/。ここでは、レコードはリストの
先頭に追加するものとし、追加するレコードの「名前」と「点」はキーボードより入力するものと
する。
一時変数 .ローカル変数/ として、
!
" 型 .構造体 */ へのポインタを宣言。
!
" 型 .構造体 */ のデータを記憶するための記憶領域を !! で確保し、その
領域へのポインタをに代入する。
$ ,"
= にを代入する。
% にを代入する。
& キーボードより「名前」を入力し、その文字列を格納するのに必要な領域を確保し、その領域
へのポインタを ,"
に代入し、入力された「名前」をその領域にコピーする。.'&$
節の例参照/
' ,
に「点」を入力する。
first
malloc
data3
data2
data1
data3
data2
data1
pt
data4
first
pt
data4
図 ) データの追加
関数の処理の概略は次のようになる。
一時変数 .ローカル変数/ として、
!
" 型 .構造体 */ へのポインタを宣言。
先頭レコードへのポインタをに代入。
$ が JKK で無い間、以下を繰り返す。
./ ,"
と ,
を出力
. / 5 ,"
=3 - 次のレコードへのポインタをに代入 -
関数も関数 !./ と同様に実現できる。レコード数を数えるための変
数 " を用意しに初期化しておく。そしてレコードの値を出力する代りに " をつずつ
増加してやり、最後にその値を出力すれば良い。
関数も関数 !./ と同様に実現できる。最初に「探すべき名前」の文
字列を適当な変数 . -
/ にキーボードから入力しておき、 !./ で ,"
と
,
を出力する部分を、文字型ポインタ ,"
の指す文字列と文字型ポインタの
指す文字列が一致すれば ,
を出力して " するようにすれば良い。
つの文字型ポインタとが指している文字列が同じであるかどうかを判定するには、演習で作成したプロ
グラムの一部分が再利用できる。あるいは、0 の標準ライブラリにある、関数を使うことも出来る。この
関数は、つの文字列が一致していればを返す。なお、$5 関数を使用する場合、ヘッダファイルとして $16- を
43' しておく必要がある。7注意8「 !! ‥‥」ではポインタの値メモリの番地を比較することになりとが指している文字列の比較にはならない。
first
data3
data2
data1
free
first
data3
data2
data1
図 ) データの削除
関数は、関数 ./ とほぼ同様に実現できる。基本的には、キーボー
ドから与えられた文字列を「名前」に持つレコードが見つかったら、その一つ前のレコードの構
造体のメンバ "
= に、削除すべきレコードの構造体のメンバ "
= の値を代入すれば良い .図 $
参照/。このためには、一つ前のレコードの番地 .ポインタ/ か、一つ前のレコードのメンバ "
=
の番地を別途記憶しておく必要がある。特に、削除すべきレコードが、先頭レコードの場合は注意
を要する。
削除したレコードが使用していたメモリ領域を開放するためには関数を用いる。例えば、
!
" 型へのポインタが今削除したレコードを指しているものとすると、
&-)'
&'
削除したレコードで名前を記憶するために使用していた領域を開放削除したレコード &)' が使用していた領域を開放で、開放することが出来る。このように不要になったメモリ領域を解放してやると、その領域は次
の !! の際に再利用される。長期間に渡り頻繁にレコードの追加と削除を繰り返すようなアプ
リケーションでは、不要になったメモリ領域は必ず解放することが重要である。
演習上記のデータベースのプログラムを作成せよ。各自件程度のレコードを準備し、
各コマンドを繰り返し適当に与え、各コマンドが正しく実行されていることを示せ。
ヒントまず、 **./ と !./ を完成させると、リスト構造が正しく出来ているか確
認できる。その次に、 "./# ./ を完成させ、最後に *
!
./
に取り組もう . *
!
./ が一番複雑になると思われる/。
ヒント本節の説明では、関数のプロトタイプ宣言については言及していないが、関数のプロトタ
イプ宣言を忘れずに行うこと。
不要になったメモリ領域を解放し忘れることを「メモリリーク . 49」と呼ぶ。メモリリークのあるプログ
ラムを走らせ続けると、 # がダウンするなど極めて深刻な事態を招く危険性があるので、メモリリークを発生させないよ
うに細心の注意を払う必要がある。

Download Report