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

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

問題① 🔗

問題①　配列に対して番兵を使った線形探索を行う関数を、関数内で番兵をセットする形で実装してください。


#include <stdio.h>

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

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

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

    int* p = linear_search_ex( array, SIZE_OF_ARRAY(array), target );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    線形探索

    array の末尾に番兵を置く場所があることを前提とする。
*/
int* linear_search_ex(int* array, size_t size, int value)
{
    array[size-1] = value;  // 番兵

    size_t i;
    for( i = 0; array[i] != value; ++i ){
    }

    if( i == size - 1 ){
        return NULL;  // 見つからなかった
    }

    return &array[i];
}

実行結果：

見つかりませんでした。

関数の中で番兵をセットするので、呼び出し側は簡単になります。一方、番兵が置かれる場所を確実に用意しておかないと、知らないうちに実データが上書きされてしまう可能性があります。

問題② 🔗

問題②　整列済みであることを利用した線形探索を、連結リスト版で実装してください。


前章の連結リスト版のサンプルプログラムを書き換えてみます。

#include <stdio.h>
#include "ppps_int_slist.h"

static PPPSIntSlist linear_search_ex(PPPSIntSlist list, int value);

int main(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 2 );
    ppps_int_slist_add_tail( list, 5 );
    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, 10 );
    ppps_int_slist_add_tail( list, 14 );
    ppps_int_slist_add_tail( list, 18 );
    ppps_int_slist_add_tail( list, 21 );

    PPPSIntSlist p = linear_search_ex( list, 7 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    ppps_int_slist_delete( list );

    return 0;
}

/*
    線形探索

    list が昇順に整列済みであることに依存している。
*/
PPPSIntSlist linear_search_ex(PPPSIntSlist list, int value)
{
    for( PPPSIntSlist p = list->next; p != NULL; p = p->next ){
        if( p->value < value ){
            continue;
        }
        if( p->value == value ){
            return p;
        }
        break;
    }

    return NULL;
}

実行結果：

見つかりました。

最初に連結リストに要素を登録するときに、昇順になるようにしています。実装方法は、本編での配列の例とまったく同じ形をしているので、難しくはないと思います。

昇順であることに依存しないシンプルな線形探索の場合との性能比較は、各自で行ってみてください。

問題③ 🔗

問題③　番兵を使った線形探索を、連結リスト版で実装してください。


前章の連結リスト版のサンプルプログラムを書き換えてみます。

#include <stdio.h>
#include "ppps_int_slist.h"

static PPPSIntSlist linear_search_ex(PPPSIntSlist list, int value);

int main(void)
{
    int target = 9;

    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 2 );
    ppps_int_slist_add_tail( list, 5 );
    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, 10 );
    ppps_int_slist_add_tail( list, 14 );
    ppps_int_slist_add_tail( list, 18 );
    ppps_int_slist_add_tail( list, 21 );

    ppps_int_slist_add_tail( list, target );  // 番兵
    PPPSIntSlist p = linear_search_ex( list, target );
    if( p == ppps_int_slist_search_tail(list) ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    ppps_int_slist_delete( list );

    return 0;
}

/*
    線形探索

    リストの末尾に番兵があることに依存する。
*/
PPPSIntSlist linear_search_ex(PPPSIntSlist list, int value)
{
    PPPSIntSlist p;

    for( p = list; p->value != value; p = p->next ){
    }

    return p;
}

実行結果：

見つかりませんでした。

探索を開始する前に、連結リストの末尾に番兵となる要素を追加しています。要素が見つからなかった場合、番兵のメモリアドレスが返されることになりますが、番兵は末尾に置かれているので、ppps_int_slist_search_tail関数が返すメモリアドレスと一致していたら、見つからないと判断しています。

さて、このサンプルの実装は実践的には非効率と言えるでしょう。ppps_int_slist_add_tail関数は、末尾の位置を探すときに、リスト内の全要素を順送りにしているので、この時点で O(n) の処理が行われています。これは単方向線形リストを使っていること自体にも問題があるかもしれません。仮に、双方向循環リスト（データ構造　第４章）を使っていたら、末尾を探すのは容易ですから、ずっと効率的になります。

また、探索の前に番兵となる要素を追加する実装だと、繰り返し探索を行うとき、次々と新しい番兵が追加されてしまいます。番兵は実データではないのですから、探索を終えた時点で、番兵は取り除いておかないと、次回の探索で誤った結果を返す可能性があります。

連結リストでダミーの先頭要素を作るのと同じ要領で、末尾にダミーを置いておくように実装することも考えられます。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

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

≪さらに古い更新履歴を展開する≫


第２章のメインページへ

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

Programming Place Plus のトップページへ

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