【数据结构】判定给定的字符序列是否为回文

产出：

CSDN 技术博客 1 篇
哔哩哔哩专栏1篇

问题

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。是回文。试写一个算法判定给定的字符序列是否为回文。

思路

总思路：将所有元素进栈，然后依次出栈与数组元素比较
具体步骤
1、键盘输入需要判断的字符串存放在数组中
2、将数组中的元素依次进栈
3、栈顶元素出栈与数组元素比较
效果相当于
a[3]
a[0]与a[2]比较
a[1]与a[1]比较
a[2]与a[0]比较

代码如下：

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

#define MAXSIZE 1024//定义顺序栈的最大长度
#define n 1024//定义数组长度

typedef char elem;
typedef struct SqStack
{
	elem data[MAXSIZE];					  //创建数组栈
	int top;							  //栈顶指针
}SqStack;

//顺序栈初始化
int Init_SqStack(SqStack *&S)
{
	S = (SqStack*)malloc(sizeof(SqStack));//申请空间
	if(S == NULL)
	{
		printf("申请分配空间失败\n");
		return 0;						//失败返回0
	}
	S -> top = -1;						//将-1赋值给栈顶指针
	return 1;
}

//判断栈是否已满
int Full_SqStack(SqStack *S)
{
	if(S -> top == MAXSIZE -1)//数组由0开始计
	{
		return 1;			  //栈满返回1
	}
	else
	{
		return 0;			  //栈未满返回0
	}
}

//判断是否为空栈
int Empty_SqStack(SqStack *S)
{
	if(S -> top == -1)
	{
		return 1;			  //空栈返回1
	}
	else
	{
		return 0;			  //非空栈返回0
	}
}

//进栈
void Push_SqStack(SqStack *&S, elem e)
{
	if(Full_SqStack(S) == 1)		//判断栈是否已满
	{
		printf("栈已满，不能进行进栈操作\n");
		return;
	}
	S -> top++;						//栈顶指针+1
	S -> data[S -> top] = e;		//元素进栈
}

//出栈
int Pop_SqStack(SqStack *S, elem &e)
{
	if(Empty_SqStack(S) == 1)//判断是否为空栈
	{
		printf("该栈是空栈, 无数据元素\n");
		return 0;			//为空栈返回0，出栈失败
	}
	e = S -> data[S -> top];//栈顶元素出栈
	S -> top--;				//栈顶指针减一
	return 1;				//出栈成功返回1
}

//判断是否为回文
int Symmetry(elem a[])
{
	elem e;
	SqStack *S;
	Init_SqStack(S);		 //初始化顺序栈
	for(int i = 0; a[i]; i++)//数组中的元素依次进栈
		Push_SqStack(S, a[i]);
	for(int i = 0; a[i]; i++)//顺序栈中栈顶元素依次出栈
	{
		Pop_SqStack(S, e);
		if(a[i] != e)//判断a[i]是否与栈顶元素相同
			return 0;//不相同直接返回0
	}
	return 1;
}


int main()
{
	printf("请输入需要判断的字符串\n");
	elem a[n];		//定义长度为n的
	gets(a);		//键盘输入需要判断的字符串
	if(Symmetry(a))//如果Symmetry(a)的返回值，为1则执行printf("该字符串是回文\n");
	{
		printf("该字符串是回文\n");
	}
	else			//否则执行printf("该字符串不是回文\n");
	{
		printf("该字符串不是回文\n");
	}
	return 0;
}

如有错误，欢迎读者批评指正。
如有疑问，可在下方留言。