1、第三章 3.5 假设以 S 和 X 分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操 作序列可以表示为仅由 S 和 X 组成的序列。称可以操作的序列为合法序列（例如，SXSX 为 合法序列，SXXS 为非法序列） 。试给出区分给定序列为合法序列或非法序列的一般准则， 并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素 （注意：在此指的是元素实体，而不是值）序列。 解： 一般准则：任何前 n 个序列中 S 的个数一定大于或等于 X 的个数且整个序列中 S 的个 数一定等于 X 的个数。 证明：设两个合法序列为： T1=SXS T2=SXX 假定前 n 个
2、操作都相同，从第 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 试将下列递推过程改写为递归过程。 void ditui(int n) in
3、t i; i = n; while(i1) cout=(*s).base0+(STACK_INIT_SIZE/2)-1) return error; else *(*s).top0+=e; return ok; if(i=1) if(*s).top1j) return 1; else return 0; void main() stack sta; char ch=0,ct; sta.base=(selemtype *)malloc(SIZE*sizeof(selemtype); if(!sta.base ) exit(0); sta.top=sta.base; sta.size=0; *st
4、a.top+=#; printf(“please enter the expression:n“); while(ch!=# if(ae; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coutch; sq.basesq.rear=ch; sq.rear=(sq.rear+1)%max; if(sq.basesq.rear
5、-1=) sq.rear-; if(sq.rear+1)%max=sq.front) cout=a) sq.basesq.rear=e; sq.rear=(sq.rear+1)%max; if(sq.front=sq.rear) sq.tag=1; else sq.base(sq.front+max-1)%max=e; sq.front=(sq.front+max-1)%max; if(sq.front=sq.rear) sq.tag=1; return ok; status dequeue(xqueue else e=sq.basesq.front; sq.front=(sq.front+1
6、+max)%max; sq.tag=0; return ok; void main() xqueue sq; elemtype e; initqueue(sq); coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coutn; coutcch; chi-1=cch; for(i=1;is; coutt; for(n=0;sn;n+); for(m=0;tm;m+); for(i=1;iss; couttt; strassign(s,ss); strass
7、ign(t,tt); pos=0; i=index(s,t,pos); while(i=s.length) for(j=1;j=t.length;j+) s.chi+j-1=*; pos=i=t.length; i=index(s,t,pos); for(i=1;i=s.length;i+) ssi-1=s.chi-1; strassign(s,ss); cout“新串 s 为：“endl; for(i=0;i=s.length-1;i+) couts.chi“ “; coutendl; 运行结果： 4.14 利用串的基本操作以及栈和集合的基本操作，编写“由一个算术表达式的前缀式求后 缀式”的递推算法（假设前缀式不含语法错误） 。
