酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2006年6月16日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html

プログラムとアルゴリズム 二分木と言った非線形なデータ構造と，これを扱うアルゴリズム，特に再帰的なアルゴリズムについて学ぶ つぎにハッシュやソートと言った良く利用されるデータ構造やアルゴリズムの概観を得る．

Ｅｕｃｌｉｄの互除法（２ページ 1.1） ｍをｎで割って、余りをｒとする。 ｒ＝０であれば、アルゴリズムは終了する。 このとき、ｎが最大公約数である。 ｍ←ｎとする（ｎの値をｍに代入する）。 次にｎ←ｒとして１に戻る。 ここでは、次の処理が使われている。 除算 ０との比較・分岐処理 変数への代入 繰り返し（ループ）

/* C言語によるgcdの例1 */ int gcd(int m, int n) { int r; 1: r = m % n; if (r == 0) goto 2; m = n; n = r; goto 1; 2: return n; } /* C言語によるgcdの例2 */ int gcd(int m, int n) { int r; while((r = m % n) != 0){ m = n; n = r; } return n; /* Java とほとんど同じ */ プログラムは、連接（文の並び順による評価）・条件分岐（たとえばif文）・繰り返し（例えばwhile文）だけで構成できるとされている。そもそも、gotoを使わないで書いたほうがわかりやすいことも多い。 そのような背景で、Javaのようにgotoを使えないプログラミング言語がある。

簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… 　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r1 ; 引数 m mov.w @(4,sp),r0 ; 引数 n 1: divxu.b r0l,r1 xor.b r2h,r2h mov.b r1h,r2l ; r = m % n beq 2f ; if(r == 0) goto 2 mov.w r0,r1 ; m = n mov.w r2,r0 ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数ｎ 引数ｍ 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。

レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。 　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r0 ; m mov.w @(4,sp),r1 ; n beq 1f ; if (n == 0) divxu.b r1l,r0 mov.b r0h,r0l xor r0h,r0h ; m % n push r0 push r1 bsr gcd adds.w #2,sp 1: rts ; return m .end 戻りアドレス 引数ｎ 引数ｍ 　ｂｓｒ直後のスタック ｓｐ＋１０ 　ｓｐ＋８ 　ｓｐ＋６ 　ｓｐ＋４ 　ｓｐ＋２ 　　　　ｓｐ 戻りアドレス 引数ｎ 引数ｍ 戻りアドレス 引数ｎ 引数ｍ レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

木構造 ルートとそれ以外の ノードにちょうど１つだけ の経路しか存在しない ルートノード 末端ノード エッジ ノード

二分木 データ 左 右 各ノードが持てる子 の数が高々２である木 順序木である

二分探索木 二分木を次のルールで作成 親よりも小さい値を持つ子は左 親よりも大きい値を持つ子は右 29 20 32 14 24 30 48 7 19 21 31

ノードの探索 ノード数をNとすると O(log N) の計算量で探索できる 木が偏っているときは 最悪O(N)になるが… 29 31 21 19 7 48 30 24 14 32 20

ハッシュテーブル データ キー１ キー２ キー３ ハッシュ関数

分離連鎖法 連結リスト ハッシュ テーブル

空き番地法 キー ハッシュ 再ハッシュ 再ハッシュ 既にデータが 格納されている ここも既にデータが 格納されている この場所は空なので ここに格納する

空き番地法を用いた場合の削除 キー 削除 削除したい ハッシュ 再ハッシュ 再ハッシュ 削除フラグを格納 同じハッシュ値だけど、これじゃない。 キー ハッシュ 再ハッシュ データは消えてるけど、これでもない。 削除 削除したい 削除フラグ 削除フラグを格納 再ハッシュ これだっ！ このデータを 探索したい

整列（ソート） (145ページ以降で詳しく) 配列を使用するソートアルゴリズム 空間計算量はいずれもO(N) バブルソート クイックソート 時間計算量O(N log N) 時間計算量は最悪でもO(N2) 空間計算量はいずれもO(N)

バブルソート ＞ 8 3 ＞ 10 8 ＞ 10 3 ＜ 8 10 ＞ 10 5 ＜ 10 15 ＞ 15 5 ＜ 10 15 ＞ 15 12 ＜ 15 32 ＞ 15 1 ＞ 32 12 ＞ 32 1 ＞ 15 6 ＞ 32 6 ＜ 15 24 ＞ 32 24 整列済み 10 1 8 3 15 5 32 12 6 24 10 8 8 3 10 3 10 5 15 5 15 12 15 1 32 12 32 1 15 6 32 6 24 32 24 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替え 入れ替え 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替え 残りも同様に整列させると… 10 1 8 3 15 5 32 12 6 24

クイックソート 基準値を決定 10 1 8 3 15 5 32 12 6 24 基準値を決定 10 8 3 5 1 6 15 32 12 24 ＜ 10 整列済み 基準値を決定 5 15 ＜ 3 1 8 6 12 32 24 10 5 15 ＜ 3 1 8 6 12 32 24 10 10 1 8 3 15 5 32 12 6 24

クイック ソート 32 24 15 12 10 8 6 5 3 1 5 24 15 12 10 8 6 3 1 ＜ 32 5 15 12 10 8 6 3 1 ＜ 32 24 5 12 10 8 6 3 1 ＜ 15 32 24 5 10 8 6 3 1 ＜ 15 12 32 24 5 8 6 3 1 ＜ 10 15 32 12 24 5 6 3 1 ＜ 10 8 15 32 12 24 5 3 1 ＜ 10 8 15 32 12 6 24 3 1 ＜ 10 8 15 5 32 12 6 24 1 ＜ 10 8 3 15 5 32 12 6 24 10 1 8 3 15 5 32 12 6 24