实验二 栈和队列的基本操作及其应用

实验二 栈和队列的基本操作及其应用

一、实验内容

回文判断

[问题描述]

对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。

[基本要求]

（1）数据从键盘读入； （2）输出要判断的字符串；

（3）利用栈的基本操作对给定的字符串判断其是否是回文，

若是则输出“Yes”，否则输出“No”。

二、概要设计 算法设计：

实验要求用栈的基本基本操作实现判断是否为回文，则必须定

义栈的初始化和出栈、入栈；另外为了判断是否是回文，则定义一个数组，便于比较。在字符串输入的时候，保证同时进入数组和栈里。因为栈的后进先出的输出特性，在比较的时候，用while语句判断：当栈输出的元素和数组的对应的元素相等，就继续比较，直到比较完毕，相等则输出YES，在比较的过程中，若有一个不相等，则输出NO。而判断while语句结束的条件有两个:一是在比较的过程中，如果有不相等的两个元素，输出“NO”，跳出while语句；二是正常结束，即字符串和栈里储存的元素完全相等，则输出YES。

流程图：

计科 092

刘亚红

20090814212

开始

定 义 数 组 初始化栈

输入字符c

s!='#' 否 是 将字符同时进入 数组和栈

输入字符c i加1

栈为不空 否 是

出栈的元素和数 组第j个元素相等

否 是 j++

输出NO

结束

输出YE

算法：

模块：

在分析了实验要求和进行了算法分析之后，可以将程序分成五

个功能函数，分别如下: 首先定义一个栈： typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack;

Initstack(Sqstack &S):构造一个空栈，便于存储元素，即栈的初始化：

S.base=(SElemType*)malloc(MAX*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base;

S.stacksize=MAX; return OK;

Push(Sqstack &S, SElemType e)：实现插入元素e成为新的栈顶元素。在程序里它实现了将元素输入到栈里的功能。 char Push(Sqstack &S, SElemType e)

{

if(S.top-S.base>=S.stacksize) {//栈满，追加存储空

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT; }//

*S.top=e; S.top++; return OK;

Pop(Sqstack &S)：该函数是删除栈S的栈顶元素。在程序里，充当了输出栈里元素的功能。便于和字符串的元素比较： char Pop(Sqstack &S) {

if(S.top==S.base) return 0; else

return *--S.top; }

Isempty(Sqstack S)：该函数是判断栈里是否还有元素。在主函数里while判断语句里充当重要的作用是判断while语句执行与否的条件，当栈不为空的时候，就执行while语句，为空的时候就执行if语句输出YES： if(S.base==S.top) return 0;

int main(void)：这是程序的主要部分。在主函数里，定义了一

个数组。在输入元素的时候要同时输入数组和栈里，便于以后的操作： cin>>s; while(s!='#') {//字符串入栈 Input[i]=s;

Push(S,s); cin>>s; i++; }

千万要记得在while语句的结束要再输入元素，否则这个输入就无效了。接下来就是最重要的部分，判断是否是回文，利用while循环惊醒判断： while(Isempty(S))

{//字符依次出栈和字符数组比较，判断是否回文数 if(Pop(S)==Input[j]) { j++; } else {

cout<<"NO"<<endl; break; } }

if(!Isempty(S))

cout<<"YES"<<endl;

特别需要注意的是，循环语句的判断条件Isempty(S)的使用。三 、测试数据

测试一:ABBA# 测试二：ABCD# 四、结果调试 测试一的结果

:

测试二的结果:

五．总结

通过这次实验，复习了栈的几种基本操作。在编程的过程中，遇到了种种的问题：刚开始，自己采用了栈和数组的形式，可是却在键盘输入元素是遇到问题，不知道该如何解决，直到询问同学之后才明白。但是就算自己编程没错误，可是在测试的时候，一直输出是回文的字样，不知道错误出现在哪，没办法就一步一步的试，才知道是循环条件出现了毛病。修改之后，才运行成功。 在这次实验过后，我明白我们的语言描述和C语言描述就算有一点的差别，就会导致不同的结果，所以在编程的过程中，要谨慎、小心，才不会出错。 六、附录：

#include<iostream.h> #include<stdlib.h> #include<string.h>

typedef char SElemType;

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0

#define OVERFLOW 0 #define MAX 100

typedef char SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack;

char Initstack(Sqstack &S) {////////

S.base=(SElemType*)malloc(MAX*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base;

S.stacksize=MAX;

return OK; }

///////////////////////////////为栈插入元素 char Push(Sqstack &S, SElemType e) {

if(S.top-S.base>=S.stacksize) {

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT; }

*S.top=e; S.top++; return OK; }

//////////////////////////删除栈顶元素 char Pop(Sqstack &S) {

if(S.top==S.base) return 0; else

return *--S.top; }

////////////////////////////////////判空 bool Isempty(Sqstack S) {

if(S.base==S.top) return 0; }

int main(void) {

char s,Input[MAX]; Sqstack S;

int i=0; int j=0;

Initstack(S);//初始化栈 cin>>s;

while(s!='#') {//字符串入栈 Input[i]=s; Push(S,s); cin>>s; i++; }

while(Isempty(S))

{//字符依次出栈和字符数组比较，判断是否回文数 if(Pop(S)==Input[j]) { j++; } else {

cout<<"NO"<<endl; break; } }

if(!Isempty(S))

cout<<"YES"<<endl; return OK; }

本文来源：https://www.bwwdw.com/article/06o4.html