アルゴリズムとデータ構造

講義 アルゴリズムとデータ構造 第 3 回基本的なデータ構造 ( リスト スタック キュー ) 大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室喜田拓也 講義資料 2018/5/23

今日の内容 基本的なデータ構造リスト : 最も基本的なデータ集合の表現 配列 / 連結リスト / 双連結リストによる実装 スタック : 積み上げ式のデータ格納方式キュー : 入れた順に取り出せるデータ格納方式 ポイント ポインタを用いたデータ構造 抽象データ型とその実装 2

抽象データ型 (Abstract Data Type) データ型を, それに適用される一連の操作で抽象的に定めたもの create insert delete 抽象データ型 データ たとえば Linked list データとその操作をカプセル化することのメリット 定められた正しい方法でのみデータがアクセスされる 不正な操作からデータを保護することができる ユーザはデータ構造の実現方法について知る必要がない プログラマは他の部分とは独立して内部を実現することができる 3

リストとは? 0 個以上の要素を一列にならべたもの リスト LL 太郎 二郎 花子 道子 LL 1 LL 2 LL 3 LL 4 要素 LL ii : 最初から ii 番目の要素 (1 ii nn) リスト中の場所を指示するための 位置 をもつリストの長さ : 要素数 nn 空リスト : 要素を含まないリストのこと 4

リストに対する操作 リスト LL 太郎 二郎 花子 道子 LL 1 LL 2 LL 3 LL 4 INSERT(xx, pp, LL) : リスト LL( 要素数 nn) の位置 pp の次の位置に 要素 xx を挿入 DELETE(pp, LL) : リスト LL の位置 pp の次の要素を削除 FIND(ii, LL) : リスト LL の ii 番目のセルの内容を返す LAST(LL) : リスト LL の最後のセルの位置を返す PREVIOUS(pp, LL) : リスト LL において 位置 pp の 1 つ前のセルの 位置を返す ここで 位置 pp とはメモリ上の位置を指し示すポインタのこと 5

ポインタ (pointer) ってなに? ポインタ pp データ xx セルの位置を示すデータ AA 機械語レベルではセルの番地とセルの型情報の組プログラミングにおいては, その値を具体的に知る必要はない ポインタ p 132 値 x 5 C 言語の場合 ポインタ p が指す変数の値を, *p で取り出せる 変数 x のアドレス ( 格納場所 ) は &x で参照できる 6

リストの実装の方策 1. 配列 (array) : メモリ上の nn 個の連続領域に格納 1 2 3 4 nn LL 1 LL 2 LL 3 LL 4 LL nn 2. 連結リスト (linked list): ポインタで次の要素の格納領域を指す init LL 1 LL 2 LL nn 3. 双方向連結リスト (doubly linked list): 2 個のポインタで前後を指す init LL 1 LL 2 LL nn last 7

連結リストによるリストの実装 (C 言語版 ) 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 型データ格納領域とみなす 8

連結リストによるリストの実装 (C 言語版 ) つづき 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; } 最初に空リストができる init 最初は, どこも指していないことを示す特別な値 が入っている list_add(5) を実行すると 1 メモリ上に空のセルが作られる 2 そのセルの element 部分に値 x が入る 5 3 ポインタ next には init が指す位置が入る 5 最初に add される要素の場合は 4 init はその新しくできたセルを指す init 5 9

連結リストによるリストの実装 (C 言語版 ) つづき 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; } 現状のリストの様子 init 5 さらにlist_add(3) を実行すると 1 メモリ上に空のセルが作られる 2 そのセルのelement 部分に値 xが入る 3 3 ポインタ next には init が指す位置が入る 3 5 4 init はその新しくできたセルを指す init 3 5 10

双方向連結リストによるリストの実装 (C 言語版 ) 双方向連結リストによる実装 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ポインタを新しい先頭データを指すように更新する 11

連結リストが得意な処理 ( 挿入の場合 ) 配列の場合 最悪 / 平均時間計算量は Θ(nn) 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 a 1 init a i-1 a i a n-1 最悪 / 平均時間計算量はΘ(1) 双方向連結リストの場合 init p a i-1 a i x a n-1 final init a i-1 a i a n-1 final 最悪 / 平均時間計算量はΘ(1) x 12

連結リストが得意な処理 ( 削除の場合 ) 配列の場合 最悪 / 平均時間計算量は Θ(nn) 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 a i-1 init a i+1 a n-1 最悪 / 平均時間計算量はΘ(1) 双方向連結リストの場合 p a i-1 a i a i+1 a i-1 a i+1 最悪 / 平均時間計算量は Θ(1) 13

配列が得意な処理 (i 番目の要素へのアクセス ) 配列の場合 連続領域であるため ii 番目の要素や前後の要素に 1 ステップでアクセス可能 FIND(i,L): Θ(1) LAST(L): Θ(1) PREVIOUS(p,L): Θ(1) a a 1 a i-1 a i a i+1 a n-1 PREVIOUS(p,L) p FIND(i,L) LAST(L) 連結リストの場合 a i-1 init a i a i+1 p a n-1 FIND(i,L): Θ(nn), LAST(L): Θ(nn), PREVIOUS(p,L): Θ(nn) 双方向連結リストの場合 init ==an-1 p a i-1 a i PREVIOUS(p,L) FIND(i,L) LAST(L) PREVIOUS(p,L) LAST(L) FIND(i,L): Θ(nn), LAST(L): Θ(1), PREVIOUS(p,L): Θ(1) final FIND(i,L) =14

配列によるコンパクトな連結リストの実現方法 連結リストを配列内に配置し, 要素が入っていないセルを管理する リストと混在させることで実現する 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 メリット メモリー確保 解放の時間を節約できる メモリー使用量を制御できる ガベージコレクションの必要がない INSERT 操作が Θ 1 時間でできる DELETE は Θ nn 時間 15

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

スタックの実現法 配列による実現 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 すべての操作の時間計算量は Θ(1) PUSH(a i+1,s) top a i a i-1 POP(S) a i+1 17

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

キューの実現法 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 rear ENQUEUE(a i+1,s) すべての操作の時間計算量は Θ(1) front a 1 a i a i+1 DEQUEUE(Q) rear front a 1 a i a i+1 rear 19

配列によるキューの実現 配列で巡回リストを表すキューの長さ nn が限定された場合先頭と末尾がつながって, 輪になったリスト要素の位置を nn の剰余演算で決定 0 1 2 3 4 5 キュー Q: AA 4 AA 1 AA 2 AA 3 rear front 先頭から ii 番目の要素 = Q[(front+ ii ) mod nn] ( 例 ) front=3,nn=6 のとき,(0 から数えて )3 番目の要素は? Q[(front + 3) mod nn] = Q[6 mod 6] = Q[0] 20

今日のまとめ 基本的なデータ構造リスト : 最も基本的なデータ集合の表現 配列 / 連結リスト / 双連結リストによる実装 スタック : 積み上げ式のデータ格納方式キュー : 入れた順に取り出せるデータ格納方式 ポイント ポインタを用いたデータ構造 抽象データ型とその実装 21

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