データ構造とアルゴリズムI実習(1限目)


以下の課題を解け. 必要に応じて講義資料を参考にすること.講義資料は ここにある. 課題の提出期限および提出方法は以下の通りとする.

課題1(提出不要):

以下は表の線形探索アルゴリズムを実装したCプログラムである.コンパイルして実行してみよ.
実行に際して,表にさまざまなデータを登録し,その後さまざまなキーで探索して,入力したデータが 正しく登録されているかを確かめること.

#include <stdio.h>
#include <math.h>
#include <time.h>

#define RECORD_MAX (10000)

struct Record {
    int key;    /* 重複しない */
    int data;   /* 0以上と仮定 */
};

struct Record table[RECORD_MAX]; /* 表 */
int n = 0;                       /* レコード数(<= RECORD_MAX) */

void regist(int key, int data) {
    int i;
    for (i = 0; i < n; i++) {
        if (table[i].key == key) {
            /* keyと一致するレコードがすでにあった場合 */
            table[i].data = data;
            return;
        }
    }
    /* keyと一致するレコードがなかった場合 */
    if (n < RECORD_MAX) {
        table[n].key = key;
        table[n].data = data;
        n++;
    }
}

int search(int key) {
    int i;
    for (i = 0; i < n; i++) {
        if (table[i].key == key) return table[i].data;
    }
    return -1;
}

main() {
    int key, data;

    for (;;) {
        printf("登録したいキーの値を入力してください(-1を入力すると登録終了):");
        scanf("%d", &key);
        if (key == -1) break;
        printf("キー(%d)のデータを入力してください:", key);
        scanf("%d", &data);
        regist(key, data);
    }
    for (;;) {
        printf("探索したいキーの値を入力してください(-1を入力すると探索終了):");
        scanf("%d", &key);
        if (key == -1) break;
        data = search(key);
        if (data == -1) {
            printf("キー(%d)を持つレコードは登録されていません.\n", key);
        } else {
            printf("キー(%d)のデータは%dです.\n", key, data);
        }
    }
}

課題2(要提出):

課題1で書いたプログラム中の関数 regist および search の中身を書き換えて二分探索ができるようにしたい.
関数 regist については以下のように書き換えた.search の中身を埋めて二分探索の実装を完成させよ.
なお,main 関数は課題1と同一のものを用いること. 実装が完了したら,課題1と同様に,登録と探索のテストを行ってみよ.

#include <stdio.h>
#include <math.h>
#include <time.h>

#define RECORD_MAX (10000)

struct Record {
    int key;    /* 重複しない */
    int data;   /* 0以上と仮定 */
};

struct Record table[RECORD_MAX]; /* 表 */
int n = 0;                       /* レコード数(<= RECORD_MAX) */

void regist(int key, int data) {
    int i, j;
    for (i = 0; i < n; i++) {
        if (table[i].key == key) {
            /* keyと一致するレコードがすでにあった場合 */
            table[i].data = data;
            return;
        } else if (table[i].key > key) {
            if (n < RECORD_MAX) {
                /* i番目以降のレコードを1つづつ後ろにずらす */
                for (j = n - 1; j >= i; j--) {
                    table[j+1].key = table[j].key;
                    table[j+1].data = table[j].data;
                }
                /* i番目のレコードに書き込み */
                table[i].key = key;
                table[i].data = data;                
                n++;
                return;
            }
        }
    }
    /* keyの値が一番大きい場合、一番最後に書き込み */
    if (n < RECORD_MAX) {
        table[n].key = key;
        table[n].data = data;
        n++;
    }
}

int search(int key) {
    [ここに二分探索の探索アルゴリズムを書け]
}

main() {
    [課題1と同じなので省略]
}