[자료구조][집합] c구현 재귀/ 반복문

목차

c언어를 공부 하는 겸 집합을 구현해 보고자 했다.

재귀를 이용한 방식과 반복문을 이용한 방식 두가지로 구현해 보았다.

 

 

문제

입력 예시

6 ↦ 집합 A 크기

3 7 45 88 99 101 ↦ 집합 A

4 ↦ 집합 B 크기

7 10 15 45 ↦ 집합 B

 

출력 예시

1 3 7 10 15 45 88 99 101 ↦ 합집합

7 45 ↦ 교집합 

 

struct 구조

typedef struct Node {
	struct Node* next;
	int data;
}Node;

typedef struct List {
	Node* head;
	Node* cur;
	int size;
}List;

 

반복문을 이용한 코드

//합 집합 구현 함수
List* Union(List* a, List* b) {
	List* list = (List*)malloc(sizeof(List));
	init(list);
	a->cur = a->head;
	b->cur = b->head;
	while (a->cur != NULL && b->cur != NULL) { //두 값중 하나라도 null을 가르키면 종료
		if (a->cur->data < b->cur->data) {   //적은 값을 추가하고 다음으로 이동
			add(list, a->cur->data);
			a->cur = a->cur->next;
		}
		else if (a->cur->data > b->cur->data) {
			add(list, b->cur->data);  //적은 값을 추가하고 다음으로 이동
			b->cur = b->cur->next;

		}
		else {
			add(list, b->cur->data);   //값 추가하고 둘다 다음으로 이동
			b->cur = b->cur->next;
			a->cur = a->cur->next;
		}
	}
	if (a->cur != NULL) {  //null값이 아니면 마저 순회하고 추가
		while (a->cur != NULL) {
			add(list, a->cur->data);
			a->cur = a->cur->next;
		}
	}
	if (b->cur != NULL) {   //null값이 아니면 마저 순회하고 추가
		while (b->cur != NULL) {
			add(list, b->cur->data);
			b->cur = b->cur->next;
		}
	}
	return list; 
}

 

//교집합 구현 함수
List* Intersect(List* a, List* b) {
	List* list = (List*)malloc(sizeof(List));
	init(list);
	a->cur = a->head;
	b->cur = b->head;
	while (a->cur != NULL && b->cur != NULL) {  //두 값이 null이 아닐때까지 이동
		if (a->cur->data < b->cur->data) {
			a->cur = a->cur->next;
		}
		else if (a->cur->data > b->cur->data) {  //적은 값 이동
			b->cur = b->cur->next;
		}
		else {
			add(list, a->cur->data);  //값이 같으면 둘 다 이동
			b->cur = b->cur->next;
			a->cur = a->cur->next;
		}
	}
	return list;
}

 

재귀를 이용한 코드

//합 집합 구현 함수
void Union(List* list, Node* a, Node* b) {
	if (a == NULL && b == NULL)  //기저 사례
		return;
	if (a == NULL) {   //a가 null이면 b만 다음 노드를 가르키고 함수 호출
		add(list, b->data);
		Union(list, a, b->next);
	}
	else if (b == NULL) {  //b가 null이면 a만 다음 노드를 가르키고 함수 호출
		add(list, a->data); 
		Union(list, a->next, b);
	}
	else {   //둘 다 값이 있을 경우
		if (a->data < b->data) {  //적은 값 추가하고 이동
			add(list, a->data);
			Union(list, a->next, b);
		}
		else if (a->data > b->data) {   //적은 값 추가하고 이동
			add(list, b->data);
			Union(list, a, b->next);
		}
		else {   //값 추가하고 둘다 이동
			add(list, b->data);
			Union(list, a->next, b->next);
		}
	}
}

 

//교집합 구현 함수
void Intersect(List* list, Node* a, Node* b) {
	if (a == NULL && b == NULL)  //기저 사례
		return;
	if (a == NULL) {  //a가 null인 경우 b의 다음 노드 가르키고 함수 호출
		Intersect(list, a, b->next);
	}
	else if (b == NULL) {   //b가 null인 경우 a의 다음 노드 가르키고 함수 호출
		Intersect(list, a->next, b);
	}
	else {
		if (a->data < b->data) {   //적은 값 추가하고 다음으로 이동
			Intersect(list, a->next, b);
		}
		else if (a->data > b->data) {  //적은 값 추가하고 다음으로 이동
			Intersect(list, a, b->next);
		}
		else {
			add(list, b->data);  //값 추가하고 둘 다 이동
			Intersect(list, a->next, b->next);
		}
	}

	
}

 

 

공통 구현 함수

void init(List *list) {
	list->head = NULL;
	list->size = 0;
	list->cur = NULL;
}

void clear(List *list) {
	list->cur = list->head;
	while (list->cur != NULL) {
		Node* del = list->cur;
		list->cur = list->cur->next;
		free(del);
	}

}

void add(List* list, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;
	if (list->head == NULL) {
		list->head = newNode;
		list->cur = list->head;
	}
	else {
		list->cur->next = newNode;
		list->cur = list->cur->next;
	}
	list->size++;
}

void print(List *list) {
	if (list->head == NULL)
		return;
	list->cur = list->head;
	while (list->cur != NULL) {
		printf(" %d", list->cur->data);
		list->cur = list->cur->next;
	}
	printf("\n");
}