数据结构-实验二-栈、队列算法设计

中国矿业大学计算机科学与技术系试验报告课程名称________数据结构_______试验名称____栈、队列算法设计_________________班级____信息平安08-1_____姓名___________学号___________仪器组号_______实验日期___09-11-18___实验报告要求：1.实验目的2.实验内容3.实验步骤4.程序清单5.运行结果6.流程图7.实验体会一实验目的1熟悉栈、队列这种特殊线性结构的特性；2熟练掌握栈、队列在顺序存储结构和链表存储结构下的根本操作。二、实验要求：1实验之前认真准备，编写好源程序。2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3不断积累程序的调试方法。三、实验内容基此题〔必做〕：1分别就栈的顺序存储结构和链式存储结构实现栈的各种根本操作。2假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：3设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。四、程序清单基此题:1.#include<iostream.h>#include<conio.h>#include<stdlib.h>constSTACK_INIT_SIZE=100; //存储空间初始分配量constSTACKINCREMENT=10; //存储空间分配增量typedefstruct{ int*base; //在构造之前和销毁之后，base的值为NULL int*top; //栈顶指针 intstacksize; //当前已分配的存储空间，以元素为单位}SqStack;voidInitStack(SqStack&S){ //构造一个空栈S S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) exit(0); //存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; //cout<<"初始化完毕"<<endl;}//InitStackvoidGetTop(SqStackS,int&e){ //假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERROR if(S.top==S.base) { cout<<"此栈为空!!!"<<endl; exit(0); } e=*(S.top-1); cout<<e<<endl;// cout<<"取值结束"<<endl;}//GetTopvoidPush(SqStack&S,inte){ //插入元素e为新的栈顶元素 if(S.top-S.base>S.stacksize){//栈满，追加存储空间 S.base=(int*)realloc(S.base,(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;}//PushvoidPop(SqStack&S,int&e){ //假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回OK；否那么返回ERROR if(S.base==S.top) { cout<<"此栈为空栈，无法删除！！！"<<endl; exit(0); } e=*--S.top;// cout<<"删除成功！！！"<<endl;}//PopvoidClearStack(SqStack&S){ //把S置为空栈 if(S.base==S.top) cout<<"此栈已经为空!!!"<<endl; S.top=S.base;}//ClearStackvoidmain(){ SqStackStack; intm,n,x,y,z,i=0; InitStack(Stack); cout<<"请输入您要建立的栈的大小："<<endl; cin>>n; Stack.stacksize=n; do{ cout<<"请选择操作："<<endl; cout<<""<<"1，进栈2，出栈3，查看栈顶值4，清空栈5，退出"<<endl; cin>>m; switch(m){ case1: cout<<"请输入进栈值："<<endl; cin>>z; if(i==Stack.stacksize) { cout<<"Sorry!!!"<<endl<<"栈溢出!!"<<endl<<"此程序将退出!!!"<<endl; exit(0); } Push(Stack,z); i++; break; case2: Pop(Stack,x); cout<<x<<"出栈"<<endl; break; case3: cout<<"栈顶值为："<<endl; GetTop(Stack,y); break; case4: ClearStack(Stack); break; case5: cout<<"Exit!!"<<endl; break; default: cout<<"输入错误！！！此程序将退出！！！"<<endl; exit(0); }//switch }while(m!=5); getch();}2.#include<iostream.h>#include<conio.h>#include<stdlib.h>#include<iomanip.h>//链式栈typedefstructStack{ Stack*next; intdata;}Stack,*SLink;typedefstruct{ SLinktop; intlength;}SqStack;voidInitStack(SqStack&S){ //构造一个空栈 S.top=NULL; //设栈顶指针的初值为"空" S.length=0; //空栈中元素个数为}//InitStackvoidPush(SqStack&S,int&e){ //在栈顶之上插入元素e为新的栈顶元素 SLinkp; p=newStack; //建新的结点 p->data=e; p->next=S.top; S.top=p; ++S.length;}//PushvoidPop(SqStack&S,int&e){ //假设栈不空，那么删除S的栈顶元素，用e返回其值 if(!S.top) { cout<<"此栈为空栈！！！"<<endl; exit(0); } e=S.top->data; S.top=S.top->next;}//PopvoidGetTop(SqStack&S,int&e){ //假设栈不空，取栈顶元素，用e返回其值 if(!S.top) { cout<<"此栈为空栈!!!"<<endl; exit(0); } e=S.top->data; cout<<e<<endl;}//GetTopvoidClearStack(SqStack&S){ // if(!S.top) cout<<"此栈已经为空!!!"<<endl; S.top=NULL;}//ClearStackvoidmain(){ SqStackStack; InitStack(Stack); intm,n,x,y,z,i=0; cout<<"请输入您要建立的栈的大小："<<endl; cin>>n; //需改正!!! do{ cout<<"请选择操作："<<endl; cout<<""<<"1，进栈2，出栈3，查看栈顶值4，清空栈5，退出"<<endl; cin>>m; switch(m){ case1: cout<<"请输入进栈值："<<endl; cin>>z; if(i==n) { cout<<"Sorry!!!"<<endl<<"栈溢出!!"<<endl<<"此程序将退出!!!"<<endl; exit(0); } Push(Stack,z); i++; break; case2: Pop(Stack,x); cout<<x<<"出栈"<<endl; break; case3: cout<<"栈顶值为："<<endl; GetTop(Stack,y); break; case4: ClearStack(Stack); break; case5: cout<<"Exit!!"<<endl; break; default: cout<<"输入错误！！！此程序将退出！！！"<<endl; exit(0); }//switch }while(m!=5); getch(); getch();}#include<iostream.h>#include<conio.h>#include<stdlib.h>//队空、入队和出队intn=0;typedefstructQ{ intdata; Q*next;}Q,*QLink;voidInitQ(QLink&q){ //构造一个队列 q->next=q;}//InitQvoidPush(QLink&q,int&e){ //入队 QLinkp; p=newQ; p->data=e; p->next=q->next; q->next=p; n++;}//PushvoidOutQ(QLink&q,int&e){ //出队 QLinkp; QLinkt; p=newQ; t=newQ; p=q; inti; for(i=0;i<=n;i++){ if(p->next->data==e) { t=p->next; p->next=t->next; deletet; break; }//if p=p->next; }//for if(i==(n+1)){ cout<<"您所输入的值不存在！此程序将退出！！"<<endl; exit(0); }}//OutQvoidClearQ(QLink&q){ //置队空 q=q->next;}//ClearQvoidcheckQ(QLink&q,int&e){ //查看队尾元素 if(q->next==q){ cout<<"此队列为空！！程序将退出！！"<<endl; exit(0); } e=q->next->data;}//checkvoidmain(){ intm,x,n,y; QLinkQu; Qu=newQ; InitQ(Qu); do{ cout<<"请选择操作："<<endl; cout<<" 1,入队2，出队3，查看队尾元素4，清空队列5，退出"<<endl; cin>>x; switch(x){ case1: cout<<"请输入您想插入的值："<<"\t"; cin>>m; Push(Qu,m); break; case2: cout<<"请输入您想出队的值："<<"\t"; cin>>n; OutQ(Qu,n); cout<<n<<"出队"<<endl; break; case3: checkQ(Qu,y); cout<<"队尾元素为："<<y<<endl; break; }//switch }while(x!=5);getch();}加强题：#include<iostream>#include<string>usingnamespacestd;boolcomp(charx,chary){ if(x==y) returntrue; else returnfalse;}//compvoidmain(){ charstr[100]; cout<<"请输入字符串："<<endl; cin>>str; inti=0,m; while(str[i]){ i++; } m=i%2; if(m){ intp=i-1,q=0; intj; for(j=0;j<(i-1)/2;j++){ if(!comp(str[q++],str[p--])) break; }//for if(j==(i-1)/2) cout<<"此字符串对称！！！"<<endl; else cout<<"此字符串不对称！！！"<<endl; }//if else{ intp=i-1,q=0; intj; for(j=0;j<(i/2);j+