假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文.试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”.

题目

假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文.试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”.

答案

以前写的,用循环队列和顺序栈实现的
也可以用指针实现
分别有两个指针,一个指向开始,一个指向结尾,各取一个字符比较,相等的话,前边的向后移动一个,后边的向前移动一个,直到两个指针指向同一个位置,则为回文,中途要是不相等或者最后没有指向同一个位置,则不是回文
////
//数据结构:循环队列和顺序栈
//算法思想:
//1.将字符串按照用户输入的顺序分别入栈和队列
//2.分别从队列和栈中取出首个字符
//3.比较取出的字符,若相等,继续分别从队列和栈中取首个字符；否则跳出循环,并设置标志flag=0;
//4.若队列和栈中的字符取完,则结束,设置标志flag=1;
//5.flag=1,表示字符从前往后和从后往前的序列完全匹配,该字符串属于回文
//6.flag=0,表示字符从前往后和从后往前的序列不完全匹配,该字符串不属于回文
#include
#include
#define m 100
typedef struct
{
char stack[m];
int top;
}stackstru; // 定义栈
typedef struct {
char queue[m];
int front;
int rear;
}queuestru; //定义队列
void main()
{
//函数声明
int stinit(stackstru *s); //初始化顺序栈
int stempty(stackstru *s); //判断栈是否为空
int stpush(stackstru *s,char x); //入栈
char stpop(stackstru *s); //出栈
int quinit(queuestru *q); //初始化循环队列
int quempty(queuestru *q); //判断队列是否为空
int enqueue(queuestru *q,char e); //入队
char dequeue(queuestru *q); //出队
//
char c;
int flag=0;
stackstru *s=(stackstru *)malloc(sizeof(stackstru)); //为顺序栈申请空间
queuestru *q=(queuestru *)malloc(sizeof(queuestru)); //为队列申请空间
stinit(s); //初始化栈
quinit(q); //初始化队列
printf("Input a string:\n");//输入字符串,输入@标示输入结束.
while((c=getchar())!='@') //将输入的字符串入栈和队列
{
putchar(c); //输出输入的字符
stpush(s,c); //字符进栈
enqueue(q,c); //字符进队列
}
printf("\n");
printf("End input!\n"); //提示信息
while(stempty(s)) //栈中还有元素
{
if(stpop(s)==dequeue(q)) //出栈的字符与出队列的字符匹配
{
flag=1; //将标志设置为1
continue; //继续从栈和队列中区字符
}
else //字符不匹配
{
flag=0;
break; //跳出循环,将标志设置为0
}
}
if(flag==1)
printf("This string is palindrome!\n"); //标志位为1,完全匹配,是回文

else
printf("This string isn't palindrome!\n");//标志位为0,不完全匹配,不是回文
}
int stinit(stackstru *s)
{
s->top=0;
return 1;
} //初始化栈
int stempty(stackstru *s)
{
if(s->top==0) //栈顶为空
{
return 0;
}
else
{
return 1;
}
} //判断栈是否空
int stpush(stackstru *s,char x)
{
if(s->top==m) //栈满
{
printf("The stack is overflow!\n"); //输出提示信息
return 0;
}
else //栈未满
{
s->top=s->top+1; //栈顶后移
s->stack[s->top]=x; //字符入栈
return 1;
}
} //入栈操作
char stpop(stackstru *s)
{
char y;
if(s->top==0) //栈为空
{
printf("The stack is empty!\n"); //输出提示信息
return ' '; //返回空格
}
else //栈不为空
{
y=s->stack[s->top]; //取出栈顶元素
s->top=s->top-1; //栈顶指示移动
return y;
}
} //出栈操作
int quinit(queuestru *q)
{
q->front=0;
q->rear=0;
return 1;
} //初始化为一个空的循环队列
int quempty(queuestru *q)
{
if(q->front==q->rear) //队头和队尾相等
{
return 0;
}
else
{
return 1;
}
} //判断队列是否为空
int enqueue(queuestru *q,char e)
{
if((q->rear+1)%m==q->front) //队列已满
{
printf("The queue is overflow!\n"); //提示信息
return 0;
}
else
{
q->queue[q->rear]=e; //入队
q->rear=(q->rear+1)%m; //移动队尾指针
return 1;
}
} //入队操作
char dequeue(queuestru *q)
{
char f;
if(q->front==q->rear) //队列为空
{
printf("The queue is empty!\n"); //提示信息
return 0;
}
else
{
f=q->queue[q->front]; //取出队首元素
q->front=(q->front+1)%m; //移动对头指针
return f;
}
} //出队操作