합병 정렬 리스트로 구현해보기

단일리스트 형태로 만들어서 합병정렬을 구현해 봄.

 

 

 

코딩 후기 및 추가적으로 더 확인 할 것

 

1.코딩 초보라서 만드는데도 오래걸리고 오류를 찾는 방식도 어리숙해서 오래걸렸다.  

 

2. 메모리 해제와 관련된 부분들은 정확히 처리하지 않고 일단 돌아가게만 했다.

 

3. 메인함수에서 free(list); 하면 코드가 중단되는데 왜 그럴지. 

(2018.06.28 추가)병슨인게 result나 list나 같은 리스트네.. 

그에 따라서 mergeSort();는 void형으로 바꾸고 메인함수에 mergeSort의 반환형을 result로 받는 부분은 삭제하면 될 것 같다. 

 (추가 의문,아 그리고, 해제할 때는 노드 하나하나 해제해야하는 건지. )

조교님한테 물어봤는데 노드 하나하나 제거해주는게 맞음. 그 다음에 리스트를 제거해줘야함.

(왜냐하면 리스트지워버리면 노드에 접근이 안되기 때문에 노드를 하나하나 접근해서 차례차례 지우고, 그다음에 리스트를 제거해주면 된다.)

//해당 내용들은 코드에 반영 안했음. 논리적으로 확실히 이해되서 굳이 코딩하면서 시간 쓰지 않기로 함.

 

4. NODE, LIST 구조체를 만들어서 초기화 하는 방식을 각각을 함수를 썼는데, mem이라는 함수로 간단하게 구현가능하더라

 

 

 

 

코드를 올리는 건, 내가 공부할 때 힘들었기 때문에 다른 사람들에게 조금이나마 참고할만한 자료를 제공해서 조금은 쉽게 공부했으면 해서이다.

 

단순히 배끼는 것은 본인에게 도움이 안되니, 아 이 허접새끼는 이렇게 짜놨구나 하고, 참고하거나 더 좋은 코드를 만들려고 하는게 좋을 것 같다.

 

//단일 연결리스트 버전

//초기에 onenote에 대략적인 구조를 만들고, 일단 나름은 완성했다고 만들었는데 안돌아감.

//1.디버깅 + 2.코드를 진행하면서 진행 과정이나 메모리 구조등을 직접 그려보면서  오류 하나씩 수정해봄.

#include
#include
//#include


typedef struct Node {
	int elem;
	struct Node* next;
}NODE;

typedef struct List {
	NODE* head;
}LIST;


typedef struct List2 {
	LIST* front;
	LIST* rear;
}L2;


NODE* initNode(int e) 
{
	NODE * node = (NODE*)malloc(sizeof(NODE));
	node->next = NULL;
	node->elem = e;
	return node;
}

LIST* initList() 
{
	LIST* list = (LIST*)malloc(sizeof(LIST));
	list->head = initNode(NULL);
	return list;
}

void insertNode(LIST* list, NODE* node)
{
	node->next = list->head->next;
	list->head->next = node;
}

int sizeList(LIST* list)
{
	int size = 0;
	NODE * finger = list->head;
	while (finger->next != NULL)
	{
		size++;
		finger = finger->next;
	}
	return size;
}

void printList(LIST* list)
{
	NODE* finger = list->head->next;
	while (finger->elem != NULL)
	{
		printf(" %d", finger->elem);
		finger = finger->next;
		if (finger == NULL)
			break;
	}
	printf("\n");
}

//-------------------------------------------------------본격적인 내용

LIST* mergeSort(LIST* list);
L2 partition(LIST* list);
void merge(LIST* L1, LIST* L2);

void main()
{
	LIST* list = initList();

	int n , e;
	scanf("%d", &n);

	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &e);
		NODE* node = initNode(e);
		insertNode(list, node);
	}

	//printList(list);

	LIST* result = initList();

	result = mergeSort(list);

	printList(result);

	free(result);
	//free(list);
}
 

 LIST* mergeSort(LIST* list)
 {
	 L2 two_list;
	 
	 if (sizeList(list) > 1)
	 {
		 two_list = partition(list);
		 
		 mergeSort(two_list.front);
		 mergeSort(two_list.rear);

		 merge(two_list.front, two_list.rear);
	 }
	 return list;
 }


 L2 partition(LIST* list) {
	 int m = sizeList(list) / 2;

	 NODE* finger = list->head;
	 NODE* temp;
	 int count = 0;

	 while (count < m) {
		 finger = finger->next;
		 count++;                 //손가락이 리스트의 중간부분을 가리키도록 하고
	 }
	
	 //본격적으로 나누는 작업

	 temp = finger->next;
	 finger->next = NULL;

	 LIST* N = initList();
	 N->head->next = temp;
	 //printf("%d\n", temp->elem);
	 //system("pause");
	 L2 two_list;
	 

	 two_list.front = list;
	 //printf("%d\n", two_list.front->head->next->elem);
	 two_list.rear = N;
	 //printf("%d\n", two_list.rear->head->next->elem);
	 //system("pause");
	 return two_list;

 }


 void merge(LIST* L1, LIST* L2)
 {
	 NODE* fingerMain = L1->head;     //결과 리스트 위에서 작업하기 위한 인덱스
	 NODE* finger1 = L1->head->next;
	 NODE* finger2 = L2->head->next;

	 while (1)
	 {
		 if (finger1 == NULL)
		 {
			 fingerMain->next = finger2;
			 break;
		 }
		 else if (finger2 == NULL)
		 {
			 fingerMain->next = finger1;
			 break;
		 }
		 else if (finger1->elem <= finger2->elem)
		 {
			 fingerMain->next = finger1;
			 fingerMain = fingerMain->next;
			 finger1 = finger1->next;
			 
		 }
		 else
		 {
			 fingerMain->next = finger2;
			 fingerMain = fingerMain->next;
			 finger2 = finger2->next;
			 
		 }
	 }
	 free(L2->head);
	 free(L2);
 }