欢迎来到天天文库
浏览记录
ID:26449511
大小:221.06 KB
页数:22页
时间:2018-11-27
《《数据结构作业》word版》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、第三章3.5假设以S和X分别表示入栈和出栈的操作,则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列(例如,SXSX为合法序列,SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则,并证明:两个不同的合法(栈操作)序列(对同一输入序列)不可能得到相同的输出元素(注意:在此指的是元素实体,而不是值)序列。解:一般准则:任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。证明:设两个合法序列为:T1=S……X……S……T2=S……X……
2、X……假定前n个操作都相同,从第n+1个操作开始,为序列不同的起始操作点。由于前n个操作相同,故此时两个栈(不妨为栈A、B)的存储情况完全相同,假设此时栈顶元素均为a。第n+1个操作不同,不妨T1的第n+1个操作为S,T2的第n+1个操作为X。T1为入栈操作,假设将b压栈,则T1的输出顺序一定是先b后a;而T2将a退栈,则其输出顺序一定是先a后b。由于T1的输出为……ba……,而T2的输出顺序为……ab……,说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.9试将下列递推过程改写为递归过程。voidditui(intn){
3、inti;i=n;while(i>1)cout<>x;if(x==0)sum=0;else{test(sum);sum+=x;}cout<4、le(x!=0){*s.front++=x;scanf("%d",&x);}sum=0;inte;printf("%d",sum);while(s.front!=s.base){e=*(--s.front);sum+=e;printf("%d",sum);}}3.15假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指5、示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解:程序源代码:#include#include#defineSTACK_INIT_SIZE100#defineTURE1#defineFALSE0#defineok1#defineerror0#defineINFEASIBLE-1typedefintselemtype;typedefintstatus;typedefstruct{int*base[2];selemtype*top[2];in6、tstacksize;}sqstack;statusINITstack(sqstack*s){int*p;p=(selemtype*)malloc(STACK_INIT_SIZE*sizeof(selemtype));(*s).base[0]=(*s).top[0]=p;(*s).base[1]=(*s).top[1]=p+STACK_INIT_SIZE-1;if(!(*s).base[0])exit(-2);if(!(*s).base[1])exit(-2);returnok;}statusPush(sqstack*s,inti7、,selemtypee){if(i==0){if((*s).top[0]>=((*s).base[0]+(STACK_INIT_SIZE/2)-1))returnerror;else*(*s).top[0]++=e;returnok;}if(i==1){if((*s).top[1]<=((*s).base[1]-(STACK_INIT_SIZE/2)+1))returnerror;else*(*s).top[1]--=e;returnok;}returnerror;}statusPop(sqstack*s,inti,selemty8、pe*e){if(i==0&&(*s).top[0]==(*s).base[0])returnerror;if(i==1&&(*s).top[1]==(*s).base[1])returnerror;if(i==0){*e=*(--(*s).top
4、le(x!=0){*s.front++=x;scanf("%d",&x);}sum=0;inte;printf("%d",sum);while(s.front!=s.base){e=*(--s.front);sum+=e;printf("%d",sum);}}3.15假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指
5、示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解:程序源代码:#include#include#defineSTACK_INIT_SIZE100#defineTURE1#defineFALSE0#defineok1#defineerror0#defineINFEASIBLE-1typedefintselemtype;typedefintstatus;typedefstruct{int*base[2];selemtype*top[2];in
6、tstacksize;}sqstack;statusINITstack(sqstack*s){int*p;p=(selemtype*)malloc(STACK_INIT_SIZE*sizeof(selemtype));(*s).base[0]=(*s).top[0]=p;(*s).base[1]=(*s).top[1]=p+STACK_INIT_SIZE-1;if(!(*s).base[0])exit(-2);if(!(*s).base[1])exit(-2);returnok;}statusPush(sqstack*s,inti
7、,selemtypee){if(i==0){if((*s).top[0]>=((*s).base[0]+(STACK_INIT_SIZE/2)-1))returnerror;else*(*s).top[0]++=e;returnok;}if(i==1){if((*s).top[1]<=((*s).base[1]-(STACK_INIT_SIZE/2)+1))returnerror;else*(*s).top[1]--=e;returnok;}returnerror;}statusPop(sqstack*s,inti,selemty
8、pe*e){if(i==0&&(*s).top[0]==(*s).base[0])returnerror;if(i==1&&(*s).top[1]==(*s).base[1])returnerror;if(i==0){*e=*(--(*s).top
此文档下载收益归作者所有