[집합과 검색] #1. 집합과 연결리스트

집합이란?

집합	명확한 조건을 만족하는 자료의 모임 객관적으로 범위를 규정한 “어떤 것“의 모임
원소	집합 안에서 각각의 “어떤 것”

집합의 특징

1. 집합의 원소에는 순서가 없다.
2. 집합에 포함되는 원소는 서로 달라야 한다.
3. 집합은 집합을 원소로 가질 수 없다.

집합 ADT

• 유일한 개체들을 담는 용기
• 효율적인 구현을 위해 원소들의 정렬된 리스트로 표현한다.

직접응용	키워드 검색엔진 집합론에 관련된 다양한 계산
간접응용	알고리즘을 위한 보조 데이터 구조 다른 데이터구조를 구성하는 요소

연결리스트와 집합

• 같은 집합의 원소들은 하나의 연결 리스트로 관리
• 연결 리스트의 맨 앞의 원소를 집합의 대표 원소

하나의 원소로 이루어진 집합	연결 리스트로 된 두 집합
대표원소로 본인을 가리키고, 다음 노드를 가리키고 있지 않음	각 원소들은 대표 원소를 가리키고, 서로 연결됨 두 집합을 합치게 될 경우, 적은 수의 원소를 가진 집합을 다른 한 집합의 뒤에 합치는 것이 효율적

집합 구현: 배열

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//배열 A,B에 5개의 정수를 각각 입력후 합집합 계산
int main() {
	int A[5], B[5];
	int ans[10];
	int i, j = 0, k = 5;
	for (i = 0; i < 5; i++) scanf("%d", &A[i]);
	for (i = 0; i < 5; i++) scanf("%d", &B[i]);
	for (i = 0; i < 5; i++) ans[i] = A[i];
	for (j = 0; j < 5; j++) {
		for (i = 0; i < 5; i++) {
			if (B[j] == A[i])
				break;
			if (i == 4) {
				ans[k] = B[j];
				k++;
			}
		}
	}
	for (i = 0; i < k; i++)printf("%d", ans[i]);
}

1. 두 개의 배열을 선언하고 값을 입력받는다.
2. 2중 반복문을 이용하여 두 배열 간의 값을 비교하고, 중복된 값이 없는 경우 결과 배열에 저장한다.

집합 구현: 연결리스트

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

typedef struct ListNode {
	int data;//현재 노드가 가지고 있는 데이터(값)
	struct ListNode *next;//다음 노드의 위치
    struct ListNode *pre;//이전 노드의 위치
}ListNode;

void add(ListNode *head, int rank, int value){//구조체 함수
    ListNode* curr = head; //순회용 노드 생성
    for(int i=0;i<rank;i++)curr= curr->next;

    ListNode *p=(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.
    p->data = value;

    p->next = curr->next;
    curr->next = p;

    p->pre = curr;
    (p->next)->pre = p;
    // printf("추가된 노드의 데이터는 %c입니다.\n",p->data);

}

void function_arrangement(ListNode* head,ListNode* tail){

    head->next = tail;
    head->pre = NULL;

    tail->next = NULL;
    tail->pre = head;

}
int main(){
    int num,cnt = 5;
    ListNode* A_head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    ListNode* A_trail = (ListNode*)malloc(sizeof(ListNode)); //트레일 노드 생성
    function_arrangement(A_head,A_trail);

    ListNode* B_head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    ListNode* B_trail = (ListNode*)malloc(sizeof(ListNode)); //트레일 노드 생성
    function_arrangement(B_head,B_trail);

    ListNode* rst_head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    ListNode* rst_trail = (ListNode*)malloc(sizeof(ListNode)); //트레일 노드 생성
    function_arrangement(rst_head,rst_trail);

    for(int i=0;i<5;i++){scanf("%d",&num);add(A_head,i,num);}
    for(int i=0;i<5;i++){scanf("%d",&num);add(B_head,i,num);}

    ListNode* curr = A_head->next; //순회용 노드 생성
    ListNode* result = rst_head->next; //합집합 저장 구조체 포인터 선언
    for(int i=0;i<5;i++){
        add(rst_head,i,curr->data);
        // printf("%d\n", curr->data);
	    curr = curr->next;
    }free(curr);
    
    //합집합
    ListNode* cmp_A = A_head->next; //순회용 노드 생성
    ListNode* cmp_B = B_head->next; //순회용 노드 생성
    for (int j=0;j<5;j++) {
        cmp_A = A_head->next;
		for (int i=0;i<5;i++) {
			if(cmp_B->data == cmp_A->data)break;
            if(i == 4){
                // printf("check!\n");
                add(rst_head,cnt,cmp_B->data);
                cnt ++;
            }
            cmp_A = cmp_A->next;
		}
        cmp_B = cmp_B->next;
	}


    ListNode* prt = rst_head->next; //순회용 노드 생성
    for(int i=0;i<cnt;i++){
        printf("%d\n", prt->data);
	    prt = prt->next;
    }free(prt);

}

1. 연결리스트 구조체를 정의한다.
2. 연결리스트의 데이터를 추가할 add함수를 생성한다. (C언어 알고리즘에서 상세히 다루겠다.)
3. 합집합은 두 집합의 공통된 원소의 집합이므로 순회를 통해 같은 값이 아닌 값을 결과 집합에 저장한다.