文档库

最新最全的文档下载
以后地位:文档库 > 第三章作业参考答案

第三章作业参考答案

3.1 有5个元素,其入栈次序为:A、B、C、D、E,在各类能够的出栈次序中,以元素

C、D最早出栈(即C第一个且D第二个出栈)的次序有哪几个?

答:要使C第一个且D第二个出栈,应是A入栈,B入栈,C入栈,C出栈,D入栈,D出栈,以后可以有以下几种情况:

(1)B出栈,A出栈,E入栈,E出栈,输入序列为CDBAE;

(2)B出栈,E入栈,E出栈,A出栈,输入序列为CDBEA;

(3)E入栈,E出栈,B出栈,A出栈,输入序列为CDEBA。

所以能够的次序有:CDBAE、CDBEA、CDEBA。

3.2 假定以I和O分别表示入栈和出栈操作,栈的初态和终栈均为空,入栈和出栈的操作序列可表示为仅由I和O构成的序列。

(1)下面所示的序列中哪些是合法的?

A.IOIIOIOO

B.IOOIOIIO

C.IIIOIOIO

D.IIIOOIOO

(2)经过过程对(1)的分析,写出一个算法剖断所给的操作序列能否合法。若合法前往1;不然前往0。(假定被剖断的操作序列已存入一维数组中)。

解:(1)A、D均合法,而B、C不合法。由于在B中,先入栈一次,急速出栈三次,这会形成栈下溢。在C中共入栈五次,出栈三次,栈的终态不为空。

(2)本题应用一个链栈来断定操作序列能否合法,个中A为存放操作序列的字符数组,n为该数组的元素个数(这里的ElemType类型设定为char)。对应的算法以下:int judge(char A[],int n)

{ int i;

ElemType x;

LiStack *ls;

InitStack(ls);

for (i=0;i

{ if (A[i]=='I') //入栈

Push(ls,A[i]);

else if (A[i]=='O') //出栈

{ if (StackEmpty(s))

return 0; //栈空时前往0

else

Pop(ls,x);

}

else return 0; //其他值有效加入

}

return (StackEmpty(ls)); //栈为空时前往1;不然前往0

}

3.3 假定表达式中许可包含3种括号:圆括号、方括号和大年夜括号。编写一个算法断定表达式中的括号能否精确配对。

解:设置一个栈st,扫描表达式exp,碰到'('、'['或'{',则将其入栈;碰到')',若栈顶是'(',则持续处理,不然以不配对前往0;碰到']',若栈顶是'[',则持续处理,不然以不配对前往0;碰到'}',若栈顶是'{',则持续处理,不然以不配对前往0。在exp扫描终了,若栈不空,则以不配对前往0;不然以括号配对前往1。本题算法以下: