实验二栈和队列

《实验二栈和队列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二栈和队列的算法实现•、实验目的与要求1）复习栈的存储结构2）复习队列的存储结构3）实现栈和队列的主要基木操作4）练习栈和队列的简单应用二、实验内容1、自行编写或根据参考代码编写，实现的初始化、入栈、出栈、判断栈空操作。2、自行编写或根据参考代码编写，实现队列的初始化、入队、出队操作。3、请使用给定的栈基本操作实现（请参阅附录）数的16以内的任意进制转换。4、请使用给定的栈基本操作实现括号判定问题。5、请使用给定的队列基本操作解决如下问题：假设称正读和反读都相同的字符序列为“回文”,例如，‘abba'和Sbcba'是回文，'abcd

2、e'和'ababab'则不是回文。试写一个算法判别读入的一个以@为结束符的字符序列是否是“冋文”。编程实现该程序。［实现提示］输入：需要进行判断的字符序列输出：回文判断结果要求能够实现多次字符串回文判断，即实现循环菜单。注：学生在编写程序时可以参观教材、网上资源或举手提问。严禁玩游戏或利用计算机做任何与实验内容无关的事情。三、实验结果验收1、完成后，要求教师查看实验设计结果，是否达到要求2、教师将以抽查语句含义的形式进行验收，学生应能回答语句的作用及含义3、课后完成实验报告，实验报告中应包含实验内容和主要的源代码。附录堆栈源代码：#de

3、fineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造Z前和销毁Z后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;/*顺序栈*/StatusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemType*)malloc(S

4、TACK」NIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack*S){/*销毁栈S,S不再存在*/free((*S).base);(*S)・base二NULL;(*S).top二NULL;(*S).stacksize=O;returnOK;1StatusClearStack(SqStac

5、k*S){/*把S置为空栈*/(*S).top=(*S)・base;returnOK;}StatusStackEmpty(SqStackS){产若栈S为空栈，则返冋TRUE,否则返冋FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){/*返回S的元素个数，即栈的长度*/returnS.top-S.base;}StatusGetTop(SqStackS,SElemType*e){/*若栈不空，则用e返冋S的栈顶元素，并返冋OK；否则返冋E

6、RROR*/if(S.top>S.base){*e=*(S.top・l);returnOK;}elsereturnERROR;}StatusPush(SqStack*S,SElemTypee){/*插入元素e为新的栈顶元素勺if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)ex

7、it(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).smcksize+二STACKINCREMENT;}*((*S)・top)++二e;returnOK;}StatusPop(SqStack*S,SElemType*e){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*・・(*S).top;returnOK;StatusStackTraverse(SqSt

8、ackS，Status(*visit)(SElemType)){/*从栈底到栈顶依次对栈中每个元素调用函数visitOo*//*—旦visit。失败,则操作失败*/while(S.top>S.base)vi