数理情報工学演習第一 C ( 第 8 回 ) 206/06/3 DEPARTMENT OF MATHEMATICAL INFORMATICS
今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 プライオリティキュー ヒープ 課題 : ヒープソート 2
プロトタイプ宣言 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int x, double y) { return (double)x * y; } int main() { double z; z = sub(, 2.5); // OK } int main() { int z; z = sub(, 2.5); // NG } double sub(int x, double y) { return (double)x * y; } 3
関数のプロトタイプ宣言 double sub(int x, double y); // 後 ( 下 ) に出てくる関数の型を示す int main() { double z; z = sub(, 2.5); // OK } double sub(int x, double y) { return (double)x * y; } 4
ヘッダーファイル ( 標準 ) ライブラリに入っている関数や定数が宣言してある #include <stdio.h> // 標準入出力ヘッダー int main() { printf( Hello. n ); // stdio.h 内で宣言してある } 5
stdio.h で宣言してあるもの FILE 構造体 fopen, fclose, fprintf, fscanf, NULL EOF 6
stdlib.h で宣言してあるもの malloc, free exit atoi, atof rand ( 乱数発生 ) qsort ( ソート ) bsearch (2 分探索 ) 7
プログラムの分割 つのファイルに全ての処理を書くと 長くて分かりにくい プログラムの再利用がしにくい ( 再コンパイルに時間がかかる ) まとまった処理ごとに分割してファイルを作る 行列演算 (matrix.c) 全体 (main.c) gcc main.c matrix.c 注 : それぞれのファイルは単独でコンパイルできるようにする ヘッダーファイルを使う 8
matrix.h の中身 typedef struct { int n,m; slist **R; } smatrix; smatrix *smatrix_read(file *fin); void smatrix_write(file *fout, smatrix *a); smatrix *smatrix_product(smatrix *A, smatrix *B); 9
matrix.c の中身 #include matrix.h // 構造体の定義を読み込む smatrix *smatrix_read(file *fin) { } // 関数の中身を書く void smatrix_write(file *fout, smatrix *a) { } // 自分で作ったファイルを読み込むときは で括る 0
main.c の中身 #include matrix.h // 構造体の定義や関数のプロトタイプ宣言 int main(int argc, char *argv[]) { smatrix *A, *B, *C; // smatrixは matrix.h で定義してある A = smatrix_read(stdin); B = smatrix_read(stdin); C = smatrix_product(a, B); smatrix_write(stdout, C); }
分割コンパイル 各ソースファイルを個別にコンパイルし, 最後に実行ファイルを作る gcc c o matrix.o matrix.c O3 #matrix.c のコンパイル gcc c o main.o main.c O3 #main.c のコンパイル gcc o main.out matrix.o main.o # リンク 修正したファイルだけ再コンパイルできる 注 : ヘッダーファイルを修正した場合, それをインクルードしている全てのソースファイルは再コンパイルする必要がある 自動化するには make コマンドを使用する 2
2 重インクルードの防止 ヘッダーファイル中で別のヘッダーファイルをインクルードする場合などに, 構造体等の宣言が 2 回出てくるとエラーになる 2 重インクルードを防止するために, ヘッダーファイル内にフラグを用意する #ifndef MATRIX_H // MATRIX_H が定義されていなければ以下が読まれる #define MATRIX_H // 回目に読まれたときに MATRIX_H を定義する // matrix.h の中身を書く #endif // #ifndef の行と対応 3
Tips 全ての関数は外部のオブジェクトファイル (.o) から参照できる 下手に名前をつけると, 名前の衝突が起きてしまう 外部で使用しない関数には static をつける // matrix.c static sub(smatrix *A) { } // matrix.c の外からは見えない smatrix *smatrix_transpose(smatrix *A) // 外から見える { smatrix *B; B = sub(a); // matrix.c 内ではsubは使える } 4
注意 domjudge に投稿する際は, 必要なファイルすべてを選択してアップロードする ファイルを分割した場合, インクルードファイル内でも stdio.h 等をインクルードしないとエラーになることがある 5
プライオリティキュー 要素の集合 S を保持するためのデータ構造 各要素はキーと呼ばれる値を持つ 次の操作をサポートする INSERT(S,x): S に要素 x を追加する MAXIMUM(S): 最大のキーを持つ S の要素を返す EXTRACT_MAX(S): 最大のキーを持つ S の要素を削除し, その値を返す 単純なキューは, 要素を入れた順番に出力するが, プライオリティキューでは優先度の高い順に出力する 6
ヒープ プライオリティキューはヒープで実現できる ヒープ : 完全 2 分木とみなせる配列 木の各節点は配列の要素に対応 木は最下位レベル以外の全てのレベルの点が完全に詰まっている 最下位のレベルは左から順に詰まっている 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 4 5 6 7 8 9 0 6 4 0 8 7 9 3 2 4 7
ヒープを表す構造体 typedef struct { int max_size; int size; heapdata *A; } heap; // 配列 A に格納できる最大要素数 // ヒープに格納されている要素の数 // 要素を格納する配列 typedef struct { ヒープに後から要素を追加する場合があるとき, int priority; 配列 A は大きいものを確保しておく value_t value; } heapdata; 8
max_size: 配列 A に格納できる最大要素数 size: H に格納されているヒープの要素数 size max_size 木の根 : A[] 節点の添え字が i のとき 親 PARENT(i) = i / 2 左の子 LEFT(i) = 2 i 右の子 RIGHT(i) = 2 i + 木の高さは (lg n) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 9
ヒープ条件 (Heap Property) 根以外の任意の節点 i に対して A[PARENT(i)].priority A[i].priority つまり, 節点の値はその親の値以下 ヒープの最大要素は根に格納される 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 20
ヒープの操作 heapify: ヒープ条件を維持する. build: 入力の配列からヒープを構成する. O(n) 時間. heapsort: 配列をソートする. O(n lg n) 時間. extract_max: ヒープの最大値を取り出す. O(lg n) 時間. insert: ヒープに値を追加する. O(lg n) 時間. 2
ヒープ条件の維持 heapify(h,i): A[i] を根とする部分木がヒープになるようにする. ただし LEFT(i) と RIGHT(i) を根とする 2 分木はヒープと仮定. void heapify(heap *H, int i) { int l, r, largest, size; heapdata *A; A = H->A; size = H->heap_size; l = LEFT(i); r = RIGHT(i); if (l <= size && A[l].priority > A[i].priority) largest = l; // A[i] と左の子で大きい else largest = i; // 方をlargestに if (r <= size && A[r].priority > A[largest].priority) // 右の子の方が大きい largest = r; if (largest!= i) { heap_swap(h, i, largest); // A[i] を子供と入れ替える heapify(h, largest); } } 22
heapify(a,2) 6 4 0 4 5 6 7 4 7 9 3 8 9 0 2 8 heapify(a,4) 6 4 0 4 5 6 7 4 7 9 3 8 9 0 2 8 heapify(a,9) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 23
ヒープの構築 heapify では左右の部分木がヒープである必要がある 全体をヒープにするには,2 分木の葉の方からヒープにしていけばいい HEAP *heap_build(int n, data *A, int max_size) { int i; HEAP *H; mymalloc(h, ); H->max_size = max_size; H->size = n; H->A = A; for (i = n/2; i >= ; i--) { heapify(h,i); } } 24
A 4 3 2 6 9 0 4 8 7 4 4 3 5 6 7 8 2 9 0 6 9 0 4 8 7 heapify(a,5) 4 3 4 5 6 7 4 6 9 0 8 9 0 2 8 7 heapify(a,3) 4 3 4 5 6 7 2 6 9 0 8 9 0 4 8 7 heapify(a,4) 4 0 4 5 6 7 4 6 9 3 8 9 0 2 8 7 heapify(a,2) 25
4 6 0 4 5 6 7 4 7 9 3 8 9 0 2 8 heapify(a,) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 26
extract_max ( 最大値を取り出す ) 最大値 ( のうちのつ ) は必ずヒープの根にある A[] を取り出せばいい 取り出した後もヒープ条件を満たすようにしたい A[] の左右の子はヒープになっている A[n] を削除してもヒープになっている A[n] を A[] に上書きして, サイズを 減らす heapify(h, ) を行えばヒープ条件を満たす 27
ヒープへの挿入 sizeをつ増やし, 新しい要素を配列の末尾に追加する 末尾の要素とその親節点の間でヒープ条件が満たされていない可能性がある 満たされていなければ両者を入れ替える 親節点の値が大きくなったので, その親でヒープ条件を調べる 最悪時は根まで入れ替える必要あり 6 O(log n) 時間 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 2 28
ヒープソート まずヒープを作る すると最大要素が A[] に入る extract_max をすると最大要素を取り除いたヒープができる 最大要素をA[n] に入れる これを繰り返す 注意 : ヒープは添字が から n なので, データを配列に読み込むときは注意 29
6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 0 8 9 4 5 6 7 4 7 3 8 2 4 6 4 8 0 4 5 6 7 4 7 9 3 8 9 2 6 9 8 3 4 5 6 7 4 7 2 0 4 6 30
8 4 7 5 6 3 7 4 4 5 3 4 2 9 2 8 9 0 4 6 0 4 6 4 4 2 3 3 2 7 8 9 4 7 8 9 0 4 6 0 4 6 3
2 2 3 2 3 4 7 8 9 4 7 8 9 0 4 6 0 4 6 A 4 7 8 9 0 4 6 32
計算量 heap_build: O(n) 時間 heapify: O(n lg n) 時間 全体で O(n lg n) 時間 33
課題 ヒープを用いて (priority, value) のペアを priority でソートするプログラム priority は整数 value は文字列 入力は標準入力から 行目はデータ数 n ( 整数 ) 2 行目から n+ 行目までは整数 (priority) 文字列 (value) のペア 出力は標準出力に i 行目はpriorityが小さい順で i 番目のデータ priority value のペアを出力 ( 整数と文字列は半角スペースつで区切る ) 34
ヒープを処理する関数を記述する heap.c, ヘッダーファイル heap.h, メイン関数を記述する main.c に分割する 提出するソースコードの中に, 学生証番号, 氏名, メールアドレスをコメントとして書いておく 締切 : 206 年 6 月 3 日 ( 月 ) 6:00 ( 演習終了時 ) 35