[한빛미디어] C로 배우는 쉬운 자료구조 - 5장 연습문제

[한빛미디어] C로 배우는 쉬운 자료구조 - 5장 연습문제

C로 배우는 자료구조 5장연습문제.hwp

5장 연습문제

1. 순차 자료구조와 연결 자료구조를 비교 설명하시오.

답 안
순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 연결 자료구조 또는 비순차 자료구조는 다음 원소의 주소에 의해 순서가 연결되는 방식이기 때문에 순차 자료구조와 달리 물리적인 순서를 맞추기위한 오버헤드가 발생하지 않는다. 연결 자료구조에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위로 저장하는데, 이러한 단위 구조를 노드(node)라고 한다. 노드는 원소의 값을 저장하는 데이터 필드(data field)와 다음 노드의 주소를 저장하는 링크필드(link field)로 구성된다.

2. 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트의 특징을 설명하시오.

답 안
단순 연결 리스트 : 한쪽으로만 연결된 단순 구조 원형 연결 리스트 : 단순 연결 리스트의 마지막 노드의 링크 필드에서 첫 번째 노드의 주소를 저장 구성 이중 연결 리스트 :양쪽 방향으로 순회할 수 있도록 노드를 연결

3. 다음의 포인터 연산의 의미를 설명하시오.

답 안
① p = p.link; >> 포인터 p가 가리키는 노드의 다음 포인터로 이동 ② p = q; >> 포인터 q가 가리키는 노드를 포인터 p로 대입 ③ p.link = q; >> 포인터 q가 가리키는 노드를 포인터 p가 가리키는 노드의 다음 노드 ④ p.link = q.link; >> 포인터 q가 가리키는 노드의 다음 노드를 포인터 p가 가리키는 노드의 다음노드가 되도록 연결

5. [알고리즘 5-8]을 C함수로 작성하시오.

답 안
void insertFirstNode(linkedList_h* CL, char *x){ ListNode* newNode; ListNode* temp; newNode = (ListNode*)malloc(sizeof(ListNode)); strcpy(newNode->data, x); if (CL->head == NULL){ CL->head = newNode; newNode->link = newNode; } else{ temp=CL->head; while(temp->link != CL->head) temp = temp->link; newNode->link = temp->link; temp->link = newNode; CL->head = newNode; } }

6. [알고리즘 5-9]을 C함수로 작성하시오.

답 안

void insertMiddleNode(linkedList_h* CL, char* pre, char* x){ ListNode* newNode; ListNode* previous; ListNode *temp; newNode = (ListNode*)malloc(sizeof(ListNode)); strcpy(newNode->data, x); if (CL->head == NULL){ CL->head = newNode; newNode->link = newNode; } else{ previous = CL->head; while(strcmp(previous->data, pre)) previous = previous->link; temp = previous->link; previous->link = newNode; newNode->link = temp; } }

7. [알고리즘 5-10]을 C함수로 작성하시오.

답 안

void deleteNode(linkedList_h * CL, char* pre){ ListNode* previous; ListNode* temp; if (CL->head == NULL) return; if (CL->head->link == NULL) { free(CL->head); CL->head = NULL; return; } else{ previous = CL->head; CL->head = previous; while(strcmp(previous->data, pre)) previous = previous->link; temp = previous->link; previous->link = temp->link; if(temp==CL->head) CL->head=previous->link; free(temp); } }