計算機言語 II 第 14 回 リスト構造
http://www.math.u-ryukyu.ac.jp/~suga/gengo/2018-2/14.pdf
今回はデータ構造とそれに関するアルゴリズム話します. 最も簡単な例として,連結リストを取り上げます. データ構造とそれを操作するアルゴリズムは密接な関係があり,様々な研究や発明がなされています. この
「密接な関係」をひとまとまりにしたのが「オブジェクト指向」の発想の原点のひとつです.
1 連結リスト
次のように,一連のデータを数珠つなぎにしたデータ構造を連結リスト, あるいは線型リストと言います. 各データは構造体からなり, データ本体と次の場所を指すポインタで構成されます. 各データの構造体は, node(節)と呼ばれます.
開始記号 → 次のデータへのポインタ情報1 → 次のデータへのポインタ情報2 → · · · → 次のデータへのポインタ情報n → 終了記号
「前から順に処理をしていく」という操作をプログラムする時に標準的に用いられるデータ構造です. 前か ら順に処理をするには,「配列を用いる」というのも選択肢の一つです. それぞれの利点,欠点は次のようにな ります.
• 配列は,データの追加や削除がある場合の処理が面倒になる.
• データの追加や削除が処理中に起こらない場合には,配列を利用した方がプログラムは書きやすい. すなわち,あらかじめ処理するデータ量が決まっており, 処理中もデータの追加は削除がほとんど起こらな いなら, 配列を用いてプログラムを書き,処理するデータ量が不明な場合や,処理途中にデータの追加や削除が 頻繁に起こるなら,連結リストを用います. 例えば,新たなエディタを作成しようとした時,「行単位に文字列 へのポインタと次の行へのポインタでデータ構造を与える」などです.
1.1 プログラム例
奥村先生のGitHubにプログラム例があります. 取りあえずダウンロードして実行して下さい. https://github.com/okumuralab/algo-c/blob/master/src/list2.c
プログラムでは,連結リストを構造体として定義し, 後ろから順にリストを作成します. そのあと, リストの 順を逆転させて正しい順序にしています. 先頭は,headという名前のポインタで,終了記号は,NULL ポインタ (どこも指していないということを明示するポインタ)を用いています. 逆転させるアルゴリズムは,ホワイト
1.2 データの検索
連結リスト内にあるデータの検索には, 前から順に検索していく線形検索しか方法はありません. 先頭から 順に検索していき,見つかれば,そのnodeへのポインタ,見つからなければ, NULLポインタを返す関数を上 の例で書くと,次のようになります.
pointer search(pointer head, infotype x) {
pointer p = head;
/* 次では p が NULL となる判定を先にしないと, 存在しない時実行時エラー */
while((p!=NULL)&& p->info !=x){
p = p -> next;
}
return p;
}
上の関数を,list2.cのmain の前に付け加えて,main を次に変更して実行して見て下さい. (ファイル名 は,list3.cとして以下のテキストでは述べます.)
int main(void) {
infotype x, s;
pointer head;
head = NULL; /* 空のリスト */
for (x = 1; x <= 9; x++) head = add_list(x, head);
head = reverse_list(head);
/* ここからが変更部分 */
fprintf(stderr, "整数を入力して下さい: ");
scanf("%d", &s);
if (search(head, s)!=NULL){
printf("%d はデータの中にあります.\n", s);
} else {
printf("%d はデータの中にありません.\n", s);
}
return 0;
1.3 データの挿入
最初に述べたように,連結リストでは,効率よくデータの追加や削除を行うことができます.
例であるようにリストのデータが整列されている場合には,通常は,整列を乱さないようにデータの追加,削 除をする必要があります.
data(1), data(2), ..., data(N)が整列されて連結リストに収められているとします. これのdata(I) とdata(I+1)の間に入るべきnewdataを挿入するとします(I = 1, 2, ..., N. I=Nのときはリストの最後に 追加する).
これには,次のようなアルゴリズムを用います.
1. nodeを指すポインタ変数pを用意して先頭nodeを指すように初期化する.
2. 先頭から data(k)とnewdataの大小関係を比較し, newdata > data(k)となるまで,pを進める. 3. newdataが増えるので,構造体をmalloc()で作成し,それを指すポインタ変数qを用意しておく. 4. もしpが最後の要素でなければ,
（a）qのnext変数にp->nextを代入し, qのデータにpのデータを代入する.
（b）p->nextにqを代入し,pのデータはnewdataにする.
5. pが最後の要素なら,qが指すnodeを末尾に加えることになるので,
（a）pのnext変数はqを指す.
（b）qにnewdataを保持させて,qのnextはNULL ポインタにする.
上の奥村先生のソースに基づくプログラム例だと,次のような関数を書くことになります.
void insertdata(pointer head, infotype x) {
pointer p=head;
pointer q;
while ((p ->next !=NULL) &&p->info < x){
p = p->next;
}
q = malloc(sizeof(*q));
if (q==NULL){
printf("メモリ不足.\n"); exit(1);
}
if ( p ->info > x){ /* 途中への挿入 */
q -> next = p -> next;
q -> info = p ->info;
p -> next = q;
p -> info = x;
} else { /* x は全てのデータより大きい. 最後に追加 */
p->next= q;
q->info = x;
q->next=NULL;
} }
list3.cに上の関数を付け加えて,さらにmain を次のようにして(初期データを奇数列にしてinsertdata の実行を入れる)コンパイル実行して見て下さい. 実行時には偶数を入力して見て下さい.
int main(void) {
infotype x, s;
pointer head;
head = NULL; /* 空のリスト */
for (x = 1; x <= 19; x+=2) /* 初期データは奇数 */
head = add_list(x, head);
head = reverse_list(head);
fprintf(stderr, "整数を入力して下さい: ");
scanf("%d", &s);
insertdata(head, s);
show_list(head);
return 0;
}
レポート問題(締め切り: 1月31日)
1. 上のsearch 関数のwhile文をwhile(p->info !=x && (p!=NULL)) に変えると,見つからない値 を探すと実行時エラーになる. それはなぜか? 件名: search
2. 上のプログラムで, 与えられた値を持つ要素を search 関数で探し, その node を削除する関数
deletedata を書け. 一致するデータが見つからない場合には,そのようなメッセージを出力すること.
(最後の要素の削除は少し面倒になるので,途中の要素の削除が出来れば,それでレポートとしてはOK とします.) 件名: deletedata
レポート問題の削除の場合や,上の挿入のソースでもそうなのですが,最後のデータに対しての操作(データ の追加や,最後のデータの削除)が「素朴な連結リスト」では面倒になります. 従って,通常は,何もデータを 持たないデータの終わりを示す「番兵」をリストの最後に置いたプログラムを作成します. 時間的に解説する 余裕がないので,興味のある人は, 例えば「Cで学ぶデータ構造とアルゴリズム: Leendert Ammeraal著 小 山浩徳訳,オーム社」などを参照して下さい.
なお, リスト構造には,連結方向が前後の両側になっている「双方向リスト」や,最後の要素が先頭要素を指 すようにした「循環リスト」などもあり,それぞれに検索,挿入,削除が同じような方法で実行できます. 挿入, 削除に関しては,双方向リストの方がアルゴリズムは簡単になります(両方を指すようにしなければ成らない 分の手間は増える). 循環リストだと, 検索に関しては最後の要素を指す番兵がなければ, 見つからない場合無 限ループになるので注意が必要です.
