第三章栈与队列(编辑修改稿)

第三章栈与队列(编辑修改稿)内容摘要：

icp( ( ), 进栈 + * ( AB 6 C 操作数 + * ( ABC 7 操作符 isp( ( ) icp(), 进栈 + * ( ABC 8 D 操作数 + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退栈 + * ( ABCD– isp(( ) == icp( )), 退栈 + * ABCD 中缀表示转换为后缀表示过程： A B C D * + E F / ) ( A C 后缀输出： + top top 空栈 top * （ top top top B 栈的应用：表达式求值 22 步 输入 类型 动作 栈内容 后缀输出 0 进栈 1 A 操作数 A 2 + 操作符 isp() icp(+), 进栈 + A 3 B 操作数 + AB 4 * 操作符 isp(+) icp(*), 进栈 + * AB 5 ( 操作符 isp(*) icp( ( ), 进栈 + * ( AB 6 C 操作数 + * ( ABC 7 操作符 isp( ( ) icp(), 进栈 + * ( ABC 8 D 操作数 + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退栈 + * ( ABCD– isp( ( ) == icp( ) ), 退栈 + * ABCD 中缀表示转换为后缀表示过程： A B C D * + E F / ) ( A B C D 后缀输出： + * （ top top top 栈的应用：表达式求值 23 步 输入 类型 动作 栈内容 后缀输出 10 操作符 isp(*) icp(), 退栈 + ABCD* isp(+) icp(), 退栈 ABCD*+ isp() icp(), 进栈 ABCD*+ 11 E 操作数 ABCD*+E 12 / 操作符 isp() icp(/), 进栈 / ABCD*+E 13 F 操作数 / ABCD*+EF 14 操作符 isp(/) icp(), 退栈 ABCD*+EF/ isp() icp(), 退栈 ABCD*+EF 结束 中缀表示转换为后缀表示过程： A B C D * + E F / ) ( + top top * top A B C D * + 后缀输出： 栈的应用：表达式求值 24 步 输入 类型 动作 栈内容 后缀输出 10 操作符 isp(*) icp(), 退栈 + ABCD* isp(+) icp(), 退栈 ABCD*+ isp() icp(), 进栈 ABCD*+ 11 E 操作数 ABCD*+E 12 / 操作符 isp() icp(/), 进栈 / ABCD*+E 13 F 操作数 / ABCD*+EF 14 操作符 isp(/) icp(), 退栈 ABCD*+EF/ isp() icp(), 退栈 ABCD*+EF 结束 中缀表示转换为后缀表示过程： A B C D * + E F / ) ( top top / top A B C D * + E F / 后缀输出： 作业  程序实现简单的中缀表达式求值  数字均为一位数，即 09  运算符只有 + * / ( ) 25 栈与递归  递归的定义  若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。  以下三种情况常常用到递归方法。  定义是递归的  数据结构是递归的  问题的解法是递归的 26 栈与递归  定义是递归的  例如 ，阶乘函数 (Factorial)  求解 阶乘函数的递归算法 long Factorial ( long n ) { if (n == 0) return 1。 else return n*Factorial(n1)。 } 27 时当时当 1 ,)!1( 0 ,1!nnnnn栈与递归  定义是递归的  例如，阶乘函数 (Factorial) 28 主程序 main : fact(4) 参数 4 计算 4*fact(3) 返回 24 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 参数 1 计算 1*fact(0) 返回 1 参数 0 直接定值 = 1 返回 1 参数传递 结果返回 递归调用 回归求值 栈与递归  数据结构是递归的  例如，单链表结构  搜索单链表中值等于 x的结点 LinkNode*Search(LinkNode *f, Type x) { if(f == null) return null。 else if(fdata == x) return f。 else Search(flink, x)。 } 29 a1 first a2 a3 an null ∙∙∙ struct LinkNode { Type data。 LinkNode *link。 }。 栈与递归  问题解法是递归的  例如，汉诺塔 (Tower of Hanoi) 问题的解法 有 3根标号为 A、 B、 C的柱子， A柱上又叠着 64个从小到大排放的盘子。 目的是要将 A柱。