- 1 -
데이터 구조1 실습 (10주차)
2021. 5. 5 1. 다음과 같이 정의된 원형 큐에 대해서 실습하라.
#define MAX_QUEUE_SIZE 5 typedef int element;
typedef struct {
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
큐의 초기 상태는 다음과 같이 표현된다: ( ), front = 0, rear = 0
a. 위의 원형 큐 q에 대해서 다음과 같은 연산을 순차적으로 수행하라. 각 연산 이후의 큐의 내용, front, rear의 값을 큐 상에 나타내라.
enqueue(&q, 1);
enqueue(&q, 2);
dequeue(&q);
enqueue(&q, 3);
b. a)에 이어서 q에 대해서 다음과 같은 연산을 순차적으로 수행하라. 각 연산 이후의 큐의 내용, front, rear의 값을 큐 상에 나타내라.
enqueue(&q, 4);
dequeue(&q);
enqueue(&q, 5);
enqueue(&q, 6);
c. 큐의 내용을 출력하는 C 함수 display(QueueType q)를 작성하라.
d. 위의 원형 큐에 대한 다음 연산의 C 함수를 작성하라.
void init(QueueType* q); int is_empty(QueueType q);
int is_full(QueueType q); void enqueue(QueueType* q, element);
element dequeue(QueueType* q);
e. a)의 큐 연산을 수행하는 main() 함수를 작성하고, 테스트하라. 큐 연산 수행 후에 큐의 내용을 출력 하라.
enqueue(&q, 1); enqueue(&q, 2); dequeue(&q); enqueue(&q, 3);
enqueue(&q, 4); dequeue(&q); enqueue(&q, 5); enqueue(&q, 6); display(q);
- 2 -
2. 1)에서 정의한 원형 큐를 이용하여 다음과 같이 피보나치 수열을 계산하라: 처음에, F(0), F(1)을 큐에 넣는다. 큐에 포함된 이전의 값을 이용하여 다음번째 피보나치 수를 구하여 이를 다시 큐에 넣는다.
피보나치 수열은 다음과 같이 정의된다:
F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2)
다음과 같이 큐를 이용하여 피보나치 수열을 계산하는 프로그램을 작성하라.
a. 큐를 이용하여 F(n)을 구하여 반환하는 C 함수 fibo_que(n)을 작성하라.
b. 사용자로부터 정수 n을 입력받고, a)의 fibo_que(n)을 이용하여 n의 피보나치 수를 구하여 출력하는 main()을 작성하고, 테스트하라.
