alg2015-3r3.ppt

1 アルゴリズムとデータ 構造 第 3 回基本的なデータ構造 ( リスト スタック キュー )

プログラミング で学ぶところ 授業で学ぶデータ構造の範囲 機械語のデータ型 レジスタ値とその番地 基本データ型 char, int, large int, double, 構造データ型 配列 (array), 構造体 (struct) 基本的データ構造 リスト (linked list), スタック (stack), 待ち行列 (queue) この で学ぶところ 二分探索木 (binary search tree), 平衡探索木 (balanced search tree), ハッシュ表 (hash table) 先進的データ構造 機械語 ( 型がない ) 昔の言語も持っている型 (C,Pascal) 最近の言語 (C++, Java, etc.)

3 データ構造 データ構造とはセル (cell) の集合にある構造を与えたもの データを格納する基本単位 Algorithms + Data Structures = Programs Niklaus Wirth ( 二クラウス ビルト ) が書いた本の題名 Niklaus Wirth(1934-) はスイスの計算機科学者 コンピュータ言語 Pascal の設計者 1984 年にチューリング賞受賞

抽象 (abstract Data Type) とは? Linked List CREATE INSERT DELETE..... データ構造 ( の API) を 抽象データ型 ともいう. データ構造には, それは何か (What) と それをどのように実現するか?(How) の二つの面がある. 現代的なプログラム言語やライブラリーはこの考え方に基づく.( 例 : C++,Java,Ruby, Python などなど )

付録 データ構造とアルゴリズムの定番教科書 この授業の教科書 ( 一冊持っていると良い. 自習には本は必須.) 茨木俊秀,C による, 照晃堂,2916 円 平田富夫, < 改訂 C 言語版 >, 森北出版,2376 円. Aho, Hopcroft, Ullman The Design and Analysis of Computer Algorithms, Addison Wesley, 1974.( 最初のデータ構造の教科書の一つ ) Knuth The Art of Computer Programming, Addison-Wesley 1 巻 ( 基本算法 ),2 巻 ( 準数値算法 ),3 巻 ( 整列と探索 ), 1975 基本部分の百科辞典. 機械語で記述. 全部読んだ人は少ない? Cormen, Leiserson, Rivest, and Stein Introduction to Algorithms, 3rd Edition, MIT Press, 2009. 現在, 最も定評がある教科書. 企業やプロコンなどでの勉強会の定番. ( 日本語訳有,3 巻組 )

第 3 回基本データ構造 n 今日の内容 : リスト n 配列 / 連結リスト / 双連結リストによる実装 スタック n スタックの応用 ( 再帰呼び出し ) キュー n ポイント ポインタを用いたデータ構造 抽象データ型とその実装 6

7 リストとは? ( 抽象データ型として ) n 0 A A A 1 A 2 A 3 A n 太郎 二郎 花子 道子 n n n n A i : i 1 i n n 位置 をもつ

8 リストに対する操作 n List L = create () : 空のリストを返す. n INSERT(x,p,L) : リスト L( 要素数 n) の位置 p の次の位置に要素 x を挿入 n DELETE(p,L) : リスト L の位置 p の次の位置の次の要素を削除 n FIND(i,L) : リスト L の i 番目のセルの内容を返す n LAST(L) : リスト L の最後のセルの位置を返す n PREVIOUS(p,L) : リスト L において 位置 p の 1 つ前のセルの位置を返す 太郎 二郎 花子 道子

9 リストに対する操作 n INSERT(x,p,L) : リスト L( 要素数 n) の位置 p の次の位置に要素 x を挿入 n DELETE(p,L) : リスト L の位置 p の次の位置の次の要素を削除 n FIND(i,L) : リスト L の i 番目のセルの内容を返す n LAST(L) : リスト L の最後のセルの位置を返す n PREVIOUS(p,L) : リスト L において 位置 p の 1 つ前のセルの位置を返す 太郎 二郎 花子 道子

10 リスト リストとは 太郎 二郎 要素を 0 個以上 1 列に並べたもの 花子 道子 ( 注意 ) リストは連結リストを指すことが多い [ リスト,a 1,,a n-1 の実現法 ] 1. 配列 (array) n 個の連続領域に格納 a 1 a n-1 2. 連結リスト (linked list) ポインタで次の要素の格納領域を指す init a 1 a n-1 null 3. 双方向連結リスト (doubly linked list) ポインタで前後の要素の格納領域を指す init null a n-1 null final a 1

ポインタ (pointer) 復習 : ポインタとは? セルの位置を示すデータ 機械語レベルでは セルの番地そのもの プログラミングにおいては その値を具体的に知る必要はない

12 ポインタは番地 オペレーティングシステム ポインタ p 132 値 x 5 C 言語の場合 ² ポインタ p が指す変数の値 x を x = *p で表す ² 変数 x を指すポインタ p を p = &x で取り出せる レジスタレベルでみた計算機 CS 専攻

13 リスト リストとは 太郎 二郎 要素を 0 個以上 1 列に並べたもの 花子 道子 ( 注意 ) リストは連結リストを指すことが多い [ リスト,a 1,,a n-1 の実現法 ] 1. 配列 (array) n 個の連続領域に格納 a 1 a n-1 2. 連結リスト (linked list) ポインタで次の要素の格納領域を指す init a 1 a n-1 null 3. 双方向連結リスト (doubly linked list) ポインタで前後の要素の格納領域を指す init null a n-1 null final a 1

14 C 言語によるリストの定義 (1/3) 配列 int a[100]; % 100 個の整数 a[0],a[1],,a[99] からなる配列 連結リスト typedef struct cell { int element; struct cell *next; } cell; cell *init=null; % 空のリスト void list_add(int x) { % 整数要素 x を先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; init=new; } struct cell { }: 構造体 cell を と定義 typedef cell: をデータタイプ cell 型として定義 init は cell 型データを指すポインタ型 sizeof(cell): cell 型のデータサイズ ( バイト ) malloc(n):n バイトのメモリーを確保 (cell *)malloc(n): 確保した n バイトの領域を cell 型データ格納領域とみなす

15 C 言語によるリストの定義 (2/3) typedef struct cell { int element; struct cell *next; } cell; cell *init=null; % 空のリスト void list_add(int x) { % 整数要素 x を先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; init=new; } new init 5 init 4init に new ポインタをコピー 3 6 NULL next 領域 3 6 list_add(5) を実行すると new new init 5 element 領域 NULL 1 メモリの確保 2element の代入 3next に init ポインタをコピー 3 6 NULL

16 C 言語によるリストの定義 (3/3) typedef struct cell { int element; struct cell *prev; struct cell *next; } cell; cell *init=null; cell *final=null; 双方向連結リスト % 空のリスト void list_add(int x) { % 整数要素 xを先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; new->prev=null; if(init==null) final=new; else init->prev=new; init=new; } cell 型は 1 つ前のデータを指すポインタ prev ももつ 最後尾のデータを指すポインタ final も必要 先頭に追加する場合は 1 つ前のデータはなし 最初に格納されたデータが最後尾のデータ (final が指すデータ ) となる 2 つ目以降に格納されたデータは prev ポインタを新しい先頭データを指すように更新する

17 連結リストが得意な処理 ( 挿入 ) INSERT(x,p,L) : リスト L( 要素数 n) の位置 p の次の位置に要素 x を挿入 配列の場合 最悪 / 平均時間計算量は Θ(n) p a 1 a i-1 a i a n-1 a 1 a i-1 x a i a n-1 連結リストの場合 a 1 init a i-1 a i p a n-1 null a 1 init a i-1 a i a n-1 null 最悪 / 平均時間計算量はΘ(1) 双方向連結リストの場合 init null p a i-1 a i x a n-1 null final init null a i-1 a i a n-1 null final 最悪 / 平均時間計算量は Θ(1) x

18 連結リストが得意な処理 ( 削除 ) DELETE(p,L) : リスト L( 要素数 n) の位置 p の次の位置の次の要素を削除 配列の場合 最悪 / 平均時間計算量は Θ(n) p a 1 a i-1 a i a n-1 a i+1 a 1 a i-1 a i+1 a n-1 連結リストの場合 a i-1 p init a i a i+1 a n-1 null a i-1 init a i+1 a n-1 null 最悪 / 平均時間計算量はΘ(1) 双方向連結リストの場合 p a i-1 a i a i+1 a i-1 a i+1 最悪 / 平均時間計算量は Θ(1)

19 配列が得意な処理 (i 番目の要素へのアクセス ) FIND(i,L) : リストL( 要素数 n) のi 番目のセルの内容を返す LAST(L) : リストL( 要素数 n) の最後のセルの位置を返す PREVIOUS(p,L) : リストL( 要素数 n) において 位置 pの1つ前のセルの位置を返す 配列の場合連続領域であるためi 番目の要素や前後の要素に1ステップでアクセス可能 p FIND(i,L) : Θ(1) LAST(L) : Θ(1) a a 1 a i-1 a i a i+1 a n-1 PREVIOUS(p,L) : Θ(1) 連結リストの場合 a i-1 PREVIOUS(p,L) FIND(i,L) init a i a i+1 FIND(i,L) : Θ(n), LAST(L) : Θ(n), PREVIOUS(p,L) : Θ(n) 双方向連結リストの場合 init null PREVIOUS(p,L) PREVIOUS(p,L) p = FIND(i,L) a i-1 a i FIND(i,L) : Θ(n), LAST(L) : Θ(1), PREVIOUS(p,L) : Θ(1) p = FIND(i,L) = a n-1 LAST(L) null LAST(L) a n-1 LAST(L) final null

20 配列による連結リストの実現 0 1 2 3 4 5 6 m-3 m-2 m-1 a 1 a 2 a n-1 a n-2 2 4 6 1 9-1 7 m-1 5-1 free_init 0 init 3 メリット メモリー確保 解放の時間を節約できる メモリー使用量を制御できる ガベージコレクションの必要がない

21 スタック (stack) スタックとは要素の挿入 削除がいつも先頭からなされるリスト LIFO(last-in-first-out) [ 基本操作 ] TOP(S) スタックSの先頭の位置を返す POP(S) スタックSの先頭の要素を削除 PUSH(x,S) スタックSの先頭に要素 xを挿入 a 2 PUSH(a2,S) POP(S) a 2 a 2 TOP(S) a 1 a 1 a 1

22 スタックの実現法 配列による実現 S top a 1 a i i =TOP(S) すべての操作の時間計算量は Θ(1) PUSH(a i+1,s) top i+1 POP(S) S a 1 a i a i+1 連結リストによる実現 TOP(S) = a i a i-1 top null すべての操作の時間計算量は Θ(1) PUSH(a i+1,s) top a i a i-1 POP(S) null a i+1

23 プログラム ( 階乗 n! の計算 ) int factorial(int n) { if(n==1) return 1; else return n*factorial(n-1); } factorial(3) スタックの応用例 ( 関数呼び出し ) 実行コードシークエンス 1: if n 1 then goto 3 2: return 1 3: r=factorial(n-1) 4: return n*r factorial(2) スタック n=3, 戻り :4 3 局所変数 n 3 実行コード 1: 2: 3: 4: 実行アドレス 3 n 2 1: 2: 3: 4: 3 n factorial(1) n=2, 戻り :4 n=3, 戻り :4 1 n 3 スタック n=3, 戻り :4 n 2 1: 2: 3: 4: 2 6 1: 2: 3: 4: 4 1: 2: 3: 4: 4

24 待ち行列 ( キュー ) とは? n 要素の挿入は最後尾 削除は先頭からなされるリスト n FIFO(first-in-first-out) ともいう GHI A B A 1, A 2,..., A C D E F n [ 基本操作 ] n TOP(Q) キュー Qの先頭の位置を返す n ENQUEUE(x,Q) 要素 xをキュー Qの最後尾に入れる n DEQUEUE(Q) 先頭の要素をキュー Qから除く エンキュー デキュー と読む

25 待ち行列 ( キュー, queue) 待ち行列 ( キュー ) とは要素の挿入は最後尾 削除は先頭からなされるリスト FIFO(first-in-first-out) [ 基本操作 ] TOP(Q) キュー Qの先頭の位置を返す ENQUEUE(x,Q) 要素 xをキュー Qの最後尾に入れる DEQUEUE(Q) 先頭の要素をキュー Qから除く ENQUEUE(a 2,Q) a 1 a 2 TOP(Q) a 1 a 2 DEQUEUE(Q) a 1 a 2

26 TOP(Q) = キューの実現法 配列による実現 すべての操作の時間計算量は Θ(1) Q front j rear (j+i)%n 0 n-1 a i a 1 ENQUEUE(a i+1,q) front j rear (j+i+1)%n 0 n-1 Q a 1 a i a i+1 DEQUEUE(Q) front (j+1)%n rear (j+i+1)%n 0 n-1 a 1 a i a i+1 連結リストによる実現 TOP(Q) = a 1 front a i null rear ENQUEUE(a i+1,s) すべての操作の時間計算量は Θ(1) front a 1 a i a i+1 DEQUEUE(Q) null rear front a 1 a i a i+1 null rear

配列で巡回リストを表わす. キューの長さ n が限定された場合 先頭と末尾がつながって, 輪になったリスト 要素の位置を,n の剰余演算で決定. 0 1 2 3 4 5 Element A 4 A 5 A 1 A 2 A 3 rear front front から i 番目の要素 = Element[ (front + i) mod n ] ex. Elem[(head + 5) mod n] (head = 1 and n = 6) = Elem[7 mod 6] = E[1]

抽象データ型 (Abstract Data Type) Linked List CREATE INSERT DELETE..... データとその操作をカプセル化定められた正しい方法でだけ外部からアクセスできる. 不正な操作からデータを保護する上で有効である. 利用にデータ構造の実現法は知らなくていい. 機能と実現を分離プログラムの他の部分と独立に内部の実現が可能.

第 3 回基本データ構造 n 今日の内容 : リスト n 配列 / 連結リスト / 双連結リストによる実装 スタック n スタックの応用 ( 再帰呼び出し ) キュー n ポイント ポインタを用いたデータ構造 抽象データ型とその実装 29