用栈和队列判断回文
实验二 栈和队列
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际中灵活应用。
2、掌握栈和队列的特点,即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算,如:入栈与出栈,入队与出队等运算在顺序存储结构和链式存储结构上的实现。
二、实验内容
1.请简述栈的基本特性和栈的几种基本操作的机制
栈是限定仅在表位进行插入或删除操作的线性表,栈的修改是按照后进先出的原则进行的,根据这种特性进行回文判断。
[问题描述]
对于一个从键盘输入的字符串,判断其是否为回文。回文即正反序相同。如“abba”是回文,而“abab”不是回文。
[基本要求]
(1)数据从键盘读入;
(2)输出要判断的字符串;
(3)利用栈的基本操作对给定的字符串判断其是否是回文,
若是则输出“该字符串是回文”,否则输出“该字符串不是回文”。
[测试数据]
由学生任意指定。
2.设计简单的程序实现用栈判断回文
#include
#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S){
}
void Push(SqStack &S,char e){
}
char Pop(SqStack &S,char &e){
S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; if(S.top - S.base >= S.stacksize){ S.base = (char *) realloc (S.base,(S.stacksize + STACKINCREMENT) * if(!S.base) printf("存储分配失败!"); S.base =(char *)malloc(STACK_INIT_SIZE * sizeof(char)); if(!S.base)exit(0); S.top = S.base; S.stacksize = STACK_INIT_SIZE; sizeof(char));
if(S.top == S.base) {
printf("该栈为空!"); printf("\n"); e = 'E'; }else{ e = *--S.top;
void main(){
SqStack S;
InitStack(S);
char a[30];
char c;
char e;
int k = 0;
printf("请输入要转换的字符串, 以#号结束:\n");
for(int i = 0;i
scanf("%c",&c); if(c != '#'){ a[i] = c; }else{ break; }
} return e; } k = i; }
for(int h = 0 ; h
Push(S,a[h]);
}
int g = 0; //定义一个计数器
for(int w = 0;w
}
printf("\n");
if(g == k){ //判断计数器的值与输入的数值是否相等 printf("YES");//相等的话打印出YES
}else{ char x = Pop(S,e); printf("%c",x); if(a[w] == x){//比较数组中的第w 个值与栈中返回的第w 个值是否相等 g++; //若相等的话,计数器加一 }
printf("NO");//否则打印出NO
}
printf("\n");
}运行结果如下图:
1.输入字符为回文字符
2.输入字符不是回文字符
三、编程并上机调试运行
四、时间、地点
五、指导教师
(在书写过程中若出现错误,望老师指出,谢谢)