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

演習7-4の解答

　List 7-2に示した実現では、追加された要素を配列の末尾に格納していくため、要素の並びは不定である。そのため、要素が含まれているかどうかを、線形探索によって実現しなければならない。
　そこで、配列内の要素を常にソートしておくように改良せよ。そうすると、要素が含まれているかどうかの判定は２分探索によって行えるし、要素の追加や削除も同様な探索によって得られた位置に対して行えることになる。もちろん、それ以外の関数も変更しなければならない。

/*
    演習7-4
    集合の実現例
*/

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

/*--- 集合を実現する構造体 ---*/
typedef struct {
    int  max;       /* 配列のサイズ */
    int  num;       /* 集合の要素数 */
    int  *set;      /* 配列（の先頭へのポインタ） */
} Set;

/*--- 集合の初期化 ---*/
int SetAlloc(Set *s, int max)
{
    s->max = s->num = 0;
    if ((s->set = (int *)calloc(max, sizeof(int))) == NULL) {
        s->max = 0;                             /* 配列の確保に失敗 */
        return (-1);
    }
    s->max = max;
    return (0);
}

/*--- 集合の後始末 ---*/
void SetFree(Set *s)
{
    if (s->set != NULL) {
        free(s->set);                           /* 配列を解放 */
        s->max = s->num = 0;
    }
}

/*--- 集合sにnが入っている添字（なければ挿入すべき添字）を求める ---*/
int __SetMember(const Set *s, int n, int *flag)
{
    int  pl = 0;            /* 探索範囲先頭の添字 */
    int  pr = s->num - 1;   /* 　 〃 　末尾の添字 */
    int  pc;                /* 　 〃 　中央の添字 */

    *flag = 1;
    if (s->num <= 0) return (0);    /* 空集合 */

    do {
        pc = (pl + pr) / 2;
        if (s->set[pc] == n) {      /* 探索成功 */
            *flag = 0;
            return (pc);
        } else if (s->set[pc] < n)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while (pl <= pr);

    return (pl);                    /* 探索失敗 */
}

/*--- 集合sにnが入っているか ---*/
int SetMember(const Set *s, int n)
{
    int flag;
    int idx = __SetMember(s, n, &flag);
    return (flag ? idx : -1);
}

/*--- 集合sにnを追加 ---*/
void SetInsert(Set *s, int n)
{
    int  i, idx, flag;

    if (s->num < s->max) {
        idx = __SetMember(s, n, &flag);
        if (flag == 1) {                        /* 含まれなかったら */
            s->num++;
            for (i = s->num - 1; i > idx; i--)
                s->set[i] = s->set[i - 1];
            s->set[idx] = n;                    /* set[idx]に挿入 */
        }
    }
}

/*--- 集合sからnを削除 ---*/
void SetDelete(Set *s, int n)
{
    int  i, idx, flag;

    if (s->num > 0) {
        idx = __SetMember(s, n, &flag);

        if (flag == 0) {                        /* 含まれていたら */
            --s->num;
            for (i = idx; i < s->num; i++)      /* set[idx]を削除して */
                s->set[i] = s->set[i + 1];      /* それ以降の要素をずらす */
        }
    }
}

/*--- 集合sが格納できる最大の要素数 ---*/
int SetMemMax(const Set *s)
{
    return (s->max);
}

/*--- 集合sの要素数 ---*/
int SetMemNum(const Set *s)
{
    return (s->num);
}

/*--- 集合s2をs1に代入 ---*/
void SetAssign(Set *s1, const Set *s2)
{
    int  i;
    int  n = (s1->max < s2->num) ? s1->max : s2->num;

    for (i = 0; i < n; i++)
        s1->set[i] = s2->set[i];
    s1->num = n;
}

/*--- 集合s2とs3の和集合をs1に代入 ---*/
void SetUnion(Set *s1, const Set *s2, const Set *s3)
{
    int  k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    while (k2 < s2->num  &&  k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            s1->set[s1->num++] = s2->set[k2++];
        else if (s2->set[k2] > s3->set[k3])
            s1->set[s1->num++] = s3->set[k3++];
        else {
            s1->set[s1->num++] = s2->set[k2++];
            k3++;
        }
        if (s1->num == s1->max) return;
    }

    if (k2 < s2->num)
        while (k2 < s2->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s2->set[k2++];
    else
        while (k3 < s3->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s3->set[k3++];
}

/*--- 集合s2とs3の積集合をs1に代入 ---*/
void SetIntersection(Set *s1, const Set *s2, const Set *s3)
{
    int  k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    while (k2 < s2->num  && k3 < s3->num) {
         if (s2->set[k2] < s3->set[k3])
            k2++;
        else if (s2->set[k2] > s3->set[k3])
            k3++;
        else {
            s1->set[s1->num++] = s2->set[k2];
            k3++;
            if (s1->num == s1->max)
                return;
        }
    }
}

/*--- 集合s2からs3を引いた集合をs1に代入 ---*/
void SetDifference(Set *s1, const Set *s2, const Set *s3)
{
    int  k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    while (k2 < s2->num  &&  k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            s1->set[s1->num++] = s2->set[k2++];
        else if (s2->set[k2] > s3->set[k3])
            k3++;
        else {
            k2++;
            k3++;
        }
        if (s1->num == s1->max) return;
    }

    if (k2 < s2->num)
        while (k2 < s2->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s2->set[k2++];
}

/*--- 集合sの全要素を表示 ---*/
void SetPrint(const Set *s)
{
    int  i;

    printf("{ ");
    for (i = 0; i < s->num; i++)
        printf("%d ", s->set[i]);
    printf("}\n");
}

/*--- 集合s1とs2の和・積・差を表示 ---*/
void PrintUID(const Set *s1, const Set *s2)
{
    Set  s3;

    if (SetAlloc(&s3, 10) == -1) {
        puts("集合の確保に失敗しました。");
        return;
    }

    printf("s1 = ");    SetPrint(s1);
    printf("s2 = ");    SetPrint(s2);

    SetUnion(&s3, s1, s2);        printf("s1 | s2 = "); SetPrint(&s3);
    SetIntersection(&s3, s1, s2); printf("s1 & s2 = "); SetPrint(&s3);
    SetDifference(&s3, s1, s2);   printf("s1 - s2 = "); SetPrint(&s3);

    SetFree(&s3);
}
    
int main(void)
{
    Set  s1, s2, s3;

    if (SetAlloc(&s1, 10) == -1 || SetAlloc(&s2, 10) == -1) {
        puts("集合の確保に失敗しました。");
        return (1);
    }

    SetInsert(&s1, 10); SetInsert(&s1, 15);     /* s1 ← {10, 15, 20, 25} */
    SetInsert(&s1, 20); SetInsert(&s1, 25);

    SetAssign(&s2, &s1);                        /* s2 ← {10, 15, 20, 25} */

    while (1) {
        int  m, x;

        PrintUID(&s1, &s2);
        printf("(1) s2に追加　(2) s2から削除　(0) 終了：");
        scanf("%d", &m);

        if (m == 0) break;

        switch (m) {
         case 1: printf("データ："); scanf("%d", &x);
                 SetInsert(&s2, x);                     break;

         case 2: printf("データ："); scanf("%d", &x);
                 SetDelete(&s2, x);                     break;
        }
    }

    SetFree(&s1);
    SetFree(&s2);

    return (0);
}

戻る