栈满isFull东南大学计算机科学与工程学院实用教案

1、会计学1栈满栈满isFull东南大学计算机科学与工程学东南大学计算机科学与工程学院院第一页，共56页。2第第1页页/共共56页页第二页，共56页。n isFull()3第第2页页/共共56页页第三页，共56页。4topabtopctop空栈空栈top第第3页页/共共56页页第四页，共56页。5topcbanull第第4页页/共共56页页第五页，共56页。6321top作业：作业：1，2，3，4，5，6依次进栈，若出栈顺序依次进栈，若出栈顺序(shnx)为为2，3，4，6，5，1则栈大小至少为多少？则栈大小至少为多少？第第5页页/共共56页页第六页，共56页。7第第6页页/共共56页页第七页，共

2、56页。8第第7页页/共共56页页第八页，共56页。9R1R2 2R3R4R5A B C D - * + E F / -R1R2 2R3R4R5A+B*(C-D)-E/F中缀表达式：中缀表达式：后缀后缀(huzhu)表达式：表达式：第第8页页/共共56页页第九页，共56页。10作业：作业：写出下列写出下列(xili)中缀表达式的后缀表达式中缀表达式的后缀表达式A*B*C-A+B-C+DA*(-B)+C(A+B)*D+E/(F+A*D)+CA&B|!(EF)!(A & !(BD) | (CE)第第9页页/共共56页页第十页，共56页。11第第10页页/共共56页页第十一页，共56页。12步步输入

3、输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R

4、3-R4进栈进栈R5top空栈空栈topBACDtoptoptopABCD-*+EF/-后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第11页页/共共56页页第十二页，共56页。13步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E

5、操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5BACDtoptoptopR1=C-DABCD-*+EF/-后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第12页页/共共56页页第十三页，共56页。14步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计

6、算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5BAtopR1=C-DtoptopABCD-*+EF/-R2=B*R1后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第13页页/共共56页页第十四页，共56页。15步步输入输入类

7、型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R

8、4进栈进栈R5AtoptopABCD-*+EF/-R2=B*R1R3=A+R2空栈空栈top后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第14页页/共共56页页第十五页，共56页。16步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R3

9、9E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5toptopABCD-*+EF/-R3=A+R2EFtop后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第15页页/共共56页页第十六页，共56页。17步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，

10、计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5ABCD-*+EF/-R3=A+R2EFtopR4=E/Ftoptop后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第16页页/共共56页页第十七页，共56页。18步步输入输入

11、类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-

12、R4进栈进栈R5ABCD-*+EF/-R3=A+R2R4=E/FtoptopR5=R3-R4空栈空栈top后缀后缀(huzhu)表达式求值过程：表达式求值过程：第第17页页/共共56页页第十八页，共56页。19各个各个(gg)算术操作符的优先级算术操作符的优先级操作符操作符#(* / %+ - )isp(栈内优先级栈内优先级)01536icp(栈外优先级栈外优先级)06421第第18页页/共共56页页第十九页，共56页。n若icp(ch) isp(op)，退栈，并输出n若icp(ch)=isp(op)，退栈不输出；若退出的是(，则读入下一个字符chn算法结束(jish)，输出序列即为所得后缀表

13、达式20第第19页页/共共56页页第二十页，共56页。21步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出0#进栈进栈#1A操作数操作数# A 2+操作符操作符isp(#) icp(+), 进栈进栈# +A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ) = icp( ), 退栈退栈# + *ABCD-中缀表示中缀表示(biosh)转

14、换为后缀表示转换为后缀表示(biosh)过程：过程：ABCD-*+EF/-)(AC后缀后缀(huzhu)输出：输出：#+toptop空栈空栈top*（-toptoptopB第第20页页/共共56页页第二十一页，共56页。22步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出0#进栈进栈#1A操作数操作数# A 2+操作符操作符isp(#) icp(+), 进栈进栈# +A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操

15、作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ( ) = icp( ) ), 退栈退栈# + *ABCD-中缀表示转换中缀表示转换(zhunhun)为后缀表示过程：为后缀表示过程：ABCD-*+EF/-)(ABCD-后缀后缀(huzhu)输出：输出：#+*（-toptoptop第第21页页/共共56页页第二十二页，共56页。23步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出10-操作符操作符isp(*) icp(-), 退栈退栈# + ABCD-*isp(+) icp(-), 退栈退栈#ABCD-*+isp(#) icp(-), 进栈进栈# -AB

16、CD-*+11E操作数操作数# -ABCD-*+E12/操作符操作符isp(-) icp(/), 进栈进栈# - /ABCD-*+E13F操作数操作数# - /ABCD-*+EF14#操作符操作符isp(/) icp(#), 退栈退栈# -ABCD-*+EF/isp(-) icp(-), 退栈退栈# + ABCD-*isp(+) icp(-), 退栈退栈#ABCD-*+isp(#) icp(-), 进栈进栈# -ABCD-*+11E操作数操作数# -ABCD-*+E12/操作符操作符isp(-) icp(/), 进栈进栈# - /ABCD-*+E13F操作数操作数# - /ABCD-*+EF1

17、4#操作符操作符isp(/) icp(#), 退栈退栈# -ABCD-*+EF/isp(-) link, x);n 29a1firsta2a3annullstruct LinkNode Type data; LinkNode *link;第第28页页/共共56页页第二十九页，共56页。n否则，执行以下三步：n用 C 柱做过渡，将 A 柱上的(n-1) 个盘子移到 B 柱上；n将 A 柱上最后一个盘子直接(zhji)移到 C 柱上；n用 A 柱做过渡，将 B 柱上的(n-1) 个盘子移到 C 柱上。30第第29页页/共共56页页第三十页，共56页。31void Hanoi ( int n, ch

18、ar A, char B, char C ) if (n = 1) printf( move %s, A, to %s , C ); else Hanoi ( n-1, A, C, B ); printf ( move %s, A, to %s , C ); Hanoi ( n-1, B, A, C ); 3个圆盘个圆盘(yun pn)的汉诺塔的移动的汉诺塔的移动第第30页页/共共56页页第三十一页，共56页。324个圆盘个圆盘(yun pn)的汉诺塔的移动的汉诺塔的移动第第31页页/共共56页页第三十二页，共56页。33void Hanoi ( int n, char a, char b,

19、char c) Stack S; initStack(S); Node q; q.n = n; q.A = a; q.B = b; q.C = c; Push (S, q); while ( ! StackEmpty(S) ) Pop(S, q); n = q. n; a = q.A; b = q.B; c = q.C; if ( n = 1 ) printf (“Move %c”, a, “ to %c”, c); else q.n = n-1; q.A = b; q.B = a; q.C = c; Push (S, q); q.n = 1; q.A = a; q.B = b; q.C =

20、c; Push (S, q); q.n = n-1; q.A = a; q.B = c; q.C = b; Push (S, q); Struct Node int n; char A,B,C;(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C第第32页页/共共56页页第三十三页，共56页。34(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)

21、(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(3,A,B,C)空栈空栈top第第33页页/共共56页页第三十四页，共56页。35(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(2,A,C,B)toptop第第34页页/共共56页页第三十五页，共56页。36(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,

22、C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(1,C,A,B)toptop(1,A,C,B)(1,A,B,C)toptop空栈空栈top第第35页页/共共56页页第三十六页，共56页。37(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C(1,A,B,C)(1,B,A,C)topt

23、op(1,B,C,A)top空栈空栈top第第36页页/共共56页页第三十七页，共56页。38Q的的convex hull是一个是一个(y )凸多边形凸多边形P，Q的点或者在的点或者在P上或者在上或者在P内内凸多边形凸多边形P是具有如下性质多边形：是具有如下性质多边形：连接连接P内任意两点的边都在内任意两点的边都在P内内第第37页页/共共56页页第三十八页，共56页。39第第38页页/共共56页页第三十九页，共56页。第第39页页/共共56页页第四十页，共56页。第第40页页/共共56页页第四十一页，共56页。第第41页页/共共56页页第四十二页，共56页。第第42页页/共共56页页第四十三页

24、，共56页。第第43页页/共共56页页第四十四页，共56页。第第44页页/共共56页页第四十五页，共56页。第第45页页/共共56页页第四十六页，共56页。47Graham-scan(Q)1. 求求Q中中y-坐标值最小的点坐标值最小的点p0；2. 按照与按照与p0极角极角(逆时针方向逆时针方向)大小大小(dxio)排序排序Q中其中其余点，余点， 结果为结果为；3. Push(p0, S); Push(p1, S); Push(p2, S);4. FOR i=3 TO m DO5. While Next-to-top(S)、Top(S)和和pi形成非左移动形成非左移动 Do6. Pop(S);7

25、. Push(pi, S);8. Rerurn S；O(nlogn)O(n)O(1)O(n)总时间复杂度总时间复杂度O(nlogn)循环为什么是循环为什么是O(n)最多最多n次入栈，次入栈，那么出栈也是最多那么出栈也是最多n次次第第46页页/共共56页页第四十七页，共56页。nn队列满 isFull()48第第47页页/共共56页页第四十八页，共56页。49ABCDEFfrontrear空队列空队列(duli)A入队入队B、C入队入队A出队出队B出队出队D、E、F入队入队rearrearrearfrontfront第第48页页/共共56页页第四十九页，共56页。5012345670DEFGHABC空队列空队列(duli)A