10 장구조체와리스트처리 0
자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1
자기참조구조체 10-2
자기참조구조체 예제 struct list { int struct list a; data; *next; dat a next 10-3
자기참조구조체 동작예제 struct list a, b, c; a.data = 1; b.data = 2; c.data = 3; a.next = b.next = c.next = NULL; a b c 1 NULL 2 NULL 3 NULL 10-4
동작예제 ( 계속 ) a.next = &b; b.next = &c; 자기참조구조체 a b c 1 2 3 NULL - a.next -> data : 값 2 - a.next -> next -> data : 값 3 10-5
선형연결리스트 선형연결리스트는자료구조체들이순차적으로매달려있는빨래줄과같음 헤드포인터는이리스트상의첫번째원소를포인트하고, 각원소는다음원소를포인트함 그리고마지막원소는 NULL 값을가짐 10-6
앞으로사용할헤더파일 선형연결리스트 /* In file list.h */ #include <stdio.h> #include <stdlib.h> typedef char DATA; /* will use char in examples */ struct linked_list { ; DATA d; struct linked_list *next; typedef struct linked_list typedef ELEMENT ELEMENT; *LINK; 10-7
선형연결리스트예제 세개의문자 n, e, w 를저장하는선형연결리스트생성 head n e w NULL 10-8
선형연결리스트예제 1. n 을위한노드생성및저장 head = malloc(sizeof(element)); head -> d = 'n'; head -> next = NULL; head n NULL 10-9
선형연결리스트예제 2. e 을위한노드를생성하고 n 노드에연결 head -> next = malloc(sizeof(element)); head -> next -> d = 'e'; head -> next -> next = NULL; head n e NULL 10-10
선형연결리스트예제 3. w 을위한노드를생성하고 e 노드에연결 head -> next -> next = malloc(sizeof(element)); head -> next -> next -> d = 'w'; head -> next -> next -> next = NULL; head n e w NULL 10-11
리스트연산 기본적인선형리스트연산 1. 리스트생성 2. 원소개수세기 3. 원소탐색 4. 두리스트결합 5. 원소삽입 6. 원소삭제 10-12
리스트연산 리스트생성 주어진문자열을리스트로변환하는함수 ( 재귀버전 ) #include <stdlib.h> #include "list.h" LINK string_to_list(char s[]) { LINK head; if (s[0] == '\0') /* base case */ return NULL; else { head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; 10-13
리스트연산 리스트생성 호출예 list = string_to_list( new ); // LINK list list string_to_list( new ) 10-14
리스트연산 리스트생성 string_to_list( new )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head n string_to_list( ew ) 10-15
리스트연산 리스트생성 string_to_list( ew )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head e string_to_list( w ) 10-16
리스트연산 리스트생성 string_to_list( w )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head w string_to_list( ) 10-17
리스트연산 리스트생성 string_to_list( )... if (s[0] == '\0') /* base case */ return NULL; 10-18
리스트연산 리스트생성 string_to_list( w )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head w string_to_list( ) 10-19
리스트연산 리스트생성 string_to_list( w )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head w string_to_list( ) NULL 10-20
리스트연산 리스트생성 string_to_list( w )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head w NULL 10-21
리스트연산 리스트생성 string_to_list( ew )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head e string_to_list( w ) 10-22
리스트연산 리스트생성 string_to_list( ew )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head e string_to_list( w ) w NULL 10-23
리스트연산 리스트생성 string_to_list( ew )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head e w NULL 10-24
리스트연산 리스트생성 string_to_list( new )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head n string_to_list( ew ) 10-25
리스트연산 리스트생성 string_to_list( new )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head n string_to_list( ew ) e w NULL 10-26
리스트연산 리스트생성 string_to_list( new )... head = malloc(sizeof(element)); head -> d = s[0]; head -> next = string_to_list(s + 1); return head; head n e w NULL 10-27
리스트연산 리스트생성 호출 list = string_to_list( new ); // LINK list list string_to_list( new ) 10-28
리스트연산 리스트생성 호출 list = string_to_list( new ); // LINK list list string_to_list( new ) n e w NULL 10-29
리스트연산 리스트생성 호출 list = string_to_list( new ); // LINK list list n e w NULL 10-30
리스트연산 리스트생성 주어진문자열을리스트로변환하는함수 ( 반복버전 ) LINK s_to_l(char s[ ]){ LINK head = NULL, tail; int i; if (s[0]!= '\0') { // first element head = malloc(sizeof(element)); head -> d = s[0]; tail = head; for (i = 1; s[i]!= '\0'; ++i) { // add to tail tail -> next = malloc(sizeof(element)); tail = tail -> next; tail -> d = s[i]; tail -> next = NULL; return head; // end of list 10-31
리스트연산 s_to_l("ab") 호출에의한리스트생성단계 head t ai l A? head t ai l A?? head A B? t ai l head A B NULL t ai l 10-32
리스트연산 원소세기 리스트의원소수를세는함수 ( 재귀버전 ) int count(link head){ if (head == NULL) return 0; else return (1 + count(head -> next)); 10-33
리스트연산 원소세기 리스트의원소수를세는함수 ( 반복버전 ) int count_it(link head){ int cnt = 0; for ( ; head!= NULL; head = head -> next) ++cnt; return cnt; 10-34
리스트연산 리스트연결 두리스트를연결하는함수 ( 재귀버전 ) void concatenate(link a, LINK b){ assert(a!= NULL); if (a -> next == NULL) a -> next = b; else concatenate(a -> next, b); 10-35
리스트처리함수 자기참조리스트를처리하기위한재귀함수의일반적인형태 void generic_recursion(link head){ if (head == NULL) else do the base case do the general case and recur with generic_recursion(head -> next) 10-36
리스트연산 삽입 리스트에서현재위치에새로운원소를삽입할경우, 고정된시간내에삽입을할수있음 반대로큰배열에새로운값을삽입할경우, 배열값의순서를유지해야하기때문에삽입에걸리는시간은평균적으로배열길이에비례함 10-37
리스트연산 삽입 리스트에서 p1 과 p2 가포인트하고있는인접한두원 소사이에 q 가포인트하고있는원소삽입 p1 p2... A C... q B NULL p1 p2... A C... q B 10-38
리스트연산 삽입 삽입함수 void insert(link p1, LINK p2, LINK q){ assert(p1 -> next == p2); p1 -> next = q; /* insert */ q -> next = p2; 10-39
리스트연산 삭제 리스트에서 p 가포인트하고있는다음원소삭제 삭제되는원소를 free() 를사용하여반납해야함 p... A B C... p... A B C... 10-40
삭제함수 리스트연산 삭제 void delete_list(link head) { if (head!= NULL) { delete_list(head -> next); free(head); // release storage 10-41
수식표기법 중위표기법예 ) 3 + 7 전위표기법예 ) +, 3, 7 후위표기법 ( 폴리시표기법 ) 예 ) 3, 7, + 10-42
폴리시표기법 중위수식을후위수식으로만드는방법 1. 중위수식을연산자의우선순위에따라완전한괄호표현으로변환예 ) 1 + 3 * 4 (1 + (3 * 4)) 2. 각연산자를그연산자를포함하는괄호중제일가까운닫는괄호뒤로보냄예 ) (1 + (3 * 4) ) (1 (3, 4) * ) + 3. 괄호제거예 ) 1, 3, 4, *, + 10-43
알고리즘 폴리시수식계산 - 수식의각항목을왼쪽에서오른쪽으로검사하며다음과같은일을반복한다. 1. 현재검사되는항목이숫자이면다음항목을검사한다. 2. 현재검사되는항목이연산자이면앞의두항목 ( 숫자 ) 을이연산자의피연산자로하여계산한후새로운항목으로삽입한다. 3. 이러한일은하나의숫자가남을때까지반복하고, 마지막남은수가이수식의값이다. 10-44
13, 4, -, 2, 3, *, + 폴리시수식계산예제 13, 4, -, 2, 3, *, + 1 2 3 9 (=13 4), 2, 3, * + 4 5 6 9, 6 (= 2 * 3), + 15 (= 9 + 6) 7 10-45
스택 선형연결리스트로구현한스택 st ack cnt el em dat a stack cnt elem NULL t op top data dat a data...... dat a NULL data 10-46
스택구현 stack.h #include <stdio.h> #include <stdlib.h> #define EMPTY 0 #define FULL 10000 typedef char data; typedef enum {false, true boolean; struct elem { // element on the stack data d; struct elem *next; ; 10-47
스택구현 stack.h typedef struct elem elem; struct stack { int cnt; // a count of the elements elem *top; // ptr to the top element ; typedef struct stack stack; void initialize(stack *stk); void push(data d, stack *stk); data pop(stack *stk); data top(stack *stk); boolean empty(const stack *stk); boolean full(const stack *stk); 10-48
#include "stack.h" 스택구현 - 함수 void initialize(stack *stk){ stk -> cnt = 0; stk -> top = NULL; void push(data d, stack *stk){ elem *p; p = malloc(sizeof(elem)); p -> d = d; p -> next = stk -> top; stk -> top = p; stk -> cnt++; 10-49
스택구현 - 함수 data pop(stack *stk){ data d; elem *p; d = stk -> top -> d; p = stk -> top; stk -> top = stk -> top -> next; stk -> cnt --; free(p); return d; 10-50
스택구현 - 함수 data top(stack *stk){ return (stk -> top -> d); boolean empty(const stack *stk){ return ((boolean) (stk -> cnt == EMPTY)); boolean full(const stack *stk){ return ((boolean) (stk -> cnt == FULL)); 10-51
스택 - 검사프로그램 #include "stack.h" int main(void){ char str[ ] = "My name is joanna Kelly!"; int i; stack s; initialize(&s); // initialize the stack printf(" In the string: %s\n", str); for (i = 0; str[i]!= '\0'; ++i) if (!full(&s)) push(str[i], &s); // push a char on the stack printf("from the stack: "); while (!empty(&s)) putchar(pop(&s)); // pop a char off the stack putchar('\n'); return 0; 10-52
스택 - 검사프로그램 출력 In the string : My name is Jonna Kelly! From the stack :!yllek annoj si eman ym 10-53
폴리시수식계산 2- 스택알고리즘 1. 폴리시스택이공백이면, 연산스택의 top 을답으로하고중지한다. 2. 폴리시스택이공백이아니면, 폴리시스택에서 pop 하여그것을 d 에배정한다. ( 이알고리즘에서는자료보관을위해 d, d1, d2 를사용한다.) 3. d 가피연산자라면, 연산스택에 d 를 push 한다. 4. d 가연산자라면, 연산스택을두번 pop 하여처음것을 d2 에배정하고다음것을 d1 에배정한다. d 연산자를 d1 과 d2 피연산자에적용하여계산하고, 결과를연산스택에 push 한다. 단계 1 부터다시수행한다. 10-54
2- 스택알고리즘예제 (1) 13 4 4 폴리시스택 연산스택 - 2 3 * + - 2 3 * + 13-2 3 * + 4 13 2 3 * + 9 10-55
2- 스택알고리즘예제 (2) 폴리시스택 연산스택 3 * + 2 9 * + 3 2 9 + 6 9 15 10-56
큐 큐는 front 와 rear 가있고, rear 에서는삽입이, front 에서는삭제가일어남 연산 - 초기화 - 삽입 - 삭제 - 상태확인 10-57
큐구현 리스트로의큐구현 queue cnt f r ont r ear el em el em el em dat a dat a dat a NULL 10-58
큐구현 queue.h #include <assert.h> #include <stdio.h> #include <stdlib.h> #define EMPTY 0 #define FULL 10000 typedef unsigned int data; typedef enum {false, true boolean; struct elem { data d; struct elem *next; ; typedef struct elem elem; // an element in the queue 10-59
큐구현 queue.h struct queue { int cnt; // a count of the elements elem *front; // ptr to the front element elem *rear; // ptr to the rear element ; typedef struct queue queue; void initialize(queue *q); void enqueue(data d, queue *q); data dequeue(queue *q); data front(const queue *q); boolean empty(const queue *q); boolean full(const queue *q); 10-60
트리 노드라고하는원소의유한집합 루트, 리프노드, 부트리 루트노드 a 부트리의루트 b f g 부트리 c d e h 리프노드 10-61
이진트리 한노드가최대 2 개의자식노드를갖는트리 G D I B F H J A C E 10-62
이진트리 헤더파일 tree.h #include <assert.h> #include <stdio.h> #include <stdlib.h> typedef char DATA; struct node { DATA d; struct node *left; struct node *right; ; typedef struct node NODE; typedef NODE *BTREE; #include "fct_proto.h" /* function prototypes */ 10-63
중위순회 1. 왼쪽부트리방문 2. 루트방문 3. 오른쪽부트리방문 전위순회 1. 루트방문 2. 왼쪽부트리방문 3. 오른쪽부트리방문 후위순회 1. 왼쪽부트리방문 2. 오른쪽부트리방문 3. 루트방문 이진트리순회 10-64
중위순회 void inorder(btree root){ if (root!= NULL) { inorder(root -> left); printf("%c", root -> d); inorder(root -> right); 10-65
중위순회 void inorder(btree root){ G if (root!= NULL) { inorder(root -> left); printf("%c", root -> d); D I inorder(root -> right); B F H J A C E 10-66
중위순회 void inorder(btree root){ G if (root!= NULL) { inorder(root -> left); printf("%c", root -> d); D I inorder(root -> right); B F H J A C E 출력 A B C D E F G H I J 10-67
전위순회 void preorder(btree root){ if (root!= NULL) { printf("%c ", root -> d); preorder(root -> left); preorder(root -> right); 10-68
전위순회 void preorder(btree root){ G if (root!= NULL) { printf("%c ", root -> d); preorder(root -> left); D I preorder(root -> right); B F H J A C E 10-69
전위순회 void preorder(btree root){ G if (root!= NULL) { printf("%c ", root -> d); preorder(root -> left); D I preorder(root -> right); B F H J A C E 출력 G D B A C F E I H J 10-70
후위순회 void postorder(btree root){ if (root!= NULL) { postorder(root -> left); postorder(root -> right); printf("%c ", root -> d); 10-71
후위순회 void postorder(btree root){ G if (root!= NULL) { postorder(root -> left); postorder(root -> right); D I printf("%c ", root -> d); B F H J A C E 10-72
후위순회 void postorder(btree root){ G if (root!= NULL) { postorder(root -> left); postorder(root -> right); D I printf("%c ", root -> d); B F H J A C E 출력 A C B E F D H J I G 10-73
트리생성 BTREE new_node( ){ return (malloc(sizeof(node))); BTREE init_node(data d1, BTREE p1, BTREE p2){ BTREE t; t = new_node( ); t -> d = d1; t -> left = p1; t -> right = p2; return t; 10-74
트리생성 BTREE create_tree(data a[], int i, int size) { if (i >= size) return NULL; else return (init_node(a[i], create_tree(a, 2 * i + 1, size), create_tree(a, 2 * i + 2, size))); 0 1 2 3 4 5 6 7 8 9 G D I B F H J A C E 10-75
일반적인연결리스트 어떤자료구조는배열과리스트를결합하여사용함 일반트리 - 형제노드는선형리스트로자식노드는배열의인덱스로접근 a t[0] a b f g b f g c d e h NULL c d e h NULL NULL NULL NULL 10-76
일반트리 일반트리의원소를위한형정의 #include <assert.h> #include <stdio.h> #include <stdlib.h> typedef char DATA; struct node { int child_no; DATA d; struct node *sib; ; typedef struct node NODE; typedef NODE *GTREE; #include "fct_proto.h" /* function prototypes */ 10-77
노드생성함수 일반트리 GTREE new_gnode(){ return (malloc(sizeof(node))); GTREE init_gnode(data d1, int num, GTREE sibs){ GTREE temp; temp = new_gnode(); temp -> d = d1; temp -> child_no = num; temp -> sib = sibs; return temp; 10-78
일반트리 일반트리생성 t[0] = init_gnode('a', 1, NULL); t[1] = init_gnode('b', 2, NULL); t[1] -> sib = init_gnode('f', 6, NULL); t[1] -> sib -> sib = init_gnode('g', 7, NULL); t[2] = init_gnode('c', 3, NULL); t[2] -> sib = init_gnode('d', 4, NULL); t[2] -> sib -> sib = init_gnode('e', 5, NULL); t[3] = t[4] = t[5] = NULL; t[6] = init_gnode('h', 8, NULL); t[7] = t[8] = NULL; 10-79
일반트리 전위순회함수 /* Preorder traversal of general trees. */ void preorder_g(gtree *t, int ind) { GTREE tmp; /* tmp traverses the sibling list */ tmp = t[ind]; /* t[ind] is the root node */ while (tmp!= NULL) { printf("%c %d\n", tmp -> d, tmp -> child_no); preorder_g(t, tmp -> child_no); tmp = tmp -> sib; 10-80