데이터 구조1 실습 (11주차)
2021. 5. 12
1. 다음 main() 함수를 고려하라. 단, 리스트는 배열로 표현된다.
#define MAX_LIST_SIZE 10
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);
print_list(list); // 리스트에 포함된 모든 항목 출력
delete(&list, 0); // 리스트의 array 인덱스 0의 위치한 항목 삭제 insert(&list, 1, 40); // 리스트의 인덱스 1의 위치에 항목 추가 insert(&list, 0, 50);
delete(&list, 1); // 리스트의 인덱스 1의 위치한 항목 삭제 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)에서의 리스트 상태와 비교하라.
// 소스 코드
#include <stdio.h>
#define MAX_LIST_SIZE 10
typedef struct { // 리스트 타입 정의
int array[MAX_LIST_SIZE];
int size; // 리스트에 포함된 항목 개수
} ArrayListType;
void init(ArrayListType* list); // 리스트 초기화
int is_empty(ArrayListType list); // 리스트가 비어 있는지 검사 int is_full(ArrayListType list); // 리스트가 꽉 차 있는지 검사
void insert_last(ArrayListType* list, int item); // 리스트 마지막에 항목 삽입 void insert(ArrayListType* list, int pos, int item); // 리스트의 pos 위치에 항목 삽입 void delete_list(ArrayListType* list, int pos); // 리스트의 pos 위치의 항목 삭제
void print_list(ArrayListType list); // 리스트에 포함된 모든 항목 출력
int main() {
ArrayListType list;
init(&list); // 리스트 초기화; size <- 0
insert_last(&list, 20); // 리스트 마지막에 항목 추가 insert_last(&list, 40);
insert_last(&list, 30);
delete_list(&list, 0); // 리스트의 인덱스 3의 위치한 항목 삭제 insert(&list, 1, 50); // 리스트의 인덱스 1의 위치에 항목 추가 insert(&list, 0, 10);
delete_list(&list, 2); // 리스트의 인덱스 3의 위치한 항목 삭제
print_list(list); // 리스트에 포함된 모든 항목 출력
return 0;
}
void init(ArrayListType* list) { // 리스트 초기화
list->size = 0;
}
int is_empty(ArrayListType list) {
int is_full(ArrayListType list) { // 리스트가 꽉 차 있는지 검사
// return list.size == MAX_LIST_SIZE;
if (list.size == MAX_LIST_SIZE) return 1;
else return 0;
}
void insert_last(ArrayListType* list, int item) { // 리스트 마지막에 항목 삽입
if (!is_full(*list)) {
list->array[list->size] = item; // 마지막에 항목 추가 list->size++; // size 필드 값 증가
} }
void insert(ArrayListType* list, int pos, int item) { // 리스트의 pos 위치에 항목 삽입
if (!is_full(*list) && pos >=0 && pos<= list->size) {
for (int i = list->size - 1; i >= pos; i--) { // 마지막 항목부터 pos 항목까지 한칸씩 뒤로 이동 list->array[i + 1] = list->array[i];
}
list->array[pos] = item; // pos 위치에 항목 추가 list->size++; // size 필드 값 증가
} }
void delete_list(ArrayListType* list, int pos) { // 리스트의 pos 위치의 항목 삭제
if (!is_empty(*list) && pos >= 0 && pos <= list->size-1) {
for (int i = pos+1; i < list->size; i++) { // pos 항목부터 마지막 항목까지 한칸씩 앞으로 이동 list->array[i - 1] = list->array[i];
}
list->size--; // size 필드 값 감소 }
}
void print_list(ArrayListType list) { // 리스트에 포함된 모든 항목 출력
for (int i = 0; i < list.size; i++) // 처음부터 마지막 항목까지 순차적으로 출력 printf("%d\n", list.array[i]);
}
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); // ② 리스트에 포함된 모든 항목 출력 // list->10->20->...
return 0;
}
a. 위 코드의 ① 지점에서의 리스트 상태를 그려라
b. 위 코드의 ② 지점에서의 리스트 상태를 그려라 list->40->20->10->NULL
c. 매개변수로 전달된 항목 item을 포함하는 노드를 생성하여 반환하는 get_node(int item)를 C 함수로 작성하라.
ListNode *get_node(int item) { ListNode *p;
p = (ListNode *)malloc(sizeof(ListNode)); // 노드 생성 p->data = 50; p->link = NULL; // 노드 초기화 return p;
}
d. insert_first(ListNode *list, int val)을 C 함수로 작성하라. 이 함수는 val의 항목을 포함하는 노드를 생 성하고, 이 노드를 list의 첫 번째 노드로 추가한 결과 리스트의 헤드 포인터를 반환한다. c)에서 작성 한 get_node()를 이용하라.
insert_first(ListNode *list, int val) { ListNode *p;
p = getNode(val); // 노드 생성 및 초기화
e. print_list(ListNode *list)를 C 함수로 작성하라. 이 함수는 리스트에 포함된 모든 노드를 순차적으로 방문하면서 노드에 포함된 항목을 출력한다.
void print_list(ListNode *list) { ListNode *p = list;
while(p != NULL) { print(p->data);
p = p->link;
} }
f. delete_first(ListNode *list)를 C 함수로 작성하라. 이 함수는 list의 첫 번째 노드를 삭제하고, 그 결과 리스트의 헤드 포인터를 반환한다.
g. main() 함수를 실행시키고, 각 지점에서의 리스트 출력을 a), b)에서 작성한 리스트 상태와 비교하라.
