3-1データ構造-スタック

stack

コンセプト

アレイスタック

課題-1（使用案）

#include <stdio.h>
#include <string.h>						//strlen, strcmp

enum { MAX = 32, TRUE = 1, FALSE = 0,
	PALINDROME = 11, NOT_PALINDROME = 12,
	SIZE_ERROR = -32 };

char stack[MAX];						//스택
int top = -1;							//스택 제일 위에 있는 원소 번호
int Push(char c);						//문자 하나씩 push
char Pop();								//pop과 동시에 top에 있던 문자 리턴
int Check(char a[], char b[], int n);	//단어를 앞과 뒤로 읽어도 같은지 판단

int Push(char c)
{
	if (top < MAX / 2 - 1) {			//MAX/2의 값보다 1이 작아야 공간추가 가능
		top++;
		stack[top] = c;
		return TRUE;
	}
	else
		return FALSE;
}

char Pop()
{
	if (top > -1)
		return stack[top--];
	else
		return FALSE;
}

int Check(char a[], char b[], int n)
{
#ifdef DEBUG
	printf("strcmp value: %d\n", strncmp(a, b, n));
#endif
	if (strncmp(a, b, n) == 0) {
		printf("palindrome\n");
		return PALINDROME;
	}
	else {
		printf("not palindrome\n");
		return NOT_PALINDROME;
	}
}

int main()
{
	char input[MAX];
	char temp[MAX / 2 + 1];				//널문자 공간 추가를 위해 +1
    int i;
	scanf("%s", input);

	int size = (int)strlen(input);
	if (size > MAX) {
		puts("단어가 32자를 초과하였습니다.\n");
		return SIZE_ERROR;
	}

	for (int i = size / 2; i < size; i++) {
		Push(input[i]);
#ifdef DEBUG
		printf("%c ", input[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif
	for (i = 0; i < size / 2; i++) {	//임시공간에 그대로 팝해서 a b c d 입력
		temp[i] = Pop();
#ifdef DEBUG
		printf("%c ", temp[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif

	temp[i+1] = '\0';					//문자열 끝에 널문자 대입
	Check(input, temp, strlen(temp));	//strncmp을 이용해서, temp의 길이만큼
										//처음 입력받은 input 문자열과 temp 문자열을 비교
										//strlen은 널문자 제외한 문자열 길이
	return 0;
}              

接続リストスタックの使用

課題-1（接続リスト使用）

#include <stdio.h>
#include <string.h>				//strlen, strcmp
#include <stdlib.h>				//malloc, free

enum { MAX = 32, TRUE = 1, FALSE = 0, EMPTY_ERROR = -99,
	PALINDROME = 11, NOT_PALINDROME = 12,
	SIZE_ERROR = -32 };

typedef struct stack {			//연결리스트 노드 구조체
	char data;					//문자
	struct stack* link;			//다음 노드의 주소값을 저장할 포인터 변수
} stack;

stack* top;						//스택의 맨 위의 노드 주소를 저장할 포인터 변수 (기본값 NULL)
int isEmpty();					//스택이 공백 상태인지 검사
void Push(char data);
char Pop();

int isEmpty()
{
	if (top == NULL) {			//top이 아무것도 가르키지 않는 경우
		puts("스택이 비어있습니다.");
		return EMPTY_ERROR;
	}
    return 0;
}

void Push(char data)
{
	//새로운 노드 s 동적 할당
	stack* s = (stack *)malloc(sizeof(stack));
	s->data = data;				//s의 data에 값(단어의 알파벳 한 문자) 저장
	s->link = top;				//s의 link에 맨 위의 노드 주소 저장
								//(top이 맨 위의 노드 주소를 가지고 있음)
	top = s;					//이제 s가 맨위노드가 되었으므로 top에 s 주소 저장
}

char Pop()
{
	if (!isEmpty()) {			//배열이 비어있지 않은 경우
		stack* temp = top;		//temp 포인터를 선언해 맨 위 노드의 주소값을 저장
		char ch = temp->data;	//ch 변수를 새로 선언하여 맨 위 노드의 데이터 저장
		top = temp->link;		//top 포인터에 2번째 노드(맨 위 다음 노드)의 주소값 저장
		free(temp);				//맨 위 노드 제거
		return ch;				//문자 리턴
	}
	else
		return 0;
}

/////////////////////////////////아래부터는 배열을 이용한 스택 풀이와 같음
int Check(char a[], char b[], int n)
{
#ifdef DEBUG
	printf("strcmp value: %d\n", strncmp(a, b, n));
#endif
	if (strncmp(a, b, n) == 0) {
		printf("palindrome\n");
		return PALINDROME;
	}
	else {
		printf("not palindrome\n");
		return NOT_PALINDROME;
	}
}

int main()
{
	char input[MAX];
	char temp[MAX / 2 + 1];			//널문자 공간 추가를 위해 +1
    int i;
	scanf("%s", input);

	int size = (int)strlen(input);
	if (size > MAX) {
		puts("단어가 32자를 초과하였습니다.\n");
		return SIZE_ERROR;
	}

	for (int i = size / 2; i < size; i++) {
		Push(input[i]);
#ifdef DEBUG
		printf("%c ", input[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif
	for (i = 0; i < size / 2; i++) {	//임시공간에 그대로 팝해서 a b c d 입력
		temp[i] = Pop();
#ifdef DEBUG
		printf("%c ", temp[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif

	temp[i+1] = '\0';					//문자열 끝에 널문자 대입
	Check(input, temp, strlen(temp));	//strncmp을 이용해서, temp의 길이만큼
										//처음 입력받은 input 문자열과 temp 문자열을 비교
										//strlen은 널문자 제외한 문자열 길이
	return 0;
}