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

プログラムの構成要素 アルゴリズムはプログラムを構成する重要な要素． もう一つの重要な構成要素: →データ構造 データを扱うアプリケーション: データベース，ワープロ，表計算，作図ソフト，メーラー，ゲーム，… 数は最も単純なデータ構造． 自然数，整数，有理数，実数，… 数学におけるより複雑なデータ構造の例． ベクトル，行列，集合，リスト，…

数学と情報科学の違い 数学が扱う対象は変化しない． 情報科学が扱う対象（データ）は変化する． 情報科学では，データは操作によって変化する． 3x = 2x + 5 ⇒ x の値は常に5 (x は未知数，代数) 情報科学が扱う対象（データ）は変化する． x = x + 1; ⇒ x の値が1つ増える (x は変数) 情報科学では，データは操作によって変化する． 例えば，集合への操作を考える． 要素の追加，要素の削除，・・・ <データ構造> 操作1 操作2 操作3

抽象データ型（1/2） データ構造に応じて操作の内容と種類が定まる． データ構造とそれに対する操作群をまとめた （カプセル化した）ものを抽象データ型と呼ぶ． 2 2 11 11 13 要素13の追加 5 5 3 3 7 7 要素3の削除 2 11 5 7

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

代表的な抽象データ型（1/2） 集合 リスト 要素の追加 要素の削除 要素の有無 要素の数を調べる k番目の位置に要素を追加 11 5 3 7 5 2 7 3 11

代表的な抽象データ型（2/2） スタック キュー(待ち行列) 先頭への要素の追加 (push) 先頭からの要素の取り出し (pop) 先頭へ要素を入れる (enqueue) 末尾からの要素の取り出し (dequeue) 頂上(top) 底(bottom) 5 5 2 7 3 11 5 5 2 7 3 11 先頭(front) 末尾(rear) 5 5 2 7 3 11 5 2 7 3 11 11

リストのデータ構造 リストを実装可能なデータ構造は何通りもある． まずは配列による実装を考えよう． リストのインターフェースは何だったか? 配列，連結リスト，… まずは配列による実装を考えよう． リストのインターフェースは何だったか? k番目の位置に要素eを追加: insert(k, e) k番目の位置の要素を削除: delete(k) k番目の位置の要素を読む: read(k) k番目の位置の要素にeを上書きする: write(k, e)

配列によるリストの実装(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) { int n; if (k <= num) { for (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 の場合最悪． (3×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++;

計算量のオーダの求め方 正しくは，最悪の場合のステップを計算する必要． どうせ，オーダで表すと係数や定数は捨てられる． insert の場合，(2×num + 3)ステップ どうせ，オーダで表すと係数や定数は捨てられる． どんぶり勘定でよい． ループの回数，深さに注目する． 基本的に，k重ループがあった場合，オーダはO(nk)． もっとも遅い処理だけに注目．

連結リスト 各要素がリンクでつながっているリスト 詳細は次回． 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