집합ADT

유일한 개체들을 담는 자료구조를 모델링
집합을 집합 원소들의 정렬된 리스트로 표현

메소드

집합A에 대한 집합연산 : $O(|A|+|B|)$를 만족해야 함.
이 연산은 파괴적일수도, 비파괴적일 수도 있음.

• set union(B) : A∪B
• set intersect(B) : A∩B
• set subtract(B) : A - B

일반메소드

• integer size()
• boolean isEmpty()
• iterator elements()

질의메소드

• boolean member(e) : e가 집합에 있는가
• boolean subset(B) : 이 집합이 집합B의 부분집합인가

갱신메소드

• addElem(e)
• removeElem(e)

예외

• emptySetException() : 비어있는 집합의 원소를 삭제/접근

집합연산에 필요한 내용의 구현

• getNode()
• putNode()
• init()
• addLast()
• removeFirst()
• getFirst()
• isEmpty()

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

typedef struct _Node {
	struct _Node* prev;
	struct _Node* next;
	int elem;
} Node;

typedef struct _List {
	struct _Node* H;
	struct _Node* T;
} List;

Node* getNode() {
	Node* n = (Node*)malloc(sizeof(Node));
	n->prev = NULL;
	n->next = NULL;
	return n;
}

void putNode(Node* p) {
	free(p);
}

List init() {
	List L;
	L.H = getNode();
	L.T = getNode();
	(L.H)->next = (L.T);
	(L.T)->prev = (L.H);

	return L;
}

void addLast(List L, int e) {
	Node* T = L.T;
	Node* n = getNode();
	n->elem = e;
	n->prev = T->prev;
	n->next = T;
	(T->prev)->next = n;
	T->prev = n;
}

void removeFirst(List L) {
	Node* H = L.H;
	Node* newNext = (H->next)->next;
	H->next = newNext;
	newNext->prev = H;
}

int getFirst(List L) {
	Node* H = L.H;
	return (H->next)->elem;
}

bool isEmpty(List L) {
	Node* H = L.H;
	Node* T = L.T;

	return (H->next == T) ? true : false;
}

집합연산

union

• 파괴적 메소드

Alg union(B)
  input set A, set B
  output set A∪B
1. C ← empty list
2. while( !(A.isEmpty()) & !(B.isEmpty()) )
     a, b ← A.get(1), B.get(1)
     if(a < b)
       C.addLast(a)
       A.removeFirst()
     else if(a > b)
       C.addLast(b)
       B.removeFirst()
     else
       C.addLast(a)
       A.removeFirst()
       B.removeFirst()
3. while( !(A.isEmpty()) )
     a ← A.get(1)
     C.addLast(a)
     A.removeFirst()
4. while( !(B.isEmpty()) )     
     b ← B.get(1)
     C.addLast(b)
     B.removeFirst()
5. return C

List Union_Destructive(List A, List B) {
	List C = init();
	while (!isEmpty(A) && !isEmpty(B)) {
		int a = getFirst(A);
		int b = getFirst(B);
		if (a < b) {
			addLast(C, a);
			removeFirst(A);
		} else if (a > b) {
			addLast(C, b);
			removeFirst(B);
		} else {
			addLast(C, a);
			removeFirst(A);
			removeFirst(B);
		}
	}
	while (!isEmpty(A)) {
		int a = getFirst(A);
		addLast(C, a);
		removeFirst(A);
	}
	while (!isEmpty(B)) {
		int b = getFirst(B);
		addLast(C, b);
		removeFirst(B);
	}

	return C;
}

• 비파괴적 메소드

Alg union(B)
  input set A, set B
  output set A∪B
1. if((A=∅)&(B=∅))
     return ∅
2. p ← getNode()
3. if(A=∅)
     p.elem ← B.elem
     p.next ← union(A, B.next)
   else if(B=∅)
     p.elem ← A.elem
     p.next ← union(A.next, B)
   else
     P.elem ← A.elem
     p.next ← union(A.next, B.next)
4. return p

Node* Union_Non_Destructive(Node* A, Node* B) {
	if (A==NULL && B==NULL) {
		return NULL;
	}
	
	Node* p = getNode();
	if (A==NULL) {
		p->elem = B->elem;
		p->next = Union_Non_Destructive(A, B->next);
	}
	else if (B==NULL) {
		p->elem = A->elem;
		p->next = Union_Non_Destructive(A->next, B);
	}
	else {
		p->elem = A->elem;
		p->next = Union_Non_Destructive(A->next, B->next);
	}

	return p;
}
List Union_Non_Destructive_Caller(List A, List B) {
	List C = init();
	Node* head = Union_Non_Destructive((A.H)->next, (B.H)->next);

	(C.H)->next = head;

	Node* p = head;
	while (p->next != NULL)
		p = p->next;
	(C.T)->prev = p;

	return C;
}

intersect

• 파괴적 메소드

Alg intersect(B)
  input set A, set B
  output set A∩B
1. C ← empty list
2. while( !(A.isEmpty()) & !(B.isEmpty()) )
     a, b ← A.get(1), B.get(1)
     if( a < b )
       A.removeFirst()
     else if ( a > b )
       B.removeFirst()
     else 
       C.addLast(a)
       A.removeFirst()
       B.removeFirst()
3. return C

List intersect_Destructive(List A, List B) {
	List C = init();

	while (!isEmpty(A) && !isEmpty(B)) {
		int a = getFirst(A);
		int b = getFirst(B);
		if (a < b) {
			removeFirst(A);
		}
		else if (a > b) {
			removeFirst(B);
		}
		else {
			addLast(C, a);
			removeFirst(A);
			removeFirst(B);
		}
	}

	return C;
}

• 비파괴적 메소드

Alg intersect(B)
  input set A, set B
  output set A∩B
1. if( (A=∅)||(b=∅) )
     return ∅
2. if(A.elem < B.elem)
     return intersect(A.next, B)
   else if(A.elem > B.elem)
     return intersect(A, B.next)
   else
     p ← getNode()
     p.elem = A.elem
     p.next = intersect(A.next, B.next)
     return p

Node* intersect_NonDestructive(Node* A, Node* B) {
	if (A == NULL || B == NULL) {
		return NULL;
	}

	while (1) {
		int a = A->elem;
		int b = B->elem;
		if (a < b) {
			return intersect_NonDestructive(A->next, B);
		}
		else if (a > b) {
			return intersect_NonDestructive(A, B->next);
		}
		else {
			Node* p = getNode();
			p->elem = a;
			p->next = intersect_NonDestructive(A->next, B->next);
			return p;
		}
	}
}

List intersect_NonDestructive_caller(List A, List B) {
	List C = init();
	Node* head = intersect_NonDestructive((A.H)->next, (B.H)->next);

	(C.H)->next = head;

	Node* p = head;
	while (p->next != NULL)
		p = p->next;
	(C.T)->prev = p;

	return C;
}

subtract

• 파괴적 메소드

Alg subtract(B)
  input set A, set B
  output set A-B
1. C ← empty list
2. while( !(A.isEmpty()) & !(B.isEmpty()) )
     a, b ← A.get(1), B.get(1)
     if( a < b )
       C.addLast(a)
       A.removeFirst()
     else if( b > a )
       B.removeFirst()
     else
       A.removeFirst()
       B.removeFirst()
3. while( !(A.isEmpty()) )
     a ← A.get(1)
     C.addLast(a)
     A.removeFirst()
4. return C

List subtract_Destructive(List A, List B) {
	List C = init();

	while (!isEmpty(A) && !isEmpty(B)) {
		int a = getFirst(A);
		int b = getFirst(B);
		if (a < b) {
			addLast(C, a);
			removeFirst(A);
		} else if (a > b) {
			removeFirst(B);
		} else {
			removeFirst(A);
			removeFirst(B);
		}
	}
	while (!isEmpty(A)) {
		int a = getFirst(A);
		addLast(C, a);
		removeFirst(A);
	}
	
	return C;
}

• 비파괴적 메소드

Alg subtract(B)
  input set A, set B
  output set A-B
1. if( (A=∅)&(B=∅) )
     return ∅
   else if(A=∅)
     return ∅
   else if(B=∅)
     return A
2. 

member

Alg member(e)
  input set A, element e
  output bool of e∈A
1. if(A=∅)
     return True
2. p ← A
3. while(True)
     a ← p.elem
     if(e < a)
       if(p.next = ∅)
         return False
       else
         p ← p.next
     else if(e > a)
       return False
     else 
       return True

bool member(List A, int e) {
	if (isEmpty(A)) {
		return false;
	}

	Node* p = (A.H)->next;
	while (1) {
		int a = p->elem;
		if (e < a) {
			if (p->next == NULL) {
				return false;
			}
			else {
				p = p->next;
			}
		}
		else if (e > a) {
			return false;
		}
		else {
			return true;
		}
	}
}

subset

Alg subset(B)
  input set A, set B
  output bool of A⊂B
1. if(A=∅)
     return True
2. p ← A
3. while(True)
     a ← p.elem
     if(B.member(a))
       if(p.next = ∅)
         return True
       else
         p ← p.next
     else
       return False

bool subset(List A, List B) {
	if (isEmpty(A) || isEmpty(B)) {
		return false;
	}

	Node* p = (A.H)->next;
	while (1) {
		int a = p->elem;
		
		if (member(B, a)) {
			if (p->next == NULL) {
				return true;
			}
			else {
				p = p->next;
			}
		}
		else {
			return false;
		}
	}
}