[알고리즘] 기본 추상자료형(2) - 예제(집합ADT)

[문제1] 집합A와 B를 입력받고, A가 B의 부분집합인지를 검사하는 프로그램(단일연결리스트)

- 오름차순 양의 정수로 저장 및 출력

- A ⊂ B이면 0을 출력, A ⊄ B이면 집합B에 속하지 않은 집합 A의 가장 작은 원소를 출력

입력예시            출력예시

3 5 10 15 4 5 20 25 30

10

입력예시            출력예시

0 3 5 10 15

0

입력예시            출력예시

3 5 10 15 0

5

#include<stdio.h> #include<stdlib.h> struct node { int number; struct node *next; }; void addSet(struct node *set, int number){ struct node *newElement = (struct node*)malloc(sizeof(struct node)); newElement->number = number; newElement->next = NULL; while (set->next != NULL){ set = set->next; } set->next = newElement; } int subSet(struct node *firstSet, struct node *secondSet){ if (firstSet == NULL){ return 0; } else{ while (firstSet != NULL){ if (secondSet == NULL) { return firstSet->number; } else if (firstSet->number < secondSet->number){ return firstSet->number; } else if (firstSet->number > secondSet->number){ secondSet = secondSet->next; } else{ firstSet = firstSet->next; secondSet = secondSet->next; } } return 0; } } void freeSet(struct node *set) { struct node *ptr = set; while (ptr != NULL){ set = set->next; free(ptr); ptr = set; } } void main(){ int setSize, number; struct node *firstSet = (struct node*)malloc(sizeof(struct node)); struct node *secondSet = (struct node*)malloc(sizeof(struct node)); firstSet->number = NULL; secondSet->number = NULL; firstSet->next = NULL; secondSet->next = NULL; scanf("%d", &setSize); for (int i = 0; i < setSize; i++){ if (i == 0){ scanf("%d", &number); firstSet->number = number; } else{ scanf("%d", &number); addSet(firstSet, number); } } scanf("%d", &setSize); for (int i = 0; i < setSize; i++) { if (i == 0) { scanf("%d", &number); secondSet->number = number; } else { scanf("%d", &number); addSet(secondSet, number); } } printf("%d\n", subSet(firstSet, secondSet)); freeSet(firstSet); freeSet(secondSet); }

[문제2] 집합A와 B를 입력받고, A와B의 합집합과 교집합을 구하는 프로그램

- 오름차순 양의 정수로 저장 및 출력

입력예시             출력예시

0 5 1 3 5 7 9

1 3 5 7 9  0

입력예시             출력예시

0 0

0  0

#include<stdio.h> #include<stdlib.h> struct node { int number; struct node *next; }; void addSet(struct node *set, int number) { struct node *newElement = (struct node*)malloc(sizeof(struct node)); newElement->number = number; newElement->next = NULL; while (set->next != NULL) { set = set->next; } set->next = newElement; } struct node *Union(struct node *firstSet, struct node *secondSet){ struct node *first = firstSet; struct node *second = secondSet; struct node *sumSet = (struct node*)malloc(sizeof(struct node)); sumSet->number = NULL; sumSet->next = NULL; if ((first->next == NULL) && (second->next == NULL)){ return sumSet; } else if (first->next == NULL){ free(sumSet); return second; } else if (second->next == NULL){ free(sumSet); return first; } else{ first = first->next; second = second->next; while ((first != NULL) && (second != NULL)){ if (first->number == second->number){ addSet(sumSet, first->number); first = first->next; second = second->next; } else if (first->number < second->number){ addSet(sumSet, first->number); first = first->next; } else if (first->number > second->number){ addSet(sumSet, second->number); second = second->next; } } while (first != NULL){ addSet(sumSet, first->number); first = first->next; } while (second != NULL){ addSet(sumSet, second->number); second = second->next; } } return sumSet; } struct node *intersect(struct node *firstSet, struct node *secondSet){ struct node *first = firstSet; struct node *second = secondSet; struct node *intersect = (struct node*)malloc(sizeof(struct node)); intersect->number = NULL; intersect->next = NULL; if ((first->next == NULL) && (second->next == NULL)){ return intersect; } else if (first->next == NULL){ return intersect; } else if (second->next == NULL){ return intersect; } else{ first = first->next; second = second->next; while ((first != NULL) && (second != NULL)){ if (first->number == second->number){ addSet(intersect, first->number); first = first->next; second = second->next; } else if (first->number < second->number){ first = first->next; } else if (first->number > second->number){ second = second->next; } } } return intersect; } void printSet(struct node *set) { struct node *ptr = set->next; if (ptr == NULL) { printf(" 0\n"); } else { while (ptr != NULL) { printf(" %d", ptr->number); ptr = ptr->next; } printf("\n"); } } void freeSet(struct node *set) { struct node *ptr = set; while (ptr != NULL) { set = set->next; free(ptr); ptr = set; } } void main(){ int setSize, number; struct node *firstSet = (struct node*)malloc(sizeof(struct node)); struct node *secondSet = (struct node*)malloc(sizeof(struct node)); struct node *sumSet, *intersectSet; firstSet->number = NULL; firstSet->next = NULL; secondSet->number = NULL; secondSet->next = NULL; scanf("%d", &setSize); for (int i = 0; i < setSize; i++){ scanf("%d", &number); addSet(firstSet, number); } scanf("%d", &setSize); for (int i = 0; i < setSize; i++) { scanf("%d", &number); addSet(secondSet, number); } sumSet = Union(firstSet, secondSet); printSet(sumSet); intersectSet = intersect(firstSet, secondSet); printSet(intersectSet); freeSet(firstSet); freeSet(secondSet); if ((sumSet != firstSet) && (sumSet != secondSet)) { freeSet(sumSet); } freeSet(intersectSet); }