Question

用堆栈来判断一串字符是不是回文

Answer 1

#include"stdio.h" //定义标准输入输出函数
#include "stdlib.h" //标准库
#define maxsize 100 //顺序栈所能存储元素的最大数

typedef char datatype; //datatype是栈中数据元素的类型

typedef struct{ //定义结构体
datatype stack[maxsize]; //定义栈的存储结构
int top; // 指向栈顶元素
}sqstack; //顺序栈的类型定义

sqstack *S; //顺序栈的变量定义

void InitStack() //定义栈
{
S->top=-1; //将顺序栈设置为空栈
}

void Push(char e){ //定义进栈函数
if(S->top>=maxsize-1) //检查顺序栈是否为满栈
{
printf("栈满溢出错误！\n"); //若顺序栈已满，则终止程序运行
}
else
{S->top++; //将栈顶指针加1，使之指向空单元
S->stack[S->top]=e; //将新结点插入栈顶指针所指的单元中
}
}

void Pop(char &e){ //定义出栈函数
if(S->top<0) //检查顺序栈是否为空栈
{
printf("下溢错误!"); //若顺序栈为空栈，则终止程序运行
}
else //若顺序栈非空，则取栈顶元素删除之
{e=S->stack[S->top]; //暂存栈顶元素以便返回调用者
S->top--; //将栈顶指针减1，即删除栈顶元素
}
}
int StackEmpty() //检查顺序栈是否为空栈运算
{
if(S->top<0) return 1; //若顺序栈为空，则函数返回1
else return 0; //若顺序栈非空，则函数返回0
}
typedef struct QNode{ //队列结点类型
char data; //链队列的数据域
struct QNode *next; //链队列的指针域
}qnode; //队列的结点类型定义

typedef struct{ //队列的存储结构
qnode *front; //链队列头指针
qnode *rear; //链队列尾指针
}linkqueue; //队列的类型说明

linkqueue Q;

void InitQueue()
{
Q.front=Q.rear=(qnode*)malloc(sizeof(qnode)); //建立队列
}

void EnQueue(char &e) //元素插入队尾函数（入队）
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode)); //开辟新结点
p->data=e; //给新结点的数据域赋值
p->next=NULL; //给新结点的指针域赋值
Q.rear->next=p; //将新结点插入表尾
Q.rear=p; //将尾指针指向新结点
}

void DeQueue(char &e) //删除对头元素（出队）
{ qnode *p; //删除对头结点，返回原对头结点数据值
if (Q.front==Q.rear) //若队空，则无法进行出队运算
printf("队列为空！\n"); //先检查链接队列是否为空队
p=Q.front->next; //指针p指向原队列的第一个结点
e=p->data; //保存原第一个结点的数据值
Q.front->next=p->next; //删除原队列第一个结点
if(Q.rear==p) //当对头结点为尾结点时
Q.rear=Q.front; //将尾结点赋值给头结点
free(p); //释放原队列的结点空间
}

int judge() //判别输入的字符串是否回文序列,是则返回1,否则返回0
{
char a,b,c; //a,b,c分别为出栈字符串，出队字符串和输入字符串
S=(sqstack *)malloc(sizeof(sqstack)); //申请内存
InitStack(); //初始化堆栈
InitQueue(); //初始化队列

while((c=getchar())!=‘\n') //输入字符串
{ //同时使用栈和队列两种结构
Push(c); //输入字符（进栈）
EnQueue(c); //输入字符（入队）
}
while(!StackEmpty()) //若顺序栈非空
{
Pop(a); //出栈
DeQueue(b); //出队
if(a!=b) //出栈与出队后的字符串不完全相同时
{
printf("\n (╯_╰) NO! 您所输入的字符串不是回文! \n\n"); //输出"不是回文"
return 0; //函数返回0
}
}
printf("\n (∩_∩) YES! 您所输入的字符串是回文! \n\n"); //出栈与出队后的字符串完全相同时，输出"是回文"
return 1; //函数返回1
}

void main() //定义主函数
{
printf(" *****欢迎您使用本程序，请输入需要进行回文判断的字符串,并按回车键结束!*****\n\n");
//用户窗口提示 输入字符串，以回车键结束
judge(); //执行判断函数
}