《栈的应用和串图讲解》由会员分享，可在线阅读，更多相关《栈的应用和串图讲解（56页珍藏版）》请在金锄头文库上搜索。
1、例1数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,除基取余法,void conversion( ) InitStack(s); scanf (“%d”,N); while(N) while(! StackEmpty(S) printf(“%d”,e); / conversion,p
2、ush(S,N%8);,N=N/8;,Pop(S,e);,例2 表达式求值 大家考虑一下：4+2310/5的求值运算过程 两个相继出现的运算符的优先关系,为了用栈来实现计算表达式，我们定义两个栈，一个是OPTR，用以寄存运算符，一个是OPND，用以寄存操作数或运算结果。,其基本思想如下： （1）首先置操作数栈为空栈，表达式起始符为“#”为栈的栈底元素；,（2）依次读入表达式的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶 的元素比较优先级后再做相应的操作，直到表达式求值结束（即：OPTR的栈顶元素和当前读入的字符均为“#” ）,OperandType EvaluateExpre
3、ssion() /算术表达式求值的算符优先算法，设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 =: /脱括号并接受下一个字符；
4、,Pop(OPTR,x);c=getchar(); break;,case : 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);,Push(OPND, Operate(a, theta, b); break; /switch,/while Rerurn GetTop(OPND); / EvaluateExpression 现在以3（72）演示一下。,选择题 1. 对于栈操作数据的原则是（ ）。 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 3. 一个栈的输入序列为1,2,3n，若输出序列的第一个元素是n，输出第i（1=
5、i=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定,B,B,D,D,2. 在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 为了增加内存空间的利
6、用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( )分别设在这片内存空间的两端,这样,当( )时，才产生上溢。 , : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底 : A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.,B,B,A,D,C,10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（
7、）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。 Afedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 AXYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop
8、,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop,D,D,C,B,14. 若一个栈以向量V1n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 Atop:=top+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D. V top:=x; top:=top-1 15. 若栈采用顺序存储方式存储，现两栈共享空间V1m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。 A. |top
9、2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2 16. 栈在（ ）中应用。 递归调用 B. 子程序调用 C. 表达式求值 D. A，,B,D,C,注：上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也较高，但是在有些情况下，该算法的效率却很低。,其主串的指针i在不断的回溯，如i=3,变为i=2,i=7变为i=4 其时间复杂度可达到O(n*m).,KMP算法，其时间复杂度为：O(n+m),如果主串i上的字符不匹配的时候，则主串i上的字符应该再与模式串上的那个字符相比较，也就是说，如果出现不匹配的时候，模式串应该“向右滑动”
10、多远？,模式串的next函数定义如下：,例子： 1.求模式串 T=a b c a c的next函数值 next= 0 1 1 1 2 2.求模式串 T=a b a a b c a c的next函数值,因为next3=1，说明主串的第3个字符a（i=3）应该再与模式串的第1个字符a相比较，故出现了第二趟比较的情况；,因next5=2，说明主串的第7个字符a（i=7）应该再与模式串的第2个字符b相比较，故出现了第三趟比较的情况。,注：nextj仅取决于模式串本身而和相匹配的主串无关。下面推导其递推算法,显然：next1=0;,假设nextj=k,则说明在模式串中存在：,p1p2pk-1=pj-k+
11、1 pj-k+2pj-1,怎么求nextj+1?,如果pk=pj，则说明:,p1p2pk-1 pk=pj-k+1 pj-k+2pj-1 pj,于是nextj+1=k+1=nextj+1,如果pk!=pj，则这又是一个模式匹配问题，其中主串和模式串相同,于是模式串应该向右滑动至pj与pnextk相对齐，继续比较，又分两种情况： pj= pnextk和pj与 pnextk不相等。,若pj= pnextk,则nextj+1=nextk+1;,若pj!=pnextk , 则考察pj和pnextnextk ,若pj=p nextnextk , 则nextj+1=nextnextk+1,若pj!=p ne
12、xtnextk ,则继续比较下去,若pj!=pnextnextk=p1, 即: nextnextk=1,则nextj+1=1.,例子：T=abaabcac,next3=next2+1, next2=1, 而p2!=p1, 所以next3=next1+1=1,next4=next3+1, next3=1, 因为p3=p1,所以next4=next3+1=2,next5=next4+1, next4=2, 而p4!=p2, 又next2=1, p4=p1,所以,next5=next2+1=2.,next6=next5+1, next5=2, 因为p5=p2, 所以next6=next5+1=3.,
13、next7=next6+1, next6=3, 而p6!=p3, next3=1, 又p6!=p1,所以next7=next1+1=1,next8=next7+1, next7=1, 因为p7=p1, 因此next8=next7+1=2,上述定义的函数在某些情况下尚有缺陷，如,在出现这种情况的时候，即第一个字符与主串中的相应字符不匹配的时候，因为模式串前四个字符相同，主串中的字符不需要和第2，3，4个字符比较，所以可以把其nextj作如下修改：,4已知串S=aaab,其Next数组值为（ ）。 A0123 B1123 C1231 D1211,5串 ababaaababaa 的next数组为（
14、）。 A012345678999 B012121111212 C011234223456 D0123012322345,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 ),A,C,A,1、树的定义和基本术语,2、 二叉树,6.1 树,6.1.1 树的定义和基本运算 1. 定义 树是一种常用的非线性结构。我们可以这样定义：树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。 由此可以看出，树的定义是递归。,树还有其他的表示形式:：1以嵌套集合的形式表示；2以广义表的形式表示；3 以凹入法表示（类似书的编目）,K L M,E F G H I J,B C D,A,A,(a),(b),(c),基本术语,结点： 包含一个数据元素及若干指向其子树根的分支。 结点的度 ：结点拥有的子树数，即结点的分支数。 终端结点（叶子）： 度为0的结点。 非终端结点 ：
