[C/자료구조] 덱 구현하기 (feat. 회문)

 

C언어를 이용한 자료구조 실습입니다.

덱을 구현하고 회문인지 확인하는 문제입니다.

---

 

I. 문제

한 개의 문자열을 매개변수로 전달받고, 이 문자열이 앞에서부터 읽으나 뒤에서부터 읽으나 같은지를 판단하여 true 또는 false를 반환하는 check_str() 알고리즘을 작성하라. 가령,  check_str()은 문자열이 “madam”이면 true를 반환하고, “data”이면 false를 반환하다. 단, 덱(deque)을 이용하라.

 

위에서 작성한 알고리즘을 C 함수로 작성하고, 또한 main() 함수를 작성하여 테스트하라. Main()에서는 사용자로부터 문자열을 입력받고, check_str()에 전달하고, 그 결과를 적절하게 출력한다. 위 과정을 사용자가 원할 때까지 반복되게 하라.

 

 

II. 구현

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define QUEUE_MAX_SIZE 100
typedef int element;

typedef struct {
	element Queue[QUEUE_MAX_SIZE];
	int front, rear;
}Dequetype;

void init(Dequetype* q) {
	q->front = q->rear = 0;

}

int is_empty(Dequetype* q) {
	return q->front == q->rear;
}

int is_full(Dequetype* q) {
	return ((q->rear + 1) % QUEUE_MAX_SIZE == q->front);
}

void add_rear(Dequetype* q, element item) {
	if (is_full(q)) {
		fprintf(stderr, "메모리가 가득찼습니다.\n");
		exit(1);
	}

	q->rear = (q->rear + 1) % QUEUE_MAX_SIZE;
	q->Queue[q->rear] = item;


}

element delete_front(Dequetype* q) {
	if (is_empty(q)) {
		fprintf(stderr, "메모리가 비어있습니다.\n");
		exit(1);
	}

	q->front = (q->front + 1) % QUEUE_MAX_SIZE;
	return q->Queue[q->front];

}

void add_front(Dequetype* q, element item) {
	if (is_full(q)) {
		fprintf(stderr, "메모리가 가득찼습니다.\n");
		exit(1);
	}

	q->Queue[q->front] = item;
	q->front = (q->front - 1 + QUEUE_MAX_SIZE) % QUEUE_MAX_SIZE;
}

element delete_rear(Dequetype* q) {
	int save = q->rear;
	if (is_empty(q)) {
		fprintf(stderr, "메모리가 비어있습니다.\n");
		exit(1);
	}

	q->rear = (q->rear - 1 + QUEUE_MAX_SIZE) % QUEUE_MAX_SIZE;
	return q->Queue[save];

}

/* 필요한 덱 기본 골격 */


int check_str(Dequetype* q, char* str)
{
	int flag = 1; // 반환값 : ture = 1 false = 0
	for (int i = strlen(str) - 1; i > 0; i--) { // 문자열의 길이만큼
		if (delete_front(q) != str[i]) // 앞 글자와 뒷 글자를 비교
			flag = 0; //다르다면 false
	}
	return flag;
}


int main(void) {

	int input = 0;		// 입력 변수
	char str[100] = ""; // 문자열 선언 및 초기화
	Dequetype q;		// 덱선언
	init(&q);			//덱 초기화

	while (1)
	{
		printf("단어를 입력해주세요 :");
		scanf_s("%s", str, sizeof(str)); 

		for (int i = 0; i < strlen(str) - 1; i++)
			add_rear(&q, str[i]); // 덱에 넣기 add_rear사용


		if (check_str(&q, str))  
			printf("회문입니다.\n"); 
		else
			printf("회문이 아닙니다.\n");

		printf("계속하려면 1을 눌러주세요: ");
		scanf_s("%d", &input, sizeof(input)); 

		if (input != 1)
			break; //입력변수가 1이 아니면 종료
	}

	return 0;

}

 

III. 결과

 

 감사합니다.

 

---

 

공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.