BohYoh.comトップページへ

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

戻る  

演習7-3の解答

 関数SetAssign SetIntersection SetDifference は、代入先の配列の要素数が十分であるかのチェックを行っていない。それらのチェックを行うように改良せよ。

/* 演習7-3 List7-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; 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 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]; if (s1->num == s1->max) return; } } /*--- 集合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]; if (s1->num == s1->max) return; } } } /*--- 集合sの全要素を表示 ---*/ void SetPrint(const Set *s) { int i; printf("{ "); for (i = 0; i < s->num; i++) printf("%d ", s->set[i]); printf("}\n"); } int main(void) { Set s1, s2, s3, s4; if (SetAlloc(&s1, 10) == -1 || SetAlloc(&s2, 3) == -1 || SetAlloc(&s3, 2) == -1 || SetAlloc(&s4, 2) == -1 ){ puts("集合の確保に失敗しました。"); return (1); } SetInsert(&s1, 10); SetInsert(&s1, 15); /* s1 ← {10, 15, 20, 25} */ SetInsert(&s1, 20); SetInsert(&s1, 25); /* s2 = s1:ただし代入されるのは高々3個 */ SetAssign(&s2, &s1); /* s3 = s1 * s2:ただし代入されるは高々2個 */ SetIntersection(&s3, &s1, &s2); /* s4 = s1 - s2:ただし代入されるは高々2個 */ SetDifference(&s4, &s1, &s2); printf("s1 = "); SetPrint(&s1); printf("s2 = "); SetPrint(&s2); printf("s3 = "); SetPrint(&s3); printf("s4 = "); SetPrint(&s4); SetFree(&s1); SetFree(&s2); SetFree(&s3); SetFree(&s4); return (0); }


戻る