习题三和上机答案

1习题三3.1设将整数a，b，c，d依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若执行以下操作序列Push(a),Pop(),Push(b),Push(c),Pop(),Pop(),Push(d),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?(2)能否得到出栈序列adbc和adcb并说明为什么不能得到或者如何得到。(3)请分析a，b，c，d的所有排列中，哪些序列是可以通过相应的入出栈操作得到的。解：（1）acbd（2）执行以下操作序列Push(a),Pop(),Push(b),Push(c),Push(d),Pop(),Pop(),Pop()就可以得到adcb栈的特点是“后进先出”，所以不可能得到adbc（3）Push(a),Push(b),Push(c),Push(d),Pop(),Pop(),Pop(),Pop()可以得到dcbaPush(a),Push(b),Push(c),Pop(),Pop(),Pop(),Push(d),Pop()可以得到cbadPush(a),Push(b),Pop(),Pop(),Push(c),Pop(),Push(d),Pop()可以得到bacdPush(a),Push(b),Pop(),Pop(),Push(c),Push(d),Pop(),Pop()可以得到badcPush(a),Pop(),Push(b),Push(c),Push(d),Pop(),Pop(),Pop()可以得到adcbPush(a),Pop(),Push(b),Push(c),Pop(),Pop(),Push(d),Pop()可以得到acbdPush(a),Pop(),Push(b),Pop(),Push(c),Pop(),Push(d),Pop()可以得到abcdPush(a),Pop(),Push(b),Pop(),Push(c),Push(d),Pop(),Pop()可以得到abdc⒊２分别借助顺序栈和链栈，将单链表倒置。解：顺序表：#includestdio.h#defineDataTypechar#definesqstack_maxsize40typedefstructsqstack{DataTypedata[sqstack_maxsize];inttop;}SqStackTp;intInitStack(SqStackTp*sq){sq-top=0;return(1);}intPush(SqStackTp*sq,DataTypex){if(sq-top==sqstack_maxsize-1){printf(栈满);return(0);}else{sq-top++;sq-data[sq-top]=x;return(1);}}intPop(SqStackTp*sq,DataType*x)2{if(sq-top==0){printf(下溢);return(0);}else{*x=sq-data[sq-top];sq-top--;return(1);}}intEmptyStack(SqStackTp*sq){if(sq-top==0)return(1);elsereturn(0);}/*主函数*/voidmain(){SqStackTpsq;DataTypech;InitStack(&sq);for(ch='A';ch='A'+12;ch++){Push(&sq,ch);printf(%c,ch);}printf(\n);while(!EmptyStack(&sq)){Pop(&sq,&ch);printf(%c,ch);}printf(\n);}链表：#includestdio.h#definedatatypechar#definesizesizeof(structnode)typedefstructnode{datatypedata;structnode*next;}*LStackTp;voidInitStack(LStackTp*ls){*ls=NULL;}voidPush(LStackTp*ls,datatypex){LStackTpp;p=(LStackTp)malloc(size);p-data=x;p-next=*ls;*ls=p;}3intPop(LStackTp*ls,datatype*x){LStackTpp;if((*ls)!=NULL){p=*ls;*x=p-data;*ls=(*ls)-next;free(p);return(1);}elsereturn(0);}intEmptyStack(LStackTpls){if(ls==NULL)return(1);elsereturn(0);}voidmain(){LStackTpls;datatypech;InitStack(ls);for(ch='A';ch='A'+12;ch++){Push(&ls,ch);printf(%c,ls-data);}printf(\n);while(!EmptyStack(ls)){Pop(&ls,&ch);printf(%c,ch);}printf(\n);}⒊３有两个栈A，B这两个栈中分别存储这一个升序数列，现要求编写算法把这两个栈中的数合成一个升序队列解：linkmerge(linka,linkb){linkh,s,m,n,t;h=(cnode*)malloc(sizeof(cnode));h-next=NULL;s=h;m=a;n=b;while(m-next&&n-next){if(m-next-datan-next-data){t=m-next;m-next=t-next;t-next=s-next;s-next=t;s=t;}elseif(m-next-data==n-next-data){t=m-next;4m-next=t-next;n=n-next;t-next=s-next;s-next=t;s=t;}else{t=n-next;n-next=t-next;t-next=s-next;s-next=t;s=t;}}while(m-next){t=m-next;m-next=t-next;t-next=s-next;s-next=t;s=t;}while(n-next){t=n-next;n-next=t-next;t-next=s-next;s-next=t;s=t;}free(m);free(n);returnh;}⒊4设两个栈共享一个数组空间，其类型定义见⒊⒈２节，试写出两个栈公用的读栈顶元算法elemtptop_dustack(dustacktpds,p;inti)；进栈操作算法voidpush_dustack(dustacktpds,p;inti,elemtpx)；及出栈算法elemtppop_dustack(dustacktpds,p;inti)。其中i的取值是1或2，用以指示栈号。解：读栈顶元函数elemtptop_sqstack(s:sqstacktp){if(s.top==0)return(null);elsereturn(s.elem[s.top]);}5进栈操作voidpush_sqstack(sqstacktps，elemtpx){若栈s未满，将元素x压入栈中；否则，栈的状态不变并给出出错信息if(s.top==maxsize)printf(“Overflow”);else{s.top++;栈顶指针加1s.elem[s.top]=xx进栈}}出栈函数elemtppop_sqstack(sqstacktps){若栈s不空，则删去栈顶元素并返回元素值，否则返回空元素NULLif(s.top==0)return(null);else{s.top--;栈顶指针减1teturn(s.elem[s.top+1]);返回原栈顶元素值}}⒊5假设以数组sequ(0..m-1)存放循环队列元素，同时设变量rear和quelen分别指示循环队列中队尾元素和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。解：队满的条件(sq.rear+1)MODmaxsize=sq.front入队列操作voiden_cqueue(cqueuetpcq,elemtpx){若循环队列cq未满，插入x为新的队尾元素；否则队列状态不变并给出错误信息if((cq.rear+1)MODmaxsize==cq.front)printf(“Overflow”);else{cq.rear=(cq.rear+1)MODmaxsize;cq.elem[cq.rear]=x}}出队列函数elemtpdl_cqueue(VARcq:cqueuetp){若循环队列cq不空，则删去队头元素并返回元素值；否则返回空元素NULLif(cq.front==cq.rear)6return(NULL);else{cq.front=(cq.front+1)MODmaxsize;return(cq.elem[cq.front]);}}⒊6假设以带头结点的环形链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列、出队列的算法。解：初始化：voidinit_lqueue(lqueuetplq){设置一个空的链队列lqnew(lq.front);lq.front-next:=NIL;lq.rear=lq.front;}入队列操作：PROCen_lqueue(VARlq:lqueuetp;x:elemtp);在链队列lq中，插入x为新的队尾元素BEGINnew(s);s↑.data:=x;s↑.next:=NIL;lq.rear↑.next:=s;lq.rear:=sENDP;en_lqueue出队列操作：elemtpdl_lqueue(lqueuetplq){若链队列lq不空，则删去队头元素并返回元素值；否则返回空元素NULLif(lq.front==lq.rear)return(null);else{p=lq.front-next;lq.front-next=p-next;IF(p-next==NIL)lq.rear=lq.front;当链队列中仅有一个结点时，出队时还需修改尾指针x=p-data;dispose(p);return(x)}}7第三章上机内容1、设单链表中存放n个字符,设计一个算法,使用栈判断该字符串是否中心对称,如abccba即为中心对称字符串.（根据题目填空完善程序）提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用bj()函数判断是否为中心对称字符串。在bj（）函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。#includestdio.h#includemalloc.h#defineMaxLen100typedefstructnode{chardata；structnode*next；}cnode；cnode*create(chars[]){intI=0；cnode*h,*p,*r；while(s[I]!=’\0’){p=(cnode*)malloc(sizeof(cnode))；p-data=s[I]；p-next=NULL；if(I==0){h=p；r=p；/*r始终指向最后一个结点*/}else{r-next=p；r=p；}I++；}returnh；}intjudge(cnode*h){charst[MaxLen]；inttop=0；cnode*p=h；while(p!=NULL){8st[top]=p-data；top++；p=p-next；}p=h；while(p!=NULL){top--；if(p-data==st[