实验二-栈队列算法设计.doc

《实验二-栈队列算法设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二栈、队列的实现、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。二、实验要求1实验之前认真准备，编写好源程序。2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3不断积累程序的调试方法。三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：1、设线性表A中有n个字符，试设计

2、程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。提高题：1、试编写程序：a.将中缀表达式计算转换成后缀表达式。b.后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。四．实验代码基础题1#include#include#includeconstSTACK_INIT_SIZE=100;//存储空间初始分配量constSTACKINCREMENT=10;//存储空间分配增量typedefstruct{in

3、t*base;//在构造之前和销毁之后，base的值为NULLint*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;voidInitStack(SqStack&S){//构造一个空栈SS.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)exit(0);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;cout<<"初始化完毕"<

4、ackvoidGetTop(SqStackS,int&e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top==S.base){cout<<"此栈为空!!!"<S.stacksize){//栈满，追加存储空间S.base=(int*)reallo

5、c(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base){cout<<"新分配空间失败！！！"<

6、.top){cout<<"此栈为空栈，无法删除！！！"<

7、t<>n;Stack.stacksize=n;do{cout<<"请选择操作："<>m;switch(m){case1:while(1){cout<<"doyouwantt

8、oinputsomeelements?(y/n)"<>c;if(c=='n')break;elsecout<<"pleaseenteroneelement"<>z;if(i==Stack.stacksize){cout<<"Sorry!