<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>"

익태 가
5 years ago
Views:

1 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )

2 Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 2/112

3 1. 연결자료구조 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입 삭제연산이많이발생하는경우에성능상의문제발생 순차자료구조는배열을이용하여구현하기때문에배열이갖고있는메모리사용의비효율성문제를그대로가짐 순차자료구조에서의연산시간에대한문제와저장공간에대한문제를개선한자료표현방법필요 3/112

4 1. 연결자료구조 연결자료구조 (Linked Data Structure) 자료의논리적인순서와물리적인순서가일치하지않는자료구조 각원소에저장되어있는다음원소의주소에의해순서가연결되는방식 물리적인순서를맞추기위한오버헤드가발생하지않음 여러개의작은공간을연결하여하나의전체자료구조를표현 크기변경이유연하고더효율적으로메모리를사용 연결리스트 리스트를연결자료구조로표현한구조 연결하는방식에따라단순연결리스트와원형연결리스트, 이중연결리스트, 이중원형연결리스트 4/112

5 1. 연결자료구조 연결리스트의노드 연결자료구조에서하나의원소를표현하기위한단위구조 < 원소, 주소 > 의구조 데이터필드 (data field) 원소의값을저장 저장할원소의형태에따라서하나이상의필드로구성 링크필드 (link field) 다음노드의주소를저장 포인터변수를사용하여주소값을저장 5/112

6 1. 연결자료구조 노드연결방법에대한이해 - 기차놀이 1 이름표뽑기 2 자기가뽑은이름의사람을찾아서연결하기 : 승희 상원 수영 X 표를뽑은사람은마지막기차기차는이름표를들고있는방향으로움직인다. 6/112

7 1. 연결자료구조 노드연결방법에대한이해 - 기차놀이 기차놀이와연결리스트 기차놀이하는아이들 : 연결리스트의노드 이름표 : 노드의링크필드 7/112

8 1. 연결자료구조 선형리스트와연결리스트의비교 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week에대한선형리스트 8/112

9 1. 연결자료구조 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week 에대한연결리스트 9/112

10 1. 연결자료구조 선형리스트와연결리스트의비교 리스트이름 week - 연결리스트의시작을가리키는포인터변수 포인터변수 week 는연결리스트의첫번째노드를가리키는동시에연결된리스트 전체를의미 연결리스트의마지막노드의링크필드 - 노드의끝을표시하기위해서 null( 널 ) 저장 공백연결리스트 - 포인터변수 week 에 null 을저장 ( 널포인터 ) 각노드의필드에저장한값은포인터의점연산자를사용하여액세스 week.data : 포인터 week 가가리키는노드의데이터필드값 월 week.link : 포인터 week 가가리키는노드의링크필드에저장된주소값 /112

11 1. 연결자료구조 선형리스트와연결리스트의비교 리스트 week 의노드에대한 C 프로그램구조체정의 typedef struct Node{ char data[4]; struct Node* link; }; 11/112

12 2. 단순연결리스트 단순연결리스트 (singly linked list) 노드가하나의링크필드에의해서다음노드와연결되는구조를가진연결리스트 연결리스트, 선형연결리스트 (linear linked list), 단순연결선형리스트 (singly linked linear list) 예 ) 12/112

13 2. 단순연결리스트 단순연결리스트의삽입 리스트 week2=( 월, 금, 일 ) 에서원소 월 과 금 사이에새원소 수 삽입하기 1 삽입할새노드를만들공백노드를메모리에서가져와서포인터변수 new 가가리키게한다. 2 new 의데이터필드에 수 를저장한다. 13/112

14 2. 단순연결리스트 단순연결리스트의삽입 3 new 의앞노드, 즉 월 노드의링크필드값을 new 의링크필드에저장한다. week2 100번지 200번지 300번지 100 월 200 금 300 일 null new 번지 수 new 의값 (new 가가리키고있는새노드의주소 ) 을 월 노드의링크필드에저장한다 100번지 200번지 300번지 week2 100 월 150 금 300 일 null 150 번지 new 150 수 /112

15 2. 단순연결리스트 단순연결리스트의삭제 리스트 week2=( 월, 수, 금, 일 ) 에서원소 수 삭제하기 1 삭제할원소의앞노드 ( 선행자 ) 를찾는다. 2 삭제할원소 수 의링크필드값을앞노드의링크필드에저장한다. week2 100번지 200번지 300번지 100 월 번지 수 금일 null 15/112

16 2. 단순연결리스트 자유공간리스트 (free space list) 사용하기전의메모리나사용이끝난메모리를관리의용이성을위해노드로구성하여연결한리스트 16/112

17 2. 단순연결리스트 자유공간리스트에서의노드할당알고리즘 17/112

18 2. 단순연결리스트 자유공간리스트에서의노드할당과정 자유공간리스트 free에서노드를할당할때는항상첫번째노드할당 초기상태 ❶ new Free; 리스트 free의첫번째노드의주소 (Free) 를포인터 new에저장하여포인터 new가할당할노드를가리키게한다. Free 번지 번지 번지 null new /112

19 2. 단순연결리스트 ❷ Free Free.link; 포인터 free에리스트의두번째노드의주소 (Free.link) 를저장 Free 번지 번지 번지 null new 100 이제자유공간리스트 free 의첫번째노드는리스트에서의미적으로분리된상태이므로포인터 new 를반환 (return new;) 해줌으로써새노드를할당 19/112

20 2. 단순연결리스트 자유공간리스트로의노드반환알고리즘 20/112

21 2. 단순연결리스트 자유공간리스트로의노드반환과정 반환되는노드는자유공간리스트 free의첫번째노드로다시삽입 초기상태 ❶ old.link Free; 자유공간리스트 free 의첫번째노드주소 (Free) 를반환할노드포인터 old.link 에저장하여포인터 old 의노드가리스트 free 의첫번째노드를가리키게한다. Free 번지 번지 null 100 번지 old /112

22 2. 단순연결리스트 ❷ Free old; 포인터 old의값즉, 반환할노드의주소 (old) 를포인터 free에저장하여리스트 free의첫번째노드로지정 Free 번지 번지 null old 번지 /112

23 2. 단순연결리스트 단순연결리스트의삽입알고리즘 첫번째노드로삽입하기 23/112

24 2. 단순연결리스트 ❶ new getnode(); 삽입할노드를자유공간리스트에서할당받는다. ❷ new.data x; 새노드의데이터필드에 x 를저장 24/112

25 2. 단순연결리스트 new.link L; 삽입할노드를연결하기위해서리스트의첫번째노드주소 (L) 를삽입할새노드 new 의링크필드 (new.link) 에저장하여, 새노드 new 가리스트의첫번째노드를가리키게한다. L 100번지 200번지 300번지 null 700번지 new 700 x /112

26 2. 단순연결리스트 ❹ L new; 리스트의첫번째노드주소를저장하고있는포인터 L 에, 새노드의주소 new 를저장하여, 포인터 L 이새노드를첫번째노드로가리키도록지정 L new 번지 200번지 300번지 null 700번지 x /112

27 2. 단순연결리스트 중간노드로삽입하기 리스트 L 에서포인터변수 pre 가가리키고있는노드의다음에데이터필드값이 x 인새노드를삽입하는알고리즘 27/112

28 2. 단순연결리스트 ❶<< 리스트 L 이공백리스트인경우 >> ❶-a L new; 리스트포인터 L 에새노드 new 의주소를저장하여, 새노드 new 가리스트의첫번째노드가되도록한다. L 700 new 번지 x ❶-b new.link null; 리스트의마지막노드인 new 의링크필드에 null 을저장하여마지막노드임을표시 L 700 new 700 x 700번지 null 28/112

29 2. 단순연결리스트 ❷<< 리스트 L 이공백리스트가아닌경우 >> ❷-a new.link pre.link; 노드 pre의링크필드값을노드 new의링크필드에저장하여, 새노드 new가노드 pre의다음노드를가리키도록한다. 100 번지 번지 300 번지 L 100 null 300 pre 100 new 번지 x /112

30 2. 단순연결리스트 ❷-b pre.link new; 포인터 new의값을노드 pre의링크필드에저장하여, 노드 pre가새노드 new를다음노드로가리키도록한다. 100 번지 200 번지 300 번지 L null pre 100 new 번지 x /112

31 2. 단순연결리스트 마지막노드로삽입하기 새노드 new 를마지막노드로삽입하는알고리즘 31/112

32 2. 단순연결리스트 ❶<< 리스트 L 이공백리스트인경우 >> [ 알고리즘 5-4] 에서공백리스트에노드를삽입하는연산과같은연산 삽입하는새노드 new 는리스트 L 의첫번째노드이자마지막노드 32/112

33 2. 단순연결리스트 ❷<< 리스트 L 이공백리스트가아닌경우 >> ❷-a temp L; 현재리스트 L 의마지막노드를찾기위해서노드를순회할임시포인터 temp 에리스트의첫번째노드의주소 (L) 를지정 L 번지 번지 300번지 300 null temp /112

34 2. 단순연결리스트 ❷-b while (temp.link null) do temp temp.link; while 반복문을수행하여순회포인터 temp 가노드의링크필드를따라이동하면서링크필드가 null 인마지막노드찾기수행 100 번지 번지 번지 L 100 null temp 100 temp 200 temp /112

35 2. 단순연결리스트 ❷-c temp.link new; 순회포인터 temp 가가리키는노드즉, 리스트의마지막노드의링크필드 (temp.link) 에삽입할새노드 new 의주소를저장하여, 리스트의마지막노드가새노드 new 를연결 L 번지 번지 번지 700 null temp 300 new 번지 x null 35/112

36 2. 단순연결리스트 단순연결리스트의삭제알고리즘 리스트 L 에서포인터 pre 가가리키는노드의다음노드를삭제하는알고리즘 포인터 old : 삭제할노드 36/112

37 2. 단순연결리스트 ❷<< 리스트 L 이공백리스트가아닌경우 >> ❷-a old pre.link; 노드 pre 의다음노드의주소 (pre.link) 를포인터 old 에저장하여, 포인터 old 가다음노드를가리키게한다. L 번지 번지 번지 번지 null pre 200 old /112

38 2. 단순연결리스트 ❷-b if (old = null) then return; 만약노드 pre 가리스트의마지막노드였다면 : 포인터 pre 가가리키는노드가마지막노드인경우에, 2-a old pre.link; 를수행한상태 : L 번지 번지 번지 null pre 300 old null pre.link 의값은 null 이므로포인터 old 의값은 null 이된다. 결국노드 pre 다음에삭제할노드가없다는의미이므로삭제연산을수행하지못하고반환 (return). 38/112

39 2. 단순연결리스트 ❷-c pre.link old.link; 삭제할노드 old 의다음노드 (old.link) 를노드 pre 의다음노드 (pre.link) 로연결 L 번지 번지 번지 번지 null pre 200 old 300 ❷-d returnnode(old); 삭제한노드 old 를자유공간리스트에반환 39/112

40 2. 단순연결리스트 단순연결리스트의노드탐색알고리즘 리스트의노드를처음부터하나씩순회하면서노드의데이터필드의값과 x 를비교하여일치하는노드를찾는연산 40/112

41 2. 단순연결리스트 : 예제 5-1(1) 001 #include <stdio.h> 002 #include <stdlib.h> 003 #include <string.h> typedef struct ListNode{ // 단순연결리스트의노드구조정의 006 char data[10]; 007 struct ListNode* link; 008 } listnode; typedef struct{ // 리스트의헤드노드의구조정의 011 listnode* head; 012 } linkedlist_h; linkedlist_h* createlinkedlist_h(void); // 함수원형선언 015 void freelinkedlist_h(linkedlist_h*); 016 void addlastnode(linkedlist_h*, char*); 017 void reverse(linkedlist_h*); 018 void deletelastnode(linkedlist_h*); 019 void printlist(linkedlist_h*); 41/112

42 2. 단순연결리스트 : 예제 5-1(2) 022 linkedlist_h* createlinkedlist_h(void){ // 공백연결리스트생성연산 023 linkedlist_h* L; 024 L = (linkedlist_h*)malloc(sizeof(linkedlist_h)); // 헤드노드할당 025 L -> head = NULL; // 공백리스트이므로 NULL 설정 026 return L; 027 } void addlastnode(linkedlist_h* L, char* x){ // 리스트의마지막노드삽입연산 030 listnode* newnode; 031 listnode* p; 032 newnode = (listnode*)malloc(sizeof(listnode)); // 삽입할새노드할당 033 strcpy(newnode->data, x); // 새노드의데이터필드에 x 저장 034 newnode->link= NULL; 035 if (L->head == NULL){ // 현재리스트가공백인경우 : 036 L->head = newnode; 037 return; 038 } 039 p = L->head; 040 while (p->link!= NULL) p = p->link; 041 p ->link = newnode; 042 } 42/112

43 2. 단순연결리스트 : 예제 5-1(3) 044 void reverse(linkedlist_h * L){ // 리스트의노드순서를역순으로바꾸는연산 045 listnode* p; 046 listnode* q; 047 listnode* r; p = L->head; 050 q=null; 051 r=null; while (p!= NULL){ // 노드의연결을반대로바꾸기 054 r = q; 055 q = p; 056 p = p->link; 057 q->link = r; 058 } 059 L->head = q; } 43/112

44 2. 단순연결리스트 : 예제 5-1(4) 063 void deletelastnode(linkedlist_h * L){ // 리스트의마지막노드삭제연산 064 listnode* previous; 065 listnode* current; 066 if (L->head == NULL) return; // 공백리스트인경우, 삭제연산중단 067 if (L->head->link == NULL) { // 리스트에노드가한개만있는경우 068 free(l->head); // 첫번째노드의메모리를해제 069 L->head = NULL; // 리스트시작포인터를 null로설정 070 return; 071 } 072 else { // 리스트에노드가여러개있는경우 073 previous = L->head; 074 current = L->head->link; 075 while(current ->link!= NULL){ 076 previous = current; 077 current = current->link; 078 } 079 free(current); 080 previous->link = NULL; 081 } 082 } 44/112

45 2. 단순연결리스트 : 예제 5-1(5) 084 void freelinkedlist_h(linkedlist_h* L){ // 리스트전체메모리해제연산 085 listnode* p; 086 while(l->head!= NULL){ 087 p = L->head; 088 L->head = L->head->link; 089 free(p); 090 p=null; 091 } 092 } void printlist(linkedlist_h* L){ // 노드순서대로리스트를출력하는연산 095 listnode* p; 096 printf("l = ("); 097 p= L->head; 098 while(p!= NULL){ 099 printf("%s", p->data); 100 p = p->link; 101 if(p!= NULL) printf(", "); 102 } 103 printf( ) \n ); 104 } 45/112

46 2. 단순연결리스트 : 예제 5-1(6) 107 int main(){ 108 linkedlist_h* L; 109 L = createlinkedlist_h(); 110 printf("(1) 공백리스트생성하기! \n"); 111 printlist(l); getchar(); printf("(2) 리스트에 3개의노드추가하기! \n"); 114 addlastnode(l, " 월 "); 115 addlastnode(l, " 수 "); 116 addlastnode(l, " 금 "); 117 printlist(l); getchar(); printf("(3) 리스트마지막에노드한개추가하기! \n"); 120 addlastnode(l, " 일 "); 121 printlist(l); getchar(); /112

47 2. 단순연결리스트 : 예제 5-1(7) 123 printf("(4) 마지막노드삭제하기! \n"); 124 deletelastnode(l); 125 printlist(l); getchar(); printf("(5) 리스트원소를역순으로변환하기! \n"); 128 reverse(l); 129 printlist(l); getchar(); printf("(6) 리스트공간을해제하여, 공백리스트상태로만들기! \n"); 132 freelinkedlist_h(l); 133 printlist(l); getchar(); 136 return 0; 137 } 47/112

48 2. 단순연결리스트 실행결과 48/112

49 3. 원형연결리스트 원형연결리스트 (circular linked list) 단순연결리스트에서마지막노드가리스트의첫번째노드를가리키게하여리스트의구조를원형으로만든연결리스트 단순연결리스트의마지막노드의링크필드에첫번째노드의주소를저장하여구성 링크를따라계속순회하면이전노드에접근가능 100번지 200번지 300번지 L null 49/112

50 3. 원형연결리스트 선형기차놀이와원형기차놀이비교 50/112

51 3. 원형연결리스트 원형연결리스트의삽입연산 마지막노드의링크를첫번째노드로연결하는부분만제외하고는단순연결리스트에서의삽입연산과같은연산 51/112

52 3. 원형연결리스트 첫번째노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를삽입하는알고리즘 52/112

53 3. 원형연결리스트 ❶<< 원형리스트가공백리스트인경우 >> 삽입하는노드 new 는리스트의첫번째노드이자마지막노드가되어야함 ❶-a CL new; 포인터 CL 이노드 new 를가리키게한다. CL new 번지 x 53/112

54 3. 원형연결리스트 ❶-b new.link new; 노드 new가자기자신을가리키게함으로써노드 new를첫번째노드이자마지막노드가되도록지정한다. CL new 번지 700 x /112

55 3. 원형연결리스트 ❷<< 원형리스트가공백리스트가아닌경우 >> ❷-a temp CL; 리스트가공백리스트가아닌경우에는첫번째노드의주소를임시순회포인터 temp 에저장하여노드순회의시작점을지정한다. CL 번지 번지 번지 temp ❷-b while (temp.link CL) do temp temp.link; while 반복문을수행하여순회포인터 temp 를링크를따라마지막노드까지이동 100번지 200번지 CL 번지 temp 200 temp 300 temp 55/112

56 3. 원형연결리스트 ❷-c new.link temp.link; 리스트의마지막노드의링크값을노드 new 의링크에저장하여, 노드 new 가노드 temp 의다음노드를가리키게한다. 리스트 CL 은원형연결리스트이므로마지막노드의다음노드는리스트의첫번째노드가된다. 100 번지 200 번지 300 번지 CL 번지 new 700 x temp ❷-d temp.link new; 포인터 new 의값을포인터 temp 가가리키고있는마지막노드의링크에저장하여, 리스트의마지막노드가노드 new 를가리키게한다. 100번지 200번지 CL 번지 new 번지 x temp /112

57 3. 원형연결리스트 ❷-e CL new; 노드 new 의값을리스트포인터 CL 에저장하여노드 new 가리스트의첫번째노드가되도록지정 CL 번지 번지 번지 700 new 번지 x temp 알고리즘 5-8 실행결과 57/112

58 3. 원형연결리스트 중간노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를포인터 pre 가가리키는노드의다음노드로삽입하는알고리즘 58/112

59 3. 원형연결리스트 ❶<< 원형연결리스트 CL 이공백리스트인경우 >> [ 알고리즘 5-8] 에서공백리스트에첫번째노드를삽입하는연산과같음 ❷<< 원형연결리스트 CL 이공백리스트가아닌경우 >> 59/112

60 3. 원형연결리스트 ❷-a new.link pre.link; 노드 pre 의다음노드로 new 를삽입하기위해서, 먼저노드 pre 의다음노드 (pre.link) 를 new 의다음노드 (new.link) 로연결 CL 번지 번지 번지 번지 100 pre 200 new 번지 x /112

61 3. 원형연결리스트 ❷-b pre.link new; 노드 new의값 ( 삽입할노드의주소 ) 을노드 pre의링크에저장하여, 노드 pre가노드 new를가리키도록한다. CL 번지 번지 300 번지 번지 100 pre 200 new 번지 x /112

62 3. 원형연결리스트 원형연결리스트의삭제연산 원형연결리스트 CL 에서포인터 pre 가가리키는노드의다음노드를삭제하고삭제한노드는자유공간리스트에반환하는연산 포인터 old 는삭제할노드지시 62/112

63 3. 원형연결리스트 ❶ old pre.link; 노드 pre 의다음노드 (pre.link) 를삭제할노드 old 로지정 CL 번지 번지 300 번지 번지 100 pre 200 old 300 ❷ pre.link old.link; old 의다음노드 (old.link) 를노드 old 의이전노드 pre 노드와서로연결 CL 번지 200번지 300번지 400번지 pre 200 old 300 ❹ returnnode(old); 63/112

64 3. 원형연결리스트 ❸<< 삭제할노드 old 가원형연결리스트의첫번째노드인경우 >> ❸-a CL old.link; 첫번째노드를삭제하는경우에는노드 old 의링크값을리스트포인터 CL 에저장하여두번째노드가리스트의첫번째노드가되도록조정 CL 번지 번지 번지 번지 200 old 100 ❹ returnnode(old); pre /112

65 4. 이중연결리스트 이중연결리스트 (doubly linked list) 양쪽방향으로순회할수있도록노드를연결한리스트 이중연결리스트의노드구조 두개의링크필드와한개의데이터필드로구성 llink(left link) 필드 : 왼쪽노드와연결하는포인터 rlink(right link) 필드 : 오른쪽노드와연결하는포인터 노드구조에대한구조체정의 typedef struct Dnode{ struct Dnode *llink; char data[5]; struct Dnode *rlink; } ; 65/112

66 4. 이중연결리스트 66/112

67 4. 이중연결리스트 리스트 week=( 월, 수, 금 ) 의이중연결리스트구성 원형이중연결리스트 이중연결리스트를원형으로구성 67/112

68 4. 이중연결리스트 68/112

69 4. 이중연결리스트 69/112

70 4. 이중연결리스트 70/112

71 4. 이중연결리스트 71/112

72 4. 이중연결리스트 72/112

73 4. 이중연결리스트 73/112

74 4. 이중연결리스트 이중연결리스트에서의삽입연산 이중연결리스트에서의삽입연산과정 ❶ 삽입할노드를가져온다. ❷ 새노드의데이터필드에값을저장한다. ❸ 새노드의왼쪽노드 (new.llink) 의오른쪽링크 (rlink) 를 새노드의오른쪽링크 (rlink) 에저장한다. ❹ 그리고왼쪽노드의오른쪽링크 (rlink) 에새노드의주소를 저장한다. ❺ 새노드의오른쪽노드 (new.rlink) 의왼쪽링크 (llink) 를 새노드의왼쪽링크 (llink) 에저장한다. ❻ 그리고오른쪽노드의왼쪽링크 (llink) 에새노드의주소를 저장한다. 74/112

75 4. 이중연결리스트 이중연결리스트에서의삽입알고리즘 75/112

76 4. 이중연결리스트 이중연결리스트 DL 에서포인터 pre 가가리키는노드의다음노드로노드 new 를삽입하는과정 76/112

77 4. 이중연결리스트 ❶ new.rlink pre.rlink ; 노드 pre 의 rlink 를노드 new 의 rlink 에저장하여, 노드 pre 의오른쪽노드를삽입할노드 new 의오른쪽노드로연결 77/112

78 4. 이중연결리스트 ❷ pre.rlink new; 새노드 new 의주소를노드 pre 의 rlink 에저장하여, 노드 new 를노드 pre 의오른쪽노드로연결 78/112

79 4. 이중연결리스트 ❸ new.llink pre; 포인터 pre 의값을삽입할노드 new 의 llink 에저장하여, 노드 pre 를노드 new 의왼쪽노드로연결 79/112

80 4. 이중연결리스트 ❹ new.rlink.llink new; 포인터 new 의값을노드 new 의오른쪽노드 (new.rlink) 의 llink 에저장하여, 노드 new 의오른쪽노드의왼쪽노드로노드 new 를연결 80/112

81 4. 이중연결리스트 : 양방향기차사람나가기 81/112

82 4. 이중연결리스트 : 양방향기차사람나가기 82/112

83 4. 이중연결리스트 이중연결리스트에서의삭제연산 이중연결리스트에서의삭제연산과정 ❶ 삭제할노드의오른쪽노드의주소 (old.rlink) 를 삭제할노드의왼쪽노드 (old.llink) 의오른쪽링크 (rlink) 에저장한다. ❷ 삭제할노드의왼쪽노드의주소 (old.llink) 를 삭제할노드의오른쪽노드 (old.rlink) 의왼쪽링크 (llink) 에저장한다. ❸ 삭제한노드를자유공간리스트에반환한다. 83/112

84 4. 이중연결리스트 이중연결리스트에서의삭제알고리즘 84/112

85 4. 이중연결리스트 이중연결리스트 DL 에서포인터 old 가가리키는노드를삭제하는과정 초기상태 85/112

86 4. 이중연결리스트 ❶ old.llink.rlink old.rlink; 삭제할노드 old 의오른쪽노드의주소를노드 old 의왼쪽노드의 rlink 에저장하여, 노드 old 의오른쪽노드를노드 old 의왼쪽노드의오른쪽노드로연결 86/112

87 4. 이중연결리스트 ❷ old.rlink.llink old.llink; 삭제할노드 old 의왼쪽노드의주소를노드 old 의오른쪽노드의 llink 에저장하여, 노드 old 의왼쪽노드를노드 old 의오른쪽노드의왼쪽노드로연결 87/112

88 4. 이중연결리스트 ❸ returnnode(old); 삭제된노드 old 는자유공간리스트에반환 88/112

89 5. 다항식의연결자료구조표현 다항식의연결자료구조표현 단순연결리스트를이용하여다항식표현 다항식의항 : 단순연결리스트의노드 노드구조 각항에대해서계수와지수를저장 계수를저장하는 coef 와지수를저장하는 expo 의두개의필드로구성 링크필드 : 다음항을연결하는포인터로구성 노드에대한구조체정의 typedef struct Node { float coef; int expo; struct Node *link; }; 89/112

90 5. 다항식의연결자료구조표현 다항식의단순연결리스트표현예 다항식 A(x)=4x 3 +3x 2 +5x 다항식 B(x)=3x 4 +x 3 +2x+1 90/112

91 5. 다항식의연결자료구조표현 다항식연결자료구조의삽입연산 다항식에항을추가하는알고리즘 다항식리스트포인터 PL 과 coef 필드값을저장한변수 coef, expo 필드값을저장한변수 expo, 리스트 PL 의마지막노드의위치를지시하는포인터 last 를매개변수로사용 91/112

92 5. 다항식의연결자료구조표현 ❶<< 공백다항식에서의항삽입연산 > > 초기상태 ❶-a PL new; 포인터 new 의값을리스트포인터 PL 에저장하여, 노드 new 가리스트 PL 의첫번째노드가되도록연결 92/112

93 5. 다항식의연결자료구조표현 ❶-b last new; 포인터 new의값을포인터 last에저장하여, 포인터 last가리스트 PL의마지막노드인노드 new를가리키도록지정 93/112

94 5. 다항식의연결자료구조표현 ❷<< 다항식에서의항삽입연산 >> 초기상태 ❷-a last.link new; 포인터 new의값을노드 last의링크에저장하여, 노드 new를노드 last의다음노드로연결 94/112

95 5. 다항식의연결자료구조표현 ❷-b last new; 포인터 new 의값을포인터 last 에저장하여, 노드 new 를리스트 PL 의마지막노드로지정 95/112

96 5. 다항식의연결자료구조표현 다항식리스트 A 에 appendterm() 알고리즘을사용하여 2x 0 항 ( 상수항 2) 추가예 96/112

97 5. 다항식의연결자료구조표현 다항식의덧셈연산 덧셈 A +B =C 를단순연결리스트자료구조를사용하여연산 다항식 A 와 B, C 의항을지시하기위해서세개의포인터를사용 포인터 p : 다항식 A 에서비교할항을지시 포인터 q : 다항식 B 에서비교할항을지시 포인터 r : 덧셈연산결과만들어지는다항식 C 의항을지시 97/112

98 5. 다항식의연결자료구조표현 p.expo < q.expo : 다항식 B 항의지수가큰경우 포인터 q가가리키는다항식 B 의항을 C 의항으로복사 q가가리키는항에대한처리가끝났으므로 q를다음노드로이동 98/112

99 5. 다항식의연결자료구조표현 p.expo = q.expo : 두항의지수가같은경우 p.coef 와 q.coef 를더하여 C 의항, 즉 r.coef 에저장하고지수가같으므로 p.expo( 또는 q.expo) 를 r.expo 에저장 다음항을비교하기위해포인터 p 와 q 를각각다음노드로이동 99/112

100 5. 다항식의연결자료구조표현 p.expo > q.expo : 다항식 A 항의지수가큰경우 포인터 p가가리키는다항식 A 의항을 C 의항으로복사 p가가리키는항에대한처리가끝났으므로 p를다음노드로이동 100/112

101 5. 다항식의연결자료구조표현 다항식의덧셈알고리즘 >> 계속 101/112

102 5. 다항식의연결자료구조표현 102/112

103 5. 다항식의연결자료구조표현 다항식의덧셈예 ) A(x)=4x 3 +3x 2 +5x B(x)=3x 4 +x 3 +2x+1 초기상태 103/112

104 5. 다항식의연결자료구조표현 14x 3 항과 3x 4 항에대한처리 p.expo < q.expo 이므로지수가큰 q 노드를리스트 C 에복사 포인터 q 는다음노드로이동 104/112

105 5. 다항식의연결자료구조표현 24x 3 항과 1x 3 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드 (5x 3 항 ) 를리스트 C에추가 포인터 p와 q는다음노드로이동 105/112

106 5. 다항식의연결자료구조표현 33x 2 항과 2x 1 항에대한처리 p.expo > q.expo 이므로지수가큰 p 노드를리스트 C에복사 포인터 p는다음노드로이동 106/112

107 5. 다항식의연결자료구조표현 45x 1 항과 2x 1 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드 (7x 1 항 ) 를리스트 C 에추가 포인터 p 와 q 는다음노드로이동 107/112

108 5. 다항식의연결자료구조표현 5 B(x) 의남은항에대한처리 포인터 p가 null이므로다항식 A 의항에대한처리끝 처리할항이남아있는다항식 B 의포인터 q는 null이될때까지모든노드를복사하여리스트 C에추가 108/112

109 5. 다항식의연결자료구조표현 실행결과 > 109/112

110 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입