3,4数据结构作业

第三章3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：一般准则：任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。证明：设两个合法序列为：T1=S……X……S……T2=S……X……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){inti;i=n;while(i1)couti--;}解：Voiddigui(intn){if(n==2)printf(“%d”,n);else{printf(“%d”,n);digui(n-1);}}3.10试将下列递归过程改写为非递归过程。voidtest(int&sum){intx;cinx;if(x==0)sum=0;else{test(sum);sum+=x;}coutsum;}解：voidtest(int&sum){sqstacks;intx;scanf(%d,&x);initstack(s);while(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，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解：程序源代码：#includestdio.h#includemalloc.h#defineSTACK_INIT_SIZE100#defineTURE1#defineFALSE0#defineok1#defineerror0#defineINFEASIBLE-1typedefintselemtype;typedefintstatus;typedefstruct{int*base[2];selemtype*top[2];intstacksize;}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,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,selemtype*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[0]);returnok;}if(i==1){*e=*(--(*s).top[1]);returnok;}}voidmain(){sqstacksta;selemtypee;selemtype*p;inti;if(INITstack(&sta))printf(双栈已被创建\n);printf(请输入进栈端(0/1)及进栈元素：\n);scanf(%d%d,&i,&e);if(Push(&sta,i,e))printf(元素已入栈\n);printf(请输入进栈端(0/1)及进栈元素：\n);scanf(%d%d,&i,&e);if(Push(&sta,i,e))printf(元素已入栈\n);printf(请输入进栈端(0/1)及进栈元素：\n);scanf(%d%d,&i,&e);if(Push(&sta,i,e))printf(元素已入栈\n);printf(左端栈元素：);p=sta.base[0];while(sta.top[0]!=p){printf(%d,*p);p++;}printf(右端栈元素：);p=sta.base[1];while(sta.top[1]!=p){printf(%d,*p);p--;}printf(\n请输入出栈端(0/1)：\n);scanf(%d,&i);if(Pop(&sta,i,&e))printf(\n栈顶元素%d出栈\n,e);printf(左端栈元素：);p=sta.base[0];while(sta.top[0]!=p){printf(%d,*p);p++;}printf(右端栈元素：);p=sta.base[1];while(sta.top[1]!=p){printf(%d,*p);p--;}}运行结果：3.21假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。解：程序源代码：#includestdio.h#includemalloc.h#defineSIZE100typedefcharselemtype;typedefstruct{selemtype*base;selemtype*top;intsize;}stack;intPrior(charc1,charc2){charch[5]=#+-*/;inti=0,j=0;if(c1=='(')return0;while(ch[i]&&ch[i]!=c1)i++;if(i==2)i--;//加和减可认为是同级别的运算符if(i==4)i--;//乘和除可认为是同级别的运算符while(ch[j]&&ch[j]!=c2)j++;if(j==2)j--;if(j==4)j--;if(ij)return1;elsereturn0;}voidmain(){stacksta;charch=0,ct;sta.base=(selemtype*)malloc(SIZE*sizeof(selemtype));if(!sta.base)exit(0);sta.top=sta.base;sta.size=0;*sta.top++='#';printf(pleaseentertheexpression:\n);while(ch!='#'&&*sta.base=='#'){ch=getchar();if('a'=ch&&ch='z')printf(%c,ch);elseif(ch=='#'){ct=*(--sta.top);while(ct!='#'){printf(%c,ct);ct=*(--sta.top);}--sta.top;}elseif(ch=='(')*sta.top++=ch;elseif(ch==')'){ct=*(--sta.top);while(ct!='('){printf(%c,ct);ct=*(--sta.top);}}else{ct=*(sta.top-1);if(Prior(ct,ch)==0)*sta.top++=ch;else{ct=*(--sta.top);while(Prior(ct,ch)){printf(%c,ct);ct=*(--sta.top);}*(++sta.top)=ch;++sta.top;}}}}运行结果：3.22如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。解：程序源代码：#includeiostream.h#includemalloc.h#definemax_size_stack100#defineincre10#defineok1#defineerror-100typedefintelemtype2;typedefintstatus;typedefstruct{elemtype2*top;elemtype2*base;intsize;}stack2;statusinitstack2(stack2&da){da.base=(elemtype2*)malloc(max_size_stack*sizeof(elemtype2));if(!da.base)cout操作失败，程序执行无效!!!!!!endl;da.top=da.base;da.size=max_size_stack;returnok;}statuspop2(stack2&da,elemtype2&e){if(da.base==da.top)returnerror;e=*(--da.top);returnok;}statuspush2(stack2&da,elemtype2e){if(da.top-da.base=da.size){da.base=(elemtype2*)realloc(da.base,(da.size+incre)*sizeof(elemtype2));if(!da.base)cout操作失败，程序执行无效!!!!!!endl;da.top=da.base+da.size;da.size+=incre;}*da.top++=e;returnok;}intcoun(elemtype2e1,elemtype2e2,charcch){switch(cch){case'+':returne1+e2;case'-':returne1-e2;case'*':returne1*e2;case'/':if(e2==0)returnerror;elsereturne1/e2;case'#':returnok;break;default:returnerror;}}voidmain(){charcch;inti,count=0,e1,e2;stack2da;initstack2(da);cout请输入表达式的逆波兰式：(#表结束)endl;for(cch='1',i=0;cch!='#'&&i20;i++){cincch;if(cch!='+'&&cch!='-'&&cch!='*'&&cch!='/'&&cch!='#')push2(da,cch-48);elseif(cch!='#'){pop2(da,e2);pop2(da,e1);if(coun(e1,e2,cch)