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

戻る  

演習7-2の解答

/*
    演習7-2
    集合が等しいか／部分集合か／真部分集合か
*/

#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;
    }
}

/*--- 集合s1とs2は等しいか ---*/
int SetIsEqual(const Set *s1, const Set *s2)
{
    int  i, j;

    if (s1->num != s2->num)                 /* 要素数が等しくなければ */
        return (0);                         /* 集合も等しくない */

    for (i = 0; i < s1->num; i++) {
        for (j = 0; j < s2->num; j++)
            if (s1->set[i] == s2->set[j])
                break;
        if (j == s2->num)                   /* s1->set[i]はs2に含まれない */
            return (0);
    }
    return (1);
}

/*--- 集合s1はs2の部分集合か ---*/
int SetIsSubset(const Set *s1, const Set *s2)
{
    int  i, j;

    for (i = 0; i < s1->num; i++) {
        for (j = 0; j < s2->num; j++)
            if (s1->set[i] == s2->set[j])
                break;
        if (j == s2->num)                   /* s1->set[i]はs2に含まれない */
            return (0);
    }
    return (1);
}

/*--- 集合s1はs2の真部分集合か ---*/
int SetIsProperSubset(const Set *s1, const Set *s2)
{
    int  i, j;

    if (s1->num >= s2->num)                 /* s1の要素数がs2以上であれば */
        return (0);                         /* s1はs2の真部分集合ではない */

    for (i = 0; i < s1->num; i++) {
        for (j = 0; j < s2->num; j++)
            if (s1->set[i] == s2->set[j])
                break;
        if (j == s2->num)                   /* s1->set[i]はs2に含まれない */
            return (0);
    }
    return (1);
}

/*--- 集合sにnが入っているか ---*/
int SetMember(const Set *s, int n)
{
    int  i;

    for (i = 0; i < s->num; i++)
        if (s->set[i] == n)
            return (i);                         /* 含まれる */
    return (-1);                                /* 含まれない */
}

/*--- 集合sにnを追加 ---*/
void SetInsert(Set *s, int n)
{
    if (s->num < s->max  &&  SetMember(s, n) == -1) /* 含まれなかったら */
        s->set[s->num++] = n;                       /* 配列の末尾に追加 */
}

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

    if (s->num > 0  &&  (idx = SetMember(s, n)) != -1) {
        int  i;

        --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;

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

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

    SetAssign(s1, s2);
    for (i = 0; i < s3->num; i++)
        SetInsert(s1, s3->set[i]);
}

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

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

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

    s1->num = 0;
    for (i = 0; i < s2->num; i++) {
        for (j = 0; j < s3->num; j++)
            if (s2->set[i] == s3->set[j])
                break;
            if (j == s3->num)
                s1->set[s1->num++] = s2->set[i];
    }
}

/*--- 集合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 Print(const Set *s1, const Set *s2)
{
    Set  s3;

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

    printf("s1とs2は等しいか　　 : %d\n", SetIsEqual(s1, s2));
    printf("s1はs2の部分集合か　 : %d\n", SetIsSubset(s1, s2));
    printf("s1はs2の真部分集合か : %d\n", SetIsProperSubset(s1, s2));
}
    
int main(void)
{
    Set  s1, s2;

    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;

        Print(&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);
}

戻る