x - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第4回
実習用環境
• C言語
– 学習用Ｃ言語開発環境
http://9cguide.appspot.com/
• Fortran 90
– Self-extracting Windows x86
http://www.g95.org/downloads.shtml
http://ftp.g95.org/g95-MinGW.exe
2
集合を扱うデータ構造
•
•
•
•
集合：数学，計算機科学において基本的
動的集合：要素が追加/削除/変更される
集合に対して行う操作によってデータ構造を変える
行いたい操作によって最適なデータ構造が決まる
行う操作
データ構造
挿入，削除，
存在判定
挿入
最小要素の取出し
辞書
プライオリティー
キュー
3
動的集合の基本
• 各要素はオブジェクトとして表現される
• オブジェクトはキーと付属データからなる
• 集合の操作で扱うフィールドがあってもよい
– アルゴリズム内部でのみ用いられる
– 他のオブジェクトへのポインタなど
• キーは全順序を持つとする場合もある
4
動的集合に関する操作
1. 集合に関する情報を返す質問 (query)
•
•
•
•
•
SEARCH(S,k): key[x] = k である S の要素 x へのポ
インタを返す．存在しなければ NIL．
MINIMUM(T): 全順序集合 T において，最小のキー
を持つ要素を返す
MAXIMUM(T): 全順序集合 T において，最大のキー
を持つ要素を返す
SUCCESSOR(T,x): キーが x のキーの次に大きな
要素を返す．x が最大なら NIL.
PREDECESSOR(T,x): キーが x のキーの次に小さ
5
な要素を返す．x が最小なら NIL.
動的集合に関する操作
2. 集合を変える修正操作 (modifying operation)
•
•
•
•
INSERT(S,x): 集合 S に要素 x を加える．
DELETE(S,x): x へのポインタが与えられたとき，S
から x を取り除く．
SUCCESSOR，PREDECESSORは同じキー
が複数ある集合にも拡張される
集合操作を実行するのにかかる時間は集合の
サイズで測る
6
11.1 スタックとキュー
• 動的集合，挿入と削除をサポートする
• スタック (stack) では，DELETEでは最後に
挿入された要素が取り除かれる
– 後入れ先出し (last-in, first-out; LIFO) という
• キュー (queue) では，最初に挿入された要素
が取り除かれる
– 先入れ先出し (first-in, first-out; FIFO) という
7
スタック (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
8
配列によるスタックの実装
• 最大 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;
9
} 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];
10
}
その他の関数
• 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;
}
11
キュー (Queue)
• INSERT, DELETEの代わりにENQUEUE,
DEQUEUEと呼ぶ
• 人の並んだ列と同じ
– ENQUEUEでは列の最後に追加
– DEQUEUEでは列の先頭を取り出す
DEQUEUE(Q)
Q
15
6
2
ENQUEUE(Q,x)
9
12
配列によるキューの実装
• 最大 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
13
環状バッファ (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
14
空のキューの作成
• 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;
}
15
実装例
• 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;
注: オーバーフロー, アンダーフロー }
処理は省略してある
16
11.2 連結リスト (Linked Lists)
• オブジェクトをある線形順序に並べて格納する
データ構造
• 連結リストでの線形順序は，オブジェクトが含む
ポインタで決定される
• 双方向連結リスト (doubly linked list) L の要素
– キーフィールド key
– ポインタフィールド prev, next
– (付属データ)
key
head(L)
9
16
prev
next
NIL
4
17
• 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
18
リストの種類
• 一方向 (singly linked) と双方向 (doubly linked)
– 一方向のとき，各要素は prev を持たない
• 既ソート (sorted) と未ソート
– 既ソート: リストの線形順序はキーの線形順序に対応
– 未ソート: 任意の順序
• 循環 (circular list) と非循環
– 循環: リストの先頭要素の prev はリストの末尾を指し，
末尾の next はリストの先頭を指す
• 以下では未ソート双方向(連結)リストを扱う
19
双方向リストの構造体
• リストの要素
typedef struct lobj {
struct lobj *prev; // 前の要素へのポインタ
struct lobj *next; // 後の要素へのポインタ
data key;
// キー
} lobj;
• 双方向リスト
typedef struct {
lobj *head;
} dllist;
// 先頭要素のポインタ
20
省略記法
#define HEAD(L) (L->head)
#define KEY(x) (x->key)
#define NEXT(x) (x->next)
#define PREV(x) (x->prev)
#define NIL NULL
21
連結リストの探索
• 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
22
連結リストへの挿入
• 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
23
連結リストからの削除
• 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
24

Download Report