【教学课件】第三章栈与队列.ppt

第三章 栈与队列,东南大学计算机学院 方效林,本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件,本章主要内容,栈栈的应用：表达式求值栈与递归队列队列的应用：电路布线,2,栈,定义：只允许在表的末端进行插入和删除的线性表特点：先进后出栈的操作进栈 push()出栈 pop()栈顶 top()置空 setEmpty()判断是否为空 isEmpty()栈满 isFull(),3,栈,栈的数组表示栈的操作进栈 push()出栈 pop()栈顶 top()置空 makeEmpty()判断是否为空 isEmpty()栈满 isFull(),4,a,b,c,空栈,栈,栈的单链表表示栈的数组表示可能栈满栈的单链表表示无栈满问题入栈在表头进行插入操作出栈在表头进行删除操作,5,栈,进栈顺序为(1,2,3)，出栈顺序能否为(3,1,2)?不能，3出栈时，说明2和1都在栈里，而且2必须先于1出栈,6,作业：1，2，3，4，5，6依次进栈，若出栈顺序为2，3，4，6，5，1则栈大小至少为多少？,栈的应用：表达式求值,一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。算术表达式三种表示中缀(infix)表示，如 A+B；前缀(prefix)表示，如+AB；后缀(postfix)表示，如 AB+；,7,栈的应用：表达式求值,中缀表达式：A+B*(C-D)-E/F后缀表达式：A B C D-*+E F/-表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。前缀和中缀表达式求值需要两个栈；后缀表达式求值只需一个栈，相对简单些。,8,栈的应用：表达式求值,从左向右扫描表达式，用一个栈暂存扫描到的操作数或计算结果。后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现,9,中缀表达式：,后缀表达式：,10,作业：写出下列中缀表达式的后缀表达式A*B*C-A+B-C+DA*(-B)+C(A+B)*D+E/(F+A*D)+CA&B|!(EF)!(A&!(BD)|(CE),栈的应用：表达式求值,后缀表达式求值过程顺序扫描后缀表达式每一项若该项是操作数，则进栈若该项是操作符，若是单目运算符，则出栈一个操作数X，并将计算结果X进栈若是双目运算符，则连续出栈两个操作数X和Y，并将计算结果X Y进栈当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。,11,栈的应用：表达式求值,12,B,A,C,D,后缀表达式求值过程：,栈的应用：表达式求值,13,B,A,C,D,R1=C-D,后缀表达式求值过程：,栈的应用：表达式求值,14,B,A,R1=C-D,R2=B*R1,后缀表达式求值过程：,栈的应用：表达式求值,15,A,R2=B*R1,R3=A+R2,后缀表达式求值过程：,栈的应用：表达式求值,16,R3=A+R2,E,F,后缀表达式求值过程：,栈的应用：表达式求值,17,R3=A+R2,E,F,R4=E/F,后缀表达式求值过程：,栈的应用：表达式求值,18,R3=A+R2,R4=E/F,R5=R3-R4,后缀表达式求值过程：,栈的应用：表达式求值,中缀表达式转换为后缀表达式使用栈将中缀表达式转换成前缀或后缀表达式。为了实现转换，需要考虑各操作符的优先级。结束符“#”优先级最低左括号“(”栈外优先级最高，进栈后极低右括号“)”栈外优先级极低其他进栈后优先级加1，这可满足自左向右计算要求,19,各个算术操作符的优先级,栈的应用：表达式求值,中缀表达式转换为后缀表达式算法操作符栈初始化，结束符#进栈，读入中缀表达式的首字符ch重复执行以下步骤，直到ch=#，同时栈顶操作符也是#，停止循环若ch是操作数直接输出，读入下一字符ch若ch是操作符，比较ch和栈顶操作符op优先级：若icp(ch)isp(op)，令ch进栈，读入下一字符ch若icp(ch)isp(op)，退栈，并输出若icp(ch)=isp(op)，退栈不输出；若退出的是(，则读入下一个字符ch算法结束，输出序列即为所得后缀表达式,20,栈的应用：表达式求值,21,中缀表示转换为后缀表示过程：,A,C,后缀输出：,#,+,*,（,-,B,栈的应用：表达式求值,22,中缀表示转换为后缀表示过程：,A,B,C,D,-,后缀输出：,#,+,*,（,-,栈的应用：表达式求值,23,中缀表示转换为后缀表示过程：,#,+,*,A,B,C,D,-,*,+,后缀输出：,栈的应用：表达式求值,24,中缀表示转换为后缀表示过程：,#,-,/,A,B,C,D,-,*,+,E,F,/,-,后缀输出：,作业,程序实现简单的中缀表达式求值数字均为一位数，即0-9运算符只有+-*/(),25,栈与递归,递归的定义若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的,26,栈与递归,定义是递归的例如，阶乘函数(Factorial)求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);,27,栈与递归,定义是递归的例如，阶乘函数(Factorial),28,栈与递归,数据结构是递归的例如，单链表结构搜索单链表中值等于x的结点 LinkNode*Search(LinkNode*f,Type x)if(f=null)return null;else if(f-data=x)return f;else Search(f-link,x);,29,struct LinkNode Type data;LinkNode*link;,栈与递归,问题解法是递归的例如，汉诺塔(Tower of Hanoi)问题的解法有3根标号为A、B、C的柱子，A柱上又叠着64个从小到大排放的盘子。目的是要将A柱的盘子全部移到C柱上。移动条件是一次只能移动一个盘子，移动过程中大盘子不能放在小盘子上面求解汉诺塔问题的递归算法若 n=1，将盘子直接从 A 柱移到 C 柱。否则，执行以下三步：用 C 柱做过渡，将 A 柱上的(n-1)个盘子移到 B 柱上；将 A 柱上最后一个盘子直接移到 C 柱上；用 A 柱做过渡，将 B 柱上的(n-1)个盘子移到 C 柱上。,30,栈与递归,问题解法是递归的例如，汉诺塔(Tower of Hanoi)问题的解法,31,void Hanoi(int n,char 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个圆盘的汉诺塔的移动,栈与递归,问题解法是递归的例如，汉诺塔(Tower of Hanoi)问题的解法,32,4个圆盘的汉诺塔的移动,栈与递归,用栈将递归转换为非递归汉诺塔(Tower of Hanoi)问题的解法,33,void Hanoi(int n,char a,char b,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=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;,栈与递归,用栈将递归转换为非递归汉诺塔(Tower of Hanoi)问题的解法,34,(3,A,B,C),栈与递归,用栈将递归转换为非递归汉诺塔(Tower of Hanoi)问题的解法,35,(1,A,B,C),(2,B,A,C),(2,A,C,B),栈与递归,用栈将递归转换为非递归汉诺塔(Tower of Hanoi)问题的解法,36,(1,A,B,C),(2,B,A,C),(1,C,A,B),(1,A,C,B),(1,A,B,C),栈与递归,用栈将递归转换为非递归汉诺塔(Tower of Hanoi)问题的解法,37,(1,A,B,C),(1,B,A,C),(1,B,C,A),寻找凸包,给定平面上n个点的集合Q，求Q的凸包,38,Q的convex hull是一个凸多边形P，Q的点或者在P上或者在P内,凸多边形P是具有如下性质多边形：连接P内任意两点的边都在P内,寻找凸包,Graham-scan的基本思想找到最下最左顶点，其他顶点与它连线按夹角从小到大排序夹角最小的开始，寻找凸包点,39,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p8,p6,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p8,p6,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p8,p6,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p6,p8,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p6,p8,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p6,p8,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,p0,p2,p1,p7,p6,p8,p5,p4,p3,p10,p9,寻找凸包,Graham-scan的基本思想,47,Graham-scan(Q)1.求Q中y-坐标值最小的点p0；2.按照与p0极角(逆时针方向)大小排序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.Push(pi,S);8.Rerurn S；,O(nlogn),O(n),O(1),O(n),总时间复杂度O(nlogn),循环为什么是O(n),最多n次入栈，那么出栈也是最多n次,队列,定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特点：先进先出队列的操作入队 EnQueue()出队 DeQueue()判断是否为空 isEmpty()队列满 isFull(),48,队列,队列的数组表示 入队：在rear 位置加入数据，rear=rear+1出队：在front位置取出数据，front=front+1,49,A,B,C,D,E,F,空队列,A入队,B、C入队,A出队,B出队,D、E、F入队,队列,队列的数组表示(循环队列)入队：在rear 处加入数据，rear=(rear+1)%SIZE出队：在front处取出数据，front=(front+1)%SIZE队满：(rear+1)%SIZE=front队空：rear=front,50,D,E,F,G,H,A,B,C,空队列,A入队,B、C、D入队,A、B出队,E、F、G、H、I入队,I,队列,队列的单链表表示队列的数组表示可能队列满队列的单链表表示无队列满问题入队在表尾进行插入操作出队在表头进行删除操作,51,打印二项展开式(a+b)i 的系数,杨辉三角形,52,(a+b)1=a+b,(a+b)2=a2+2ab+b2,(a+b)3=a3+3a2b+3ab2+b3,打印二项展开式(a+b)i 的系数,第i行与第i+1行关系,53,i=2,i=3,i=4,打印二项展开式(a+b)i 的系数,54,0,0,1,2,1,0,1,1,1,3,3,1,0,出队列时与前一个出队列的数相加，结果入队列0作为被加数时，0入队列，作为分隔符,队列的应用：电路布线,找最短路径网格方式布线，布线不能有重叠，转弯用直角,55,队列的应用：电路布线,找最短路径,56,(1,1),(0,1),(1,0),(2,1),(2,0),(3,1),(3,0),(3,2),(3,3),已访问,null,(1,1),(1,1),(1,1),(1,0),(2,1),(2,0),(3,1),(3,2),