Chapter 04. 연결 리스트의 정렬 삽입의 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

앞서 구현한 연결 리스트에서 정렬 기준의 설정과 관련 있는 부분은 다음과 같습니다. 따라서 이들은 하나로 묶어서 이해해야 합니다.

• 연결 리스트의 정렬기준이 되는 함수를 등록하는 SetSortRule 함수
• SetSortRule 함수를 통해서 전달된 함수 정보를 저장하기 위한 LinkedList의 멤버 comp
• comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수

위에서 언급한 세 가지를 하나의 문장으로 정리하면 다음과 같습니다.

 "SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다." 

이렇듯 SetSortRule 함수는 리스트의 멤버 comp를 초기화하는 함수이므로 다음과 같이 간단히 정의할 수 있습니다.

void SetSortRule(List* plist, int (*comp)(LData d1, LData d2))
{
	plist->comp = comp;
}

 

이어서 SInsert 함수입니다.

void SInsert(List* plist, LData data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) exit(1);
	Node* pred = plist->head;

	newNode->data = data;

	//새 노드가 들어갈 위치를 찾기 위한 반복문
	while (pred->next != NULL && plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next;
	}

	newNode->next = pred->next;
	pred->next = newNode;

	plist->numOfData++;
}

위 함수의 반복문을 제외하고는 이해하기 쉬울 것입니다. 반복문에 대해서 설명하겠습니다.

 

위 반복문은 첫 번째 노드부터 시작해서 해당 노드의 값과 입력된 데이터를 비교합니다. 비교 기준이 무엇인지는 알 필요가 없습니다. 하지만 설명을 위해 예를 들겠습니다. 데이터를 만약 오름차순으로 정렬한다면, pred를 계속 다음 노드로 옮겨가면서 data와 값을 비교하는데 어느 순간 pred->next의 데이터가 data보다도 큽니다. 그렇게 되면 pred와 pred->next 사이에 newNode가 삽입되어야 합니다. 따라서 newNode가 pred->next를 가리키도록 하고, pred->next가 newNode를 가리키도록 하는 것입니다.

 

혹시 설명이 부족했다면 언제든지 물어봐주시기 바랍니다.

---

이제 마지막으로 남은 일은 정렬의 기준을 결정하는 함수를 정의하는 것입니다. 이 함수는 다음과 같이 간단하게 정의할 수 있습니다.

int WhoIsPrecede(int d1, int d2)
{
	if(d1 < d2) return 0;

	return 1;
}

위 함수는 오름차순을 보이는 함수입니다. 만약 내림차순을 적용하고 싶다면 다음과 같이 수정할 수 있습니다.

int WhoIsPrecede(int d1, int d2)
{
	if(d1 > d2) return 0;

	return 1;
}

위 함수는 DLinkedList.h 파일이나 DLinkedList.c 파일에 정의되지 않습니다. 정렬의 기준은 프로그래머가 유연하게 정할 수 있어야 하므로 main.c 파일에 프로그래머가 직접 정의하여 사용할 수 있도록 합니다.

 

즉, 다음과 같이 main 함수를 작성해야 합니다.

//main.c 소스 파일로 저장
#include <stdio.h>
#include "DLinkedList.h"

int WhoIsPrecede(int d1, int d2)
{
	if (d1 < d2) return 0;

	return 1;
}

int main(void)
{
	//리스트의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	//정렬의 기준 등록
	SetSortRule(&list, WhoIsPrecede);

	//5개의 데이터 저장
	LInsert(&list, 11); 
	LInsert(&list, 22);
	LInsert(&list, 33); 
	LInsert(&list, 11);
	LInsert(&list, 22);

	//저장된 데이터의 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	//숫자 22를 검색하여 모두 삭제
	if (LFirst(&list, &data))
	{
		if (data == 22) LRemove(&list);

		while (LNext(&list, &data))
		{
			if (data == 22) LRemove(&list);
		}
	}

	//삭제 후 남아 있는 데이터 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}

/*
실행결과

현재 데이터의 수 : 5
11 11 22 22 33

현재 데이터의 수 : 3
11 11 33

*/