1、第 3 章 限定性线性表栈和队列 4.迷宫求解迷宫求解（穷举法）（穷举法）3.2 栈的应用举例栈的应用举例0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 l当前位置：某一时刻所在图当前位置：某一时刻所在图中某个方块位置。中某个方块位置。l当前位置可通：未曾走到过当前位置可通：未曾走到过的通道块，既要求该方块位置的通道块，既要求该方块位置不在当前位置上，也不是曾经不在当前位置上，也不是曾经纳入过路径的通道块。纳入过路径的通道块。回路不能出现，简单路径；回路不能出现，简单路径；防止在死胡同内转圈。防止在死胡同内转圈。l下一位置：当前位置四周四下一位置：当前位置四周四个方
2、向上相邻的方块。个方向上相邻的方块。第 3 章 限定性线性表栈和队列 l 从入口到出口的路径算法从入口到出口的路径算法设当前位置的初值为入口位置；设当前位置的初值为入口位置；do 若当前位置可通，则若当前位置可通，则 将当前位置插入栈顶；将当前位置插入栈顶；若该位置为出口位置，则结束；若该位置为出口位置，则结束；将该位置的东邻块置为当前位置；将该位置的东邻块置为当前位置；否则否则 若栈不空且栈顶位置尚有其它方向未经探索，则若栈不空且栈顶位置尚有其它方向未经探索，则 设定新的当前位置为栈顶位置的下一相邻块；设定新的当前位置为栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不通，则若栈不空但栈顶位
3、置的四周均不通，则 删去栈顶位置；删去栈顶位置；若栈不空，则若栈不空，则 重新测试新的栈顶位置，直至找到一个可通的重新测试新的栈顶位置，直至找到一个可通的 相邻块或栈至栈空；相邻块或栈至栈空；while(栈不空栈不空)第 3 章 限定性线性表栈和队列 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 typedef struct int ord;/在路径上的序号在路径上的序号 int i,j;/坐标坐标 int dir;/当前位置下一方向当前位置下一方向SElemType;ord i j dir 1 (1,1)1 2 (1,2)2 3 (2,2)2 4 (3,2)1
4、5 (3,3)1 6 (3,4)4 7 (2,4)1 8 (2,5)1 9 (2,6)410 (1,6)311 (1,5)312 (1,4)X13 (3,1)214 (4,1)2 4 (3,2)第 3 章 限定性线性表栈和队列 l迷宫迷宫maze的表示：的表示：char maze1010=;：未曾走过；：未曾走过；*：在当前路径上；：在当前路径上；#：墙；：墙；X：曾走过。：曾走过。char*maze;maze=(char*)malloc(m*sizeof(char*);for(i=1;i=n;i+)mazei=(char*)malloc(n*sizeof(char);l下一位置：下一位置：i
5、nt movei4=1,0,-1,0;int movej4=0,1,0,-1;设当前位置为设当前位置为e(i,j)，则，则e(i,j)的下一位置：的下一位置：i=e.i+moveie.dir-1;j=e.j+moveje.dir-1;l当前通道块是否可通：当前通道块是否可通：if(mazeij=)可通；可通；第 3 章 限定性线性表栈和队列 操作数操作数（operand）、运算符运算符（operator）、界限符界限符(delimiter 左右括号和表达式结束符），左右括号和表达式结束符），运算符和界限运算符和界限符统称符统称算符算符。（7+15）*（23-28/4）(1)从左算到右；从左算到
6、右；(2)先乘除，先乘除，后加减；后加减；(3)先括号内，先括号内，后括号外。后括号外。OPND栈栈和和OPTR栈栈操作数入操作数入OPND栈，算符入栈，算符入OPTR栈栈l表达式求值（算符优先算法）表达式求值（算符优先算法）第 3 章 限定性线性表栈和队列 l12，表明可以进行，表明可以进行1 的运算，的运算，1退栈，运算，退栈，运算，运算结果入栈。运算结果入栈。l1=2，脱括号，读下一字符或表达式结束。，脱括号，读下一字符或表达式结束。第 3 章 限定性线性表栈和队列 l#3*（7-2）#步骤步骤 OPTR栈栈 OPND栈栈 输入字符输入字符 主要操作主要操作1#3*(7-2)#PUSH(
7、OPND,3)2#3 *(7-2)#PUSH(OPTR,*)3#*3 (7-2)#PUSH(OPTR,()4#*(3 7-2)#PUSH(OPND,7)5#*(37 -2)#PUSH(OPTR,-)6#*(-37 2)#PUSH(OPND,2)7#*(-372 )#operate(7,-,2)8#*(35 )#POP(OPTR)9#*35#operater(3,*,5)10#15#RETURN 第 3 章 限定性线性表栈和队列 中缀表示法：中缀表示法：3*（7-2）表示法：表示法：372-*思想（后缀）：自左至右扫描，如是操作思想（后缀）：自左至右扫描，如是操作数，则入栈，遇到运算符，则连续两
8、次数，则入栈，遇到运算符，则连续两次出栈，进行相应运算。出栈，进行相应运算。第 3 章 限定性线性表栈和队列 1.递归的概念：递归的概念：一个过程（或子程序，函数）在完成之前又直接或一个过程（或子程序，函数）在完成之前又直接或间接地调用自己，则称之为递归过程（或子程序，间接地调用自己，则称之为递归过程（或子程序，函数）。函数）。若直接调用自己称为直接递归，若通过其它函数并若直接调用自己称为直接递归，若通过其它函数并由后者反过来调用前者，成为间接递归。由后者反过来调用前者，成为间接递归。2.递归不是一种数据结构，而是一种算法设计方法。递归不是一种数据结构，而是一种算法设计方法。3.3 栈与递归的
9、实现栈与递归的实现第 3 章 限定性线性表栈和队列 3.以下三种情况，常用到递归方法以下三种情况，常用到递归方法l 数学函数是递归定义的数学函数是递归定义的时当时当 1,)!1(0,1!nnnnn求阶乘的递归算法求阶乘的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);第 3 章 限定性线性表栈和队列 l求解阶乘求解阶乘 n!的过程的过程第 3 章 限定性线性表栈和队列 l 数据结构是递归的数据结构是递归的例：单链表结构例：单链表结构搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值voi
10、d Find(LNode *L)if(L-next=NULL)cout data next);第 3 章 限定性线性表栈和队列 l 问题的解法是递归的问题的解法是递归的例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题问题第 3 章 限定性线性表栈和队列 解决汉诺塔问题的算法解决汉诺塔问题的算法void Hanoi(int n,char A,char B,char C)if(n=1)cout “Move disk”n“from”A “to”C endl;else Hanoi(n-1,A,C,B);cout “Move disk”n“from”A “to”C endl;Hanoi(n-
11、1,B,A,C);第 3 章 限定性线性表栈和队列 4.递归设计递归设计l 对原问题对原问题f(s)进行分解，给出合理的较小问题进行分解，给出合理的较小问题f(s)；l 假设假设f(s)是可解的，在此基础上确定是可解的，在此基础上确定f(s)的解，给的解，给出出f(s)与与f(s)之间的关系；之间的关系；l 确定一个特定情况的解，由此作为递归出口。确定一个特定情况的解，由此作为递归出口。含一个递归调用的递归过程的一般形式含一个递归调用的递归过程的一般形式 void p(参数参数)if(数据为递归出口数据为递归出口)操作操作;else 操作操作;p(参数参数);操作操作;第 3 章 限定性线性表
12、栈和队列 5.递归调用的内部实现原理递归调用的内部实现原理（1）一般函数调用）一般函数调用运行被调用函数之前运行被调用函数之前l 实在参数，返回地址传给被调用函数保存；实在参数，返回地址传给被调用函数保存；l 为被调用函数的局部变量分配存储区；为被调用函数的局部变量分配存储区；l 将控制转移到被调用函数入口，转被调用函数执行。将控制转移到被调用函数入口，转被调用函数执行。被调用函数返回之前被调用函数返回之前l 保存被调用函数的计算结果；保存被调用函数的计算结果；l 释放被调用函数的数据区；释放被调用函数的数据区；l 按返回地址将控制权转移到调用函数。按返回地址将控制权转移到调用函数。（2）递归
13、调用）递归调用 调用自身代码的复制件调用自身代码的复制件函数之间的信息传递和控制转移通过函数之间的信息传递和控制转移通过“栈栈”来实现。来实现。第 3 章 限定性线性表栈和队列 long Factorial(long n)int temp;if(n=0)return 1;else temp=n*Factorial(n-1);return temp;RetLoc2void main()int n;n=Factorial(4);RetLoc1第 3 章 限定性线性表栈和队列 计算计算Factorial时活动记录的内容时活动记录的内容第 3 章 限定性线性表栈和队列 l递归算法具有两个特性：递归算法
14、具有两个特性：(1)递归算法是一种分而治之、把复杂递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析对求解某些复杂问题，递归算法的分析方法是有效的。方法是有效的。（2）递归算法的时间效率低。递归执递归算法的时间效率低。递归执行时需要系统提供隐式栈实现递归，效行时需要系统提供隐式栈实现递归，效率低且费时。率低且费时。第 3 章 限定性线性表栈和队列 l 练习：递归算法计算练习：递归算法计算K阶斐波那契阶斐波那契(Fibonacci)数列的数列的第第m项值。项值。int Fib(int m,int k)if(k 2|
15、m 0)return-1;if(m k-1)return 0;else if(m=k-1)return 1;else sum=0;for(i=1;i=k;i+)sum+=Fib(m-i,k);return sum;第 3 章 限定性线性表栈和队列 m=4,k=2Fib(4,2)Fib(3,2)Fib(2,2)Fib(1,2)+1Fib(0,2)01+Fib(1,2)21+Fib(2,2)Fib(1,2)1+Fib(1,2)013第 3 章 限定性线性表栈和队列 int Fib(int m,int k)if(k 2|m 0)return-1;if(m k-1)return 0;else if(m=k-1|m=k)return 1;else return 2*Fib(m-1,k)Fib(m-k-1,k);1(1)2mmmkfff 第 3 章 限定性线性表栈和队列 m=4,k=2Fib(4,2)2*Fib(3,2)2*Fib(2,2)10-Fib(0,2)2-Fib(1,2)13第 3 章 限定性线性表栈和队列 l作业：作业：3.7 3.15
