Chapter 4. LISTS

Size: px

Start display at page:

Download "Chapter 4. LISTS"

래원 마
7 years ago
Views:

1 C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or stddef.h(ansi C) 노드의각필드에값할당 ptr data = 10; // (*ptr).data = 10; ptr link = NULL; 4 장. 리스트 (Page 8)

2 리스트에새로운노드를삽입 (1) 두개의노드로구성된리스트 ptr NULL (2) A 다음에 temp 라는새로운노드를삽입 : insert(&ptr, A) - Program 4.3 ptr NULL A 50 temp 4 장. 리스트 (Page 9)

3 Program 4.3: 리스트에삽입 void insert(struct node **ptr, struct node *before) { /* data = 50 인새로운노드를 ptr 이가리키는리스트의 before 노드다음에삽입 */ struct node *temp; temp = (struct node *) malloc(sizeof(struct node)); if (temp == NULL) { fprintf(stderr, "The memory is full\ n"); exit(1); temp data = 50; if (*ptr!= NULL) { temp link = before link; before link = temp; else { temp link = NULL; *ptr = temp; 4 장. 리스트 (Page 10)

4 리스트에서노드삭제 delete(&ptr, before, A) ptr 이가리키는리스트에서노드 A 를삭제 before 는 A 노드의이전노드를가리키고있음 void delete(struct node **ptr, struct node *before, struct node *A) { // ptr: 포인터의포인터, before와 A: 포인터 if (before!= NULL) before link = A link; else *ptr = (*ptr) link; free(a); before 가없을경우, A 를삭제하는방법? 연습문제 4, 6, 7, 8( 페이지 154) 풀것! 4 장. 리스트 (Page 11)

5 예 : 삭제 (1) delete(&ptr, NULL, ptr) ptr A before = NULL ptr NULL NULL (a) before deletion (b) after deletion (2) delete(&ptr, ptr, ptr link) ptr before A ptr NULL NULL (a) before deletion (b) after deletion 4 장. 리스트 (Page 12)

6 3. 리스트를이용한스택과큐 배열을이용한스택과큐의구현방법의문제점 메모리낭비 Stack Full 의발생가능성 리스트를이용한스택과큐의구현 top element link... NULL Linked Stack front Linked Queue element link... rear NULL 4 장. 리스트 (Page 13)

7 리스트를이용한스택의선언 #define MAX_STACK 10 typedef struct { int key; /* other fields */ element; struct stack { element data; struct stack *link; ; (1) 스택의초기조건 : top[i] = NULL; 0 i < MAX_STACKS (2) 경계조건 : top[i] = NULL if i 번째 stack이 empty. IS_FULL(temp) if the memory is full. //MAX_STACKS 만큼의스택선언 struct stack *top[max_stacks]; 4 장. 리스트 (Page 14)

8 Program 4.6: 리스트스택에노드추가 void push( int i, element item ) { // 스택 top에새로운 item 추가 struct stack *temp = (struct stack *) malloc(sizeof(struct stack)); if (temp == NULL) { // memory full fprintf(stderr,"the memory is full\ n"); exit(1); temp data = item; temp link = top[i]; top[i] = temp; 4 장. 리스트 (Page 15)

9 Program 4.7: 리스트스택에서삭제 element pop(int i) { // 스택의 top이가리키는 element를삭제하여 return struct stack *temp = top[i]; element item; if (temp == NULL) { // top[i] == NULL fprintf(stderr, "The stack is empty\ n"); exit(1); item = temp data; top[i] = temp link; free(temp); return item; 4 장. 리스트 (Page 16)

10 리스트를이용한큐의선언 #define MAX_QUEUES 10 struct Que { element data; struct Que *link; ; 큐를위한초기설정 : front[i] = NULL; 0 i < MAX_QUEUES 경계조건 : front[i] = NULL if i번째큐가 empty IS_FULL(temp) if the memory is full //MAX_QUEUES 만큼의큐선언 struct Que *front[max_queues], *rear[max_queues]; 4 장. 리스트 (Page 17)

11 Program 4.8: 리스트큐에노드추가 void addq(int i, element item) { // 큐의 rear에새로운 element 추가 struct Que *temp = (struct Que *)malloc(sizeof(struct Que)); if (temp == NULL) { // memory full fprintf(stderr,"the memory is full\ n"); exit(1); temp data = item; temp link = NULL; if (front[i]) rear[i] link = temp; else front[i] = temp; rear[i] = temp; 4 장. 리스트 (Page 18)

12 Program 4.9: 리스트큐에서삭제 element deleteq(int i) { // 큐에서 front가가리키는노드삭제후 element는 return struct Que *temp = front[i]; element item; if (temp == NULL) { // *front == NULL fprintf(stderr, "The queue is empty\ n"); exit(1); item = temp data; front[i] = temp link; free(temp); return item; 4 장. 리스트 (Page 19)

13 4. 다항식 (Polynomials) 다항식을단일연결리스트로표현 struct poly { int coef; int expon; struct poly *link; ; struct poly *a, *b, *d; coef expon link 4 장. 리스트 (Page 20)

14 다항식의예 a = 3x x b = 8x 14 3x x 6 a b 다항식의합 d = a + b 의처음세단계 (Figure 4.12) Program 4.10 & Program 4.11: 두개의다항식의합 시간복잡성 : O(m + n) 4 장. 리스트 (Page 21)

15 그림 4.12: d = a + b 의첫번째단계 NULL a NULL b NULL d (a) a expon == b expon 4 장. 리스트 (Page 22)

16 그림 4.12: d = a + b 의두번째단계 NULL a NULL b NULL d (b) a expon < b expon 4 장. 리스트 (Page 23)

17 그림 4.12: d = a + b 의세번째단계 NULL a NULL b NULL d (c) a expon > b expon 4 장. 리스트 (Page 24)

18 Program 4.10: 두개의다항식더하기 (1) struct poly *padd(struct poly *a, struct poly *b) { // d = a + b인다항식 d를 return struct poly *front, *rear, *temp; int sum; // 사용하지않는초기노드를생성. 이유는? rear = (struct poly *)malloc(sizeof(struct poly)); if (rear == NULL) { fprintf(stderr, The memory is full\ n ); exit(1); front = rear; while (a && b) switch (COMPARE(a expon, b expon)) { case -1: // a expon < b expon attach(b coef, b expon, &rear); b = b link; break; 4 장. 리스트 (Page 25)

19 Program 4.10: 두개의다항식더하기 (2) case 0: // a expon == b expon sum = a coef + b coef; if (sum) attach(sum, a expon, &rear); a = a link; b = b link; break; case 1: // a expon > b expon attach(a coef, a expon, &rear); a = a link; // 리스트 a 와 b 의나머지부분을복사 for (; a; a = a link) attach(a coef, a expon, &rear); for (; b; b = b link) attach(b coef, b expon, &rear); rear link = NULL; // 초기노드를삭제 temp = front; front = front link; free(temp); return front; 4 장. 리스트 (Page 26)

20 Program 4.11: 리스트의끝에새로운항추가 void attach ( float coefficient, int exponent, struct poly **rear) { /* coef = coefficient 이고 expon = exponent 인새로운노드를생성한후, ptr 이가리키는노드다음에연결. ptr 은생성된노드를가리키도록변경 */ struct poly *temp; temp = (struct poly *) malloc(sizeof(struct poly)); if (temp == NULL) { fprintf ( stderr, The memory is full \ n ); exit(1); temp coef = coefficient; temp expon = exponent; (*rear) link = temp; *rear = temp; 4 장. 리스트 (Page 27)

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경