KU COSE101 2017기말고사 4번 문제

2016 기출	1번	2번	3번	4번	5번
2017 기출	1번	2번	3번	4번	5번
2018 기출	1번	2번	3번	4번	5번	6번

void insert(NodePtr, int) 함수도 만들어서 값을 넣어봅시다.

void showlist(NodePtr) 함수도 만들어서 insert, remove_dup, merge 함수가 제대로 작동하는지 확인해봅시다.

다음과 같이 정의된 linked list에 대해 다음 물음에 답하시오. (리스트의 마지막은 NULL로 표시함.)

typedef struct node{
  int val;
  struct node* next;
} Node, *NodePtr;

(a) 주어진 linked list가 오름차순으로 정렬되어있는지 확인하는 함수 is_sorted()를 작성하시오.

int is_sorted(NodePtr head) {

}

(b) 오름차순으로 정렬된 list에서 중복된 값이 있을 경우, 하나만 남겨두고 나머지는 모두 제거하는 함수 remove_dup()을 작성하시오. 예를 들어 1, 2, 2, 2, 3, 3은 1, 2, 3으로 변환한다. 제거되는 모든 node들은 free 되어야 한다.

NodePtr remove_dup(NodePtr x) {

}

(c) 두 개의 정렬된 linked list가 있을 때 이들을 정렬된 형태로 결합하는 함수 merge()를 작성하시오. 중복이 있는 경우, 중복을 포함하도록 하시오. 예를 들어 두 개의 linked list 0, 1, 3, 3, 4, 5와 2, 3, 4, 4, 5가 주어진다면 이 둘을 합한 linked list는 0, 1, 2, 3, 3, 3, 4, 4, 4, 5, 5 가 된다.

NodePtr merge(NodePtr x, NodePtr y) {

}

---

예시답안

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

typedef struct node{
	int val;
	struct node* next;
} Node, *NodePtr;

void insert(NodePtr head, int value) {
	NodePtr newPtr = (NodePtr)malloc(sizeof(Node));
	newPtr->val = value;
	newPtr->next = NULL;
	
	NodePtr curPtr = head;
	while(curPtr != NULL){
		if(curPtr->next == NULL){
			curPtr->next = newPtr;
			break;
		}
		curPtr = curPtr->next;
	}
}

int is_sorted(NodePtr head) {
	NodePtr prevPtr = head -> next;
	NodePtr curPtr = prevPtr -> next;
	
	while(curPtr != NULL){
		if(prevPtr->val > curPtr->val){
			return 0;
		}
		prevPtr = curPtr;
		curPtr = curPtr->next;
	}
	
	return 1;
}

NodePtr remove_dup(NodePtr x) {
	NodePtr prevPtr = x -> next;
	NodePtr curPtr = prevPtr -> next;
	
	while(curPtr != NULL) {
		if(curPtr->val == prevPtr->val) {
			prevPtr->next = curPtr->next;
			free(curPtr);
			curPtr = prevPtr->next;
		}
		else{
			prevPtr = curPtr;
			curPtr = curPtr->next;
		}
	}
	
	return x;
}

NodePtr merge(NodePtr x, NodePtr y) {
	NodePtr head = (NodePtr)malloc(sizeof(Node));
	NodePtr p;
	head->next = NULL;
	
	x = x->next;
	y = y->next;
	while(x!=NULL && y!=NULL){
		if(x->val > y->val){
			if(head->next==NULL) head->next=y;
			else p->next = y;
			p = y;
			y = y->next;
		}
		else{
			if(head->next==NULL) head->next=x;
			else p->next = x;
			p = x;
			x = x->next;
		}
	}
	if(x!=NULL) p->next = x;
	else p->next = y;
	
	return head;
}

void showlist(NodePtr head) {
	head = head->next;
	while(head != NULL){
		printf("%d --> ", head->val);
		head = head->next;
	}
	printf("NULL\n");
}

int main()
{
	int n,m,t;
	int i;
	NodePtr list1 = (NodePtr)malloc(sizeof(Node));
	NodePtr list2 = (NodePtr)malloc(sizeof(Node));
	list1->next = NULL;
	list2->next = NULL;
	
	scanf("%d",&n);
	for(i=0 ; i<n ; i++){
		scanf("%d",&t);
		insert(list1, t);
	}
	
	scanf("%d",&m);
	for(i=0 ; i<m ; i++){
		scanf("%d",&t);
		insert(list2, t);
	}
	
	NodePtr list = merge(list1, list2);
	showlist(list);
}