栈和队列-北京师范大学.ppt

导航图(3) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(4) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(5) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(6) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(7) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(8) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 导航图(9) 栈和队列 栈 栈的应用 递归问题的 非递归算法 队列 队列的应用 (迷宫最短路径) 括号匹配检查 表达式求值 迷宫路径 斐波那契 Ackerman 函数 汉诺塔问题 二、栈的应用——算术表达式求值(4) case =: while(s2.elem[s2.top].word.op!=() {/*反复出栈处理，直到遇到最开始放在栈里的左括号为止*/ if(!Pop(s1,W2)||!Pop(s1,W1)||!Pop(s2,W3)) /*表达式有错*/ {DestroySqstack(s1); DestroySqstack(s2); return 0; } if(!(W2.word.X==0W3.word.op==/)) { W1.word.X=comput(W1.word.X,W3.word.op,W2.word.X); Push(s1,W1);/*计算结果入栈*/ } else {DestroySqstack(s1);DestroySqstack(s2); return 0; } /*表达式计算出现了除以0的情况*/ } *result=s1.elem[s1.top].word.X;/*操作数栈顶的值就是最终的表达式的值*/ if(s1.top!=0) {DestroySqstack(s1); DestroySqstack(s2); return 0; } else { DestroySqstack(s1); DestroySqstack(s2); return 1; } 二、栈的应用——算术表达式求值(5) default: while(InPri(s2.elem[s2.top].word.op)OutPri(w.word.op)) {/*只要栈顶运算符的优先级数大于栈外运算符的优先级数，则反复出栈处理*/ if(!Pop(s1,W2)||!Pop(s1,W1)||!Pop(s2,W3)) { DestroySqstack(s1); DestroySqstack(s2); return 0; } if(!(W2.word.X==0W3.word.op==/)) { W1.word.X=comput(W1.word.X,W3.word.op,W2.word.X); Push(s1,W1); } else { DestroySqstack(s1); DestroySqstack(s2); return 0; } } Push(s2,w);/*此时栈外运算符优先级数高，入栈*/ break; }/*属于switch语句*/ }/*属于while(1)语句*/ } 二、栈的应用——迷宫路径求解(1) 【任务描述】给定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，注意横坐标是从左向右的，