이제 연결리스트의 정렬 삽입을 구현해 볼것이다.
우리가 구현한 연결리스트에서 정렬기준의 설정과 관련 있는 부분은 다음과 같다. 따라서 이들은 하나로 묶어서 이해해야 한다.
1. 연결리스트의 정렬기준이 되는 함수를 등록하는 SertSortRule 함수
2. SerSortRule 함수를 통해서 전달된 함수 정보를 저장하기 위한 LinkedList의 멤버 comp
3. comp에 등록된 정렬 기준을 근거로 데이터를 저장하는 SInsert함수
위에서 언급한 세 가지를 하나의 문장으로 정리하면 다음과 같다.
"SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInesrt함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다."
이렇듯 SetSortRule 함수는 리스트의 멤버 comp를 초기화하는 함수이므로 다음과 같이 간단히 정의할 수 있다.
void SetSortRule(List *plist, int(*comp) (LData d1, LData d2))
{
plist->comp = comp;
}
이서 SInsert 함수를 소개하겠다. 이 함수도 리스트이 멤버 comp의 활용에 대한 부분이 생소할 뿐 나머지는 익순한 코드들이다.
void SInsert(List *plist, LData data)
{
Node * newNode = (Node *) malloc(sizeof(Node)); //새 노드 생성
Node *pred = plist-> head; //pred는 더미노드를 가리킴
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)++; //저장된 데이터의 수 하나 증가
}
위 함수의 반복문에서 보이듯이 comp에 등록된 함수의 호출결가를 기반으로 새 노드가 추가될 위치를 찾는다.
다음과 같이 리스트가 구성된 상황이라 가정한다.
head-> DMY->2->4->6->NULL
위 리스트는 오름차순으로 데이터 저장된 상황이다. 이 상황에서 다음 문장이 실행된다고 가정해보자.
참고로 이 문자에서 slist는 위 그림의 리스트를 의미한다.
SInsert(&slist, 5); //리스트에 숫자 5를 저장
위의 함수 호출로 인해서 다음 세 문장이 실행된다.
void SInsert(List *plist, LData data)
{
Node * newNode = (Node *) malloc(sizeof(Node)); //새 노드 생성
Node *pred = plist-> head; //pred는 더미노드를 가리킴
newNode ->data = data; //새 노드에 데이터 저장
....
}
이로 인해서 새 노드에 숫자 5가 저장되고, 다음에 보이듯이 모든 노드를 차례로 가리키기 위해 선언된 포인터 변수 pred는 더미노드를 가리키게 된다.
head->DMY->2->4->6->NULL
pred->DMY
newNode->5
위의 상황에서 포인터 변수 pred가 숫자 2가 저장된 첫번째 노드가 아닌 더미노드를 가리키는 이유를 알아야한다.
우리는 노드를 추가할때도 포인터 변수 pred를 활용한다. 그런데 한쪽방향으로만 연결이 형성되어 있어서 pred가 가리키는 노드의 오른쪽에는 새 노드를 추가할 수 있어도 왼쪽에는 새 노드를 추가할 수 없다. 그래서 pred는 더미노드부터 가리키는 것이다. 그럼 이어서 실행되는 반복문을 보자
//새 노드가 들어갈 위치를 찾기 위한 반복문
while(pred->next !=NULL && plist->comp(data, pred->next->data) != 0)
{
pred = pred ->next; //다음 노드로 이동
}
위의 반복문은 잠시후에 별도로 설명한다. 그러니 위의 반복문을 탈출하고 나면 다음 상황과 같이 pred가 가리키는 노드의 오른쪽에 새 노드가 추가되어야 한다는 사실만 인식해야한다.
head->DMY->2->4->6->NULL
pred->4
newNode->5
이렇듯 pred는 새 노드를 추가하는데 있어서 중요한 정보를 담고있다. 따라서 이어지는 다음 문장을 통해 새 노드는 제자리를 찾게 된다.
newNode ->next = pred->next; 새 노드의 오른쪽을 연결
pred ->next = newNode; //새 노드의 왼쪽을 연결
(plist->numOfData)++; //저장된 데이터의 수 하나 증가
위의 문장을 실행한 결과는
head->DMY->2->4->5->6->NULL
pred->4
newNode->5
이로써 SInsert 함수의 노드 추가에 대한 큰 흐름은 모두 설명하였다. 남은 것은 SInsert 함수 내에서 존재하는 정렬 삽입의 핵심이 되는 while문에 대한 이해이다.
SInsert 함수의 while 문은 언뜻 복잡해 보이나 반복의 조건을 나누어 생각하면 별로 복잡하지 않다.
반복의 조건1 pred->next !=NULL
pred가 리스트이 마지막 노드를 가리키는 지 묻기 위한 연산
반복의 조건 2 plist->comp(data, pred->next->data)!= 0)
새 데이터 pred의 다음 노드에 저장된 데이터의 우선순위 비교를 위한 함수호출
따라서 다음 반복문이 의미하는 바는
while(pred->next != NULL && plist->comp (data, pred->next->data)!=0)
{
pred= pred->next; //다음 노드로 이동
}
다음과 같이 정리할 수 있다.
"pred가 마지막 노드를 가리키는 것도 아니고, 새 데이터가 들어갈 자리도 아직 찾지 못했다면 pred를 다음 노드로 이동시킨다."
그럼 이제 우선순위 비교를 위한 다음 함수 호출에 대해 설명하겠다.
plist->comp (data, pred->next->data)!=0
comp에 등록된 함수가 반환하는 값의 종류와 그 의미는 다음과 같다.
comp가 0을 반환
첫번째 인자인 data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우
comp가 1을 반환
두번째 인자인 pred->next->data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우
물론 이러한 반환 값의 종류와 그 의미는 앞서 우리가 결정한 것이다.
"매개변수인 d1에 전달되는 인자가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우에는 0을 반환하고, 매개변수인 d2에 전달되는 인자가 정렬 순서상 앞서거나 같은 경우에는 1을 반환한다"
이제 반복문에 관한 모든것이 명확해졌다. 첫 번째 인자로 전달된 데이터가 head에 더 가까워야 하는 경우 0을 반환하도록 약속했기 때문에 위와 같이 반복문을 구성한 것이다.
이제 마지막으로 남은 일은 정렬의 기준을 결정하는 함수, 다시 말해서 함수 SetSortRule의 인자가 될수 있는 함수를 정의하는 일이다. 이 함수를 정의하는데 있어서 필요한 정보 두가지를 정리하면 다음과 같다.
1. 두개의 인자를 전달받을수 있도록 함수를 정의한다.
2. 첫번째 인자의 정렬 우선순위가 높으면 0을 , 그렇지 않으면 1을 반환한다.
이 두가지만 만족한다면 어떤 함수건 SetSortRule의 인자가 될수 있다. 그럼 위의 두 조건을 만족하는 함수를 먼저 보이겠다.
int WhoIsPrecede(int d1, int d2) //typedef int LData;
{
if (d1 <d2)
return 0; //d1이 정렬 순서상 앞선다
else
return 1; //d2가 정렬순서상 앞서거나 같다
}
물론 이는 앞서 한차례 보인 함수이다. 하지만 SInsert 함수를 본 이후이니 느낌이 다를 것이다, 그럼 위의 함수를 보고서 정렬의 기준을 말해보자.
첫번째 인자인 d1이 두번째 인자인 d2보다 그 값의 크기가 작을때 0을 반환한다 . 즉 값이 작을수록 정렬의 우선순위가 높다. 따라서 '오름차순 정렬'을 위한 함수라 할 수 있다. 그렇다면 내림차순 정렬을 위해서는 위의 함수를 어떻게 바꿔야 하겠는가? 간단하다. 첫번째 인자인 d1의 값이 두번째 인자 d2보다 클 때 0을 반환하게 하면 된다.
이제 마지막으로 함수를 추가해서 예제를 실행하여, 실제로 오름차순으로 정렬이 되는지 확인을 할 차례이다.
프로그래머가 연결리스트의 정렬 기준을 결정하도록 유연성을 부여하기 때문에 , 따라서 연결리스트를 활용하는 main함수가 정의되어있는 소스파일에 위 함수를 저장해야 한다.
#include <stdio.h>
#include "DLinkedList.h"
int WhoIsPreCede(int d1, int d2)
{
if(d1 <d2)
return 0; //d1이 정렬 순서상 앞선다
else
return 1; //d2가 정렬 순서상 앞서거나 같다.
}
int main()
{
List list;
int data;
ListInit(&list);
SetSortRule(&list, WhoIsPrecede); // 정렬의 기준을 등록한다.
LInest(&list, 11); LInest(&list, 11);
LInest(&list, 22); LInest(&list, 22);
LInest(&list, 33);
printf("현재 데이터 수 : %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
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))
{
if(data ==22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data==22)
LRemove(&list);
}
printf("\n\n");
return 0;
}
===============================실행 결과======================
현재 데이터의 수 : 5
11 11 22 22 33
현재 데이터의 수 : 3
11 11 33
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 양방향 연결 리스트 (0) | 2021.02.16 |
|---|---|
| 원형 연결 리스트 (0) | 2021.02.15 |
| 연결리스트2 (0) | 2021.02.13 |
| 링크드리스트1 (0) | 2021.02.12 |
| 배열 기반의 리스트(List)2 (0) | 2021.02.09 |