2016-09-07_조재찬_스터디일지_C언어-연결리스트의 정렬삽입

정렬 기능 추가된 연결 리스트의 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;
}

문제 4-3 연결리스트에 구조체 변수의 주소값 저장

Prob04-3.7z

Output : 

현재 데이터의 수: 4

[3 2][3 1][2 2][2 1]

현재 데이터의 수: 2

[3 2][3 1]

문제 4-4 Point 구조체의 정렬기준 등록

// PostListMain.c

#include <stdio.h>

#include <stdlib.h>

#include "Point.h"

#include "DLinkedList.h"

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

{

  if (d1->xpos < d2->xpos)

    return 0;    // x좌표의 값을 기준으로 d1이 정렬 순서상 앞선다.

  else if (d1->xpos == d2->xpos)

  {

    if (d1->ypos < d2->ypos)  // x 좌표값이 같으면 y 좌표 대상으로 오름차순 정렬

      return 0;

    else

      return 1;

  }

  else

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

}

int main(void)

{

  List list;

  Point compPos;

  Point * ppos;

  ListInit(&list, WhoIsPrecede);

  //SetSortRule(&list, )

  /*** 4개의 데이터 저장 ***/

  ppos = (Point*)malloc(sizeof(Point));

  SetPointPos(ppos, 3, 2);

  LInsert(&list, ppos);

  ppos = (Point*)malloc(sizeof(Point));

  SetPointPos(ppos, 3, 1);

  LInsert(&list, ppos);

  ppos = (Point*)malloc(sizeof(Point));

  SetPointPos(ppos, 2, 2);

  LInsert(&list, ppos);

  ppos = (Point*)malloc(sizeof(Point));

  SetPointPos(ppos, 2, 1);

  LInsert(&list, ppos);

(...이하 생략)

Output :

현재 데이터의 수: 4

[2 1][2 2][3 1][3 2]

현재 데이터의 수: 2

[3 1][3 2]