情報工学概論 (アルゴリズムとデータ構造) 第5回

11.1 スタックとキュー 動的集合，挿入と削除をサポートする スタック (stack) では，DELETEでは最後に挿入された要素が取り除かれる 後入れ先出し (last-in, first-out; LIFO) という キュー (queue) では，最初に挿入された要素が取り除かれる 先入れ先出し (first-in, first-out; FIFO) という

スタック (Stack) INSERT, DELETEの代わりにPUSH, POPと呼ぶ 9 2 6 15 PUSH(S,x): 集合 S に要素 x を加える． POP(S): S から最後に PUSH された要素を削除し， その要素を返す PUSH(S,15) POP(S) 15 6 9 2 9 2 6 15

配列によるスタックの実装 最大 MAX 要素を格納できるスタックを実装 スタックを表す構造体 要素は S[1..top] に格納される S: 要素を格納するサイズMAXの配列(へのポインタ) MAX: 配列 S のサイズ 要素は S[1..top] に格納される S[1]: スタックの底 S[top]: スタックの最上部 top  MAX typedef int data; typedef struct { int top; int MAX; data *S; } stack;

実装例 PUSH(S,x) POP(S) topを1増やし，x を配列に入れる topがMAXを超えたらエラー O(1) 時間 スタックが空ならエラー サイズを1減らし，最上部の要素を返す O(1) 時間 void PUSH(stack *s,data x) { if (s->top == s->MAX) { printf("オーバーフロー\n"); exit(1); } s->top = s->top + 1; s->S[s->top] = x; data POP(stack *s) { if (STACK_EMPTY(s)) { printf("アンダーフロー\n"); exit(1); } s->top = s->top - 1; return s->S[s->top + 1];

その他の関数 STACK_EMPTY(S) MAKE_STACK(size) スタックが空なら1を返す O(1) 時間 int STACK_EMPTY(stack *S) { if (S->top == 0) return 1; else return 0; } stack *MAKE_STACK(int size) { stack *s; data *S; s = malloc(sizeof(stack)); S = malloc((size+1)*sizeof(data)); s->top = 0; s->MAX = size; s->S = S; return s; }

キュー (Queue) INSERT, DELETEの代わりにENQUEUE, DEQUEUEと呼ぶ 人の並んだ列と同じ 15 6 2 9 DEQUEUE(Q) Q ENQUEUE(Q,x) 15 6 2 9

配列によるキューの実装 最大 MAX1 要素を格納できるキュー キューを表す構造体 Q: 要素を格納する配列 MAX: 配列 Q のサイズ head: キューの先頭の位置 tail: 次に追加される位置 typedef struct { int head; int tail; int MAX; data *Q; } queue; 1 2 3 4 5 6 7 8 9 10 11 12 15 6 9 8 4 head tail

環状バッファ (Ring Buffer) 配列 Q の右端と左端はつながって輪になっていると考える Q[MAX] の右は Q[1] だとみなす 要素は Q[head..MAX] Q[1..tail1] に格納される DEQUEUEの際に全要素を左にずらす必要がない 1 2 3 4 5 6 7 8 9 10 11 12 3 5 15 6 9 8 4 17 tail head

空のキューの作成 MAKE_QUEUE(size) size 個の要素を格納できる空のキューを作成 queue *MAKE_QUEUE(int size) { queue *q; data *Q; size = size+1; q = (queue *)malloc(sizeof(queue)); Q = (data *)malloc((size+1)*sizeof(data)); q->head = 1; q->tail = 1; q->MAX = size; q->Q = Q; return q; }

実装例 ENQUEUE(Q,x) DEQUEUE(Q) x をQ[tail]に入れる tailを1増やす O(1) 時間 Q[head]を取り出す headを1増やす O(1) 時間 void ENQUEUE(queue *q,data x) { q->Q[q->tail] = x; if (q->tail == q->MAX) q->tail = 1; else q->tail = q->tail + 1; } data DEQUEUE(queue *q) { data x; x = q->Q[q->head]; if (q->head == q->MAX) q->head = 1; else q->head = q->head + 1; return x; } 注: オーバーフロー, アンダーフロー 処理は省略してある

11.2 連結リスト (Linked Lists) オブジェクトをある線形順序に並べて格納するデータ構造 連結リストでの線形順序は，オブジェクトが含むポインタで決定される 双方向連結リスト (doubly linked list) L の要素 キーフィールド key ポインタフィールド prev, next (付属データ) key next NIL head(L) 9 16 4 prev

next(x): リスト中の x の直後の要素のポインタ prev(x): x の直前の要素のポインタ next(x) = NIL のとき，x は最後の要素 prev(x): x の直前の要素のポインタ prev(x) = NIL のとき，x はリストの最初の要素 head(L): リストの先頭の要素のポインタ head(L) = NIL のとき，リストは空 NIL head(L) 9 16 4 prev

リストの種類 一方向 (singly linked) と双方向 (doubly linked) 既ソート (sorted) と未ソート 一方向のとき，各要素は prev を持たない 既ソート (sorted) と未ソート 既ソート: リストの線形順序はキーの線形順序に対応 未ソート: 任意の順序 循環 (circular list) と非循環 循環: リストの先頭要素の prev はリストの末尾を指し，末尾の next はリストの先頭を指す 以下では未ソート双方向(連結)リストを扱う

双方向リストの構造体 リストの要素 双方向リスト typedef struct lobj { struct lobj *prev; // 前の要素へのポインタ struct lobj *next; // 後の要素へのポインタ data key; // キー } lobj; typedef struct { lobj *head; // 先頭要素のポインタ } dllist;

省略記法 #define HEAD(L) (L->head) #define KEY(x) (x->key) #define NEXT(x) (x->next) #define PREV(x) (x->prev) #define NIL NULL

連結リストの探索 LIST_SEARCH(L, k): リスト L に属する，キー k を持つ最初の要素のポインタを返す キー k を持つ要素が存在しなければ NIL を返す (n) 時間 lobj *LIST_SEARCH(dllist *L, data k) { lobj *x; x = HEAD(L); while (x != NIL && KEY(x) != k) { x = NEXT(x); } return x; 9 16 4 head(L)

連結リストへの挿入 LIST_INSERT(L, x): x を L の先頭に挿入 O(1) 時間 x のキーは既にセットされているとする void LIST_INSERT(dllist *L, lobj *x) { NEXT(x) = HEAD(L); if (HEAD(L) != NIL) PREV(HEAD(L)) = x; HEAD(L) = x; PREV(x) = NIL; } 9 16 4 head(L) x 9 16 4 head(L)

連結リストからの削除 LIST_DELETE(L, x): L から x を削除 O(1) 時間 head(L) head(L) void LIST_DELETE(dllist *L, lobj *x) { if (PREV(x) != NIL) NEXT(PREV(x)) = NEXT(x); else HEAD(L) = NEXT(x); if (NEXT(x) != NIL) PREV(NEXT(x)) = PREV(x); } 9 16 4 head(L) x head(L) 9 4

双方向リストによる辞書の計算量 挿入 削除 キーの検索 常にリストの先頭に入れるので O(1) 時間 リストの要素を1つずつ見ていくので最悪 O(n) 時間 n: リスト長 (要素数) 既ソートリストでもリストの先頭から見ていくしか ないので O(n) 時間

一方向リストによる辞書の計算量 挿入 削除 キーの検索 常にリストの先頭に入れるので O(1) 時間 削除する要素のポインタが与えられても，リストの 1つ前の要素が分からないので O(n) 時間 キーの検索の際に，目的の要素の1つ前の要素を 求めるようにしておけば，削除は O(1) 時間 キーの検索 O(n) 時間