资源描述：
《习题三和上机答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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)
2、,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()可以得到bacdPus
3、h(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(
4、),Push(c),Push(d),Pop(),Pop()可以得到abdc⒊２分别借助顺序栈和链栈，将单链表倒置。解：顺序表：#include"stdio.h" #defineDataTypechar #definesqstack_maxsize40 typedefstructsqstack {DataTypedata[sqstack_maxsize]; inttop; }SqStackTp; intInitStack(SqStackTp*sq) {sq->top=0;return(1);} intPush(SqStackTp*sq,Data
5、Typex) { if(sq->top==sqstack_maxsize-1) {printf("栈满");return(0);} else {sq->top++;sq->data[sq->top]=x;return(1);} } intPop(SqStackTp*sq,DataType*x) { if(sq->top==0){printf("下溢");return(0);} else{*x=sq->data[sq->top];sq->top--;return(1);} } intEmptyStack(SqStackTp*sq) {
6、 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(""); while(!EmptyStack(&sq)) {Pop(&sq,&ch);printf("%c",ch);} printf(""); }链表：#include"std
7、io.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; } intPo
8、p(LStackTp*ls,datatype*x) {LStackTpp; if((*ls)!=NULL) {p=*ls;*x=p->data;*
