数据结构 课件 栈

《数据结构 课件 栈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈的定义栈与递归栈的实现栈的应用StackOfCupsAddacuptothestack.bottomtopCABDEFRemoveacupfromnewstack.AstackisaLIFOlist.bottomtopCABDE只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)定义退栈进栈a0an-1an-2topbottomtop空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出

2、abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop栈与递归系统堆栈当一个函数被呼叫时，程序会建立一个称为活动记录(activationrecord)或是堆栈框(stackframe)的结构,并且把它放在系统堆栈最上端.returnaddresspreviousframepointerfpmainreturnaddresspreviousframepointerfpmainreturnaddresspreviousframepointera1localvariables

3、多个函数嵌套调用的规则是:此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………a();b();c();……}//main}//a}//bmain的数据区函数a的数据区函数b的数据区函数c的数据区栈的应用：递归递归的定义若一个对象部分地包含它自己，或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。递归的例子求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;e

4、lsereturnn*Factorial(n-1);}例如，阶乘函数求解阶乘n!的过程主程序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参数传递结果返回递归调用回归求值自顶向下、逐步分解的策略子问题应与原问题做同样的事情，且更为简单；解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解

5、。—分而治之策略（分治法）这些比较小的问题的求解方法与原来问题的求解方法一样。构成递归的条件不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。Procedure(){if()//递归结束条件return(initialvalue);else//递归return((parameterexchange));}递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用n!(n-1)!(n-2)

6、!1!0!=1返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。递归过程与递归工作栈longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);returntemp;}voidmain(){intn;n=Factorial(4);}RetLoc1RetLoc2递归工作栈每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归

7、工作记录，按后进先出的栈组织。局部变量返回地址指向下一栈框指针活动记录框架递归工作记录函数递归时的活动记录……………….<下一条指令>Function(<参数表>)……………….调用块函数块返回地址(下一条指令)局部变量指针计算Fact时活动记录的内容递归调用序列01RetLoc211RetLoc222RetLoc236RetLoc2424RetLoc1变量返回值返回地址返回时的指令return4*6//返回24return3*2//返回6return1//返回1return1*1//返回1re

8、turn2*1//返回2bottomtop递归过程改为非递归过程递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+