x - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第5回
11.1 スタックとキュー
• 動的集合，挿入と削除をサポートする
• スタック (stack) では，DELETEでは最後に挿
入された要素が取り除かれる
– 後入れ先出し (last-in, first-out; LIFO) という
• キュー (queue) では，最初に挿入された要素
が取り除かれる
– 先入れ先出し (first-in, first-out; FIFO) という
2
スタック (Stack)
• INSERT, DELETEの代わりにPUSH, POPと呼ぶ
– PUSH(S,x): 集合 S に要素 x を加える．
– POP(S): S から最後に PUSH された要素を削除し，
その要素を返す
PUSH(S,15)
POP(S) 15
692
9
2
6
15
3
配列によるスタックの実装
• 最大 MAX 要素を格納できるスタックを実装
• スタックを表す構造体
– top: 最後に挿入された要素の格納場所(= 要素数)
– S: 要素を格納するサイズMAXの配列(へのポインタ)
– MAX: 配列 S のサイズ
typedef int data;
• 要素は S[1..top] に格納される
– S[1]: スタックの底
– S[top]: スタックの最上部
– top  MAX
typedef struct {
int top;
int MAX;
data *S;
4
} stack;
実装例
• PUSH(S,x)
– topを1増やし，x を配
列に入れる
– topがMAXを超えたら
エラー
– 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;
}
• POP(S)
– スタックが空ならエラー
– サイズを1減らし，最上部
の要素を返す
– O(1) 時間
data POP(stack *s)
{
if (STACK_EMPTY(s)) {
printf("アンダーフロー\n");
exit(1);
}
s->top = s->top - 1;
return s->S[s->top + 1];
5
}
その他の関数
• STACK_EMPTY(S)
– スタックが空なら1を返す
– O(1) 時間
int STACK_EMPTY(stack *S)
{
if (S->top == 0) return 1;
else return 0;
}
• MAKE_STACK(size)
– 最大サイズ size のスタッ
クを作成する
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;
}
6
キュー (Queue)
• INSERT, DELETEの代わりにENQUEUE,
DEQUEUEと呼ぶ
• 人の並んだ列と同じ
– ENQUEUEでは列の最後に追加
– DEQUEUEでは列の先頭を取り出す
DEQUEUE(Q)
Q
15
6
2
ENQUEUE(Q,x)
9
7
配列によるキューの実装
• 最大 MAX1 要素を格納できるキュー
typedef struct {
• キューを表す構造体
–
–
–
–
int head;
int tail;
int MAX;
data *Q;
} queue;
Q: 要素を格納する配列
MAX: 配列 Q のサイズ
head: キューの先頭の位置
tail: 次に追加される位置
1
2
3
4
5
6
7
8
15 6
head
9 10 11 12
9
8
4
tail
8
環状バッファ (Ring Buffer)
• 配列 Q の右端と左端はつながって輪になっている
と考える
• Q[MAX] の右は Q[1] だとみなす
• 要素は Q[head..MAX] Q[1..tail1] に格納される
• DEQUEUEの際に全要素を左にずらす必要がない
1
2
3
5
tail
3
4
5
6
7
8
15 6
head
9 10 11 12
9
8
4 17
9
空のキューの作成
• 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;
}
10
実装例
• ENQUEUE(Q,x)
– x をQ[tail]に入れる
– tailを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;
}
• DEQUEUE(Q)
– Q[head]を取り出す
– headを1増やす
– O(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
11.2 連結リスト (Linked Lists)
• オブジェクトをある線形順序に並べて格納する
データ構造
• 連結リストでの線形順序は，オブジェクトが含む
ポインタで決定される
• 双方向連結リスト (doubly linked list) L の要素
– キーフィールド key
– ポインタフィールド prev, next
– (付属データ)
key
head(L)
9
16
prev
next
NIL
4
12
• next(x): リスト中の x の直後の要素のポインタ
– next(x) = NIL のとき，x は最後の要素
• prev(x): x の直前の要素のポインタ
– prev(x) = NIL のとき，x はリストの最初の要素
• head(L): リストの先頭の要素のポインタ
– head(L) = NIL のとき，リストは空
NIL
head(L)
9
16
prev
4
13
リストの種類
• 一方向 (singly linked) と双方向 (doubly linked)
– 一方向のとき，各要素は prev を持たない
• 既ソート (sorted) と未ソート
– 既ソート: リストの線形順序はキーの線形順序に対応
– 未ソート: 任意の順序
• 循環 (circular list) と非循環
– 循環: リストの先頭要素の prev はリストの末尾を指し，
末尾の next はリストの先頭を指す
• 以下では未ソート双方向(連結)リストを扱う
14
双方向リストの構造体
• リストの要素
typedef struct lobj {
struct lobj *prev; // 前の要素へのポインタ
struct lobj *next; // 後の要素へのポインタ
data key;
// キー
} lobj;
• 双方向リスト
typedef struct {
lobj *head;
} dllist;
// 先頭要素のポインタ
15
省略記法
#define HEAD(L) (L->head)
#define KEY(x) (x->key)
#define NEXT(x) (x->next)
#define PREV(x) (x->prev)
#define NIL NULL
16
連結リストの探索
• LIST_SEARCH(L, k): リスト L に属する，キー k を
持つ最初の要素のポインタを返す
• キー k を持つ要素が存在しなければ NIL を返す
lobj *LIST_SEARCH(dllist *L, data k)
• (n) 時間
{
lobj *x;
x = HEAD(L);
while (x != NIL && KEY(x) != k) {
x = NEXT(x);
}
return x;
}
head(L)
9
16
4
17
連結リストへの挿入
• LIST_INSERT(L, x): x を L の先頭に挿入
– x のキーは既にセットされているとする
• O(1) 時間
x
9
head(L)
head(L)
9
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;
}
16
4
16
4
18
連結リストからの削除
• LIST_DELETE(L, x): L から x を削除
• O(1) 時間
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);
}
head(L)
9
head(L)
9
x
16
4
4
19
双方向リストによる辞書の計算量
• 挿入
– 常にリストの先頭に入れるので O(1) 時間
• 削除
– 削除する要素のポインタが与えられれば O(1) 時間
• キーの検索
– リストの要素を1つずつ見ていくので最悪 O(n) 時間
n: リスト長 (要素数)
– 既ソートリストでもリストの先頭から見ていくしか
ないので O(n) 時間
20
一方向リストによる辞書の計算量
• 挿入
– 常にリストの先頭に入れるので O(1) 時間
• 削除
– 削除する要素のポインタが与えられても，リストの
1つ前の要素が分からないので O(n) 時間
– キーの検索の際に，目的の要素の1つ前の要素を
求めるようにしておけば，削除は O(1) 時間
• キーの検索
– O(n) 時間
21

Download Report