实验二-栈队列算法设计

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

2、称，例如xyzyx和xyzzyx都是中心对称的字符串。提高题：1、试编写程序：a.将中缀表达式计算转换成后缀表达式。b.后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。四实验代码基础题1#include <iostream.h>#include <conio.h>#include <stdlib.h>const STACK_INIT_SIZE=100;/存储空间初始分配量const STACKINCREMENT=10;/存储空间分配增量typedef structint *base;/在构造之前和销毁之后，base的值

3、为NULLint *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单位SqStack;void InitStack(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<<"初始化完毕"<<endl;/InitStackvoid GetTop(SqStack S,int &e)/

4、若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top=S.base)cout<<"此栈为空!"<<endl;exit(0);e=*(S.top-1);cout<<e<<endl; cout<<"取值结束"<<endl;/GetTopvoid Push(SqStack &S,int e)/插入元素e为新的栈顶元素if(S.top-S.base>S.stacksize)/栈满，追加存储空间S.base=(int *)realloc(S.base,

5、(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)cout<<"新分配空间失败！"<<endl;exit(0);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+=e; cout<<"插入元素成功"<<endl;/Pushvoid Pop(SqStack &S,int &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S

6、.base=S.top)cout<<"此栈为空栈，无法删除！"<<endl;exit(0);e=*-S.top; cout<<"删除成功！"<<endl;/Popvoid ClearStack(SqStack &S)/把S置为空栈if(S.base=S.top)cout<<"此栈已经为空!"<<endl;S.top=S.base;/ClearStackint visit(int *p)return *p;void Traverse(SqStack S)in

7、t *p;p=S.base;while(p!=S.top)cout<<visit(p)<<" "p+;cout<<endl;void main()SqStack Stack;int m,n,x,y,z,i=0;char c;InitStack(Stack);cout<<"请输入您要建立的栈的大小："<<endl;cin>>n;Stack.stacksize=n;docout<<"请选择操作："<<endl;cout<<"

8、; "<<"1，进栈 2，出栈 3，查看栈顶值 4，清空栈 5，退出"<<endl;cin>>m;switch(m)case 1:while(1)cout<<"do you want to input some elements?(y/n)"<<endl;cin>>c;if(c='n')break;else cout<<"please enter one element"<<endl;cin>>z;if

9、(i=Stack.stacksize)cout<<"Sorry!"<<endl<<"the stack is overflow!"<<endl<<"exit!"<<endl;exit(0); Push(Stack,z);i+; cout<<"the stack is:" Traverse(Stack); break;case 2:Pop(Stack,x);cout<<x<<"出栈"<

10、<endl;break;case 3:cout<<"栈顶值为："<<endl;GetTop(Stack,y);break;case 4:ClearStack(Stack);break;case 5:cout<<"Exit!"<<endl;break;default:cout<<"输入错误！此程序将退出！"<<endl;exit(0);/switchwhile(m!=5);getch();基础题2#include <iostream.h>#incl

11、ude <conio.h>#include <stdlib.h>/队空、入队和出队int n=0;typedef struct Qint data;Q *next;Q,*QLink;void InitQ(QLink &q)/构造一个队列q->next=q;/InitQvoid Push(QLink &q,int &e)/入队QLink p;p=new Q;p->data=e;p->next=q->next;q->next=p;n+;/Pushvoid OutQ(QLink &q,int &e)/出队Q

12、Link p;QLink t;p=new Q;t=new Q;p=q;int i;for(i=0;i<=n;i+)if(p->next->data=e)t=p->next;p->next=t->next;delete t;break;/ifp=p->next;/forif(i=(n+1)cout<<"您所输入的值不存在！此程序将退出！"<<endl;exit(0);/OutQvoid ClearQ(QLink &q)/置队空q->next=q;/ClearQvoid checkQ(QLink &

13、amp;q,int &e)/查看队尾元素if(q->next=q)cout<<"此队列为空！程序将退出！"<<endl;exit(0);e=q->next->data;/checkvoid main()int m,x,n,y,e;QLink Qu;Qu=new Q;InitQ(Qu);docout<<"请选择操作："<<endl;cout<<"1,入队 2，出队 3，查看队尾元素 4，清空队列 5，退出 "<<endl;cin>>x;switch(x)case 1:cout<<"请输入您想插入的值："<<"t"cin>>m;Push(Qu,m);break;case 2:cout<<"请输入您想出队的值："<<"t"cin>>n;OutQ(Qu,n);cout<<n<<