（Ｃ言語）線形探索 - 日々まなび、日々あそび、生きる

（子の本棚にＣ言語入門の本が落ちてたので、勉強してみよっと）

【実行プログラム】

【ソースプログラム】

#include  <stdio.h>

#define NUMBER 5
#define FAILED -1

int search(const int vc, int key, int no)
{
    int i = 0;

    while (1) {
        if (i == no)
            return (FAILED);
        if (vc[i] == key)
            return (i);
        i++;
    }
}

int main(void)
{
    int i, ky, idx;
    int vx[NUMBER];

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

    idx = search(vx, ky, NUMBER);

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

    return (0);
}

【まなび】

■ 線形探索とは

　要素数NUMBERの配列vxからKyと一致する要素を探索（走査）するプログラム。

■ 番兵法

　負荷軽減する手法で、配列の最後に必ず番兵を格納することで探索を必ず成功させるものになる。

#include  <stdio.h>

#define NUMBER 5
#define FAILED -1

int search(int v, int key, int no)
{
    int i = 0;

    v[no] = key;

    while (1) {
        if (v[i] == key)
            break;
        i++;
    }
}

int main(void)
{
    int ky, idx;
    int x[NUMBER + 1];

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

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

    return (0);
}

************************************************
【演習6-11 】

要素数nの配列v内のKeyと等しい全要素の添字を配列idxに格納する関数search_idxを作成せよ。なお、返却するのはKeyと等しい要素の個数とする。

int search_idx(const int v, int idx, const int key, const int n)

例えば、vに受け取った配列の要素が｛1, 7, 5, 7, 2, 4, 7｝でKeyが7であれば、｛1, 3, 6｝を格納した上で3を返却する。

#include  <stdio.h>

#define NUMBER 7
#define FAILED -1

int search_idx(const int v, int idx, const int key, const int n)
{
    int j = 0;

    for(int i = 0; i < n; i++) {
        if (i == n)
            return (FAILED);
        if (v[i] == key){
            idx[j] = i;
            j++;
        }
    }

    printf("idx = {");
    for (int i = 0; i < j ; i++) {
        printf("%d, ", idx[i]);
    }
    printf("}\n");

    return(j);
}

int main(void)
{
    int ky, idx_c ;
    int idx[] = {0};
    int v[NUMBER];

    for (int i = 0; i < NUMBER; i++) {
        printf("v[%d]：", i);
        scanf("%d", &v[i]);
    }
    printf("探す値：");
    scanf("%d", &ky);
printf("kyは%d\n", ky);
    idx_c = search_idx(v, idx, ky, NUMBER);
printf("kyは%d\n", ky);     //なぜ、kyは変わってしまうのか？？
printf("idx_cは%d\n", idx_c);
    if (idx_c == FAILED)
        puts("\a探索に失敗しました。");
    else
        printf("%dは%d個ありました\n", ky, idx_c);

    printf("idx = {");
    for (int i = 0; i < idx_c ; i++) {
        printf("%d, ", idx[i]);     //なぜ、idx最後の配列だけ中味が変わってしまう？？
    }
    printf("}\n");

    return (0);
}