出席の確認はOpenLMS の 3 限のコマを用いて行う. 3限の授業時間中に出席登録を完了せよ.
この授業のトップページから レポートのページに移動し, レポートの提出状況を常に確認せよ.
前回図4.5 の出力部分に注目する.
printf ("%d ",header.next->value); printf ("%d ",header.next->next->value); printf ("%d ",header.next->next->next->value); printf ("%d ",header.next->next->next->next->value);
図 5.1 出力部分
第 4 回課題 の print_all を作成するにはこの出力部分をループで実現しなければならない. ループにするためにはループ変数を決めて,同じ形を繰り返すように 変形しなければならない.上のプログラム部分は以下のものと等価である. (p は (struct CELL *) 型のポインタ変数とする)
p = header.next; printf ("%d ",p->value); p = p->next; printf ("%d ",p->value); p = p->next; printf ("%d ",p->value); p = p->next; printf ("%d ",p->value);
図5.2 出力部分を繰り返す形に
これで printf ("%d ", p->value); p = p->next; をループの中で繰り返せばよいことがわかる. 最後の要素を出力したときのポインタ p が指す要素の p->next の値は NULL であるから これをループ終了の条件とすればよい.結局 print_all は以下のような ループで作ることができる.
void print_all(void) { struct CELL *p; p = header.next; while (p != NULL){ printf("%d ", p->value); p = p->next; } printf("\n"); }
図5.3 連結リストの print_all
この,リストの先頭から最後までたどる処理は連結リストの 基本となる処理なのでよく理解すること.
前回図4.5 の main 関数の上に print_all() 関数を追加し, 出力するための行
printf ("%d ",header.next->value); printf ("%d ",header.next->next->value); printf ("%d ",header.next->next->next->value); printf ("%d ",header.next->next->next->next->value); printf ("\n");
を print_all(); で置き換えたものを作り,動作を確認せよ.
単純な連結リストでは,途中の要素にアクセスするためには 先頭から一つずつ next メンバをたどってゆく必要がある. ($O(n)$)また,全ての要素にデータを格納する領域の他に 次の要素を指すポインタを格納する領域が必要である.
要素の途中への挿入,削除は,近隣の数個の要素の next メンバの書き換えで行うことができる.配列のように 後の要素を全てずらす必要がない.
P.54 Fig5.2 の操作を実際に行ってみる. 前回図4.5 の2個目の要素の後ろに要素(value=8 とする)を挿入する手順を 説明する.まず教科書 p.54 Fig 5.2 と同じ状況になるように 挿入位置の前の要素へのポインタを記憶する変数 x と 新しい要素へのポインタを記憶する変数 p を main 関数の最初の変数宣言の場所に付け加える.
struct CELL *ap, *bp, *cp, *dp, *x, *p;
図5.4 main の変数宣言への追加
前回図4.5 の
dp->next = NULL;
図5.5 main 変更場所
の行でリスト(2,5,12,-4)が完成している.その後ろに 挿入作業のコードを追加する.
教科書図 5.2 の変数 x と同じ状況にするには 2 個めの要素へのポインタ bp を x に代入すればよい. (2番目の後に挿入するため)
x = bp;
図5.6 x の設定
次にmalloc を行い, 要素一つ分のメモリを確保してそのアドレスを変数 p に保存する以下の文を挿入する.
if ((p = malloc(sizeof(struct CELL))) == NULL) exit(1);
図5.7 malloc による領域確保
次にデータの記録(value=8)と周辺の ポインタのつなぎ変えを行う. 具体的にはまず p->value にデータである 8 を代入する. x->next には旧3番めの要素へのポインタが格納されている. この値は新4番目として必要なので先に p->next に コピーしておく. 次に x->next へ新3番目となる新しく作成した要素へのポインタ p を代入する. (x->next が p と同じものを指すようにする) まとめると,具体的には上の図5.7「malloc による領域確保」の次に以下の文を挿入する.
p->value = 8; p->next = x->next; x->next = p;
図5.8 value の設定と周辺ポインタのつなぎ変え
2 行目と 3 行目の順番を逆にししまうと後で必要になる 新4番目へのポインタの値が消えてしまうので正しく動作しない ことに注意せよ.
main に上記の変更を行い,挿入作業(図5.6,図5.7と図5.8追加部分) の前後で print_all()を実行するテストプログラムを作成し, 実行してリストが (2 5 12 -4) から (2 5 8 12 -4) に変化し,実際に挿入が行われていることを確認せよ.
必要になってから要素の領域を動的に増やせることが 連結リストの大きな利点である.
P.54 Fig5.3 をよく見て,練習 5.2 の状態のリスト(2 5 8 12 -4) から2 番目の要素を削除するようにポインタをつなぎ変えよ. print_all() を使って削除されていることを確認せよ.
実際のプログラムでは,ここまでの例の変数 ap, bp, cp, dp のように 全ての要素へのポインタを記憶しておくようなことはしない. 「現在見ている要素」へのポインタ p を用意しておいて p = p->next などを実行して p を「進めながら」処理する.
P.56 Fig5.4,5.5 のように連結リストは, 接続,切断ポイントのポインタが分っていれば簡単に($O(1)$で) 接続,切断が行える.
動的割り当てを行うのでプログラム実行中に 領域を確保する関数を実行する必要がある. この授業では malloc を使う.コンパイル時ではなく, プログラム実行中の任意の時点で malloc で領域を確保し, free で解放できる.
ここからは練習5.2までのように全ての要素へのポインタを記憶する ことなく必要なポインタ変数だけ使用してメモリの動的割り当てを行う より実践的な関数を実装してゆく.また,データ構造の実現と 本体アルゴリズムを分離する意味から,抽象データ型リスト (データ構造である連結リストとは別の概念であることに注意) の基本操作(教科書p.35 Table 4.1)を関数として提供し, main からは基本操作関数を通してのみデータにアクセスする 方針でプログラムを作成する.例えば今まで行っていたように main 内で直接構造体の value メンバの値を参照するようなことはせず, 値を取り出す基本操作関数を通して要素の値を受け取るような構造にする.
データ構造と本体アルゴリズムを分離し,基本操作のアクセス方法を 決めることで,データ構造だけの改良,本体アルゴリズムだけの変更 ができる.これは抽象化を意識したソフトウェアの開発方法で, 大規模なソフトウェアになるほど重要になる.
使用する連結リストはこれまでと同様に struct CELL 型として宣言されたグローバル変数 header をダミーヘッダとしたものとする. header.next が NULL なら連結リストは空であり, NULL でなければ header.next が一個目の要素へのポインタ となる.
最初に空のリストを作成する関数 new_list を作成する. 構造体 header はグローバル変数として宣言されているので プログラム開始時は領域は確保されているが値が 設定されていない状態になっている.new_list のすべきことは グローバル変数 header の next メンバに NULL を代入することである. 関数 new_list には引数も戻り値もない.
void new_list(void) { header.next = NULL; }
図5.9 new_list
次にリストの先頭に要素を挿入する関数 insert_head を作成する.この関数には引数として挿入する要素の 値(value メンバに設定する値)を渡す必要がある. この int 型のパラメータの名前を v とする.
insert_head の戻り値はない.
手順としてはまず以下のことを行い,挿入する一個分 の要素を作成する.
次に,p が指している(アドレスが p である)新たに作成した要素を 連結リストの先頭に挿入するためのポインタのつなぎ変えを行う. 連結リストが空のときでも正しく動作するかどうか吟味することは 重要である.このような場合には漏れがないように場合分けを行って考察する.
ここで上記 2 つの場合をよく見ると,要素が存在するときの処理を 連結リストが空のときに行っても正しい値が設定されることが わかる.(空のリストの header.next は NULL だから) このことからプログラムでは場合分けは必要なく,要素があるとき用に 書いた処理を行えば両方の場合で正しく動作することがわかる.
以上をまとめたものが下の関数 insert_head である.
void insert_head(int v) { struct CELL *p; if ((p = malloc(sizeof(struct CELL))) == NULL) exit(1); p->value = v; p->next = header.next; header.next = p; }
図5.10 insert_head
sttuct CELL 構造体の定義と, これまで作成した new_list, insert_head, print_all をまとめて,main として簡単なテストを行う プログラムを付け加えたものが下の図5.11 である. 実行し,main 内のテスト内容を変更して動作を確認せよ.
#include <stdio.h> #include <stdlib.h> struct CELL { struct CELL *next; int value; } header; void insert_head(int v) { struct CELL *p; if ((p = malloc(sizeof(struct CELL))) == NULL) exit(1); p->value = v; p->next = header.next; header.next = p; } void new_list(void) { header.next = NULL; } void print_all(void) { struct CELL *p; p = header.next; while (p != NULL) { printf("%d ",p->value); p = p->next; } printf("\n"); } int main(void) { new_list(); print_all(); insert_head(-4); print_all(); insert_head(12); print_all(); insert_head(5); print_all(); insert_head(2); print_all(); }
図5.11 連結リストのテスト
第 5 回課題「連結リストでの要素の途中挿入」 を提出せよ.