データ構造と アルゴリズム 第四回 知能情報学部 新田直也
抽象データ型 データ構造とそれを操作するアルゴリズムを外から見えないように一まとめに（カプセル化）したもの． メーラーソフトで考えてみよう． データ抽象とも呼ばれる(厳密には異なる概念)． メーラーソフトで考えてみよう． ユーザは操作の種類 (インタフェース)のみを 知っている． 受信する メールを読む 操作の中身（アルゴリズム）や データの保存形式（データ構造） を知らなくても使える． メールを書く アドレスを登録する
リスト リスト: 抽象データ型の1つ(データの有限列) リストのインターフェース リストを実装可能なデータ構造は何通りもある． k番目の位置に要素を追加: insert(k, e) k番目の位置の要素を削除: delete(k) k番目の位置の要素を読む: read(k) k番目の位置の要素に書く: write(k, e) リストを実装可能なデータ構造は何通りもある． 配列，連結リスト，… 5 2 7 3 11
配列によるリストの実装(1) まずは簡単なものから… int list[1000]; int num = 0; int read(int k) { if (k < num) return list[k]; return ERR; } void write(int k, int e) { if (k < num) list[k] = e;
配列によるリストの実装(2) 続き… deleteは…? void insert(int k, int e) { if (k <= num) { for (int n = num - 1; n >= k; n--) { list[n+1] = list[n]; } list[k] = e; num++; deleteは…?
リストを配列で実装した場合の計算量 データのサイズ: 配列の要素数(num)． (最悪)時間計算量 read: 2ステップ → O(1) write: 2ステップ → O(1) insert: k が 0 の場合最悪． (2×num + 3)ステップ → O(num) void insert(int k, int e) { if (k <= num) { for (int n = num - 1; n >= k; n--) { list[n+1] = list[n]; } list[k] = e; num++;
連結リスト 各要素がリンクでつながっているリスト n番目の要素には先頭からn回リンクをたどらなければたどり着かない． 先頭 5 2 7 3 11 5 2 7 3 11 5 2 7 3 11 5 2 7 3 11
連結リストによるリストの実装 read, write: O(n) insert: O(n) delete: O(n) 先頭 5 2 3 11 7 先頭 5 2 7 3 11
リストの実装のまとめ 同じ抽象データ型でも内部のデータ構造が変わると操作するアルゴリズムもその計算量も変わる． リストの インタフェース リストの場合: リストの インタフェース 配列による 実装 連結リストによる実装 read O(1) O(n) write insert delete
連結リストのプログラム(1) C言語での実装には構造体とポインタを用いる． Webページを考えて見ればよい． Javaではクラスとその参照だけで実装できる． Webページを考えて見ればよい．
連結リストのプログラム(2) struct CELL { int value; struct CELL *next; } 内容 1ページに相当 (構造体) 次ページのアドレス (ポインタ) CELL value next
連結リストのプログラム(3) ポインタの復習: 構造体の復習: p がポインタ(アドレス)なら，*p は pが示す先を表す． *p s がメンバ m を持つ構造体なら，s.m は s のメンバ m を示す． *p p s s.value s.next
連結リストのプログラム(4) 先頭の要素を示すポインタ(リンク): ポインタを使ったアクセス: struct CELL *header; *(*header).next header (*header).value (*header).next (*(*header).next).value (*(*header).next).next
連結リストのプログラム(5) リストの最後は? リストを順に表示するプログラム: 略記法： next が何も指さない(NULL)． struct CELL *header; for (p = header; p != NULL; p = (*p).next ) { printf(“%d\n”, (*p).value); } 略記法： (*p).next は p->next と書ける． ( (*p).value も同様．)