제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보 (address) 도저장해주어야한다. 즉, 배열에서의단점을제거하면서메모리를효율적으로사용하고삽입과삭제가쉬워처리시간이단축되나, 관리유지에부가적인비용이든다. 그림 6-1: 각각의글씨조각들을연결해서만든휴대폰줄
연결리스트종류 3 단일연결리스트 (singly linked list) 포인터를이용해서한쪽방향으로만연결되어있는구조 환형연결리스트 (circular linked list) 환형큐와마찬가지로마지막노드에서처음노드로연결하여원형으로된구조 이중연결리스트 (doubly linked list) 한쪽방향으로만연결된경우반대방향의노드를접근하기어렵다는단점을보안, 양방향으로포인터를이용해서연결한구조 노드 (node) 4 연결리스트에서하나의데이터요소를저장하는단위 데이터정보 (data) 와위치정보 (pointer) 두가지는꼭가지고있어야하며이런다른자료형을하나로묶는데는구조체가적당하다. 데이터정보가저장되는부분은여러가지형태의자료형이나배열과같은복합적인자료형도가질수있으나이해를돕기위해 char형으로한다. 위치정보를가진포인터부분은다음노드나이전노드를가리킨다. 다음노드를가리키는포인터 : next(struct pnode* 형 ) 재귀적인용법으로쓰임.
노드 (node) 5 data next 그림 6.2 노드의구조 struct pnode char data; // 자료가저장되는부분 struct pnode *next; // 다음노드를가리키는포인터부분 *head, *p; typedef struct pnode NODE; 단일연결리스트 (Singly Linked List) 6 여러개의노드들이포인터를이용하여한방향으로만연결된단순한연결리스트 연결리스트의시작점은임의의포인터가가리킴시작점을가리키는포인터가그리스트의이름그림 6.3 Head : 연결리스트의시작점을가리킴 P : 연결되어있는방향으로움직이면서해당되는노드를가리키는포인터 NULL : 포인터의특수한형태로아무런항목도가리키지않음. 연결리스트의마지막노드에사용.
단일연결리스트 (Singly Linked List) 7 head->next->next->data head->next-> data head->data 256 300 128 400 head A B C D head->next head->next->next head->next->next->next NULL 그림 6.3 연결리스트의구조 연결리스트의동작 8 기본적인리스트의동작들 createnode(ch) - 노드가하나인연결리스트를만든다. 노드의데이터값은 ch이고리스트는지금만든한개의노드만을가지고있음. insert (list, ch) - 리스트에노드를삽입하는함수. 입력이되는대로리스트의맨뒤에차례대로삽입시킴 delete (list) - 리스트에서노드를삭제하는함수. 어느위치의노드를삭제하는지에따라다르게구현할수있다. printlist (list) - 리스트에있는노드들의값을출력
연결리스트의동작 9 노드만들기 NODE *createnode(char ch) NODE *p; p = (NODE *)malloc(sizeof(node)); // 메모리에노드영역을할당 if ( p == NULL) // 메모리에러 exit(0); p->data = ch; // 노드의자료멤버 p->next = NULL; // 노드의포인터멤버 return p; // 할당된노드 ( 구조체 ) 의주소 프로그램 6.2 노드의생성 연결리스트의동작 10 struct pnode char data; struct pnode *next; *head, *p; typedef struct pnode NODE; main() head = createnode('a'); 프로그램 6.3 생성된노드를헤드에연결 그림 6.5 생성되어진노드 A 를가지고있는리스트
연결리스트의동작 11 리스트출력하기 배열에서의출력 연결리스트의출력 printarray(a[]) i=0; while(a[i]!= 0 ) printf("%c", a[i]); i++; printf(" n"); printlist(node *p) while (p) printf("% c", p->data); p = p->next; printf(" n"); 연결리스트의동작 12 노드삽입 리스트가널인경우 그림 6.6 리스트가널인경우 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p->data = ch; p->next = NULL; 프로그램 6. 6 리스트가널인경우
연결리스트의동작 13 리스트가널이아닌경우 그림 6.7 리스트가널이아닌경우 ( 노드 3 개 ) 뒤에새로운노드를삽입 연결리스트의동작 14 temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp->next; temp->data = ch; temp->next = NULL; 프로그램 6.7 리스트가널이아닌경우 NODE *insert(node *p, char ch) NODE *temp; if(p==null) // 리스트에노드가없을경우
연결리스트의동작 15 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else // 리스트에노드가있으면맨뒤에삽입한다. temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p); 프로그램 6.8 두가지경우를고려한 insert 함수 연결리스트의동작 16 head 리스트 head 는 NULL Node f 를삽입 head f Node a 를삽입 head f a Node e 를삽입 head f a e Node c 를삽입 head f a e c Node d 를삽입 head f a e c d 그림 6.8 연결리스트에노드를 insert 하는과정
연결리스트의동작 17 // 연결리스트1.cpp #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert (NODE *, char); void prtlist (NODE *); /***************************************************/ /* insert : 노드를삽입하는함수 /***************************************************/ NODE *insert(node *p, char ch) NODE *temp; 연결리스트의동작 18 if(p==null) // 리스트에노드가없을경우 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else // 리스트에노드가있으면맨뒤에삽입한다. temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p);
연결리스트의동작 19 /**********************************************/ /* 출력함수 : 노드사이에화살표맨끝은. /**********************************************/ void prtlist ( NODE *p ) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data); /*******************************************/ /* main 함수 /*******************************************/ void main() char ch; int n = 5; NODE* head = NULL ; 연결리스트의동작 20 while ( n-- > 0 ) printf( "Enter the data value of the node : "); ch = getche(); printf(" n"); head = insert ( head, ch ); printf(" nlinked list : "); prtlist ( head ); 프로그램 6.9 연결리스트 그림 6.9 연결리스트프로그램을실행한결과화면
연결리스트의동작 21 노드삭제 1 맨앞의노드를삭제하는경우 head = head->next; head A B C D p 그림 6.10 리스트의맨앞의노드삭제 NULL 2 리스트의중간노드를삭제하는경우 q->next = q->next->next; head A B C D q p 그림 6.11 중간에있는노드를삭제하기 NULL 연결리스트의동작 22 /******************************************/ /* data 멤버값이 ch인노드를찾아서삭제 */ /******************************************/ int deletenode(node* p, char ch) NODE *q; //p보다하나전에위치한노드 if ( p->data == ch ) p = p->next; free(p); return 1; while ( p->data!= c ) if ( p->next == NULL) return 0; q = p; p = p->next; q->next = q->next->next; free(p); return 1; // 첫번째노드가찾는노드인경우 //head를다음노드로 // 시작노드를제거 // 삭제성공 // 찾는노드가있는곳까지이동 // 끝까지찾는노드가없으면 // 삭제실패 // 바로뒤의노드의위치를기억 //p를다음노드로이동시킨다 //p보다두번째뒤의노드 //p 노드를제거
연결리스트의정렬 23 그림 6.12 리스트정렬하기 1 단계 연결리스트의정렬 24 그림 6.13 리스트정렬하기 2 단계
연결리스트의정렬 25 // 연결리스트 3.c -- 연결리스트정렬하기 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert (NODE *, char); void prtlist (NODE *); NODE *sortlist (NODE *); /* insert : 노드를삽입하는함수 연결리스트의정렬 26 NODE *insert(node *p, char ch) NODE *temp; if(p==null) // 리스트에노드가없을경우 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else // 리스트에노드가있으면맨뒤에삽입한다. temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL;
연결리스트의정렬 27 return (p); /* 출력함수 void prtlist ( NODE *p ) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data); /* 리스트를정렬하기 NODE *sortlist(node *p) NODE *temp1,*temp2,*min,*prev,*q; 연결리스트의정렬 28 q = NULL; while(p!= NULL) prev = NULL; min = temp1 = p; temp2 = p->next; while ( temp2!= NULL ) if( min->data > temp2->data ) min = temp2; prev = temp1; temp1 = temp2; temp2 = temp2->next; if(prev == NULL) p = min->next; else prev->next = min->next; min->next = NULL;
연결리스트의정렬 29 if( q == NULL) q = min; /* 최저값의노드를옮김 */ else temp1 = q; while( temp1->next!= NULL) temp1 = temp1->next; temp1->next = min; return (q); /* 메인함수 void main() char ch; int n = 5; NODE *head = NULL ; while ( n-- > 0 ) printf( "Enter a character : "); ch = getche(); 연결리스트의정렬 30 printf(" n"); head = insert (head,ch); printf(" nlinked list : "); prtlist ( head ); head = sortlist(head); printf(" nsorted list : "); prtlist ( head ); 프로그램 6.11 연결리스트정렬 그림 6.14 연결리스트정렬프로그램결과화면
31 노드의값에따라정렬해가면서리스트에노드삽입하기 리스트맨앞에삽입리스트의맨앞이나, 빈리스트에노드삽입하는경우리스트중간에삽입현재참조중인노드가연결리스트의중간노드인경우리스트맨뒤에삽입현재참조중인노드가연결리스트의마지막노드인경우 그림 6.15 리스트정렬하여노드삽입 노드의값에따라정렬해가면서리스트에노드삽입하기 32 리스트맨앞에삽입 리스트의맨앞이나, 빈리스트에노드삽입하는경우 그림 6.16 리스트맨앞에노드 a 를삽입 prev = (NODE *)malloc(sizeof(node)); prev->data = ch; prev->next = curr; p = prev; return p; 프로그램 6.12 리스트맨앞에노드를생성
33 노드의값에따라정렬해가면서리스트에노드삽입하기 리스트중간에삽입 현재참조중인노드가연결리스트의중간노드인경우 그림 6.17 리스트중간에노드 d 를삽입 temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = curr; prev->next = temp; return p; 프로그램 6.13 리스트중간인 prev 와 curr 사이에 temp 를삽입 노드의값에따라정렬해가면서리스트에노드삽입하기 34 리스트맨뒤에삽입 현재참조중인노드가연결리스트의마지막노드인경우 그림 6.18 리스트맨뒤에노드 g 를삽입 temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = NULL; curr->next = temp; return p; 프로그램 6.14 리스트의맨뒤에 temp 노드삽입
35 노드의값에따라정렬해가면서리스트에노드삽입하기 // 연결리스트4.c -- 정렬되게삽입하기 // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert(node *p, char ch); NODE *sorted_insert (NODE *p, char ch); void prtlist (NODE *p); /* insert : 노드를삽입하는함수 ( 일반적인 ) 노드의값에따라정렬해가면서리스트에노드삽입하기 36 NODE *insert(node *p, char ch) NODE *temp; if(p==null) // 리스트에노드가없을경우 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else // 리스트에노드가있으면맨뒤에삽입한다. temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p); 자료구조 ( 오용철著 ) : 제6장연결리스트
37 노드의값에따라정렬해가면서리스트에노드삽입하기 /* sorted insert : 알파벳순으로정렬되게삽입하는함수 NODE *sort_insert (NODE* p, char ch) NODE *curr, *prev, *temp; curr = p; prev = NULL; // 리스트맨앞에삽입되는경우 if (curr->data > ch) temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = curr; p = temp; return p; 노드의값에따라정렬해가면서리스트에노드삽입하기 38 while (curr->data < ch) // 적절한위치를찾는다 // 리스트맨마지막노드에삽입되는경우 if (curr->next == NULL) temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = NULL; curr->next = temp; return p; prev = curr; curr = curr->next; // 리스트중간에삽입되는경우 temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = curr; prev->next = temp; return p; /* 출력함수
39 노드의값에따라정렬해가면서리스트에노드삽입하기 void prtlist (NODE *p) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data); /* 메인함수 void main() char ch; int n = 3; NODE *head = NULL ; head = insert (head, 'b'); head = insert (head, 'd'); head = insert (head, 'e'); printf (" n정렬된 linked list : "); prtlist ( head ); 노드의값에따라정렬해가면서리스트에노드삽입하기 40 while ( n-- > 0 ) printf( " nenter the data (into the sorted list) : "); ch = getche(); printf(" n"); head = sort_insert (head, ch); printf (" nlinked list : "); prtlist ( head ); 프로그램 6.15 정렬하면서삽입하는 ilnked list 그림 6.19 정렬된 linkded list 결과화면
연결리스트의크기 41 // 연결리스트5.c -- 연결리스트의크기 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert(node *, char); void prtlist(node *); int nodecount(node *); /* insert : 노드를삽입하는함수 연결리스트의크기 42 NODE *insert(node *p, char ch) NODE *temp; if(p==null) // 리스트에노드가없을경우 p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else // 리스트에노드가있으면맨뒤에삽입한다. temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p); 자료구조 ( 오용철著 ) : 제6장연결리스트
연결리스트의크기 43 /* 출력함수 void prtlist ( NODE *p ) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data); /* 연결리스트의크기를알아보는함수 int nodecount (NODE *p ) int count=0; while (p!= NULL) count ++; p = p->next; return(count); 자료구조 ( 오용철著 ) : 제6장연결리스트 연결리스트의크기 44 /* 메인함수 void main() char ch; int n = 5, size; NODE *head = NULL ; while ( n-- > 0 ) printf( "Enter a character : "); ch = getche(); printf(" n"); head = insert(head,ch); printf(" nlinked list : "); prtlist ( head ); size = nodecount(head); printf(" nthe number of nodes : %d n",size); 프로그램 6.16 리스트의길이를구하는프로그램
연결리스트의크기 45 그림 6.20 리스트의길이를구하는결과화면 연결리스트의도치 46 // 연결리스트 6.c -- 도치 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert(node *, char); void prtlist(node *); NODE *reverse(node *); /**************************************************/ /* insert : 노드를삽입하는함수 /**************************************************/
연결리스트의도치 47 NODE *insert(node *p, char ch) NODE *temp; if(p==null) p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p); 자료구조 ( 오용철著 ) : 제6장연결리스트 연결리스트의도치 48 /***************************************************/ /* 출력함수 /***************************************************/ void prtlist ( NODE *p ) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data); /***************************************************/ /* reverse : 연결리스트의도치시키는함수 /***************************************************/ NODE *reverse(node* p) NODE *temp, *curr, *prev; prev = NULL; curr = p; while (curr!= NULL) temp = prev; prev = curr; curr = curr->next; prev->next = temp; return (prev); 자료구조 ( 오용철著 ) : 제6장연결리스트
연결리스트의도치 49 /***************************************************/ /* 메인함수 /***************************************************/ void main() char ch; int n = 5, size; NODE *head = NULL ; while ( n-- > 0 ) printf( "Enter a character : "); ch = getche(); printf(" n"); head = insert(head,ch); printf(" nlinked list : "); prtlist ( head ); head = reverse(head); printf(" nreversed list : "); prtlist ( head ); 프로그램 6.17 리스트의순서를도치시키는프로그램 연결리스트의도치 50 그림 6.21 리스트의순서를도치시키는결과화면
두개의연결리스트를병합하여하나로만들기 51 p a c d q b e f r a b c d e f 그림 6.22 연결리스트의정렬병합과정 두개의연결리스트를병합하여하나로만들기 52 // 리스트 7.c : 두개의리스트를 merge 시키는함수 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode char data; struct pnode *next; ; typedef struct pnode NODE; NODE *insert(node *, char); NODE *sort_insert(node *, char); void prtlist(node *);
두개의연결리스트를병합하여하나로만들기 53 /* insert : 노드를삽입하는함수 NODE *insert(node *p, char ch) NODE *temp; if(p==null) p=(node *)malloc(sizeof(node)); if(p==null) exit(0); p-> data = ch; p-> next = NULL; else temp = p; while (temp-> next!= NULL) temp = temp-> next; temp-> next = (NODE *)malloc(sizeof(node)); if(temp -> next == NULL) exit(0); temp = temp-> next; temp-> data = ch; temp-> next = NULL; return (p); 두개의연결리스트를병합하여하나로만들기 54 /* sorted insert : 알파벳순으로정렬되게삽입하는함수 NODE *sort_insert (NODE* p, char ch) NODE *curr, *prev, *temp; curr = p; prev = NULL; // 리스트맨앞에삽입되는경우 if (curr->data > ch) temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = curr; p = temp; return p;
두개의연결리스트를병합하여하나로만들기 55 while (curr->data < ch) // 적절한위치를찾는다 // 리스트맨마지막노드에삽입되는경우 if (curr->next == NULL) temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = NULL; curr->next = temp; return p; prev = curr; curr = curr->next; // 리스트중간에삽입되는경우 temp = (NODE *)malloc(sizeof(node)); temp->data = ch; temp->next = curr; prev->next = temp; return p; 두개의연결리스트를병합하여하나로만들기 56 /* 출력함수 void prtlist ( NODE *p ) while (p->next!= NULL) printf("%c->",p-> data); p = p-> next; printf("%c. n", p->data);
두개의연결리스트를병합하여하나로만들기 57 /* merge : 두개의리스트를병합시키는함수 NODE *merge (NODE *p, NODE *q) NODE *r=null,*temp; if (p == NULL) r = q; else if(q == NULL) r = p; else if (p->data < q->data ) r = p; temp = p; p = p->next; temp->next = NULL; else r = q; temp =q; q = q->next; temp->next = NULL; 두개의연결리스트를병합하여하나로만들기 58 while((p!= NULL) && (q!= NULL)) if (p->data < q->data) temp->next = p; p = p->next; temp =temp->next; temp->next =NULL; else temp->next =q; q = q->next; temp =temp->next; temp->next =NULL; if (p!= NULL) temp->next = p; if (q!= NULL) temp->next = q; return( r) ;
두개의연결리스트를병합하여하나로만들기 59 /* 메인함수 void main() NODE *head1 = NULL; NODE *head2 = NULL; NODE *head3 = NULL; head1 = insert (head1, 'b'); head1 = insert (head1, 'd'); head1 = insert (head1, 'e'); printf (" nthe 1st list : "); prtlist ( head1 ); head2 = insert (head2, 'a'); head2 = insert (head2, 'c'); head2 = insert (head2, 'f'); printf (" nthe 2nd list : "); prtlist ( head2 ); head3 = (head1, head2); printf (" nmerged list : "); prtlist ( head3 ); 프로그램 6.18 리스트를정렬병합하는프로그램 두개의연결리스트를병합하여하나로만들기 60 그림 6.19 두개의리스트를병합시킨결과화면
연결리스트의응용 ( 다항식표현 ) 61 각항을하나의노드로표현하는데각노드는계수 (coefficient), 지수 (exponent), 그리고다음항을가리키는포인터로구성된다. exp coef exp coef exp coef A 5 3 2 4 0 6 exp coef exp coef exp coef B 5 6 4 3 1 2 그림 6.24 리스트로표현한다항식 연결리스트의응용 ( 다항식표현 ) 62 // 연결리스트 7.c -- 다항식 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct pnode int exp; int coeff; struct pnode *next; ; typedef struct pnode NODE; NODE *insert(node *, int, int); void printlist ( NODE * ); NODE *polyadd(node *, NODE *); NODE *sortlist(node *);
연결리스트의응용 ( 다항식표현 ) 63 /******************************************************/ /* insert /******************************************************/ NODE *insert(node *p, int e, int c) NODE *temp; if(p==null) p = (NODE *)malloc(sizeof(node)); if(p==null) printf("error n"); exit(0); p->exp = e; p->coeff = c; p->next = NULL; 연결리스트의응용 ( 다항식표현 ) 64 else temp = p; while (temp->next!= NULL) temp = temp->next; temp->next = (NODE *)malloc(sizeof(node)); if(temp->next == NULL) printf("error n"); exit(0); temp = temp->next; temp->exp = e; temp->coeff = c; temp->next = NULL; return (p);
연결리스트의응용 ( 다항식표현 ) 65 /******************************************************/ /* sort insert /******************************************************/ NODE *sortlist(node *p) NODE *temp1,*temp2,*max,*prev,*q; q = NULL; while(p!= NULL) prev = NULL; max = temp1 = p; temp2 = p->next; while ( temp2!= NULL ) if(max->exp < temp2->exp) max = temp2; prev = temp1; temp1 = temp2; temp2 = temp2-> next; if(prev == NULL) p = max -> next; 연결리스트의응용 ( 다항식표현 ) 66 else prev -> next = max -> next; max -> next = NULL; if( q == NULL) q = max; else temp1 = q; while( temp1 -> next!= NULL) temp1 = temp1 -> next; temp1 -> next = max; return (q);
연결리스트의응용 ( 다항식표현 ) 67 /******************************************************/ /* polyadd : 다항식덧셈하는함수 /******************************************************/ NODE *polyadd(node *p, NODE *q) NODE *r = NULL; int e; int c; while((p!=null) && (q!= NULL)) if(p->exp > q->exp) r = insert(r,p->exp,p->coeff); p = p->next; else if(p->exp < q->exp) r = insert(r,q->exp,q->coeff); q = q->next; else c = p->coeff + q->coeff; e = q->exp; r = insert(r, e, c); p = p->next; q = q->next; 연결리스트의응용 ( 다항식표현 ) 68 while(p!= NULL) r = insert( r, p->exp, p->coeff); p = p->next; while(q!=null) r = insert( r, q->exp, q->coeff); q = q->next; return(r); /******************************************************/ /* 다항식출력 : (coef, exp) -> (coef, exp) ->... /******************************************************/ void printlist ( NODE *p ) printf(" npolynomial : "); while (p->next!= NULL) printf("(%d,%d) -> ", p->coeff, p->exp); p = p->next; printf("(%d,%d)", p->coeff, p->exp);
연결리스트의응용 ( 다항식표현 ) 69 /******************************************************/ /* main /******************************************************/ void main() int e; int n,i; int c; NODE *poly1 = NULL ; NODE *poly2 = NULL; NODE *result; printf("how many terms in the 1st polynomial? n"); scanf("%d",&n); i=1; while ( n > 0 ) printf( "term #%d : coef and exp n",i); scanf("%d %d", &c, &e); poly1 = insert (poly1, e, c); i++; n--; 연결리스트의응용 ( 다항식표현 ) 70 printf("how many terms in the 2nd polynomial? n"); scanf("%d",&n); i=1; while ( n > 0 ) printf( "term #%d : coef and exp n",i); scanf("%d %d", &c, &e); poly2 = insert (poly2, e, c); i++; n--; poly1 = sortlist(poly1); poly2 = sortlist(poly2); printf(" nthe 1st "); printlist ( poly1 ); printf(" nthe 2nd"); printlist ( poly2 ); result = polyadd(poly1,poly2); printf(" nthe result of addition "); printlist ( result ); 프로그램 6.19 다항식두개를더하는프로그램
연결리스트의응용 ( 다항식표현 ) 71 그림 6.25 다항식두개를더하는프로그램결과화면 연결리스트응용 ( 스택과큐구현하기 ) 72 X X top A top A B C B NULL C 그림 6.11 연결리스트로구현한스택 (push) top A B C D B top C NULL D 그림 6.12 연결리스트로구현한스택 (pop)
연결리스트의응용 ( 스택과큐구현하기 ) 73 X NULL front A B C front A B C D NULL NULL A B C X B C D front rear front rear 그림 6.12 연결리스트로구현한큐 ( 삽입 ) 그림 6.13 연결리스트로구현한큐 ( 삭제 ) 연결리스트의응용 ( 스택과큐구현하기 ) 74 x A B C NULL y D E F NULL z G H I NULL 그림 6.14 연결리스트병합
단일연결리스트의장단점 75 구조가간단하고기억장소의소모가적은반면에역방향으로리스트를검색할수없기때문에노드를삽입하거나삭제하려면별도의포인터가필요하다. 위단점을해결하기위해이중연결리스트 (doubly linlked list) 를사용한다. 이중연결리스트 (Doubly Linked List) 76 llink data rlink 그림 6.15 이중연결리스트의노드구조 struct _NODE char data; // 자료를수록 struct _NODE *llink; // 이전노드를가리킨다. struct _NODE *rlink; // 다음노드를가리킨다. ; typedef struct _NODE NODE; NODE *head, *tail; head A B C D NULL NULL 그림 6.16 이중연결리스트의구조
이중연결리스트의장단점 77 단순연결리스트는오직하나의연결부분 ( 링크필드 ) 을가지고있지만이중연결리스트는연결부분을두개로하여한개일때보다는기억장소의낭비가있지만효율적인리스트운영이가능하다. 이중연결리스트의동작 78 X head A B C D NULL NULL 그림 6.17 이중연결리스트의노드삽입 head A B C D NULL NULL 그림 6.18 이중연결리스트의노드삭제
이중연결리스트의동작 79 Doubly linked list 의초기화 void initialize(char c) head = tail = (NODE *) malloc(sizeof(node)); head->pre = NULL; head->data = A ; head->post = NULL; 이중연결리스트의동작 80 Doubly linked list 의노드삽입 /* tail 노드뒤에새로운노드를추가 */ void insert_node(node *p, char ch) p->next = tail = (NODE *) malloc(sizeof(node)); tail->data = E ; tail->pre = p; tail->post = NULL; /* 노드 X 의우측에노드 I 를삽입 */ void addnode(node *I, NODE *X) I->data = E ; I->post = X->post; I->pre = X; X->post->pre = I; X->post = I;
이중연결리스트의동작 81 Doubly linked list 의노드삭제 /* 임의의노드 D 삭제 */ void delete_node(node *D) if(head->post == NULL) printf( 연결된리스트가없음 n ); else D->pre->post = D->post; D->post->pre = D->pre; free(d); 환형연결리스트 (Circular Linked List) 82 head A B C D 그림 6.19 환형연결리스트의구조 A B C D 그림 6.20 환형이중연결리스트의구조