- 1 -
데이터 구조 실습 (6주차)
2021. 4. 7
학번: 성명:
1. 다음의 동적 자료구조를 생성하고자 한다. 이 자료구조는 3개의 노드로 구성되어 있고, 각 노드는 (val, next)의 2개 필드를 포함하는 구조체이다. 여기서 val은 int 타입이며, next는 노드를 가리키는 포인터이다. 노 드들은 next 필드를 통해서 연결되는 것을 알 수 있다. 다음에 답하시오.
a. 노드의 타입을 정의하라. 그 타입의 이름은 struct node이다.
b. struct node의 다른 타입 이름으로 nodeType을 만들어라.
b. first, p, q, r을 nodeType에 대한 포인터로 선언하라.
c. 한 개의 노드를 동적 생성하고, p가 이를 가리키게 하라.
d. p가 가리키는 구조체의 val 필드에 10을 할당하고, next 필드에는 NULL을 할당하라.
e. 위의 c), d)의 과정을 반복하여 2개의 노드를 동적 생성하고, q, r이 이들을 각각 가리키게 하라.
f. q, r이 가리키는 구조체의 val 필드에 각각 20, 30을 할당하고, next에는 NULL을 할당하라.
g. p가 가리키는 구조체의 next 필드가 q가 가리키는 구조체를 가리키게 하라.
h. q가 가리키는 구조체의 next 필드가 r이 가리키는 구조체를 가리키게 하라.
I. first가 p가 가리키는 구조체를 가리키게 하라.
j. first 포인터를 이용하여 첫 번째 노드의 val 필드 값을 출력하라.
k. first 포인터를 이용하여 두 번째 노드의 val 필드 값을 출력하라.
l. first 포인터를 이용하여 세 번째 노드의 val 필드 값을 출력하라.
m. 위의 j~k의 과정을 반복 구조를 이용하여 처리하라.
n. a ~m에서 작성한 문장들을 포함한 main() 함수를 작성하고, 테스트하라.
- 2 - 2. 다음에 답하시오.
#define MAX_SIZE 20
typedef struct { // 스택 타입 정의 int stack[MAX_SIZE];
int top;
} stack_type;
typedef stack_type* stack_ptr;
void init(stack_ptr s) { s->top = -1; } main() {
stack_type s; // 스택 생성
init(&s); // 스택 초기화: top을 –1로 설정 push(&s, 1); // 스택에 값 저장
push(&s, 2);
push(&s, 3);
//스택 값 출력
while (!is_empty(s) ) {
printf(“%d\n“, ( pop(&s));
} }
a. 다음 스택 연산 함수를 작성하라:
i) int is_empty(stack_type s) {}
ii) int is_full(stack_type s) {}
b. a)의 함수를 이용하여 다음 스택 연산 함수를 작성하라:
i) void push(stack_ptr s, int val) {}
ii) int pop(stack_ptr s) {}
c. a), b)의 함수를 이용하여 위의 코드를 완성하고, 테스트하라.
3. 2)에서 정의된 스택을 이용하여 주어진 문자열을 역순으로 출력하고자 한다. 다음 순서대로 문제를 해결하라.
a. “abcdefgh”의 문자열 str을 선언하면서 초기화하라.
b. str에 포함된 문자들을 순서대로 스택 s에 저장하라.
c. b)에서 스택 s에 저장된 문자들을 꺼내어 출력하라.
d. a) ~ c)의 과정을 수행하는 C 프로그램을 작성하고, 테스트하라.