Chapter 9 – 구조형과 리스트 처리 Outline 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산 9.4 스택 연산 9.5 2진 트리 9.6 배열과 리스트 9.7 요약 9.8 예제

9.1 자신 참조 구조형 (예 9.1) 자신 참조 구조형의 예 struct elt는 2개의 멤버를 갖는다. 9.1 자신 참조 구조형 (예 9.1) 자신 참조 구조형의 예 struct elt는 2개의 멤버를 갖는다. 멤버 next는 struct elt 포인터형이다. 즉 통상 다른 struct elt형의 자료의 포인터이다. (예 9.1) struct elt /* (1) 정의 */ struct elt { float data; struct elt *next; }; /* (2) 기억 형태 */

9.1 자신 참조 구조형 (예 9.2) 리스트의 배정과 연결 (1) 3개의 struct elt형 변수에 멤버 data의 값을 배정한다. (예 9.2) 리스트의 배정과 연결 #define NULL 0 struct elt a, b, c; /* (1) */ a.data = 1.0; b.data = 2.0; c.data = 3.0; a.next = b.next = c.next = NULL; a b c 1.0 NULL 2.0 3.0

9.1 자신 참조 구조형 (예 9.2 계속) 리스트의 배정과 연결 (2) 구조체를 연결한다. 9.1 자신 참조 구조형 (예 9.2 계속) 리스트의 배정과 연결 (2) 구조체를 연결한다. a의 멤버 next의 값으로 b의 포인터를 저장 b의 멤버 next의 값으로 c의 포인터를 저장 (예 9.2 계속) 리스트의 배정과 연결 /* (2) */ a.next = &b; b.next = &c; a b c 1.0 2.0 3.0 NULL 연결 후 a.next -> data는 2.0이고, a.next -> next -> data는 3.0이다.

9.2 선형 연결 리스트 (예 9.3) 선형 연결 리스트(linear linked list) 헤더 file(list.h) 9.2 선형 연결 리스트 (예 9.3) 선형 연결 리스트(linear linked list) 헤더 file(list.h) (예 9.3) list.h 1 /* File : list.c 2 선형 연결 리스트 헤더 file */ 3 #ifndef LIST_H 4 #define LIST_H 5 6 #define NULL 0 7 typedef int BOOL; /* 이제부터 BOOL은 int와 같다. */ 8 struct elt { 9 float data; 10 struct elt *next; 11 }; 12 typedef struct elt NODE; 13 14 #endif 줄 6부터 12까지가 정의하려는 내용이다. 줄 3, 4, 14 안에 정의하려는 내용을 넣어두면, 분리컴파일 시 이중으로 포함되는 것을 방지할 수 있다. 줄 6의 NULL 선언은 만약 <stdio.h>를 포함시키고 그 안에 이미 NULL이 정의되어 있다면 생략한다. 줄 7: 참(1)과 거짓(0)을 사용하기 위한 자료형 BOOL을 int로 정의하였다.

9.2 선형 연결 리스트 (예 9.4) 선형 연결 리스트 생성 3 개의 실수 5.0, 6.0, 7.0을 동적으로 저장 9.2 선형 연결 리스트 (예 9.4) 선형 연결 리스트 생성 3 개의 실수 5.0, 6.0, 7.0을 동적으로 저장 malloc은 인수로 넘어온 바이트 수 크기의 메모리를 할당하고, 그 주소를 반환하며, 그 앞의 (NODE *)는 그 주소를 NODE 포인터로 casting한다. (예 9.4) 리스트 생성 NODE *head = NULL; /* 전역변수로 리스트 맨 앞을 가리킴 */ /* (1) */ head = (NODE *) malloc(sizeof(NODE)); head.data = 5.0; head.next = NULL; /* (2) */ head -> next = (NODE *) malloc(sizeof(NODE)); head -> next -> data = 6.0; head -> next -> next = NULL; /* (3) */ head -> next -> next = (NODE *) malloc(sizeof(NODE)); head -> next -> next -> data = 7.0; head -> next -> next -> next = NULL;

9.2 선형 연결 리스트 (예 9.4 계속) 선형 연결 리스트 생성 (예 9.4) 리스트 생성 9.2 선형 연결 리스트 (예 9.4 계속) 선형 연결 리스트 생성 (1) 동적으로 하나의 리스트를 생성 head 5.0 NULL (2) 6.0 (3) 7.0 (예 9.4) 리스트 생성 그림 9.1 세 노드의 선형 연결 리스트

9.3 리스트 연산 선형 리스트의 연산 리스트의 프린트 리스트 맨 앞에 노드 삽입 리스트 맨 앞의 노드 제거 9.3 리스트 연산 선형 리스트의 연산 리스트의 프린트 리스트 맨 앞에 노드 삽입 리스트 맨 앞의 노드 제거 리스트 맨 뒤에 노드 삽입 리스트에서 특정 노드 제거 정렬된 리스트에 노드 삽입 리스트에서 특정 노드 찾기 리스트에 들어있는 노드 수 알아내기 2 개의 리스트 연결

9.3 리스트 연산 (예 9.5) 리스트의 내용 출력 리스트 함수들은 list.c에 구현되어 있다고 가정함 (예 9.5) 9.3 리스트 연산 (예 9.5) 리스트의 내용 출력 리스트 함수들은 list.c에 구현되어 있다고 가정함 1 /* File : list.c 2 일반적인 리스트 함수들의 모음 */ 3 #include “list.h” 4 extern NODE *head; 5 /* (예 9.5) 리스트의 내용 출력 */ 6 void print_list(NODE *p) { 7 while (p != NULL) { 8 printf(“%.1f”, p->data); 9 if (p->next != NULL) printf(“-->”); 10 p = p->next; 11 } 12 printf(“\n”); 13 } 14 (예 9.5) print_list (list.c에서) [해 설] output p가 가리키는 노드가 널이 아니면 멤버 data를 출력하고, p를 다음 노드를 가리키는 포인터로 바꾼다. p가 널이 아닌 동안 이를 반복한다. 줄 4는 main 프로그램이 들어있는 원시 file에서 정의될 변수 head를 가리킴 [그림 9.1](3)과 같은 리스트의 경우 print_list(head)는 다음을 출력함 5.0-->6.0-->7.0

9.3 리스트 연산 (예 9.6) 리스트의 맨 앞에서 삽입, 삭제 리스트의 맨 앞은 head가 가리킨다고 가정 (예 9.6) 9.3 리스트 연산 (예 9.6) 리스트의 맨 앞에서 삽입, 삭제 리스트의 맨 앞은 head가 가리킨다고 가정 (예 9.6) add_front (list.c에서) [해 설] 15 /* (예 9.6) 리스트 맨 앞에서 삽입, 삭제 */ 16 void add_front(float d) { 17 NODE *p; 18 p = (NODE *) malloc(sizeof(NODE)); 19 p->data = d; 20 p->next = head; 21 head = p; 22 } 줄 18: NODE크기의 메모리를 잡고 그 주소를 NODE 포인터로 바꾸어 p에 저장 줄 19: 인수로 넘어온 d를 멤버 data값으로 저장 줄 20: p가 가리키는 노드의 멤버 next에 리스트head를 저장 줄 21: head를 새로 앞에 넣은 노드를 가리키게 한다.

9.3 리스트 연산 (예 9.6 계속) 리스트의 맨 앞에서 삽입, 삭제 (예 9.6 계속) del_front 9.3 리스트 연산 (예 9.6 계속) 리스트의 맨 앞에서 삽입, 삭제 23 BOOL del_front(float *fp) { /* 성공시 1을 반환 */ 24 NODE *p; 25 if (head == NULL) return 0; /* 삭제 연산 실패 */ 26 *fp = head->data; /* 맨 앞 자료를 저장 */ 27 p = head; 28 head = head->next; 29 free(p); /* 맨 앞 노드가 차지하는 메모리 반납 */ 30 return 1; 31 } 32 (예 9.6 계속) del_front (list.c에서) [해 설] 줄 23: del_front는 빈 리스트면 거짓(0)을, 아니면 참(1)을 반환하는 함수 줄 25: 빈 리스트면 0을 반환한다. 줄 26: 맨 앞 노드의 data를 인수(fp)가 가리키는 곳에 저장 줄 28: head를 둘 째 노드의 포인터로 배정함. 줄 27,29: 맨 앞 노드를 p가 가리키게 하고, 그 노드의 메모리 반납 줄 30: 노드 삭제가 성공했음을 알림

9.3 리스트 연산 (예 9.7) 리스트 맨 뒤에 노드 삽입 리스트의 맨 앞은 head가 가리킨다고 가정 (예 9.7) 9.3 리스트 연산 (예 9.7) 리스트 맨 뒤에 노드 삽입 리스트의 맨 앞은 head가 가리킨다고 가정 33 /* (예 9.7) 리스트 맨 뒤에 노드 삽입 */ 34 void add_rear(float d) { 35 NODE *p; NODE *p1; 36 p = (NODE *) malloc(sizeof(NODE)); 37 p->data = d; 38 p->next = NULL; 39 40 if (head == NULL) /* 현재 빈 리스트의 경우 */ 41 head = p; 42 else { 43 p1 = head; 44 while (p1->next != NULL) /* p1이 마지막 노드를 가리키도록 하자. */ 45 p1 = p1->next; 46 p1->next = p; 47 } 48 } 49 (예 9.7) add_rear (list.c에서) [해 설] 줄 36-38 : p가 가리키는 새 노드를 만들고 자료 저장 줄 40-41 : 현재 빈 리스트면 head가 p가 가리키는 새 노드를 가리키게 함 줄 43-45 : 리스트의 끝 노드(멤버 next가 NULL인 노드)를 p1이 가리키게 함 줄 46 : p1이 가리키는 노드 뒤에 (p가 가리키는) 새로 만든 노드 추가.

9.3 리스트 연산 (예 9.8) 리스트에서 특정 노드 제거 리스트의 맨 앞은 head가 가리킨다고 가정 (예 9.8) del 9.3 리스트 연산 (예 9.8) 리스트에서 특정 노드 제거 리스트의 맨 앞은 head가 가리킨다고 가정 50 /* (예 9.8) 리스트에서 특정 노드 제거 */ 51 BOOL del(float d) { /* 성공시 1, 실패시 0을 반환 */ 52 NODE *p1, *p2; 53 if (head == NULL) /* 빈 리스트의 경우, 실패 */ 54 return 0; 55 p1 = head; p2 = p1->next; /* 앞으로 p2는 p1 바로 다음 노드 가리킴 */ 56 if (p1->data == d) { /* 맨 앞 노드가 바로 그 노드 */ 57 head = p2; 58 free(p1); /* (히프 영역으로) p1이 가리키는 노드의 메모리 반납 */ 59 return 1; 60 } 61 while (p2 != NULL) { 62 if (p2->data == d) { /* p2가 가리키는 노드가 바로 그 노드 */ 63 p1->next = p2->next; 64 free(p2); 65 return 1; 66 } 67 p1 = p2; /* 다음 노드를 테스트하기 위해 준비 */ 68 p2 = p1->next; 69 } 70 return 0; 71 } 72 (예 9.8) del (list.c에서)

9.3 리스트 연산 (예 9.8 계속) 리스트에서 특정 노드 제거 (예 9.8) del (list.c에서) [해 설] 9.3 리스트 연산 (예 9.8 계속) 리스트에서 특정 노드 제거 줄 53,54: 빈 리스트면 실패이므로 거짓(0)을 반환 줄 55: 앞으로 p1이 가리키는 노드의 다음 노드를 p2가 가리킴 줄 56-60: 맨 앞 노드가 삭제하려는 노드인 경우이다. head가 둘째 노드 가리키게 바꾸고, (p1이 가리키는) 맨 앞의 노드는 메모리 반납 함수의 반환값으로 참(1)을 반환한다. 줄 62-66: p2가 가리키는 노드가 삭제하려는 바로 그 노드인 경우이다. p2가 가리키는 노드를 p1이 가리키게 하고, p2가 가리키는 노드의 메모리 반납, 함수의 반환 값으로 참(1)을 반환한다. 줄 67-68: p2가 원하는 노드를 가리키지 않음을 확인한 직후이며, p1, p2를 다음으로 이동 줄 70: 리스트의 끝(p2가 NULL)이므로 거짓(0)을 반환. (예 9.8) del (list.c에서) [해 설]

9.3 리스트 연산 (예 9.8 계속) 리스트에서 특정 노드 제거 9.3 리스트 연산 (예 9.8 계속) 리스트에서 특정 노드 제거 del(6.0)을 호출하면 p1과 p2를 이동하다가 결국은 다음 그림(1)과 같이 p2가 해당 노드를 가리키게 된다. 줄 62에서 참이 되면 줄 63을 수행하게 되는데, 다음 그림 (2)는 줄 63 수행 직 후의 모습이다. (예 9.8 계속) del 삭제 장면

9.3 리스트 연산 (예 9.9) 정렬된 리스트에 노드 삽입 리스트의 맨 앞은 head가 가리킨다고 가정 (예 9.9) add 9.3 리스트 연산 (예 9.9) 정렬된 리스트에 노드 삽입 리스트의 맨 앞은 head가 가리킨다고 가정 73 /* (예 9.9) 정렬된 리스트에 노드 삽입 */ 74 void add(float d) { 75 NODE *p; NODE *p1, *p2; 76 p = (NODE *) malloc(sizeof(NODE)); 77 p->data = d; 78 p->next = NULL; 79 80 if (head == NULL) /* 현재 빈 리스트의 경우 */ 81 head = p; 82 else if (p <= head->data) { 83 p->next = head; 84 head = p; 85 } else { 86 p1 = head; p2 = head->next; /* p2는 p1 바로 다음 노드 가리킴 */ 87 while (p2 != NULL) { 88 if (d <= p2->data) 89 break; /* p1 바로 다음에 넣어야 함을 확인하였음 */ 90 p1 = p2; p2 = p1->next; 91 } 92 /* p1, p2 사이에 넣자. 단 p2가 NULL일 수도 있음 */ 93 p1->next = p; 94 p->next = p2; 95 } 96 } (예 9.9) add (list.c에서)

9.3 리스트 연산 (예 9.9 계속) 정렬된 리스트에 노드 삽입 (예 9.9 계속) add (list.c에서) [해 설] 9.3 리스트 연산 (예 9.9 계속) 정렬된 리스트에 노드 삽입 줄 76-78: 삽입할 새로운 노드를 생성하고 자료를 저장 줄 80-81: 빈 리스트인 경우 새로 만든 노드 1 개로 이루어진 리스트가 됨 줄 82-84: 맨 앞에 삽입하는 경우 줄 85-95: 맨 앞이 아닌 경우로 삽입 위치를 p1, p2로 찾는다. 자료 d보다 큰 첫번째 노드를 p2가 가리키게 하려한다. P2노드 바로 전의 노드를 p1이 가리킨다. 줄 88에서 위치가 확인되면 줄89에서 while문을 빠져나온다. 줄 93,94: p1, p2가 가리키는 노드 사이에 p가 가리키는 노드를 삽입한다. (예 9.9 계속) add (list.c에서) [해 설]

9.3 리스트 연산 (예 9.10) 정렬된 리스트에 노드 삽입 (예 9.10) find_list (list.c에서) 9.3 리스트 연산 (예 9.10) 정렬된 리스트에 노드 삽입 97 98 /* (예 9.10) 리스트에서 특정 노드 찾기 */ 99 /* 리스트 p에서 값 d를 갖는 노드의 위치를 반환 */ 100 NODE *find_list(NODE *p, float d) { 101 while (p != NULL) { 102 if (p->data == d) return p; 103 else p = p->next; 104 return NULL; /* 못 찾았음 */ 105 } 106 (예 9.10) find_list (list.c에서) 줄 100: 리스트 p에서 값 d를 갖는 노드의 위치를 반환하는 함수 줄 101: p가 널이 아닌 동안 102와 103을 수행함 줄 102: p 가 가리키는 노드가 바로 자료 d를 가진 노드이면 p를 반환 줄 103: 아니면, 다음 노드로 간다. 줄 104: p가 NULL인 채로(즉 해당 노드를 못 찾고) while 문을 나온 경우 NULL을 반환

9.3 리스트 연산 (예 9.11) 리스트의 노드 수 알아내기 (예 9.11) count_list (list.c에서) 9.3 리스트 연산 (예 9.11) 리스트의 노드 수 알아내기 107 /* (예 9.11) 리스트의 노드 수 알아내기 */ 108 /* 리스트 p에 있는 노드의 수를 반환 */ 109 int count_list(NODE *p) { 110 int len; 111 for (len = 0; p != NULL; p = p->next) 112 len++; 113 return len; 114 } (예 9.11) count_list (list.c에서) 줄 111,112: len을 0으로 초기화하고, p가 널이 아닌 동안 len을 증가시키고, p가 다음 노드를 가리키게 한다. 줄 113: p가 NULL을 가리키므로 for문장을 빠져 나왔다. 이제 len을 반환

9.3 리스트 연산 (예 9.12) list.c의 함수 들을 테스트 (prog9-12.c) 9.3 리스트 연산 1 /* File : prog9-12.c 2 list.c의 함수들을 테스트; 다음 같이 사용 3 cc –o prog9-12 list.c prog9-12.c 4 prog9-12 5 */ 6 #include “list.h” 7 void print_list(NODE*), add_front(float), add_rear(float), add(float); 8 BOOL del_front(float), del(float); 9 NODE *find_list(NODE*, float); 10 int count_list(NODE*); 11 NODE *head = NULL; /* 전역변수로 리스트의 맨 앞을 가리킴 */ 12 int main(void) { 13 float f; /* 삭제된 노드의 값 저장 용 */ 14 NODE *p; /* 검색된 노드 포인터 저장 용 */ 15 add_front(1.0); add_front(2.0); add_front(3.0); /* (1) */ 16 print_list(head); /* (2) */ 17 del_front(&f); del_front(&f); del_front(&f); /* (3) */ 18 /* 현재 리스트 head는 비어 있다. 이제 정렬된 리스트를 만들자. */ 19 add(3.0); add(7.0); add(4.0); add(2.0); add(9.0); /* (4) */ 20 print_list(head); /* (5) */ 21 printf(“#nodes = %d\n”, count_list(head)); /* (6) */ 22 del(4.0); del(9.0); print_list(head); /* (7) */ 23 add_rear(4.5); print_list(head); /* (8) */ 24 p = find_list(head, 3.0); /* (9) */ 25 printf(“Node with %.1f Found\n”, p->data); /* (10) */ 26 } (예 9.12) list.c의 함수 들을 테스트 (prog9-12.c)

9.3 리스트 연산 (예 9.12 계속) 리스트 함수들의 테스트 (예 9.12) [해 설] output 9.3 리스트 연산 (예 9.12 계속) 리스트 함수들의 테스트 줄 7-10: 분리 컴파일로 다른 file에서 링크시킬 함수들의 프로토타입 [주의] 다른 file의 함수의 경우 반환형과 모든 인수형을 명시하여야 함 줄 11: 사용할 리스트의 헤드 선언(NULL로 초기화) (1)(2)(3): 빈 리스트 앞에 1.0, 2.0, 3.0을 순서대로 넣고 출력한 후, 리스트를 비운다. (4)(5)(6): 임의 순으로 들어 온 5개의 수를 정렬하여 리스트에 넣고 출력한 후, 리스트 내의 노드 수를 출력한다. (7): 리스트 내의 특정 노드 2개를 지우고 출력한다. (8): 리스트 맨 뒤에 값 4.5를 갖는 노드를 추가하고, 출력한다. (9)(10): 값이 3.0인 노드를 찾아 그 노드의 값을 출력하여 확인한다. (예 9.12) [해 설] output $ cc –o prog9-12 list.c prog9-12.c $ prog9-12 3.0-->2.0-->1.0 2.0-->3.0-->4.0-->7.0-->9.0 #nodes = 5 2.0-->3.0-->7.0 2.0-->3.0-->7.0-->4.5 Node with 3.0 Found

9.3 리스트 연산 (예 9.13) 임의의 리스트 맨 앞에서 삽입, 삭제 9.3 리스트 연산 (예 9.13) 임의의 리스트 맨 앞에서 삽입, 삭제 지금까지는 전역변수 head가 가리키는 리스트를 가정하였다. 즉 head는 전역 리스트의 첫 노드의 포인터이다. 임의의 리스트를 사용하게 프로그램을 바꾸는 방법. 사용할 리스트의 첫 노드의 포인터의 포인터를 함수의 첫 인수(phead라 하자)로 추가한다. 기존의 head 대신에 *phead를 사용한다. [참고] 연산자 *의 우선순위를 고려하여 필요시 (*phead)로 사용 여기서는 add_front와 del_front를 임의의 리스트를 처리하는 add_front_list와 del_front_list로 바꾸는 예를 보여 준다. 기타 add_rear나 add, del등도 동일한 방식으로 add_rear_list, add_list, del_list란 이름의 임의의 리스트 처리 함수로 바꿀 수 있다.

9.3 리스트 연산 (예 9.13) 임의의 리스트 맨 앞에서 삽입 9.3 리스트 연산 (예 9.13) 임의의 리스트 맨 앞에서 삽입 리스트 head를 사용하는 add_front를 임의의 리스트를 사용하는 add_front_list로 바꾸기 (예 9.13) add_front (list.c) 에서 add_front_list (list2.c) 로 변환 /* (예 9.6) 리스트 head 맨 앞에서 삽입 */ void add_front(float d) { NODE *p; p = (NODE *) malloc(sizeof(NODE)); p->data = d; p->next = head; head = p; } /* (예 9.13) 임의의 리스트 맨 앞에서 삽입 */ void add_front_list(NODE **head, float d) { NODE *p; p = (NODE *) malloc(sizeof(NODE)); p->data = d; p->next = *phead; *phead = p; }

9.3 리스트 연산 (예 9.13 계속) 임의의 리스트 맨 앞에서 삭제 9.3 리스트 연산 (예 9.13 계속) 임의의 리스트 맨 앞에서 삭제 리스트 head를 사용하는 del_front를 임의의 리스트를 사용하는 del_front_list로 바꾸기 (예 9.13 계속) del_front (list.c) 에서 del_front_list (list2.c) 로 변환 /* (예 9.6) 리스트 head 맨 앞에서 삭제 */ BOOL del_front(float *fp) { /* 성공시 1을 반환 */ NODE *p; if (head == NULL) return 0; /* 삭제 연산 실패 */ *fp = head->data; /* 맨 앞 자료를 저장 */ p = head; head = head->next; free(p); /* 맨 앞 노드가 차지하는 메모리 반납 */ return 1; } /* (예 9.13) 임의의 리스트 맨 앞에서 삭제 */ BOOL del_front_list(NODE **phead, float *fp) { /* 성공시 1을 반환 */ NODE *p; if (*phead == NULL) return 0; /* 삭제 연산 실패 */ *fp = (*phead)->data; /* 맨 앞 자료를 저장 */ p = *phead; *phead = (*phead)->next; free(p); /* 맨 앞 노드가 차지하는 메모리 반납 */ return 1; }

9.3 리스트 연산 (예 9.14) 2개의 리스트 연결 리스트 l1 뒤에 리스트 l2를 연결하여 반환함 9.3 리스트 연산 (예 9.14) 2개의 리스트 연결 리스트 l1 뒤에 리스트 l2를 연결하여 반환함 여기서는 앞 리스트를 복사하지 않고 그 뒤에 두 번째 리스트를 연결하였다. for 문장으로 l1의 마지막 노드를 찾아낸다. 멤버 next 가 NULL 인 노드가 마지막 노드임 (예 9.14) append_lists (list2.c) /* (예 9.14) 2 개의 리스트 연결 */ /* 리스트 l1 뒤에 리스트 l2를 연결하여 반환 */ NODE *append_lists(NODE *l1, NODE *l2) { NODE *p; if (l1 == NULL) return l2; /* l1이 빈 리스트면 l2를 반환한다. */ for (p = l1; p->next != NULL; p = p->next); /* for 몸체가 비었음 */ p->next = l2; /* l1의 마지막 노드 뒤에 l2를 연결한다. */ return l1; }

9.3 리스트 연산 (예 9.15) 두 개 이상의 리스트 처리하는 함수들의 테스트 9.3 리스트 연산 (예 9.15) 두 개 이상의 리스트 처리하는 함수들의 테스트 임의의 리스트를 처리하는 함수들을 list2.c에 저장하였다. 줄 6 : 헤더 file을 포함시킴 줄 7,8 : 다른 file(list2.c)에서 정의된 함수의 프로토타입 (예 9.15) list2.c의 함수들 테스트 1 /* File : prog9-15.c 2 list2.c의 함수들을 테스트; 다음 같이 사용 3 cc –o prog9-15 list2.c prog9-15.c 4 prog9-15 5 */ 6 #include “list.h” 7 void print_list(NODE*), add_front_list(NODE**, float); 8 NODE *append_lists(NODE*, NODE*); 9

9.3 리스트 연산 (예 9.15 계속) 두 개 이상의 리스트 처리하는 함수들의 테스트 줄 12: 두 리스트의 초기화 9.3 리스트 연산 (예 9.15 계속) 두 개 이상의 리스트 처리하는 함수들의 테스트 줄 12: 두 리스트의 초기화 줄 13,14: 리스트 lst1에 두 수를 앞에 한 개씩 넣고 출력 줄 15,16: 리스트 lst2에 두 수를 앞에 한 개씩 넣고 출력 줄 17: 두 리스트를 연결하고 출력 10 int main(void) { /* 삭제된 노드의 값 저장 용 */ 11 float f; 12 NODE *lst1 = NULL, *lst2 = NULL; /* 2개의 리스트 헤드 */ 13 add_front_list(&lst1, 1.0); add_front_list(&lst1, 2.0); 14 print_list(lst1); 15 add_front_list(&lst2, 3.0); add_front_list(&lst2, 4.0); 16 print_list(lst2); 17 lst1 = append_lists(lst1, lst2); print_list(lst1); 18 } (예 9.15 계속) list2.c의 함수들 테스트 output $ cc –o prog9-15 list2.c prog9-15.c $ prog9-15 2.0-->1.0 4.0-->3.0 2.0-->1.0-->4.0-->3.0

9.4 스택과 큐 (예 9.16)(1) 스택 연산. 스택은 리스트의 머리(top이라 함)쪽에서만 삽입 삭제 가능 9.4 스택과 큐 (예 9.16)(1) 스택 연산. 스택은 리스트의 머리(top이라 함)쪽에서만 삽입 삭제 가능 함 수 명 행 동   isempty(top)    vtop(top)    pop(&top, &d)    push(&top, d) 스택이 비어 있으면 1을 반환, 그렇지 않으면 0을 반환 top 노드의 값을 반환 top 노드를 삭제하고, d에 삭제된 노드의 값을 저장 스택의 top에 값 d를 갖는 노드를 삽입 (예 9.16)(1) 스택 함수들 prog9-16a.c 1 /* File : prog9-16a.c 2 stack 3 list2.c의 함수를 이용; 다음같이 컴파일 4 cc –o prog9-16a list2.c prog9-16a.c 5 prog9-16a 6 */ 7 #include “list.h” 8 void add_front_list(NODE**, float); 9 BOOL del_front_list(NODE**, float*); 10

9.4 스택과 큐 (예 9.16a 계속) 스택 연산 스택은 후입선출(last-in first-out; LIFO)로 동작 9.4 스택과 큐 (예 9.16a 계속) 스택 연산 스택은 후입선출(last-in first-out; LIFO)로 동작 (예 9.16a 계속) 스택 함수들 11 #define push add_front_list 12 #define pop del_front_list 13 BOOL isempty(NODE *top) { /* 빈 스택이면 참을 return */ 14 return (top == NULL); 15 } 16 float vtop(NODE *top) { 17 return top->data; 18 } 19 NODE *top = NULL; /* stack top */ 20 int main(void) { 21 float f; /* 삭제된 노드의 값 저장 용 */ 22 push(&top, 1.0); push(&top, 2.0); push(&top, 7.0); push(&top, 5.0); 23 while (!isempty(top)) { 24 pop(&top, &f); printf(“%.1f popped\n”, f); 25 } 26 }

9.4 스택과 큐 (예 9.16a 계속) 스택 연산 줄 8,9: 다른 file(list2.c)의 함수들의 프로토타입 9.4 스택과 큐 (예 9.16a 계속) 스택 연산 줄 8,9: 다른 file(list2.c)의 함수들의 프로토타입 줄 11,12: 스택 앞에서 넣고 빼는 함수 push, pop은 add_front_list와 del_front_list와 동일함 줄 13-15: 함수 isempty는 빈 스택인지 확인하는 함수 줄 16-18: 함수 vtop은 pop없이 top의 성분을 확인함 줄 19: 스택의 top을 전역변수로 선언함 main 프로그램에서는 4개의 수를 push한 후 pop하여 동작을 확인함. (예 9.16a 계속) output $ cc –o prog9-16a list2.c prog9-16a.c $ prog9-16a 5.0 popped 7.0 popped 2.0 popped 1.0 popped

9.4 스택과 큐 (예 9.16)(2) 큐 연산. 큐는 리스트의 뒤로 삽입되고, 앞에서 삭제된다. (예 9.16)(1) 9.4 스택과 큐 (예 9.16)(2) 큐 연산. 큐는 리스트의 뒤로 삽입되고, 앞에서 삭제된다. 함 수 명 행 동 del_queue(&front, &d) add_queue(&front, d) front노드를 삭제하고, d에 삭제된 노드의 값을 저장 front큐의 맨 뒤에 값 d를 갖는 노드를 삽입 (예 9.16)(1) 큐 함수들 prog9-16b.c 1 /* File : prog9-16b.c 2 queue 3 list2.c의 함수를 이용; 다음같이 컴파일 4 cc –o prog9-16b list2.c prog9-16b.c 5 prog9-16b 6 */ 7 #include “list.h” 8 void add_rear_list(NODE**, float); 9 BOOL del_front_list(NODE**, float*); 10

9.4 스택과 큐 (예 9.16b 계속) 큐 연산 큐는 선입선출(first-in first-out; FIFO)로 동작 9.4 스택과 큐 (예 9.16b 계속) 큐 연산 큐는 선입선출(first-in first-out; FIFO)로 동작 (예 9.16b 계속) 큐 함수들 11 #define add_queue add_rear_list 12 #define del_queue del_front_list 13 NODE *front = NULL; /* queue top */ 14 int main(void) { 15 float f; /* 삭제된 노드의 값 저장 용 */ 16 add_queue(&top, 1.0); add_queue(&top, 2.0); 17 add_queue(&top, 7.0); add_queue(&top, 5.0); 18 while (del_queue(&front, &f)) 19 printf(“%.1f deleted from the queue\n”, f); 20 } 21 }

9.4 스택과 큐 (예 9.16b 계속) 큐 연산 줄 8,9 : 다른 file(list2.c)의 함수들의 프로토타입 줄 11,12 : 큐에서 넣고 빼는 함수는 add_rear_list와 del_front_list와 동일함 줄 13 : 큐의 front를 전역변수로 선언함 main 프로그램에서는 4개의 수를 큐에 넣은 후 빼서 동작을 확인함. [참 고]지금까지 리스트 처리 시 맨 앞의 노드를 가리키는 포인터 front만을 사용하였으나, 맨 뒤 노드를 가리키는 포인터 rear도 사용하게 하면 맨 뒤에 삽입하는 함수를 더 효과적으로 구현할 수 있다. (예 9.16b 계속) output $ cc –o prog9-16b list2.c prog9-16b.c $ prog9-16b 1.0 deleted from the queue 2.0 deleted from the queue 7.0 deleted from the queue 5.0 deleted from the queue

9.5 2진 트리 그림 9.5 2진 트리의 예 2진 트리는 2개 이하의 자손을 노드로 갖는 트리 다음 그림에서 9.5 2진 트리 2진 트리는 2개 이하의 자손을 노드로 갖는 트리 다음 그림에서 루트(root) 노드: 자료로 G를 갖는 노드 잎(leaf) 노드: 왼쪽 child와 오른쪽 child가 모두 NULL인 노드 (예) 자료값이 A, C, E, H, J인 노드들 문자열을 이 같은 트리로 바꾸어 저장하는 방법은 예제 9.4를 참조하시오. 그림 9.5 2진 트리의 예

9.5 2진 트리 (예 9.17) 2진 트리 헤더 file : tree.h 정의하려는 내용은 줄 6-14이다. 9.5 2진 트리 (예 9.17) 2진 트리 헤더 file : tree.h 정의하려는 내용은 줄 6-14이다. 줄 3, 4,16은 분리 컴파일 시 이 헤더 file을 단 한 번만 포함되게 하기 위한 방법이다. 줄 6은 가령<stdio.h>을 포함하고 그곳에 NULL이 이미 정의 되었다면 생략해야 함 (예 9.17) tree.h 1 /* File : tree.h 2 2진 트리 헤더 file */ 3 #ifndef TREE_H 4 #define TREE_H 5 6 #define NULL 0 7 typedef char DATA; 8 struct node { 9 DATA d; 10 struct node *left_child; 11 struct node *right_child; 12 }; 13 typedef struct node NODE; 14 typedef NODE *BTREE; 15 16 #endif

9.5 2진 트리 (예 9.18) 중위순 2진 트리 방문 좌측 부트리의 방문을 완료한후 자료값을 참조한다. 9.5 2진 트리 (예 9.18) 중위순 2진 트리 방문 좌측 부트리의 방문을 완료한후 자료값을 참조한다. 그 후 우측 부트리를 방문하는 방식이다. 줄 7, 줄 9는 좌측 child와 우측 child에 대한 재귀적 호출이다. 아래의 출력은 그림 9.5의 경우를 inorder로 방문한 결과이다. 1 /* File : tree.c */ 2 #include “tree.h” 3 /* (예 9.18) 중순위 2진 트리 방문 */ 4 void inorder(BTREE root) 5 { 6 if (root != NULL) { 7 inorder(root -> left_child); /* left 재귀 호출 */ 8 printf(“%c ”, root -> d); 9 inorder(root -> right_child); /* right 재귀 호출 10 } 11 } 12 (예 9.18) 함수inorder (tree.c에서) output A B C D E F G H I J

9.5 2진 트리 (예 9.19) 전위순 2진 트리 방문 자료값을 참조한 후, 좌측 부트리를 방문한다. 9.5 2진 트리 (예 9.19) 전위순 2진 트리 방문 자료값을 참조한 후, 좌측 부트리를 방문한다. 그 후 우측 부트리를 방문하는 방식이다. 줄 18, 줄 19는 좌측 child와 우측 child에 대한 재귀적 호출이다. 아래의 출력은 그림 9.5의 경우를 preorder로 방문한 결과이다. (예 9.19) 함수preorder (tree.c에서) output 13 /* (예 9.19) 전순위, 후순위 2진 트리 방문 */ 14 void preorder(BTREE root) 15 { 16 if (root != NULL) { 17 printf(“%c ”, root -> d); 18 preorder(root -> left_child); /* left 재귀 호출 */ 19 preorder(root -> right_child); /* right 재귀 호출 20 } 21 } G D B A C F E I H J

9.5 2진 트리 (예 9.19) 후위순 2진 트리 방문 좌측 부트리의 방문을 완료한후 우측 트리를 방문한다. 9.5 2진 트리 (예 9.19) 후위순 2진 트리 방문 좌측 부트리의 방문을 완료한후 우측 트리를 방문한다. 그 후 자료값을 참조한다. 줄 25, 줄 26은 좌측 child와 우측 child에 대한 재귀적 호출이다. 아래의 출력은 그림 9.5의 경우를 postorder로 방문한 결과이다. (예 9.19 계속) 함수postorder (tree.c에서) output 22 void postorder(BTREE root) 23 { 24 if (root != NULL) { 25 postorder(root -> left_child); /* left 재귀 호출 */ 26 postorder(root -> right_child); /* right 재귀 호출 27 printf(“%c ”, root -> d); 28 } 29 } 30 A C B E F D J I G

9.8 예 제 (예제 9.1) p1과 p2가 가리키는 노드들 사이에 q가 가리키는 노드를 삽입하는 함수 void insert(NODE*) 예제 9.1

p1, p2, q라는 3 개의 NODE 포인터를 인수로 받아 q가 가리키는 노드를 void insert(NODE *p1, NODE *p2, NODE *q) { p1 -> next = q; /* 삽 입 */ q -> next = p1; } 예제 9.1(계속) 함수 insert [해 설] p1, p2, q라는 3 개의 NODE 포인터를 인수로 받아 q가 가리키는 노드를 p1과 p2가 가리키는 노드 사이에 삽입하고 있다.

(예제 9.2) 주어진 리스트의 모든 노드의 메모리를 반환 하는 리스트 제거 함수 void remove_list(NODE *head) { if (head != NULL) { remove_list(head -> next); free(head); /* 기억장소 해제 */ } 예제 9.2 함수 remove_list [해 설] 맨 앞 노드가 널이 아니면 맨 앞 노드 제외한 나머지 리스트에 대해 재귀적으로 remove_list를 호출하여 모두 지우고 반환하면, 맨 앞 노드를 최종적으로 지우게 된다. 결국 가장 뒤쪽 노드부터 제거되는 방식이다. 가령 노드 수가 5개라면 마지막 널로 호출하는 것 포함 총 6번의 호출이 일어난다.

예제 9.3 reverse_data 1 /* File : ex9-3.c 2 stack 의 push, pop을 이용 자료 배열을 뒤집어 저장하는 함수 작성 3 list2.c의 함수를 이용; 다음 같이 컴파일 4 cc –o ex9-3 list2.c ex9-3.c 5 ex9-3 6 */ 7 #include “list.h” 8 void add_front_list(NODE**, float); 9 BOOL del_front_list(NODE**, float*); 10 11 #define push add_front_list 12 #define pop del_front_list 13 14 void reverse_data(int length, float s[]) { 15 NODE *t = NULL; 16 int i; 17 for (i = 0; i < length; i++) 18 push(&t, s[i]); 19 for (i = 0; i < length; i++) 20 pop(&t, &s[i]); 21 } 22 예제 9.3 reverse_data

배열에 저장된 값들을 뒤집어 저장하는 reverse_data를 작성하였음. 23 int main(void) { 24 #define NUM 5 25 int i; 26 float s[NUM] = {10.0, 11.0, 12.0, 13.0, 14.0}; 27 for (i = 0; i < NUM; ++) printf(“%.1f ”, s[i]); printf(“\n”); 28 reverse_data(NUM, s); 29 for (i = 0; i < NUM; ++) printf(“%.1f ”, s[i]); printf(“\n”); 30 } 예제 9.3(계속) [해 설] output 배열에 저장된 값들을 뒤집어 저장하는 reverse_data를 작성하였음. push를 이용하여 배열의 자료를 순서대로 스택에 저장한 다음, pop을 이용하여 배열에 순서대로 넣는다. - push, pop 함수는 교재의 add_front_list와 del_front_list를 사용하였다. 10.0 11.0 12.0 13.0 14.0 14.0 13.0 12.0 11.0 10.0

(예제 9.4) 배열로 저장된 자료값에서 2진 트리를 생성하는 프로그램 1 /* File : ex9-4.c 2 배열로 저장된 자료에서 2진 트리 생성 3 tree.c의 함수를 이용 테스트; 다음같이 컴파일 후 동작 4 cc –o ex9-4 tree.c ex9-4.c 5 ex9-4 */ 6 #include “tree.h” 7 8 /*------ 2진 트리 생성 ------*/ 9 BTREE new_node(void) 10 { 11 return ((BTREE) malloc(sizeof(NODE))); 12 } 13 BTREE init_node(DATA d1, BTREE p1, BTREE p2) 14 { 15 BTREE t; 16 t = new_node(); 17 t->d = d1; 18 t->left_child = p1; 19 t->right_child = p2; 20 return t; 21 } 예제 9.4

예제 9.4(계속) output 22 23 /* ------ 배열로 부터 연결 2진 트리 생성 --------- */ 23 /* ------ 배열로 부터 연결 2진 트리 생성 --------- */ 24 BTREE create_tree(DATA a[], int i, int size) 25 { 26 if (i >= size) 27 return NULL; 28 return (init_node(a[i], 29 create_tree(a, 2*i+1, size), 30 create_tree(a, 2*i+2, size) )); 31 } 32 33 int main(void) { 34 #define SIZE 10 35 DATA a[SIZE] = {‘G’, ‘D’, ‘I’, ‘B’, ‘F’, ‘H’, ‘J’, ‘A’, ‘C’, ‘E’}; 36 BTREE tree; /* 트리의 루트 */ 37 38 tree = create_tree(a, 0, SIZE); 39 inorder(tree); printf(“ : inorder traversal\n”); 40 preorder(tree); printf(“ : preorder traversal\n”); 41 postorder(tree); printf(“ : postorder traversal\n”); 42 } 예제 9.4(계속) output $ cc –o ex9-4 tree.c ex9-4.c $ ex9-4 A B C D E F G H I J : inorder traversal G D B A C F E I H J : preorder traversal A C B E F D H J I G : postorder traversal

배열 a에는 다음 트리의 상위 레벨부터 순서대로 저장하고 있다. 즉 a[0]에 ‘G’, a[1]에 ‘D’, a[2]에 ‘I’, a[3]에 ‘B’, a[4]에 ‘F’ 등등 이 방식은 a[i]의 좌측 child는 a[2*i+1]에, 우측 child는 a[2*i+2]에 저장하는 방법이다. create_tree는 배열 a에서 다음의 2진 트리를 생성한다. 교재의 inorder, preorder, postorder 방문기법을 이용(tree.c에 저장) 출력하였다. 예제 9.4(계속) [해 설]