본문 바로가기
Datastructure/[Algorithm]

[자료구조] 연결리스트의 집합 구현

old-cast1e 2022. 2. 6.
728x90
반응형

합집합

#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);

}

교집합

#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 = 0;
    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* 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++) {
            // printf("cmp_B->data = %d | cmp_A->data = %d\n",cmp_B->data,cmp_A->data);
			if(cmp_B->data == cmp_A->data){
                // printf("check!\n");
                add(rst_head,cnt,cmp_B->data);
                cnt ++; break;
            }
            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);


}

차집합

#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 delete(ListNode *head, int data){
    //해당 데이터를 찾을 때까지 순회하고, 찾으면 해당 노드를 삭제함.
    ListNode* removed = head; //삭제용 노드 생성
	while(removed != NULL){
        if(removed->data == data){
            (removed->next)->pre = removed->pre;
            (removed->pre)->next = removed->next;
            free(removed); return;
        }
		removed = removed->next;
	}
}

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

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

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

}
int main(){
    int num;
    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; //순회용 노드 생성
    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; //순회용 노드 생성
    ListNode* cmp_B = B_head->next; //순회용 노드 생성

    //차집합은 일단 A의 요소를 결과 리스트에 저장하고 B리스트와 겹치는 부분을 빼서 만들면됨.
    for (int j=0;j<5;j++) {
        cmp_A = A_head->next;
		for (int i=0;i<5;i++) {
            // printf("cmp_B->data = %d | cmp_A->data = %d\n",cmp_B->data,cmp_A->data);
			if(cmp_B->data == cmp_A->data){
                delete(rst_head,cmp_A->data);
                break;
            }
            cmp_A = cmp_A->next;
		}
        cmp_B = cmp_B->next;
	}


   ListNode* prt = rst_head->next; //삭제용 노드 생성
	while(prt != NULL){
        printf("%d ",prt->data);
		prt = prt->next;

        if(prt->next == NULL) break;
	}
}
728x90
반응형
저작자표시

'Datastructure > [Algorithm]' 카테고리의 다른 글

[자료구조] 검색의 활용  (0) 2022.02.10
[자료구조] 선형 검색  (0) 2022.02.06
[자료구조] 연결리스트의 활용 2 : 다항식 덧셈  (0) 2022.02.06
[자료구조] 연결리스트 ADT  (3) 2022.01.24
[자료구조] 배열 연습문제(3): 행렬  (0) 2022.01.19

'Datastructure/[Algorithm]' 관련글

댓글

티스토리툴바