어제 많은 내용을 복습해서 오늘은 막 그렇게 복습할 내용이 많진 않을거다.
어제는 LinkedList를 노드를 활용해서 구현을 하는 과정중 LRemove 까지 소개를 했다. SetSortRule을 제외하고 왠만한 추가 / 조회 / 삭제 과정은 다 소개를 한 것. 이제 연결 리스트 정렬 삽입을 이해하면서 구현해보겠다
SetSortRule
여기서 우리가 이해해야 할 부분은 크게 세 개로 나눠보겠다.
1. 연결 리스트의 정렬기준이 되는 함수를 등록해주는 "SetSortRule"
2. SetSortRule 을 통해 전달된 함수정보를 저장하기 위한 "LinkedList의 멤버, comp"
3. comp에 등록된 정렬 기준을 근거로, 데이터를 저장하는 함수 "SInsert"
이렇게 크게 세 갈래로 나눠서 이해를 할건데, 이걸 전체적인 맥락으로 묶어 이해한다면
"SetSortRule 함수가 호출 되면서 어떤 정렬 기준이 List의 멤버인 comp에 저장이 되면, 이 comp에 저장된 정렬 기준을 근거로 해서 SInsert를 통해 데이터를 정렬, 저장한다"
SetSortRule 그 자체에는 크게 뭐 구현해줄게 없다. 그냥 얘의 역할은 정렬기준이 되는 함수를 등록해주는거다.
아마 코드를 보면, 이해가 빠를거다.
void SetSortRule(List *plist, int (*comp) (LData d1, LData d2)) {
plist->comp = comp;
}plist가 우리가 main함수에서 set한 어떤 list가 될거고, 우리가 필요로 하는건 이 "list의 정렬 기준"이 필요한데, 두번째 인자인 int (*comp) 뭐시기 함수 포인터에서 정렬 기준을 불러오면 그 정렬기준을 "plist의 정렬 기준"으로 저장해주면 된다는 소리다.
이 정렬기준은 앞에서 다뤘던 WhoIsPrecede 함수같은걸 생각해주면 된다.
그러면, 이제 SInsert가 필요할거다.
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)++;
}아마 아무것도 모르고 그냥 이걸 본다면
" 뭔 개소리냐 " 싶을거다. 일일히 생각해보겠다.
우선 FInsert와 SInsert 중 이 SInsert를 어떤 때에 해주느냐.
앞서 211115 복습 내용을 보면 이런 내용이 있다.
void LInsert(List *plist, LData data) {
if(plist->comp = NULL) FInsert(plist, data);
else SInsert(plist, data);
}LInsert 라는 데이터를 저장(삽입)하는 함수의 내용인데, 보면 plist->comp != NULL. 즉, list의 정렬 기준이 존재할 때 SInsert를 해준다는 거다. 잊지 말고 기억해두자.
그리고 pred라는 새로운 포인터가 등장했는데, 얘는 LinkedList의 head 부분에 있는 더미노드를 말한다.
그리고 그 밑의 while문. 우선 첫번째 조건인 "pred->next != NULL". 말 그대로 이 pred가 가리키는 노드의 다음 노드가 존재할 때.
그리고 두번째 조건인 plist->comp(data, pred->next->data) != 0. 이게 처음 보면 좀 어려울 수도 있다.
만약 함수 포인터 comp가 아래와 같은 함수를 나타낸다고 치자.
int WhoIsPrecede(int d1, int d2) {
if (d1 < d2) return 0;
else return 1;
}그러면 comp(data, pred->next->data)가 0이 아닌 1일 때, 즉 1을 return할 때 조건이 만족된다는 것이다. 1을 만족한다는 것은 d1 >= d2라는 소리이다. 그림으로 예를 들겠다.
이게 SInsert에서 while문 까지의 과정이다. (p->n->d 는 pred->next->data)
그리고 그 이후 나머지. 이런 과정으로, comp, 즉 정렬 기준이 있을때 데이터의 추가가 이루어진다.
여기까지, 연결 리스트였다.
