搜索
实验二栈、队列的实现、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。二、实验要求1实验之前认真准备，编写好源程序。2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3不断积累程序的调试方法。三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：1、设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。提高题：1、试编写程序：a.将中缀表达式计算转换成后缀表达式。b.后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。四．实验代码基础题1#includeiostream.h#includeconio.h#includestdlib.hconstSTACK_INIT_SIZE=100;//存储空间初始分配量constSTACKINCREMENT=10;//存储空间分配增量typedefstruct{int*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初始化完毕endl;}//InitStackvoidGetTop(SqStackS,int&e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top==S.base){cout此栈为空!!!endl;exit(0);}e=*(S.top-1);couteendl;cout取值结束endl;}//GetTopvoidPush(SqStack&S,inte){//插入元素e为新的栈顶元素if(S.top-S.baseS.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；否则返回ERRORif(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;}//ClearStackintvisit(int*p){return*p;}voidTraverse(SqStackS){int*p;p=S.base;while(p!=S.top){coutvisit(p);p++;}coutendl;}voidmain(){SqStackStack;intm,n,x,y,z,i=0;charc;InitStack(Stack);cout请输入您要建立的栈的大小：endl;cinn;Stack.stacksize=n;do{cout请选择操作：endl;cout1，进栈2，出栈3，查看栈顶值4，清空栈5，退出endl;cinm;switch(m){case1:while(1){coutdoyouwanttoinputsomeelements?(y/n)endl;cinc;if(c=='n')break;elsecoutpleaseenteroneelementendl;cinz;if(i==Stack.stacksize){coutSorry!!!endlthestackisoverflow!!endlexit!!!endl;exit(0);}Push(Stack,z);i++;}coutthestackis:;Traverse(Stack);break;case2:Pop(Stack,x);coutx出栈endl;break;case3:cout栈顶值为：endl;GetTop(Stack,y);break;case4:ClearStack(Stack);break;case5:coutExit!!endl;break;default:cout输入错误！！！此程序将退出！！！endl;exit(0);}//switch}while(m!=5);getch();}基础题2#includeiostream.h#includeconio.h#includestdlib.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;}//ifp=p-next;}//forif(i==(n+1)){cout您所输入的值不存在！此程序将退出！！endl;exit(0);}}//OutQvoidClearQ(QLink&q){//置队空q-next=q;}//ClearQvoidcheckQ(QLink&q,int&e){//查看队尾元素if(q-next==q){cout此队列为空！！程序将退出！！endl;exit(0);}e=q-next-data;}//checkvoidmain(){intm,x,n,y,e;QLinkQu;Qu=newQ;InitQ(Qu);do{cout请选择操作：endl;cout1,入队2，出队3，查看队尾元素4，清空队列5，退出endl;cinx;switch(x){case1:cout请输入您想插入的值：\t;cinm;Push(Qu,m);break;case2:cout请输入您想出队的值：\t;cinn;OutQ(Qu,n);coutn出队endl;break;case3:checkQ(Qu,y);cout队尾元素为：yendl;break;case4:ClearQ(Qu);checkQ(Qu,e);case5:exit(0);}//switch}while(x!=5);getch();}五、程序调试基础题1：基础题2六、实验心得