C语言入门教程全第9章课件

第9章数据结构与算法基础

9.1数据结构与算法概述

9.2

线性表9.3栈和队列

9.4树和二叉树

9.5图9.6排序9.7本章小结第9章数据结构与算法基础9.1数据结构与算法概述9.1数据结构与算法概述

9.1.1数据结构的相关概念 实践证明，要想更有效地使用计算机，仅仅掌握计算机语言而缺乏数据结构和算法的有关知识，是难以处理诸多复杂应用问题的。 早期的计算机主要解决纯数值计算的问题，以此为加工对象的程序设计称为数值型程序设计。其涉及的操作对象比较简单，其一般为整型、实型数据等。9.1数据结构与算法概述 9.1.1数据结构的相关 后来，随着计算机应用领域的不断拓宽，解决非数值计算的问题越来越引起人们的关注。例如，金融管理、文献检索、计算机辅助设计等。这些问题主要集中于对数据集合中的各元素以各种方式进行运算，如插入、更新、删除、查找等。在此涉及的数据类型比较复杂，而且数据元素之间具有各种特定的联系，所以，如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据，就能大大提高计算机处理问题的效率。 后来，随着计算机应用领域的不断拓宽，解决非数值计算的问题 数据结构是一门研究非数值运算的程序设计问题的学科，它包含以下3个方面的内容： （1）数据集合中各数据元素之间的逻辑结构。 （2）对数据进行处理时，各数据元素在计算机中的存储（物理）结构。 （3）对数据的抽象运算。 1．数据（data） 数据是反映客观事物信息符号的集合，也是计算机程序要加工的对象。这个集合中包括客观事物 数据结构是一门研究非数值运算的程序设计问题的学科，它包含 的数值、字符以及能够输入到计算机中并被计算机程序处理的符号。 计算机发展初期，由于计算机主要用于数值计算，数据指的就是数值。随后由于计算机应用的普及，数据的含义也比原来变得更加广泛。如文字、表格、声音、图形、图像等都属于数据的范畴。 2．数据元素（dataelement） 数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据 的数值、字符以及能够输入到计算机中并被计算机程序处理的符号 集合N={1，2，3，4，5}中整数1～5都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位，例如，在老师档案信息管理中的每一位老师就是一个数据元素，组成它的数据项可以是姓名、性别、年龄等。 3．数据对象（dataobject） 数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个 集合N={1，2，3，4，5}中整数1～5都是数据元素。每 数据对象，可表示为集合W={Mon，Tue，Wed，Thu，Fri，Sat，Sun}；再如，字母数据对象可表示为集合C={‘A’，‘B’，…，‘Z’}。 4．数据类型（datatype） 数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。 数据对象，可表示为集合W={Mon，Tue，Wed，T 在C语言中，基本数据类型包括整型、实型等，这些变量的值是不可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。 5．数据结构（datastructure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 可以用集合论的方法定义数据结构如下： 在C语言中，基本数据类型包括整型、实型等，这些变量的值是S=(D,R) D={ai|ai∈ElemSet,i=0,1,2,3,…,n,n≥0} R={<ai-1,ai>|ai-1,ai∈D,2≤i≤n} 数据结构S是一个二元组，其中D是一个数据元素的有限集合，R是定义在关系D上的有限集合，即R是由有限个关系所构成的集合。若n=0时，则D是一个空集。 数据结构分为逻辑结构与物理结构两种。S=(D,R)（1）数据的逻辑结构。数据的逻辑结构就是数据元素间的逻辑关系，它研究的是数据元素及其关系的数学特性，与数据的存储无关，是独立于计算机的。 数据的逻辑结构可概括地分为线性结构和非线性结构两种，如图9.1.1所示。图9.1.1数据的逻辑结构（1）数据的逻辑结构。数据的逻辑结构就 线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除第一个元素以外，其他元素有且仅有一个直接前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。 非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。 线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。 线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，（2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。 在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间（2）数据的物理结构。数据的物理结构又 的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。 下面介绍4种常见的存储结构： 1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中，各节点之间的逻辑关系由存储单元的邻接关系来体现。 的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各 如图9.1.2所示为顺序存储结构，假设每个节点占据长度为l（字母，以下同）的存储空间，这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间。对于这种结构，只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置。在顺序存储结构中存取任意一个元素所需要的时间是相等的。 如图9.1.2所示为顺序存储结构，假设每个节点占据长度为图9.1.2顺序存储结构图9.1.2顺序存储结构2）链式存储结构。顺序存储结构比较适合于线性结构，而非线性结构一般很难用顺序存储结构来实现，所以，通常不用顺序存储结构，而是用链式存储结构来实现非线性结构。 链式存储结构是给节点附加指针字段。在这种存储结构中，节点所占的存储单元分为两部分：一部分是用来存放节点自身的信息，称为数据域；另一部分是用来存放该节点后继节点的存储单元的地址，称为指针域。指针域中可以有一个或者多个指针，用来表示节点的一个或多个后继，也可以用来2）链式存储结构。顺序存储结构比较适合 表示其他节点的地址。在用链式存储结构存储一个非线性结构时，节点中的指针个数可以根据该节点的直接后继个数来设置。 如图9.1.3所示的链式存储结构，在Addr1的存储单元中，既包含了节点a1本身的信息，又包含了它的后继节点a2的存储单元的地址Addr1+3×l，其他节点与此类似。 表示其他节点的地址。在用链式存储结构存储一个非线性结构时，图9.1.3链式存储结构图9.1.3链式存储结构 由此不难看出，链式存储结构可以存储线性结构，也可以存储非线性结构。在链式存储结构中，各个节点在存储空间中的前后位置关系与其逻辑顺序也可以不一致，其存储空间也可以不连续。 3）索引存储结构。在线性结构中，所有节点可以排成一个序列，每个节点在该序列中都有对应的位置值，这个位置值就是节点的索引号。索引存储结构是用节点的索引号来确定节点的存储地址。可用以下两种方法实现索引存储： 由此不难看出，链式存储结构可以存储线性结构，也可以存储非①建立一个附加的索引表，索引表中第i项的值就是第i个节点的存储地址。 ②如果每个节点所占单元数都相等，可用位置值的线性函数的值来指出节点对应的存储地址，即第i个节点di的地址为LOC(di)=(i-1)×l+d，其中l为节点所占单元数，d为开始节点d1对应的存储地址。 4）散列存储结构。散列存储结构是指根据节点的关键字值来确定其存储地址，也称为哈希法。用这种方法进行存储时，每个节点分散地存储在存储①建立一个附加的索引表，索引表中第i 单元中，其查找的效率是很高的，关键问题是怎样选择哈希函数和研究解决冲突的办法。 上述4种存储结构也可以组合起来对数据进行存储映像。同一个逻辑结构可以有多种不同的存储方法，应根据具体情况进行选择。另外，存储结构只是数据结构的一个重要方面，如果逻辑结构相同但存储结构不同，也是不同的数据结构。例如，如果用顺序存储结构存储线性表，则称为顺序表；如果用链式存储结构存储线性表，则称为链表。 单元中，其查找的效率是很高的，关键问题是怎样选择哈希函数和

9.1.2算法评价 在第3章中读者已初步了解了算法的概念、特性等，在前面其他章节的编程举例中还学习了不少给定的算法。而解决同一个问题通常有许多不同的算法。算法评价的目的首先在于从解决同一个问题的不同算法中选择出较为合适的一种，其次在于知道怎样对现有算法进行改进，进而设计出更好的算法。对于算法的评价可以从以下几个方面进行。 9.1.2算法评价1．正确性 正确性（correctness）是设计和评价算法的首要条件，一个正确的算法是指在有合理的数据输入的情况下，能够在有限的运行时间内得出正确的结果。要从理论上证明一个算法的正确性，并不是一件容易的事，所以通常可采用各种典型的输入数据上机调试算法，并使算法中的每段代码都被测试过，若发现错误及时修正，最终可以验证出算法的正确性。 1．正确性 2．健壮性 健壮性（robustness）是指一个算法对不合理（又称不正确、非法、错误等）数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应的处理。对错误数据的处理一般包括打印出错误信息、调用错误处理程序、返回标识错误的特定信息、中止程序运行等。 2．健壮性3．可读性 可读性（readability）是指一个算法供人们阅读和理解的容易程度。一个可读性好的算法，应该符合结构化和模块化程序设计的思想，应该对其中的每个功能模块、重要数据类型或语句加以必要注释；应该建立相应的文档，对整个算法的功能、结构、使用及有关事项进行说明。 4．简单性 简单性（simplicity）是指一个算法所采用数据3．可读性 结构和方法的简单程度。如对数组进行查找时，采用顺序查找的方法比采用二分查找的方法要简单；对数组进行排序时，采用简单选择排序的方法比采用堆排序或快速排序的方法要简单。但最简单的算法往往不是最有效的，即有可能占用较长的运行时间和较多的内存空间。算法的简单性便于用户编写、分析和调试，所以对于处理少量数据的情况是适用的，但若要处理大量的数据，则算法的有效性比简单性更重要。有效性主要表现为时间复杂度和空间复杂度。 结构和方法的简单程度。如对数组进行查找时，采用顺序查找的方5．时间复杂度 时间复杂度（timecomplexity）是指计算机执行一个算法时在时间上的消耗度量。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算。通常人们采用第二种方法，所以这里只介绍事前分析估算方法。 一般情况下，把算法中一条语句重复执行的次数称为此语句的频度，它常表示为问题规模n的某个函数，记作F(n)。而算法的时间复杂度则记作5．时间复杂度T(n)=O(F(n))下面举例说明如何求时间复杂度：for(i=0;i<n;i++){for(j=0;j<n;j++){b[i][j]=0;for(k=0;k<n;k++){T(n)=O(F(n)) b[i][j]=b[i][j]+a[i][k]*a[k][j]; } } } 以执行次数最多的语句（b[i][j]=b[i][j]+a[i][k]*a[k][j];）进行计算： 语句频度：F(n)=n3 时间复杂度：T(n)=O(F(n))=O(n3) 下列程序段的时间复杂度如下： b[i][j]=b[i][j]+（1）x=x+1;T(n)=O(1) （2）for(j=0;j<n;j++) x=x+1;T(n)=O(n) （3）for(j=0;j<n;j++) for(k=0;k<n;k++) x=x+1;T(n)=O(n2) 算法的时间复杂度一般是以数量级的形式给出，常见的时间复杂度如下：（1）x=x+1;（1）O(1)：常量型； （2）O(n)，O(n2)，...，O(nk)：多项式型； （3）O(log2n)，O(2log2n)：对数型； （4）O(2n)，O(en)：指数型。 6．空间复杂度 空间复杂度（spacecomplexity）是指在一个算法的运行过程中，对临时耗费的存储空间的度量，而不包括问题的原始数据占用的空间（因为这些单元与算法无关）。（1）O(1)：常量型； 空间复杂度的表示类似于算法的时间复杂度，可记作 S(n)=O(F(n)) 分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般算法本身较简短，所占用的存储空间较少，但运行时需一个附加堆栈，从而占用较多的临时存储空间；若改成非递归算法，则一般可能算法本身较长，所占用存储空间较多，但运行时可能占用较少的临时存储空间。 空间复杂度的表示类似于算法的时间复杂度，可记作 高效且低内存要求的算法最好，但在算法中的时间与空间往往是相互影响的，要节约空间往往就要消耗较多的时间，反之亦然。目前由于计算机硬件的发展，一般都有足够的内存空间，因此在算法评价中应着重考虑时间因素。 9.1.3算法分类 通常，需要人们解决的特定问题可被分为数值的和非数值的两大类，所以算法通常分为数值算法和非数值算法两类。 高效且低内存要求的算法最好，但在算法中的时间与空间往往是1．数值算法 解决数值问题的算法叫做数值算法。科学和工程计算方面的算法属于数值算法，如求解数值积分、线性方程组、代数方程和微分方程等。 2．非数值算法 解决非数值问题的算法叫做非数值算法。数据处理方面的算法大多属于非数值算法，如在各种数据结构上进行的排序算法、查找算法、插入算法、删除算法、遍历算法等。1．数值算法 数值算法和非数值算法并没有严格的划分，一般说来，在数值算法中主要进行算术运算，而在非数值算法中，则主要进行比较和逻辑运算。 数值算法和非数值算法并没有严格的划分，一般说来，在数值算9.2线性表

9.2.1线性表的定义及其运算 1．线性表的定义 线性表（linear_list）是由n（n≥0）个元素a1，a2，a3，…，an组成的一个有限序列，它有且只有一个开始节点，该节点没有前驱且只有一个后继；有且只有一个终端节点，该节点没有后继且只有一个前驱，其他所有节点都是有且只有一个前驱和一个后继。线性表是最基本、最简单、最常用的数据结构。9.2线性表 9.2.1线性表的定义及其运算 在日常生活中，能够找出很多线性表的例子，例如： （1）人民币面值构成线性表（1角、2角、5角、1元、2元、5元、10元、20元、50元、100元），其中每一种面值为一个数据元素。 （2）一个n维向量x=(x1,x2,x3…,xn)，其中每一个分量为一个数据元素。 （3）一年有4个季节（春、夏、秋、冬），其中每一季节为一个数据元素。 在日常生活中，能够找出很多线性表的例子，例如： 现实中客观存在的实体经过数学抽象后都可以用线性表的形式表示如下： L=(a1,a2,…,an) 其中，L为线性表，ai(i=1,2,…,n)是属于某数据对象的元素，a1为开始节点，an为终端节点，ai-1是ai的前驱，ai是ai-1的后继。n(n≥0)为元素个数，又称为表长，n=0时，为空表。 线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的特征。从上述对线性表的描述可知线性表是一种线性结构。 现实中客观存在的实体经过数学抽象后都可以用线性表的形式表2．线性表的基本运算 线性表是一种非常灵活的数据结构，不仅可对线性表的数据元素进行访问，还可对其进行插入和删除等其他操作。 （1）建立一个空线性表。 （2）判断空表。 （3）求线性表的长度，返回线性表中数据元素的个数。 （4）读取线性表中的某个元素。 2．线性表的基本运算 （5）插入，在线性表的某一个位置插入一个新元素。 （6）删除，删除线性表中的某个元素。 9.2.2线性表的顺序存储结构 1．顺序表 在计算机中可以用不同的方式来表示线性表，其中最简单和最常用的存储方式是用一组地址连续的存储单元来依次存放线性表的数据元素，这种表示称为线性表的顺序存储结构，也称为向量式存储 （5）插入，在线性表的某一个位置插入一个新元素。 结构。如图9.1.2所示的就是顺序存储线性表的存储形式。 假设已知线性表中每个元素占l个单元，且线性表在内存中的首地址为Addr(a1)，则线性表中第i个元素ai的存储地址为 Addr(ai)=Addr(a1)+(i-1)×l （1≤i≤Length(L)） 其中，Length(L)是线性表L的长度，这种存储结构只要确定了存储线性表的起始位置就很容易找到 结构。如图9.1.2所示的就是顺序存储线性表的存储形式。 第i个数据元素，且无论序号i为何值，找到第i个元素所需的时间相同，故这种存储结构也称为随机存储结构。 顺序存储的线性表通常称为顺序表。在高级语言中常用一维数组类型表示顺序表，因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。 第i个数据元素，且无论序号i为何值，找到第i个元素所需的时 顺序表用C语言定义如下： typedefstruct { ElemType*elem; /*elem为顺序表空间的基地址，ElemType表示元素的数据类型*/ intlistsize; /*listsize为顺序表的存储空间容量（字节数）*/ intlength; /*length为顺序表的长度*/ }SqList; 顺序表用C语言定义如下： 顺序表的存储结构具有以下两个基本特点： （1）顺序表中，所有元素所占的存储空间是连续的。 （2）顺序表中，各数据元素在存储空间中是按逻辑顺序依次存放的。 由此看出，在线性表的顺序存储结构中，其逻辑上相邻的两个元素在存储空间中也是相邻的。如果顺序表中各数据元素所占的存储空间相等，则在该顺序表中查找某一个元素是非常方便的。 顺序表的存储结构具有以下两个基本特点：2．顺序表的基本运算 在顺序存储结构中，线性表的某些运算比较容易实现，如求线性表的长度、读线性表中的元素等，下面只重点讨论线性表的插入与删除运算。 （1）插入运算。首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。 如图9.2.1（a）所示，一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2 个元素（即37）之前插入一个新元素55。其插入过2．顺序表的基本运算 程如下： 1）从最后一个元素开始直到第2个位置，每一个元素均依次往后移动一个位置。 2）将新元素55插入到第2个位置。 插入一个新元素后，线性表的长度变成了9，如图9.2.1（b）所示。 如果再要在线性表的第9个元素之前插入一个新元素32，则采用类似的方法：将第9个元素往后移动一个位置，然后将新元素插入到第9个位置。插 程如下： 入后，线性表的长度变成了10，如图9.2.1（c）所示。现在，为线性表开辟的存储空间已经满了，不能再插入新的元素了。如果再要插入，则会造成称为“上溢”的现象。图9.2.1顺序表的插入 入后，线性表的长度变成了10，如图9.2.1（c）所示。现 一般来说，设一个长度为n的线性表为 (a1,a2,…,ai,…,an) 要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表为 (a1,a2,…,ai-1,b,ai,…,an) 一般情况下要在第i（1≤i≤n）个元素前插入一个新元素时，先要从最后一个（即第n个）元素开始，直到第i个元素，之间共n–i+1个元素，依次向后移一个位置；空出第i个位置，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。 一般来说，设一个长度为n的线性表为 显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素之后（可以认为是在第n+1个元素之前）插入新元素，只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。所以，如果插入运算在第i（1≤i≤n）个元素之前进行，则原来第i个元素之后（包括第i个元素）的所有元素都必须向后移动。 显然，在线性表采用顺序存储结构时，如果插入运算在线性表的C语言入门教程全第9章课件【注意】 本章所有算法描述中有一些预定义的常量，其定义如下： #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW-1 typedefintElemType; 【注意】 （2）删除运算。首先举一个例子来说明如何在顺序表中删除一个元素。 如图9.2.2（a）所示，一个长度为8的线性表顺序存储在长度为10的存储空间中，现在要求删除线性表中的第1个元素（即删除元素32）。其删除过程如下： 从第2个元素开始直到最后一个元素，每一个元素均依次往前移动一个位置。此时，线性表的长度变成了7，如图9.2.2（b）所示。如果再要删除线性 （2）删除运算。首先举一个例子来说明如何在顺序表中删除一 表中的第5个元素，则采用类似的方法：将第6和第7个元素依次往前移动一个位置。此时，线性表的长度变成了6，如图9.2.2（c）所示。图9.2.2顺序表的删除 表中的第5个元素，则采用类似的方法：将第6和第7个元素依次 一般来说，设长度为n的线性表为：（a1,a2,…,ai,…,an），现要删除第i个元素，删除后得到长度为n–1的线性表为：（a1,a2,…,ai-1,ai+1,…,an）。一般情况下，要删除第i（1≤i≤n）个元素，则要从第i+1个元素开始，直到第n个元素，之间共有n－i个元素，依次向前移动一个位置。删除结束后，线性表的长度就减小了1。 很显然，在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动表中的元素；如果要删除线性表 一般来说，设长度为n的线性表为：（a1,a2,…,ai, 的第1个元素，则需要移动表中所有的元素。所以如果要删除第i（1≤i≤n）个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。 算法描述如下： 的第1个元素，则需要移动表中所有的元素。所以如果要删除第i3．算法分析 从上面两个算法可看出，顺序表的插入与删除运算，其时间主要花费在移动元素上，而移动元素的个数不仅依赖于表长n，而且还与插入和删除的位置有关。 在平均情况下，要在顺序表中插入或删除一个元素，需要移动表中一半的元素。若表长为n，则两个算法的时间复杂度为O(n)。 3．算法分析 由此看出，当表长n较小时，算法的效率较高，此时顺序存储结构对于较小的线性表或者其中元素不常变动的线性表来说是合适的。但当表长n较大时，算法的效率较低，因此顺序存储结构不适合元素经常需要变动的、较大的线性表。 9.2.3线性表的链式存储结构 线性表顺序存储结构的特点是逻辑上相邻的两个元素在物理位置上也相邻，这个特点使得我们可以随机存取顺序表中任意元素，但是这种存储结构也存在以下不足： 由此看出，当表长n较小时，算法的效率较高，此时顺序存储结（1）在插入或删除元素时需移动大量元素。 （2）在给长度变化较大的线性表预先分配存储空间时，必须按最大空间分配，使存储空间不能得到充分利用。 （3）表的容量难以扩充。 下面介绍线性表的另一种存储结构，即链式存储结构，它克服了顺序表的不足，它不要求在逻辑上相邻的两个元素在物理位置上也必须相邻。链式存储的线性表通常称为链表。下面介绍几种常见的链表。（1）在插入或删除元素时需移动大量元素1．单链表 线性表的链式存储结构不需要一组连续的存储单元，它的数据元素可以分散存放在存储空间中。为了使线性表在逻辑上保持连续，必须在每个元素中存放其后继元素的地址，如图9.2.3（a）所示。这样由n个节点组成的序列便构成一个线性表的链式存储结构，称为链表，如图9.2.3（b）所示。由于这种链表的每个节点中只包含一个指针域，故又称为线性链表或单链表。1．单链表图9.2.3线性表的链式存储结构图9.2.3线性表的链式存储结构 在链式存储结构中，每一个数据元素由两部分组成：一部分存放元素的值，称为数据域；另一部分存放后继元素的存储地址，称为指针域。即节点a的结构为 用data表示数据域，用next表示指针域。其中指示链表中开始节点（第一个节点）地址的指针称为头指针，用“head”表示，最后一个节点的指针为空指针，用“NULL”或符号“∧”表示。 在链式存储结构中，每一个数据元素由两部分组成：一部分存放 有时我们在单链表的第一个节点之前附加一个节点，称为头节点。头节点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，它的指针域存储指向第一个节点的指针，也就是第一个元素节点的存储位置。如图9.2.4（a）所示，单链表的头指针指向头节点。当表空时只有一个头节点，它的指针域为空，如图9.2.4（b）所示。图9.2.4带头节点的单链表 有时我们在单链表的第一个节点之前附加一个节点，称为头节点 由于单链表可用头指针唯一确定，因此在C语言中可用结构指针来描述，其节点类型定义如下： typedefstructLnode /*定义单链表节点类型*/ { ElemTypedata; structLnode*next; }Lnode,*LinkList; 假设L是LinkList型变量，则L为单链表的头指针，指向表中第一个节点。若L为“空”（L=NULL）， 由于单链表可用头指针唯一确定，因此在C语言中可用结构指针 则所表示的线性表为“空”表，其长度n为“0”。在单链表中，任何两个元素的存储位置之间没有必然的联系，不能从线性表的起始位置直接求出某一元素的位置。欲取得某个数据元素必须从头指针出发寻找，因此单链表是非随机存取的存储结构。 2．单链表的基本运算 在讨论单链表的插入、删除运算前，先对一些基本操作进行介绍，插入、删除运算是这些基本操作的组合。设p，q，s均为指针类型变量，它指向 则所表示的线性表为“空”表，其长度n为“0”。在单链表中， 数据域为data，指针域为next的节点，如图9.2.5所示为单链表的几种基本操作。图9.2.5单链表的基本操作 数据域为data，指针域为next的节点，如图9.2.5所（1）插入运算。在顺序表进行元素插入运算时需要移动大量的元素，而在单链表中元素的插入只需要修改有关的指针内容，不需移动元素。在单链表上进行插入运算时指针的变化如图9.2.6所示。图9.2.6单链表上插入节点时指针的变化情况（1）插入运算。在顺序表进行元素插入运 上述指针修改可描述如下： s->next=p->next; p->next=s; 在进行指针的修改时，必须要注意其修改的顺序，假如把上述两条语句顺序颠倒，那么执行结果就完全错误。 在带头节点的单链表的第i个元素之后插入元素x的算法描述如下： ListInsert_L(LinkList*L,inti,ElemTypex) 上述指针修改可描述如下：C语言入门教程全第9章课件（2）删除运算。单链表的删除运算与插入运算一样，在删除时，不需要移动元素，只须修改有关的指针内容。在单链表上进行删除运算时指针的变化如图9.2.7所示。 上述指针修改可描述如下： p->next=p->next->next;图9.2.7单链表上删除节点时指针的变化情况（2）删除运算。单链表的删除运算与插入 在带头节点的单链表中删除第i个元素的算法描述如下： 在带头节点的单链表中删除第i个元素的算法描述如下：3．其他形式的链表 根据实际需要，线性表的链式存储结构还有循环链表和双向链表等其他形式。 （1）循环链表。循环链表是线性表的另一种链式存储结构，它的特点是表中最后一个节点的指针域不为空，而是指向表头，整个链表形成一个环。如图9.2.8（a）、（b）所示分别表示具有头节点的非空循环链表和空循环链表。3．其他形式的链表图9.2.8循环链表 循环链表与一般链表的不同之处在于只要给定循环链表中任一节点的地址，就可以遍历表中所有节点，而不必从头指针开始。这样有可能对某些运算带来方便。 图9.2.8循环链表 循环链表与一般链表的不同之处在于 （2）双向链表。前面讨论的链表都是单向链表，它们只能单方向地寻找表中的节点，若要寻找前驱节点，则需从表头指针出发查找或向后循环一周查找，当表长为n时执行时间为O(n)。为克服其单向性缺点，可采用双向链表。在双向链表的节点中有两个指针域，一个指向直接后继，一个指向直接前驱，如图9.2.9所示。图9.2.9双向链表 （2）双向链表。前面讨论的链表都是单向链表，它们只能单方 双向链表的节点类型定义如下： typedefstructDlnode /*定义双向链表节点 类型*/ { ElemTypedata; structDLnode*left; structDLnode*right; }DLnode,*DLinkList; 双向链表的节点类型定义如下： 此类型包含有3个域：数值域data、左指针域left和右指针域right。left域用于指向其前驱节点，right域用于指向其后继节点。 由于双向链表具有对称性，因此从表中某一给定的节点可随意向前或向后查找。但在执行插入、删除运算时，需同时修改两个方向上的指针。 此类型包含有3个域：数值域data、左指针域left和右 9.2.4线性表的应用 一元多项式相加是线性表的一个典型应用实例。多项式的操作是表处理中经常出现的操作，我们以一元多项式相加为例，说明线性链表在实际中的应用。 一个一元多项式Pn(x)可以表示为 Pn(x)=P0+P1x+P2x2+…+pnxn 该多项式按升幂排列，并由n+1个系数唯一确定，因此可以用一个线性表P表示为 9.2.4线性表的应用 P=(p0，p1，p2，…，pn) 其指数i隐含在系数pi的序号内。 一元多项式的存储结构可以采用顺序存储结构，也可以用链式存储结构，这要取决于执行何种操作。如果只求多项式的值，无须修改多项式的系数和指数，则采用顺序存储结构为宜。但在进行多项式相加时，通常要改变多项式的系数和指数，而且在实际问题中，经常会出现多项式的次数很高但又存在大量的零系数项的情况，例如： P=(p0，p1，p2，…，pn)S(x)=8+2x1050+3x2000 这时如果采用顺序存储结构会浪费大量的存储空间，故一般采用链式存储结构。 用链式存储结构表示多项式是把每一个非零系数项构成链表中的一个节点，节点是由两个数据域和一个指针域构成，如图9.2.10（a）所示。其中，exp(i)表示该项的指数，称为指数域；coef(i)表示该项的系数，称为系数域；next(i)是指向下一个非零系数的节点，称为指针域。整个多项式Pn(x)如图9.2.10（b）所示。S(x)=8+2x1050+3x200图9.2.10一元多项式的链式存储结构 设有一元多项式A(x)和B(x)，现要求其相加结果C(x)=A(x)+B(x)。其运算规则为：将两个多项式中指数相同的项对应系数相加，若和不为零，则构成C(x)中的一项；A(x)和B(x)中所有指数不相同的项均复制到C(x)中。图9.2.10一元多项式的链式存储结构 设有一元多项式 其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个节点，则比较两个节点中的指数项，有下列3种情况： （1）指针qa所指节点的指数值<指针qb所指向节点的指数值，则应摘取qa指针所指节点插入到C(x)链表中去。 （2）指针qa所指节点的指数值>指针qb所指向节点的指数值，则应摘取qb指针所指节点插入到C(x)链表中去。 其运算规则如下：假设指针qa和qb分别指向多项式A和多项 （3）指针qa所指节点的指数值=指针qb所指向节点的指数值，则把两个节点中的系数相加，若和数不为0，则修改qa所指节点的系数值，同时释放qb所指向节点；反之，从多项式A的链表中删除相应节点，并释放指针qa和qb所指节点。 如图9.2.11（a）所示，为带头节点的单链表表示的多项式A5(x)=8-2x+15x5，B8(x)=2x+7x4-9x5+3x8；如图9.2.11（b）所示表示相加后的“和多项式”C(x)。 （3）指针qa所指节点的指数值=指针qb所指向节点的指数图9.2.11用链式存储结构进行多项式求和图9.2.11用链式存储结构进行多项式求和9.3栈和队列

9.3.1栈的定义及其运算 1．栈的定义 栈（stack）又称堆栈，它实际上是一种操作受限的特殊的线性表，是限定仅在表的一端进行插入和删除的线性表。 在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，自然也是最先被删除的元素；栈底元素总是最先被插入的元素，自然也是最后才被9.3栈和队列 9.3.1栈的定义及其运算 被删除的元素。也是说栈是按照“先进后出”（FirstInLastOut，FILO）或者“后进先出”（LastInFirstOut，LIFO）的原则组织数据的，所以，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆功能。 通常用指针top指示栈顶的位置，用指针bottom指向栈底。向栈中插入一个元素（即插入为新的栈顶元素）称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。栈顶指针top动态反 被删除的元素。也是说栈是按照“先进后出”（First图9.3.1栈的示意图 映了栈中元素的变化情况。如图9.3.1所示为栈的示意图。图9.3.1栈的示意图 映了栈中元素的变化情况。如图9. 栈这种结构在日常生活中是很常见的。例如子弹夹就是一种栈的例子，最先压入的子弹总是最后一个被弹出，而最后压入的子弹最先被弹出，这就遵循了“后进先出”或“先进后出”的原则。 2．栈的基本运算 （1）建立一个空栈。 （2）判断空栈。 （3）读栈顶元素。 （4）求栈的长度，返回栈的数据元素个数。 栈这种结构在日常生活中是很常见的。例如子弹夹就是一种栈的 （5）入栈，将元素插入到栈顶。 （6）出栈，删除栈顶元素。

9.3.2栈的存储结构 1．栈的顺序存储结构——顺序栈 实现栈的顺序存储结构最简单的方法是用一维数组来存储。由于栈底不变，而栈顶是随入栈、出栈操作动态变化的，因此必须记住栈顶的位置，并且由于栈是有容量限制的，因此用C语言定义顺序栈的结构如下： （5）入栈，将元素插入到栈顶。#defineStack_NUM100 #defineStack_MORENUM10 typedefstruct { ElemType*bottom; ElemType*top; intstacksize; }SqStack; 其中，stacksize说明栈当前可用的最大容量。#defineStack_NUM1 栈的初始化操作如下：按设定的初始分配量进行第一次存储分配，bottom称为栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值为NULL，则表明栈结构不存在。在程序设计语言中，用一维数组S（1:m）作为栈的顺序存储空间，其中m为栈的最大容量。如图9.3.2（a）所示是容量为10的栈顺序存储空间，栈中已经有6个元素；如图9.3.2（b）和图9.3.2（c）所示分别为入栈与出栈后的状态。 栈的初始化操作如下：按设定的初始分配量进行第一次存储分配图9.3.2顺序栈的插入与删除运算图9.3.2顺序栈的插入与删除运算 在栈的顺序存储空间S（1:m）中，S（bottom）通常为栈底元素（是在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。 在栈上进行操作，都比较容易实现，下面介绍顺序栈的建立、插入和删除的算法。 （1）建立空栈。 Init_StackSq(SqStack*S) { 在栈的顺序存储空间S（1:m）中，S（bottom）通常C语言入门教程全第9章课件C语言入门教程全第9章课件2．栈的链式存储结构——链栈 顺序栈最大的缺点是：必须设置最大容量，但是当栈的容量不固定时，这样可能会造成很多存储空间的浪费，也可能产生上溢。栈的链式存储结构克服了这个缺点，它采用一个链表结构来表示栈，栈顶指针就是链表的头指针，其插入和删除操作仅在表头进行，如图9.3.3所示。图9.3.3链栈示意图2．栈的链式存储结构——链栈图9.3. 链栈节点类型的定义如下： typedefstructSnode { ElemTypedata; /*数据域*/ structSnode*next; /*指针域*/ }Snode,*LinkStack; 假设s是LinkStack型的变量，则s为链栈的头指针。 下面介绍链栈的插入和删除算法。 链栈节点类型的定义如下：C语言入门教程全第9章课件p=*S; /*使栈顶指针指向下一节点*/ *S=p–>next; free(p); /*释放栈顶元素*/ returntemp; }

9.3.3栈的应用 栈最初用于高级语言的编译程序中，如表达式求值、程序的嵌套以及递归调用等，后来在各类回溯求解问题中也得到应用。下面以过程嵌套的实例来说明栈的应用。p=*S; /*使栈顶指针指向下一节 过程（函数）嵌套是程序设计中很重要的应用。当过程调用子过程（自定义函数）时，必须把断点的信息及地址保留起来，当子过程执行完毕返回时，取用这些信息，找到返回地址，由此断点继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出。 如图9.3.4所示给出了具有嵌套调用关系的5个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序。 过程（函数）嵌套是程序设计中很重要的应用。当过程调用子过图9.3.4主程序与子程序之间的调用关系图9.3.4主程序与子程序之间的调用关系 下面来具体介绍计算机系统是如何处理它们之间的调用关系的。其中的关键是要正确处理好执行过程中的调用层次和返回路径，这就需要记忆每一次调用时的返回点。计算机系统用一个栈来动态记忆调用过程中的路径，其基本原则如下： （1）在开始执行程序前，先建立一个栈，其初始状态为空。 （2）当发生调用时，将当前调用的返回点地址（在图9.3.4中用语句标号表示）插入到栈。 下面来具体介绍计算机系统是如何处理它们之间的调用关系的。（3）当遇到从某个子程序返回时，就从栈顶取出返回点地址。 根据以上原则，图9.3.4中5个程序在执行过程中的调用顺序以及栈中元素变化的情况如下： （1）主程序开始执行前，建立一个空栈，即栈的状态为（）。 （2）开始执行主程序MAIN，当执行到CALLSUB1时，调用子程序SUB1，这时，将本次调用的返回点地址A入栈。此时，栈的状态为（A）。（3）当遇到从某个子程序返回时，就从栈（3）开始调用执行子程序SUB1，当执行CALLSUB2时，调用子程序SUB2，这时将本次调用的返回点地址B入栈。此时栈状态为（A，B）。 （4）开始调用执行子程序SUB2，当执行到CALLSUB3时，调用子程序SUB3，这时将本次调用的返回点地址C入栈。此时栈状态为（A，B，C）。 （5）开始调用执行子程序SUB3，当执行到CALLSUB4时，调用子程序SUB4，这时，将本次调用的返回点地址D入栈。此时栈的状态为（A，B，C，D）。（3）开始调用执行子程序SUB1，当执 从上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址入栈，而这种插入操作不需要移动栈中原有元素，并且，各返回点地址在栈中的存放顺序恰好是调用顺序。 （6）开始调用执行子程序SUB4，而SUB4不再调用其他子程序，因此执行完子程序后要返回到子程序SUB3的地址D处。其中返回点地址D从栈顶取出，这时，栈的状态为（A，B，C）。 从上述逐步调用的过程可以看出，每次发生调用时，都需要将当（7）返回到子程序SUB3的D处继续执行，执行完子程序SUB3后要返回到子程序SUB2的地址C处。其中返回点地址C从栈顶取出，这时，栈的状态为（A，B）。 （8）返回到子程序SUB2的C处继续执行，执行完子程序SUB2后要返回到子程序SUB1的地址B处。其中返回点地址B从栈顶取出，这时，栈的状态为（A）。（7）返回到子程序SUB3的D处继续执（9）返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A从栈顶取出。取出A后，栈变为空，即栈的状态为（）。 （10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完毕。 由上述逐步返回的过程可以看出，当子程序返回到上一个调用程序时，需要从栈顶取出返回点地址，即对栈作出栈操作。由于各返回点地址在线性（9）返回到子程序SUB1的B处继续执 表中的存放顺序恰好是对应的调用顺序，因此，每次从栈顶取出的返回点地址正好对应了各次调用的正确返回顺序。 9.3.4队列的定义及其运算 1．队列的定义 队列（equeue）简称队，也是一种操作受限的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。显然，在队列这种数据结构中，最先插入的元素将 表中的存放顺序恰好是对应的调用顺序，因此，每次从栈顶取出的 最先被删除，反之，最后插入的元素将最后才被删除。所以，队列又称为“先进先出”（FirstInFirstOut，FIFO）或者“后进后出”（LastInLastOut，LILO）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与队首指针front共同反映了队列中元素动态变化的情况。如图9.3.5所示是具有5个元素的队列示意图。图9.3.5具有5个元素的队列示意图 最先被删除，反之，最后插入的元素将最后才被删除。所以，队列 向队列的尾部插入一个元素称为入队运算，从队列的头部删除一个元素称为出队运算。 如图9.3.6所示在队列中进行插入与删除的示意图。由图9.3.6可看出，入队运算只涉及尾指针rear的变化，而出队运算只涉及头指针front的变化。图9.3.6队列的插入与删除运算 向队列的尾部插入一个元素称为入队运算，从队列的头部删除一2．队列的基本运算 （1）建立空队列。 （2）判定队列是否为空。 （3）入队，在队尾插入元素。 （4）出队，删除队首元素。 （5）返回队首元素。

9.3.5队列的存储结构 线性表的存储结构同样适用于队列，也可根据不同的应用场合分别采用顺序存储结构和链式存储结构。2．队列的基本运算1．队列的顺序存储结构——顺序队列 在程序设计语言中，一般要用一维数组作为队列的顺序存储空间，同时尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便，我们约定：用队尾指针rear指向队列中的队尾元素，用队首指针front指向头元素的前一个位置。每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。 若对存储队列的数组空间采用动态分配，则顺序队列的结构类型可定义如下：1．队列的顺序存储结构——顺序队列typedefstruct { ElemType*base; /*初始化的动态分配存储空间*/ intfront; /*头指针，若队列不空，则指向队列头元素*/ intrear; /*尾指针，若队列不空，则指向队列尾元素的下一位置*/ }SqQueue;typedefstruct 假设为某队列分配的最大空间为n，则当队尾指针指向数组空间的最后一个位置时，不能再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破坏。然而此时又不适合进行存储再分配扩大数组空间，因为队列的实际可用空间可能并未占满。一个巧妙的方法是采用循环队列。 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图9.3.7所示。在循环队列结构 假设为某队列分配的最大空间为n，则当队尾指针指向数组空间 中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列的初始状态为空，即rear=front=0，如图9.3.7所示。图9.3.7循环队列存储空间示意图 中，当存储空间的最后一个位置已被使用而再要进行入队运算时， 在循环队列中，每进行一次入队的运算，队尾指针就加1，当队尾指针rear=m+1时，置rear=0；每进行一次出队运算，队首指针就加1，当队首指针front=m+1时，置front=0。 下面介绍顺序队列的建立、插入和删除算法。 （1）建立空队列。 Init_Queue(SqQueue*Q) { 在循环队列中，每进行一次入队的运算，队尾指针就加1，当队C语言入门教程全第9章课件2．队列的链式存储结构——链队列 如果应用程序中使用顺序队列，则必须为它设定一个最大的队列长度，但这样往往会造成存储空间的浪费；当无法预先估计所用队列的最大长度时，则宜采用链式存储结构，即链队列，如图9.3.8所示。 链队列的操作即为单链表的插入和删除操作的特殊情况，只是同时需要修改尾指针或头指针，如图9.3.9所示为进行这两种操作时指针变化的情况。2．队列的链式存储结构——链队列图9.3.8链队列示意图图9.3.9链队列操作指针变化情况图9.3.8链队列示意图图9.3.9链队列操作指针变假定链队列的节点类型类似于前面定义的单链表节点类型，定义如下：假定链队列的节点类型类似于前面定义的单C语言入门教程全第9章课件

9.3.6队列的应用 这里从两个方面简述队列在计算机科学领域中的应用：一是解决主机与外部设备之间速度不匹配的问题，二是解决由多用户引起的资源竞争问题。 对于第一个方面，这里以主机和打印机之间速度不匹配的问题为例进行简要说明。主机输出数据给打印机，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，则由于速度不匹配，显然是不行的。所以解决的方法是 9.3.6队列的应用 设置一个打印数据缓冲区，主机把需要打印的数据依次写入到这个缓冲区中，写满后就暂停写入，转去做其他的事情；打印机就从缓冲区中按照先进先出的队列操作原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样做既保证了打印数据的正确性，又提高了主机的效率。由此可见，在打印数据缓冲区中所存储的数据就是一个队列。 设置一个打印数据缓冲区，主机把需要打印的数据依次写入到这个 对于第二个方面，CPU资源的竞争也是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU运行自己的程序，它们分别通过各自终端向操作系统提出占用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用，当相应的程序运行结束或用完规定的时间间隔后，则令其出队，再把CPU分配给新的队首请求的用户使用，这样既满足了每个用户的请求，又使CPU能够正常运行。 对于第二个方面，CPU资源的竞争也是一个典型的例子。在一9.4树和二叉树 树型结构是一种重要的非线性结构，它与线性结构的最大区别在于：在这种结构中，除去根节点外每个节点最多只能和上层的一个节点相关，除叶子节点外每个节点都可以和下层的多个节点相关，节点间存在着明显的分支和层次关系。树型结构在客观世界中广泛存在，例如家族关系中的家谱、各种社会组织机构等，都可以形象地用树型结构表示；在计算机软件技术中，树型结构也得到广泛的应用，例如操作系统中的目录（树型）结构、高级9.4树和二叉树 树型结构是一种重要的非线性结构，它 语言中源程序的语法结构等。本节主要讨论树和二叉树的定义及其存储结构。

9.4.1树的定义及其存储结构 1．树的定义和术语 树（tree）是由n个（n≥0）节点组成的有限集合T，其中有且仅有一个节点称为根节点（root），其余节点可分为m（m≥0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合Ti本身又是一棵树，称为根节点root的子树。当n=0时称为空树。 语言中源程序的语法结构等。本节主要讨论树和二叉树的定义及其 这是一个递归的描述，即在描述树时又用到树本身这个术语。如图9.4.1所示为一棵树，A为根节点，其余节点分为3个不相交的子集T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M}，它们均为根节点A下的3棵子树，而这3棵子树本身也是树。图9.4.1树 这是一个递归的描述，即在描述树时又用到树本身 树型结构中常用的术语有： （1）节点（node）：表示树中的元素。 （2）节点的度（degree）：节点拥有的子树数，如图9.4.1中节点D的度为3，C的度为1。一棵树中最大的节点度数为这棵树的度，如图9.4.1所示的树的度为3。 （3）叶子（leaf）：度为零节点，又称端节点。 （4）孩子（child）：除根节点外，每个节点都是其前驱节点的孩子。 树型结构中常用的术语有： （5）双亲（parents）：对应上述孩子节点的上层节点称为这些节点的双亲。 （6）兄弟（sibling）：同一双亲的孩子。 （7）节点的层次（level）：从根节点开始算起，根为第一层，根的直接后继节点为第二层，其余各层以此类推。例如图9.4.1中的节点K，L和M都在第4层。 （8）深度（depth）：树中节点的最大层次数。如图9.4.1中树的深度为4。 （5）双亲（parents）：对应上述孩子节点的上层节点（9）森林（forest）：是m（m≥0）棵互不相交的树的集合。 （10）有序树、无序树：树中节点在同层中按从左至右有序排列、不能互换的称为有序树，并把各子树分别称为第一子树，第二子树……反之称为无序树。 2．树的存储结构 树的存储结构根据应用可以有多种形式，如常见的顺序存储和链式存储结构等，但由于树是非线（9）森林（forest）：是m（m≥ 性结构，因此常采用链式存储结构来表示树，在这里我们只介绍链式存储结构。因为树是多分支非线性表，所以需要采用多重链表结构，即每个节点设有多个指针域，其中每一个指针指向一棵子树的根节点。对于每一个节点的结构类型可以有两种形式：一种是节点异构型，它根据每个节点的子树数设置相应的指针域，由于树中每个节点的度数不尽相同，因此一棵树中各节点的结构形式也不同。这种结构形式虽能节省存储空间，但不方便运算；另一种是采用同构型，即每个节点的指针域个数均为 性结构，因此常采用链式存储结构来表示树，在这里我们只介绍链 树的度数，这种形式运算方便，但会使链表中出现很多空链域，浪费空间，如图9.4.2所示。 假设有一棵具有n个节点的k叉树，则有nk个指针域，其中有用的指针域为n–1个，这时的空链域个数为nk–(n–1)=n(k–1)+1个。图9.4.2树的链式存储结构 树的度数，这种形式运算方便，但会使链表中出现很多空链域，浪 由此可见，k越大则空链域所占比例也越高，其中k=2时空链域的比例最低，这就是我们下面要着重讨论的二叉树结构。 9.4.2二叉树 1．二叉树的定义 二叉树（binarytree）是n（n≥0）个节点的有限集合，它或为空树（n=0），或由一个根节点和两棵互不相交的分别称为这个根的左子树和右子树的二叉树构成。 由此可见，k越大则空链域所占比例也越高，其中k=2时空链 可以看出，和树的定义一样，二叉树也是递归定义的。应该引起注意的是，二叉树的节点的子树有明确的左、右之分。 2．几种特殊形式的二叉树 （1）满二叉树。深度为h且含有2h–1个节点的二叉树称为满二叉树。如图9.4.3所示为一棵深度为4的满二叉树，其节点的编号为自上至下，自左至右，共有24－1=15个节点。 可以看出，和树的定义一样，二叉树也是递归定义的。应该引起图9.4.3满二叉树图9.4.3满二叉树（2）完全二叉树。如果一棵有n个节点的二叉树，按与满二叉树相同的编号方式对节点进行编号，若树中n个节点和满二叉树1～n编号完全一致，则称该树为完全二叉树，如图9.4.4（a）所示。如图9.4.4（b）所示的就不是完全二叉树。图9.4.4完全二叉树与非完全二叉树（2）完全二叉树。如果一棵有n个节点的 完全二叉树具有以下特点： 1）叶子节点只在层次最大的两层出现。 2）其中任一节点，如果其左子树深度为k，则其右子树的深度为k或k–1。 （3）平衡二叉树。平衡二叉树又称AVL树，它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树， 而且左子树和右子树的深度之差的绝对值不超过1。节点的左子树深度减去它的右子树深度定义为节点的平衡因 完全二叉树具有以下特点： 子，所以，平衡二叉树上所有节点的平衡因子只可能是–1，0和1。只要二叉树上有一个节点的平衡因子绝对值大于1，则该二叉树就是不平衡的。如图9.4.5（a）所示为平衡二叉树，如图9.4.5（b）所示为不平衡二叉树。图9.4.5平衡二叉树与不平衡二叉树 子，所以，平衡二叉树上所有节点的平衡因子只可能是–1，0和3．二叉树的基本性质 性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。可用数学归纳法予以证明。 性质2：深度为h的二叉树中至多含有2h－1个节点。利用性质1的结论可推导得出。 性质3：在任意二叉树中，若有n0个叶子节点，n2个度为2的节点，则必有n0=n2+1。 性质4：具有n个节点的完全二叉树的深度为log2n+1或log2(n+1)。3．二叉树的基本性质 性质5：如果对一棵有n个节点的完全二叉树（深度为log2n+1）的节点编号，从根节点开始，自上而下，自左而右，则对任一节点i(1≤i≤n)有 （1）如果i=l，则节点i是二叉树的根，无双亲；如果i>1，则其双亲是节点i/2。 （2）如果2i>n，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i。 （3）如果2i+1>n，则节点i无右孩子；否则其右孩子是节点2i+1。 性质5：如果对一棵有n个节点的完全二叉树（深度为log【注意】 符号x表示不大于x的最大整数，反之，x表示不小于x的最小整数。 4．二叉树的存储结构 二叉树的存储结构有顺序存储结构和链式存储结构两种。 （1）顺序存储结构。顺序存储结构是将二叉树的所有节点，按照一定的顺序方式，存储到一段连续的存储单元中。节点的顺序反映出节点之间的逻辑关系。 【注意】 对于满二叉树或完全二叉树，可用顺序存储结构将n个节点按自上而下、自左至右的顺序依次存放在一段地址连续的存储单元中，即按层存放。如用C语言定义一个完全二叉树为 anytypeb[n]; 为处理方便，我们定义数组长度为n+1，不用b[0]，只用b[1]～b[n]。 一般的二叉树虽然也可以按完全二叉树的形式来存储，但会造成存储空间的浪费。 对于满二叉树或完全二叉树，可用顺序存储结构将n个节点按自 （2）链式存储结构。二叉树通常都采用链式存储。在这种存储方式下，二叉树的每个节点由数据域（data）、左指针域（Lchild）和右指针域（Rchild）组成，即 链式存储不要求各个节点的存储空间连续，二叉树的这种存储结构也称为二叉链表，如图9.4.6（a）所示二叉树的二叉链表如图9.4.6（b）所示。 （2）链式存储结构。二叉树通常都采用链式存储。在这种存储图9.4.6二叉树图9.4.6二叉树二叉链表节点描述如下：typedefintdatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}BTnode;BTnode*root;二叉链表节点描述如下： 其中，root是指向根节点的头指针，当二叉树为空时，root＝NULL。当节点某个孩子不存在时，相应的指针为空。 5．一般树转换为二叉树 为了使一般树也能像二叉树一样用二叉链表表示，必须找出树与二叉树间的对应关系。这样当给定一棵树时，可找到唯一的一棵二叉树与之对应，而且这种关系的逆变换也是存在的。在这里只介绍变换的方法，对于变换过程的唯一性不作证明。 其中，root是指向根节点的头指针，当二叉树为空时，ro 将一般树转换为二叉树的步骤如下： （1）在兄弟节点之间加一连线。 （2）对每个节点，除了保留与其左孩子的连线外，去除与其他孩子间的连线。 （3）以树根为轴心，将整棵树顺时针旋转45º。 如图9.4.7（a），（b），（c）所示为一般树转换为二叉树的过程。 将一般树转换为二叉树的步骤如下：图9.4.7一般树转换为二叉树图9.4.7一般树转换为二叉树 由转换结果可以看出，任何一棵树转换成二叉树，其右子树必为空。

9.4.3二叉树的遍历 遍历（traversing）是指按照某条搜索路线，依次访问某数据结构中的全部节点，而且每个节点只被访问一次。对于线性结构来说，遍历很容易实现，只需顺序访问每个节点即可；但是对于非线性结构来说，则要人为设定搜索的路径，路径即连接两个节点的边的集合。 由转换结果可以看出，任何一棵树转换成二叉树，其右子树必为 遍历是二叉树中最重要的运算。按照搜索路径的不同，二叉树的遍历分为深度优先遍历和广度优先遍历两种方式。 1．深度优先遍历 一棵非空二叉树是由根节点、左子树和右子树3个基本部分组成的，深度优先遍历二叉树就是依次遍历这3部分。若我们以D，L，R分别表示访问根节点、遍历左子树和遍历右子树，则按顺序排列可以有DLR，LDR，LRD，DRL，RDL和RLD6种遍历形式。 遍历是二叉树中最重要的运算。按照搜索路径的不同，二叉树 若规定先左后右，那么上述6种形式可以归并成下述3种形式： DLR：先序遍历； LDR：中序遍历； LRD：后序遍历。 由于二叉树是递归定义，因此用递归方式描述二叉树的深度优先遍历较清楚。如先序遍历可定义为：若二叉树为空，则为空操作，否则先访问根节点，然后先序遍历左子树，再先序遍历右子树。这 若规定先左后右，那么上述6种形式可以归并成下述3种形 里在遍历左、右子树时递归应用先序遍历的定义。对于中序、后序遍历的定义与此类似，不再赘述。 由上述遍历的定义可知，用不同的遍历方式对同一棵二叉树进行遍历，可以得到不同的节点序列。以如图9.4.8所示的二叉树为例，分别用3种遍历方式遍历的结果如下：图9.4.8遍历二叉树 里在遍历左、右子树时递归应用先序遍历的定义。对于中序、后序