#자료구조와 함께 배우는 알고리즘 입문 C언어 - 8

7장 집합

 

07-1 집합

집합이란?

명확한 조건을 만족하는 자료의 모임

 

집합과 원소

집합 : 객관적으로 범위를 규정한 '어떤 것'의 모임

원소 : 집합 안에서 각각의 '어떤 것'

 

부분집합과 진부분집합

부분집합

A = {1, 3} ⊂ B = {1, 3, 5}	A = {1, 3, 5} ⊂⊃ B = {1, 3, 5}
o	o

진부분집합

A = {1, 3} ⊂ B = {1, 3, 5}	A = {1, 3, 5} ⊂⊃ B = {1, 3, 5}
o	x

 

집합의 연산

합집합 : A = {1, 3, 5} ∪ B = {1, 4, 6} = {1, 3, 4, 5, 6}

교집합 : A = {1, 3, 5} ∩ B = {1, 4, 6} = {1}

차집합 : A = {1, 3, 5} - B = {1, 4, 6} = {3, 5}

 

07-2 배열로 집합 만들기

// int형 집합 프로그램 헤더
#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);

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

void Print(const IntSet* s);

void PrintLn(const IntSet* s);

void Terminate(IntSet* s);
#endif

배열을 초기화하는 Initialize 함수

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

원소가 들어 있는지 확인하는 IsMember 함수

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

원소를 추가하는 Add 함수

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

원소를 삭제하는 Remove 함수

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

집합의 크기를 조사하는 Capacity 함수

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

집합의 원소 개수를 조사하는 Size 함수

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

집합을 복사하는 Assign 함수

void Assign(IntSet* s1, const IntSet* 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;
}

두 집합이 같은지 조사하는 Equal 함수

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;
		}
		if (j == s2->num)
			return 0;
	}
	return 1;
}

두 집합의 합집합을 구하는 Union 함수

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

두 집합의 교집합을 구하는 Intersection 함수

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

두 집합의 차집합을 구하는 Difference 함수

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

집합의 모든 원소를 출력하는 Pint와 PrintLn 함수

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

메모리를 정리하고 종료하는 Terminate 함수

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