今回は、「線形探索」のプログラムを作成する。
条件は、要素数がnであるint型の配列vから、keyと同じ要素をもつ要素の添字を返却する関数であること。
なお、複数の要素がkeyと同じ値を持つ場合、最も先頭側の要素の添字を返却するものとする。
線形探索(逐次探索)
//線形探索(逐次探索)
#include <stdio.h>
#define NUMBER 5 //要素数
#define FAILED -1 //探索失敗
// 要素数nの配列vからkeyと一致する要素を先頭から線形探索
int search(const int v[], int key,int n)
{
for (int i = 0; i < n -1; i++)
{
if(v[i] == key)
return i; //探索成功
}
return FAILED; //探索失敗
}
int main(void)
{
int ky,idx;
int x[NUMBER];
for (int i = 0; i < NUMBER; i++)
{
printf("x[%d]:",i);
scanf("%d",&x[i]);
}
printf("探す値:");
scanf("%d",&ky);
if((idx = search(x,ky,NUMBER))== FAILED)
puts("探索に失敗しました。");
else
printf("%dは%d番目にあります。\n",ky,idx + 1);
return 0;
}
実行結果
1回目(要素あり)
x[0]:83
x[1]:49
x[2]:77
x[3]:49
x[4]:25
探す値:49
49は2番目にあります。
2回目(要素なし)
x[0]:83
x[1]:49
x[2]:77
x[3]:49
x[4]:24
探す値:16
探索に失敗しました。
配列の要素を順に走査して、目的とするものと同じ値をもつ要素をみつける手続きは、線形探索(linear search)あるいは逐次探索(sequential search)と呼ばれる。
関数searchは、配列vを先頭から末尾へと走査していき、その過程でkeyと等しい要素をみつけると、その添字iを返す。
ただし、全要素を走査しても見つからない場合は、FAILED すなわち -1を返す。
(参考)新・解きながら学ぶC言語 第2版 柴田望洋 (監修・著), 由梨かおる(著)SBクリエイティブ
コメント