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

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

2、 ):,计算机科学系李长志,FAQ:,设将整数1,2,3,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、算机科学系李长志,链栈存储结构描述,3.2 分治与递归,计算机科学系李长志,将要求解的较大规模的问题分割成k个更小规模的子问题 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,算法总体思想,计算机科学系李长志,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),计算机科学系李长志,将求出的

4、小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,n/2,n/2,n/2,n/2,计算机科学系李长志,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 凡治众如治寡，分数是也。 -孙子兵法,计算机科学系李长志,递归的概念,直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然

5、导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,计算机科学系李长志,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,递归举例,计算机科学系李长志,无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,例2 Fibonacci数列,计算机科学系李长志,对函数f (n)的递归定义应满足的条件,定义中必须包含一个基本部分，其中对于n的一个或多个值，f (n)必须是直接定义的。 在递

6、归部分，右侧出现的所有f的参数都必须有一个比n小，以便重复运用递归部分来改变右侧出现的f，直至出现f的基本部分,计算机科学系李长志,对函数f (n)的递归定义应满足的条件,nf (n-1),基本部分：当n=1时 f (n) =1； 递归部分：f (n)=n f( n-1) ，其中右侧参数为n-1，比n小。,计算机科学系李长志,计算Fibomacci数列,第n个Fibonacci数可递归地计算如下： int Fibonacci(int n) if (n = 1) return 1; return Fibonacci(n-1)+Fibonacci(n-2); ,计算机科学系李长志,计算n!的时间复

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

8、系李长志,1代入法,推测：T(n)=O(nlogn) T(n)Cnlog n (C=2),后用数学归纳法证明:,计算机科学系李长志,换元：m=logn / n=2m T(2m)=2T(2m/2)+m S(m)=T(2m) S(m)=2S(m/2)+m OK,计算机科学系李长志,2 迭代法,T(n)=O(n),T(n)=T(n-1)+n,T(n)=n2,计算机科学系李长志,T(n)=2T(n/2)+n2,计算机科学系李长志,T(n)= T(n/3)+ T(2n/3)+n,计算机科学系李长志,3 套用公式法,T(n)=aT(n/b)+f(n),af(n/b)cf(n)，则T(n)=(f(n),计算

9、机科学系李长志,几个例子：,T(n)=9T(n/3)+nT(n)=aT(n/b)+f(n) 一 T(n)=(n2),T(n)=T(2n/3)+1二 T(n)=(logn),T(n)=3T(n/4)+nlogn三 T(n)=(f(n)=(nlogn),T(n)=2T(n/2)+nlogn 二三之间：失败！,计算机科学系李长志,4 差分方程法,常微分方程的结构十分相似： 特征方程 基本解系 通解 + 一个特解,举例：,F(n)=3f(n-1)+4f(n-2), n2, f(1)=1, f(2)=4,计算机科学系李长志,T(n)=4T(n-1)-4T(n-2)+2nn 和初始条件T(0)=0，T(1

10、)=4/3,T(n)=n2(1/2+n/6)2nT(n)=(n32n),计算机科学系李长志,5 母函数法,建立A(x)的一个定解方程并将其解出，那么， 把A(x)展开成幂级数,(n-1)T(n)=(n-2)T(n-1)+2T(n-2) ，n2 初始条件T(0)=0，T(1)=1,B(x)= A (x)/x,计算机科学系李长志,D(n)=nD(n-1)+(-1)n n1 初始条件D (0)= 1,A(x)=e-x/(1-x),计算机科学系李长志,例3 排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 集合X中元素的全

11、排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由 (r1)perm(R1)， (r2)perm(R2)， ， (rn)perm(Rn) 构成。,计算机科学系李长志,例4. 汉诺(Hanoi)塔问题,1. 每次只能移动一个盘子; 2. 盘子只能在柱子上来回移动; 3. 柱子上的盘子必须始终保持大盘在下,小盘在上.,计算机科学系李长志,规则1:每次只能移动1个圆盘； 规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上

12、 规则3:在满足移动规则1和2的前提下，可将圆盘移至A,B,C中任一塔座上。,例4. 汉诺(Hanoi)塔问题,计算机科学系李长志,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,计算机科学系李长志,3.3 队列,队列的定义及操作特性 队列是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾（rear），删除元素的一端被称为队头（front）。 队列的存储结构 链队列、循环队列、顺序队列 队列的应用 电路布线

13、、工厂仿真、图元识别等。,计算机科学系李长志,队列的定义及操作特性,计算机科学系李长志,队列的ADT描述,ADT queue 实例： 线性表，队头、队尾。 基本操作： Creat ( )创建一个空的队列； IsEmpty ( )判断队列是否为空； IsFull ( )判断队列是否为满； First（）返回队列中的第一个元素； Last ( )返回队列中的最后一个元素； Add ( )向队列中添加元素； Delete ( )删除队列首元素；,计算机科学系李长志,队列的逻辑结构,FAQ: 如何定义队头指针和队尾指针？ 如何利用已定义的队头和队尾指针表述队列为空或队列为满的条件？,计算机科学系李长志,队列的存储结构链队列,计算机科学系李长志,队列的存储结构顺序队列,计算机科学系李长志,循环队列,计算机科学系李长志,循环队列,计算机科学系李长志,应用：电路布线问题,问题（电路布线问题）： 输入：nm方格，电路布线于此，不能够交叉 输出：格点a,b 间的最短布线