[C/자료구조] 원형 연결리스트 덱 구현하기 (feat. 회문)

 

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

덱은 전단과 후단 양쪽 모두에서 삽입과 삭제의 입출력과 반환이 가능한 원형 큐를 말합니다.

덱의 삽입/삭제 연산을 구현하고 이를 이용해 입력된 문자열이 회문인지 판별합니다.

---

 

I. 문제

원형 연결리스트를 이용하여 아래와 같이 덱(이것을 ListDeq이라 한다)을 구현하고자 한다.

 

 

ListDeq 타입(ListDeqType)을 노드에 대한 front, rear의 2개 포인터를 포함하는 구조체로 정의하라. front는 리스트의 첫번째 노드를, rear는 마지막 노드를 가리킨다. 노드는 (data, link)의 2개 필드를 포함하는 구조체이며, data는 문자 타입이며, link는 노드에 대한 포인터이다.

 

 

다음 덱의 연산을 ListDeq에 대해서도 정의하라 :

 

• init_queue()
• is_empty()
• is_full()
• add_rear()
• delete_rear()
• add_front()
• delete_front()
• get_front()
• get_rear()

 

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

 

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

 

II. 구현

[ListDeq타입 정의]

typedef char element;

typedef struct {
            element data;
            struct Node* link;
} Node;

typedef struct {
            Node* front, * rear;
} ListDeq;

 

[덱 *ADT]

*ADT (Abstract Data Type 추상자료형) : 순수하게 기능이 무엇인지를 나열한 것

 

• init_queue(q) ::= 덱 q의 front포인터와 rear포인터를 NULL로 초기화 한다.
• is_empty(q) ::= 덱 q가 비어있는지 검사한다.
• is_full(q) ::= 덱 q가 꽉 찼는지 검사한다.
• add_rear(q, item) ::= 덱 q의 맨 끝에 노드를 추가한다.
• delete_rear(q) ::= 덱 q의 맨 끝에 노드를 삭제한 뒤 반환한다.
• add_front(q, item) ::= 덱 q의 맨 처음에 노드를 추가한다.
• delete_front(q)::= 덱 q의 맨 처음 노드를 삭제한 뒤 반환한다.
• get_front(q) ::= 덱 q의 첫번째 노드를 반환한다.
• get_rear(q) ::= 덱 q의 마지막 노드를 반환한다.

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

typedef char element;

typedef struct {
	element data;
	struct Node* link;
}Node;  // 노드 구조체 정의

typedef struct {
	Node* front, * rear;
}ListDeq;   // 덱 구조체 정의


void init_queue(ListDeq* q) {
	q->front = q->rear = NULL;
}    // 덱 초기화

int is_empty(ListDeq* q) {
	return q->front == NULL;
}   // 덱이 비어있는지 검사

int is_full(ListDeq* q) {
	return 0;
}   // 덱이 꽉 차있는지 검사


// 덱의 뒷자리 제거후 반환
element* delete_rear(ListDeq* q) {
	if (!is_empty(q)) { // 덱이 비어있지 않다면

		if (q->front == q->rear) { // 노드가 1개 일때
			element val = q->front->data; // 데이터 저장
			q->front = NULL;
			q->rear = NULL;
			return val;
		}
		else {  // 노드가 여러개 있을 때
			Node* pre; // rear전 요소를 가르킬 노드 포인터
			Node* remove = (Node*)malloc(sizeof(Node)); // 지울 노드를 가르킬 포인터
			pre = q->front;		// 첫 요소를 가르킴
			remove = q->rear;	// 마지막 요소를 카르킴
			element val = remove->data;

			while (1) {
				if (pre->link == q->rear)
					break;
				pre = pre->link;  // pre를 rear전 요소를 가르키게 이동시킴
			}
			q->rear = pre;				// rear를 pre노드로 옮김
			q->rear->link = q->front;	// rear가 front를 가르킴

			free(remove); // 동적 할당 해제
			return val;   // 삭제된 요소 반환
		}
	}


}


// 맨뒤에 요소 추가 하기
void add_rear(ListDeq* q, element item) {

	// 동적할당후 초기화
	Node* new = (Node*)malloc(sizeof(Node));
	new->link = NULL;
	new->data = item;

	if (is_empty(q)) { // 첫 번째 요소라면
		q->front = new;
		q->rear = new;		// 포인터들을 new를 가르키게 변경
		new->link = new;	// 자신에게 연결 시켜줌
	}
	else {  // 첫번째 요소가 아니라면
		new->link = q->rear->link;  //rear가 가르키던곳을 new가 가르킴
		q->rear->link = new;		// rear는 new를 가르킴
		q->rear = new;				// new를 rear로 바꿔줌
	}

}

// 맨앞에 노드 삭제
element delete_front(ListDeq* q) {
	if (!is_empty(q)) // 비어있지 않다면
	{
		if (q->front == q->rear) { // 노드가 1개라면
			element val = q->front->data;
			q->front = NULL;
			q->rear = NULL;		// 노드를 NULL로 초기화
			return val;			// 노드값 반환
		}

		else {  // 노드 요소가 여러개라면
			Node* remove = (Node*)malloc(sizeof(Node));  // 제거할 노드 동적생정
			remove = q->front;				// 첫번째 노드를 가르킴
			element val = remove->data;		// 노드값 저장

			q->front = q->front->link;		// front포인터가 다음 요소를 가르킴
			q->rear->link = q->front;		// 바뀐 front요소를 rear가 가르킴
			free(remove);					// 동적할당 해제
			return val;						// 삭제된 노드값 반환

		}
	}
}


// 앞에 노드추가
void add_front(ListDeq* q, element item) {

	Node* new = (Node*)malloc(sizeof(Node)); // 추가할 노드 동적생성
	new->link = NULL; // 노드포인터 초기화
	new->data = item; // 데이터 값 초기화

	if (is_empty(q)) { // 첫번째 노드라면
		q->front = new;
		q->rear = new;		// front와 rear가 모두 new노드를 가리킴
		new->link = new;	// new에 자기 자신을 연결
	}

	else {  // 첫번째 노드가 아니라면
		new->link = q->rear->link;	// rear가 가리키던 곳을 new가 가리킴
		q->rear->link = new;		// rear는 new를 가리킴
		q->front = new;				// front를 이동시켜준다.
	}
}

// 출력함수
void print_list(ListDeq* q) {
	Node* p = NULL; // 값출력에 쓰일 포인터 생성
	if (!is_empty(q)) {
		p = q->rear->link; // p가 첫번째 요소를 가르키게 함
		do {
			printf("%c->", p->data); // 값 출력
			p = p->link;			 // 뒤노드로 이동
		} while (p != q->rear);      // rear가 아닐때까지
		printf("%c\n", p->data);	 // rear값 출력
	}
	else
		printf("빈 덱 입니다.");
}

// front 노드값 반환
element get_front(ListDeq* q) {
	return q->front->data;
}
// rear 노드값 반환
element get_rear(ListDeq* q) {
	return q->rear->data;
}

// 회문인지 검사
int check_str(ListDeq* q, char* str)
{
	for (int i = 0; i < strlen(str); i++) {
		if (delete_rear(q) != str[i]) // 뒤부터 요소 꺼내기
			return 0; // 다르다면 0반환
	}
	return 1; // 전부 같다면 1반환
}



int main()
{
	// 덱 생성
	ListDeq* q = (ListDeq*)malloc(sizeof(ListDeq));
	init_queue(q);  // 초기화
	int input = 0;  // 입력변수
	char str[100] = ""; // 문자열 선언 및 초기화

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

		for (int i = 0; i < strlen(str); i++)
			add_rear(q, str[i]); // 덱에 요소넣기

		if (check_str(q, str))
			printf("회문입니다.\n\n");

		else
			printf("회문이 아닙니다.\n\n");

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

		if (input != 1)  // 선택이 1이면 반복문 탈출
			break;
	}
	return 0;
}

 

III. 결과

 

 

 

감사합니다.

---

 

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