chapt栈和队列栈二.pptx

上传人:知****量 文档编号:17598324 上传时间:2022-05-25 格式:PPTX 页数:20 大小:346.23KB
返回 下载 相关 举报
chapt栈和队列栈二.pptx_第1页
第1页 / 共20页
chapt栈和队列栈二.pptx_第2页
第2页 / 共20页
点击查看更多>>
资源描述

《chapt栈和队列栈二.pptx》由会员分享,可在线阅读,更多相关《chapt栈和队列栈二.pptx(20页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 1.1 1.1 栈的概述栈的概述 1.2 1.2 栈的顺序存储结构及其基本运算实栈的顺序存储结构及其基本运算实现现 1.3 1.3 栈的链式存储结构及其基本运算实现栈的链式存储结构及其基本运算实现 1.4 1.4 栈的应用栈的应用 1 1 栈栈 1.5 1.5 栈与递归的实现栈与递归的实现 堆栈在程序设计语言中的一项重要应用是堆栈在程序设计语言中的一项重要应用是实现递归实现递归。 1.1.1 1.1.1 递归的定义递归的定义 在程序设计语言中,一个函数直接调用自己,或通过一系列在程序设计语言中,一个函数直接调用自己,或通过一系列的调用语句间接地调用自己的过程,称为递归。的调用语句间接地调用自

2、己的过程,称为递归。 若函数调用自身,称之为若函数调用自身,称之为直接递归直接递归。 若过程或函数若过程或函数p调用过程或函数调用过程或函数q,而,而q又调用又调用p,称之为,称之为间接递间接递归归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为语句,则称这种递归调用为尾递归尾递归。1.5 1.5 栈与递归的实现栈与递归的实现 1.1.2 1.1.2 递归的作用递归的作用 递归是程序设计中一个强有力的工具。帮助程序设计者解决递归是程序设计中一个强有力的工具。帮助程序设计者解决复杂的问题,并精简程序结构。它的

3、作用表现在:复杂的问题,并精简程序结构。它的作用表现在: 第一,解决很多的第一,解决很多的数学问题数学问题。很多数学函数是递归定义的,。很多数学函数是递归定义的,比如阶乘、费氏级数、求最大公因子、组合公式等。比如阶乘、费氏级数、求最大公因子、组合公式等。 第二,有的第二,有的数据结构数据结构,如二叉树、广义表等,结构本身就,如二叉树、广义表等,结构本身就具备递归特性,对它们的操作就可以递归地描述。具备递归特性,对它们的操作就可以递归地描述。 第三,还有一类问题,本身并没有明显的递归结构,但使第三,还有一类问题,本身并没有明显的递归结构,但使用递归求解可以用递归求解可以简化算法简化算法。比如著名

4、的汉诺塔问题、八皇后。比如著名的汉诺塔问题、八皇后问题等。问题等。 1.1.3 1.1.3 递归的步骤递归的步骤 求解递归问题的步骤求解递归问题的步骤(1 1)判断题意是否适合用递归来递解;)判断题意是否适合用递归来递解;(2 2)决定递归结束的条件()决定递归结束的条件(Stopping CasesStopping Cases)(3 3)决定递归执行部分()决定递归执行部分(Recursive StapRecursive Stap) 递归模型递归模型递归函数的算法格式递归函数的算法格式 处理递归问题,常采用处理递归问题,常采用ifif语句语句来判断是否符合递归结束条件,来判断是否符合递归结束

5、条件,算法格式如下:算法格式如下: if (if (符合递归结束条件符合递归结束条件) ) 返回答案;返回答案; elseelse 调用递归程序;调用递归程序; / /* *传递参数递减传递参数递减( (增增) ),表示更高一层的递归,表示更高一层的递归* */ / 递归出口递归出口递归体递归体1.1.4 1.1.4 递归的执行过程递归的执行过程函数调用、信息传递函数调用、信息传递 1. 1. 普通函数的调用过程普通函数的调用过程 v在高级语言编制的程序中,调用函数和被调函数之间的链接和信在高级语言编制的程序中,调用函数和被调函数之间的链接和信息交换需要通过息交换需要通过堆栈堆栈来进行。来进行

6、。 系统将整个程序运行所需的数据空间安排在一个堆栈中。系统将整个程序运行所需的数据空间安排在一个堆栈中。v通常,在一个函数的运行期间调用另一个函数时,在运行被调函通常,在一个函数的运行期间调用另一个函数时,在运行被调函数之前,系统先要完成三件事:数之前,系统先要完成三件事:1 1、将所有的实参、返回地址等信、将所有的实参、返回地址等信息传递给被调函数保存;息传递给被调函数保存;2 2、为被调函数的局部变量分配存储区;、为被调函数的局部变量分配存储区;3 3、将控制转移到被调函数的入口。、将控制转移到被调函数的入口。v当执行完被调函数,在返回调用函数之前,系统也先要完成三件当执行完被调函数,在返

7、回调用函数之前,系统也先要完成三件事:事:1 1、保存被调函数的计算结果;、保存被调函数的计算结果;2 2、释放被调函数的数据区;、释放被调函数的数据区;3 3、依照被调函数保存的返回地址将控制转移到调用函数。依照被调函数保存的返回地址将控制转移到调用函数。v当有多个函数构成嵌套调用时,按照当有多个函数构成嵌套调用时,按照“后调用先返回后调用先返回”的原则,函的原则,函数之间的信息传递和控制转移均通过堆栈来实现。数之间的信息传递和控制转移均通过堆栈来实现。v每当调用一个函数时,就在堆栈顶端为它分配一个存储区,保存其每当调用一个函数时,就在堆栈顶端为它分配一个存储区,保存其参数(实参、局部变量)

8、和返回地址等信息;每当从一个函数退出参数(实参、局部变量)和返回地址等信息;每当从一个函数退出时,就释放它的存储区,使得当前正在运行函数的数据区总是在栈时,就释放它的存储区,使得当前正在运行函数的数据区总是在栈顶。顶。v最后被调用的函数,其相关的参数和返回地址等信息作为栈顶元素,最后被调用的函数,其相关的参数和返回地址等信息作为栈顶元素,我们称之为我们称之为栈顶工作记录栈顶工作记录,因为是当前执行函数的工作记录,也称,因为是当前执行函数的工作记录,也称之为之为“活动记录活动记录”。指向活动记录的指针通常也被称为。指向活动记录的指针通常也被称为“环境指环境指针。针。”【例例3.63.6】两个子函

9、数两个子函数first、second的嵌套调用的嵌套调用 int first(int a, int b) int i; second(i); 2: int second(int d); int x,y; v当前运行函数为当前运行函数为secondsecond时,堆栈状态如右上图所示。工作记录的内容:时,堆栈状态如右上图所示。工作记录的内容:返回地返回地址址(被调函数的下一语句,控制转移至调用函数)、(被调函数的下一语句,控制转移至调用函数)、实参实参、局部变量局部变量。v执行完最后调用的函数执行完最后调用的函数secondsecond后,栈顶记录被后,栈顶记录被pop出去,控制转移至返回地址出

10、去,控制转移至返回地址2 2,接着执行,接着执行firstfirst函数的其它语句。函数的其它语句。v执行完执行完firstfirst函数语句,当前栈顶记录(函数语句,当前栈顶记录(firstfirst的记录)又被的记录)又被pop出去,控制转移出去,控制转移至返回主函数地址至返回主函数地址1 1,接着执行主函数中的其它语句。,接着执行主函数中的其它语句。2 i x y 1 m n i m n (second工作记录) (first 的记录 ) 栈顶主函数工作区2. 2. 递归函数的调用过程递归函数的调用过程v一个递归函数的嵌套过程类似于多个函数的嵌套调用。只是调用函一个递归函数的嵌套过程类似

11、于多个函数的嵌套调用。只是调用函数和被调函数均为同一个函数。唯一的不同点是其中的一个数和被调函数均为同一个函数。唯一的不同点是其中的一个传入参传入参数数每次执行函数调用时都每次执行函数调用时都递减(增)递减(增)。 这个传入参数可以表明递归函数运行的这个传入参数可以表明递归函数运行的“层次层次”。v若调用递归函数的主函数为第若调用递归函数的主函数为第0 0层,那么从主函数调用递归函数为进层,那么从主函数调用递归函数为进入第一层。从第入第一层。从第i i 层递归函数调用自身为进入第层递归函数调用自身为进入第i+1i+1层。反之,第层。反之,第i i层函数执行完退回至层函数执行完退回至i-1i-1

12、层。层。v系统也需要设立一个系统也需要设立一个“递归工作栈递归工作栈”作为整个递归函数运行期间使作为整个递归函数运行期间使用的数据区,不需用户自己管理,而用的数据区,不需用户自己管理,而由系统完成管理工作。由系统完成管理工作。 v每一层递归函数所需信息也构成一个每一层递归函数所需信息也构成一个“工作记录工作记录”。最。最“高高”层的层的工作记录就是栈顶的活动记录。指示活动记录的栈顶指针为工作记录就是栈顶的活动记录。指示活动记录的栈顶指针为“当前当前环境指针环境指针”。【例例3.73.7】设计一个乘法器(只能做加法)设计一个乘法器(只能做加法) 分析:A*B=A+(A*(B1)= A+A+(A*

13、(B2)=A+A+A*1 B个A B=1为循环结束的条件(递归结束)v运算规律:运算规律:每次运算时,A所乘的数B依次递减,将所乘的积返回再与A相加。v算法如下页。算法如下页。 主函数定义了一个乘积变量product。实参A、B;形参M、N;局部变量result。result返回运算值给product。 主函数对递归函数的调用:product=multiply(NumA, NumB) 递归体:result = M+ multiply(M, N-1)乘法器算法如下:乘法器算法如下:int Multiply(int M, int N) int Result; if (N=1) Result=M;

14、else Result=M+Multiply( M, N-1);20 return Result;void main( ) int NumA,NumB,Product; printf(“Please enter number A:”); scanf(“%d”,&NumA); printf(“Please enter number B:”); scanf(“%d”,&NumB);38 Product= Multiply(NumA , NumB);39 printf(“%d*%d=%d”, NumA , NumB ,Product); printf(n);v表述乘法器算法的递归工作栈如下:表述乘法

15、器算法的递归工作栈如下: 栈顶记录 M 第4层 20; A ,B ; Result Multiply(13,1) M+M 第3层 20; A, B ; Result Multiply(13,2) M+M+M 第2层 20; A ,B; Result Multiply(13,3) M+M+M+M 第1层 39; A, B; Result Multiply(13,4) 实际上,在调用函数和被调函数之间不一定传递参数的值,也实际上,在调用函数和被调函数之间不一定传递参数的值,也可以传递参数的地址。每种程序设计语言都有它自己约定的传递可以传递参数的地址。每种程序设计语言都有它自己约定的传递方法,包括被

16、调函数的执行结果如何返回到调用函数等等。方法,包括被调函数的执行结果如何返回到调用函数等等。 1.1.5 1.1.5 递归算法的设计递归算法的设计 递归求解过程的特征递归求解过程的特征 递归过程先将整个问题划分为若干个子问题,而这些子问题具递归过程先将整个问题划分为若干个子问题,而这些子问题具有与原问题有与原问题相同相同的求解方法。于是可以再将它们划分成若干个子问的求解方法。于是可以再将它们划分成若干个子问题,如此反复进行,直到不能再划分成子问题,已经可以求解为止题,如此反复进行,直到不能再划分成子问题,已经可以求解为止(此时分解到递归出口此时分解到递归出口)。)。 递归分解不是随意的分解,要

17、保证递归分解不是随意的分解,要保证“大问题大问题”与与“小问题小问题”相相似,即似,即求解过程与环境都相似求解过程与环境都相似。 递归算法设计先要给出递归模型,再转换成对应的递归算法设计先要给出递归模型,再转换成对应的C/C+C/C+语言语言函数。函数。 递归设计的步骤递归设计的步骤 (1)(1)对原问题对原问题f(s)f(s)进行分析进行分析, ,假设出合理的假设出合理的“较小问题较小问题”f(s) f(s) ( (与与数学归纳法中假设数学归纳法中假设n=k-1n=k-1时等式成立相似时等式成立相似) ); (2)(2)假设假设f(s)f(s)是可解的是可解的, ,在此基础上确定在此基础上确

18、定f(s)f(s)的解。即的解。即给出给出f(s)f(s)与与f(s)f(s)之间的关系之间的关系( (与数学归纳法中求证与数学归纳法中求证n=kn=k时等式成立的过程相似时等式成立的过程相似) ); (3)(3)确定确定一个特定情况一个特定情况( (如如f(1)f(1)或或f(0)f(0)的解的解, ,由此作为由此作为递归出口递归出口( (与与数学归纳法中求证数学归纳法中求证n=1n=1时等式成立相似时等式成立相似) )。【例例3.83.8】采用递归算法求实数数组采用递归算法求实数数组A0.n-1A0.n-1中的最小中的最小值。值。 解:设解:设f(A,i)f(A,i)函数,求数组元素函数,

19、求数组元素A0A0AiAi中的最小值。中的最小值。 当当i=0i=0时时, ,有有f(A,i)=A0f(A,i)=A0; 假设假设f(A,i-1)f(A,i-1)已求出已求出, ,则则f(A,i)=MIN(f(A,i-1),Ai),f(A,i)=MIN(f(A,i-1),Ai),其中其中MIN()MIN()为求两个值较小值函数。因此得到如下递归模型:为求两个值较小值函数。因此得到如下递归模型: A0 A0 当当i=0i=0时时 f(A,i)=f(A,i)= MIN(f(A,i-1),Ai) MIN(f(A,i-1),Ai) 其他情况其他情况递归求解算法如下:递归求解算法如下: float f(

20、float A,int i) float m; if (i=0) return A0; else m=f(A,i-1); if (mAi) return Ai; else return m; 【例例3.93.9】求求1 1,2 2,n n的全排列。的全排列。 解:解:设设a是含是含n个不同字符的字符串,个不同字符的字符串,f(a,k-1,n) 为为 a0.k-1的的所有字符的全排序,所有字符的全排序,f(a,k,n) 为为 a0.k的所有字符的全排序。的所有字符的全排序。 假设假设f(a,k-1,n)可求,对于可求,对于ak位置,可以取位置,可以取a0.k任何之值,任何之值,再组合再组合f(a

21、,k-1,n),则得到,则得到f(a,k,n)递归模型为:递归模型为: f(a,k,n):输出输出a 当当k=0时时 f(a,k,n):ak位置取位置取a0.k任何之值任何之值, 并组合并组合f(a,k-1,n)的结果的结果; 其他情况其他情况 a0 a1 ak-1 ak an-1 f(a,k-1,n) f(a,k,n) 递归求解算法如下:递归求解算法如下: void f(char a,int k,int n) int i,j;char tmp;if (k=0) for (j=0;jn;j+) printf(%c,aj); printf(n);else for (i=0;i=k;i+) aka

22、i; f(a,k-1,n); akai 【例例3.103.10】采用递归算法求解采用递归算法求解皇后问题皇后问题:在:在n nn n的方格的方格棋盘上,放置棋盘上,放置n n个皇后,要求每个皇后不同行、不同列、个皇后,要求每个皇后不同行、不同列、不同左右对角线。不同左右对角线。 解:设解:设place(k,n)表示前面已将表示前面已将1,k-1个皇后放置好,用个皇后放置好,用于放置于放置k,n的皇后。的皇后。 求解皇后问题的递归模型如下:求解皇后问题的递归模型如下: place(i,n):n个皇后放置完毕,输出解个皇后放置完毕,输出解 若若i=n place(k,n):对于第对于第k列的每个合

23、适的位置列的每个合适的位置i, 在其上放置一个皇后在其上放置一个皇后; place(k+1,n); 其他情况其他情况递归过程与算法教材递归过程与算法教材p144【例例3.113.11】求解求解汉诺塔问题汉诺塔问题。源塔。源塔X X;辅助塔;辅助塔Y Y;目标塔;目标塔Z Z。设圆盘从小到大的顺序编号为设圆盘从小到大的顺序编号为1 1,2 2,n n。实现全部圆。实现全部圆盘从盘从X X移动至移动至Z Z。要求移动过程中不破坏圆盘原来的次序。要求移动过程中不破坏圆盘原来的次序。 分析:当分析:当n=1n=1时,问题最为简单,只需将编号为时,问题最为简单,只需将编号为1 1的圆盘直接从的圆盘直接从

24、X X 移动到移动到Z Z。 if(n=1) move (X ,1, Z ); 当当n1n1时,需要利用时,需要利用Y Y作为辅助塔,先将第作为辅助塔,先将第1 1n-1n-1号盘先移号盘先移动至动至Y Y;再将第;再将第n n号盘移至号盘移至Z Z;最后将;最后将Y Y塔的第塔的第1 1n-1n-1号盘移动至目标号盘移动至目标塔塔Z Z。 那么,实现那么,实现n-1n-1个圆盘从一个塔移至另一个塔的问题,是和原个圆盘从一个塔移至另一个塔的问题,是和原问题具有相同特性的问题,只是问题的规模小了问题具有相同特性的问题,只是问题的规模小了1 1,因此可以用同,因此可以用同样的方法来求解。样的方法来求解。 递归工作栈的工作记录含递归工作栈的工作记录含5 5个数据项:返回地址、个数据项:返回地址、4 4个实参。个实参。 递归求解算法如下:递归求解算法如下:/ /* *主函数主函数* */ /*搬移函数搬移函数*/

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > 工作计划

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁