연결리스트2

정렬 기능 추가된 연결 리스트의 ADT

추가되는 함수

void SetSortRule(List * plist, int (*comp)(LData d1, Ldata d2)  

int (*comp)(LData d1, Ldata d2)  

반환형이 int인 LData형 인자를 두개 전달받는, 함수의 주소값 전달

(typedef LData int)

다음과 같이 정의된 함수의 주소값이 SetSortRule 함수의 두번째 인자가 됨

int WhoIsPrecede(LData d1, LData d2)

{

if(d1 < d2)

return 0; // d1이 head에 가까우면 0 반환

else

return 1; // d2가 head에 가까우면 1 반환

}

리스트라는 자료구조를 바꾸지 않으면서

정렬의 기준을 지정(약속)하는 함수를 정의

DLinkedList.h

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__
 
#define TRUE    1
#define FALSE    0
 
typedef int LData;
 
typedef struct _node
{
    LData data;
    struct _node * next;
} Node;
 
typedef struct _linkedList
{
    Node * head;
    Node * cur;
    Node * before;
    int numOfData;
    int (*comp)(LData d1, LData d2);
} LinkedList;
 
 
typedef LinkedList List;
 
void ListInit(List * plist);
void LInsert(List * plist, LData data);
 
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
 
LData LRemove(List * plist);
int LCount(List * plist);
 
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));
 
#endif

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

SetSortRule 함수 : 정렬 기준이 되는 함수 

LinkedList의 멤버 comp : SetSortRule 함수를 통해 전달된 함수 정보 저장

SInsert : comp에 등록된 정렬기준을 근거로 데이터 저장

-> SetSortRule 함수가 호출되면서 정렬 기준이 리스트의 멤버 comp에 등록되면,

Sinsert 함수내에서 comp에 등록된 정렬기준을 근거로 데이터를 정렬해 저장한다.

SInsert 함수

pred(predicate)가 첫번째 노드가 아닌 더미노드를 가리키는 이유

: 노드가 한쪽 방향으로만 연결되있어서 pred가 가리키는 노드의 오른쪽에만

새 노드를 추가할 수 있기 때문이다.

Sinsert함수의 while문 조건의 의미

while (pred->next != NULL &&
        plist->comp(data, pred->next->data) != 0)

조건 1.

pred->next != NULL // 연결리스트의 끝에 도달했음을 의미

조건 2.

plist->comp(data, pred->next->data) != 0

// 첫번째 인자인 data가 앞서면 0을 반환해서 숫자의 대소를 비교해나감. (오름차순 기준)

newNode -> data = data;

정렬의 기준을 설정하기 위한 함수

int WhoIsPrecede(int d1, int d2) // 오름차순 정의

{

if (d1 < d2)

return 0;    // d1이 정렬 순서상 앞선다.

else

return 1;    // d2가 정렬 순서상 앞서거나 같다.

}

comp에 등록된 함수가 반환하는 값의 종류와 의미를 결정

main함수에서 SetSortRule(&list, WhoIsPrecede);    // 정렬의 기준 등록

DLinkedList.c

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
 
void ListInit(List * plist)
{
  plist->head = (Node *)malloc(sizeof(Node));
  plist->head->next = NULL;
  plist->comp = NULL;
  plist->numOfData = 0;
}
 
void FInsert(List * plist, LData data)
{
  Node * newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
 
  newNode->next = plist->head->next;
  plist->head->next = newNode;
  (plist->numOfData)++;
}
 
void SInsert(List * plist, LData data)
{
  Node * newNode = (Node*)malloc(sizeof(Node));
  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)++;
}
 
 
void LInsert(List * plist, LData data)
{
  if(plist->comp == NULL)
    FInsert(plist, data);
  else
    SInsert(plist, data);
}
 
int LFirst(List * plist, LData * pdata)
{
  if (plist->head->next == NULL)
    return FALSE;
 
  plist->before = plist->head;
  plist->cur = plist->head->next;
 
  *pdata = plist->cur->data;
  return TRUE;
}
 
int LNext(List * plist, LData * pdata)
{
  if (plist->cur == NULL)
    return FALSE;
 
  plist->before = plist->cur;
  plist->cur = plist->cur->next;
 
  *pdata = plist->cur->data;
  return TRUE;
}
 
LData LRemove(List * plist)
{
  Node * rmPos = plist->cur;
  Node * rmData = plist->cur->data;
 
  plist->before->next = plist->cur->next;
  plist->cur = plist->before;
 
  free(rmPos);
  (plist->numOfData)--;
  return rmData;
}
 
int LCount(List * plist)
{
  return plist->numOfData;
}
 
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
  plist->comp = comp;
}