제 6 강의. 연결리스트 1. 포인터타입 2. 단순연결리스트 3. 연결리스트를이용한스택의구현 4. 연결리스트를이용한큐의구현 5. 리스트구현방법의정리 1
리스트자료구조 데이터연산설명 스택 int stack[100]; (10, 30, 40, 20) push(35); y=pop(); 삽입과삭제가한쪽끝 큐 int queue[100]; (10, 30, 40, 20) insert(35); y=delete(); 삽입과삭제가양쪽끝 삽입과삭제가아무곳에서나일어난다. 리스트 ( 순서있는리스트 ) Ordered List int list[100]; (10, 30, 40, 20) insert(35); y=delete(); ( 문제점 ) => 데이터가많으면순서를유지하기위하여데이터이동이많아진다. ( 해결방법 )? 2
동적 (dynamic) 데이터의관리 프로그램실행중데이터가이동을많이한다면? - 데이터가움직이지않으면검색을빨리할수있다. - 데이터는삽입, 삭제연산에의하여위치와개수가변한다. - 데이터가변경되어위치가바뀌면검색을빨리하기위한위한재배치를한다. 3
1. 포인터타입 (Pointers) 연결리스트는기억장소의임의의구조체로구현된노드를서로연결하여리스트를만든다. 따라서다음데이터가저장된노드의기억장소를저장하는 ( 가리키는 ) 값이필요하다. 기억장소의주소값을저장하는데이터타입을 포인터 (pointer) 타입 이라한다 기억장소 -> 기억장소의주소 -> 주소를저장하는기억장소 1020 번지 777 1020 번지 1020 기억장치 ( 정수저장 ) 기억장소주소 주소를기억하는변수 ( 포인터변수 ) 서울시하늘동 100 번지 서울시하늘동 100 번지 장소 ( 집 ) 주소 주소를기록한종이 4
포인터타입사용예 1 int x; /* 내용을저장하는정수형변수 */ int *y; /* 주소를저장하는정수형변수 */ int z; x= 10; /* 내용 10을저장 */ y = &x; /* x의주소를저장, x의주소값을알필요없다.*/ z = *y; /* 주소 y가가리키는곳의내용을저장 */ /* z = x와같은의미가된다. */ int a[10]; /* 배열변수 a는주소값으로처리한다. */ /* 그이유는배열의내용전체를이동할경우보다주소값을알려주면편하기때문이다. */ x(100 번지 ) 10 y(104 번지 ) 100 z(108 번지 ) 10 a(120 번지 ) 130 130 번지 5
포인터사용의예 2 예제 1) 아래프로그램을실행하고결과를살펴보아라. #include <stdio.h> int main() { int i, *pi; float f, *pf; pi = &i; // i의주소값 pf = &f; // j의주소값 *pi = 1024; *pf = (float) 3.14; printf("an integer=%d,a float=%f\n", *pi, *pf); 6
예제 2) 아래프로그램을예제 1 프로그램과비교하여보아라. 포인터변수와포인터가가리키는기억장소확보하여데이터를저장하고기억장소반납 /* DBLAB pointer.c */ #include <stdio.h> #include <malloc.h> int main() { int *pi; float *pf; pi = (int *)malloc(sizeof(int)); /* 기억장소배정 */ pf = (float *)malloc(sizeof(float)); /* 기억장소배정 */ *pi = 1024; *pf = (float) 3.14; printf("an integer=%d,a float=%f\n", *pi, *pf); free(pi); /* 기억장소반환 */ free(pf); 7
실행문장 => 1: int i,*pi; 2: float f,*pf; /* 변수 i, pi, f, pf 의기억장소가할당된다. */ 기억장소 0 NULL i(int) pi(int *) 0.0 NULL f(float) pf(float *) 힙기억장소 출력 8
실행문장 => 3: pi = (int *)malloc(sizeof(int)); 4: pf = (float *)malloc(sizeof(float)); /* 변수 pi, pf 에힙에서임의의기억장소가할당되어각각정수형, 실수형포인터로변환되어주소값을저장한다 */ 기억장소 0 1050 i(int) pi(int *) 0.0 1080 f(float) pf(float *) 힙기억장소 0 1050 번지 0.0 1080 번지 출력 9
실행문장 => 5: *pi = 1024; 6: *pf = 3.14; /* 변수 pi, pf 가가리키는곳에 1024 와 3.14 를저장한다.*/ 기억장소 0 1050 i(int) pi(int *) 0.0 1080 f(float) pf(float *) 힙기억장소 1024 1050 번지 3.14 1080 번지 출력 10
실행문장 => 7: printf( an integer=%d,a float=%f\n,*pi,*pf); /* 변수 pi, pf 가가리키는곳의값을출력한다.*/ 기억장소 0 1050 i(int) pi(int *) 0.0 1080 f(float) pf(float *) 힙기억장소 1024 1050 번지 3.14 1080 번지 출력 an integer=1024,a float=3.14 11
실행문장 => 8: free(pi); 9: free(pf); /* 변수 pi, pf 가가리키는기억장소를반환한다. pi, pf 가가리키는값은남아있지만사용하면 error 이다.*/ 기억장소 0 1050 i(int) pi(int *) 0.0 1080 f(float) pf(float *) 힙기억장소 출력 an integer=1024,a float=3.14 12
데이터의관리 : 배열과연결리스트 배열 ( 리스트 ) 연결리스트 ( 리스트 ) 구현방법배열로선언예 ) int list[n]; 연결리스트예 ) list_ptr ptr; 검색이진검색트리를이용한검색 조작 ( 삽입, 삭제 ) 삽입과삭제후데이터재배치가힘들다. 데이터는그대로두고포인터로데이터를연결한다. 13
연결리스트를만들기위한구조체선언 - ( 자기참조구조체, self referential structure, a pointer to itself) - ( 동적인자료의할당과해지 (allocation/deallocation) 를위한자료구조 ) struct node { int data; // 데이터 struct node *link; // 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; data(int) link(list_ptr) list 타입 14
리스트자료의예 list_node item1, item2, item3; item1.data = 10; item2.data = 20; item3.data = 30; item1.link = item2.link = item3.link = NULL; // 포인터초기값 item1 item2 item3 10 20 30 리스트의연결예 item1.link=&item2; item2.link=&item3; item1 item2 item3 10 20 30 15
프로그램 1 - 노드를 3개선언하여연결하여리스트로만든다. #include <stdio.h> #include <malloc.h> struct node { int data; // 데이터 struct node *link;// 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; int main(void) { list_node item1, item2, item3; item1.data = 10; item2.data = 20; item3.data = 30; item1.link = item2.link = item3.link = NULL; // 포인터초기값 printf("%d %d %d\n", item1.data, item2.data, item3.data); 16
프로그램 2 - 노드를 3개기억장소에서받아와서연결하여리스트로만든다 #include <stdio.h> #include <malloc.h> struct node { int data; // 데이터 struct node *link;// 다른데이터주소 ( 포인터 ) ; typedef struct node list_node; typedef list_node * list_ptr; int main(void) { list_ptr first, second, third; first = (list_ptr)malloc(sizeof(list_node)); second = (list_ptr)malloc(sizeof(list_node)); third = (list_ptr)malloc(sizeof(list_node)); third->link = NULL; first->data = 10; second->data = 20; third->data = 30; first->link = second; second->link = third; 17 printf("%d %d %d\n", first->data, second->data, third->data);
2. 단순연결리스트 (Singly Linked Lists) 연결리스트의가장간단한형태로그냥 연결리스트 라고부른다. 노드들을연결한형태이며노드는데이터부분과링크부분으로구성된다. 데이터부분은한개혹은여러개의속성을저장할수있다. 링크부분은다음노드의주소값을가리킨다. 동적기억할당과해제가가능하다. 단순연결리스트 ptr 20 40 30 10 18
예 1) 단순연결리스트노드의선언과생성 struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; list_node 타입의구조 data(int) link(list_ptr) 19
예 2) 빈리스트에노드를한개생성하여 50 을저장 list_ptr ptr = NULL; ptr=(list_ptr)malloc(sizeof(list_node)); // 기억장소를 Heap 영역에서 ( 동적 ) 할당받는문장 ptr->data=50; ptr->link=null; ptr ptr->data 50 ptr->link NULL 20
예 3) 단순연결리스트 삽입알고리즘 30과 70 사이에 50을삽입한다면? 1) 기억장소로부터노드를얻는다.( 주소값 : paddr) ptr 10 30 70 90 NULL 주소값을변수 paddr 에저장 paddr 2) 노드에 50 데이터를저장한다. ptr 10 30 70 90 NULL paddr 50 21
3) paddr 노드의링크값에 30 노드의링크값을저장한다. ptr 10 30 70 90 NULL paddr 50 4) 30 노드의링크값에 paddr 을저장한다. ptr 10 30 70 90 NULL paddr 50 22
예 4) 단순연결리스트 삭제알고리즘 ptr 10 30 50 70 90 NULL 1 2 1) 삭제할 50 노드의앞노드 30 을찾는다. 2) 30 노드의링크를 50 노드의링크가가리키는데이터로바꾼다. 23
예 5) 연결리스트의생성함수 ( 정수형데이터저장, 리스트포인터반환 ) list_ptr create() { list_ptr first, second; first = (list_ptr)malloc(sizeof(list_node)); second = (list_ptr)malloc(sizeof(list_node)); second->link=null; second->data=20; first->data=10; first->link=second; return first; first second 10 20 NULL 24
Q/A 다음그림에서노드가가리키는곳 first second 10 20 30 NULL * 다음이가리키는곳은? first -> data first -> link -> data first -> link -> link second -> link 다음의값은? first -> data first -> link -> data first -> link -> link -> link second -> link (*first).data 25
예6) 리스트생성실험프로그램 : 1개의노드동적 (dynamic) 생성 #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; int main() { list_ptr ptr = NULL; ptr = (list_ptr)malloc(sizeof(list_node)); ptr->data = 10; /* 리스트의값 */ ptr->link = NULL; printf(" %d n", ptr->data); 26
예 7)-1 리스트생성실험프로그램 : 4 개의노드를반복문으로생성 #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; ptr 40 int main() { list_ptr ptr = NULL, before=null; int i; for(i=1; i<=4; i++) //=> create( ) { ptr = (list_ptr)malloc(sizeof(list_node)); ptr->data = i*10; /* 리스트의값 */ ptr->link = before; before=ptr; printf(" %d n", ptr->data); // => print_list( ) printf(" %d n", ptr->link->data); printf(" %d n", ptr->link->link->data); printf(" %d n", ptr->link->link->link->data); /* for( ; ptr; ptr=ptr->link) printf(" %d n", ptr->data); */ 30 20 10 NULL 27
예 7)-2 리스트출력함수 print_list( ) while not end of the list do print out data field; move to the next node; end; void print_list(list_ptr ptr) { printf( The list contains: ); for( ; ptr; ptr = ptr->link) printf( %4d, ptr->data); printf( \n ); 28
예 7)-3 리스트생성실험프로그램 함수 create() 로작성 #include <stdio.h> #include <malloc.h> struct node { int data; // int 로 struct node *link; ; typedef struct node list_node; typedef list_node *list_ptr; list_ptr create(int); // 함수원형선언... void print_list(list_ptr p); void delete(list_ptr p, int k); int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); // 40 30 20 10 29
list_ptr create(int n) // QUIZ : 30을끝에다붙인다. { list_ptr first, temp = NULL, before = NULL; // for (int i = 1; i <= n; i++) // { temp = (list_ptr)malloc(sizeof(list_node)); temp->data =(n- i+1) * 10; temp->link = before; before = temp; // 중요 first = temp; return first; void print_list(list_ptr p) { list_ptr temp; for (temp = p; temp; temp = temp->link) //temp!= NULL { printf("%d ", temp->data); // 수정 printf(" n"); ptr 10 20 30 40 NULL 30
예 8)-1 연결리스트실험 - k 값을가진노드삭제함수 delete ( ) #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; /* 7-3 동일 create, print_list */ int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); // 40 30 20 10 delete(p, 30); print_list(p); // 40 20 10 // 리스트에서 k 값노드삭제... void delete(list_ptr p, int k) { list_ptr temp, before; if (!p) return; // p 가 NULL 이면아무것도않는다. // k 앞노드를 before 에저장한다. before = NULL; for (temp = p; temp!= NULL; temp = temp->link) { if (temp->data == k) { before->link = temp->link; break; // k 앞노드링크를 k 노드링크값으로치환. before = temp; // QUIZ : 맨처음노드의데이터가 k 이면어떻게해야하는가? 실험을해보고결과를살피자 31
예 8)-2 연결리스트실험 - k 값을가진노드삽입 insert ( ) #include <stdio.h> #include <malloc.h> struct node { int data; struct node * link; ; typedef struct node list_node; typedef list_node * list_ptr; /* 7-3 동일 create, print_list */ int main() { list_ptr p; p = create(4); // 이렇게작동... print_list(p); // 40 30 20 10 insert(p, 35); print_list(p); // 40 35 30 20 10 void insert(list_ptr p, int k) { list_ptr temp, before, temp1; if (!p) return; // p 가 NULL 이면아무것도않는다. // k 앞노드를 before 에저장한다. before = NULL; for (temp = p; temp!= NULL; temp = temp->link) { if (temp->data > k) { temp1 = (list_ptr)malloc(sizeof(list_node)); temp1->data = k; temp1->link = temp; before->link = temp1; break; // k 앞노드링크를 k 노드링크값으로치환. before = temp; 32
예 9) 노드삽입 : ptr 이가리키는리스트에 aptr 이가리키는노드다음에 x(50) 삽입 ptr 10 30 20 NULL ptr 10 30 20 NULL aptr 50 temp 33
/* node 변수가가리키는곳다음에데이터 50 을노드를삽입 */ 함수로작성했을경우 ptr 대신 ptr 주소값 *ptr 을인자로전달하는이유 => 다음페이지참고 void insert(list_ptr *ptr, list_ptr aptr, int x) { list_ptr temp; temp=(list_ptr)malloc(sizeof(list_node)); temp->data=50; if(*ptr) // 연결리스트가빈리스트가아닐경우 { temp->link = aptr->link; aptr->link = temp; else { // 연결리스트가비어있는경우처리 temp->link = NULL; *ptr = temp; 34
[ 참고 ] ptr 대신 ptr의주소값 *ptr 을인자로전달하는이유 => 함수에서 ptr 값의변화된값을받기위하여주소인자로전달앞의 insert( ) 함수의경우 ptr 값이바뀌어반환될수있기떄문에바뀐값을받을수있도록 ptr의주소값을전달한다. ( 선언 ) void insert(list_ptr ptr, list_ptr node) { ptr 대신 void insert(list_ptr *ptr, list_ptr node) { *ptr 로사용 ( 호출 ) main() { insert(ptr, node) 대신 main() { insert(&ptr, node) 로호출 35
예 10) 노드삭제 - ptr: 리스트첫노드를가리키는포인터변수 - aptr 삭제될노드를가리키는변수 - trail: 삭제될노드의바로앞노드를가리키는변수 ptr trail aptr 10 50 30 70 20 NULL 삭제될노드가첫노드일경우 ( 삭제후 ptr 값이바뀌는경우 ) 와그렇지않은경우로나눈다. 1) 삭제될노드가리스트의첫노드일때 리스트시작인 ptr 값이바뀐다 ptr=aptr trail Trail =NULL ptr 10 50 20 NULL (a) 삭제전 50 20 NULL (a) 삭제후 36
2) 그외의경우리스트시작인 ptr 값이안바뀐다 ptr trail aptr ptr 10 50 20 NULL 10 20 NULL (a) 삭제전 (a) 삭제후 void delete(list_ptr *ptr, list_ptr trail, list_ptr aptr) { if(aptr==*ptr) /* 첫노드가지울노드와같을때 */ *ptr=aptr->link; else /* 그외의경우 */ trail->link = aptr->link; free(aptr); 37
3. 연결리스트를이용한스택과큐의구현 3.1. 연결리스트를이용한스택의구현 (Dynamically Linked Stacks) top NULL 연결리스트스택 #define MAX_STACKS 10 /* n=max_stacks=10 */ typedef struct stack *stack_ptr; typedef struct stack { 연결리스트를이용한스택구조의선언 int item; stack_ptr link; ; stack_ptr top; 38
top element key link NULL 스택의초기상태 top = NULL 스택의상태 - 비어있는스택 : top = NULL -꽉찬상태 malloc( ) 함수호출시기억장소공간이부족할때 39
/* top 대신 top 의주소값 *top 을인자로전달하는이유 => push() 함수에서 top 값의변화된값을받기위하여주소인자로전달 */ void push(stack_ptr *top, int data) { stack_ptr temp = (stack_ptr)malloc(sizeof (stack)); if(!temp) { fprintf(stderr, The memory is full\n ); exit(1); temp->item=item; temp->link=*top; *top = temp; 스택의 push() 함수 - 리스트맨앞에노드를삽입 40
int pop(stack_ptr *top) { stack_ptr temp = *top; int data; if(!temp ) { fprintf(stderr, The stack is empty\n ); exit(1); 스택의 pop( ) 함수 data=temp->item; -리스트맨앞의노드삭제 *top=temp->link; free(temp); return data; 41
/* 연결리스트스택정의여기에 */ int main() { int e; push(20); push(40); push(40); push(40); push(60); 스택테스트의 main 함수 printf(" Begin Stack Test...\n"); while(!isempty()) { e = pop(); printf("value = %d\n", e); 42
3.2. 연결리스트를이용한큐의구현 (Dynamically Linked Queues) front rear NULL 연결리스트큐 연결리스트를이용한 1 개의큐구현 #define MAX_QUEUES 10 /* m=max_queues=10 */ typedef struct queue *queue_ptr; typedef struct queue { element item; queue_ptr link; ; queue_ptr front, rear; 43
front element key link rear NULL 큐의초기상태 front = rear = NULL 큐의상태 - 비어있는큐 : front = NULL -꽉찬상태: malloc( ) 함수호출시기억장소확보가안될때 44
void insert(queue_ptr *front, queue_ptr *rear, element x) { queue_ptr temp = (queue_ptr)malloc(sizeof(queue)); if(!temp ) { fprintf(stderr, The memory is full\n ); exit(1); temp->item=x; temp->link=null; if(*front) (*rear)->link=temp; else *front = temp; *rear = temp; 연결리스트큐에삽입함수 insert( ) - 리스트의맨뒤 (rear) 에삽입 45
element delete(queue_ptr *front) { queue_ptr temp=*front; element x; if(!(*front)) { fprintf(stderr, The queue is empty\n ); exit(1); 연결리스트큐에삭제함수 delete( ) - 리스트의맨앞에서삭제 x=temp->item; *front=temp->link; free(temp); return x; 46
Q/A linkedlist-queue.c 프로그램을실행해보자 ( 실험 1) linkedlist-queue.c 프로그램을실행해보고 4 장의 queue.c 프로그램과비교해보자 ( 실험 2) 큐에있는원소의수를세는함수를작성하여라 (linkedlist-queue.c) int elementcount(queue_ptr front, queue_ptr rear) { /* 여기작성 */ 47
4. 연결리스트를이용한다항식문제해결 연결리스트를이용한응용이많이있지만대표적인예로다항식의계산을보도록한다. 다항식은 A(x) = 7x 3 + 4x 2 + + 2 같은식처럼여러개의항 (term) 으로구성된식이다. 다항식에관한연산을하기위해서항의검색, 삽입, 삭제가필요하고이러한연산을하기위한자료구조로연결리스트를사용하면편리하다. - 두개의다항식의덧셈을통하여연결리스트를조작하는프로그래밍기법 - 연결리스트의노드를획득하고해지하는함수를통하여기억장소를관리 48
4.1. 다항식 (Polynomials) 과연결리스트 다항식이란? 다항식은 A(x) = 7x 3 + 4x 2 + + 2 같은식처럼여러개의항 (term) 으로구성된식이다. 다항식의계산, 두개의다항식의덧셈, 곱셈등에관한여러가지문제를해결하려면다항식을컴퓨터프로그램에표현하여저장하여야한다. 저장된다항식은여러가지연산과정을거쳐서계산을하거나, 다항식끼리덧셈, 다항식끼리곱셈등을하게된다. 이러한문제를효율적으로해결하려면다항식의항들을저장하는방법을잘선택하여야한다. 자료구조기초함수들함수들 다항식자료구조 컴퓨터에저장 항의비교 같은항찾기 두항을더하기 다항식의계산 다항식의덧셈 다항식의곱셈 두항을곱하기 항의삽입 항의삭제 49
다항식을배열에표현하면? 예를들어다음다항식 7x 3 + 4x 2 + 2 은배열에다음 { (7,3), (4,2), (2,0) 을저장하여야한다. 예를들어다음과같이선언하고계수 (coefficient) 만을배열에저장하면된다. int poly [10]; 배열 0 1 2 3 4 5 6 7 8 9 poly 2 0 4 7 0 0 0 0 0 0 50
다항식을연결리스트에표현하면? 다음다항식을배열로표현하면어떻게될까? 7x 1000 + 4x 23 + + 2 - 방법 1 : 배열에단순저장 - 방법 2 : 연결리스트로다항식의항 { (7,1000), (4,23), (2,0) 을저장 다항식을연결리스트로표현하면? A(x) = a m-1 x m-1 + + a 0 x0 typedef struct poly_node *poly_ptr; typedef struct poly_node { int coef; int expon; poly_ptr link; ; poly_ptr a,b,d; coef expon link 51
예 ) a a = 3x 14 + 2x 8 + 1 3 14 2 8 1 0 NULL b b = 8x 14-3x 10 + 10x 6 8 14-3 10 10 6 NULL 52
4.2. 연결리스트를이용한다항식의덧셈 연결리스트로표현된두개의다항식을더하는프로그램을작성하여보자. a = 3x 14 + 2x 8 + 1 b = 8x 14-3x 10 + 10x 6 d = 11x 14-3x 10 + 2x 8 + 10x 6 + 1 a 3 14 2 8 1 0 NULL d 11 14-3 10 2 8 10 6 1 0 NULL b 8 14-3 10 10 6 NULL 53
연결리스트로표현된두개의다항식 a, b 를더하는경우를단계별로보자. (a) a->expon == b->expon ( 지수가같은경우 ) 두다항식 a,b 의최고차항두개를비교하여같으면두항의계수를더하여새로운다항식 d 에항을만든다. 덧셈후포인터를이동한다. 3 14 2 8 1 0 NULL 8 a 14-3 10 10 6 NULL b 11 14 NULL d 54
(b) a->expon < b->expon (b 의지수가더큰경우 ) 두다항식 a,b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다. 예의경우 b 가가르키는지수값이크므로 b 의항을 d 에더한다. 3 14 2 8 1 0 NULL a 8 14-3 10 10 6 NULL b 11 14-3 10 NULL 55
(c) a->expon > b->expon (a 의지수가더큰경우 ) 두다항식 a, b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다 ( 예의경우 a 의가르키는지수값이크므로 a 의항을 d 에더한다 ). 3 14 2 8 1 0 NULL a 8 14-3 10 10 6 NULL b 11 14-3 10 2 8 NULL d 56
(d) a->expon < b->expon 두다항식 a,b 의최고차항두개를비교하여같으면항의계수가큰항을새로운다항식 d 에더한다 ( 예의경우 b 가가르키는지수값이크므로 b 의항을 d 에더한다 ). 3 14 2 8 1 0 NULL 8 14-3 10 10 6 NULL a b 11 14-3 10 2 8 10 6 NULL d 57
(e) b == NULL; 두다항식 a,b 중 b 의항이 NULL 이되면 a 의남은항을 d 에복사하여연결한다 ( 예의경우 a 가가르키는지수값이크므로 b 의항을 d 에더한다 ). 3 14 2 8 1 0 NULL 8 14-3 10 10 6 NULL a b = NULL 11 14-3 10 2 8 10 6 1 0 NULL d 58
두다항식의덧셈 - 앞의예를참고하여두개의다항식을더하는프로그램 padd() 를작성하였다. padd() 함수 /* 두개의다항식을더하는함수, 인자는두다항식의포인터, 결과는새로생성된다항식의포인터이다 */ poly_ptr padd(poly_ptr a,poly_ptr b) { poly_ptr front,rear,temp; int sum; rear=(poly_ptr)malloc(sizeof(poly_node)); if(is_full(rear)) { 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; ( 계속 ) 59
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; 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; 60
리스트의끝에노드를첨가 padd() 함수에서필요한다항식의끝에항을붙이는함수 attach() 이다. attach 함수 /* 항을다항식에연결하는함수, 인자는항의계수, 지수, 다항식의포인터이고출력인자는다항식포인터 *ptr 이다 */ void attach(float coef, int exp, poly_ptr *ptr) { poly_ptr temp; temp=(poly_ptr)malloc(sizeof(poly_node)); if(is_full(temp)) { fprintf(stderr, The memory is full n ); exit(1); temp->coef = coef; temp->expon = exp; (*ptr)->link = temp; *ptr=temp; 61
두개의다항식을더하는프로그램의수행시간은? m, n : 두다항식의항의수 -계수덧셈 O(min{m, n) -지수비교 O(m + n) - 다항식 d의노드생성시간 O(m + n) 전체시간복잡도 O(m + n) 62
4.3. 연결리스트노드의관리 다항식의예에서연산을하다보면필요없는항이만들어진다. 이러한항은기억장소에다시반환되어야한다. 예 아래예에서임시로계산된다항식 temp 의모든항은기억장소에반환되어야한다. e (x) = a(x) * b(x) + d(x) ( 프로그램 ) poly_ptr a, b, d, temp, e; a = read_poly(); b = read_poly(); d = read_poly(); temp = pmult(a, b); e = padd(temp, d); print_poly(e); 63
다항식을가리키는포인터가인자로주어지면다항식에포함된항을하나씩모두기억장소에반환하는프로그램은다음과같다. 다항식의삭제 erase 함수 /* 다항식항을기억장소로반환하는함수인자는다항식의포인터이다. */ void erase(poly_ptr *ptr) { poly_ptr temp; while (*ptr) { temp = *ptr; *ptr = (*ptr)->link; free(temp); 64
노드 ( 항 ) 의할당과해지 다항식의계산을위해자주일어나는노드의생성과해지를위하여노드를저장하는리스트 ( 노드창고 ) 를만들어놓을수도있다. - 처음에모든사용가능한노드를기억장소 ( 연결리스트 ) 에모아둔다. - avail : 연결리스트의처음을가르키는포인터 avail 1 2 n 초기연결리스트 NULL 노드저장소 (Storage pool) 65
get_node 함수 /* 노드가필요할경우노드저장소에서노드한개를를반환해주는함수 get_node() */ poly_ptr get_node(void) { poly_ptr node; if (avail) { node = avail; avail = avail->link; else { node = (poly_ptr)malloc(sizeof(poly_node)); if(is_full(node)) { fprintf(stderr, The memory is full n ); exit(1); return node; 66
ret_node 함수 /* 필요없는노드를반환받아노드저장소 avail 에저장하는함수 ret_node() */ void ret_node(poly_ptr ptr) { ptr->link = avail; avail = ptr; erase 함수 /* 필요없는다항식전체를받아서각노드를반복하여 avail 연결리스트에반환하는함수 */ void erase(poly_ptr *ptr) { poly_ptr temp; while (*ptr) { temp = *ptr; *ptr = (*ptr)->link; ret_node(temp); 67
다항식의노드를쉽게반환하려면? 다항식의노드를반환하는함수 erase() 는 O(n) 의시간이소요된다. 좀더효율적인방법으로 O(1) 의시간에해결하려면? - 다항식을원형연결리스트로바꾼다. ( 마지막노드의링크가리스트의시작노드를가리킨다.) ptr - 효율적인 erase 알고리즘 - 알고리즘효율성 O(1) cerase 함수 /* 필요없는노드들을한번에원형노드저장소에반환하는함수 */ void cerase(poly_ptr *ptr) { if(*ptr) { temp = (*ptr)->link; (*ptr)->link = avail; avail = temp; *ptr = NULL; 68
5. 리스트와연결리스트 (List and Linked List) 리스트 (list) - 순서가있는데이터를말한다. - 리스트자료에대한연산은검색, 변경 ( 삽입, 삭제 ) 이다. - 스택과큐는리스트의특수한형태이다. 리스트자료구조의구현 - 배열은리스트자료구조를구현하는방법이다. - 연결리스트도리스트를구현하는방법이다. 배열을이용한리스트구현은다음과같은장단점이있다. - 연속된기억장소 - 데이터의중간에삽입, 삭제시데이터이동이필요하다. - 데이터의크기가수행전 ( 컴파일때 ) 결정된다. - 정적인기억장소할당 (static storage allocation) 69
리스트자료구조 순서가있는자료의총칭. 검색과변경 ( 삽입과삭제 ) 연산이필요한자료구조 일반리스트 삽입과삭제가임의의장소에서일어남. 스택 큐 삽입과삭제가한쪽끝에서일어남 삽입은 rear 에서삭제는 front 에서일어남 70
리스트자료구조를구현하는프로그램자료구조의종류 ( 설명 ) 왼쪽은자료구조이고오른쪽은구현방법이다. 예를들면스택은배열로구현할수도있고연결리스트로도구현할수있다. 리스트자료구조 자료구조구현 일반리스트 배열 스택 원형배열 큐 연결리스트 71
리스트자료구조와연산 리스트자료구조연산 삽입 삭제 insert ( ) delete ( ) insertfirst() insertlast ( ) deletefirst ( ) deletelast ( ) 리스트자료구조 스택자료구조 큐자료구조 ( 리스트연산 ) Insert(), delete(), ( 스택연산 ) insertfirst()=push(), deletefirst()=pop(), ( 큐연산 ) deletefirst(), insertlast(), 72
리스트를구현하는두가지방법의비교 배열연결리스트설명 구현방법 배열로선언예 ) int list[n]; 연결리스트예 ) list_ptr ptr; 기억장소확보시점 프로그램수행전 (compile time) 정적기억장소할당 ( 기억장소 N 개로시작 ) 프로그램수행후 (run time) 동적기억장소할당 ( 기억장소 1 개로시작 ) 배열에서기억장소가수행전에할당되는경우기억장소크기가고정되고, 사용여부에관계없이기억장소를확보한다. 기억장소연속성 연속된기억장소할당 기억장소힙 (heap) 영역에서임의로할당 연결리스트에서는기억장소가여기저기흩어져있고링크를통하여연결이된다. 삽입과삭제알고리즘 O(n) O(1) 프로그래밍은연결리스트가복잡하다. 73
Review 포인터는데이터의효율성, 함수의주소인자, 동적인자료구조의세가지기능을구현하기위한방법이다. 포인터는주소값을저장하며수행시간 ( 동적, dynamic) 에리스트데이터들을주소값으로연결하는데사용된다. 리스트를배열을이용하면쉽게표현할수있다. 연결리스트는포인터를이용하여리스트데이터를연결하는방법이다. 연결리스트는스택과큐를구현하는방법이된다. 다항식문제는배열을이용하여해결할수있다 연결리스트의생성과반환을위한함수들에대한정확한이해가필요하다. C 언어에서주로쓰는함수는 malloc() 과 free() 함수이다. 74