Copy /*
                집합
                
                2008. 11. 13.
*/
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int SZ_NAME = 64;
const int SZ_BUFF = 20;

/*
*       선언부
*/
typedef struct _node{
        char *name;
        struct _node *next;
}linkedList;

typedef struct {
        linkedList *head;
        linkedList *tail;
        int size;
}linkedList_h;

typedef linkedList_h Set;
#define createSetHead createListHead

/*
*       내부 인터페이스
*/
linkedList_h *createListHead();
BOOL list_ins_next(linkedList_h *, const char *);
BOOL list_ins_next(linkedList_h *, linkedList *, const char *);
int list_rem_next(linkedList_h *);
void list_print(linkedList_h *);

/*
*       사용자 인터페이스
*/
BOOL set_insert(Set *, char *);
BOOL set_is_member(Set *, char *);
Set *set_union(Set *, Set *);
Set *set_intersection(Set *, Set *);
Set *set_difference(Set *, Set *);

int main()
{
        Set *S1 = createSetHead();
        Set *S2 = createSetHead();
        Set *setu = createSetHead();
        Set *seti = createSetHead();
        Set *setd = createSetHead();

        set_insert(S1, "CC");
        set_insert(S1, "AA");
        set_insert(S1, "DD");
        set_insert(S1, "FF");

        set_insert(S2, "AA");
        set_insert(S2, "BB");
        set_insert(S2, "FF");

        list_print(S1);
        list_print(S2);

        puts("");
        setu = set_union(S1, S2); /* S1 과 S2 의 합집합 */
        list_print(setu);

        puts("");
        seti = set_intersection(S1, S2); /* S1 과 S2 의 교집합 */
        list_print(seti);

        puts("");
        setd = set_difference(S1, S2); /* S1 과 S2 의 차집합 */
        list_print(setd);

        return 0;
}

/*
*       집합 정의부
*/
BOOL set_insert(Set *S, char *str)
{
        /*
                TODO: 집합에 같은 멤버가 있으면 리턴한다. 중복 삽입을 방지.
        */
        if(set_is_member(S, str))
        {      
                return TRUE;
        }

        return list_ins_next(S, str);
}

BOOL set_is_member(Set *S, char *str)
{
        linkedList *p = S->head;

        while(p != NULL)
        {
                if(strcmp(p->name, str) == 0)
                {
                        return TRUE;
                }
                p = p->next;
        }

        return FALSE;
}

Set *set_union(Set *S1, Set *S2)
{
        Set *setu = createSetHead();
        linkedList *p = S1->head;

        while(p != NULL)
        {
                list_ins_next(setu, S1->tail, p->name);
                p = p->next;
        }

        p = S2->head;
        while(p != NULL)
        {
                if(set_is_member(setu, p->name))
                        {/* no work */}
                else
                        list_ins_next(setu, S2->tail, p->name);
                p = p->next;
        }

        return setu;
}

Set *set_intersection(Set *S1, Set *S2)
{
        Set *seti = createSetHead();
        linkedList *p = S1->head;

        while(p != NULL)
        {
                if(set_is_member(S2, p->name))
                {
                        list_ins_next(seti, p->name);
                }
                p = p->next;
        }

        return seti;
}

Set *set_difference(Set *S1, Set *S2)
{
        Set *setd = createSetHead();
        linkedList *p = S1->head;

        while(p != NULL)
        {
                if(!set_is_member(S2, p->name))
                {
                        list_ins_next(setd, p->name);
                }
                p = p->next;
        }

        return setd;
}

/*
*       연결 리스트 정의부
*/
linkedList_h *createListHead()
{
        linkedList_h *r = NULL;
        r=(linkedList_h*)malloc(sizeof(linkedList_h));
        r->head=NULL;
        r->tail=NULL;
        r->size=0;
        return r;
}

/*
        인자가 리스트 헤더와 입력 데이터면 가장 앞 노드에 새 노드를 추가한다.
*/
BOOL list_ins_next(linkedList_h *L, const char *str)
{
        /*
                TODO: 새 노드 생성 후 데이터를 삽입한다.
        */
        linkedList *newNode = NULL;
        newNode = (linkedList*)malloc(sizeof(linkedList));
        if(newNode == NULL)
        {
                printf("Memory Set ERROR.\n");
                exit(1);
        }
        newNode->name = (char*)malloc(sizeof(char)*SZ_NAME);
        strcpy(newNode->name, str);
        newNode->next = NULL;

        /*
                TODO: 리스트에 노드가 없으면 헤드에 새 노드를 넣고 리턴한다.
        */
        if(L->head == NULL)
        {
                L->head = newNode;      
                L->tail = newNode;
                ++(L->size);
                return FALSE;
        }

        /*
                TODO: 가장 앞 노드(L->head)에 새 노드를 추가한다.
        */
        newNode->next = L->head;
        L->head = newNode;
        ++(L->size);
        return FALSE;
}

/*
        인자가 리스트 헤더, 노드, 입력 데이터면 전달받은 노드 뒤에 새 노드를 추가한다.
*/
BOOL list_ins_next(linkedList_h *L, linkedList *t, const char *str)
{
        /*
                TODO: 새 노드 생성 후 데이터를 삽입한다.
        */
        linkedList *newNode = NULL;
        newNode = (linkedList*)malloc(sizeof(linkedList));
        if(newNode == NULL)
        {
                printf("Memory Set ERROR.\n");
                exit(1);
        }
        newNode->name = (char*)malloc(sizeof(char)*SZ_NAME);
        strcpy(newNode->name, str);
        newNode->next = NULL;

        /*
                TODO: 리스트에 노드가 없으면 헤드에 새 노드를 넣고 리턴한다.
        */
        if(L->head == NULL)
        {
                L->head = newNode;      
                L->tail = newNode;
                ++(L->size);
                return FALSE;
        }

        /*
                TODO: 타겟 노드까지 이동한다.
        */
        linkedList *p = L->head;
        while(p->next != NULL || p == t)
        {
                p = p->next;
        }

        /*
                TODO: 타겟 노드 뒤에 새 노드를 추가한다.
        */
        newNode->next = p->next;
        p->next=newNode;
        ++(L->size);
        if(L->tail->next != L->head)
        {       /* 추가된 노드가 테일이면 L->tail 을 새 노드로 한다. */
                L->tail = newNode;
        }
        return FALSE;
}

int list_rem_next(linkedList_h *L)
{
        int r = 0;
        linkedList *p = L->head;

        L->head = L->head->next;
        
        r = atoi(p->name);
        free(p);

        return r;
}

void list_print(linkedList_h *L)
{
        if(L->head == NULL)
        {
                printf("! 리스트가 존재하지 않습니다.\n");
                return;
        }

        linkedList *p = L->head;
        while(1){
                if(p->next == NULL)
                {
                        printf(" %s -> NULL\n", p->name);
                        break;
                }
                else
                {
                        printf(" %s ->", p->name);
                }
                p = p->next;
        }
}

void list_free(linkedList_h *L)
{
        if(L->head == NULL)
                return;

        linkedList *p = L->head;
        while(1)
        {
                if(L->head == L->tail)
                {
                        free(L->head);
                        free(L);
                        break;
                }
                p = L->head;
                L->head = L->head->next;
                free(p);        
        }
}