배열로 집합 만들기

• 구조체 IntSet: int형 원소를 갖는 집합을 관리

typedef struc{
    int max; //집합의 최대 크기
    int num; //집합의 원소 개수
    int* set; //집합
} IntSet;

 

• 헤더 파일 IntSet.h

#ifndef ___IntSet
#define ___IntSet

typedef struct {
	int max;	
	int num;	
	int *set;	
} IntSet;

int Initialize(IntSet *s, int max);

int IsMember(const IntSet *s, int n);

int IsFull(const IntSet *s);

void Add(IntSet *s, int n);

void Remove(IntSet *s, int n);

int Capacity(const IntSet *s);

int Size(const IntSet *s);

void Assign(IntSet *s1, const IntSet *s2);

int Equal(const IntSet *s1, const IntSet *s2);

IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3);

IntSet *Intersection(IntSet *s1, const IntSet *s2, const IntSet *s3);

IntSet *Difference(IntSet *s1, const IntSet *s2, const IntSet *s3);

IntSet *SymmetricDifference(IntSet *s1, const IntSet *s2, const IntSet *s3);

IntSet *ToUnion(IntSet *s1, const IntSet *s2);

IntSet *ToIntersection(IntSet *s1, const IntSet *s2);

IntSet *ToDifference(IntSet *s1, const IntSet *s2);

int IsSubset(const IntSet *s1, const IntSet *s2);

int IsProperSubset(const IntSet *s1, const IntSet *s2);

void Print(const IntSet *s);

void PrintLn(const IntSet *s);

void Clear(IntSet *s);

void Terminate(IntSet *s);

#endif

 

 

• 소스파일 IntSet.c

#include <stdio.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;
}

int IsFull(const IntSet* s) {
	return s->num >= s->max;
}

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

void Assign(IntSet* s1, const IntSet* s2) { //집합 s2를 s1에 복사
	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;
}

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[j]) break; //s2에서 같은 요소를 찾으면 나감
		if (j == s2->num) return 0; //s2에서 같은 요소를 끝까지 찾지 못하면 false(0)
	}
	return 1;
}

IntSet* Union(IntSet* s1, const IntSet* s2, const IntSet* s3) { //s2와 x3의 합집합을 s1에 대입
	int i;
	Assign(s1, s2);
	for (i = 0; i < s3->num; i++) {
		Add(s1, s3->set[i]);
	}
	return s1;
}

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

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

IntSet* SymmetricDifference(IntSet* s1, const IntSet* s2, const IntSet* s3) { //대칭차
	int i;

	s1->num = 0;

	for (i = 0; i < s2->num; i++)
		if (IsMember(s3, s2->set[i]) == -1)
			Add(s1, s2->set[i]);

	for (i = 0; i < s3->num; i++)
		if (IsMember(s2, s3->set[i]) == -1)
			Add(s1, s3->set[i]);

	return s1;
}

IntSet *ToUnion(IntSet *s1, const IntSet *s2){ //s1에 s2의 원소를 추가
	int i;

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

	return s1;
}

IntSet *ToIntersection(IntSet *s1, const IntSet *s2){ //s1에서 s2에 없는 원소를 삭제
	int i = 0;

	while (i < s1->num) {
		if (IsMember(s2, s1->set[i]) == -1)
			Remove(s1, s1->set[i]);
		else
			i++;
	}
	return s1;
}

IntSet *ToDifference(IntSet *s1, const IntSet *s2){ //s1에서 s2에 있는 원소를 삭제
	int i;

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

	return s1;
}

int IsSubset(const IntSet *s1, const IntSet *s2){ //s1이 s2의 부분집합이면 1 아니면 0 반환
	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)					
			return 0;
	}
	return 1;
}

int IsProperSubset(const IntSet *s1, const IntSet *s2){ //s1이 s2의 진부분집합이면 1 아니면 0 반환
	int i;

	if (s1->num >= s2->num)					
		return 0;							

	return IsSubset(s1, s2);
}

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 Clear(IntSet *s){ //s의 모든 원소를 삭제
	s->num = 0;
}

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

 

 

• IntSet을 사용하는 프로그램 IntSetTest.c

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

enum {ADD, RMV, SCH};

int scan_data(int sw) {
	int data;
	switch (sw) {
	case ADD: printf("추가할 데이터 : "); break;
	case RMV: printf("삭제할 데이터 : "); break;
	case SCH: printf("검색할 데이터 : "); break;
	}
	scanf_s("%d", &data);

	return data;
}

int main(void) {
	IntSet s1, s2, temp;
	Initialize(&s1, 512); Initialize(&s2, 512); Initialize(&temp, 512);

	while (1) {
		int m, x, idx;

		printf("s1 = "); PrintLn(&s1);
		printf("s2 = "); PrintLn(&s2);
		printf("(1)s1에 추가 (2)s1에서 삭제 (3)s1에서 검색 (4)s1<-s2 (5)여러 연산\n"
			"(6)s2에 추가 (7)s2에서 삭제 (8)s2에서 검색 (9)s2<-s1 (0)종료 : ");

		scanf_s("%d", &m);
		if (m == 0) break;

		switch (m) {
		case 1: x = scan_data(ADD); Add(&s1, x); break;
		case 2: x = scan_data(RMV); Remove(&s1, x); break;
		case 3: x = scan_data(SCH); idx = IsMember(&s1, x); 
			printf("s1에 들어있%s.\n", idx >= 0 ? "습니다" : "지 않습니다");  break;
		case 4: Assign(&s1, &s2); break;
		case 5: printf("s1 == s2 = %s\n", Equal(&s1, &s2) ? "true" : "false");
			printf("s1 & s2 ="); Intersection(&temp, &s1, &s2);
			PrintLn(&temp);
			printf("s1 | s2 ="); Union(&temp, &s1, &s2);
			PrintLn(&temp);
			printf("s1 - s2 ="); Difference(&temp, &s1, &s2);
			PrintLn(&temp);
			break;
		case 6: x = scan_data(ADD); Add(&s2, x); break;
		case 7: x = scan_data(RMV); Remove(&s2, x); break;
		case 8: x = scan_data(SCH); idx = IsMember(&s2, x);
			printf("s2에 들어있%s.\n", idx >= 0 ? "습니다" : "지 않습니다");  break;
		case 9: Assign(&s2, &s1); break;
		}
	}
	Terminate(&s1); Terminate(&s2); Terminate(&temp);

	return 0;
}