データ構造と アルゴリズム 第四回 知能情報学部 新田直也

抽象データ型 集合抽象データ型 抽象データ型では， ≪操作≫ ≪データ構造≫ 要素の追加 要素の削除 要素の有無 要素の数を調べる 操作の種類と働きは定義されているが，操作のアルゴリズムは問われない．（正しければ何でもよい．） 具体的なデータ構造も定義されていない． →情報隠蔽と呼ばれる． 集合抽象データ型 ≪操作≫ ≪データ構造≫ 要素の追加 要素の削除 要素の有無 要素の数を調べる 2 11 5 3 7

リスト リスト: 抽象データ型の1つ(データの有限列) リストのインターフェース リストを実装可能なデータ構造は何通りもある． k番目の位置に要素を追加: insert(k, e) k番目の位置の要素を削除: delete(k) k番目の位置の要素を読む: read(k) k番目の位置の要素に書く: write(k, e) リストを実装可能なデータ構造は何通りもある． 配列，連結リスト，… 5 2 7 3 11

配列によるリストのイメージ 運動場に一列に並べた段ボール箱を考える． 段ボール箱の中には番号が書かれたボーリングの玉が端から詰められている． 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

連結リストのイメージ 運動場にバラバラに配置した段ボール箱を考える． 段ボール箱はリストの並び順に紐で結ばれている． 3 11 5 7 2

連結リストによるリストの実装 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 も同様．)