第一章 DS003.1 堆栈1.ppt

Data Structure Chapter 3: Stack Queue chapter 3: Stack Queue 《Data Structure》 College of Science, Xidian University 第三章 堆栈与队列 (I) 西安电子科技大学·理学院 hjTang@xidian.edu.cn 函数调用的例子 程序1的执行结果？ 程序2的执行结果？ 计算机如何执行程序？ 线性表的操作 改变线性表 插入、删除 遍历 不改变线性表 获取元素、查找元素 求前驱、后继 ——可以在任意位置进行 操作受限的线性表 限制内容 限制改变线性表内容的操作：插入、删除[、取元素内容] 限制方式 对位置的限制：只能从线性表的某些固定位置进行操作 两种操作受限的线性表 堆栈 插入、删除、获取元素只能从线性表的一端进行 队列 插入只能从线性表的一端进行 删除、获取元素的值只能从线性表另一端进行 堆栈 堆栈——只能在线性表的一端进行操作的线性表 操作 插入 删除 取值 栈顶(top，表尾) 栈底(表头) 常见的栈 书 光盘 汽车零件 栈的基本操作 入栈(Push) 出栈(Pop) 取栈顶(Top) 栈的ADT表示 栈的存储结构 顺序结构 ——顺序栈 链式结构 ——链栈 顺序栈 顺序栈(II) 栈的应用举例 数制转换 括号匹配 迷宫求解 计算器程序 数制转换 括号匹配 在一个表达式中，如何判断括号是否匹配 假定括号有 { }, [ ], ( ) 算法 看见{[(：入栈 看见)]}：出栈， 括号匹配 栈空 结束：判断栈空 迷宫求解 穷举求解法： 从入口出发，沿8个方向挨个有哪些信誉好的足球投注网站，若无路可走，则退回原路，否则，继续向前走，直到到达目的点 两种操作 前进： 走到下一个地点，并开始尝试第一个可行方向 后退： 已经尝试了所有方向，但没有发现可以继续前进的路线 退回到上次所在位置， 并从上次没有尝试过的方向继续尝试 算法描述 下一个方块 不同方向取得的不同结果 表达式求值 目的： 将一个表达式(字符串形式)转换为机器指令 4+3*(5-8/2)-9 运算的优先级 先括号，再乘除，再加减 括号匹配算法 算法表达式的三种表示方法 三种表示方法 中序 A+B A+B*C 先序 +AB +*ABC ——波兰式，无括号 后序 AB+ ABC*+ ——逆波兰式，无括号 中序?后序变换过程 A+B*C Step1: 加括号 (A+(B*C)) Step2: 移运算符 (A(BC*)+) Step3: 去括号 ABC*+ 中序?后序变换过程 中序： (A+B)*C+D+E*F-G 加括号： (((((A+B)*C)+D)+(E*F))-G) 改变顺序： (((((AB+)C*)D+)(EF*)+)G-) 去掉括号： AB+C*D+EF*+G- 逆波兰式计算过程 遇见运算符就取出前两个栈顶数据进行计算，并把结果再压入堆栈 ABCDEF+-*/+ ? (A+(B/(C*(D-(E+F))))) 问题： 计算机如何添加括号并转换顺序？ 变换算法Parsing 运算符优先级：＋－×÷（ 优先级2: *, / 优先级1: +, - 优先级0: ( 算法原则 数字直接输出，运算符缓输出 缓输出的运算符暂存于堆栈 当前运算符优先级高于栈顶优先级：入栈 当前运算符优先级底于栈顶优先级：出栈 当前运算符为“)”：出栈，直到遇见“(“ 当前运算符为“(”，无条件入栈 递归调用 ff(x, y)： ff(x, 0) = ff(0, y) = 1 ff(x, y) = ff([x/2], y) + ff(x, y-1); ax,y = ax/2, y + ax, y-1 阶乘函数Fact(n)=n! Fact(n) = n*Fact(n-1); Fact(0) = 1; Fibonacci数列 Fib(0) = Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2) * * * * 程序1 void f1() { printf(“1);} void f2() { f1(); printf(2); } void f3() { f2(); printf(3); f1(); } void f4() { f3(); printf(4); f2(); } void main(){ f4(); } 结果：1231412 程序2 int ff(int x, int y) { int res = 1; if (x y ) res = ff(x/2, y)+ff(x, y-1); return res; } void main(){ printf(%d\n, ff(10, 10