探索と整列はアルゴリズムの基本
たくさんのデータ群から1つのデータを見つけ出す「探索」（サーチ）処理を試してみましょう。探索は、前回紹介した整列（ソート）と並ぶアルゴリズムの二本柱と言えます。
探索は整列より簡単
例えば10枚のカードの中から特定の1枚を見つけるような処理は、整列と同じように、人間であればいとも簡単に結果を出せます。しかしコンピュータでは、やはり整列のときと同じように、その処理手順を整理して論理的に組み立てる必要があります。
今回は、図1のようにΙ桁の整数が書かれた7枚のカードの中から「7」のカードを探す処理を考えてみましょう。人間がこの処理を行う場合、単に「カードを見つけた！」で終わってしまいます。カルタのように、見つけたカードを手で押さえるなり取り上げるなりするかもしれません。
しかしコンピュータでは、見つけたことを示すための処理も必要になります。ここでは、「見つけたカードが先頭（左端）から何枚目にあるのか」を表示させることにしましょう。
 図1：7枚のカードの中から「7」を探す
先頭から順に比較していく
見つけたカードが何枚目に存在するのかを示すには、やはり整列の場合と同じようにカードを配列として扱う必要があります。Cの配列は添字が0から始まるので、一般的な「1から始まる形」にするため、添字に1を加算しなければなりません。そのための処理については、Cのソースを紹介するときに説明します。
整列ではカードの並び順を入れ替えなければなりませんでしたが、探索処理では単純に見つかったカードの位置（何枚目か）を示すだけで済みます。したがって、整列に比べて処理の仕組みは単純なものになります。
最もシンプルな処理の手順を考えてみましょう。
1枚目(3)と比較
7≠3 → 違うので次へ
2枚目(6)と比較
7≠6 → 違うので次へ
3枚目(2)と比較
7≠2 → 違うので次へ
4枚目(7)と比較
7＝7 → 同じなので探索完了
見つかった位置（4枚目）を記録
このように、先頭から順に値を比較していって、探索値と被探索値が同じであれば処理は完了──という、実にシンプルな構造となります。このような探索処理を「逐次探索」と言います。
逐次探索をプログラミングする
上述の処理手順をCのプログラムにしてみましょう。やはり、各カードの並びを配列にして、見付かった位置を『配列の何番目か』で表すことになります。
では、この処理手順をCのプログラムにしてみましょう。リスト1のようになります。
処理を単純化するため、配列の各要素の値を固定し、そこから探す値も「7」に固定しています。動作についてはコメントを参照してください。
リスト1：配列の中から「7」を探すプログラム～ex5201.c
#include <stdio.h>
/* 探索先の配列 */
int arry[] = {3, 6, 2, 7, 1, 4, 8};
void showarray(void)
{
int i;
/* 配列の値を表示 */
printf("探索先 :");
for (i=0; i<7; i++) {
printf("%d ", arry[i]);
}
printf("¥n");
}
int main(void)
{
int i;
showarray();
/* 要素数分繰り返す */
for (i=0; i<7; i++) {
/* 値が見付かったらメッセージを表示して終了 */
if (arry[i] == 7) {
printf("¥'7¥'は %d 番目に見付かりました。¥n", i+1);
break;
}
}
return (0);
}
プログラムを汎用化する
これではあまりに限定的なので、配列の中から探す値をキーボードから入力できるようにしたものをリスト2に掲げます。
値を自由に入力できるようにしたため、値が見付からなかったとき――入力された値が配列内に存在しなかったとき――にメッセージを表示するようにしています。
forループで配列の要素数である7回処理を繰り返しているので、値が見付かった場合は、ループから抜けたときのカウンタ変数iが6以下になります。よって、値が見付からなかった場合には、カウンタ変数iの値は7になっているはずです。そこでiが7以上なら「見付からなかった」と判断しています。
リスト2：探す値を入力できるようにした～ex5202.c
#include <stdio.h>
/* 探索先の配列 */
int arry[] = {3, 6, 2, 7, 1, 4, 8};
void showarray(void)
{
int i;
/* 配列の値を表示 */
printf("探索先 :");
for (i=0; i<7; i++) {
printf("%d ", arry[i]);
}
printf("¥n");
}
int main(void)
{
int i, n;
showarray();
/* 探索する値を入力 */
printf("input number : ");
scanf("%d", &n);
printf("¥n");
/* 要素数分繰り返す */
for (i=0; i<7; i++) {
/* 値が見付かったらメッセージを表示 */
if (arry[i] == n) {
printf("¥'%d¥'は %d 番目に見付かりました。¥n", n, i+1);
break;
}
}
/* 見付からなかったとき */
if (i >= 7) {
printf("¥'%d¥'は見付かりませんでした。¥n", n);
}
return (0);
}
|
|
|
TOP