計数工学プログラミング演習 ( 第 6 回 ) 2017/05/16 DEPARTMENT OF MATHEMATICAL INFORMATICS 1
今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2
再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い 関数内部で宣言される変数は,CPU のスタック上に確保される int factorial(int n) { int x; if (n == 0) return 1; x = factorial(n-1); return n * x; 3
2 分探索木とは何か? 各節点は key, left, right, parent フィールドを持つ 2 分探索木条件 (binary-search-tree property) 節点 y が x の左部分木に属する key[y] key[x] 節点 y が x の右部分木に属する key[x] key[y] 2 5 3 7 3 5 7 8 2 5 8 5 4
2 分探索木の構造体 typedef struct node { struct node *left; // 左の子へのポインタ struct node *right; // 右の子へのポインタ struct node *parent; // 親へのポインタ searchkey_t key; // 探索に使うキー value_t value; // 付属値 node; typedef struct { node *root; // 根節点のポインタ tree; 5
2 分探索木に対する質問操作 質問操作は高さに比例した時間で終了する 探索 : 2 分探索木の中から, ある与えられたキーを持つ節点のポインタを求める ( 存在しなければ NULL) node *tree_search(node *x, searchkey_t k) { if (x == NULL k == x->key) return x; if (k < x->key) return tree_search(x->left,k); else return tree_search(x->right,k); 6
探索の正当性 キー k が見つかったら探索を終了する k が key(x) より小さい場合 2 分探索木条件より,k は x の右部分木にはない 左部分木に対して探索を続行する k が key(x) より大きい場合 右部分木に対して探索を続行する 探索する節点は根からのパスになる 実行時間は O(h) (h: 木の高さ ) 7
この場合の再帰は while ループにできる node *tree_search(tree *T, searchkey_t k) { node *x; x = T->root; // 根ノード while (x!= NULL && k!= x->key) { if (k < x->key) x = x->left; else x = x->right; return x; 8
今回はキーは文字列なので単純に比較できない key_cmp(x, y) 以下の値を返す関数とする x == y なら 0 x < y なら負の値 x > y なら正の値 node *tree_search(tree *T, searchkey_t k) { node *x; x = T->root; // 根ノード while (x!= NULL && key_cmp(k, x->key)!= 0) { if (key_cmp(k, x->key) < 0) x = x->left; else x = x->right; return x; 9
挿入と削除 要素を挿入 / 削除したあとも2 分探索木条件が満たされる必要がある 挿入は比較的簡単 削除は複雑 どちらも O(h) 時間 今回は削除は扱わない 10
挿入 5 z 6 3 7 y tree_insert(tree *T, node *z) { x 2 5 z 6 8 node *x, *y; y = NULL; x = root(t); while (x!= NULL) { // z を挿入する場所 x を決める y = x; if (key(z) < key(x)) x = left(x); 挿入場所は必ず葉 else x = right(x); // y は x の親 parent(z) = y; // z の親を y にする if (y == NULL) root(t) = z; // T が空なら z が根節点 else if (key(z) < key(y)) left(y) = z; // y の子を z にする else right(y) = z; 11
深さ優先探索, 幅優先探索 木やグラフの探索法 深さ優先探索 (depth-first search, DFS) 行き止まりになるまで先に進む 幅優先探索 (breadth-first search, BFS) 全体を同時に探索する DFSはスタック ( 再帰 ),BFSはキューで実現できる 1 2 5 1 2 3 3 4 6 4 5 6 DFS BFS 12
木の中間順巡回 木の中間順巡回 ( 通りがけ順, inorder tree walk) 根の左部分木に出現するキー集合 根のキー 右部分木に出現するキー集合の順にキーを出力 木の根から辿ると, 全てのキーをソートされた順序で出力できる この再帰は while ループにできない inorder_tree_walk(node *x) { if (x!= NIL) { inorder_tree_walk(left(x)); print(key(x)); inorder_tree_walk(right(x)); 2 5 3 13 THE 5UNIVERSITY OF TOKYO 2 5 3 5 7 7 8 8
void inorder_tree_walk(node *x) { if (x!= NULL) { inorder_tree_walk(x->left); printf("%s %s n",x->key, x->value); inorder_tree_walk(x->right); 14
その他の巡回法 先行順巡回 ( 行きがけ順, preorder tree walk): 根節点を先に出力し, 次に左右の部分木を出力 後行順巡回 ( 帰りがけ順, postorder tree walk): 先に左右の部分木を出力し, 最後に根節点を出力 PREORDER_TREE_WALK(node x) { if (x!= NIL) { print(key(x)); PREORDER_TREE_WALK(left(x)); PREORDER_TREE_WALK(right(x)); POSTORDER_TREE_WALK(node x) { if (x!= NIL) { POSTORDER_TREE_WALK(left(x)); POSTORDER_TREE_WALK(right(x)); print(key(x)); 15
課題 :2 分探索木を用いたソート 入力 : 標準入力から英単語と和訳のペアの集合を読み込む 出力 : 標準出力に, 単語のペアを英単語の辞書順に並べたものを出す int main(int argc, char *argv[]) { tree *T; node *x; char buf1[100], buf2[100]; char *eng, *jpn; T = allocate_tree(); while (1) { if (scanf(" %s %s", buf1, buf2) < 2) break; eng = strdup(buf1); jpn = strdup(buf2); x = allocate_node(eng, jpn); tree_insert(t, x); inorder_tree_walk(t->root); free_tree(t); return 0; 16
提出するソースコードの中に, 学生証番号, 氏名, メールアドレスをコメントとして書いておく 締切 : 2017 年 5 月 16 日 ( 火 ) 17:35 ( 演習終了時 ) 17
作成する関数 node *allocate_node(char *eng, char *jpn) 英語と日本語の文字列を持つノードを作る tree *allocate_tree(void) 空の木 T を作る (T-root == NULL) void tree_insert(tree *T, node *z) 木にノードを挿入 void inorder_tree_walk(node *x) 18
最終レポート 疎行列の 2 乗を計算し, 実行時間を測定する 入力は Matrix Market のデータを用いる http://math.nist.gov/matrixmarket/matrices.html 形式を変換したものを用意しています http://researchmap.jp/mub2jpgrp-1587/#_1587 ファイルから行列を読み込み, その 2 乗を計算しファイルに出力する./a.out < ( 入力 ) > ( 出力 ) 実行時間は time コマンドで測る time./a.out < bcspwr01.txt > bcspwr01-2.txt 19
実行時間のグラフを作る 行列のデータ構造や乗算アルゴリズムは複数用いてそれらの違いを調べる 密行列 (2 次元配列 ), 疎行列 ( リストの配列 ) など 疎行列でも乗算のアルゴリズムによって時間は異なる それぞれのデータ構造, アルゴリズムの概略も説明する 締切 :6/6( 火 ) 14:55 宛先 :miprogramming2017+final@gmail.com 20
レポートについての注意 メールの題名 : 学生証番号 8 桁ハイフンなし ( 半角スペース ) 氏名 ( 半角スペース ) 最終レポート提出 例 : 03150699 定兼邦彦最終レポート提出 添付ファイル : レポート ( 学生証番号 8 桁.pdf 5 枚以内 ) ソースコードを圧縮したもの ( 学生証番号 8 桁.zip) 例 : 03150699.pdf 例 : 03150699.zip レポートについて タイトル 所属 学生証番号 氏名 日付を一ページ目に書くこと ( 独立させたページにはしなくてよい 1. 課題内容 2. 手法 ( データ構造 アルゴリズム ) の説明 3. 結果 4. 考察の章立てで書くこと A4 5 枚以下に収めること 以下は本レポートに限らず留意のこと グラフにはタイトル 縦軸 横軸 ( 単位も ) 凡例を忘れずに 表のタイトルを忘れずに グラフ 表のタイトルは本文を読まなくても何が書いてあるかわかるように 21