付録: プログラム集（Ｃ版） 　これらのプログラムの作成については，玉井浩先生（大妻女子大学）の全面的 協力が得られた。 1. 検索プログラム(1) 　まず逐次検索法(Sequential Search，Linear Probing) に基づく，データに重複がない場合の 検索プログラムを示す． 目的：X[j] = key をみたすj（もしあれば）を探す． 使用法：関数search(key)を実行すると，その値は 　　　　X[j] = keyをみたすj がある場合はそのj， 　　　　そのようなj がないときは-1 となる． 前提： [１]データ数をnとし，データは，X[0]，… ，X[n - 1]に格納されている．また，X[n]を作業用に 使用して差し支えない． [２]データに重複はないものとし，keyに等しいデータがひとつ見つかったらそこで検索をやめる． [３]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ int search(double key); void main(void) { double key; nの設定 Xの設定（X[0]，… ，X[n - 1]にデータを入れる） keyの設定 search(key)の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- int search(double key) { int j; X[n] = key; for (j = 0; X[j] != key; j++) ; return j < n ? j : -1; } ------------------------------------------------------------------------ 2. 検索プログラム(2) 　データに重複がある場合の逐次検索法プログラムを示す． 目的：X[j] = keyをみたすj（もしあれば）を探す． 使用法：主プログラムでj = -1とおいてからsrch2(key)を実行すると，関数の値は， 　　　　X[j] = keyをみたすjがある場合はそのj， 　　　　そのようなj がないときは-1 となる． 　関数の値が-1でないときは，繰り返しsrch2を実行すると，表Xのさらに先を検索してくれる． ただしその場合は，jの値を変えてはいけない．-1にするとまた表の最初から検索を始めてしま う． 前提： [１]データ数をnとし，データは，X[0]，… ，X[n - 1]に格納されている．また，X[n]を作業用に 使用して差し支えない． [２]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ int j; int srch2(double key); void main(void) { double key; nの設定 Xの設定（X[1]，… ，X[n]にデータを入れる） keyの設定 j = -1; srch2(key)の呼び出し，結果の出力等 次のsrch2(key)の呼び出し，結果の出力等 … } ----- プログラム ------------------------------------------------------- int srch2(double key) { X[n] = key; while (X[++j] != key) ; return j < n ? j : -1; } ------------------------------------------------------------------------ 3. 検索プログラム(3) 　2分検索法(Binary Search) に基づくプログラムを示す．データは大きさの昇順に，配列Xに格 納されているものとする． 目的：X[j] = keyをみたすj（もしあれば）を探す． 使用法：関数bsrch(key)の計算を実行すると，その値は 　　　　X[j] = keyをみたすj がある場合j， 　　　　そのようなj がないときは-1 となる． 前提： [１]データ数をnとし，データは，X[0]，… ，X[n - 1]に格納されている． [２]データに重複はないものとし，keyに等しいデータがひとつ見つかったらそこで検索をやめる． [３]配列Xの内容は昇順に整列されている： 　　　　X[0] ≦ … ≦ X[n - 1]． ＜注意＞前提[３]が必要なので，逐次検索法より応用範囲は狭まる．そのかわりデータ数n が大き いとき，検索速度は桁違いに速くなる． [４]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ int bsrch(double key); void main(void) { double key; nの設定 Xの設定（X[0]，… ，X[n - 1]にデータを昇順に入れる． 　　　　　　　　　　 すなわち，X[0] ≦ … ≦ X[n - 1]となるようにする．） keyの設定 bsrch(key)の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- int bsrch(double key) { int j, left, right; left = 0; right = n - 1; while (left < right) { j = (left + right) / 2; if (X[j] < key) left = j + 1; else right = j; } return X[right] == key ? right : -1; } ------------------------------------------------------------------------ 4. 検索プログラム(4) 　ハッシュ法に基づく検索プログラムを示す． 目的：H[j] = keyをみたすj（もしあれば）を探す． 使用法：関数hsrch(key) の計算を実行すると，その値は 　　　　H[j] = keyをみたすj がある場合j ， 　　　　そのようなjがないときは-1 となる． 前提： [１]データkeyを0以上m未満の整数値に変換する関数hash(key)が宣言されている． [２]検索の対象となるn 個のデータは，ハッシュ表H[0]，…,H[m - 1] の中に，ある特別のしかた でおさめられている（ここでm > n）． ＜注意＞ハッシュ表Hを作成するためのプログラムhtableは，すぐあとに示す（「5．ハッシュ表 の作成」）． [３]データはすべて，-999.0とは異なる実数値であり，表Hの空欄には-999.0が書き込まれている． [４]全体のプログラムはおよそ次の形になる． #define EMPTY -999.0 /* 「空欄」 */ double H[200]; int n; /* データ数 */ int m; /* ハッシュ表の大きさ */ int hsrch(double key); void main(void) { double key; nの設定 mの設定（m＞n） Hの設定（H[0]，… ，H[m - 1]にn個のデータを入れる．ただし， 　　　　　　　　　　 空欄にはEMPTYが入っている．） keyの設定 hsrch(key)の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- int hash(double key); int hsrch(double key) { int j; j = hash(key); while (1) { if (H[j] == key) return j; if (H[j] == EMPTY) return -1; if (++j == m) j = 0; } } ------------------------------------------------------------------------ 5. ハッシュ表(Hash Table)の作成 目的：与えられたデータから，ハッシュ関数hashに基づき，ハッシュ表Hを作成する． 使用法：検索の対象となるデータを配列Xに入力してから，このプロシージャhtableを実行する と，Xの内容が表Hに写され，前の関数プログラムhsrchが使えるようになる． 前提： [１]データ数n，データX[0], …, X[n - 1]，および表Hの大きさm（m ＞ n）は設定されている． [２]データはすべて，-999.0とは異なる実数値である． ＜注意＞-999.0は「空欄を表す記号」として利用されるので，データとして使われない値であり さえすれば何でもよい．データの型は変更できるが，(-999.0に代わる) 「空欄を表す記号」が 何かひとつ必要である． [３]全体のプログラムはおよそ次の形になる． #define EMPTY -999.0 /* 「空欄」 */ double X[100]; double H[200]; int n; /* データ数 */ int m; /* ハッシュ表の大きさ */ void htable(void); void main(void) { nの設定 Xの設定（X[0]，… ，X[n - 1]にn個のデータを入れる．） mの設定（m ＞ n） htable()の呼び出し } ----- プログラム ------------------------------------------------------- int hash(double key); void htable(void) { int i, k; for (k = 0; k < m; k++) H[k] = EMPTY; for (i = 0; i < n; i++) { k = hash(X[i]); while (H[k] != EMPTY) if (++k == m) k = 0; H[k] = X[i]; } } ------------------------------------------------------------------------ 6. 整列プログラム(1) 　最小値選択法(Minimum Selection Sort)に基づくプログラムを示す． 目的：配列X の中の数値を小さい順に並べ換える． 使用法：プロシージャminselを実行すれば，配列Xの内容が小さい順になるように並べ換えられ る． 前提： [１]データ数をnとし，データは，X[0]，… ，X[n - 1]に格納されている． [２]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ void minsel(void); void main(void) { nの設定 Xの設定（X[0]，… ，X[n - 1]にデータを入れる） minsel()の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- void exchange(int p, int q); void minsel(void) { int i, j, k; for (i = 0; i < n; i++) { k = i; for (j = i + 1; j < n; j++) if (X[k] > X[j]) k = j; exchange(i, k); } } void exchange(int p, int q) { double y; y = X[p]; X[p] = X[q]; X[q] = y; } ------------------------------------------------------------------------ 7. 整列プログラム(2) 　直接挿入法(Straight Insertion)に基づくプログラムを示す． 目的：配列X の中の数値を小さい順に並べ換える． 使用法：プロシージャstraightを実行すれば，配列Xの内容が小さい順になるように並べ換えら れる． 前提： [１]データ数をnとし，データは，X[1]，… ，X[n]に格納されている．また，X[0]を作業用に使用 して差し支えない． [２]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ void straight(void); void main(void) { nの設定 Xの設定（X[1]，… ，X[n]にデータを入れる） straight()の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- void straight(void) { int i, j; for (i = 2; i <= n; i++) if (X[i - 1] > X[i]) { X[0] = X[i]; j = i; while (X[--j] > X[0]) X[j + 1] = X[j]; X[j + 1] = X[0]; } } ------------------------------------------------------------------------ 8. 整列プログラム(3) 　ヒープ法に基づくプログラムを示す． 目的:配列Xの中の数値を小さい順に並べ換える． 使用法:プロシージャheapsortを実行すれば，配列Xの内容が小さい順になるように並べ換えられ る． 前提： [１]データ数をnとし，データは，X[1]，… ，X[n]に格納されている．また，X[0]を作業用に使用 して差し支えない． [２]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ void heapsort(void); void main(void) { nの設定 Xの設定（X[1]，… ，X[n]にデータを入れる） heapsort()の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- void siftup(int left); void sift2(int right); void heapsort(void) { int m, k; m = n / 2; for (k = m; k > 0; k--) siftup(k); X[0] = X[n]; X[n] = X[1]; for (k = n - 1; k > 2; k--) { sift2(k); X[0] = X[k]; X[k] = X[1]; } if (X[0] <= X[2]) X[1] = X[0]; else { X[1] = X[2]; X[2] = X[0]; } } void siftup(int left) { int j; double y; y = X[left]; L100: j = left + left; if (j < n) { if (X[j] < X[j + 1]) j++; } else if (j > n) goto L200; if (X[j] > y) { X[left] = X[j]; left = j; goto L100; } L200: X[left] = y; } void sift2(int right) { int i, j; i = 1; L100: j = i + i; if (j < right) { if (X[j] < X[j + 1]) j++; } else if (j > right) goto L200; X[i] = X[j]; i = j; goto L100; L200: j = i / 2; if (X[j] < X[0]) { X[i] = X[j]; i = j; goto L200; } X[i] = X[0]; } ------------------------------------------------------------------------ 9. 整列プログラム(4) 　クイック法に基づくプログラムを示す． 目的：配列X の中の数値を小さい順に並べ換える． 使用法：プロシージャqsortを実行すれば，配列Xの内容が小さい順になるように並べ換えられる． なお，straightも利用する． 前提： [１]データ数をnとし，データは，X[1]，… ，X[n]に格納されている．また，X[0]を作業用に使用 して差し支えない． [２]全体のプログラムはおよそ次の形になる． double X[100]; int n; /* 実際の要素数 */ int k; /* 左区間の右端 */ void qsort(void); void main(void) { nの設定 Xの設定（X[1]，… ，X[n]にデータを入れる） qsort()の呼び出し，結果の出力等 } ----- プログラム ------------------------------------------------------- void quick(int left, int right); void partition(int left, int right, double b); void straight(void); void qsort(void) { quick(1, n); straight(); } void quick(int left, int right) { int center; double bnd; if (right - left > 10) { center = (left + right) / 2; bnd = (X[left] + X[center] + X[right]) / 3; if (X[right] < bnd) { X[0] = X[left]; X[left] = X[right]; if (X[0] >= bnd) X[right] = X[0]; else { X[right] = X[center]; X[center] = X[0]; } } else if (X[left] > bnd) { X[0] = X[left]; X[left] = X[center]; X[center] = X[0]; } partition(left, right, bnd); quick(left, k); quick(k + 1, right); } } void partition(int left, int right, double bnd) { double y; y = X[right]; L100: while (X[++left] < bnd) ; X[right] = X[left]; while (X[--right] > bnd) ; if (left < right) { X[left] = X[right]; goto L100; } X[left] = y; k = left == right ? left - 1 : right; } ------------------------------------------------------------------------ ＜注意＞分割後の，左側のブロックの右端の番号を変数kにおいているが，これをプロシージャq uickに正しく伝えるために，変数kを大域的に宣言している． 10. 整列プログラム(5) 　分配法(Distributive Sorting) に基づき，得点の整列と出力を行うプログラムを示す． 目的：得点が記録されている配列Tの内容を，大きい順に，順位と共に出力する（xxページ参照）． 使用法：プロシージャdprint(n) を実行すると，配列Tの中のn人ぶんの得点が大きい順に，順位 と共に出力される． 前提： [１]得点は0以上，700以下の整数値である． [２]得点は，T[1], …, T[n]にすでに記録されている． [３]全体のプログラムはおよそ次の形になる． int T[1000]; void dprint(int n); void main(void) { int n; nの設定 Tの設定（T[1]，… ，T[n]にデータを入れる） dprint(n)を呼ぶと，Tの内容が大きい順に，順位と共に出力される } ----- プログラム ------------------------------------------------------- void dprint(int n) { int J[701]; int i, point, rank, rr; printf("順位 番号 得点\n"); for (point = 0; point <= 700; point++) J[point] = 0; for (i = n; i > 0; i--) { point = T[i]; T[i] = J[point]; J[point] = i; } rr = 0; for (point = 700; point >= 0; point--) { i = J[point]; rank = rr + 1; while (i > 0) { printf("%5d%6d%6d\n", rank, i, point); rr++; i = T[i]; } } } ------------------------------------------------------------------------ 11 ．整列プログラム(6) 　実数値に対する分配法のプログラムを示す． 目的：配列Xの中の数値を小さい順に，配列Yの中に移す． 使用法：プロシージャdsortを実行すれば，配列Xの内容が小さい順に配列Yに移る． 前提： [１]実数値配列X，Y，整数値配列T，J，および整数変数nは大域的に宣言されている．これらの配 列の最大の添え字（番号）はどれも同じである． ＜注意＞配列T，Jはdsortの中で宣言してもよいが，最大添え字に注意が要る． [２]直接挿入法のプログラムstraight（ただし配列名XをYに書き換えたもの）を利用する． [３]Xの内容とデータの個数nの値はすでに設定されている． [４]n個のデータは「すべて同じ」ではない． [５]X[0] が自由に使える（そのように宣言されていて，そこにはデータは入っていない）． [６]全体のプログラムはおよそ次の形になる． #define MAX 100 double X[MAX], Y[MAX]; int T[MAX], J[MAX]; int n; /* 実際の要素数 */ void dsort(void); void main(void) { nの設定 Xの設定（X[1]，… ，X[n]にデータを入れる） dsort()の呼び出し，結果(Y)の出力等 } ----- プログラム ------------------------------------------------------- void straight(void); void dsort(void) { int i, j, k, imax, imin; double d; imax = imin = 1; for (i = 2; i <= n; i++) if (X[i] > X[imax]) imax = i; else if (X[i] < X[imin]) imin = i; d = (n - 0.1) / (X[imax] - X[imin]) ; for (i = 1; i <= n; i++) T[i] = (int)(d * X[i]) + 1 ; for (k = 1; k <= n; k++) J[k] = 0; for (i = 1; i <= n; i++) { k = T[i]; T[i] = J[k]; J[k] = i; } j = 0; for (k = 1; k <= n; k++) { i = J[k]; while (i > 0) { Y [++j] = X[i]; i = T[i]; } } straight(); } ------------------------------------------------------------------------ 12. 文字列照合プログラム 　ボイヤー・ムーアの方法に基づくプログラムを示す． 目的：文字列「パターン」が，文字列「テキスト」のどこに現れるかを調べる． 使用法：テキストとパターンを設定し，プロシージャBM()を実行すると，テキストの中のパター ンの位置と「テキスト中にパターンが現れた回数」が出力される． 例：　　テキスト　［文字位置］ 0 1 2 3 4 5 6 7 8 9 10 ［文　　字］ A B R A C A D A B R A パターン ［文字位置］ 0 1 2 ［文　　字］ B R A に対してBM()を実行すると，次のような出力が得られる． 　　　　あった: i = 1 　　　　あった: i = 8 　　　　パターンの出現回数 = 2 前提： [１]文字列は，Ｃの慣例に従ってcharの配列で表し，ナル文字(\0)で終わるものとする． [２]文字列を表す配列Txtとptnは大域的に宣言されている．テキストはTxtに，パターンはptnに， すでに設定されている． [３]パターンの長さは256 以下である． ＜注意＞これは本質的な制限ではなく，配列DD の宣言を修正すればいくらでも変更できる． [４]全体のプログラムはおよそ次の形になる． char Txt[1001], ptn[257]; void BM(void); void main(void) { Txtにテキストを設定 ptnにパターンを設定 BM(); } ----- プログラム ------------------------------------------------------- void BM(void) { int i, j, k, m, n, max, count; int D[256], DD[256]; m = strlen(ptn); n = strlen(Txt); /* 表D，DDの作成 */ for (j = 0; j < 256; j++) D[j] = m; for (j = 0; j < m - 1; j++) D[ptn[j]] = m - j - 1; D[ptn[m - 1]] = n + m; max = ptn[0] == ptn[m - 1] ? m - 1 : m; for (k = 0; k < m; k++) DD[k] = max; for (i = 1; i < m - 1; i++) if (ptn[i] == ptn[m - 1]) { k = 0; L20: if (ptn[i - k - 1] == ptn[m - k - 2]) { if (++k < i) goto L20; for (j = k + 1; j < m; j++) DD[j] = m - i - 1; } DD[k] = m - i - 1; } /* 照合開始　*/ count = 0; j = m - 1; L100: while (j < n) j += D[Txt[j]]; if (j >= n + m) { j -= n + m; for (k = 0; k < m - 1; k++) if (Txt[j - k - 1] != ptn[m - k - 2]) goto L50; printf("あった: i = %d\n", j - m + 1); count++; L50: j += DD[k]; if (j < n) goto L100; } printf("パターンの出現回数 = %d\n", count); } ------------------------------------------------------------------------ 13. nクイーン問題の解を求めるプログラム 　バックトラッキングによって解を求めるプログラムを示す． 目的：nクイーン問題の 　　　　解の個数， 　　　　90°回転対称な解の個数， 　　　　180°回転対称な解の個数， 　　　　解の種類の数 を求める． 使用法：このプログラムを実行し，サイズnを入力すると，上の数値が出力される． 前提： [１]nは20以下でなければならない． ＜注意＞配列の宣言を修正すれば，もっと大きいサイズnを扱える．ただし，nが大きくなると所 要時間が飛躍的に増大するので注意すること． ----- プログラム ------------------------------------------------------- #include void main(void) { int P[21], R[21]; int A[41], B[41]; int S[21], T[21]; int i, j, k, n, half; long count, d1, d2; /* 初期設定 */ printf("サイズn（≦20）を入力して下さい: n ="); scanf("%d", &n); count = d1 = d2 = 0; half = (n + 1) / 2; for (j = 1; j <= n; j++) { R[j] = 0; S[j] = j + 1; T[j] = j - 1; } S[0] = 1; T[0] = -1; for (k = 1; k < 2 * n; k++) A[k] = B[k] = 0; /* 解の探索開始 */ i = 0; /* 次の行に進む */ L100: i++; j = 0; /* 次の列に進む */ L200: j = S[j]; if (j > n) goto L300; k = R[j] + A[i - j + n] + B[i + j - 1]; if (k > 0) goto L200; P[i] = j; if (i == n) goto L250; R[j] = A[i - j + n] = B[i + j - 1] = 1; S[T[j]] = S[j]; T[S[j]] = T[j]; goto L100; /* 解がひとつ見つかった */ L250: count++; for (k = 1; k <= half; k++) if (P[k] + P[n - k + 1] != n + 1) goto L300; d2++; for (k = 1; k <= half; k++) if (k + P[P[k]] != n + 1) goto L300; d1++; /* バックトラッキング */ L300: if (--i > 0) { j = P[i]; R[j] = A[i - j + n] = B[i + j - 1] = 0; S[T[j]] = j ; T[S[j]] = j ; goto L200; } /* 答の出力 */ printf("解の個数= %ld\n", count); printf("90°回転対称な解= %ld\n", d1); printf("180°回転対称な解= %ld\n", d2) ; printf("解の種類の数= %ld\n", (count + 2 * d1 + d2) / 8); } ------------------------------------------------------------------------ - 1 -