【数据结构课件】栈与队列

《【数据结构课件】栈与队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈与队列3.1栈栈的定义及操作特性堆栈是一个线性表，其插入（也称为添加）和删除操作都在表的同一端进行。其中一端被称为栈顶（top），另一端被称为栈底（bottem）栈的存储结构顺序栈、链栈栈的应用迷宫求解、汉诺塔、数制转换等计算机科学系李长志栈的定义与操作特性栈是限定仅在表尾进行插入或删除操作的线性表。表尾端被称为栈顶，表顶端被称为栈底。计算机科学系李长志抽象数据类型（ADT）定义Stack{实例：线性表，栈底，栈顶操作：Init():IsEmpty():IsFull():GeTop():Push():Pop():计算机科学系李长志FAQ:设将整数1,2,3,

2、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。计算机科学系李长志栈的存储结构——顺序栈计算机科学系李长志栈的存储结构——链栈计算机科学系李长志链栈存储结构描述计算机科学系李长志3.2分治

3、与递归将要求解的较大规模的问题分割成k个更小规模的子问题对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。算法总体思想计算机科学系李长志nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)计算机科学系李长志将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2n/

4、2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)计算机科学系李长志分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。----孙子兵法计算机科学系李长志递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治

5、手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。计算机科学系李长志例1阶乘函数阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。递归举例计算机科学系李长志无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：边界条件递归方程例2Fibonacci数列计算机科学系李长志对函数f(n

6、)的递归定义应满足的条件定义中必须包含一个基本部分，其中对于n的一个或多个值，f(n)必须是直接定义的。在递归部分，右侧出现的所有f的参数都必须有一个比n小，以便重复运用递归部分来改变右侧出现的f，直至出现f的基本部分计算机科学系李长志对函数f(n)的递归定义应满足的条件nf(n-1)f(n)=1基本部分：当n<=1时f(n)=1；递归部分：f(n)=nf(n-1)，其中右侧参数为n-1，比n小。计算机科学系李长志计算Fibomacci数列第n个Fibonacci数可递归地计算如下：intFibonacci(intn){if(n<=1)return1;returnF

7、ibonacci(n-1)+Fibonacci(n-2);}计算机科学系李长志计算n!的时间复杂度n!可递归地计算如下：intFactorial(intn){if(n<=1)return1;returnn*Factorial(n-1);}设fact的运行时间函数为T（n），则有计算机科学系李长志问题：求解递归方程：T(n+1)=f(n,T(n))递归方程的求解递归方程的形式多种多样，求解方法也多种多样代入法:先推测，后用数学归纳法证明迭代法：反复迭代，变换成级数，然后求和套用公式法：T(n)=aT(n/b)+f(n),三种情况下方程的解差分方程法：解差分方程(初