计算机科学第5章-数据结构与算法

1、计算机学科导论,第5章 数据结构与算法,本 章 教 学 目 的,理解数据结构的概念，理解数据结构的逻辑和存储结构 理解算法的概念和算法的基本特性，了解算法复杂度的度量方法 理解线性数据结构，掌握栈和队列、串和数组等典型线性数据结构 了解非线性的数据结构，了解树、二叉树和图等典型非线性数据结构 理解排序、查找的概念，了解排序、查找的典型算法及其比较分析方法 理解递归的概念，了解递归的实际应用,本 章 教 学 内 容,数据结构概述 线性结构 非线性结构 基本算法 递归,本 章 学 习 重 点,数据结构的基本概念 算法的描述、流程图的使用以及算法的复杂度的衡量 顺序存储和链式存储的方法 栈、队列、串

2、和数组的概念和用法 二叉树数据结构 查询、排序和递归算法,第一节 数据结构概述,5.1 数据结构概述,5.1.1 数据结构 数据是对客观事物的符号表示，是信息的载体，它能够被计算机识别、存储和加工处理，是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。 数据元素是构成数据的基本单位。对于复杂事务的数学描述往往需要多个组成成分，每个基本的成分称为一个数据元素。有时，一个数据元素可以细分为一组数据项，数据项是数据中不可再分割的最小单位。研究具体问题时可以根据实际需要，确

3、定数据的组成，即需要有多少数据元素，具体的数据元素是否再细分为数据项。,4.1 数据结构概述,4.1.1 数据结构 数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，它们之间总是存在着这样或那样的关系，这种数据元素之间的关系称为结构。 根据数据元素间关系的不同特性，通常有下列四类基本的结构： 集合结构。在集合中，各数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构，各元素间没有直接的关联。 线性结构。该结构的数据元素之间存在着一对一的关系。 树型结构。该结构的数据元素之间存在着一对多的关系。 图形结构。该结构的数据元素之间

4、存在着多对多的关系，图形结构也称作网状结构。,5.1 数据结构概述,5.1.1 数据结构,图 51 四类基本结构的示意图,5.1 数据结构概述,4=5.1.1 数据结构,逻辑结构数据元素之间的逻辑关系（设计算法数学模型） 物理结构数据结构在计算机中的映像（存储结构算法的实现） 顺序存储结构借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。 链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系。,5.1 数据结构概述,5.1.1 数据结构,数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的

5、操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。,5.1 数据结构概述,5.1.2 算法,用计算机解决一个复杂的实际问题，大体需要如下的步骤。 （1）将实际问题数学化，即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。 （2）对于确定的数学问题，设计其求解的方法，即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成

6、算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。 （3）用计算机上的一种程序设计语言来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计或程序编制。 （4）在计算机上编辑、调试和测试编制好的程序，直到输出所要求的结果。,5.1 数据结构概述,5.1.2 算法,1. 算法的概念 算法: 对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。 算法具有以下五个重要的特征： 1）有穷性：一个算法必须保证执行有限步之后结束。 2）确切性：算法的每一步骤必须有确切的定义。 3）输入：一个算法有0个或多个输入，以刻画

7、运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。 4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。 5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。,5.1 数据结构概述,5.1.2 算法,1. 算法的概念 算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。数据结构的优劣由算法的执行来体现。要设计一个好的算法通常要考虑以下几个因素。 正

8、确性：算法的执行结果应当满足预先规定的功能和性能要求。 可读性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。 稳健性：当输入不合法数据时，应能作适当处理，不至引起严重后果。 高效性：有效使用存储空间和有较高的时间效率。,5.1 数据结构概述,5.1.2 算法,2. 算法的描述 算法可以使用各种不同的方法来描述。最直接的方法是使用自然语言。用自然语言来描述算法的优点是直接，便于人们对算法的阅读，其缺点是不够严谨，对于有些问题的描述不够简洁，表面上容易理解，但对于人们掌握算法的实质和整体结构并不直观。算法设计的最直接目的是指导程序设计，算法也可以使用程序设计语言描述，程序设计语言接近于数学

9、语言，十分严谨，但是需要进行专业化训练，不便于人们阅读理解。因此算法的描述通常使用流程图或伪代码。,5.1 数据结构概述,5.1.2 算法,2. 算法的描述,图 52 流程图基本图元,5.1 数据结构概述,5.1.2 算法,3. 算法的基本结构,图 53 算法基本结构示意图,通过基本结构的有机组合，可以描述各种算法。 顺序结构的所有步骤使用率为1；分支结构有些分支不会被执行，使用率小于1；循环结构通常会多次执行，使用率大于1。 从复杂程度上看，循环结构最复杂，顺序结构最简单。,5.1 数据结构概述,5.1.2 算法,4. 算法的度量,（1）时间复杂度 指算法从开始执行到处理结束所需要的总时间。

10、通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的基本操作，以该基本操作重复执行的次数作为算法的时间度量。 （2）空间复杂度 指算法从开始执行到处理结束所需的存储量空间的总和。程序运行所需的存储空间包括固定部分：这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关；可变部分：这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。,5.1 数据结构概述,5.1.2 算法,4. 算法的度量,研究发现，时间和空间通常可以转换。在存储空间有限时，可以选择空间复杂度较低的算法，在减少对空间使用量的同时，时间复杂度通常会增加；如果需要能够较快地求出结果，则需要更大的存

11、储空间支持。在大多数情况下，时间和空间因素可以进行相应转换，具体选择时可根据实际需要和成本因素确定选择什么策略。 另外，需要提醒一点，不是时间复杂度高，算法的数学复杂程序就高。使用更高级的数学方法，能够以更少的时间和空间代价获取处理结果。这时，用于算法执行的时间虽然少了，但是用于算法设计的时间会大大增加。如果设计出的程序有足够多的使用率，代价总体上是值得的。,5.1 数据结构概述,5.1.2 算法,5. 子算法,为了简化算法设计，提高空间利用率，提出了子算法和算法调用的概念。所谓子算法，与算法类似，其功能和结构相对简单。设计子算法的目的是为了简化整个算法的设计，对于算法来说，需要用到子算法提供

12、的功能时，通过算法调用来使用子算法提供的功能，即算法调用就是在算法中引用子算法，这样子算法所表示的整个处理过程在算法中就可以用一条调用语句来表示，使得整个算法的结构更为清晰，并且提高了空间得用率。子算法的调用需要专门处理，调用子算法在会多一些时间开销。子算法的方式适用于同一功能多次使用的情况。 子算法在具体实现时，可以使用子程序、过程、函数、方法、模块等形式进行实现，具体实现方式与使用的程序设计语言、程序设计方法有关。,第二节 线性结构,5.2 线性结构,5.2.1 线性表和串 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系。线性结构的特点是逻辑结构简单，易于进行查找、插入

13、和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。 1.线性表 (1)定义 线性表是n(n=0)个数据元素的有限序列，表中各个元素具有相同的属性，表中相邻元素间存在“序偶”关系。 记做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序,5.2 线性结构,5.2.1 线性表和串 1.线性表 (2)顺序存储 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

14、内存中的地址空间是线性的，用物理上的相邻实现数据元素之间的逻辑相邻关系既简单又自然。 (3)链式存储,顺序存储方法简单，容易实现，但做插入删除操作时，需移动的元素较多，因此效率低。链表的特点恰好与顺序表相反。,5.2 线性结构,5.2.1 线性表和串 2. 串 串（即字符串）是一种特殊的线性表，它的数据元素是一个字符，字符串是计算机最常处理的非数值对象。串还具有自身的特性，常常把一个串作为一个整体来处理，因此，在这里我们把串作为独立结构的概念加以研究，介绍串的概念及基本运算。 串是由零个或多个任意字符组成的字符序列。一般记作： S =”s1 s2 sn” 其中S是串名；（注：双引号为定界符，双

15、引号内的字符序列为串值，引号本身不属于串的内容。）si(1=i=n)为串的元素，可是任意一字符，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为。,5.2 线性结构,5.2.1 线性表和串 2. 串 子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 子串的位置：子串的第一个字符在主串中的序号称为子串的位置。求子串的位置就是串的基本运算之一。子串的定位操作通常称做串的模式匹配(其中子串称为模式)。 串相等：两个串的长度相等且对应字符都相等称两个串是相等的。比较两个串是否相等也是串的运算。它是模

16、式匹配的特例。 串的基本操作还有求串长度和串的连接操作。求串长度运算返回串中包含的字符的个数。联接操作是将两个串合并成一个长度更长的串，将原来一个串的头接在另一个尾部，联接后生成的新串长度是原来两个串长度之和。,5.2 线性结构,5.2.2 栈和队列 1. 栈 栈（Stack）是限制在表的一端进行插入和删除的线性表。允许操作的一端为栈顶，固定的一端为栈底。当表中没有元素时称为空栈。栈又称为后进先出表（LIFO，Last In First Out）。 栈的运算包括入栈、出栈和空。如果栈满进行入栈，则产生溢出，称为上溢出。对空栈进行出栈操作，也产生溢出，称为下溢出。为防止发生溢出，需要判空操作。,

17、5.2 线性结构,5.2.2 栈和队列 2. 队列 队列（Queue）是插入在表一端进行，而删除在表的另一端进行的数据结构，是“先进先出” （First In First Out，简称FIFO）的数据结构，允许插入的一端叫队尾，允许删除的一端叫队头。 队列的基本运算包括入队、出队和空等。新加入队列的元素成为队尾。与栈操作类似，入队操作、出队操作也能产生溢出，也需要判空。,5.2 线性结构,5.2.3 数组 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。数组可以看作线性表的推广。数组元素本身可以是属于同一数据类型的某种结构。在数组中通常做下面两种操作： 取值操作

18、：给定一组下标，读其对应的数据元素。 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 数组的存储和处理有两种方式：沿着列的方向，一列完成再进行下一列，称为列序为主或列序优先；沿着行的方向，一行完毕再进行下一行，则称为行序为主或行序优先。,第三节 非线性结构,5.3 非线性结构,所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。 5.3.1 树 树用来描述层次结构，是典型的一对多或多对一的关系。一个节点有两个或多个下级节点，比如社会关系和

19、组织结构，通常一个上级单位有若干个下属部门，一个部门可能有多位员工等。,5.3.1 树,1. 树的定义 树是n(n=0)个数据元素（节点）的有限集合，若为空集，则为空树。否则： （1）有一个特殊的数据元素称为树的根节点，根节点没有前驱节点。 （2）若n1，除根节点之外的其余数据元素被分成m（m0）个互不相交的集合T1，T2，Tm，其每一个集合Ti（1im）本身又是一棵树。树T1，T2，Tm称为这个根节点的子树。 可以看出，在树的定义中用了递归概念，即用树来定义树。树结构的算法与后面将介绍的二叉树结构的算法相类似，都使用了递归方法。,5.3.1 树,1. 树的定义,树具有下面两个特点： (1)

20、树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。 (2) 树中所有节点可以有零个或多个后继节点。,5.3.1 树,1. 树的定义,树中节点拥有的子树的个数称为节点的度。树的度是树内节点度的最大值，即树中下级节点最多的节点的下级节点个数。 节点的层次是指从根开始经过的节点数量，根的层次为1。树中节点的最大层次称为树的深度或高度。 所经过的节点序列称为路径，如果设各边有权，则路径中各边权值的和称为路径长度。 树内度为0的节点称为叶节点，或者称为终端节点；度不为0的节点称为分支节点，或者称为非终端节点。一棵树的节点除叶节点外，其余的都是分支节点。树中一个节点的子树的根节点称为这个

21、节点的孩子，这个节点称为它孩子节点的双亲，具有同一个双亲的孩子节点互称为兄弟，双亲节点的上级节点称为祖先，子节点的下级称为子孙。多棵不相交的树构成的集合称为森林，树中节点的子树就是森林。,5.3.1 树,2. 二叉树,二叉树（Binary Tree）是每个节点最多有两个子树的有序树；这两个子树是分别被称为左子树和右子树的二叉树。二叉树可以为空二叉树，此时树中没有节点。 二叉树是度为2的有序树，是树的一个特例，具有树的全部特性且便于学习和理解。计算机使用二进制，二叉树具有特殊意义。,图 510 二叉树的五种基本形态,5.3.1 树,2. 二叉树,满二叉树：二叉树的所有分支节点都有左子树和右子树，

22、并且所有叶子节点都在同一层上。,图 511 满二叉树和非满二叉树示意图,5.3.1 树,2. 二叉树,完全二叉树：一棵二叉树，其节点编号与同深度的满二叉树中的节点位置相同。 完全二叉树的特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。,图 512 完全二叉树和非完全二叉树示意图,5.3.1 树,3. 树的运算,树的运算主要是插入节点、删除节点和遍历等几种。插入节点、删除节点运算改变树的结构，但要求在改变结构的同时，保持树的特性不变，对于二叉树，插入和删除操作后的树仍然是一棵二叉树。树的操作比较复杂，在专业书

23、籍中有介绍，感兴趣的同学可以参考有关资料学习。,5.3.2 图,1. 定义,图也称做网，是一种比树形结构更复杂的非线性结构。图中任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。图结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。,图由一组节点（称之为顶点）和一组顶点间的连线（称之为边或弧）构成的一种抽象数据类型。树是层次结构的，其节点只能有一个双亲，而图中的节点可以有一个或多个双亲。若图中的边有方向，则称为有向图，若图中的边无方向，则称为无向图。,5.3.2 图,1. 定义,图是由非空的顶点集合和一个描述顶点之间关

24、系边（或者弧）的集合组成，其形式化定义为： G（V，E） Vvi| vi数据元素 E( vi,vj)| vi, vj V P(vi, vj) 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。图 413所示为无向图G1，图414所示为有向图G2。,图 513 无向图G1,图 514 有向图G2,5.3.2 图,2. 图的运算,添加顶点将一个新顶点插入到图中 添加边连接一个顶点和一个目标顶点 删除顶点从一个图里移除一个顶点，同时删除连接顶点的边。 删除边从一个图里移除某条边。 查找顶点通

25、过遍历图来查找特定的顶点。 图的遍历指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。 说明：图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上。,第四节 基本算法,5.4 基本算法,5.4.1 排序 排序：将任意排列的数据集合，根据一定的规则，重新排列成有序的序列。 关键字(key):在排序处理时用于比较的值称为关键字，它可能是数据本身，也可以是数据的某个数据项。 排序算法的稳定性: 如果在对象序列中有两个对象ri和rj，它们的关键字 ki = kj，且在排序之前，对象ri排在rj前面。如果在排序之后，对象ri仍在对象rj的前面，则称这个排序方法是稳定的，否

26、则称这个排序方法是不稳定的。 在排序中需要进行两种基本操作：（1）比较关键字的大小；（2）改变某个记录的位置，即改变该序列的排列方式。,5.4.1 排序,1. 插入排序 插入排序是一类排序方法，其中最简单的是直接插入排序，其基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 直接插入排序时：将排序列表分为已排序的和未排序的两部分。每次扫描时从未排序子列表中取出一个记录，转换到已排序的子列表中与其记录逐个比较并插入到合适的位置。含有n个元素列表至少需要n-1次扫描。 直接插入排序结构简单，容易实现。在空间来看，它需要一个记录的辅助空间用作比较；从时间来看，排序的

27、基本操作为比较两个记录的关键字和移动记录。当待排序记录的数量很小时，这是一种很好的排序方法，但随着记录数n的增大，其效率显然不佳。,5.4.1 排序,1. 插入排序,图 515 插入排序算法,5.4.1 排序,2. 选择排序 选择排序的基本思想是：每一趟在未排序记录选取关键字最小的记录作为有序序列中的某个记录，根据排序的目标是升序还是降序分别将选出的记录加入到有序序列的最前面或最后面。选择排序作为一类排序方法也有多种具体算法，其中最简单的是简单选择排序。 一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1in）个记录交换。对n个记录进行

28、简单选择排序的算法为：从1到n-1，进行n-1趟选择操作。与直接插入排序相比，选择排序由于是有选择地选取记录，在插入有序序列时，需要进行的记录移动操作较少，但其总的时间复杂度也是O(n2)。,5.4.1 排序,3. 气泡排序 气泡排序在有些资料上称做“起泡”或“冒泡”排序，是排序算法中最为著名的一种。 气泡排序的过程：首先将第一个记录的关键字与第二个记录的关键字进行比较，若与需要的顺序不符，则将两个记录交换，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟气泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟气泡排序，对前n-1个记录

29、进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i趟起泡排序是从r1到rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1kn)趟起泡排序。,5.4.1 排序,4. 快速排序 快速排序是对起泡排序的一种改进。其基本思想是：通过一趟排序将待排记录分成两部分，一部分记录的关键字均比另一部分的小，再分别对这两部分记录进行排序，直到整个序列有序。 经验证明，在所有同数量级的此类(先进的)排序方法中，就平均时间而言，快速排序是目前被认为是最实用的一种排序方

30、法。,5.4.2 查找,在计算机科学里另一种常用的算法是查找，是一种在列表中确定目标所在位置的算法。在日常生活中，查找是人们几乎每天都做的工作，比如在电话号码簿中查阅需要的电话号码，在字典中查找某个字，在火车时刻表中查找某次列车或到达某站的车次等。其中，电话号码簿、字典、火车时刻表都可以视为一个列表，查找是根据给定的一个值，在目标列表中找到该值的第一个记录的位置（这个位置有时称为索引）。如果表中存在这样的记录，则称查找成功，如果没有找到这样的记录，则称查找不成功。 查找的算法与列表的结构有关，我们介绍两种基本的查找方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则需要列表是有序

31、的。,5.4.2 查找,1. 顺序查找 顺序查找是最基本的查找方法，其过程为：从列表的某一端开始，逐个记录地用关键字和给定值进行比较，若该记录的关键字与给定值相等，则查找成功，找到要查的记录；反之进行下一个记录的比较，如果到达列表的另一端都没有关键字与给定值相等的记录，则表明表中没有要查的记录，查找不成功。 顺序查找的思想很简单，便于理解，并且它对于目标列表没有要求，适用于对不规则列表的查找。但是从效率上讲这种方法并不高，而在实际使用往往对很大的列表进行查找并且对各记录查找的概率也不同，此时效率的问题更加突出。顺序查找的平均查找长度为列表长度的一半，人们需要研究效率更好的查找算法。,5.4.2

32、 查找,2. 折半查找 折半查找是针对有顺列表设计的。其基本思想是：先确定待查记录所在的范围，然后逐步缩小范围，直到范围缩小到一个记录，此时便可以判断是否找到所要查的记录。 折半查找从列表的中间记录开始比较，判别出目标在列表里的前半部还是后半部分，这样将范围缩小一半；下一步在剩下的一半中再比较，将范围再缩小一半。重复这个过程直到找到目标或是目标不在这个列表里。折半查找的平均查找长度接近log2(n+1)-1。折半查找要求查找列表必须为有序列表。在实际运用中，需先对无序列表进行排序，然后进行折半查找。如果只进行一次查找，这样做的代价比顺序查找还要大，对于频繁的查找，进行一次排序多次查找，总体上效

33、率得到提高。,第五节 递归,5.5 递归,递归：递归是指算法在过程中调用自身作为子算法的一种设计方法。调用可以是直接的或间接的，直接调用指算法中将自身作为子算法直接调用，间接调用指算法中调用了其他算法作为子算法，而被调用的算法中又调用了这个算法。递归调用产生了算法的重入现象。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。,5.5 递归,递归是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法

34、将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解。这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特殊情况下当规模N=1时，能直接得解。本书第1.1.4节中介绍的梵天塔问题就是递归算法的经典用例。,5.5 递归,递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的。(例如Fibonacci函数) (2)问题解法按递归算法实现。(例如回溯) (3)数据的结构形式是按递归定义的。(例如树的遍历，图的搜索等) 一般来说，递归需要有边界条件，递归算法的执行过程分递推和回归两个阶段。当边界条件不满足时，是递推

35、阶段，把较复杂问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在递推阶段，必须要有终止递归的情况。当边界条件满足时，进入回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。,5.5 递归,递归算法的优点： (1) 对于按递归定义的数据集合处理效率很高。 (2) 易于将复杂的问题简单化，便于理解。 (3) 对于特殊的数据结构，例如二叉树、图等具有良好的处理能力。 递归算法的缺点： 递归需要一系列的调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。在递归调用的过程当中系统为每一层的返回点、局部量等需要堆栈来存储。递归次数多了容易造成栈溢出等。,5.5 递归,例 52：背包问题(Knapsack problem) 问题描述：有一个最大承重量为M的背包和重量、价值各不相同的物品N件，每种物品只有一件，可以选取或不选。问如何选取才能使所选物品的总重量不超过背包的承重限制M，并且所选物品的价值之和最大。 问题分析：设N件物品的重量分别为w1、w2、wn，物品的价值分别为v1、v2、vn。设用Sumv(m,n) 表示已选取入背包中的所