计算机科学数据结构与算法.pptx

《计算机科学数据结构与算法.pptx》由会员分享，可在线阅读，更多相关《计算机科学数据结构与算法.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机科学数据结构与算法现在学习的是第1页，共59页本 章 教教 学学 目目 的的1.理解数据结构的概念，理解数据结构的逻辑和存储结构2.理解算法的概念和算法的基本特性，了解算法复杂度的度量方法3.理解线性数据结构，掌握栈和队列、串和数组等典型线性数据结构4.了解非线性的数据结构，了解树、二叉树和图等典型非线性数据结构5.理解排序、查找的概念，了解排序、查找的典型算法及其比较分析方法6.理解递归的概念，了解递归的实际应用 现在学习的是第2页，共59页本 章 教教 学学 内内 容容1.数据结构概述2.线性结构3.非线性结构4.基本算法5.递归现在学习的是第3页，共59页本 章 学学 习习 重重

2、点点1.数据结构的基本概念2.算法的描述、流程图的使用以及算法的复杂度的衡量3.顺序存储和链式存储的方法4.栈、队列、串和数组的概念和用法5.二叉树数据结构6.查询、排序和递归算法现在学习的是第4页，共59页第一节第一节 数据结构概述数据结构概述现在学习的是第5页，共59页5.1 数据结构概述数据结构概述5.1.1 数据结构数据结构 数据是对客观事物的符号表示，是信息的载体，它能够被计算机识别、存储和加工处理，是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。数据元

3、素是构成数据的基本单位。对于复杂事务的数学描述往往需要多个组成成分，每个基本的成分称为一个数据元素。有时，一个数据元素可以细分为一组数据项，数据项是数据中不可再分割的最小单位。研究具体问题时可以根据实际需要，确定数据的组成，即需要有多少数据元素，具体的数据元素是否再细分为数据项。现在学习的是第6页，共59页4.1 数据结构概述数据结构概述4.1.1 数据结构数据结构数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，它们之间总是存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有下列四类基本的结构：l集合

4、结构。在集合中，各数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构，各元素间没有直接的关联。l线性结构。该结构的数据元素之间存在着一对一的关系。l树型结构。该结构的数据元素之间存在着一对多的关系。l图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。现在学习的是第7页，共59页5.1 数据结构概述数据结构概述5.1.1 数据结构数据结构 （a）集合结构 （b）线性结构 （c）树型结构（d）图形结构图图 5 1 四类基本结构的示意图四类基本结构的示意图现在学习的是第8页，共59页5.1 数据结构概述数据结构概述4=5.1.1 数据结构数据结构逻辑结构数

5、据元素之间的逻辑关系（设计算法数学模型）物理结构数据结构在计算机中的映像（存储结构算法的实现）顺序存储结构借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系。现在学习的是第9页，共59页5.1 数据结构概述数据结构概述5.1.1 数据结构数据结构 数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。现在学习的是第10页，共59页5.1 数据结构概述数

6、据结构概述5.1.2 算法算法用计算机解决一个复杂的实际问题，大体需要如下的步骤。（1）将实际问题数学化，即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。（2）对于确定的数学问题，设计其求解的方法，即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。（3）用计算机上的一种程序设计语言

7、来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计或程序编制。（4）在计算机上编辑、调试和测试编制好的程序，直到输出所要求的结果。现在学习的是第11页，共59页5.1 数据结构概述数据结构概述5.1.2 算法算法1.算法算法的的概念概念 算法:对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。算法具有以下五个重要的特征：1）有穷性：一个算法必须保证执行有限步之后结束。2）确切性：算法的每一步骤必须有确切的定义。3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。4）输出：一

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

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

10、序设计语言接近于数学语言，十分严谨，但是需要进行专业化训练，不便于人们阅读理解。因此算法的描述通常使用流程图或伪代码。现在学习的是第14页，共59页5.1 数据结构概述数据结构概述5.1.2 算法算法2.算法的描述算法的描述图图 5 2 流程图基本图元流程图基本图元现在学习的是第15页，共59页5.1 数据结构概述数据结构概述5.1.2 算法算法3.算法的基本结构算法的基本结构图图 5 3 算法基本结构示意图算法基本结构示意图 通过基本结构的有机组合，可以描述各种算法。顺序结构的所有步骤使用率为1；分支结构有些分支不会被执行，使用率小于1；循环结构通常会多次执行，使用率大于1。从复杂程度上看，

11、循环结构最复杂，顺序结构最简单。现在学习的是第16页，共59页5.1 数据结构概述数据结构概述5.1.2 算法算法4.算法的度量算法的度量（1）时间复杂度 指算法从开始执行到处理结束所需要的总时间。通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的基本操作，以该基本操作重复执行的次数作为算法的时间度量。（2）空间复杂度 指算法从开始执行到处理结束所需的存储量空间的总和。程序运行所需的存储空间包括固定部分：这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关；可变部分：这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。现在学习的是第17页，共59页5.1

12、 数据结构概述数据结构概述5.1.2 算法算法4.算法的度量算法的度量 研究发现，时间和空间通常可以转换。在存储空间有限时，可以选择空间复杂度较低的算法，在减少对空间使用量的同时，时间复杂度通常会增加；如果需要能够较快地求出结果，则需要更大的存储空间支持。在大多数情况下，时间和空间因素可以进行相应转换，具体选择时可根据实际需要和成本因素确定选择什么策略。另外，需要提醒一点，不是时间复杂度高，算法的数学复杂程序就高。使用更高级的数学方法，能够以更少的时间和空间代价获取处理结果。这时，用于算法执行的时间虽然少了，但是用于算法设计的时间会大大增加。如果设计出的程序有足够多的使用率，代价总体上是值得的

13、。现在学习的是第18页，共59页5.1 数据结构概述数据结构概述5.1.2 算法算法5.子算法子算法 为了简化算法设计，提高空间利用率，提出了子算法子算法和算法调用算法调用的概念。所谓子算法，与算法类似，其功能和结构相对简单。设计子算法的目的是为了简化整个算法的设计，对于算法来说，需要用到子算法提供的功能时，通过算法调用来使用子算法提供的功能，即算法调用就是在算法中引用子算法，这样子算法所表示的整个处理过程在算法中就可以用一条调用语句来表示，使得整个算法的结构更为清晰，并且提高了空间得用率。子算法的调用需要专门处理，调用子算法在会多一些时间开销。子算法的方式适用于同一功能多次使用的情况。子算法

14、在具体实现时，可以使用子程序、过程、函数、方法、模块等形式进行实现，具体实现方式与使用的程序设计语言、程序设计方法有关。现在学习的是第19页，共59页第二节第二节 线性结构线性结构现在学习的是第20页，共59页5.2 线性结构线性结构5.2.1 线性表和串线性表和串 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系。线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。1.1.线性表线性表 (1)定义 线性表是n(n=0)个数据元素的有限序列，表中各个元素具有相同的属性，表中相邻元素间存在“序偶”关系。记做

15、：(a1,a2,.ai-1,ai,ai+1,an-1,an)其中，ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序现在学习的是第21页，共59页5.2 线性结构线性结构5.2.1 线性表和串线性表和串1.1.线性表线性表 (2)顺序存储 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。内存中的地址空间是线性的，用物理上的相邻实现数据元素之间的逻辑相邻关系既简单又自然。(3)链式存储 顺序存储方法简单，容易实现，但做插入删除操作时，需移动的元素较

16、多，因此效率低。链表的特点恰好与顺序表相反。现在学习的是第22页，共59页5.2 线性结构线性结构5.2.1 线性表和串线性表和串2.2.串串串串 串（即字符串）是一种特殊的线性表，它的数据元素是一个字符，字符串是计算机最常处理的非数值对象。串还具有自身的特性，常常把一个串作为一个整体来处理，因此，在这里我们把串作为独立结构的概念加以研究，介绍串的概念及基本运算。串是由零个或多个任意字符组成的字符序列。一般记作：S=”s1 s2 sn”其中S是串名；（注：双引号为定界符，双引号内的字符序列为串值，引号本身不属于串的内容。）si(1=i=0)个数据元素（节点）的有限集合，若为空集，则为空树空树。

17、否则：（1）有一个特殊的数据元素称为树的根根节点，根节点没有前驱节点。（2）若n1，除根节点之外的其余数据元素被分成m（m0）个互不相交的集合T1，T2，Tm，其每一个集合Ti（1im）本身又是一棵树。树T1，T2，Tm称为这个根节点的子树子树。可以看出，在树的定义中用了递归概念，即用树来定义树。树结构的算法与后面将介绍的二叉树结构的算法相类似，都使用了递归方法。现在学习的是第30页，共59页5.3.1 树树 1.1.树的定义 树具有下面两个特点：(1)树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。(2)树中所有节点可以有零个或多个后继节点。现在学习的是第31页，共59页

18、5.3.1 树树 1.1.树的定义 树中节点拥有的子树的个数称为节点的度度。树的度是树内节点度的最大值，即树中下级节点最多的节点的下级节点个数。节点的层次层次是指从根开始经过的节点数量，根的层次为1。树中节点的最大层次称为树的深度深度或高度高度。所经过的节点序列称为路径路径，如果设各边有权，则路径中各边权值的和称为路径长路径长度度。树内度为0的节点称为叶叶节点，或者称为终端终端节点；度不为0的节点称为分支分支节点，或者称为非终端非终端节点。一棵树的节点除叶节点外，其余的都是分支节点。树中一个节点的子树的根节点称为这个节点的孩子孩子，这个节点称为它孩子节点的双亲双亲，具有同一个双亲的孩子节点互称

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

20、叉树的所有分支节点都有左子树和右子树，并且所有叶子节点都在同一层上。图图 5 11 满二叉树和非满二叉树示意图满二叉树和非满二叉树示意图现在学习的是第34页，共59页5.3.1 树树 2 2.二叉二叉树 完全二叉树：一棵二叉树，其节点编号与同深度的满二叉树中的节点位置相同。完全二叉树的特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。图图 5 12 完全二叉树和非完全二叉树示意图完全二叉树和非完全二叉树示意图现在学习的是第35页，共59页5.3.1 树树 3.3.树的运算树的运算 树的运算主要是插入节点、删除

21、节点和遍历等几种。插入节点、删除节点运算改变树的结构，但要求在改变结构的同时，保持树的特性不变，对于二叉树，插入和删除操作后的树仍然是一棵二叉树。树的操作比较复杂，在专业书籍中有介绍，感兴趣的同学可以参考有关资料学习。现在学习的是第36页，共59页5.3.2 图图 1 1.定义定义 图也称做网，是一种比树形结构更复杂的非线性结构。图中任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。图结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。图由一组节点（称之为顶点）和一组顶点间的连线（称之为边或弧）构成的一种抽象数据类型。

22、树是层次结构的，其节点只能有一个双亲，而图中的节点可以有一个或多个双亲。若图中的边有方向，则称为有向图，若图中的边无方向，则称为无向图。现在学习的是第37页，共59页5.3.2 图图 1 1.定义定义 图是由非空的顶点集合和一个描述顶点之间关系边（或者弧）的集合组成，其形式化定义为：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。图图 5 13 无

23、向图无向图G1图图 5 14 有向图有向图G2现在学习的是第38页，共59页5.3.2 图图 2.2.图的运算图的运算 l添加顶点将一个新顶点插入到图中l添加边连接一个顶点和一个目标顶点l删除顶点从一个图里移除一个顶点，同时删除连接顶点的边。l删除边从一个图里移除某条边。l查找顶点通过遍历图来查找特定的顶点。l图的遍历指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。说明：图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上。现在学习的是第39页，共59页第四节第四节 基本算法基本算法现在学习的是第40页，共59页5.4 基本算法基本算法5.4.1 排序 排序：

24、将任意排列的数据集合，根据一定的规则，重新排列成有序的序列。关键字(key):在排序处理时用于比较的值称为关键字，它可能是数据本身，也可以是数据的某个数据项。排序算法的稳定性:如果在对象序列中有两个对象ri和rj，它们的关键字 ki=kj，且在排序之前，对象ri排在rj前面。如果在排序之后，对象ri仍在对象rj的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。在排序中需要进行两种基本操作：（1）比较关键字的大小；（2）改变某个记录的位置，即改变该序列的排列方式。现在学习的是第41页，共59页5.4.1 排序排序1.插入排序 插入排序是一类排序方法，其中最简单的是直接插入排序直接插

25、入排序，其基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序时：将排序列表分为已排序的和未排序的两部分。每次扫描时从未排序子列表中取出一个记录，转换到已排序的子列表中与其记录逐个比较并插入到合适的位置。含有n个元素列表至少需要n-1次扫描。直接插入排序结构简单，容易实现。在空间来看，它需要一个记录的辅助空间用作比较；从时间来看，排序的基本操作为比较两个记录的关键字和移动记录。当待排序记录的数量很小时，这是一种很好的排序方法，但随着记录数n的增大，其效率显然不佳。现在学习的是第42页，共59页5.4.1 排序排序1.插入排序 图图 5 15 插入排序

26、算法插入排序算法现在学习的是第43页，共59页5.4.1 排序排序2.选择排序 选择排序选择排序的基本思想是：每一趟在未排序记录选取关键字最小的记录作为有序序列中的某个记录，根据排序的目标是升序还是降序分别将选出的记录加入到有序序列的最前面或最后面。选择排序作为一类排序方法也有多种具体算法，其中最简单的是简单选择排序。一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1in）个记录交换。对n个记录进行简单选择排序的算法为：从1到n-1，进行n-1趟选择操作。与直接插入排序相比，选择排序由于是有选择地选取记录，在插入有序序列时，需要进行的记

27、录移动操作较少，但其总的时间复杂度也是O(n2)。现在学习的是第44页，共59页5.4.1 排序排序3.气泡排序 气泡排序气泡排序在有些资料上称做“起泡”或“冒泡”排序，是排序算法中最为著名的一种。气泡排序的过程：首先将第一个记录的关键字与第二个记录的关键字进行比较，若与需要的顺序不符，则将两个记录交换，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟气泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟气泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i趟起泡排序是从r1到r

28、n-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1kn)趟起泡排序。现在学习的是第45页，共59页5.4.1 排序排序4.快速排序 快速排序快速排序是对起泡排序的一种改进。其基本思想是：通过一趟排序将待排记录分成两部分，一部分记录的关键字均比另一部分的小，再分别对这两部分记录进行排序，直到整个序列有序。经验证明，在所有同数量级的此类(先进的)排序方法中，就平均时间而言，快速排序是目前被认为是最实用的一种排序方法。现在学习的是第46页，共59页5.4.2 查找查找 在计算机科学里另

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

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

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

32、，对于频繁的查找，进行一次排序多次查找，总体上效率得到提高。现在学习的是第49页，共59页第五节第五节 递归递归现在学习的是第50页，共59页5.5 递归递归 递归：递归是指算法在过程中调用自身作为子算法的一种设计方法。调用可以是直接的或间接的，直接调用指算法中将自身作为子算法直接调用，间接调用指算法中调用了其他算法作为子算法，而被调用的算法中又调用了这个算法。递归调用产生了算法的重入现象。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。现在学习的是第51页，共59页5

33、.5 递归递归 递归是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解。这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特殊情况下当规模N=1时，能直接得解。本书第1.1.4节中介绍的梵天塔问题就是递归算法的经典用例。现在学习的是第52页，共59页5.5 递归递归 递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(例如Fibonacci函数)(2)问题解法按递归算法实现

34、。(例如回溯)(3)数据的结构形式是按递归定义的。(例如树的遍历，图的搜索等)一般来说，递归需要有边界条件，递归算法的执行过程分递推和回归两个阶段。当边界条件不满足时，是递推阶段，把较复杂问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在递推阶段，必须要有终止递归的情况。当边界条件满足时，进入回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。现在学习的是第53页，共59页5.5 递归递归递归算法的优点：递归算法的优点：(1)对于按递归定义的数据集合处理效率很高。(2)易于将复杂的问题简单化，便于理解。(3)对于特殊的数据结构，例如二叉树、图等具有良好的处

35、理能力。递归算法的缺点：递归算法的缺点：递归需要一系列的调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。在递归调用的过程当中系统为每一层的返回点、局部量等需要堆栈来存储。递归次数多了容易造成栈溢出等。现在学习的是第54页，共59页5.5 递归递归例例 5 2：背包问题：背包问题(Knapsack problem)问题描述：有一个最大承重量为M的背包和重量、价值各不相同的物品N件，每种物品只有一件，可以选取或不选。问如何选取才能使所选物品的总重量不超过背包的承重限制M，并且所选物品的价值之和最大。问题分析：设N件物品的重量分别为w1、w2、wn，物品的价值分别为v1、v2、vn。

36、设用Sumv(m,n)表示已选取入背包中的所有物品价值和，m为背包当前可用的承重量，n为没有被选取到背包中的待选取的物品个数。现在学习的是第55页，共59页5.5 递归递归例例 5 2：背包问题：背包问题(Knapsack problem)不失一般性地，设物品i，其重量为wi，价值为vi。有两种可能：选取物品i，不选取物品i；则有对应的下列两种情况：（1）当前背包容量m大于wi时，物品i被选取，递归关系为：Sumv=(m-w,i-1)+vi即针对剩下的(i-1)个物品求承重量为（m-wi）的背包问题；（2）假设物品i不被选取，递归关系为：Sumv=(m,i-1)即针对剩下的(i-1)个物品求承

37、重量为m的背包问题；然后，取这两种可能的 中较大者为本步骤的解。现在学习的是第56页，共59页本本 章章 小小 结结现在学习的是第57页，共59页本 章 小小 结结 数据是计算机化的信息，是计算机可以直接处理的最基本的对象。计算机中的各种应用，都是对数据进行加工处理的过程。要使程序高效率地运行，必须根据数据的特性及数据间的相互关系设计出高质量的数据结构；数据结构通常有：集合结构、线性结构和非线性结构（树和图）。结构中定义的“关系”描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构。数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。数据结构主要研究数据的各种逻辑结构和存储

38、结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。现在学习的是第58页，共59页本 章 小小 结结 对特定问题求解步骤的一组规格化描述就是算法，也是计算机解题的过程。算法与数据结构是相辅相成的。算法必须具备：正确性、可读性、稳健性和高效性。算法的描述通常使用流程图或伪代码。线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，现实中的许多事物的关系都是非线性的。线性表是最简单、最基本、也是最常用的一种线性结构，有顺序存储和链式存储两种存储方法。栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作。现在学习的是第59页，共59页