数据结构第06讲-栈的应用2与递归c

1、第3章 栈和队列3.1 栈3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.4 迷宫求解 3.2.5 表达式求值3.3 栈与递归的实现3.4 队列 通常用“穷举求解”方法。3.2.4 迷宫求解求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前

2、位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； 否则 求迷宫中一条从入口到出口的路径的算法： 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个有可通相邻块的位置 或出栈至栈空； while (栈不空)；若栈空，则表明迷宫没有通路。第3章 栈和队列3.1 栈3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.4

3、迷宫求解 3.2.5 表达式求值3.3 栈与递归的实现3.4 队列 3.2.5 表达式求值以表达式 A*B + CD 为例说明利用栈的求值过程： 操作数：常数、变量或常量标识符 运算符：* / * + - 界限符： ( ) # 优先级：运算符和界限符统称算符。思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是算符，应进行判断：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。2. 若读入的

4、运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。3. 若读入的是“#”，且算符栈顶的符号也是“#”时，则表达式处理结束。从操作数栈弹出表达式结果。A*B + C/Dtop2top1初态#(a)OSNSBA*#(b)NSOST1#(c)T1=A*BNSOSDCT1/+#(d)NSOS(g)NSOST2=C/DT2T1+#(e)NSOST3#(f)T3=T2+T1NSOS算术表达式求值的算符优先算法。OperandType EvaluateExpressiOn

5、( ) /设OPTR和OPND分别为运算符栈和运算数栈。OP为运算符集合。 InitStack(OPTR)； InitStack(OPND)； Push(OPTR，#)； c=getchar()；while (c !=#| GetTop(OPTR)!=#)if(!In(c,OP) /不是运算符则进栈 Push(OPND,c); c=getchar( ); elseswitch ( Precede ( GetTop (OPTR)，c)case ： /退栈并将运算结果入栈Pop(OPTR，theta)； Pop(OPND，b)； Pop(OPND，a)； Push(OPND，Operate(a，t

6、heta，b)；break ；/注意这里无c=getchar() /swith/whilereturn GetTop(OPND)； /end of EvaluateExpression 由于栈结构具有的后进先出的特性，致使栈成为程序设计中的有用工具。在系统软件设计以及应用软件中解决实际问题都有广泛的应用。 栈的其他应用还有：子程序的调用、处理递归调用、二叉树的遍历、图的深度优先搜索法等。第3章 栈和队列3.1 栈3.2 栈的应用举例3.3 栈与递归的实现3.4 队列 3.3 栈与递归的实现 当求解一个问题时，是通过求解与它同样解法的子问题而得到的，这就是递归。 或理解为子程序或函数反复的调用自

7、己，并传入不同的变量来执行的一种程序设计技巧。 是程序设计及解题的一种有力的、重要的工具，帮助程序设计者解决复杂问题，并精简程序结构。例：设计一个乘法器，可以计算出两个数相乘的乘积。但是此时计算机不能提供乘法运算（仅知道任何数乘 1，其值不变），则唯一可以使用的运算方式就是加法运算。即： 11 * 3是 11 连加 3 次 (11 * 3) = 11 + （11 * 2） = 11 + （11 + （11 * 1）) = 11 + （11 + 11） = 11 + 22 = 33使用递归的一个重要问题 一个递归的求解问题必然包含有终止递归的条件，当满足一定条件时就终止向下递归，从而使问题得以解

8、决。 解决递归问题的算法称递归算法，在递归算法中需要根据递归条件直接或间接地调用算法本身，当满足某种条件时结束递归调用。当然对于一些简单的递归问题，很容易把它转换为循环问题解决，从而使编写出的算法更为有效。将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。 从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是:此时的内存管理实行

9、“栈式管理”后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。 递归函数执行的过程可视为同一函数进行嵌套调用，例如：例1：采用递归算法求解正整数n的阶乘（n!） 用C语言编写出求解n!的递归函数为： long f（int n） if （n = = 0） return 1; else return n

10、 * f（n 1）; f(n) = 1 (n=0) nf(n-1) (n0)4r13r24r12r33r24r1进行f(4)调用的系统栈的变化状态0r41r42r33r24r11r42r33r24r14r13r24r12r33r24r1进行f(4)调用的系统栈的变化状态1r42r33r24r1例2：最大公因子问题 数学上利用辗转相除法解决。同时此种方法也称为欧几理德定理，其定义为：GCD(M，N) =GCD（N，M % N） （N0）M （N=0）写出求解最大公因子的递归函数为： long GCD（int M，int N） / 前提条件：MN if （N = = 0） /递归结束条件 retu

11、rn M ； else return GCD（N，M % N）； 假设有三个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1、2、n的圆盘。现要求将X轴上的n个圆盘移到塔座Z上并仍按同样的顺序叠排，圆盘移动时必须遵循下列规则： 1）每次只能移动一个圆盘； 2）圆盘可以插在X、Y、Z的任一塔座上； 3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上。例3：汉诺（hanoi)塔问题void hanoi (int n, char x, char y, char z)/ 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1

12、 2 if (n=1)3 move(x, 1, z); / 将编号为的圆盘从x移到z4 else 5 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔6 move(x, n, z); / 将编号为n的圆盘从x移到z7 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔8 9 递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc主函数： 执行调用语句hanoi (3,a,b,c) ，入栈。层1： 执行1,2,4,5语句，产生向下调用，进层2。递归工作栈状态(返址,

13、n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b层2 入栈，记录层1的返回地址6等信息； 执行2层的1,2,4,5语句，执行到语句再向下调用，进入层3。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c层3 入栈，记录层2的返回地址6等信息； 执行1,2,3,9语句，过程执行完。层 第层调用结束，出栈，返回第2层； 从第2层的断点语句执行； 执行到语句，又开始向下递归调用到第3层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a

14、, b, cabc6, 2, a, c, b6, 1, a, b, c层3 入栈,记录层2的返回地址8等信息； 执行语句1,2,3,9,过程执行完。 出栈，返回第2层断点语句8。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b8, 1, c, a, b层 从第3层返回后，从断点开始执行，执行语句8,9，过程执行完，出栈，返回第1层。层 从第2层返回后，从断点开始执行；执行到语句，又开始向下递归调用到层2，入栈，记录第1层的返回地址8等信息。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b8, 2, b, a, c层 执行到语句，向下递归调用。层 执行语句,2,3,9，结束，返回第2层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc8, 2, b, a, c6, 1, b, c, a层 从断点语句6开始执行，执行到语句7，向下递归调用，到层