算法与数据结构讲课课件.ppt

第三章 算法与数据结构,用计算机解决实际问题时，首先要进行程序 设计；而程序设计主要包括两个方 面的内 容： -行为特性的设计- 将解决实际问题的每个细节准确地加以定义，并且还应当将全部解题过程完整地描述出来。这就是算法的设计 -结构特性的设计- 确定合适的数据结构,程序设计的步骤： 1了解和研究需要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤 2模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来 3用计算机语言将步骤转化为计算机可以“读懂”的计算机程序，即所谓的“编程” 4进行测试和修改 本章着重讨论解决问题的核心-算法以及 算法的处理对象-数据的结构,3.1 算法,通常，把解题过程的准确而完整的描述称作解该问题的算法 程序的目的是加工数据，而如何加工数据是算法的问题。程序是数据结构与算法的统一 niklaus wirth教授进一步提出了如下有名公式： 程序算法数据结构 程序就是在数据的某些特定的表示方式和结构基础上对抽象算法的计算机语言具体表述 从算法的角度，可将程序定义为: 为解决给定问题的计算机语言有穷操作规则的有序集合,一算法的两要素,一个算法由一些操作组成，而这些操作又是按一定的控制结构所规定的次序执行的 操作 (1) 逻辑运算： “与”、“或”、“非” (2) 算术运算： 加、减、乘、除 (3) 数据比较： 大于、小于、等于、不等于 (4) 数据传送： 输入、输出、赋值 算法的控制结构（三种基本控制结构） (1)顺序 (a.顺序结构） (2)选择 (b.选择结构） (3)循环 (c.直到型循环 d.当型循环),三种基本控制结构的一般形式,算法结构化,1966 bohm jacopini,顺序,选择,循环直到,循环当,二算法的特征,算法具有以下几个特征： 有效性 确定性，可行性 足够的信息:一个或多个输出;0个或多个输入 有穷性:执行是可终止的 算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答,三算法的表示,自然语言 专用工具 算法描述语言,自然语言,用自然语言描述算法通俗易懂，但它 存在着难以克服的缺陷: 易产生歧义性 语句比较繁琐冗长，并且很难清楚地表达算法的逻辑流程。如果算法中包含判断、循环处理，尤其是这些处理的嵌套层数增多，自然语言描述其流程既不直观又很难表达清楚 当今的计算机尚不能处理用自然语言表示的算法,专用工具,为了形象地描述算法，人们创造了许多专用工具来描述算法。常用的有流程图、pad图和n-s图等。除图形工具之外，人们可使用代码符号(如伪代码)描述算法 pad是问题分析图（problem analysis diagram）的英文缩写，自1973年由日本日立公司发明以来，已经得到一定程度的推广。它用二维数形结构的图表示程序的控制流，将这种图转换为程序代码比较容易,常用流程图符号,流程图简明直观、便于交流,n-s图,nassi和shneiderman提出了一种符合结构化程序设计原则的图形描述工具，叫做盒图，也叫做n-s图,n-s图的五种基本控制结构,pad图,pad是problem analysis diagram 的缩写，它是日本日立公司提出，由程序流程图演化来的，用结构化程序设计思想表现程序逻辑结构的图形工具。现在已为iso认可,pad图的五种基本控制结构,算法描述语言,为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。如pascal_like，c_like等类_xxx语言。本书约定一种算法描述语言，这种语言是vb语言的变体，称为类vb语言,类vb语言一览表,类vb语言一览表,四. 常用算法,枚举法 (穷举法） 迭代法 递归法 递推法 分治法 回溯法,枚举法,枚举法亦称穷举法，它的基本思想是：首先依据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则本题无答案 枚举法的实质是枚举所有可能的解，用检验条件判断定哪些是有用的，哪些是无用的，而题目往往就是检验条件。枚举法的特点是算法简单，但有时运算量大，对于可确定解的取值范围且又一时找不到其他更好的算法时，就可以用它,枚举法例题,百鸡问题：百元买百鸡 公鸡 5元 母鸡 3元 小鸡 1/3元 x+y+z=100 5x+3y+z/3=100 三层循环嵌套,迭代法,重复同样步骤，可以逐次求得更精确的值。这一过程即为迭代过程 使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差，然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差。并认为最后一次迭代得到的近似值为问题的解。这种迭代方法称为逼近迭代,在x1.5附近的一个根,递归法,递归是构造计算机算法的一种基本方法。如果一个过程直接或间接地调用它自身，则称该过程是递归的， 递归过程必须有一个递归终止条件，即存在“递归出口”。无条件的递归是毫无意义的 f(n)=n!=n*(n-1)!=n*f(n-1),long fac(int i) if (i = 1) fac = 1; return fac; else fac = i * fac(i - 1); ,递归算法汉诺塔,proc movetower( n, 1, 2) call movetower( n-1, 1, 3) call movedisk( 1, 2) call movetower( n-1, 3, 2) end,1,2,3,n,n-1,递归法（汉诺塔移动问题）,please input the number of disks : n= 3 move disk 1 from peg 1 to peg 2 move disk 2 from peg 1 to peg 3 move disk 1 from peg 2 to peg 3 move disk 3 from peg 1 to peg 2 move disk 1 from peg 3 to peg 1 move disk 2 from peg 3 to peg 2 move disk 1 from peg 1 to peg 2 press any key to continue,递推法,所谓递推法，它的数学公式也是递归的（如：f(n)=n!=n*(n-1)!=n*f(n-1) ）。只是在实现计算时迭代方向相反。从给定边界出发逐步迭代到达指定计算参数。它不需反复调用自己（节省了很多调用参数匹配开销），效率较高 递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见,递归与递推,递推是从已知的初始条件出发，逐次递推出最后所求的值 递归则是从需求的函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值 一般说来，一个递推算法总可以转换为一个递归算法。尽管递归算法往往比非递归算法要付出更多的执行时间，由于递归算法编程序非常容易，用递归过程来描述算法非常自然，而且证明算法的正确性也比相应的非递归形式容易很多，因此，递归是算法设计的基本技术,f(0) = 0! = 1 f(1) = 1! = 1*f(0) = 1 f(2) = 2! = 2*f(1) = 2 f(3) = 3! = 3* f(2) = 6 . f(n) = n* (n-1)! = n*f(n-1),分治法,解一个复杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法 分治法在设计检索、快速分类选择等问题的算法中是很有效的，并得到广泛应用,分治法（divide and conquer) “分”而治之,一般方法 对大规模问题的求解 利用分治法求解大规模问题,分治策略基本思想 当问题的规模较大而无法直接求解时，将整个问题分成若干个小问题，然后分而治之。 可用递归过程描述。,一般情况下，子问题与原始问题“同质”,回溯法,回溯法是设计算法中的一种基本策略。在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解,例：迷宫游戏,例：8皇后问题 在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。 8皇后问题可以表示为8-元组(x1,x8) ，其中xi是放置皇后i所在的列号。 显式约束条件是si=1,2,3,4,5,6,7,8, 1i8 隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。,算法分析,评价算法是否完善，我们主要关心以下三个问题: 算法的复杂度 时间复杂度-算法的时间代价 空间复杂度-执行算法所需的内存空间 算法的最优性-衡量算法的好坏主要依据算法的复杂度，特别是时间复杂度 最优算法是指在解决一个问题时，如果在被研究的算法类中，没有一个算法比现有算法执行更少的基本运算，则称此算法是最优的 快速算法的设计-与工程上常用的算法相比，其时间复杂度较小 快速算法不一定是最优算法,背包问题,假设有一个能装入总体积为t的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=t，要求找出所有满足上述条件的解。例如：当t=10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2） （1，4，5） （8，2） （3，5，2）。 提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。,举例：顺序搜索法,输入：一维数组 l（1：n），搜索项 x 输出：第一次使l（j）=x的j，若x不在数组l中，则输出为0 j=1 while (jx) do j=j+1 if jn then j=0 output j return 设x在数组l中的概率为q。当输入的x为l(i)时，算法所做的 比较次数为 i,1=i=n t(l(i)= n,i=n+1,假设输入x出现在数组每个位置上的可能性相等： q/n,1=i=n p(l(i)= 1-q,i=n+1 于是：a(n)=(n+1)q/2+(1-q)n 当已知x在数组l中时，q=1,则a(n)=(n+1)/2，平均要检查一半的元素 当已知有一半的机会不在此数组中时，q=1/2,则a(n)约为3n/4，即大约要检查数组中3/4的元素 最坏的情况是检查n次,3.2 数据结构,任何程序都要处理数据 在计算机诞生后的一段时期，它主要作为高速的科学计算工具。程序关心的是计算机速度、精确性、可靠性，用到的数据相对简单：各种类型的变量，一维或多维数组、简单的表 随着计算机商业应用的发展，程序关心的数据组织和快速存取 计算机系统更是大量处理数据 计算机科学的各个领域及有关的应用软件都要用到数据结构,一数据结构概述,数据的基本单位称为数据元素。有时一个数据元素由若干个数据项组成，在这种情况下，称数据元素为记录。数据项是数据的最小单位 最简单的数据元素是一个数据项（有时也叫元素），复杂的数据项间存在着某些联系。这种联系称为结构。当然，数据元素之间还可以构成结构关系，所以数据结构就是指数据之间的结构关系(或是带有结构特性的数据元素的集合),数据结构的研究内容,数据结构作为一个学科分支主要是研究程序设计中计算机所操作的对象以及它们之间的关系和运算，概括地说是三个方面： 数据的逻辑结构 数据的存储结构 数据的运算,数据的逻辑结构,数据的逻辑结构是数据元素之间的逻辑关系。它只抽象地反映数据元素集合的结构，而不管其存储方式，它可以用一个二元组给出如下形式的定义： data-structure (d,r) 其中，d是数据元素的集合，r是d上关系的集合,数据的存储结构,数据的逻辑结构在计算机内存中的映象称为数据的物理结构。数据的存储结构是数据在计算机内存中的实际存放方式。只能是首地址后跟一长串数据，或按地址寻值别无它法,数据的运算,程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等。简单的逻辑结构和物理结构完全一致，如数组和表处理，所以学好简单数据结构就可以打下实现复杂数据结构的基础。而复杂数据结构能提高我们解决问题的能力。在以下的讲述中数据元素用“结点”画出，关系用结点间弧线或箭头表示,数据结构的分类,从结构的观点，一般将数据结构分为两大类： 线性数据结构 线性表、栈、队列、串、数组和文件 非线性数据结构 树和图,二线性表,线性表是最简单、最常用也是最基本的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列: (a1, a2 ,a3,an) 表中元素的个数n定义为线性表的长度(n0)，n=0的表称为空表 线性表的结构特征是：数据元素呈线性关系 在线性表中必存在唯一被称为“第一个”的数据元素 必存在唯一的一个被称为“最后一个”的数据元素 除第一个元素外，每个元素都有且只有一个前驱元素 除最后一个元素外，每个元素都有且只有一个后继元素 所有数据元素ai在同一个线性表中必须是相同的数据类型,线性表（续）,线性表按其存储结构可分为顺序表和链表 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表 线性表的基本运算主要有： 在两个确定的元素之间插入一个新的元素 删除线性表中某个元素 按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新,顺序表和一维数组,计算机中表示线性表最简单的办法是用一组地址连续的存储单元依次存放线性表的数据元素。这种顺序分配的存储方式的表，称为顺序表 逻辑上的相邻元素存储地址也相邻 线性表的逻辑关系隐含在存储单元的邻接关系中 数据元素的数据类型相同，每个元素占用同样大小的存储单元 高级语言里的一维数组就是用顺序方式存储的线性表 线性表的示意图如下图所示,顺序表插入算法,在线性表(a1, a2,，ai，ai+1，an)的第i个位置插入元素x，使之成为(a1, a2,，ai，x，ai+1，an)，其算法描述如下： proc insert (var a,var n,i,x) 注释：在一维数组a(1n)中第i个元素之前插入一个新元素x if(in+1) then error(“位置不存在！”) 注释：插入的位置不合法 else for j=n down to i+1 a(j+1)=a(j) 注释：元素后移 next j endif a(i)=x 注释：进行插入 n=n+1 注释：线性表的长度加1 end,顺序表删除算法,通常，在表长为n的线性表(a1, a2 ,，ai-1,ai，ai+1，an)中删除第i个数据元素，还需将第i+1个至第n个元素向前推动一个位置，即(a1, a2 ,，ai-1,ai+1，an)，其算法描述如下： proc delete (var a,var n,i) 注释：一维数组a(1:n)中的第i个元素处删除该元素x if (in) then error (位置不存在！) 注释：删除的位置不合法 else for j=i to n-1 a(j)=a(j+1) 注释：元素前移 next j n=n-1 注释：表长减1 endif end,链表,在顺序表中插入或删除元素时，都不可避免地要作元素的移动，每进行一次插入或删除，都要移动近乎一半的元素。又由于顺序表是一组地址连续的存储单元，对于长度可变的线性表，必须按其可能达到的最大长度预先分配空间，这可能由于估计不足造成一部分空间太长而得不到充分利用，也可能因空间过短而造成溢出。链表恰能有效地克服这些缺点。链表一般有单链表、双向链表和循环链表,单链表(线性链表),单链表就是链式存储的线性表，其结点除信息域外还含有一个指针域，用来指出其后继结点的位置。单链表的最后一个结点没有后继结点，它的指针域为空(记为null 或)。另外还需要设置一个指针head，指向单链表的第一个结点 链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可,单链表的相关操作,单链表节点结构,单链表逻辑示意图,单链表的插入,单链表的删除,循环链表,循环链表是表结构形式上和单循表稍有不同的一种链表。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“null”，而是指向头一个结点，整个链表成为一个由链指针相链结的环，故称之为循环链表。其插入、删除算法和单链表没有多大区别,双向链表,对于线性表来说，除了设有指向后继结点的指针外，还可设一个指向前驱结点的指针。我们称这种含有两个指针域的结点构成的链表为双向链表。由于每个结点中都设有两个指针，则不仅可直接得到后继结点的信息，也容易得到前驱结点的信息。但在作插入、删除运算时，需要同时修改两个方向上的指针。一般情况下，我们称结点含有多个指针域的链表为多重链表，上述表示线性表的双向链表是多重链表,循环链表与双向链表结构对比,栈,栈(stack)也是一种特殊的线性表，是一种“后进先出”的结构，也是使用最为广泛的数据结构之一 栈的结构特点货栈 货栈 穿衣服的顺序 子弹压入子弹夹 摞盘子,栈（续）,栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom) ；栈的操作是按先进后出的原则进行，故栈又称为lifo (last in first out)表，如右上图所示 栈的物理存储可以用顺序存储结构，也可以用链式存储结构，如右下图所示,栈（续）,栈的运算： 通常对栈进行的运算有：设置一个空栈、判定某个栈是否为空栈、进栈操作、退栈操作以及读取栈顶元素等。下面分别给出顺序存储结构栈的进栈和退栈的算法,进栈,proc pushstack (var stack，m，var top，x) 注释：在栈stack(1:m)的栈顶top之上插入元素x begin if top=m then error (“栈满！”) else top=top+1 注释：栈顶上移 stack(top)=x 注释：将x放入栈顶 endif end,退栈,proc popstack (var stack，var top，var y)：var 注释：当栈空时返回函数值false，反之 退出栈顶元素赋给变量y并返回函数值true begin if top=0 then return (false) else y=stack(top) 注释：将栈顶元素赋给变量y top=top-1 注释：栈顶下移 return (true) endif end,队列,队列也是一种特殊的线性表，与生活中的“排队”极为相似，也是按“先来到先解决”的原则行事的，既不允许“加塞儿”，也不允许“中途离队”，“先入先出” 队列(queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)，队列的物理存储可以用顺序存储结构，也可以用链式存储结构,队列的运算,通常对队列进行的运算有：设置一个空队列；判定某个队列是否是空队列；插入一个新的队尾元素，简称入队列；删除队头元素，简称出队列；以及读取队头元素等 如果进入队列的元素个数事先可以估计得到，则队列可以按顺序存储方式进行组织。当队列的容量无法预先估计时，可以采用右图所示的链表存储结构,队列的运算（续）,“假溢出”问题：若采取每插入一个元素，队尾指针变量r的值加1，每删除一个元素，队头指示变量f的值加1的方法，则经过若干次插入、删除运算后，尽管队列中的元素个数小于存储空间的容量，但由于此时r可能已指向存储空间的末端，而无法再进行插入了。解决办法是把队列的存储空间逻辑上看成一个环，当r指向存储空间的末端后，就把它重新置成指向存储空间的始端，如下图所示,循环队列,将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。采用循环队列结构后，有效地解决了“假溢出”的问题，避免了数据元素的移动 插入一个新元素 rear = mod(rear,m)+1 删除一个元素 front = mod(front,m)+1 front = rear 队列空或满， 增加一个标志变量s,循环队列（续）,假设标志为s，其状态定义为 0，队列空 s 1，队列不空,设初始状态 f=r， s0， 插入一个元素后置 s1，,插入操作 if ( f = r ) and ( s = 1 ) then error (“ 队满！”)； return; else r = mod ( r,m ) + 1; q(r) = x; s = 1; endif,删除操作 if s = 0 then error (“ 队空！”)； return; else f mod ( f,m ) + 1; if f = r then s = 0; endif,三串,串(string)：由零个或多个字符组成的有限序列，一般记作 s=“s0 s1 s2 sn” 可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作，在这点上其结构和链表类似。串也可以用链表表示 子串(substring)是串的一部分，具有串的一切特征 字符串在数据处理中是最常用到的数据结构，为了连接、删除、插入操作，用子串有时很方便值为空格字符串的空格串“ ”不等同空串 值为单个字符的字符串不等同单个字符，如字符串“a”不等同字符a,串(string)的操作,赋值：s=“student” 求长度：len (s)=7 判等：equal (s,“stud”)=false 联接：concat(s,“ number”)=“student number” 定位：index(s,“d”)=4 求子串：substr(s,2,4)=“tud” 置换 插入 删除,四树和二叉树,树型结构是一类重要的非线性数据结构。在此类结构中，元素之间存在着明显的分层或嵌套关系，它们通常以各种形式的链表作存储结构，树和二叉树是最常用的树型结构 基本术语 结点、结点度、根、支、叶结点 子结点、父结点、兄弟结点 树的度、路径、长度、高度、深度 森林、有序、无序,树,树结构类似一棵倒长的树，结构中含有一个类似“树根”的结点和若干类似“树叶”的结点以及若干分支结点。树的逻辑结构如图所示,树的形式化定义,树(tree)是由一个或多个结点组成的有限集合t 其中有一个特定的称为根(root)的结点 其余结点可分为m(m0)个互不相交的有限集t1,t2,t3 ,tm 其中每一个集合本身又是一棵树，且称为根的子树(subtree）,树,树的表示，每进一层次加一个括号，同层次用逗号分开。例如： (a(b(e,f),c(g),d(h,i,j) 一个结点的子树个数称为该结点的度（degree）；树中各结点的度的最大值被定义为该树的度；0棵或多棵不相交的树的集合(通常是有序集)称为森林,树结构举例,树的存储结构,数组实现方式（双亲表示法） 链表实现方式（孩子表示法） 二叉链表实现方式（孩子兄弟表示法）,数组实现方式,用数组存储树的结点信息，在每个结点中附设一个指示器指示其双亲结点在数组中的位置。结构描述： #define maxsize 100 typedef struct ptnode telemtype data； int parent ； ptnode； typedef struc ptnode nodesmaxsize； int n； ptree；,数组实现方式,链表实现方式,把每个结点的孩子结点排列起来，组成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表。结构描述： typedef struct ctnode typedef struct int child； ctbox nodesmaxsize； struct ctnode *next： int n，r； *childptr； ctree； typedef struct telemtype data； childptr firstchild； ctbox；,链表实现方式,二叉链表实现方式,以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。结构描述： typedef struct csnode elemtype data； struct csnode *firstchild ， *netsibling； csnode，* cstree；,二叉链表实现方式,二叉树,二叉树是另一种重要的树形结构，其结构定义为：二叉树(binary tree)是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成，如右下图所示,二叉树的五种基本形态,二叉树的性质,性质一 二叉树的第i层上至多有2i-1 个结点（1=i） 利用归纳法证明： 只有一个结点，对的； 假设对所有的j，i=j=1，命题成立，即在第j层上，至多有2j-1 个结点。 由归纳假设，第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大 结点数的2倍，即 2x2i-2 = 2i-1。 由性质一可见，深度为k的二叉树的最大结点数为：2k-1 性质二 深度为k的二叉树上最多含有2k-1个结点（k = 1）,二叉树的存储结构,顺序存储（一维数组） 记录数组结构 链式存储 二叉链表 三叉链表,顺序存储（一维数组）,记录数组结构,二叉链表,三叉链表,二叉树与树的区别（表达形式）,二叉树与树的区别（观念）,二叉树是一种特定的树结构，但不是普通树的特殊情况； 二叉树可以为空；而树则不能为空； 二叉树的结点的子树分左子树和右子树，而树则无此区分,树、森林与二叉树的转换,树转换成二叉树： 保留一个结点的最左子结点； 抹掉其余兄弟结点与上级结点的连线； 将兄弟结点连在一起； 以根为轴，顺时针旋转一个角度； 二叉树还原成树 step1 若某结点是其双亲的左子，则把该结点的右子、右子的右子、, 都与该结点的双亲结点用线连起来； step2 删除原二叉树中所有的双亲结点与右子结点的连线； step3 整理1、2两步所得到的树或森林，使之结构层次分明,森林转换成二叉树 将森林中每棵树的树根连接起来； 将每棵树转换成对应的二叉树； 以森林中第一棵树的根为轴顺时针旋转一个 角度,树转换成二叉树,二叉树还原成树,森林转换成二叉树,树和二叉树的遍历(周游),对于树形结构的运算很多，但最重要、使用最为 广泛的是遍历。遍历一个树形结构就是按一定的次序，系统地访问该结构中的所有结点，使每个结点恰被访问一次。我们将重点讨论二叉树的遍历,树的遍历,根据树的递归定义，有两种遍历树的方法： 先根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先访问树的根结点，然后依次先根遍历每棵子树 后根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先依次后根遍历每一棵子树，然后访问树的根结点,二叉树的遍历,遍历（traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。 遍历的方法很多，常用的有： 前序遍历 中序遍历 后序遍历,二叉树的遍历演示,算法语言描述的遍历算法,我们以二叉树中序遍历为例，给出二叉树遍历的递归算法和非递归算法 中序遍历的递归算法 procedure inorder (btp) 注释：中序遍历二叉树，btp为指向根结点的指针 begin if btpnull then call inorder(btp.lc) call process(btp) call inorder(btp.rc) endif end,中序遍历的非递归算法,由中序遍历的定义可知，若二叉树不空，应先遍历其左子树。算法中设置了一堆栈stack(1:m)，栈顶指针为top；同时，算法中还设置了一个活动指针变量p，用来指向当前要访问的结点 算法的主要思想是： 若pnull，则该结点进栈，再将p指向左孩子结点； 若pnull，则退出栈顶元素送p，并处理该结点， 然后再将p指向该结点的右孩子结点； 重复上述过程，直到p为空(nil)并且栈顶指针top为0,中序遍历的非递归算法,procedure inorder1(btp) 注释：中序遍历二叉树，指针btp指向根结点，stack(1:m)为栈 begin p=btp；top=0 注释：将指针p赋为根结点，栈顶指示器赋初值 while not (p=nil .and. top=0) do while pnil do top=top+1 注释：栈顶上移 stack(top)=p 注释：将指针压入栈顶 p=p.lc 注释：指针p入栈后指向其左孩子直至p为空 endwhile if top0 then p=stack(top) top=top-1 call process(p) p=p.rc endif 注释：退栈访问根结点之后p指向其右孩子 endwhile end,本节小结,主要掌握： 树与二叉树的关系 树的二叉树表示 二叉树的遍历 习题： 课后习题 9、10 二叉树的后序遍历的非递归算法,五图,图是一种较之线性表和树形结构更为复杂的非线性数据结构。图中各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。图是对结点的前趋和后继个数不加限制的数据结构。有关图的理论，在“离散数学”的图论中有详细论述和证明。在ds中，只讨论图在计算机中的实现和操作。 现实生活中，图的应用范围很广泛，涉及：电讯工程、电网调度、集成电路设计；交通管理、工程管理、系统工程等领,图的概念和术语,习惯上，常用g=(v,e)代表一个图 结点又称为顶点，v是结点的有穷集合(非空) 相关的结点偶对称为边(或弧)，e是边的有穷集合(e可为空集，对应的图中只有顶点没有边)。 图中代表一条边的结点偶对如果是无序的，则称此图为无向图，在无向图中(v1, v2)和(v2, v1)这两个偶对代表的是同一条边 有向图是由顶点的非空有限集和边的有限集组成。边是顶点的有序对，(v1, v2)和(v2, v1)表示的是不同的边,图的概念和术语（续）,无向图,有向图,图的概念和术语（续）,n个顶点的无向图边的最大数目是n(n-1)/2。n个顶点的有向图边的最大数目为n2（不仅双环，而且自环） 若(v1, v2)e，则称v1和v2是相邻结点。边(v1, v2)是v1和v2相关联的边。一个结点的度是与该结点相关联的边的数目。对于有向图，则把以结点vi为终止的边的数目称结点vi的入度； 把以vi为始点的边的数目称为vi的出度。出度为0的结点称为终端结点,图的概念和术语（续）,在图g=(v,e)中，若(vp, vi1),( vi1, vi2),，(vin, vg)，都在e中，则称结点序列vp，vi1 ，vi2,，vin，vg为从结点vp到结点vg的一条路径。路径的长度定义为路径上边的数目 如果一条路径上的结点除vp和vg可以相同外，其它结点都不相同，则称此路径为一简单路径。vp = vg的简单路径称为回路(或环),图的概念和术语（续）,在无向图g=(v,e)中，如果从v1到v2有一条路径(相应的从v2到v1也一定有一条路径)，则称v1和v2是连通的。若图中任意两个结点vi和vj(vivj)，都是连通的，则称无向图g是连通的 在有向图中，若对于任意两个结点vi和vj (vivj)，都有一条从vi到vj的路径，同时还有一条从vj到vi的路径，则称有向图是强连通的,图的概念和术语（续）,在实际应用中可以用图的结点代表研究对象，用图的边代表对象之间的联系 由于应用需要，常常要在边上标出数字以表示附加信息。例如给代表公路或铁路的边标出数字以表示距离。我们把这样的图称为带权图。带权连通图又称为网络。如图给出的网络示例。(a)无向网络； (b)有向网络,无向网络与有向网络,无向网络,有向网络,图的存储,前面在讨论树和线性表的存储结构时，用到两种存储结构：顺序表和链表。但图结构中的结点间没有确定的关系（没根），任意两点之间都可能存在联系，因此无法用顺序结构来存放图的顶点数据。但借助数组可以用来表示顶点之间的关系。在图的存储结构中，常用下面两种方法：相邻矩阵表示法、邻接表表示法,相邻矩阵表示法,相邻矩阵是表示结点间的相邻关系的矩阵，若g是一个具有 n 个结点的图，则g的相邻矩阵是如下定义的 nn 矩阵:,1，若（vi，vj）是图g的边 ai,j 0，若（vi，vj）不是图g的边,相邻矩阵表示法（续）,相邻矩阵表示法（续）,用相邻矩阵表示图，占用的存储单元个数只与图中结点个数有关，而与边的数目无关。一个n个结点的图，若其边数比n少得多，那么它的相邻矩阵中就会有很多零元素，占用很多空间来存储零元素当然是个浪费。如果用邻接表表示法来表示图，则占用的存储单元个数不但与图中结点个数有关，而且与边数有关。同是n个结点的图，如果边数少，则占用的存储单元也少,邻接表表示法,邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点vi的所有邻接顶点 在邻接表中，每个顶点由三个域组成： 每个单链表附设一个头结点，结构为：,无向图的邻接表,有向图的邻接表,图的遍历,从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历 图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组visited，每访问一个顶点，便将其状态visitedi置为“真”。常用的图的遍历方法有两种：深度优先遍历和广度优先遍历,深度优先遍历,算法思想： step1 从图中某个顶点v0出发，并访问此顶点 step2 从v0出发，访问与v0邻接的顶点v1后，再从v1出发，访问与v1邻接且未被访问过的顶点v2。重复上述过程，直到不存在未访问过的邻接点为止 step3 如果是连通图，从任一顶点v0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止,深度优先遍历（续）,深度优先遍历算法程序(非递归) traver_dfs(struct headnode g,int v) int i,stackn,visitedn, top=-1 ; arcnode *p; for (i=0;i printf(“%d -”,gv.data); visitedv=1; top +; stacktop=v; p=gv.firstarc; while(top!=-1)|(p!=null) while(p!=null) if (visitedp-adjvex) p=p-nextarc; else printf(“%d -”,gp-adjvex.data); visitedp-adjvex=1; top+; stacktop=p-adjvex; p=gp-adjvex.firstarc; if( top !=-1) v=stacktop; top- -; p=gv.firstarc; p=p-nextarc; ,深度优先遍历,广度优先遍历,广度优先遍历法类似于树的按层次遍历的过程。即先访问第1个顶点所有邻接点后，再访问下一个顶点所有未被访问的邻接点 算法思想： step1 从图中某个顶点v0出发，并访问此顶点 step2 从v0出发，访问v0的各个未曾访问的邻接点w1，w2，,wk;然后,依此从w1,w2,wk出发访问各自未被访问的邻接点 step3 重复step2，直到全部顶点都被访问为止,广度优先遍历,本节小结,主要掌握： 图的基本概念和术语 邻接表表示法 图的深度优先遍历 习题： 课后习题 13,3.3 查找,计算机操作的数据有两种类型： 科学计算型：一种是数据量并不大，但计算异常复杂。 数据处理型：另一类是数据量很大，计算相对来说比较简单，如只做一些查询、登记、统计分析等 查找是数据处理中最基本、最重要的操作之一,基本概念,关键字是数据元素中可以唯一标识一个数据元素的数据项 查找是在数据结构中找出满足某种条件的记录 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数，或称平均检索长度 最常用的算法有顺序查找、二分查找、分块查找等,顺序查找,顺序查找的方法：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值； 或者找遍所有结点都找不到符合要求的项，即查找失败 假设我们采用一维数组来表示线性表，我们可以得到顺序查找的算法： 输入：线性表存储空间a，线性表长度n，被查找元素k 输出：查找成功，返回元素k的下标，否则返回-1,顺序查找算法,sub chazhao(a,n,x) dim i as integer for i=1 to n i为循环控制变量，n为线性表下标上界 if a(i)=k then k 为待查关键字值，如果 相等，则表明找到，退出循环 exit for end if next i if in then 如果i大于n，表明没找到， 返回假，否则返回i值 retuen -1 else return i end if end sub,顺序查找（续）,优点是对线性表的结点逻辑次序无要求，对线性表的存储结构无要求(顺序存储、链接存储皆可） 缺点是平均检索长度长，为n/2 设x在数组l中的概率为q。当输入的x为l(i)时，算法所做的比较次数为 i,1=i=n t(l(i)= n,i=n+1,顺序查找（续）,假设输入x出现在数组每个位置上的可能性相等，即： q/n,1=i=n p(l(i)= 1-q,i=n+1 于是：a(n)=(n+1)q/2+(1-q)n 当已知x在数组l中时，q=1,则a(n)=(n+1)/2，平均要检查一半的元素； 当已知有一半的机会不在此数组中时，q=1/2,则a(n)约为3n/4，即大约要检查数组中3/4的元素。 最坏的情况是检查 n 次,二分法查找,如果线性表结点是按关键字码值排好序的，且线性表以顺序方式存储，我们可以采用二分查找。这是一种效率较高的线性表查找方法 二分法查找的方法是：用要查找的关键码值x与线性表中间位置结点的关键码值w相比较，这时有三种可能： x = w，此时已经查找成功，查找结束 x w,表明 x只能在表的后半部分，所以取表的后半部分进行查找 x w表明 x只能在表的前半部分，取前半部分进行查找,二分法查找（续）,优点是平均检索长度小，为log2n 。粗略地可以这样看：每经过一个关键码值比较，则查找范围缩小一半，因此经过 log2n 次比较就可完成查找过程 缺点是它要求文件必须按关键字有序，并且只适用于顺序方式存储的顺序表 若初始文件无序，且不再进行记录的插入和删除则比较好的办法是，先对文件进行排序，使文件按关键字有序，使以后的查找可用二分查找法。但若文件中的记录不断变动，二分法就不适用了,二分查找算法,输入：顺序表存储空间a，表长度n，被查找元素x 输出：如果成功，返回x在表中的下标，否则返回-1 sub chazhao(a,n,x) dim i,j,m as integer dim flag as boolean i=1 j=n flag=false while(ik then j= m-1 大于则取表的前半部分,二分查找算法（续）,else i= m+1 小于则取表的后半部分 end if end if end while if flag=false then 如果flag=false，表明没 找到，返回-1，否则返回m retuen -1 else return m end if end sub,二分法查找（续）,数组（ 1,3,4,5,17,18,31,33 ） x=17 第一次：下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 low mid high xamid 第二次：下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 low mid high xamid 第三次：下标 0 1 2 3 4 5 6 7 元素值 1 3 4 5 17 18 31 33 low mid high xamid,分块查找,分块查找又称索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法，其特点是要求文件中记录关键字“分块有序” 分块查找的基本思想是：先抽取各块中的最大关键字构成一个索引表，由于文件中的记录按关键字分