- 1 -
데이터 구조1 실습 (13주차)
2021. 5. 26
1. 다음 main() 함수를 고려하라. 여기서 고려하는 리스트는 원형 연결리스트이며, 헤드 포인터는 리스트 의 마지막 노드를 가리킨다.
typedef struct ListNode { // 리스트 노드 타입 정의 int data;
struct ListNode *link;
} ListNode;
int main() {
ListNode *list = NULL; // 헤드 포인터
list = insert_first(list, 10); // 1) 리스트의 첫번째 항목으로 추가 list = insert_first(list, 20); // 2)
list = insert_first(list, 30); // 3)
list = insert_last(list, 40); // 4) 리스트의 마지막 항목으로 추가 list = insert_last(list, 50); // 5)
print_list(list); // 리스트에 포함된 모든 항목 출력 return 0;
}
a. main()에 포함된 각 리스트 삽입 연산 후의 결과 리스트를 그려라. list 포인터가 어느 노드를 가리키 는지 표시하라.
b. list와 data를 전달받아서, data를 포함하는 노드를 동적 생성하고, 이 노드를 list의 첫 번째 노드로 삽 입하는 insert_first(list, data)를 작성하라.
c. list와 data를 전달받아서, data를 포함하는 노드를 동적생성하고, 이 노드를 list의 마지막 노드로 삽입 하는 insert_last(list, data)를 작성하라.
d. list를 전달받아서 list에 포함된 모든 노드의 data 필드 값을 출력하는 print_list(list)를 작성하라.
e. 위의 main() 함수를 실행시켜서 테스트하라.
- 2 -
2. 다음에서 이중 연결리스트를 생성하고, 출력하는 C 코드를 고려하라.
typedef struct DlistNode{
int data;
struct DListNode*llink;
struct DListNode*rlink;
} DListNode;
int main(void) {
DListNode* head = (DListNode*)malloc(sizeof(DListNode));
init(head); // llink, rlink가 자신을 가리키게 초기화
for (int i = 1; i< 5; i++) // 리스트의 첫 번째 노드로 삽입 dinsert(head, i);
print_dlist(head); // 지점 1
dinsert_last(head, 5); // 리스트의 마지막 노드로 삽입 print_dlist(head);
return 0;
}
a. main()에서 for 문의 수행 결과로 생성된 리스트를 그려라.
b. init() 함수를 C 언어로 작성하라.
c. for 문에서 dinsert()는 이중연결리스트의 헤드 노드를 가리키는 head와 정수 data를 전달받아서 data 를 포함하는 DlistNode를 동적 생성하고, 이 노드를 head의 첫 번째 노드로 삽입한다. 이 함수를 C 언 어로 작성하라.
d. 리스트에 포함된 모든 노드를 출력하는 print_dlist(head)를 C 언어로 작성하라. 매개변수로 전달된 head는 헤드 노드에 대한 포인터이다. 또한 main()에서 지점 1까지 실행하여 이중연결리스트가 올바 르게 생성되었는지를 확인하라.
e. dinsert_last()는 dinsert()와 마찬가지로 한 개의 노드를 생성하여 리스트에 삽입하는데, 리스트의 첫 번째 노드가 아닌 마지막에 삽입한다. 이 함수를 C 언어로 작성하라.
f. 위의 main() 함수 전체를 실행시켜서 dinsert_last()가 올바르게 동작하는지를 테스트하라.
