2014 Data Structures and Algorithms


コードを次のように変更しよう。
  1. データの件数を増やしてみよう。
  2. 何度も繰り返しデータを探せるように変更してみよう。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NOT_FOUND   (-1)
#define N           (10)
 
int linear_search(int x, int *a, int num) {
    int n = 0;
 
    /* 配列の範囲内で目的の値を探す */
    while(n < num && a[n] != x) {
        n++;
    }
 
    if(n < num) {
        return n;
    }
 
    return NOT_FOUND;
}
 
int main(void) {
    int i, r, array[N];
 
    srand((unsigned int)time(NULL));
 
    /* 適当な配列を作る */
    printf("array ");
    for(i = 0; i < N; i++) {
        printf("[%d]:%d ", i, array[i] = rand() % 20);
    }
 
    printf("\n何を探しますか:");
    scanf("%d", &i);
 
    r = linear_search(i, array, N);
 
    if(r == NOT_FOUND) {
        printf("%dは見つかりません\n", i);
    } else {
        printf("%dは%d番目です\n", i, r);
    }
 
    return EXIT_SUCCESS;
}




#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NOT_FOUND   (-1)
#define N           (10)
 
int search(int x, int *a, int num) {
    int     n = 0, t;
 
    /* 最後の値をxに入れ替える(番兵) */
    t = a[num - 1];
    a[num - 1] = x;
 
    /*目的の値を探す*/
    while(a[n] != x) {
        n++;
    }
 
    a[num - 1] = t;     /* 配列最後の値を元に戻す */
    if(n < num-1) {
        return n;   /* いちばん最後以外で一致 */
    }
    if(x == t) {
        return n;   /* いちばん最後が一致 */
    }
 
    return NOT_FOUND;
}
 
int main(void) {
    int     i, r, array[N];
 
    srand((unsigned int)time(NULL));
 
    /* 適当な配列を作る */
    printf("array ");
    for(i = 0; i < N; i++) {
        printf("[%d]:%d ", i, array[i] = rand() % 20);
    }
 
    printf("\n何を探しますか:");
    scanf("%d",&i);
 
    r = search(i, array, N);
    if(r == NOT_FOUND) {
        printf("%dは見つかりません\n", i);
    } else {
        printf("%dは%d番目です\n", i, r);
    }
 
    return EXIT_SUCCESS;
}




コードを次のように変更しよう。
  1. データの件数を増やしてみよう。
  2. 何度も繰り返しデータを探せるように変更してみよう。
  3. 最初に乱数で配列を初期化し、ソートアルゴリズムを使って配列をソートしてから探索するように、変更してみよう。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NOT_FOUND   (-1)
#define N           (10)
 
int binary_search(int x,int *a,int left,int right) {
    int     mid;
 
    while(left <= right) {
        mid = (left + right) / 2;
        if(a[mid] == x) {
            return mid;
        }
 
        if(a[mid] < x) {
            left = mid + 1;     /* midより左側にxは存在しない */
        } else {
            right = mid - 1;    /* midより右側にxは存在しない */
        }
    }
 
    /* サーチ範囲がなくなっても一致するものはなかった */
    return NOT_FOUND;
}
 
int main(void) {
    int     i, r, array[N];
 
    srand((unsigned int)time(NULL));
 
    /* 適当なソートされた配列を作る */
    printf("array ");
    printf("[0]:%d ", array[0] = rand() % 3);
    for(i = 1; i < N; i++) {
        printf("[%d]:%d ", i, array[i] = array[i-1] + rand() % 3);
    }
 
    printf("\n何を探しますか:");
    scanf("%d", &i);
 
    r = binary_search(i, array, 0, N-1);
 
    if(r == NOT_FOUND) {
        printf("%dは見つかりません\n", i);
    } else {
        printf("%dは%d番目です\n", i, r);
    }
 
    return EXIT_SUCCESS;
}




#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NOT_FOUND   (-1)
#define N           (10)
 
int binary_search(int x, int *a, int left, int right) {
    int      mid;
 
    while(left < right) {
        mid = (left + right) / 2;
        if(a[mid] < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if(a[left]==x) {
        return left;
    }
 
    /* サーチ範囲がなくなっても一致するものはなかった */
    return NOT_FOUND;
}
 
int main(void) {
    int     i, r, array[N];
 
    srand((unsigned int)time(NULL));
 
    /* 適当なソートされた配列を作る */
    printf("array ");
    printf("[0]:%d ", array[0] = rand() % 3);
    for(i = 1; i < N; i++) {
        printf("[%d]:%d ", i, array[i] = array[i - 1] + rand() % 3);
    }
 
    printf("\n何を探しますか:");
    scanf("%d", &i);
 
    r = binary_search(i, array, 0, N - 1);
 
    if(r == NOT_FOUND) {
        printf("%dは見つかりません\n", i);
    } else {
        printf("%dは%d番目です\n", i, r);
    }
 
    return EXIT_SUCCESS;
}




コードを次のように変更しよう。
  1. 最初に本のIDをソートするとき、逆順にソートしてみよう。
  2. 貸し出し中ではない本が見つかったら、すぐに貸し出し中として設定されるようにしよう。
  3. このサンプルファイルにある本のデータをサーチできるようにしてみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define N   5
 
/* 蔵書を表すデータ */
typedef struct {
    char *title;
    char *author;
    int bookID;
    int available;      /* 貸し出し中なら0,そうでなければ1 */
} book;
 
book *bookarray[N];     /* 蔵書データのポインタの配列 */
 
/* 蔵書のデータを初期化する */
void initdata(void) {
    int n;
    for(n = 0; n < N; n++) {
        bookarray[n] = (book*)malloc(sizeof(book));
    }
 
/* 書籍名&著者名は,好きな本をどうぞ! */
    bookarray[0]->title = "book0";
    bookarray[1]->title = "book1";
    bookarray[2]->title = "book2";
    bookarray[3]->title = "book3";
    bookarray[4]->title = "book4";
    bookarray[0]->author = "author0";
    bookarray[1]->author = "author1";
    bookarray[2]->author = "author2";
    bookarray[3]->author = "author3";
    bookarray[4]->author = "author4";
    bookarray[0]->bookID = 1000;
    bookarray[1]->bookID = 502;
    bookarray[2]->bookID = 731;
    bookarray[3]->bookID = 628;
    bookarray[4]->bookID = 1;
    bookarray[0]->available = 1;
    bookarray[1]->available = 0;
    bookarray[2]->available = 0;
    bookarray[3]->available = 1;
    bookarray[4]->available = 1;
}
 
/* 蔵書データのメモリを解放 */
void cleanupdata(void) {
    int n;
    for(n = 0; n < N; n++) {
        free(bookarray[n]);
    }
}
 
/* 本のデータをbookIDの順に昇順でクイックソートする */
void sortbook(int bottom,int top) {
    int lower, upper, div;
    book *temp;
 
    if(bottom >= top) {
        return;
    }
 
    div = bookarray[bottom]->bookID;  /* 適当な基準値を選択 */
    for(lower = bottom, upper = top; lower < upper;) {
        while(/*lower < upper && */bookarray[lower]->bookID < div) {
            lower++;
        }
        while(/*lower < upper && */bookarray[upper]->bookID > div) {
            upper--;
        }
        if(lower<upper) {
            /* データ(へのポインタ)の順番を入れ替える */
            temp = bookarray[lower];
            bookarray[lower] = bookarray[upper];
            bookarray[upper] = temp;
            lower++;
            upper--;
        }
    }
    sortbook(bottom, upper);
    sortbook(upper + 1, top);
}
 
/* booksのなかからbookIDがkeyと一致するデータをバイナリサーチで
    検索して,その添え字を返す。見つからなければ-1を返す */
int searchbook(book *books[],int size,int key) {
    int left, mid, right;
 
    left = 0;
    right = size;
    while(left < right) {
        mid = (left + right) / 2;
        if(books[mid]->bookID < key) {  /* bookIDの大小を比較 */
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if(books[left]->bookID == key) {
        return left;
    }
 
    return -1;  /* 見つからなかった場合 */
}
 
int main(void) {
    int key, position;
 
    initdata();
    sortbook(0, N - 1);    /* 最初に,管理番号順にソートしておく */
 
    /* 検索キーとして本の管理番号を入力 */
    while(1) {
        printf("検索する本の番号を入力してください"
                "(0で終了):");
        scanf("%d" , &key);
        if(key == 0) {
            break;      /* 0が入力されたら終了 */
        }
 
        /* 検索して結果を表示 */
        position = searchbook(bookarray, N - 1, key);
 
        if(position != -1) {
            printf("--次の本が見つかりました--\n"
                    "[タイトル]%s \n[著者]%s \n[管理番号]%d \n",
                bookarray[position]->title,
                bookarray[position]->author,
                bookarray[position]->bookID);
            if(bookarray[position]->available != 0) {
                puts("この本は貸し出し可能です。\n");
            } else {
                puts("この本は貸し出し中です。\n");
            }
        } else {
            puts("お探しの本は見つかりませんでした。\n");
        }
    }
 
    cleanupdata();
    return 0;
}




コードについて次のことを調べよう。
  1. リニアサーチ(list2-1.c)に比べて本当に効率が良くなっているのか、データの個数を増やして、実行時間の差を確かめよう。(実行時間の差が確かめられるような実験をすること。配列の大きさをある程度大きくしてから、同じデータを何回も探しに行くようにすれば、 差は出てくるはず。)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NOT_FOUND   (-1)
#define N           (10)
 
int organization_search(int x, int *a, int num) {
    int n = 0, t;
 
    while(n < num && a[n] != x) {
        n++;
    }
 
    if(n < num) {
        if(n > 0) {     /* 1つ前と入れ替える */
            t = a[n - 1];
            a[n - 1] = a[n];
            a[n] = t;
            return n-1;
        }
        return n;
    }
 
    return NOT_FOUND;
}
 
int main(void) {
    int i, r, array[N];
 
    srand((unsigned int)time(NULL));
 
    /* 適当な配列を作る */
    for(i=0;i<N;i++) {
        array[i] = rand();
    }
 
    for(;;) {
        printf("array ");
        for(i = 0; i < N; i++) {
            printf("[%d]:%d ", i, array[i]);
        }
 
        printf("\n何を探しますか(-1で終了):");
        scanf("%d", &i);
        if(i == -1) {
            break;
        }
 
        r = organization_search(i, array, N);
 
        if(r == NOT_FOUND) {
            printf("%dは見つかりません\n", i);
        } else {
            printf("%dは%d番目です\n", i, r);
        }
    }
 
    return EXIT_SUCCESS;
}