栈和队列的基本操作及其应用.doc

《栈和队列的基本操作及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容1、问题描述对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。2、基本要求（1）数据从键盘读入；（2）输出要判断的字符串；（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。3、代码附录#inclu

2、de#include#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE100#defineOK1#defineERROR0typedefcharQElemType;typedefcharSElemType;typedefstructSqStack{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacks

3、ize;//当前已分配的存储空间，以元素为单位}SqStack;typedefstructSqQueue//构造队链{QElemType*base;intfront;intrear;}SqQueue;intInitStack(SqStack&S)//构造一个空栈S{S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)//存储分配失败{cout<<"存储分配失败!"<

4、;cout<<"已成功建立空栈S!"<S.stacksize)//栈满追加存储空间{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT*sizeof(SElemType)));if(!S.base){cout<<"存储空间已满!"<

5、CKINCREMENT;}*S.top++=e;return(1);}intStackEmpty(SqStack&S)//若栈空返回OK否则返回error{if(S.top==S.base)return(1);elsereturn(0);}intPop(SqStack&S,SElemType&e)//若栈不空则删除栈顶元素用e返回其值并返回OK否则返回error{if(S.top==S.base){cout<<"Underflow!"<

6、个空队链Q{Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base){cout<

7、urn(ERROR);//存储分配失败}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return(OK);}intDeQueue(SqQueue&Q,QElemType&e)//若栈不空则删除Q的队头元素用e返回其值并返回OK否则返回error{if(Q.front==Q.rear){cout<