[12]

배열로 집합 만들기

"IntSet.h"

#ifndef ___IntSet
#define ___IntSet

typedef struct{
        int max; // 집합의 크기
        int num; // 집합의 원소 개수
        int *set; // 집합 본체의 배열
}IntSet;

//집합 초기화
int Initialize(IntSet *s,int max);

//s에 n이 있는지
int IsMember(const IntSet *S,int n);

//s에 n을 추가
void Add(IntSet *s,int n);

//s에 n을 삭제 
void Remove(IntSet *s, int n);

//s의 최대원소개수 반환
int Capacity(const IntSet *s);

//s의 원소개수
int Size(const IntSet *s);

//집합 s2를 s1에 대입
void Assign(IntSet *s1, const IntSet *s2);

집합 s1과 s2가 같은지
int Equal(const IntSet *s1, const IntSet *s2);

//집합 s2와 s3의 합집합을 s1에 대입
IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3);

//집합 s2와 s3의 교집합을 s1에 대입
IntSet *Intersection(IntSet *s1, const IntSet *s2, const IntSet *s3);

//s2에서 s3을 뺀 차집합을 s1에 대입
IntSet *Difference(IntSet *s1, const IntSet *s2, const IntSet *s3);

// s의 모든원소 출력
void Print(const IntSet *s);

// s의 모든원소 출력(줄바꿈 추가)
void PrintLn(const IntSet *s);

//집합 종료
void Terminate(IntSet *s);
#endif

"IntSet.c"

#include<stdlio.h>
#include<stdlib.h>
#include "IntSet.h"

int Initialize(IntSet s, int max){
        s->num=0;
        if((s->set = calloc(max,sizeof(int))) == NULL){
                s->max=0;
                return -1;
        }
        s->max = max;
        return 0;
}

int IsMember(const IntSet *s, int n){
        int i;
        for(i=0; i<s->num; i++)
                if(s->set[i] ==n) return i
        return -1;
}

void Add(IntSet *s, int n){
        if(s->num < s->max && IsMember(s,n) == -1)
                s->set[s->num++] = n;
}

void Remove(IntSet *s, int n){
        int idx;
        if((idx = IsMember(s,n)) != -1){
                s->set[idx] = s->set[--s->num];
        }
}

int Capacity(const IntSet *s){
        return s->max;
}

int Size(const IntSet *s){
        return s->num;
}

IntSet *Intersection(IntSet *s1, const IntSet *s2, const IntSet *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])
                                Add(s1,s2->set[i]);
        return s1;
}

int Equal(const IntSet *s1, const IntSet *s2){
        int i,j;
        if(Size(s1) != Size(s2))
                return 0;
        for(i=0; i<s1->num; i++){
                for(j=0; j<s2->num; j++)
                        if(s1->set[i] == s2->set[i]) break;
                        if(j==s2->num) return 0;
        }
        return 1;
}

IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3){
        int i;
        Assign(s1,s2);
        for(i=0; i<s3->num; i++)
                Add(s1,s3->set[i]);
        return s1;
}

IntSet *Difference(IntSet *s1, const IntSet *s2, const IntSet *s3){
        int i,j;
        s->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) Add(s1,s2->set[i]);
        }
        return s1;
}

void Print(const IntSet *s){
        int i;
        printf("{");
        for(i=0; i<s->num; i++)
                printf("%d", s->set[i]);
        printf("}");
}

void PrintLn(const IntSet *s){
        print(s);
        putchar('\n');
}

void Terminate(IntSet *s){
        if(s->set != NULL){
                free(s->set);
                s->max = s->num =0;
        }
}