计算机软件及应用栈的应用和串图课件

例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：nndiv8nmod8134816841682102125202除基取余法例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本1voidconversion(){InitStack(s);scanf(“%d”,N);while(N){

}while(!StackEmpty(S)){

printf(“%d”,e);}}//conversionpush(S,N%8);N=N/8;Pop(S,e);voidconversion(){push(S,N%2例2表达式求值大家考虑一下：4+2×3－10/5的求值运算过程两个相继出现的运算符的优先关系为了用栈来实现计算表达式，我们定义两个栈，一个是OPTR，用以寄存运算符，一个是OPND，用以寄存操作数或运算结果。其基本思想如下：（1）首先置操作数栈为空栈，表达式起始符为“#”为栈的栈底元素；（2）依次读入表达式的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶的元素比较优先级后再做相应的操作，直到表达式求值结束（即：OPTR的栈顶元素和当前读入的字符均为“#”）例2表达式求值为了用栈来实现计算表达式，我们定义两个栈，一3OperandTypeEvaluateExpression()//算术表达式求值的算符优先算法，设OPTR和OPND分别是运算符栈和运算数栈，OP为运算符集合InitStack(OPTR);Push(OPTR,”#”);InitStack(OPND);c=getchar();While(c!=‘#’||GetTop(OPTR)!=‘＃’){if(!In(c,OP)){Push(OPND,c);c=getchar();}//不是运算符则进入栈switch(Precede(GetTop(OPTR),c)){case‘<’://栈顶元素的优先级低Push(OPTR,c);c=getchar();break;case‘=’://脱括号并接受下一个字符；OperandTypeEvaluateExpressio4Pop(OPTR,x);c=getchar();break;case‘>’:退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whileRerurnGetTop(OPND);}//EvaluateExpression现在以3×（7－2）演示一下。

Pop(OPTR,x);c=getchar();5选择题1.对于栈操作数据的原则是（）。先进先出B.后进先出C.后进后出D.不分顺序3.一个栈的输入序列为1,2,3…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i4.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.i

B.n-iC.n-i+1D.不确定BBDD选择题BBDD62.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③)。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④)分别设在这片内存空间的两端,这样,当(⑤)时，才产生上溢。①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.长度B.深度C.栈顶D.栈底⑤:A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.BBADC2.在作进栈运算时,应先判别栈是否(①),在作退栈710.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b11.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。A．fedcbaB.bcafedC.dcefbaD.cabdef12.设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX13.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,popDDCB10.某堆栈的输入序列为a,b，c，d,下面的四个序列814.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-115.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.栈在（）中应用。递归调用B.子程序调用C.表达式求值D.A，Ｂ，ＣBDC14.若一个栈以向量V[1..n]存储，初始栈顶指针top9注：上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也较高，但是在有些情况下，该算法的效率却很低。其主串的指针i在不断的回溯，如i=3,变为i=2,i=7变为i=4…其时间复杂度可达到O(n*m).注：上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑10KMP算法，其时间复杂度为：O(n+m),KMP算法，其时间复杂度为：O(n+m),11如果主串i上的字符不匹配的时候，则主串i上的字符应该再与模式串上的那个字符相比较，也就是说，如果出现不匹配的时候，模式串应该“向右滑动”多远？如果主串i上的字符不匹配的时候，则主串i上的字符应该再与模式12模式串的next函数定义如下：例子：1.求模式串T=‘abcac’的next函数值next=011122.求模式串T=‘abaabcac’的next函数值模式串的next函数定义如下：例子：13因为next[3]=1，说明主串的第3个字符a（i=3）应该再与模式串的第1个字符a相比较，故出现了第二趟比较的情况；因next[5]=2，说明主串的第7个字符a（i=7）应该再与模式串的第2个字符b相比较，故出现了第三趟比较的情况。因为next[3]=1，说明主串的第3个字符a（i=3）应该14注：next[j]仅取决于模式串本身而和相匹配的主串无关。下面推导其递推算法显然：next[1]=0;假设next[j]=k,则说明在模式串中存在：‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’怎么求next[j+1]?如果pk=pj，则说明:‘p1p2…pk-1pk’=‘pj-k+1pj-k+2…pj-1pj’于是next[j+1]=k+1=next[j]+1如果pk!=pj，则这又是一个模式匹配问题，其中主串和模式串相同于是模式串应该向右滑动至pj与pnext[k]相对齐，继续比较，又分两种情况：pj=pnext[k]和pj与pnext[k]不相等。注：next[j]仅取决于模式串本身而和相匹配的主串无关。下15若pj=pnext[k],则next[j+1]=next[k]+1;

若pj!=pnext[k],则考察pj和pnext[next[k]],若pj=pnext[next[k]],则next[j+1]=next[next[k]]+1若pj!=pnext[next[k]],则继续比较下去,

若pj!=pnext[next[k]]=p1,即:next[next[k]]=1,则next[j+1]=1.若pj=pnext[k],则next[j+1]=next[16例子：T=‘abaabcac’next[3]=next[2+1],next[2]=1,而p2!=p1,所以next[3]=next[1]+1=1next[4]=next[3+1],next[3]=1,因为p3=p1,所以next[4]=next[3]+1=2next[5]=next[4+1],next[4]=2,而p4!=p2,又next[2]=1,p4=p1,所以,next[5]=next[2]+1=2.next[6]=next[5+1],next[5]=2,因为p5=p2,所以next[6]=next[5]+1=3.next[7]=next[6+1],next[6]=3,而p6!=p3,next[3]=1,又p6!=p1,所以next[7]=next[1]+1=1,next[8]=next[7+1],next[7]=1,因为p7=p1,因此next[8]=next[7]+1=2例子：T=‘abaabcac’next[3]=next[2+17上述定义的函数在某些情况下尚有缺陷，如在出现这种情况的时候，即第一个字符与主串中的相应字符不匹配的时候，因为模式串前四个字符相同，主串中的字符不需要和第2，3，4个字符比较，所以可以把其next[j]作如下修改：上述定义的函数在某些情况下尚有缺陷，如在出现这种情况的时候，184．已知串S=‘aaab’,其Next数组值为（）。A．0123B．1123C．1231D．1211

5．串‘ababaaababaa’的next数组为（）。A．012345678999B．012121111212C．011234223456D．0123012322345

6．字符串‘ababaabab’的nextval为（）A．(0,1,0,1,04,1,0,1)B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1)D．(0,1,0,1,0,1,0,1,1)

ACA4．已知串S=‘aaab’,其Next数组值为（）。191、树的定义和基本术语2、二叉树1、树的定义和基本术语2、二叉树206.1树6.1.1树的定义和基本运算1.定义树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。树还有其他的表示形式:：1以嵌套集合的形式表示；2以广义表的形式表示；3以凹入法表示（类似书的编目）6.1树6.1.1树的定义和基本运算树还有其他的表示21KLMEFGHIJBCDAA(a)(b)(c)KLM22基本术语结点：包含一个数据元素及若干指向其子树根的分支。结点的度：结点拥有的子树数，即结点的分支数。终端结点（叶子）：度为0的结点。非终端结点：度不为0的结点。结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度：树中所有结点度的最大值。树的深度：树中结点的最大层次。有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。基本术语结点：包含一个数据元素及若干指向其子树根的分支。23森林：是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子、双亲：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先：从根结点到该结点路径上的所有结点。兄弟：同一个双亲的孩子之间互为兄弟。堂兄弟：双亲在同一层的结点互为堂兄弟。森林：是m（m≥0）棵互不相交的树的集合。24问题1：图中结点个数和分支之间的关系？问题2：图中某个结点的度数和从它引出的分支之间的关系？假设B为上图所表的树中分支（直线段）的个数，ni表示度为i的结点的个数，n为结点总数，显然有n=B+1,n=n0+n1+n2…nk,B=n0*0+n1*1+n2*2+…nk*k,问题1：图中结点个数和分支之间的关系？问题2：图中某个结点的25例如：.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8Dn=B+1,n=n0+n1+n2…nk,B=n0*0+n1*1+n2*2+…nk*k,B=n0*0+1*4+2*2+3*1+4*1=15,n=B+1=16,而n=n0+4+2+1+1=n0+8=16,n0=8例如：.设树T的度为4，其中度为1，2，3和4的结点个数分266.2二叉树

6.2.1二叉树的定义和基本运算1.定义定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。6.2二叉树6.2.1二叉树的定义和基本运算27GHDEFBCA例如：G28二叉树的5种形态：ø(a)(b)(c)(d)(e)二叉树的5种形态：ø(a)(b)(c)(d)(e)29二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1≤j<i成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。2．二叉树的性质二叉树具有下列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i≥1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=2130【性质2】深度为K的二叉树最多有2K-1个结点（K≥1）。

由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：【性质2】深度为K的二叉树最多有2K-1个结点（K≥1）。31其中a1为第一项，an为第n项，q为比值。可以得到，该数列前K项之和为：其中a1为第一项，an为第n项，32【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2（1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n33又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1（2）用（1）式减去（2）式，并经过调整后得到：n0=n2+1。满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生348910111213141545672318910111235完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。完全二叉树：有一棵深度为h，具有n个36[计算机软件及应用]栈的应用和串图课件37不是完全二叉树不是完全二叉树38【性质4】具有n个结点的完全二叉树的深度为log2n+1。其中，log2n的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1<n≤2K-1将不等式两端加1得到：2K-1≤n<2K将不等式中的三项同取以2为底的对数，并经过化简后得到：K-1≤log2n<K由此可以得到：log2n=K-1。整理后得到：K=log2n+1。【性质4】具有n个结点的完全二叉树的深度为39【性质5】对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。（2）如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，则根没有右孩子；若n<2，则根将没有左、右孩子；以上对于（2）和（3）均成立。假设：对于所有的1≤j≤i结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。【性质5】对于有n个结点的完全二叉树中的所有结402i+2

2i2i+12i+22i+3i+12i2i+1iii+12i+22i2i+12i+41由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。又因为二叉树由n个结点组成，所以，当2(i+1)+1>n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)>n，结点i+1既没有左孩子也没有右孩子。由完全二叉树的结构可以看出：结点i+42以上证明得到（2）和（3）成立。下面利用上面的结论证明（1）。对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而(2i+1)/2=i，由此可以得出（1）成立。以上证明得到（2）和（3）成立。436.2.3二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1.顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。6.2.3二叉树的存储结构44845672318456453．2链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：3．2链式存储结构46其中，lchild和rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。在C语言中的类型定义为：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchlid;}BiTNode,*BiTree;其中，lchild和rchild是分47GHDEFBCA^G^^H^^D^E^F^B^CABT一棵二叉树及相应的链式存储结构GHD48

这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。注：在具体的应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需进行何种操作。这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，495.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定9．在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．7DBC5.在下述结论中，正确的是（）DBC5011．具有10个叶结点的二叉树中有（）个度为2的结点，A．8B．9C．10D．ll12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对16.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为217．二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-1BEBC11．具有10个叶结点的二叉树中有（）个度为2的结5118.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+120．对于有n个结点的二叉树,其高度为（）A．nlog2nB．log2nC．log2n+1D．不确定21.一棵具有n个结点的完全二叉树的树高度（深度）是（）A．log2n+1B．log2n+1C．log2nD．log2n-122．深度为h的满m叉树的第k层有（）个结点。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1CBDAA18.一个具有1025个结点的二叉树的高h为（）C5223．在一棵高度为k的满二叉树中，结点总数为（）A．2k-1B．2kC．2k-1D．log2k+124．高度为K的二叉树最大的结点数为（）。A．2k B．2k-1C．2k-1 D．2k-1-125.一棵树高为K的完全二叉树至少有（）个结点A．2k–1B.2k-1–1C.2k-1D.2k26.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A．4B．5C．6D．7CCCC23．在一棵高度为k的满二叉树中，结点总数为（）CC53二、填空题1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。6．具有256个结点的完全二叉树的深度为______。

7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。8．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。9．深度为H的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；H和结点总数N之间的关系是(3)__。10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。11．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。二、填空题6．具有256个结点的完全二叉树的深度为_____5412．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支（非终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。17．高度为K的完全二叉树至少有______个叶子结点。

19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。

20．一个有2001个结点的完全二叉树的高度为______。

12．一棵有n个结点的满二叉树有__(1)_个度为1的结点、55参考答案1.(1)根结点(2)左子树(3)右子树；6.97.128.(1)2k-1(2)2k-19.(1)2H-1(2)2H-1(3)H=log2N+110.用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t,则结点i和j在同一层上的条件是log2s=log2t。11.log2i=log2j

12.(1)0(2)(n-1)/2(3)(n+1)/2(4)log2n+113.n14.N2+115.(1)2K+1-1(2)k+117.2k-219.9920.11参考答案1.(1)根结点(2)左子树(3)右子树；56例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：nndiv8nmod8134816841682102125202除基取余法例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本57voidconversion(){InitStack(s);scanf(“%d”,N);while(N){

}while(!StackEmpty(S)){

printf(“%d”,e);}}//conversionpush(S,N%8);N=N/8;Pop(S,e);voidconversion(){push(S,N%58例2表达式求值大家考虑一下：4+2×3－10/5的求值运算过程两个相继出现的运算符的优先关系为了用栈来实现计算表达式，我们定义两个栈，一个是OPTR，用以寄存运算符，一个是OPND，用以寄存操作数或运算结果。其基本思想如下：（1）首先置操作数栈为空栈，表达式起始符为“#”为栈的栈底元素；（2）依次读入表达式的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶的元素比较优先级后再做相应的操作，直到表达式求值结束（即：OPTR的栈顶元素和当前读入的字符均为“#”）例2表达式求值为了用栈来实现计算表达式，我们定义两个栈，一59OperandTypeEvaluateExpression()//算术表达式求值的算符优先算法，设OPTR和OPND分别是运算符栈和运算数栈，OP为运算符集合InitStack(OPTR);Push(OPTR,”#”);InitStack(OPND);c=getchar();While(c!=‘#’||GetTop(OPTR)!=‘＃’){if(!In(c,OP)){Push(OPND,c);c=getchar();}//不是运算符则进入栈switch(Precede(GetTop(OPTR),c)){case‘<’://栈顶元素的优先级低Push(OPTR,c);c=getchar();break;case‘=’://脱括号并接受下一个字符；OperandTypeEvaluateExpressio60Pop(OPTR,x);c=getchar();break;case‘>’:退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whileRerurnGetTop(OPND);}//EvaluateExpression现在以3×（7－2）演示一下。

Pop(OPTR,x);c=getchar();61选择题1.对于栈操作数据的原则是（）。先进先出B.后进先出C.后进后出D.不分顺序3.一个栈的输入序列为1,2,3…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i4.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.i

B.n-iC.n-i+1D.不确定BBDD选择题BBDD622.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③)。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④)分别设在这片内存空间的两端,这样,当(⑤)时，才产生上溢。①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.长度B.深度C.栈顶D.栈底⑤:A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.BBADC2.在作进栈运算时,应先判别栈是否(①),在作退栈6310.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b11.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。A．fedcbaB.bcafedC.dcefbaD.cabdef12.设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX13.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,popDDCB10.某堆栈的输入序列为a,b，c，d,下面的四个序列6414.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-115.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.栈在（）中应用。递归调用B.子程序调用C.表达式求值D.A，Ｂ，ＣBDC14.若一个栈以向量V[1..n]存储，初始栈顶指针top65注：上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也较高，但是在有些情况下，该算法的效率却很低。其主串的指针i在不断的回溯，如i=3,变为i=2,i=7变为i=4…其时间复杂度可达到O(n*m).注：上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑66KMP算法，其时间复杂度为：O(n+m),KMP算法，其时间复杂度为：O(n+m),67如果主串i上的字符不匹配的时候，则主串i上的字符应该再与模式串上的那个字符相比较，也就是说，如果出现不匹配的时候，模式串应该“向右滑动”多远？如果主串i上的字符不匹配的时候，则主串i上的字符应该再与模式68模式串的next函数定义如下：例子：1.求模式串T=‘abcac’的next函数值next=011122.求模式串T=‘abaabcac’的next函数值模式串的next函数定义如下：例子：69因为next[3]=1，说明主串的第3个字符a（i=3）应该再与模式串的第1个字符a相比较，故出现了第二趟比较的情况；因next[5]=2，说明主串的第7个字符a（i=7）应该再与模式串的第2个字符b相比较，故出现了第三趟比较的情况。因为next[3]=1，说明主串的第3个字符a（i=3）应该70注：next[j]仅取决于模式串本身而和相匹配的主串无关。下面推导其递推算法显然：next[1]=0;假设next[j]=k,则说明在模式串中存在：‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’怎么求next[j+1]?如果pk=pj，则说明:‘p1p2…pk-1pk’=‘pj-k+1pj-k+2…pj-1pj’于是next[j+1]=k+1=next[j]+1如果pk!=pj，则这又是一个模式匹配问题，其中主串和模式串相同于是模式串应该向右滑动至pj与pnext[k]相对齐，继续比较，又分两种情况：pj=pnext[k]和pj与pnext[k]不相等。注：next[j]仅取决于模式串本身而和相匹配的主串无关。下71若pj=pnext[k],则next[j+1]=next[k]+1;

若pj!=pnext[k],则考察pj和pnext[next[k]],若pj=pnext[next[k]],则next[j+1]=next[next[k]]+1若pj!=pnext[next[k]],则继续比较下去,

若pj!=pnext[next[k]]=p1,即:next[next[k]]=1,则next[j+1]=1.若pj=pnext[k],则next[j+1]=next[72例子：T=‘abaabcac’next[3]=next[2+1],next[2]=1,而p2!=p1,所以next[3]=next[1]+1=1next[4]=next[3+1],next[3]=1,因为p3=p1,所以next[4]=next[3]+1=2next[5]=next[4+1],next[4]=2,而p4!=p2,又next[2]=1,p4=p1,所以,next[5]=next[2]+1=2.next[6]=next[5+1],next[5]=2,因为p5=p2,所以next[6]=next[5]+1=3.next[7]=next[6+1],next[6]=3,而p6!=p3,next[3]=1,又p6!=p1,所以next[7]=next[1]+1=1,next[8]=next[7+1],next[7]=1,因为p7=p1,因此next[8]=next[7]+1=2例子：T=‘abaabcac’next[3]=next[2+73上述定义的函数在某些情况下尚有缺陷，如在出现这种情况的时候，即第一个字符与主串中的相应字符不匹配的时候，因为模式串前四个字符相同，主串中的字符不需要和第2，3，4个字符比较，所以可以把其next[j]作如下修改：上述定义的函数在某些情况下尚有缺陷，如在出现这种情况的时候，744．已知串S=‘aaab’,其Next数组值为（）。A．0123B．1123C．1231D．1211

5．串‘ababaaababaa’的next数组为（）。A．012345678999B．012121111212C．011234223456D．0123012322345

6．字符串‘ababaabab’的nextval为（）A．(0,1,0,1,04,1,0,1)B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1)D．(0,1,0,1,0,1,0,1,1)

ACA4．已知串S=‘aaab’,其Next数组值为（）。751、树的定义和基本术语2、二叉树1、树的定义和基本术语2、二叉树766.1树6.1.1树的定义和基本运算1.定义树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。树还有其他的表示形式:：1以嵌套集合的形式表示；2以广义表的形式表示；3以凹入法表示（类似书的编目）6.1树6.1.1树的定义和基本运算树还有其他的表示77KLMEFGHIJBCDAA(a)(b)(c)KLM78基本术语结点：包含一个数据元素及若干指向其子树根的分支。结点的度：结点拥有的子树数，即结点的分支数。终端结点（叶子）：度为0的结点。非终端结点：度不为0的结点。结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度：树中所有结点度的最大值。树的深度：树中结点的最大层次。有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。基本术语结点：包含一个数据元素及若干指向其子树根的分支。79森林：是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子、双亲：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先：从根结点到该结点路径上的所有结点。兄弟：同一个双亲的孩子之间互为兄弟。堂兄弟：双亲在同一层的结点互为堂兄弟。森林：是m（m≥0）棵互不相交的树的集合。80问题1：图中结点个数和分支之间的关系？问题2：图中某个结点的度数和从它引出的分支之间的关系？假设B为上图所表的树中分支（直线段）的个数，ni表示度为i的结点的个数，n为结点总数，显然有n=B+1,n=n0+n1+n2…nk,B=n0*0+n1*1+n2*2+…nk*k,问题1：图中结点个数和分支之间的关系？问题2：图中某个结点的81例如：.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8Dn=B+1,n=n0+n1+n2…nk,B=n0*0+n1*1+n2*2+…nk*k,B=n0*0+1*4+2*2+3*1+4*1=15,n=B+1=16,而n=n0+4+2+1+1=n0+8=16,n0=8例如：.设树T的度为4，其中度为1，2，3和4的结点个数分826.2二叉树

6.2.1二叉树的定义和基本运算1.定义定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。6.2二叉树6.2.1二叉树的定义和基本运算83GHDEFBCA例如：G84二叉树的5种形态：ø(a)(b)(c)(d)(e)二叉树的5种形态：ø(a)(b)(c)(d)(e)85二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1≤j<i成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。2．二叉树的性质二叉树具有下列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i≥1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=2186【性质2】深度为K的二叉树最多有2K-1个结点（K≥1）。

由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：【性质2】深度为K的二叉树最多有2K-1个结点（K≥1）。87其中a1为第一项，an为第n项，q为比值。可以得到，该数列前K项之和为：其中a1为第一项，an为第n项，88【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2（1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n89又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1（2）用（1）式减去（2）式，并经过调整后得到：n0=n2+1。满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生908910111213141545672318910111291完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。完全二叉树：有一棵深度为h，具有n个92[计算机软件及应用]栈的应用和串图课件93不是完全二叉树不是完全二叉树94【性质4】具有n个结点的完全二叉树的深度为log2n+1。其中，log2n的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1<n≤2K-1将不等式两端加1得到：2K-1≤n<2K将不等式中的三项同取以2为底的对数，并经过化简后得到：K-1≤log2n<K由此可以得到：log2n=K-1。整理后得到：K=log2n+1。【性质4】具有n个结点的完全二叉树的深度为95【性质5】对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。（2）如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，则根没有右孩子；若n<2，则根将没有左、右孩子；以上对于（2）和（3）均成立。假设：对于所有的1≤j≤i结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。【性质5】对于有n个结点的完全二叉树中的所有结962i+2

2i2i+12i+22i+3i+12i2i+1iii+12i+22i2i+12i+97由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。又因为二叉树由n个结点组成，所以，当2(i+1)+1>n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)>n，结点i+1既没有左孩子也没有右孩子。由完全二叉树的结构可以看出：结点i+98以上证明得到（2）和（3）成立。下面利用上面的结论证明（1）。对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而(2i+1)/2=i，由此可以得出（1）成立。以上证明得到（2）和（3）成立。996.2.3二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1.顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。6.2.3二叉树的存储结构1008456723184561013．2链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：3．2链式存储结构102其中，lchild和rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。在C语言中的类型定义为：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchlid;}BiTNode,*BiTree;其中，lchild和rchild是分103GHDEFBCA^G^^H^^D^E^F^B^CABT一棵二叉树及相应的链式存储结构GHD104

这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。注：在具