- 1 -
데이터 구조1 실습 (11주차)
2021. 5. 12
1. 다음 main() 함수를 고려하라. 단, 리스트는 배열로 표현된다.
typedef struct { // 리스트 타입 정의 int array[MAX_LIST_SIZE];
int size; // 리스트에 포함된 항목 개수
} ArrayListType;
int main() {
ArrayListType list;
init(&list); // 리스트 초기화
insert_last(&list, 10); // 리스트 마지막에 항목 추가 insert_last(&list, 20);
insert_last(&list, 30);
delete(&list, 0); // 리스트의 인덱스 3의 위치한 항목 삭제 insert(&list, 1, 40); // 리스트의 인덱스 1의 위치에 항목 추가 insert(&list, 0, 50);
delete(&list, 1); // 리스트의 인덱스 3의 위치한 항목 삭제 print_list(list); // 리스트에 포함된 모든 항목 출력 return 0;
}
a. main()에 포함된 모든 리스트 연산 수행 후 리스트의 상태는 무엇인가? 리스트의 상태는 array와 size 로 표현된다.
b. 다음의 리스트 관련 함수를 작성하라. 또한, is_full(), is_empty() 함수를 포함시켜라.
int is_empty(ArrayListType list) // 리스트가 비어 있는지 검사 int is_full(ArrayListType list) // 리스트가 꽉 차 있는지 검사 insert_last(ArrayListType* list, int item) // 리스트 마지막에 항목 삽입 insert(ArrayListType* list, int pos, int item) // 리스트의 pos 위치에 항목 삽입 delete(ArrayListType* list, int pos) / 리스트의 pos 위치의 항목 삭제 print_list(ArrayListType list); // 리스트에 포함된 모든 항목 출력
c. main() 함수를 실행시켜라. 실행 결과와 a)에서의 리스트 상태와 비교하라.
- 2 -
2. 다음 main() 함수를 고려하라. 단, 리스트는 연결리스트로 표현된다.
typedef struct ListNode { // 리스트 노드 타입 정의 int data;
struct ListNode *link;
} ListNode;
int main() {
ListNode *list = NULL;
list = insert_first(list, 10); // 리스트 첫 번째 항목으로 추가 list = insert_first(list, 20);
list = insert_first(list, 30);
print_list(list); // ① 리스트에 포함된 모든 항목 출력 list = delete_first(list); // 리스트의 첫번째 항목 삭제 list = insert_first(list, 40);
list = insert_first(list, 50);
list = delete_first(list);
print_list(list); // ② 리스트에 포함된 모든 항목 출력 return 0;
}
a. 위 코드의 ① 지점에서의 리스트 상태를 그려라
b. 위 코드의 ② 지점에서의 리스트 상태를 그려라
c. 매개변수로 전달된 항목 item을 포함하는 노드를 생성하여 반환하는 get_node(int item)를 C 함수로 작성하라.
d. insert_first(ListNode *list, int val)을 C 함수로 작성하라. 이 함수는 val의 항목을 포함하는 노드를 생 성하고, 이 노드를 list의 첫 번째 노드로 추가한 결과 리스트의 헤드 포인터를 반환한다. c)에서 작성 한 get_node()를 이용하라.
e. print_list(ListNode list)를 C 함수로 작성하라. 이 함수는 리스트에 포함된 모든 노드를 순차적으로 방 문하면서 노드에 포함된 항목을 출력한다.
f. delete_first(ListNode *list)를 C 함수로 작성하라. 이 함수는 list의 첫 번째 노드를 삭제하고, 그 결과 리스트의 헤드 포인터를 반환한다.
g. main() 함수를 실행시키고, 각 지점에서의 리스트 출력을 a), b)에서 작성한 리스트 상태와 비교하라.
