線形探索　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第１章

トップページ – アルゴリズムとデータ構造編 – 【探索アルゴリズム】第１章

問題① 🔗

問題①　最初に見つけた要素ではなく、最後に見つけた要素を返すような linear_search関数を作成してください。


末尾から先頭に向かって探索するようにすれば、最後に見つけた要素を返せます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* linear_search(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 7, 12, 4, 3, 7, 10 };

    int* p = linear_search( array, SIZE_OF_ARRAY(array), 7 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
        printf( "array: %p\n", array );
        printf( "p:     %p\n", p );
    }

    return 0;
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    for( int i = (int)size - 1; i >= 0; --i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

実行結果：

見つかりました。
array: 0000002755EFFAA8
p:     0000002755EFFAB8

配列array には、7 が 2つあるので、後ろの方の 7 が見つかったかどうか確認するために、返されたメモリアドレスを出力しています。配列array の先頭メモリアドレス + 16 のところを指しているので、array[4] のメモリアドレスが返されたことが分かります。

変数 i については、符号無し整数型にすると、-1 が表現できずに巨大な正の数になってしまうことに注意が必要です。ここでは int型（符号付き整数型）にしました。

ただし、こうすると今度は、引数 size が、int型の上限値を超える数だったときに正しく動作しません。実戦では、assert で検出するなり、long long int型などのより大きな型を使うなり検討してください。


linear_search関数の実装ですが、先頭から調べるような形のままで、すぐに return しないようにしても同じ結果になります。

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    int* result = NULL;

    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){
            result = &array[i];
        }
    }

    return result;
}

結果は同じですが、この方法だと、つねに配列全体を調べつくさないといけません。そのため、平均的な計算量が O(n/2) で済むはずの線形探索が、つねに O(n) になるため、効率が悪くなってしまいます。

しかし、対象が単方向線形リストの場合、末尾から逆方向にたどれませんから、こちらの手法で実装しなければなりません。

/*
    線形探索
*/
PPPSIntSlist linear_search(PPPSIntSlist list, int value)
{
    PPPSIntSlist result = NULL;

    for( PPPSIntSlist p = list->next; p != NULL; p = p->next ){
        if( p->value == value ){
            result = p;
        }
    }

    return result;
}

問題② 🔗

問題②　要素の値ではなく、「偶数」とか「3 の倍数」のような条件で探索できる inear_search関数を作成してください。


linear_search関数の汎用性を高く保ったまま、複雑な条件での探索に対応するには、関数ポインタ（Ｃ言語編第３８章）を利用して、判定を別の関数に任せるようにします。

例として、偶数の要素を探すサンプルプログラムを挙げます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

typedef int (*compare_func)(int* elem);

static int is_even(int* num);
static int* linear_search(int* array, size_t size, compare_func compare);

int main(void)
{
    int array[] = { 5, 12, 7, -8, -3, 9 };

    int* p = linear_search( array, SIZE_OF_ARRAY(array), is_even );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        printf( "見つかりました。 (%d)\n", *p );
    }

    return 0;
}

/*
    偶数かどうか判定する
*/
int is_even(int* num)
{
    return (*num) % 2 == 0;
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, compare_func compare)
{
    for( size_t i = 0; i < size; ++i ){
        if( compare( &array[i] ) ){
            return &array[i];
        }
    }

    return NULL;
}

実行結果：

見つかりました。 (12)

このように実装すれば、linear_search関数の第３引数に別の関数を渡せば、探索条件を自由に変えられます。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

　問題②の linear_search関数の引数が間違っていたのを修正。

　新規作成。


第１章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る