Chapter 04. 연결 리스트(Linked List) 2

Presentation on theme: "Chapter 04. 연결 리스트(Linked List) 2"— Presentation transcript:

1 Chapter 04. 연결 리스트(Linked List) 2
연결 리스트의 개념적인 이해

2 Linked! 무엇을 연결하겠다는 뜻인가! 일종의 바구니, 연결이 가능한 바구니
typedef struct _node { int data; // 데이터를 담을 공간 struct _node * next; // 연결의 도구! } Node; 일종의 바구니, 연결이 가능한 바구니 예제 LinkedRead.c의 분석을 시도 바랍니다!

3 예제 LinkedRead.c의 분석: 초기화
typedef struct _node { int data; struct _node * next; } Node; int main(void) Node * head = NULL; Node * tail = NULL; Node * cur = NULL; Node * newNode = NULL; int readData; } ∙ head, tail, cur이 연결 리스트의 핵심! ∙ head와 tail은 연결을 추가 및 유지하기 위한것 ∙ cur은 참조 및 조회를 위한것 LinkedRead.c의 일부

4 예제 LinkedRead.c의 분석: 삽입 1회전
while(1) { printf("자연수 입력: "); scanf("%d", &readData); if(readData < 1) break; // 노드의 추가과정 newNode = (Node*)malloc(sizeof(Node)); newNode->data = readData; newNode->next = NULL; if(head == NULL) head = newNode; else tail->next = newNode; tail = newNode; } LinkedRead.c의 일부

5 예제 LinkedRead.c의 분석: 삽입 2회전
while(1) { printf("자연수 입력: "); scanf("%d", &readData); if(readData < 1) break; // 노드의 추가과정 newNode = (Node*)malloc(sizeof(Node)); newNode->data = readData; newNode->next = NULL; if(head == NULL) head = newNode; else tail->next = newNode; tail = newNode; } 다수의 노드를 저장한 결과 LinkedRead.c의 일부

6 예제 LinkedRead.c의 분석: 데이터 조회
전체 데이터의 출력 과정 if(head == NULL) { printf("저장된 자연수가 존재하지 않습니다. \n"); } else cur = head; printf("%d ", cur->data); while(cur->next != NULL) cur = cur->next; LinkedRead.c의 일부

7 예제 LinkedRead.c의 분석: 데이터 삭제
전체 노드의 삭제 과정 if(head == NULL) { return 0; } else Node * delNode = head; Node * delNextNode = head->next; printf("%d을 삭제\n", head->data); free(delNode); while(delNextNode != NULL) delNode = delNextNode; delNextNode = delNextNode->next; printf("%d을 삭제\n", delNode->data); LinkedRead.c의 일부

8 Chapter 04. 연결 리스트(Linked List) 2
단순 연결 리스트의 ADT와 구현

9 정렬 기능 추가된 연결 리스트의 ADT1 이전과 동일 이전과 동일 이전과 동일 이전과 동일

10 정렬 기능 추가된 연결 리스트의 ADT2 이전과 동일 이전과 동일 새로 추가된 함수
SetSortRule 함수는 정렬의 기준을 설정하기 위해 정의된 함수! 이 함수의 선언 및 정의를 이해하기 위해서는 ‘함수 포인터’의 대한 이해가 필요하다.

11 새 노드의 추가 위치에 따른 장점과 단점 새 노드를 연결 리스트의 머리에 추가하는 경우 ∙ 장점 포인터 변수 tail이 불필요하다. ∙ 단점 저장된 순서를 유지하지 않는다. 새 노드를 연결 리스트의 꼬리에 추가하는 경우 ∙ 장점 저장된 순서가 유지된다. ∙ 단점 포인터 변수 tail이 필요하다. 두 가지 다 가능한 방법이다. 다만 tail의 관리를 생략하기 위해서 머리에 추가하는 것을 원칙으로 하자!

12 SetSortRule 함수 선언에 대한 이해
void SetSortRule ( List * plist, int (*comp)(LData d1, LData d2) ); √ 반환형이 int이고, int (*comp)(LData d1, LData d2) √ LData형 인자를 두 개 전달받는, int (*comp)(LData d1, LData d2) √ 함수의 주소 값을 전달해라! int (*comp)(LData d1, LData d2) int WhoIsPrecede(LData d1, LData d2) // typedef int LData; { if(d1 < d2) return 0; // d1이 정렬 순서상 앞선다. else return 1; // d2가 정렬 순서상 앞서거나 같다. } 인자로 전달이 가능한 함수의 예

13 정렬의 기준을 결정하는 함수에 대한 약속! 약속에 근거한 함수 정의의 예 Cr에 저장된 값이 0이라면
이렇듯 결정된 약속을 근거로 함수가 정의되어야 하며, 연결 리스트 또한 이를 근거로 구현되어야 한다. int WhoIsPrecede(LData d1, LData d2) { if(d1 < d2) return 0; // d1이 정렬 순서상 앞선다. else return 1; // d2가 정렬 순서상 앞서거나 같다. } 약속에 근거한 함수 정의의 예 int cr = WhoIsPrecede(D1, D2); Cr에 저장된 값이 0이라면 head D1 . . D tail D1이 head에 더 가깝다. Cr에 저장된 값이 1이라면 head D2 . . D tail D2가 head에 더 가깝다.

14 우리가 구현할 더미 노드 기반 연결 리스트 첫 번째 노드와 두 번째 이후의 노드 추가 및 삭제 방식이 다를 수 있다.
머리에 새 노드를 추가하되 더미 노드 없는 경우 첫 번째 노드와 두 번째 이후의 노드 추가 및 삭제 방식이 다를 수 있다. 머리에 새 노드를 추가하되 더미 노드 있는 경우 노드의 추가 및 삭제 방식이 항상 일정하다. LinkedRead.c와 문제 04-2의 답안인 DLinkedRead.c를 비교해보자!

15 정렬 기능 추가된 연결 리스트의 구조체 연결 리스트에 필요한 변수들을 구조체로 묶지 않는 것은 옳지 못하다.
노드의 구조체 표현 연결 리스트에 필요한 변수들을 구조체로 묶지 않는 것은 옳지 못하다. 연결 리스트의 구조체 표현

16 정렬 기능 추가된 연결 리스트 헤더파일 뒷부분 앞부분 #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)); 앞부분

17 더미 노드 연결 리스트 구현: 초기화 초기화 함수의 정의를 위해서 살펴봐야 하는 구조체의 정의 초기화 함수의 정의

18 더미 노드 연결 리스트 구현: 삽입1

19 더미 노드 연결 리스트 구현: 삽입2 모든 경우에 있어서 동일한 삽입과정을 거친다는 것이 더미 노드 기반 연결 리스트의 장점!

20 더미 노드 연결 리스트 구현: 참조1

21 더미 노드 연결 리스트 구현: 참조2

22 더미 노드 연결 리스트 구현: 삭제1 삭제 전 삭제 후 cur은 삭제 후 제조정의 과정을 거쳐야 하지만 before는 LFirst or LNext 호출 시 재설정되므로 재조정의 과정이 불필요하다.

23 더미 노드 연결 리스트 구현: 삭제2

24 Dlinkedlist.c DLinkedlist.h DLinkedlistmain.c 더미 기반 단순 연결 리스트 한데 묶기
실행결과 Dlinkedlist.c DLinkedlist.h DLinkedlistmain.c Chapter 03의 ListMain.c의 main 함수와 완전히 동일하다. 다만 노드를 머리에 추가하는 방식이기 때문에 실행결과에서는 차이가 난다.

25 Chapter 04. 연결 리스트(Linked List) 2
연결 리스트의 정렬 삽입의 구현

26 정렬기준 설정과 관련된 부분 단순 연결 리스트의 정렬 관련 요소 세 가지 하나의 문장으로 구성한 결과
∙ 정렬기준이 되는 함수를 등록하는 SetSortRule 함수 ∙ SetSortRule 함수 통해 전달된 함수정보 저장을 위한 LinkedList의 멤버 comp ∙ comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수 하나의 문장으로 구성한 결과 “SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.”

27 SetSortRule 함수와 멤버 comp
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2)) { plist->comp = comp; } typedef struct _linkedList { Node * head; Node * cur; Node * before; int numOfData; int (*comp)(LData d1, LData d2); } LinkedList; 2. 멤버 comp가 초기화되면 void LInsert(List * plist, LData data) { if(plist->comp == NULL) FInsert(plist, data); else SInsert(plist, data); } 3. 정렬 관련 SInsert 함수가 호출된다.

28 SInsert 함수1 위 상황에서 다음 문장이 실행되었다고 가정! SInsert(&slist, 5);
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)++; 위 상황에서 다음 문장이 실행되었다고 가정! SInsert(&slist, 5);

29 SInsert 함수2 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)++; comp가 0을 반환한다는 것은 첫 번째 인자인 data가 정렬 순서상 앞서기 때문에 head에 가까워야 한다는 의미!

30 SInsert 함수3 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)++;

31 정렬의 핵심인 while 반복문 ∙ 반복의 조건 1 pred->next != NULL
∙ 반복의 조건 2 plist->comp(data, pred->next->data) != 0 새 데이터와 pred의 다음 노드에 저장된 데이터의 우선순위 비교를 위한 함수호출 while(pred->next != NULL && plist->comp(data, pred->next->data) != 0) { pred = pred->next; // 다음 노드로 이동 }

32 comp의 반환 값과 그 의미 우리의 결정 내용! 이 내용을 근거로 SInsert 함수를 정의하였다. ∙ comp가 0을 반환
while(pred->next != NULL && plist->comp(data, pred->next->data) != 0) { pred = pred->next; // 다음 노드로 이동 } 우리의 결정 내용! 이 내용을 근거로 SInsert 함수를 정의하였다. ∙ comp가 0을 반환 첫 번째 인자인 data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우 ∙ comp가 1을 반환 두 번째 인자인 pred->next->data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우

33 정렬의 기준을 설정하기 위한 함수의 정의 Dlinkedlist.c DLinkedlist.h
∙ 두 개의 인자를 전달받도록 함수를 정의한다. ∙ 첫 번째 인자의 정렬 우선순위가 높으면 0을, 그렇지 않으면 1을 반환한다. 함수의 정의 기준 int WhoIsPrecede(int d1, int d2) { if(d1 < d2) return 0; // d1이 정렬 순서상 앞선다. else return 1; // d2가 정렬 순서상 앞서거나 같다. } 오름차순 정렬을 위한 함수의 정의 정렬 관련된 함수를 DLinkedListSortMain.c에 포함시켜야 함을 이해한다. Dlinkedlist.c DLinkedlist.h DLinkedlistSortmain.c 실행결과