Ｃ言語によるアルゴリズムとデータ構造

演習3-4の解答

　bsearch 関数と同じ形式で呼び出すことのできる以下の関数を作成せよ。
　　void *seqsearch (const void *key , const void *base , size_t nmemb ,
　　　　size_t size , int (*compar )(const void *, const void *));
ただし、線形探索アルゴリズムを利用すること。もちろん、配列はソート済みでなくてもよいものとする。

/*
    演習3-4
    汎用線形探索関数（あらゆる要素型／要素数に対応）
*/

#include  <stdio.h>

/*--- baseが指す要素の大きさがsizeで要素数がnmembの配列からkeyと一致する要素を
      比較関数comparを用いて線形探索 ---*/
void *seqsearch(const void *key, const void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void*))
{
    size_t  i;
    char    *x = (char *)base;

    for (i = 0; i < nmemb; i++)
        if (!compar((const void *)&x[i * size], key))
            return (&x[i * size]);
    return (NULL);
}

/*--- int型整数を比較する関数 ---*/
int int_cmp(const int *a, const int *b)
{
    if (*a < *b)
        return (-1);
    else if (*a > *b)
        return (1);
    else
        return (0);
}

int main(void)
{
    int  i, ky, idx;
    int  x[7];
    int *ptr;
    int  nx = sizeof(x) / sizeof(x[0]);

    printf("%d個の整数を入力せよ。\n", nx);

    for (i = 0; i < nx; i++) {
        printf("x[%d]：", i);
        scanf("%d", &x[i]);
    }
    printf("探す値：");
    scanf("%d", &ky);

    ptr = seqsearch(&ky, x, nx, sizeof(int), 
                (int (*)(const void *, const void*))int_cmp);

    if (ptr == NULL)
        puts("\a探索に失敗しました。");
    else
        printf("%dは%d番目にあります。\n", ky, ptr - x + 1);

    return (0);
}

戻る