線形リスト構造(2)
Copyright(C) 14May2003 coskx TNCT
多くの同じ型の変数を扱う場合,配列が使われることが多い。プログラミングの時点で,使用する配列の大きさ(要素数)がわかっている場合は静的な配列を使う。
int
array[1024]; /*静的な配列の例*/
しかし,プログラミングの時点で配列の大きさがわからない場合は,配列の動的確保の手法があった。しかし,この方法でも,プログラムが起動した直後に配列の大きさが決まらなければ,配列を確保することができない。たとえば人の名前を登録する場合,何人で終わるか見当もつかないことがある。あらかじめ1000人ぐらいを予想してプログラム起動時に1000人分の配列を作っても,途中で不足してしまうこともある。
さて,このように,プログラムの実行が進むにつれて,保存すべきデータ量が増えてゆくときには線形リスト構造というデータ保存の形式がある。線形リスト構造では1データの登録時に1要素を確保するという手法をとる。しかも新たな要素が確保された(作られた)時には新しい要素のアドレスを,直前の要素が覚えているようにする。
このような機能を持つ要素は次のような構造体となる。(ここでは登録データ用の変数は1つだが,複数あってもよい)
線形リスト構造を作る構造体 | |
構造体の要素1 |
登録データ用の変数 |
構造体の要素2 |
次のアドレスをしまうためのポインタ変数 |
1.線形リスト構造にカタカナ名前を登録し,表示後,全削除する例 | |
線形リスト構造に,「ハリー・ポッター」「ロン・ウィーズリー」「ハーマイオニー・グレンジャー」の3つのカタカナ名前を登録する。
登録用の線形リスト構造をつくる構造体は次のようになる。
名前の線形リスト構造を作る構造体 list_t | |
構造体の要素1 |
登録データ用の文字列変数(char型配列) |
構造体の要素2 |
次のアドレスをしまうための「list_tを指すポインタ変数」 |
最初の3つのデータを登録する様子は次のようになればよい。
(1)初めの状態(データが1つも入っていない状態)
元締めとなる「list_tを指すポインタ変数」 namelist | |
値(アドレス) |
NULL(無効) |
(2)1つ目のデータ(「ハリー・ポッター」)が登録された状態
|
→ |
|
(3)2つ目のデータ(「ロン・ウィーズリー」)が登録された状態
|
→ |
|
→ |
|
(4)3つ目のデータ(「ハーマイオニー・グレンジャー」)が登録された状態
|
→ |
|
→ |
|
→ |
|
このように,データ保存用の構造体は,データを格納する変数と,次の構造体が確保された時のアドレスを保存するポインタ変数からできている。
データが登録された構造体はこのポインタ変数によってつながっており,最後に登録された構造体のポインタ変数には必ず「NULL」が入るようになっている。
サンプルプログラムを次に示す。登録の様子を見るために,データ未登録状態の様子,データを登録するたびにどのようにリスト構造ができているかを見せまている。この見せるからくりは,void printListStructure(void)である。
関数registerName()中に list_t
**ptrptr という「ポインタのポインタ」が出てくるが,これは,『「現在着目中のリスト要素」をさしているアドレス』を格納しているポインタ変数のアドレスを格納する「ポインタのポインタ変数」である。
liststructure.c |
#include <stdio.h> |
実行結果 デバッグモード(#define debugが有効な時) (「#ifdef debug」と「#endif」の間も実行する) |
** printListStructure (debug 1)
** got [00373148] and saved it to [0040D000] got [00373178] and saved it to [00373168] got [003731A8] and saved it to [00373198] 3 |
実行結果 利用モード(「#define debug」を「/*#define debug*/」にして無効にした場合) (「#ifdef debug」と「#endif」の間は実行されない(実はコンパイルもされない)) |
3 ハリー・ポッター ロン・ウィーズリー ハーマイオニー・グレンジャー 0 |
デバッグモードで実行した結果,3つのデータが登録されてゆく状態が次のようにわかる。
(1)データ未登録状態(** printListStructure (debug 1) **)
元締めとなるポインタ変数 namelist | |
値(アドレス) |
NULL(表示では00000000) |
(2)「ハリー・ポッター」が登録された状態(** printListStructure (debug 2) **)
|
→ |
|
(3)「ロン・ウィーズリー」が登録された状態(** printListStructure (debug 3) **)
|
→ |
|
→ |
|
(4)「ハーマイオニー・グレンジャー」が登録された状態(** printListStructure (debug 4) **)
|
→ |
|
→ |
|
→ |
|
2.線形リスト構造にカタカナ名前を辞書順に登録し,表示後,全削除する例 | |
名前を辞書順に登録してみよう。リストの中間に新しいデータを登録する場合も生ずる。
登録する名前は「ハリー・ポッター」「ロン・ウィーズリー」「ハーマイオニー・グレンジャー」「ルビウス・ハグリッド」「アルバス・ダンブルドア」で,この順に与えるものとする。ただし,出来上がったリストでは次の順に並んでいるようにする。
アルバス・ダンブルドア
ハーマイオニー・グレンジャー
ハリー・ポッター
ルビウス・ハグリッド
ロン・ウィーズリー
状況を想定すると,最初の2つの登録(「ハリー・ポッター」「ロン・ウィーズリー」)は先の例のとおりに行なわれる。次に「ハーマイオニー・グレンジャー」を登録しようとすると先頭に割り込ませることになる。(「ー」は「リ」より前になる)そこで次のような作業になるであろう。(なおアドレスが書いてあるが,実は実行結果を見ながら書いたものである。実行前にどこのアドレスでこれらの作業が行なわれるか想定するのは不可能である。)
作業前
|
→ |
|
→ |
| |||||||||||||||||
↑ | |||||||||||||||||||||
|
作業後
|
→ |
|
→ |
|
→ |
|
そして,その次の「ルビウス・ハグリッド」の登録時には,「ハリー・ポッター」と「ロン・ウィーズリー」の間に登録することになるので,つぎの作業が想定される。
作業前
|
→ |
|
→ |
|
→ |
| ||||||||||||||||||||||
↑ | ||||||||||||||||||||||||||||
|
作業後
|
→ |
|
→ |
|
→ |
|
→ |
|
次のプログラムを追跡し,データの登録の様子を確認せよ。
関数registerNameSorted()中に list_t
**ptrptr という「ポインタのポインタ」が出てくるが,これは,『「現在着目中のリスト要素」をさしているアドレス』を格納しているポインタ変数のアドレスを格納する「ポインタのポインタ変数」である。
リストに名前を辞書順に登録する |
#include <stdio.h> |
実行結果 デバッグモード(#define debugが有効な時) (「#ifdef debug」と「#endif」の間も実行する) |
** printListStructure (debug 1)
** |
3.線形リスト構造の指定場所に登録,指定場所を削除する例 | |
|
線形リスト構造の先頭からN番目の位置に名前を登録する関数registerName()と指定の位置の名前を削除する関数deleteName()を作ります。先頭から3番目に「ichiro」を登録したかったら,registerName(3,"ichiro")というように使います。先頭から5番目の要素を削除したかったらdeleteName(5)のように使います。
ただし,これらの関数では,各要素は0,1,2,3,...と数えます。また要素数が3つしかないのに6番目に登録しようとしたり,10番目を削除使用とした場合は,これらの関数はエラーを表示し,リスト構造への作業は何もしないことにします。
関数registerName(),deleteName()中に list_t
**ptrptr という「ポインタのポインタ」が出てくるが,これは,『「現在着目中のリスト要素」をさしているアドレス』を格納しているポインタ変数のアドレスを格納する「ポインタのポインタ変数」である。
liststructure.c |
#include <stdio.h> closeList();
/*List構造の解放*/ |
実行結果 デバッグモード(#define debugが有効な時) (「#ifdef debug」と「#endif」の間も実行する) |
** printListStructure (debug 1)
** **REEOR** 1 is out of range accepted [ロン・ウィーズリー] accepted [ハーマイオニー・グレンジャー] accepted [ルビウス・ハグリッド] accepted [アルバス・ダンブルドア] 5 |
実行結果 利用モード(「#define debug」を「/*#define debug*/」にして無効にした場合) (「#ifdef debug」と「#endif」の間は実行されない(実はコンパイルもされない)) |
**REEOR** 1 is out of range **REEOR** 6 is out of range 5 アルバス・ダンブルドア ルビウス・ハグリッド ハリー・ポッター ロン・ウィーズリー ハーマイオニー・グレンジャー **REEOR** 5 is out of range 5 アルバス・ダンブルドア ルビウス・ハグリッド ハリー・ポッター ロン・ウィーズリー ハーマイオニー・グレンジャー 4 アルバス・ダンブルドア ルビウス・ハグリッド ハリー・ポッター ロン・ウィーズリー 3 アルバス・ダンブルドア ルビウス・ハグリッド ハリー・ポッター 2 アルバス・ダンブルドア ルビウス・ハグリッド 1 アルバス・ダンブルドア 0 **REEOR** 0 is out of range 0 |