C言語のきほん「線形探索」

スポンサーリンク
プログラミング C言語

今回は、「線形探索」のプログラムを作成する。

条件は、要素数が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クリエイティブ

新・解きながら学ぶC言語 第2版

コメント

タイトルとURLをコピーしました