C언어 응용 제 6 주 연결 자료구조

다음 주 과제 6장 읽어오기 숙제 해서 제출하기

제 5장 연결 자료구조 연결 자료구조 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 다항식의 연결 자료구조 표현

연결 자료구조를 이해한다. 순차 자료구조와 연결 자료구조의 차이와 장단점 을 알아본다. 연결 리스트의 종류와 특징을 알아본다. 연결 자료구조를 이용한 다항식의 덧셈 연산 방법 을 알아본다.

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

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

노드 원소, 주소의 구조 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조 데이터 필드(data field) 원소의 값을 저장 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성 링크 필드(link field) 다음 노드의 주소를 저장 포인터 변수를 사용하여 주소값을 저장 [그림 5-2] 노드에 대한 논리적 구조

노드 연결 방법에 대한 이해 - 기차놀이 이름표 뽑기 자기가 뽑은 이름의 사람을 찾아서 연결하기 : 희진→삼식 →삼순 X 표를 뽑은 사람은 마지막 기차 기차는 이름표를 들고 있는 방향으로 움직인다. [그림 5-3] 기차놀이_이름표 뽑기 [그림 5-4] 기차놀이_뽑은 이름표대로 기차 연결하기

노드 연결 방법에 대한 이해 - 기차놀이 기차놀이와 연결 리스트 기차놀이 하는 아이들 : 연결리스트의 노드 이름표 : 노드의 링크 필드 [그림 5-5] 기차놀이에 대한 노드 표현

선형 리스트와 연결 리스트의 비교 리스트 week=(월, 화, 수, 목, 금, 토, 일) week에 대한 선형 리스트

리스트 week=(월, 화, 수, 목, 금, 토, 일) week에 대한 연결 리스트

리스트 이름 week - 연결 리스트의 시작을 가리키는 포인터변수 연결 리스트의 마지막 노드의 링크필드 - 노드의 끝을 표시하기 위해서 null(널) 저장 공백 연결 리스트 - 포인터변수 week에 null을 저장 (널 포인터) 각 노드의 필드에 저장한 값은 포인터의 점 연산자를 사용하여 액세스 week.data : 포인터 week가 가리키는 노드의 데이터 필드 값 “월” week.link : 포인터 week가 가리키는 노드의 링크 필드에 저장된 주소값 리스트 week의 노드에 대한 C 프로그램 구조체 정의 typedef struct tag_Node{ char data[4]; struct tag_Node* link; }Node ; [그림 5-8] 공백 연결 리스트

단순연결 리스트에서의 삽인 연산 ①기차놀이에 헨리를 끼워주기로 하자. 그러려면 먼저 헨리를 데려와야 한다. ②헨리를 희진이와 삼식이 사이에 끼워주기로 하자. 먼저 헨리의 앞사람이 될 희진이가 가지고 있는 이름표를 받아온다. ①기차놀이에 헨리를 끼워주기로 하자. 그러려면 먼저 헨리를 데려와야 한다. [그림 5-9] 기차놀이에 사람 추가하기_헨리 불러오기 [그림 5-10] 기차놀이에 사람 추가하기_앞사람에게서 이름표 받아오기

④ 이제 이름표대로 연결하여 기차를 완성하면 [희진-헨리-삼식-삼순]의 기차가 된다. ③ 그 대신 희진에게는 헨리 이름이 적힌 이름표를 준다. [그림 5-11] 기차놀이에 사람 추가하기 _앞사람에게 자기 이름표 주기 [그림 5-12] 기차놀이에 사람 추가하기_완성

단순 연결 리스트에 노드를 삽입하는 방법 리스트 week2=(월, 금, 일)에서 원소 “월”과 “금”사이에 새 원소“수” 삽입하기 ① 삽입할 새 노드를 만들 공백 노드를 메모리에서 가져와서 포인터 변수 new가 가리키게 한다. ②new의 데이터 필드에“수”를 저장한다. [그림 5-13] 단순 연결 리스트 week2 [그림 5-14] 단순 연결 리스트 week2_공백 노드 준비 [그림 5-15] 단순 연결 리스트 week2_새 노드의 데이터 필드 값 저장

③ new의 앞 노드, 즉“월”노드의 링크 필드 값을 new의 링크 필드에 저장한다. [그림 5-16] 단순 연결 리스트 week2_새 노드의 링크 값 지정 [그림 5-17] 단순 연결 리스트 week2_리스트에 새 노드 연결

단순 연결 리스트에서의 삭제 연산 기차놀이를 하던 헨리가 그만 놀고 집에 가겠다고 한다. ① 헨리는 자기 이름표를 가지고 있는 사람, 즉 헨리의 앞사람인 희진이에게 자기가 가지고 있던 이름표를 넘겨준다. ② 헨리의 앞사람인 희진이가‘삼식’이름표를 넘겨받았으므로 이제 희진이는 삼식이와 연결되어 기차놀이를 하게 된다. [그림 5-18] 기차놀이에서 빠지기 _앞사람에게 이름표 넘겨주기 [그림 5-19] 기차놀이에서 빠지기_나머지 사람들끼리 기차놀이 계속하기

단순 연결 리스트에서의 삭제 연산 단순 연결 리스트 week2=(월,수,금,일)에서 원소“수”를 삭제할 경우에는 다음의 단계를 수행한다. ① 삭제할 노드의 앞 노드(선행자)를 찾는다. ② 앞 노드의 링크 필드에 삭제할 노드의 링크 필드값을 저장한다. [그림 5-20] 리스트 week2에서 노드 삭제하기_앞 노드 찾기 [그림 5-21] 리스트 week2에서 노드 삭제하기_앞 노드에 링크 필드값 저장

자유 공간 리스트(free space list) 사용하기 전의 메모리나 사용이 끝난 메모리를 관리하기 위해 노드로 구성하여 연결한 리스트 [그림 5-22] 자유 공간 리스트 [그림 5-23] 자유 공간 리스트 free의 논리적 노드 구조

자유 공간 리스트에서의 노드 할당 알고리즘 getNode() if (Free = null) then             underflow();         // 언더플로우 처리 루틴        new ← Free;             // ①        Free ← Free.link;      // ②        return  new;              end getNode()

자유 공간 리스트에서의 노드 할당 과정 자유공간 리스트 free에서 노드를 할당할 때는 항상 첫 번째 노드 할당 초기 상태 ① new ← Free; 리스트 free의 첫 번째 노드의 주소를 포인터 new에 저장하여 포인터 new가 할당할 노드를 가리키게 한다. [그림 5-24] getNode( ) 함수 수행 과정_초기 상태 [그림 5-25] getNode( ) 함수 수행 과정_알고리즘 설명 ❶

자유 공간 리스트로의 노드 반환 알고리즘 ② Free ← Free.link; 이제 자유공간 리스트 free의 첫 번째 노드는 리스트에서 의미적으로 분리된 상태이므로 포인터 new를 반환(return new;)해줌으로써 새 노드를 할당 자유 공간 리스트로의 노드 반환 알고리즘 [그림 5-26] getNode( ) 함수 수행 과정_알고리즘 설명 ❷ returnNode(old)        old.link ← Free; // ①        Free ← old;      // ② end returnNode()

자유 공간 리스트로의 노드 반환 과정 반환되는 노드는 자유공간 리스트 free의 첫 번째 노드로 다시 삽입 초기 상태 ① old.link ← Free; 자유 공간리스트 free의 첫 번째 노드주소를 반환할 노드 포인터 old.link에 저장하여 포인터 old의 노드가 리스트 free의 첫 번째 노드를 가리키게 한다. [그림 5-27] returnNode( ) 함수 수행 과정_초기 상태 [그림 5-28] returnNode( ) 함수 수행 과정_알고리즘 설명 ❶

② Free ← old; 포인터 old의 값 즉, 반환할 노드의 주소를 포인터 free에 저장하여 리스트 free의 첫 번째 노드로 지정 [그림 5-29] returnNode( ) 함수 수행 과정_알고리즘 설명 ❷

단순 연결 리스트의 삽입 알고리즘 첫 번째 노드로 삽입하기 insertFirstNode(L, x) ① new ← getNode( ); 삽입할 노드를 자유 공간리스트에서 할당 받는다. insertFirstNode(L, x)               new ← getNode(); // ①               new.data ← x;     // ②               new.link ← L;     // ③               L ← new;         // ④ end insertFirstNode() [그림 5-30] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❶

② new.data ← x; ③ new.link ← L; 새 노드의 데이터 필드에 x를 저장 삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소를 삽입할 새 노드 new의 링크 필드에 저장하여, 새 노드 new가 리스트의 첫 번째 노드를 가리키게 한다. [그림 5-31] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷ [그림 5-32] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❸

④ L ← new; 리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에, 새 노드의 주소를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정 [그림 5-33] insertFirstNode( ) 함수 수행 과정_알고리즘 설명❹

중간 노드로 삽입하기 리스트 L에서 포인터변수 pre가 가리키고 있는 노드의 다음에 데이터 필드 값이 x인 새 노드를 삽입하는 알고리즘 insertMiddleNode(L, pre, x)                                    new ← getNode();                    new.data ← x;                    if (L=null) then {                // ①                          L ← new;               // ①-ⓐ                          new.link ← null;      // ①-ⓑ               }                          else {                               // ②                          new.link ← pre.link;  // ②-ⓐ                            pre.link ← new;        // ②-ⓑ               } end insertMiddleNode()

리스트 L이 공백 리스트인 경우 ① L ← new; ② new.link ← null; 리스트의 마지막 노드인 new의 링크 필드에 null을 저장하여 마지막 노드임을 표시 [그림 5-34] insertMiddleNode( ) 함수 수행 과정 _초기 상태 [그림 5-35] insertMiddleNode( ) 함수 수행 과정 _알고리즘 ❶-ⓐ [그림 5-36] insertMiddleNode( ) 함수 수행 과정 _알고리즘 ❶-ⓑ

리스트 L이 공백 리스트가 아닌 경우 ① new.link ← pre.link; 노드 pre의 링크 필드 값을 노드 new의 링크 필드에 저장하여, 새 노드 new가 노드 pre의 다음 노드를 가리키도록 한다. [그림 5-37] insertMiddleNode( ) 함수 수행 과정_초기 상태 [그림 5-38] insertMiddleNode( ) 함수 수행 과정_알고리즘 ❷-ⓐ

② pre.link ← new; 포인터 new의 값을 노드 pre의 링크 필드에 저장하여, 노드 pre가 새 노드 new를 다음 노드로 가리키도록 한다. [그림 5-39] insertMiddleNode( ) 함수 수행 과정_알고리즘 ❷-ⓑ

마지막 노드로 삽입하기 새 노드 new를 마지막 노드로 삽입하는 알고리즘 insertLastNode(L, x)           new ← getNode();               new.data ← x;           new.link ← null;           if (L = null) then {              // ①                L ← new;                return;           }                               // ②           temp ← L;                        // ②-ⓐ            while (temp.link ≠ null) do                   temp ← temp.link;           // ②-ⓑ           temp.link ← new;                 // ②-ⓒ end insertLastNode()

리스트 L이 공백 리스트인 경우 [알고리즘 5-4]에서 공백리스트에 노드를 삽입하는 연산과 같은 연산 삽입하는 새 노드 new는 리스트 L의 첫 번째 노드이자 마지막 노드 [그림 5-40] insertLastNode( ) 함수 수행 과정_초기 상태

② while (temp.link ≠ null) do temp ← temp.link; 현재 리스트 L의 마지막 노드를 찾기 위해 노드를 순회할 임시포인터 temp에 리스트의 첫 번째 노드의 주소를 지정 ② while (temp.link ≠ null) do                 temp ← temp.link;  while 반복문을 수행하여 순회포인터 temp가 노드의 링크 필드를 따라 이동하면서 링크 필드가 null인 마지막 노드 찾기 수행 [그림 5-41] insertLastNode( ) 함수 수행 과정_알고리즘 ❷-ⓐ [그림 5-42] insertLastNode( ) 함수 수행 과정_알고리즘 ❷-ⓑ

③ temp.link ← new; 순회포인터 temp가 가리키는 노드 즉, 리스트의 마지막 노드의 링크 필드에 삽입할 새 노드 new의 주소를 저장하여, 리스트의 마지막 노드가 새 노드 new를 연결 [그림 5-43] insertLastNode( ) 함수 수행 과정_알고리즘 ❷-ⓒ

단순 연결 리스트의 삭제 알고리즘 리스트 L에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하는 알고리즘 포인터 old : 삭제할 노드 deleteNode(L, pre)           if (L = null) then error;              // ①           else {                                // ②                  old ← pre.link;                // ②-ⓐ                  if (old = null) then return;    // ②-ⓑ                  pre.link ← old.link;           // ②-ⓒ           }           returnNode(old);                       // ②-ⓓ end deleteNode() 

리스트 L이 공백 리스트가 아닌 경우 ① old ← pre.link; 노드 pre의 다음노드의 주소를 포인터 old에 저장하여, 포인터 old가 다음 노드를 가리키게 한다. [그림 5-44] deleteNode( ) 함수 수행 과정_초기 상태 [그림 5-45] deleteNode( ) 함수 수행 과정_알고리즘 ❷-ⓐ

② if (old = null) then return; 만약 노드 pre가 리스트의 마지막 노드 였 다면 : pre.link의 값은 null이므로 포인터 old의 값은 null이 된다. 결국 노드 pre 다음의 삭제할 노드가 없다는 의미이므로 삭제연산을 수행하지 못하고 반환(return). [그림 5-46] deleteNode( ) 함수 수행 과정_알고리즘 ❷-ⓑ

③ pre.link ← old.link; ④ returnNode(old); 삭제할 노드 old의 다음 노드(old.link)를 노드 pre의 다음 노드(pre.link)로 연결 ④ returnNode(old); 삭제한 노드 old를 자유 공간리스트에 반환 [그림 5-47] deleteNode( ) 함수 수행 과정_알고리즘 ❷-ⓒ [그림 5-48] deleteNode( ) 함수 수행 과정_알고리즘 ❷-ⓓ

단순 연결 리스트의 노드 탐색 알고리즘 리스트의 노드를 처음부터 하나씩 순회하면서 노드의 데이터 필드의 값과 x를 비교하여 일치하는 노드를 찾는 연산 searchNode(L, x)          temp ← L;                      // ①          while (temp ≠ null) do {                    if (temp.data = x ) then  return temp;    // ②              temp ← temp.link;          }          return temp;                    // ③ end searchNode()

단순 연결 리스트 구현 프로그램 001 #include <stdio.h> 002 #include <stdlib.h> 003 #include <string.h> 004 005 typedef struct ListNode{ 006 char data[10]; 007 struct ListNode* link; 008 } listNode; 009 010 typedef struct{ 011 listNode* head; 012 } linkedList_h; 013 014 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*); 020 021 022 linkedList_h* createLinkedList_h(void){ 023 linkedList_h* L; 024 L = (linkedList_h*)malloc(sizeof(linkedList_h)); 025 L -> head = NULL; 026 return L; 027 } 028 029 void addLastNode(linkedList_h* L, char* x){ 030 listNode* newNode; 031 listNode* p; 032 newNode = (listNode*)malloc(sizeof(listNode)); 033 strcpy(newNode->data, x);

단순 연결 리스트 구현 프로그램 034 newNode->link= NULL; 051 p = L->head; 035 if (L->head == NULL){ 036 L->head = newNode; 037 return; 038 } 039 p = L->head; 040 while (p->link != NULL) { 041 p = p->link; 042 } 043 p ->link = newNode; 044 } 045 046 void reverse(linkedList_h * L){ 047 listNode* p; 048 listNode* q; 049 listNode* r; 050 051 p = L->head; 052 q=NULL; 053 r=NULL; 054 055 while (p!= NULL){ 056 r = q; 057 q = p; 058 p = p->link; 059 q->link = r; 060 } 061 L->head = q; 062 063 } 064 065 void deleteLastNode(linkedList_h * L){ 066 listNode* previous; 067 listNode* current; 068 if (L->head == NULL) return;

단순 연결 리스트 구현 프로그램 069 if (L->head->link == NULL) { 070 free(L->head); 071 L->head = NULL; 072 return; 073 } 074 else { 075 previous = L->head; 076 current = L->head->link; 077 while(current ->link != NULL){ 078 previous = current; 079 current = current->link; 080 } 081 free(current); 082 previous->link = NULL; 083 } 084 } 085 086 void freeLinkedList_h(linkedList_h* L){ 087 listNode* p; 088 while(L->head != NULL){ 089 p = L->head; 090 L->head = L->head->link; 091 free(p); 092 p=NULL; 093 } 094 } 095 096 097 void printList(linkedList_h* L){ 098 listNode* p; 099 printf("L = ("); 100 p= L->head; 101 while(p != NULL){ 102 printf("%s", p->data); 103 p = p->link;

단순 연결 리스트 구현 프로그램 104 if(p != NULL){ 122 printList(L); getchar(); 105 printf(", "); 106 } 107 } 108 printf(") \n"); 109 } 110 111 112 int main(){ 113 linkedList_h* L; 114 L = createLinkedList_h(); 115 printf("(1) 공백 리스트 생성하기! \n"); 116 printList(L); getchar(); 117 118 printf("(2) 리스트에 3개의 노드 추가하기! \n"); 119 addLastNode(L, "월"); 120 addLastNode(L, "수"); 121 addLastNode(L, "금"); 122 printList(L); getchar(); 123 124 printf("(3) 리스트 마지막에 노드 한개 추가하기! \n"); 125 addLastNode(L, "일"); 126 printList(L); getchar(); 127 128 printf("(4) 마지막 노드 삭제하기! \n"); 129 deleteLastNode(L); 130 printList(L); getchar(); 131 132 printf("(5) 리스트 원소를 역순으로 변환하기! \n"); 133 reverse(L); 134 printList(L); getchar(); 135 136 printf("(6) 리스트 공간을 해제하여, 공백 리스트 상태로 만들기! \n"); 137 freeLinkedList_h(L); 138 printList(L);

단순 연결 리스트 구현 프로그램 실행 결과 139 140 getchar(); 141 return 0; 142 }

원형 연결 리스트(circular linked list) 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성 링크를 따라 계속 순회하면 이전 노드에 접근 가능 [그림 5-49] 원형 연결 리스트 [그림 5-50] 원형 기차놀이

원형 연결 리스트의 삽입 연산 마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 제외하고는 단순 연결 리스트에서의 삽입 연산과 같은 연산 첫 번째 노드로 삽입하기 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 삽입하는 알고리즘 insertFirstNode(CL, x)           new ← getNode();               new.data ← x;                    if (CL = null) then {         // ① 공백 원형연결리스트인 경우                CL ← new;                // ①-ⓐ                new.link ← new;        // ①-ⓑ           }                                        temp ← CL;                    // ②            while (temp.link ≠ CL) do     // ③ 마지막 노드까지 temp포인터 이동                temp ← temp.link;                          new.link ← temp.link;         // ④           temp.link ← new;              // ⑤           CL ← new;                     // ⑥ end insertFirstNode()                   

원형리스트가 공백 리스트인 경우 ① CL ← new; ② new.link ← new; [그림 5-51] insertFirstNode( ) 함수 수행 과정_초기 상태 [그림 5-52] insertFirstNode( ) 함수 수행 과정 _알고리즘 설명 ❶-ⓐ [그림 5-53] insertFirstNode( ) 함수 수행 과정 _알고리즘 설명 ❶-ⓑ

② while (temp.link ≠ CL) do temp ← temp.link; 원형리스트가 공백 리스트가 아닌 경우 ① temp ← CL;    리스트가 공백리스트가 아닌 경우에는 첫 번째 노드의 주소를 임시 순회 포인터 temp에 저장하여 노드 순회의 시작점을 지정한다. ② while (temp.link ≠ CL) do   temp ← temp.link;    while 반복문을 수행하여 순회 포인터 temp를 링크를 따라 마지막 노드까지 이동 [그림 5-54] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓐ [그림 5-55] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓑ

③ new.link ← temp.link; ④ temp.link ← new; 리스트의 마지막 노드의 링크 값을 노드 new의 링크에 저장하여, 노드 new가 노드 temp의 다음 노드를 가리키게 한다. 리스트 CL은 원형 연결 리스트이므로 마지막 노드의 다음 노드는 리스트의 첫 번째 노드가 된다. ④ temp.link ← new;       포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다. [그림 5-56] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓒ [그림 5-57] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓓ

⑤ CL ← new; 원형 연결 리스트의 첫 번째 노드 삽입 연산 결과 노드 new의 주소를 리스트 포인터 CL에 저장하여 노드 new가 리스트의 첫 번째 노드가 되도록 지정 원형 연결 리스트의 첫 번째 노드 삽입 연산 결과 [그림 5-58] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓔ [그림 5-59] insertFirstNode( ) 함수 수행 과정_알고리즘 설명 ❷-완성

insertMiddleNode(CL, pre, x) new ← getNode(); new.data ← x; 중간 노드로 삽입하기 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 포인터 pre가 가리키는 노드의 다음 노드로 삽입하는 알고리즘 insertMiddleNode(CL, pre, x)                                   new ← getNode();                    new.data ← x;                    if (CL=null) then {               // ①                          CL ← new;                                       new.link ← new;                      }                          else {                              // ②                          new.link ← pre.link;   // ②-ⓐ                            pre.link ← new;        // ②-ⓑ               } end insertMiddleNode()

① new.link ← pre.link; 노드 pre의 다음 노드로 new를 삽입하기 위해서, 먼저 노드 pre의 다음 노드(pre.link)를 new의 다음 노드(new.link)로 연결 [그림 5-60] insertMiddleNode( ) 함수 수행 과정_초기 상태 [그림 5-61] insertMiddleNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓐ

② pre.link ← new; 노드 new의 주소를 노드 pre의 링크에 저장하여, 노드 pre가 노드 new를 가리키게 한다. [그림 5-62] insertMiddleNode( ) 함수 수행 과정_알고리즘 설명 ❷-ⓑ

원형 연결 리스트의 삭제 연산 원형 연결 리스트 CL에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하고 삭제한 노드는 자유공간 리스트에 반환하는 연산 포인터 old는 삭제할 노드 지시 deleteNode(CL, pre)           if (CL = null) then error;                       else {                                                   old ← pre.link;                       // ①                  pre.link ← old.link;                // ②                  if (old = CL) then                  // ③                          CL ← old.link;               // ③-ⓐ                  returnNode(old);                            }                              end deleteNode() 

① old ← pre.link; ② pre.link ← old.link; 노드 pre의 다음 노드를 삭제할 노드 old로 지정 [그림 5-63] deleteNode( ) 함수 수행 과정_알고리즘 설명 ❶ [그림 5-64] deleteNode( ) 함수 수행 과정_알고리즘 설명 ❷

삭제할 노드 old가 리스트 포인터 CL인 경우 CL ← old.link; 첫 번째 노드를 삭제하는 경우에는 노드 old의 링크 값을 리스트 포인터 CL에 저장하여 두 번째 노드가 리스트의 첫 번째 노드가 되도록 조정 [그림 5-65] deleteNode( ) 함수 수행 과정-삭제 노드가 첫 번째 노드인 경우 [그림 5-66] deleteNode( ) 함수 수행 과정-삭제 노드가 첫 번째 노드인 경우 ❷-ⓐ

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

단순연결기차 이중연결기차 [그림 5-68] 단방향 기차놀이 [그림 5-69] 양방향 기차놀이

리스트 week=(월, 수, 금)의 이중 연결 리스트 구성 원형 이중 연결 리스트 이중 연결 리스트를 원형으로 구성 [그림 5-70] 리스트 week의 이중 연결 리스트 [그림 5-71] 리스트 week의 이중 원형 연결 리스트

양방향 기차 만들기 [그림 5-72] 양방향 기차놀이에 사람 추가하기_초기 상태

양방향 기차 만들기 1 [그림 5-73] 양방향 기차놀이에 사람 추가하기 _왼쪽 사람의 오른손 이름표 받기 [그림 5-74] 양방향 기차놀이에 사람 추가하기 _왼쪽 사람에게 자기 이름 주기

양방향 기차 만들기 2 [그림 5-75] 양방향 기차놀이에 사람 추가하기 _오른쪽 사람의 왼손 이름표 받기 [그림 5-76] 양방향 기차놀이에 사람 추가하기 _오른쪽 사람에게 자기 이름 주기

양방향 기차 만들기 완성 [그림 5-77] 양방향 기차놀이에 사람 추가하기_완성

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

이중 연결 리스트에서의 삽입 알고리즘 insertNode(DL, pre, x) new ← getNode();           new.data ← x;            new.rlink ← pre.rlink ;      // ①                              pre.rlink ← new;              // ②                              new.llink ← pre;              // ③                      new.rlink.llink ← new;      // ④                    end insertNode() 

이중 연결 리스트에서의 삽입 연산 이중 연결 리스트 DL에서 포인터 pre가 가리키는 노드의 다음 노드로 노드 new를 삽입하는 과정 [그림 5-78] insertNode( ) 함수 수행 과정_초기 상태

① new.rlink ← pre.rlink ; ② pre.rlink ← new; 노드 pre의 rlink를 노드 new의 rlink에 저장하여, 노드 pre의 오른쪽 노드를 삽입할 노드 new의 오른쪽 노드로 연결 ② pre.rlink ← new;     새 노드 new의 주소를 노드 pre의 rlink에 저장하여, 노드 new를 노드 pre의 오른쪽 노드로 연결 [그림 5-79] insertNode( ) 함수 수행 과정 _알고리즘 설명 ❶ [그림 5-80] insertNode( ) 함수 수행 과정 _알고리즘 설명 ❷

③ new.llink ← pre; ④ new.rlink.llink ← new; 포인터 pre의 값을 삽입할 노드 new의 llink에 저장하여, 노드 pre를 노드 new의 왼쪽 노드로 연결 ④ new.rlink.llink ← new; 포인터 new의 값을 노드 new의 오른쪽 노드(new.rlink)의 llink에 저장하여, 노드 new의 오른쪽 노드의 왼쪽 노드로 노드 new를 연결 [그림 5-81] insertNode( ) 함수 수행 과정 _알고리즘 설명 ❸ [그림 5-82] insertNode( ) 함수 수행 과정 _알고리즘 설명 ❹

이중 연결 리스트 삭제 [그림 5-83] 양방향 기차놀이에서 사람 나가기_오른손 이름표 넘겨주기

이중 연결 리스트 삭제 [그림 5-84] 양방향 기차놀이에서 사람 나가기_왼손 이름표 넘겨주기

이중 연결 리스트 삭제 [그림 5-85] 양방향 기차놀이에서 사람 나가기_완성

이중 연결 리스트에서의 삭제 연산 이중 연결 리스트에서의 삭제 알고리즘 이중 연결 리스트에서의 삭제 연산 과정 (1) 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크(rlink)에 저장한다. (2) 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장한다. (3) 삭제한 노드를 자유 공간 리스트에 반환한다. 이중 연결 리스트에서의 삭제 알고리즘 deleteNode(DL, old)           old.llink.rlink ← old.rlink;  // ①           old.rlink.llink ← old.llink;  // ②           returnNode(old);               // ③                    end deleteNode() 

이중 연결 리스트에서의 삭제 연산 이중 연결 리스트 DL에서 포인터 old가 가리키는 노드를 삭제하는 과정 ① old.llink.rlink ← old.rlink; 삭제할 노드 old의 오른쪽 노드의 주소를 노드 old의 왼쪽 노드의 rlink에 저장하여, 노드 old의 오른쪽 노드를 노드 old의 왼쪽 노드의 오른쪽 노드로 연결 [그림 5-86] deleteNode( ) 함수 수행 과정_초기 상태 [그림 5-87] deleteNode( ) 함수 수행 과정_알고리즘 설명 ❶

② old.rlink.llink ← old.llink; 삭제할 노드 old의 왼쪽 노드의 주소를 노드 old의 오른쪽노드의 llink에 저장하여, 노드 old의 왼쪽 노드를 노드 old의 오른쪽 노드의 왼쪽 노드로 연결 ③ returnNode(old);   삭제된 노드 old는 자유공간리스트에 반환 [그림 5-88] deleteNode( ) 함수 수행 과정_알고리즘 설명 ❷ [그림 5-89] deleteNode( ) 함수 수행 과정_알고리즘 설명 ❸

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

다항식의 단순 연결 리스트 표현 예 다항식 A(x)=4x3+3x2+5x 다항식 B(x)=3x4+x3+2x+1 [그림 5-91] 다항식 A(x)와 B(x)의 단순 연결 리스트 표현

다항식 연결 자료구조의 삽입 연산 다항식에 항을 추가하는 알고리즘 appendTerm(PL, coef, expo, last) 다항식 리스트 포인터 PL과 coef 필드 값을 저장한 변수 coef, expo 필드 값을 저장한 변수 expo, 리스트 PL의 마지막 노드의 위치를 지시하는 포인터 last를 매개변수로 사용 appendTerm(PL, coef, expo, last)         new ← getNode();         new.expo ← expo;         new.coef ← coef;         new.link ← null;         if (PL = null) then {           // ①                  PL ← new;             // ①-ⓐ                 last ← new;            // ①-ⓑ         }         else {                           // ②                  last.link ← new;      // ②-ⓐ                  last ← new;            // ②-ⓑ end appendTerm()

공백 다항식에서의 항 삽입 연산 초기 상태 ① PL ← new; 포인터 new의 값을 리스트 포인터 PL에 저장하여, 노드 new가 리스트 PL의 첫 번째 노드가 되도록 연결 [그림 5-92] appendTerm( ) 함수 수행 과정 _알고리즘 설명 ❶ [그림 5-93] appendTerm( ) 함수 수행 과정 _알고리즘 설명 ❶-ⓐ

다항식에서의 항 삽입 연산 ② last ← new; 초기 상태 포인터 new의 값을 포인터 last에 저장하여, 포인터 last가 리스트 PL의 마지막 노드인 노드 new를 가리키도록 지정 다항식에서의 항 삽입 연산 초기 상태 [그림 5-94] appendTerm( ) 함수 수행 과정 _알고리즘 설명 ❶-ⓑ [그림 5-95] appendTerm( ) 함수 수행 과정_알고리즘 설명 ❷

① last.link ← new; ② last ← new; 포인터 new의 값을 노드 last의 링크에 저장하여 노드 new를 노드 last의 다음노드로 연결 ② last ← new; 포인터 new의 값을 포인터 last에 저장하여, 노드 new를 리스트 PL의 마지막 노드로 지정 [그림 5-96] appendTerm( ) 함수 수행 과정_알고리즘 설명 ❷-ⓐ [그림 5-97] appendTerm( ) 함수 수행 과정_알고리즘 설명 ❷-ⓑ

다항식 리스트 A에 appendTerm() 알고리즘을 사용하여 2x0항(상수항 2) 추가 예

다항식의 덧셈 연산 덧셈 A⒳+B⒳=C⒳를 단순 연결 리스트 자료구조를 사용하여 연산 포인터 p : 다항식 A⒳에서 비교할 항을 지시 포인터 q : 다항식 B⒳에서 비교할 항을 지시 포인터 r : 덧셈연산 결과 만들어지는 다항식 C⒳의 항을 지시

p.expo < q.expo : 다항식 A⒳ 항의 지수가 작은 경우 포인터 q가 가리키는 다항식 B⒳의 항을 C⒳의 항으로 복사 q가 가리키는 항에 대한 처리가 끝났으므로 q를 다음 노드로 이동 [그림 5-99] q의 지수가 더 큰 경우의 연산

p.expo = q.expo : 두 항의 지수가 같은 경우 p.coef와 q.coef를 더하여 C⒳의 항, 즉 r.coef에 저장하고 지수가 같아야 하므로 p.expo(또는 q.expo)를 r.expo에 저장 다음 항을 비교하기 위해 포인터 p와 q를 각각 다음 노드로 이동 [그림 5-100] 지수가 같은 경우의 연산

p.expo > q.expo : 다항식 A⒳ 항의 지수가 큰 경우 포인터 p가 가리키는 다항식 A⒳의 항을 C⒳의 항으로 복사 p가 가리키는 항에 대한 처리가 끝났으므로 p를 다음 노드로 이동 [그림 5-101] p의 지수가 더 큰 경우의 연산

다항식의 덧셈 알고리즘 addPoly(A, B) // 단순 연결 리스트로 표현된 다항식 A와 B를 더하여 다항식의 덧셈 알고리즘 addPoly(A, B)                 // 단순 연결 리스트로 표현된 다항식 A와 B를 더하여                // 새로운 다항식 C를 반환         p ← A;         q ← B;         C ← null;     // 결과 다항식         r ← null;     // 결과 다항식의 마지막 노드를 지시         while (p ≠ null and q ≠ null) do {     // p, q는 순회 포인터              case {                 p.expo = q.expo :                                sum ← p.coef + q.coef                                if (sum ≠ 0) then appendTerm(C, sum, p.expo, r);                                p ← p.link;                                q ← q.link;                p.expo < q.expo :                               appendTerm(C, q.coef, q.expo, r);                               q ← q.link;                 else :     // p.expo > q.expo인 경우                               appendTerm(C, p.coef, p.expo, r);                               p ← p.link;              } // end case         } // end while

        while (p ≠ null) do {     // A의 나머지 항들을 복사                appendTerm(C, p.coef, p.expo, r);                p ← p.link;         }         while (q ≠ null) do {     // B의 나머지 항들을 복사               appendTerm(C, q.coef, q.expo, r);               q ← q.link;        return C;   end addPoly()

다항식의 덧셈 예) A(x)=4x3+3x2+5x B(x)=3x4+x3+2x+1 초기 상태 다항식의 덧셈 예) A(x)=4x3+3x2+5x B(x)=3x4+x3+2x+1 초기 상태 [그림 5-102] A(x)+B(x)=C(x)_초기 상태

① 4x3항과 3x2항에 대한 처리 p.expo < q.expo이므로 지수가 큰 q 노드를 리스트 C에 복사 [그림 5-103] A(x)+B(x)=C(x)_4x3항과 3x4항에 대한 처리 후

② 4x3항과 1x3 항에 대한 처리 p.expo = q.expo 이므로 두 노드의 coef 필드의 값을 더하고, expo 필드의 값을 복사한 노드를 리스트 C에 추가 포인터 p와 q는 다음 노드로 [그림 5-104] A(x)+B(x)=C(x)_4x3항과 1x3항에 대한 처리 후

③ 3x2항과 2x1 항에 대한 처리 p.expo > q.expo 이므로 지수가 큰 p 노드를 리스트 C에 복사 [그림 5-105] A(x)+B(x)=C(x)_3x2항과 2x1항에 대한 처리 후

④ 5x1항과 2x1 항에 대한 처리 p.expo = q.expo 이므로 두 노드의 coef 필드의 값을 더하고, expo 필드의 값을 복사한 노드를 리스트 C에 추가 포인터 p와 q는 다음 노드로 이동 [그림 5-106] A(x)+B(x)=C(x)__5x1항과 2x1항에 대한 처리 후

⑤ B(x)의 남은 항에 대한 처리 포인터 p가 null이므로 다항식 A⒳의 항에 대한 처리 끝 처리할 항이 남아있는 다항식 B⒳의 포인터 q는 null이 될 때까지 모든 노드를 복사하여 리스트 C에 추가 [그림 5-107] A(x)+B(x)=C(x)_남은 항에 대한 처리 후

연결 리스트 이용한 다항식 프로그램 001 #include <stdio.h> 002 #include <stdlib.h> 003 004 typedef struct ListNode{ 005 float coef; 006 int expo; 007 struct ListNode* link; 008 } ListNode; 009 010 typedef struct ListHead{ 011 ListNode* head; 012 } ListHead; 013 014 015 ListHead* createLinkedList(void) 016 { 017 ListHead* L; 018 L = (ListHead *)malloc(sizeof(ListHead)); 019 L->head = NULL; 020 return L; 021 } 022 023 void addLastNode(ListHead* L, float coef, int expo) 024 { 025 ListNode* newNode; 026 ListNode* p; 027 newNode = (ListNode *)malloc(sizeof(ListNode)); 028 newNode->coef = coef; 029 newNode->expo = expo; 030 newNode->link = NULL; 031 if(L->head == NULL){ 032 L->head = newNode; 033 return; 034 }

연결 리스트 이용한 다항식 프로그램 035 else { 053 addLastNode(C, sum, pA->expo); 036 p = L->head; 037 while(p->link != NULL) { 038 p = p->link; 039 } 040 p->link = newNode; 041 } 042 } 043 044 void addPoly(ListHead* A, ListHead* B, ListHead* C) 045 { 046 ListNode* pA = A->head; 047 ListNode* pB = B->head; 048 float sum; 049 050 while(pA && pB){ 051 if(pA->expo == pB->expo){ 052 sum = pA->coef + pB->coef; 053 addLastNode(C, sum, pA->expo); 054 pA=pA->link; pB=pB->link; 055 } 056 else if(pA->expo > pB->expo){ 057 addLastNode(C, pA->coef, pA->expo); 058 pA=pA->link; 059 } 060 else { 061 addLastNode(C, pB->coef, pB->expo); 062 pB=pB->link; 063 } 213 064 } 065 066 for( ; pA!=NULL; pA=pA->link) 067 addLastNode(C, pA->coef, pA->expo); 068

연결 리스트 이용한 다항식 프로그램 069 for( ; pB!=NULL; pB=pB->link) 070 addLastNode(C, pB->coef, pB->expo); 071 } 072 073 void printPoly(ListHead* L) 074 { 075 ListNode* p = L->head; 076 for(;p;p=p->link){ 077 printf("%3.0fx^%d", p->coef, p->expo); 078 } 079 } 080 081 void main(void){ 082 ListHead *A, *B, *C; 083 084 A = createLinkedList(); 085 B = createLinkedList(); 086 C = createLinkedList(); 087 088 addLastNode(A, 4,3); 089 addLastNode(A, 3,2); 090 addLastNode(A, 5,1); 091 printf("\n A(x)="); 092 printPoly(A); 093 094 addLastNode(B, 3,4); 095 addLastNode(B, 1,3); 096 addLastNode(B, 2,1); 097 addLastNode(B, 1,0); 098 printf("\n B(x)="); 099 printPoly(B); 100 101 addPoly(A, B, C); 102 printf("\n C(x)="); 103 printPoly(C); 104 105 getchar(); 106 }

연결 리스트 이용한 다항식 프로그램 실행 결과