Next: 2.2 ソーティング Up: 2 サーチングとソーティング Previous: 2 サーチングとソーティング

2.1 サーチング

配列あるいは構造体に記憶されたデータの中から特定の情報を有するものを検 出することをサーチング(探索)といいます．探索を実現するためのアルゴリズ ムとして，逐次探索法，2分探索法，補間探索法などが知られています．この うち2分探索法，補間探索法はデータの並べ替え(ソーティング)を必要とする ものの，高速な検索を実現することができます．一方，逐次探索法では， 図 9に示すように， 配列または構造体の先頭要素から順に， 与えられた要素と一致するものがあるかひとつひとつ照合を行います．

 
Figure 9: 逐次探索法

練習問題 2-1 データファイルの内容を構造体配列に読み込み，キーボードから入力した交差 点名と一致する交差点の番号，位置，隣接する交差点番号を表示するプログラ ムを作成しましょう．文字列の比較には関数strcmpを使用すること．

• サンプル・プログラムリスト中の... の部分には適当なプログラ ムを補って下さい．

-----------------------

/* Search.c ---                単純探索法によるデータの検索 */
#include <stdio.h>

#define CrossingNumber ...            /* 交差点数 */

...                                   /* 構造体の定義 */

Crossing cross[CrossingNumber];       /* 交差点の変数宣言 */ 
...


void search(void)
{
    int i;
    char item_search[20];
       
    printf("交差点名を入力して下さい\n");
    ...                /* 検索する要素の入力 */
    for (i = 0; i < CrossingNumber; i++ ) {
    ...                /* 構造体配列の交差点名を表す要素と，検索する要素の
                          比較を行い，一致した場合，交差点名，交差点番号，
                          位置，隣接する交差点番号を表示する手続きを入力
                          して下さい.  */
    }
}

void main(void)
{
    map_read("map.dat");  /* 地図情報の読み込み */
    search();             /* サーチングの実行 */
}

-----------------------

注：

キーボードから日本語を入力する場合は kanji input server ``kinput2''を 立ち上げる必要があります(1-10 参照)．kterm 上で kinput2 & と入力して下さい． Controlキーを押しながら spaceキーを押すと，画面上部に日本語変換窓が出ますので， ローマ字で日本語を入力して下さい．Shiftキーを押しながら spaceキーを押すと 日本語モードは終了します．

なお，マウスを使ってコピーアンドペーストするのも一つの方法です

Next: 2.2 ソーティング Up: 2 サーチングとソーティング Previous: 2 サーチングとソーティング