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

《实验二栈和队列的基本操作及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计科092刘亚红20090814212实验二栈和队列的基本操作及其应用一、实验内容回文判断[问题描述]对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。[基本要求]（1）数据从键盘读入；（2）输出要判断的字符串；（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。二、概要设计算法设计：实验要求用栈的基本基本操作实现判断是否为回文，则必须定义栈的初始化和出栈、入栈；另外为了判断是否是回文，则定义一个数组，便于比较。在字符串输入的时

2、候，保证同时进入数组和栈里。因为栈的后进先出的输出特性，在比较的时候，用while语句判断：当栈输出的元素和数组的对应的元素相等，就继续比较，直到比较完毕，相等则输出YES，在比较的过程中，若有一个不相等，则输出NO。而判断while语句结束的条件有两个:一是在比较的过程中，如果有不相等的两个元素，输出“NO”，跳出while语句；二是正常结束，即字符串和栈里储存的元素完全相等，则输出YES。流程图：8计科092刘亚红20090814212开始定义数组　初始化栈输入字符ｃ是ＨＩ　s!='#'将字符同时进入数组和栈输入字符ｃｉ加１

3、否是栈为不空是 出栈的元素和数组第ｊ个元素相等ｊ＋＋否输出ＮＯ否输出ＹＥ结束8计科092刘亚红20090814212算法：主函数Main（）字符串入栈Push(Sqstack&S,SElemTypee)字符串出栈Pop(Sqstack&S)栈的判空Isempty(SqstackS)栈的初始化Initstack(Sqstack&S)模块：在分析了实验要求和进行了算法分析之后，可以将程序分成五个功能函数，分别如下:首先定义一个栈：typedefstruct{SElemType*base;SElemType*top;intstacks

4、ize;}Sqstack;Initstack(Sqstack&S):构造一个空栈，便于存储元素，即栈的初始化：S.base=(SElemType*)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=MAX;returnOK;Push(Sqstack&S,SElemTypee)：实现插入元素e成为新的栈顶元素。在程序里它实现了将元素输入到栈里的功能。charPush(Sqstack&S,SElemTypee)8计科092

5、刘亚红20090814212{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++;returnOK;Pop(Sqstack&S)：该函数是删除栈

6、S的栈顶元素。在程序里，充当了输出栈里元素的功能。便于和字符串的元素比较：charPop(Sqstack&S){if(S.top==S.base)return0;elsereturn*--S.top;}Isempty(SqstackS)：该函数是判断栈里是否还有元素。在主函数里while判断语句里充当重要的作用是判断while语句执行与否的条件，当栈不为空的时候，就执行while语句，为空的时候就执行if语句输出YES：if(S.base==S.top)return0;intmain(void)：这是程序的主要部分。在主函数里，

7、定义了一个数组。在输入元素的时候要同时输入数组和栈里，便于以后的操作：cin>>s;while(s!='#'){//字符串入栈Input[i]=s;8计科092刘亚红20090814212Push(S,s);cin>>s;i++;}千万要记得在while语句的结束要再输入元素，否则这个输入就无效了。接下来就是最重要的部分，判断是否是回文，利用while循环惊醒判断：while(Isempty(S)){//字符依次出栈和字符数组比较，判断是否回文数if(Pop(S)==Input[j]){j++;}else{cout<<"NO"<

8、