数据结构与算法1

1、 大学计算机基础 第6章 数据结构与算法 程序是什么？ 程序=数据结构+算法！ 算法与数据结构一览表 DS算法算法定义、特性算法分析时间复杂度T(n)空间复杂度D(n)逻辑结构线性结构树型结构网状结构存储结构链式存储索引存储顺序存储散列存储查询DS上的运算插入删除更新例：某校对100个学生进行奖励，学生信息存在磁盘文件“file.dat”中，条件是其三门成绩全部在90分以上才能进行奖励，打印出被奖励学生的学号。以C语言为例，程序代码如下：#include Void main() struct stu /*数据类型*/ int num; float score3; a100; /* 定义变量*/

2、FILE *fp； Int I,j; fp=fopen(“file.dat”,”r”); /* 打开文件file.dat*/ for(i=0;i100;i+) Fread(&ai,sizeof(struct stu),1,fp); /* 从文件中读取数据*/ for(j=0;j3;j+) if(ai.scorej=3) /* 如果符合条件，输出其学号*/ printf(“num:%d”,ai.num); Fclose(fp); 由此可见，程序包括：对数据的描述，在程序中要指定数据的类型和数据的组织形式。 对操作的描述，即对数据的操作处理步骤 第6章 数据结构与算法数据结构（data struc

3、ture） ： 对数据的描述。即在程序中要指定数据的类型和数据的组织形式。算法（algorithm）： 对操作的描述。即对数据的操作处理步骤。程序：就是用计算机语言表示的数据结构和算法。程序设计：用计算机语言编写程序的过程。两个基本步骤： 1、设计数据结构和算法。 2、用一种计算机语言表示出来。 因此，数据结构与算法是程序设计的基础。 6.1 算 法 6.1.1 算法的基本概念 算法（algorithm）： 对操作的描述。即对数据的操作处理步骤。 算法的表示方法： 自然语言、流程图、N-S流程图、伪代码、计算机语言案例：计算sum=1+2+3+n的算法一、用自然语言描述1、输入n，即数据个数；

4、2、设置累加器sum，初始制为0；设置计数器i，初始值为1。3、当i小于或等于n时，做累加，即将sum与i相加，其和再放入sum中。计数器i取下一个数，即i等于i+1，直到i大于n时终止。4、输出累加和sum。二、流程图描述：sum=1+2+3+n的算法开始输入nSum0i 1i=nSum sum+Ii i+1输出sum结束否是三、N-S图描述： sum=1+2+3+n的算法 N-S图是美国学者I.Nassi和B.Shneiderman在1973年提出的一种流程图，其主要特点是不带有流程线，整个算法完全写在一个大的矩形框中。当i=n时，做输入nSum=0，i=1Sum=sum+Ii=i+1输出

5、sum的值N-S图方式四、伪代码描述： sum=1+2+3+n的算法 就是用文字和符号的方式来描述算法。在实际应用中，人们往往用接近于某种程序语言的代码形式作为伪代码。这样可以方便编程。 伪代码方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend五、计算机语言描述：程序用C语言描述sum=1+2+3+n的算法main() int n; int sum=0,i=1; scanf(“%d”,&n); for(i=1;i=n;i+) sum=sum+i; printf(“sum=%dn”,sum);一、算法的5个基本特征 1、可行性 2

6、、确定性 3、有穷性 4、有零个或多个输入 5、有一个或多个输出二、算法的2个基本要素 1、对数据的运算和操作 2、算法的控制结构。 算法的基本要素之一：对数据的运算和操作 在计算机系统中，基本的运算和操作有以下四类： 算术运算：主要包括加、减、乘、除等运算。 逻辑运算：主要包括“逻辑与”、“逻辑或”、“逻辑非” 等运算。 关系运算：主要包括“大于”、“大于或等于”、“小于”、 “小于或等于”、“等于”、“不等于”等运算。 数据传输：主要包括赋值、输入、输出等操作。算法流程图例子 算法的基本要素之二：算法的控制结构 控制结构-算法中各种操作步骤之间的执行顺序。 顺序结构选择结构循环结构三种基本

7、控制结构算法流程图例子三、算法设计的基本方法 六种：列举法、归纳法、递推、 递归、减半递推技术、回溯法。 1、列举法 列举法就是根据所要解决的问题，把所有可 能的情况都一一列举出来，并用问题中给定的条 件来检验哪些是需要的，哪些是不需要的。2、归纳法 归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。 可以看出，归纳法可以解决列举量为无限的问题。 3、迭代法（递推法） 递推是指从已知的初始条件出发，逐步推出所要求的结果。4、递归 在解决某些复杂问题时，为了降低问题的复杂程度（如问题的规模等），可以将问题逐层分解，最后归结为一些最简单的问题。例8.2 有5个人坐在一起，问第

8、5个人多少岁?他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？ 用递归方法求解，递归过程如下： age（5）age（4）十2 age（4）=age（3）十2 age（3）age（2）十2 age（2）age（1）十2 age（l）105、减半递推技术 “减半”是指将问题的规模减半，而问题的性质不变； “递推”是指重复“减半”的过程。 例8.3 设方程f（x）=0在区间 a，b上有实根，且f（a）与f（b） 符号相反，即f（a）f（b）0。利用二分法求该方程在区间 a，

9、b上的一个实根。 用二分法求方程实根的减半递推过程如下： 首先计算区间的中点c=（a+b）/2，然后计算函数在中点c的值f（c），并判断f （c）是否为0。若f（c）=0，则说明c就是所求的根，求解过程结束；如果f （c）0，则根据以下原则将原区间减半： 若f（a）f（c）0，则取原区间的前半部分，； 若f（b）f（c）0，则取原区间的后半部分。 最后根据计算精度 的要求，判断减半后的区间长度是否已经很小： 若|ab|，则过程结束，取（a+b）/2为根的近似值； 若|ab| ，则重复上述的减半过程。 6、回溯法 对于某些问题，一种有效的方法是“试”，即通过对问题的分析，找出一个解决问题的线索，

10、然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。 6.1 算 法 6.1.1 算法的基本概念 一、算法的基本特征 1、可行性 2、确定性 3、有穷性 4、有零个或多个输入 5、有一个或多个输出 二、算法的基本要素 1、对数据的运算和操作 2、算法的控制结构 三、算法设计的基本方法 列举法、归纳法、递推、递归、减半递推技术、回溯法 小结： 选用算法首先考虑正确性，还要考虑执行算法所耗费的时间和存储空间，同时算法应易于理解、编码、调试等。 算法的复杂度可分为时间复杂

11、度和空间复杂度，是衡量算法优劣的度量。8.1 算法8.1.2 算法的复杂度 一、算法的时间复杂度 算法的时间复杂度：执行算法所需要的计算工作量。 算法的计算工作量：用算法所执行的基本运算次数来度量， 基本运算次数：是问题规模的函数。 则：算法的计算工作量=f（n），其中n是问题的规模。（1） 平均性态 （Average Behavior） 平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。假设x是所有可能输入中的某个特定输入，用p（x）表示x出现的概率（即输入为x的概率），用t（x）表示算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为 在分析一个给定问题

12、算法的时间复杂度时，可以采用下面两种方法来分析算法的工作量。 其中Dn表示当规模为n时，算法执行时所有可能输入的集合。（2）最坏情况复杂性（Worst-Case Complexity） 最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。它定义为 其中，Dn和t（x）的含义同上。可以看出，最坏情况分析W（n）的计算要比平均性态分析A（n）的计算方便得多。 实际上，W（n）给出了估计算法工作量的一个上界，因此，它比A（n）更具有实用价值，是分析算法的时间复杂度常用的一个方法。 算法的执行时间依赖于具体的软硬件环境，所以，不能用执行时间的长短来衡量算法的时间复杂度，而要通过基本语句执行次

13、数的数量级来衡量。求解算法的时间复杂度的具体步骤是： 找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。 计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。 用大记号表示算法的时间性能。将基本语句执行次数的数量级放入大记号中。时间复杂度计算步骤：如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：for (i=1

14、; i=n; i+)x+;for (i=1; i=n; i+) for (j=1; j=n; j+) x+;第一个for循环的时间复杂度为(n)，第二个for循环的时间复杂度为(n2)，则整个算法的时间复杂度为(n+n2)=(n2)。算法时间复杂度举例：常见的算法时间复杂度：常见的算法时间复杂度由小到大依次为：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!) (1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是(1)。 (log2n)、(n)、(nlog2n)、(n2)和(n3)称为多项式时间，而(2n)和(n!)称为指数时间。

15、计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。“如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。” Temp=i; i=j; j=temp; 总共由3条语言,每条的频度均为1,每条的频度可认为都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。 下面4条语句: scanf(“%d”,&n); i=n; for(i=0,in;i+) i= i*1; (这也只算是一句) for(将j=0,jn*n;j+) i=i*1;(同上) 前两条频度均为1; 后两条分别

16、频度为 n和n*n 那么总频度均为 O(1)+O(1)+O(n)+O(n*n)=O(n*n) 1. 交换i和j的内容 sum=0；（一次） for(i=1;i=n;i+)（n次 ） for(j=1;j=n;j+) （n2次 ） sum+；（n2次 ）解：T(n)=2n2+n+1 =O(n2)2. for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; 解：语句1的频度是n-1语句2的频度是(n-1)*(2n+1)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2该程序的时间复杂度T(n)=O(n2). a=0; b=1; for (i=1

17、;in;i+) s=a+b; b=a; a=s; 解：语句1的频度：2,语句2的频度： n,语句3的频度： n-1,语句4的频度：n-1, 语句5的频度：n-1T(n)=2+n+3(n-1)=4n-1=O(n). 2算法的空间复杂度 -执行这个算法所需要的内存空间。 类似算法的时间复杂度，空间复杂度作为算法所需存储空间的度量。 6.1 算法课堂练习题考题(2005_4):(11)算法具有五个特性,以下选项中不属于算法特性的是 (A)有穷性 (B)简洁性 (C)可行性 (D)确定性 答案：B 考题（2005_4）5.问题处理方案的正确而完整的描述称为_答案： 算法考题（2005_9）（1）算法复

18、杂度主要包括时间复杂度和_复杂度。答案：空间6.2 数据结构数据结构主要研究三个问题:1、数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；2、在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；3、对各种数据结构进行的运算。6.2.1 什么是数据结构？例6.5 无序表的顺序查找与有序表的对分查找。现实世界中存在的一切个体都可以是数据元素。例如：“春、夏、秋、冬”，可以作为季节的数据元素； “26、56、65、 73、26、”，可以作为数值的数据元素； “父亲、儿子、女儿”，可以作为家庭成员的数据元素。 在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数

19、据元素一般简称为元素。在具有相同特点的数据元素集合中，各个数据元素之间存在着某种关系（即联系），这种关系反映了数据元素所固有的一种结构。 在数据处理中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。例如： 在“春、夏、秋、冬” 中，“春”是“夏”前件，。 一般来说，数据元素之间的任何关系都可以用前后件关系来描述。1数据的逻辑结构数据结构是指带有结构的数据元素的集合。这里所说的结构实际上就是指数据元素之间的前后件关系。由此可见，一个数据结构应包含如下两种信息： 表示数据元素的信息； 表示各数据元素之间的前后件关系。数据元素之间的前后件关系是指它们的逻辑关系

20、，这与它们在计算机中的存储位置无关。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 由前面的叙述可以看出，数据的逻辑结构有两个基本要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。因此，一个数据的逻辑结构可以表示成 B=（D，R），其中B表示数据的逻辑结构。例 一年四季的数据逻辑结构可以表示成 B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）例 家庭成员的数据逻辑结构可以表示成 B=（D， R） D=父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）2数据的存储结构数据的逻辑结构在计算机存储空间中的存放

21、形式称为数据的存储结构（也称数据的物理结构）。在数据的存储结构中，不仅要存放各数据元素的信息，还需 要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。对于一种数据的逻辑结构，如果采用不同的存储结构，则数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是非常重要的。6.2.2 数据结构的图形表示数据结构除了可以用前面的所述的二元关系表示外，还可以用图形来表示。例 n维向量 X = (x1,x2,xn) 也是一种数据结构。即X = (D,R)，其中数据元素的集合为： D = x1,x2,xn 关系为： R

22、= (x1,x2),(x2,x3),(xn 1,xn)例如，mn的矩阵mn的矩阵是一个数据结构。在这个数据结构中，矩阵的每一行 Ai = (ai1，ai2，ain)，i = 1,2,m可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为： D = A1，A2，AmD上的一个关系为： R = (A1，A2)，(A2，A3)，(Ai，Ai+1)，(Am 1，Am)显然，数据结构A中的每一个数据元素Ai（i = 1,2,m）又是另一个数据结构，即数据元素的集合为： Di = ai1，ai2, ，ainDi上的一个关系为： Ri = (ai1，ai2)，(ai2，ai3)，(aij,ai,j

23、+ 1)，(ai,n 1，ain)一个数据结构除了用二元关系表示外，还可以直观地用图形表示。 例 用图形表示数据结构B =（D，R），其中 D = di |1i7 = d1，d2，d3，d4，d5，d6，d7 R = (d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5) 这个数据结构的图形表示如图所示。6.2.3 线性结构与非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构与非线性结构。如果一个非空的数据结构满足下列条件：（1）有且只有一个根结点；（2）有且只有一个终端结点；（3）除根结点外，其他结点均只有一个前件；（4）除

24、终端结点外，其他结点均只有一个后件。则称该数据结构为线性结构。线性结构又称线性表。例如，如图所示的数据结构显然是满足上述两个条件的，但它不属于线性结构这个类型，因为如果在这个数据结构中删除结点A后，就不满足上述的条件。一个数据结构不是线性结构，则称之为非线性结构。 线性结构与非线性结构都可以是空的数据结构。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。课堂练习：6.2 数据结构的基本概念考题（2005_4）:(1)数据的存储结构是指 (A)存储在外存中的数据(B)数据所占的存储空间量 (C)数据在计算机中的顺序存储方式(D)数据的逻辑结构在计算机中的表示

25、答案：D考题（2005_9）:(4)下列叙述正确的是( )。A)一个逻辑数据结构只能有一种存储结构B) 数据的逻辑结构属于线性结构，存储结构属于非线性结构C)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率答案：D数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5 数据逻辑结构层次关系图图1-4 逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构一个数据结构中的各数据元素在计算机存

26、储空间中的位置关系与逻辑关系是有可能不同的。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 。数据的存储结构在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 常用的存储结构有顺序、链接、索引、散列等存储结构。 顺序存储结构主要用于线性结构。在这种存储方式中，把逻辑上相邻的数据元素结点存储在物理上相邻的存储单元中，各结点之间的关系由存储单元的邻接关系来体现。右图是将线性结构(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)顺序地存放在存储单元中的示意图。 （1）顺序存储结构在链接存储结构中，每个

27、存储结点要有两部分组成：一部分用于存放数据信息，另一部分用于存放指针。其中指针用于指向该结点的前件或后件。 （2）链接存储结构利用链接存储方式也可以存储非线性结构。下图（a）和（b）分别为一棵二叉树的逻辑结构与链接存储结构的示意图。 6.3 线性表及其顺序存储结构6.3.1 线性表的基本概念 线性表（Linear List）是最简单、最常用的一种数据结构。所谓线性表，是指n个数据元素的有限序列。 线性表可以表示为 （a1，a2，ai，an），其中ai是属于数据对象的元素，通常也称其为线性表中的一个结点。 当n=0时，称为空表。 6.3.2 线性表的顺序存储结构 在计算机中存放线性表，一种最简单

28、的方法是顺序存储。其特点如下：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 对于线性表的顺序存储结构，可以进行各种处理。 下面主要讨论线性表在顺序存储结构下的插入与删除运算。 下面通过一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。 例 下图 （a）是为一个长度为5的线性表顺序存储在长度为8的存储空间中。 例 图（a）是一个长度为7的线性表顺序存储在长度为8的存储空间中。现在要求删除表中的第2个元素（即删除元素23）。考题（2005_4）(5)下列对于线性表的描述中正确的是 A)存储空间不一定是连续,且各元素的存储顺序是任

29、意的 B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面 C)存储空间必须连续,且各前件元素一定存储在后件元素的前面 D)存储空间必须连续,且各元素的存储顺序是任意的答案：A课堂练习：6.3 线性表及其顺序存储结构6.4 栈和队列6.4.1 栈及其基本运算 1栈的基本概念 栈（stack）是限定仅在一端进行插入和删除运算的线性表。 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。 1栈的基本概念栈的顺序存储结构如图所示。6.4.1 栈及其基本运算 1栈的基本概念 2栈的基本运算栈的基本运算有三种：入栈、退栈与读栈顶元素。（1） 入栈运算入栈运算是指在栈顶位置

30、插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置；6.4.1 栈及其基本运算 （2） 退栈运算退栈运算是指取出栈顶元素并赋给某个变量。这个运算有两个基本操作：首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一。6.4.1 栈及其基本运算 （3） 读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。在这个运算中，栈顶指针不会改变。例 在下图中，设top为指向栈顶元素的指针。（a） 为容量为8的栈顺序存储空间，栈中已有4个元素；（b）与图（c）分别为入栈与退栈后的状态。考题（2005_4）(2)下列关于栈的描述中错误的是(A)栈是先进后出的线性表

31、 (B)栈只能顺序存储 (C)栈具有记忆作用 (D)对栈的插入和删除操作中，不需要改变栈底指针答案：B分析： 栈：特殊的线性表。限定只在一端进行插入与删除的线性表，这一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。6.4.2 队列及其基本运算1队列的基本概念队列（queue）是限定仅在表的一端进行插入，而在表的另一端进行删除的线性表。在队列中，允许插入的一端称为队尾， 允许删除的一端称为队头。队列又称为“先进先出”或“后进后出”的线性表。在队列中，通常用指针front 指向队头，用rear指向队尾，如图所示。1队列的基本概念下图是在队列中进行插

32、入与删除的示意图。 考题（2005_9）（3）以下关于栈的描述正确的是( )。A)在栈中只能插入元素而不能删除元素B)在栈中只能删除元素而不能插入C)栈是特殊的线性表，只能在一端插入或删除元素D)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素答案：C考题（2005_9）（5）数据结构分为逻辑结构和存储结构，循环队列属于_结构。答案：存储6.6 树与二叉树 6.6.1 树的基本概念树（tree）是一种非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特点。下图表示了一棵一般的树。图6.22 树的结构图实际上，能用树结构表示的例子有许多。例如，下图中的树表示了学校行政关

33、系结构。 图8.23 学校行政层次结构树在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为根结点（简称根）。例如，在下图中，结点A是树的根结点。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。例如，在下图中，结点E、F、G、H、I、J均为叶子结点。在树结构中，个结点所拥有的后件的个数称为该结点的度。例如，在下图中，根结点A的度为3；结点B的度为2；结点C的度为1；叶子结点的度为0。在树结构中，所有结点中的最大的度称为树的度。例如，下图所示的树的度为3。下面介绍树这种数据结构中的一些基本特征和基本术语由于树结构具有明显的层次关

34、系，即树是一种层次结构，所以在树结构中，一般按如下原则分层：根结点在第1层。同一层上所有结点的所有子结点都在下一层。例如，在下图中，根结点A在第1层；结点B、C、D在第2层；结点E、F、G、H、I、J在第3层。 树的最大层数称为树的深度。例如，下图所示的树的深度为3。 在树结构中，以某结点的一个子结点为根构成的树称为该结点的一棵 子树。例如，在下图中：根结点A有3棵子树，它们分别以B、C、D为根结点；结点B有2棵子树，它们分别以E、F为根结点。在树结构中，叶子结点没有子树。6.6.2 二叉树及其基本运算1二叉树的基本概念 二叉树（binary tree）是一种非常用的非线性数据结构。二叉树与前

35、面介绍的树结构不同，但它与树结构很相似，并且，有关树结构的所有术语都可以用到二叉树这种数据结构上。二叉树具有以下两个特点： 非空二叉树只有一个根结点； 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 右图所示是一颗二叉树，根结点为A，其左子树包含结点B、D、G、H，右子树包含结点C、E、F、I、J。根A的左子树又是一颗二叉树，其根结点为B，有非空的左子树（由结点D、G、H组成）和空的右子树。根A的右子树也是一颗二叉树，其根结点C，有非空的左子树（由结点E、I、J组成）和右子树（由结点F组成）。 在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。例如，下

36、图中所示的是4颗不同的二叉树，但如果作为树，它们就相同了。 4颗不同的二叉树2满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊的二叉树。（1） 满二叉树 在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。图（a）、（b）分别是深度为2、3的满二叉树。（2） 完全二叉树 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，而在最后一层上只缺少右边的若干结点。显然，满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。下图是两颗深度为3的完全二叉树。3二叉树的基本性质二叉树具有下列重要性质：性质1 在二叉树中，第i层的结点数最多为

37、2i-1个（i1）。性质2 在深度为k的二叉树中，结点总数最多为2k-1个（k1）。20+21+22+。+2K-1=2K-1例如，在下图所示的二叉树中，有5个叶子结点，有4个度为2的结点，度为0的结点比度为2的结点多一个。性质3 对任意一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4 （1）具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。（2）具有n个结点的完全二叉树的深度为log2n+1。6.6.3 二叉树的存储结构 二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。 由于在二叉树的存储

38、结构中每个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。下图表示二叉链表的存储示意图。6.6.4 二叉树的遍历遍历是二叉树的重要运算。二叉树的遍历是指按一定的次序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法，并用D、L、R分别表示“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”。1前序遍历（DLR）前序遍历是指首先访问根结点，然后遍历左子树，最后遍历右子树；并且，

39、在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树例如，对如图中的二叉树进行前序遍历，则遍历的结果为ABDGCEHIF。2中序遍历（LDR） 中序遍历是指首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图中的二叉树进行中序遍历，则遍历结果为DGBAHEICF。3后序遍历（LRD）后序遍历是指首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。例如，对图中的二叉树进行后序遍历，则遍历结果为GDBHIEFCA。考题（2005_

40、4）1.某二叉树中度为2的结点有18个，则该二叉树中有_1_个叶子结点。答案：19考题（2005_4）（4）一棵二叉树第六层（根结点为第一层）的结点数最多为_个。答案：326.7 查找与排序技术6.7.1 顺序查找顺序查找又称为顺序搜索。顺序查找一般是指在线性表中查找指定的元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较，但都不相等，则表示线性表中没有要查找的元素（即查找失败）。6.7.2 二分法查找二分法查找只适用于顺序存储的有序表，即要求线性表中的元素按元素值的大小排列（递减排

41、列或递增排列）。假设有序线性表是按元素值递增排列的，并设表的长度为n，被查元素为x，则二分法查找过程如下：将x与线性表的中间元素进行比较：若中间元素的值等于x，则说明查成功，查找结束；若x小于中间元素的值，则在线性表的前半部分以相同的方法查找；若x大于中间元素的值，则在线性表的后半部分以相同的方法查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。可以看出，当有序的线性表为顺序存储时才能采用二分查找。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，顺序查找需要比较n次。可见，二分查找的效率要比顺序查找高得多。6.7.3 交换类排序法

42、1冒泡排序法冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序的。冒泡排序法的操作过程如下：首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两元素的大小，若前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。然后，按相反的方向扫描剩下的线性表，在扫描过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下的线性表中的最小者换到了表的最前

43、面。此时，线性表的第一个元素就是最小者，最后一个元素就是最大者。对剩下的元素构成的线性表重复上述过程，直到剩下的元素为空或者在扫描过程中没有交换任何元素，此时，线性表变为有序。 图8.32是冒泡排序法的示意图。图中有下划线的元素表示扫描过程中的第一个和最后一个元素的位置。 从冒泡排序法的操作过程可以看出，对长度为n的线性表，在最坏的情况下需要进行（n-1）+（n-2）+2+1=n（n-1）/2次比较。原序列628131957第1遍（从前往后）261318579（从后往前）126135879第2遍（从前往后）121356789（从后往前）112356789第3遍（从前往后）112356789最后

44、结果1123567898.32冒泡排序示意图2快速排序法 快速排序法是对冒泡排序法的改进，又叫作分区交换排序法。快速排序法的基本思想如下： 从线性表中任意选取一个元素（通常选第一个元素），设为T，将线性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，结果就将线性表分成了两部分（称为两个子表），T处于分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，此时的线性表

45、就变成了有序表。设当前要排序的线性表的下界为low，上界为high，则分割操作的步骤如下：（1）设两个指针i和j分别指向线性表的第一个元素和最后一个元素，即P（i）=low；P（j）=high，并将第一个元素保存在T中。（2）用T与j指向的元素比较，若TP（j），则让j指向前一个元素，再比较；否则将P（j）和P（i）互换位置。（3）用T与i指向的元素比较，若TP（i），则让i指向后一个元素，再比较；否则将P（j）和P（i）互换位置。（4）反复进行（2）和（3）两步操作，直到i和j指向同一个元素，即i=j时，分割结束。i所指向的元素就是T应该放置的位置。下面举例说明快速排序法。设线性表为（33

46、18 22 88 38 14 55 13 47），若选第一个元素33为T，则第一次排序过程如图8.33（a）所示。对线性表进行完一次快速排序后，用同样的方法对分割后的子表进行快速排序，直到各个子表的长度为1为止。排序过程如图8.33（b）所示。6.7.3 插入类排序法1简单插入排序法 简单插入排序法也叫直接插入排序法。插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。 图8.34给出了插入排序的示意图。图中方括号 中为已排好序的元素。 在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n（n-1）/2次比较。2希尔排序法 希尔排序法（Shell Sort）又称缩小增量排序法，它对简单插入排序做了较大的改进。 其方法如下： 将整个无序序列分割成若干小的子序列分别进行简单插入排序。 子序列的分割方法如下： 使相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后