3,4数据结构作业

《3,4数据结构作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第三章3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列(例如，SXSX为合法序列，SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法(栈操作)序列(对同一输入序列)不可能得到相同的输出元素(注意:在此指的是元素实体，而不是值)序列。解：一般准则：任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。证明：设两个合法序列为：T1二SXST2

2、二SXX假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈(不妨为栈A、B)的存储情况完全相同，假设此时栈顶元素均为ao第n+1个操作不同，不妨T1的第n+1个操作为S,T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先8后b。由于T1的输出为ba,而T2的输出顺序为ab,说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.9试将下列递推过程改写为递归过程。voidditui(

3、intn){inti;i=n;whi1e(i>1)cout«i--；}解：Voiddigui(intn){if(n==2)printf(W；n);else{printfCW*,n);digui(n-1);}}3.10试将下列递归过程改写为非递归过程。voidtest(int&sum){intx;cin»x;if(x==0)sum=0;elsetest(sum);sum+=x;cout«sum;解：voidtest(int&sum){sqstacks;intx;scanf("%d：&x);initstack

4、(s);while(x!=0){*s.front++=x;scanf("%d",&x);}sum=0;inte;printf(〃%cT,sum);while(s.front!=s.base){e=*(-一s.front);suni+二e;printfsum);}}3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)入栈push(tws,i,x)和出栈pop(tws,i)的算法

5、,其中i为0或1,用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解：程序源代码：#include#include#defineSTACK1N1TSIZE100#defineTURE1#defineFALSE0#defineok1#defineerror0#defineINFEASIBLE-1typedefintselemtype;typedefintstatus;typedefstruct{int*ba

6、se[2];selemtype*top[2];intstacksizc;}sqstack;statusTNTTstack(sqstack*s){int*p;p=(selemtype*)malloc(STACK_IN1T_SIZE*sizeof(selemtype));(*s).base[0]=(*s).top[0]=p;(*s).base[1]二(*s)・top[1]=p+STACK_INIT_SIZE-l;if(!(*s).base[0])exit(-2);if(!(*s).base[l])exit(-

7、2);returnok;}statusPush(sqstack*s,inti,seiemtypee){if(i==0){if((*s).top[0]>=((*s).base[0]+(STACK1N1TSIZE/2)-l))returnerror;else*(*s).top[0]++=e;returnok;}if(i==l){if((*s)・to讥1]<=((*s).base[1]-(STACK_INITSIZE/2)+l))returnerror;else*(*s).top[1]--=e;returnok

8、;}returnerror;}statusPop(sqstack*s,inti,selemtype*e){if(i==0&&(*s).top[0]==(*s).base[0])returnerror;if(i=l&&(*s).top[l]==(*s).base[l])returnerror;if(i==0){*e=*(—(*s).top[0]);returnok;}if(i==l){*e=*(—(*s).top[l]);ret