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

演習7-6の解答

　要素数がunsigned long型のビット数に制限されることのない、ビットベクトルによる集合を、以下に示すVBset型によって実現せよ。

typedef struct {
    size_tz   sz ;       /* set の要素数 */
    int       max ;      /* 要素の値の上限 */
    int       min ;      /* 要素の値の下限 */
    unsigned  *set ;     /* 集合（の先頭要素へのポインタ） */
}

　たとえば、VBset 型の集合s1 を10以上99以下の整数を表せる集合とするのであれば、以下に示す方法で初期化できるように実現すること。
　　VBsetAlloc (&s1 , 10, 99);
もしもunsigned int型が16ビットであれば、この関数は10から99までの90種類の数値を格納できるようにするために、要素数が6であるunsigned int型の配列を動的に確保する。そうすると、set [0]の各ビットは10から25までを、set [1]の各ビットは26から41までを、…、set[5]の各ビットは90から99までを格納することになる。
　また、基本的な操作を行うための関数をすべて作成すること。

/*
    演習7-6
    ビットベクトルによる整数集合演算
*/

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

/* unsigned型のビット数 */
#define UNSIGNED_BIT    16

/* 第nビットのみがたったビットパターン */
#define BITof(no)       (1U << (no))

/* s->setの要素数*/
#define VBno(s)         (((s)->sz + UNSIGNED_BIT - 1) / UNSIGNED_BIT)

typedef struct {
    size_t    sz;       /* setの要素数 */
    int       max;      /* 要素の値の上限 */
    int       min;      /* 要素の値の下限 */
    unsigned  *set;     /* 集合（の先頭要素へのポインタ） */
} VBset;

/*--- 集合sを生成 ---*/
void VBsetAlloc(VBset *s, int m1, int m2)
{
    s->min = m1;
    s->max = m2;
    s->sz = (m2 - m1 + 1);
    s->set = calloc(VBno(s), sizeof(unsigned));
}

/*--- 集合sにnが入っているか ---*/
int VBsetMember(const VBset *s, int n)
{
    int idx;

    if (n < s->min || n > s->max)
        return (0);
    idx = (n - s->min) / UNSIGNED_BIT;
    return (s->set[idx] & BITof((n - s->min) % UNSIGNED_BIT));
}

/*--- 集合sにnを追加 ---*/
void VBsetInsert(VBset *s, int n)
{
    int idx;

    if (n < s->min || n > s->max)
        return;
    idx = (n - s->min) / UNSIGNED_BIT;
    s->set[idx] |= BITof((n - s->min) % UNSIGNED_BIT);
}

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

    if (n < s->min || n > s->max)
        return;
    idx = (n - s->min) / UNSIGNED_BIT;
    s->set[idx] &= ~(BITof((n - s->min) % UNSIGNED_BIT));
}

/*--- 集合s1からs2を引く ---*/
void VBsetDifference(VBset *s1, const VBset *s2)
{
    int i;

    for (i = s1->min; i <= s1->max; i++)
        if (VBsetMember(s2, i))
            VBsetDelete(s1, i);
}

/*--- 集合sの要素数 ---*/
int VBsetMemNum(const VBset *s)
{
    int  i, n = 0;

    for (i = 0; i < VBno(s); i++) {
        unsigned bits = s->set[i];
        for ( ; bits != 0; n++)
            bits &= bits - 1;
    }
    return (n);
}

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

    printf("{");
    for (i = s->min; i <= s->max; i++)
        if (VBsetMember(s, i))
            printf("%d ", i);
    printf("}\n");
}

/*--- 集合sのビットをダンプ ---*/
void VBsetDump(const VBset *s)
{
    int i, j;
    int idx;

    for (i = 0; i < VBno(s); i++) {
        unsigned bits = s->set[i];
        printf("%04d～：", s->min + i * UNSIGNED_BIT);
        for (j = 0; j < UNSIGNED_BIT; j++) {
            putchar((bits & 1U) ? '0' + (s->min + i * UNSIGNED_BIT + j) % 10 : '-');
            bits >>= 1;
        }
        putchar('\n');
    }
}

int main(void)
{
    int   i;
    VBset  s1, s2;

    VBsetAlloc(&s1, 1, 17);     /* s1は1～17 */
    VBsetAlloc(&s2, 0, 32);     /* s2は0～32 */

    VBsetInsert(&s1, 3);        /* s1 ← {3, 5, 7} */
    VBsetInsert(&s1, 5);
    VBsetInsert(&s1, 7);
    VBsetInsert(&s1, 17);

    VBsetInsert(&s2, 11);       /* s2 ← {11, 17} */
    VBsetInsert(&s2, 17);

    VBsetDifference(&s1, &s2);  /* s1 ← s1 - s2 */

    printf("s1 =");
    VBsetPrint(&s1);
    VBsetDump(&s1);

    printf("s2 = ");
    VBsetPrint(&s2);
    VBsetDump(&s2);


    return (0);
}

戻る