- 1 -
데이터 구조1 실습 (9주차)
2021. 4. 28
1. 정수 n을 매개변수로 전달받아서 n에 포함된 숫자들중에서 반복되는 숫자들을 제거하여 반환하는 알 고리즘 remove_multiples()를 작성하라. 가령, 주어진 정수가 11222334일 경우에 출력은 1234이다. 반드시 스택을 이용하라. 다음과 같이 정의된 스택을 복사하여 사용하라.
#define MAX_SIZE 20
typedef struct { // 스택 타입 정의 int data[MAX_SIZE];
int top;
} stack_type;
typedef stack_type* stack_ptr;
void init(stack_ptr s) { s->top = -1; } int is_empty(stack_type s) {
return (s.top == -1);
}
int is_empty(stack_type s) { return (s.top == -1);
}int is_full(stack_type s) {
return (s.top == (MAX_SIZE - 1));
}
void push(stack_ptr s, int val) { if (is_full(*s)) {
fprintf(stderr, "Error: stack full\n");
return;
}else
s->data[++s->top] = val;
}
int pop(stack_ptr s) { if (is_empty(*s)) {
fprintf(stderr, "Error: stack empty\n");
exit(1);
}else
return s->data[s->top--];
}
int peek(stack_type s) { if (is_empty(s)) {
fprintf(stderr, "Error: stack empty\n");
exit(1);
}else
return s.data[s.top];
}
위에서 작성된 알고리즘을 C 함수로 작성하고, 다음과 같이 main()을 작성하여, 테스트하라.
int main() {
int num = 11222344;
printf(“%d => %d\n”, num, remove_multiples(num));
return 0;
}
- 2 - 2. 다음과 같이 정의된 선형 큐에 대해서 실습하라.
#define MAX_QUEUE_SIZE 5 typedef int element;
typedef struct {
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
큐의 초기 상태는 다음과 같이 표현된다: ( ), front = -1, rear = -1
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);
