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

演習7-5の解答

　　集合s1 がs2 の部分集合であるか、s1 がs2 の真部分集合であるかどうかを判定する以下の関数を作成せよ。
　　int BsetIsSubset (Bset s1 , Bset s2 );
　　int BsetIsProperSubset (Bset s1 , Bset s2 );
なお、判定結果が成立すれば1を、そうでなければ0を返すこと。

/*
    演習7-5
    ビットベクトルによる整数集合演算（実現部：部分集合／真部分集合）
*/

#include  <stdio.h>
#include  "bsetlib.h"

/*--- 集合sにnが入っているか ---*/
int BsetMember(Bset s, int n)
{
    return (s & Bsetof(n));
}

/*--- 集合sにnを追加 ---*/
void BsetInsert(Bset *s, int n)
{
    *s |= Bsetof(n);
}

/*--- 集合sからnを削除 ---*/
void BsetDelete(Bset *s, int n)
{
    *s &= ~Bsetof(n);
}

/*--- 集合sの要素数 ---*/
int BsetMemNum(Bset s)
{
    int  n = 0;

    for ( ; s != BsetNull; n++)
        s &= s - 1;
    return (n);
}

/*--- 集合s1からs2を引いた集合を求める ---*/
Bset BsetDifference(Bset s1, Bset s2)
{
    return (s1 & ~s2);
}

/*--- 集合s1はs2の部分集合か ---*/
int BsetIsSubset(Bset s1, Bset s2)
{
    return (((s1 & s2) == s1) ? 1 : 0);
}

/*--- 集合s1はs2の真部分集合か ---*/
int BsetIsProperSubset(Bset s1, Bset s2)
{
    return ((((s1 & s2) == s1) && (s1 != s2)) ? 1 : 0);
}

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

    printf("{ ");
    for (i = 0; i < BsetBIT; i++)
        if (BsetMember(s, i))
            printf("%d ", i);
    printf("}\n");
}

/*--- 集合sを文字列に変換 ---*/
char *BsetStr(Bset s, char *buff)
{
    int   i;
    char  *save = buff;

    for (i = 0; i < BsetBIT; i++) {
        *buff++ = ((s & BsetOne) ? '0' + i % 10 : '-');
        s >>= 1;
    }
    *buff = '\0';
    return (save);
}
/*--- 表示 ---*/
void Print(const char *msg, Bset x)
{
    char  buffer[33];

    printf("%s%s\n", msg, BsetStr(x, buffer));
}

/*--- 集合s1とs2の和・積・差・包含関係を表示 ---*/
void PrintUIDP(Bset s1, Bset s2)
{
    Bset  s3;

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

    printf("s1 | s2 = ");
    BsetPrint(s1 | s2);

    printf("s1 & s2 = ");
    BsetPrint(s1 & s2);

    s3 = BsetDifference(s1, s2);
    printf("s1 - s2 = ");
    BsetPrint(s3);

    printf("s1はs2の部分集合：%d\n",   BsetIsSubset(s1, s2));
    printf("s1はs2の真部分集合：%d\n", BsetIsProperSubset(s1, s2));

}

int main(void)
{
    int   i;
    Bset  s1 = BsetNull, s2;

    for (i = 1; i < 32; i += 4)
        BsetInsert(&s1, i);
    s2 = s1;

    Print("s1 = ", s1);  Print("s2 = ", s2);

    while (1) {
        int  m, x;

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

        if (m == 0) break;

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

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

    return (0);
}

戻る