データ構造とアルゴリズムI実習(第一回)

以下の課題を解け．
C言語によるプログラミング，コンパイルおよび実行は paiza.ioにアクセスすれば，すべてWeb上で行うことができる．
必要に応じて講義資料を参考にすること．講義資料はここにある．課題の提出期限および提出方法は以下の通りとする．

提出期限： 6月30日(月)23:59

提出方法：課題2のソースコードと実行結果をMyKONANに提出すること．課題3の提出は任意である．

課題1(提出不要):

以下は表の線形探索アルゴリズムを実装したCプログラムである．コンパイルして実行してみよ．
ただし，このプログラムの入力の形式は以下の通りである．

n
key₁
value₁
…
key_n
value_n
m
key₁
…
key_m

ここで，nは登録するレコード数，mは検索を行う回数とし，key_iをキー，value_iをデータ（値）とする．（合わせて2+2n+m行になる．）
実行に際して，複数のキーと値を登録した表をさまざまなキーで探索し，入力したキーに対応する値が正しく検索されるかを確かめること．

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

#define RECORD_MAX (10000)

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

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

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

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

int main() {
    int n, m, i, key, value;

    scanf("%d", &n);
    printf("レコード数(%d)\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        scanf("%d", &value);
        printf("キー(%d), 値(%d)を登録\n", key, value);
        regist(key, value);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &key);
        printf("キー(%d)を探索．\n", key);
        value = search(key);
        if (value == -1) {
            printf("キー(%d)を持つレコードは登録されていません．\n", key);
        } else {
            printf("キー(%d)の値は%dです．\n", key, value);
        }
    }
}

課題2(要提出):

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

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

#define RECORD_MAX (10000)

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

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

void regist(int key, int value) {
    int i, j;
    for (i = 0; i < n; i++) {
        if (table[i].key == key) {
            /* keyと一致するレコードがすでにあった場合 */
            table[i].value = value;
            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].value = table[j].value;
                }
                /* i番目のレコードに書き込み */
                table[i].key = key;
                table[i].value = value;                
                n++;
                return;
            }
        }
    }
    /* keyの値が一番大きい場合、一番最後に書き込み */
    if (n < RECORD_MAX) {
        table[n].key = key;
        table[n].value = value;
        n++;
    }
}

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

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

課題3(発展課題):

同じデータを用いて，課題1と課題2の登録に要する時間，探索に要する時間をそれぞれ計測し，比較せよ．
計測結果は予想通りであったか，予想通りでなければなぜそうなったのかについて考察せよ．
なお，時間計測には，clock()関数を用いよ．
課題1のプログラムに対して，clock()関数を用いて時間計測する例は以下の通りである．

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

#define RECORD_MAX (10000)

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

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

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

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

int main() {
    int n, m, i, key, value;
    clock_t start, end;

    scanf("%d", &n);
    printf("レコード数(%d)\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        scanf("%d", &value);
        printf("キー(%d), データ(%d)を登録\n", key, value);
        start = clock();
        regist(key, value);
        end = clock();
        printf ("登録に要した時間[%lf]\n", (double)(end - start) / CLOCKS_PER_SEC);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &key);
        printf("キー(%d)を探索．\n", key);
        start = clock();
        value = search(key);
        end = clock();
        if (value == -1) {
            printf("キー(%d)を持つレコードは登録されていません．\n", key);
        } else {
            printf("キー(%d)のデータは%dです．\n", key, value);
        }
        printf ("探索に要した時間[%lf]\n", (double)(end - start) / CLOCKS_PER_SEC);
    }
}