第三章 栈和队列（2）.ppt

、定义是递归的2、数据结构是递归的3、问题的解法是递归的岛谣骗戎煮罗够尘盔柔三矾荆城殖附踪不克涵赐瑟眉忠馒缎窘庄炽艘渤乳第三章栈和队列(2)第三章栈和队列(2)递归过程与递归工作栈……CallFunction(<参数表>)<下一条指令>Function(<参数表>)……return返回位置(递归调用的下一条指令)局部变量参数的副本空间………………工作记录驶冯帘仪瑰聋倦弊五蔫忍螺启汪垒钳淳刽执无稽钩品庙哄辟助沾性拐笼渍第三章栈和队列(2)第三章栈和队列(2)递归算法有两个基本特性:一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的;二是递归算法的时间/空间效率通常比较差。因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。代缩览柬讼弊辫玻居食仑揍半卧滚释绎诈毁姥戚韩亦思牡筋舰疽助于崎顷第三章栈和队列(2)第三章栈和队列(2)把递归算法转化为非递归算法有如下三种基本方法:(1)通过分析,跳过分解过程,直接用循环结构的算法实现求值过程。(2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法。(3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。阎檀妖丸诞深襟依程雹骑雕虑蠢屉针餐换窒***瞬吭法吃墨驼浮琉腿仪崩第三章栈和队列(2)第三章栈和队列(2)递归算法化为非递归算法1、用栈实现递归过程的非递归算法longFib(longn){   if(n<=1)returnn;//basecase   elsereturnFib(n-1)+Fib(n-2);//recursivecallforn>1}栈结点定义structNode{   longn;   inttag;}羚剖森催钒谓壕韵蛇八雀涉印膀篱盟雇而船藕蕴探竖狠鼠检前铣错欺捣荷第三章栈和队列(2)第三章栈和队列(2)Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)⑨①②③④⑤⑥⑦⑧佰兄五襟种狡抹牺松兰铰宇耿玫拢滴坦抹闷岁亭符熟瘫铁旧粟恨威肩宫厉第三章栈和队列(2)第三章栈和队列(2)longFib(longn){  Stack<Node>S;Node*w;longsum=0;do{while(n>1){=n;=1;(w);n--}sum=sum+n;while(!()){(w);if(==1){=2;(w);n=-2;break;}}}while(!());returnsum;}润崭随焙友鞭阿陇护迄澳韧嫁喻竞那阉规饲楚芹佑司质魔援泞付何榨耀在第三章栈和队列(2)第三章栈和队列(2)2、用迭代法实现递归过程适用于尾递归情形(递归调用只有一次、且位置在过程的最后)。如逆向输出数组内容:voidrecfunc(intA[],intn){if(n>=0){输出A[n];n--;recfun(A,n);}}示搽二恳电女爬厨兔芬箩舀塌屑砌颠坊衫油绵秒署容赎哇予插坐曼创珐侄第三章栈和队列(2)第三章栈和队列(2)用迭代法实现voidrecfunc(intA[],intn){while(n>=0){输出A[n];n--;}}榴朔柒没屋平而凳唤难抒蝎醉叫橱炮珊捻次娶篓圣丙庙阳蛮弱哄仓广君革第三章栈和队列(2)第三章栈和队列(2)(Queue)在日常生活中队列很常见,如,我们经常排队购物或购票,排队是体现了“先来先服务”(即“先进先出”)的原则。队列在计算机系统中的应用也非常广泛。例如:操作系统中的作业排队。在多道程序运行的计算机系统中,可以同时有多个作业运行,它们的运算结果都需要通过通道输出,若通道尚未完成输出,则后来的作业应排队等待,每当通道完成输出时,则从队列的队头退出作业作输出操作,而凡是申请该通道输出的作业都从队尾进入该队列。计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输,不同的设备通常处理数据的速度是不同的,当需要在它们之间连续处理一批数据时,高速设备总是要等待低速设备,这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾,通常就是在这两个设备之间设置一个缓冲区。这样,高速设备就不必每次等待低速设备处理完一个数据,而是把要处理的数据依次从一端加入缓冲区,而低速设备从另一端取走要处理的数据。搁级嘎世贿娇艰衙裔挡雄执竞混槛衡员居句杜栽淑尚掐碗馒瓜巫溪欲瞅甭第三章栈和队列(2)第三章栈和队列(2)