1.1 考点精讲

计算机已经被广泛用于数据处理。所谓数据处理，是指对数据集合中的各元素以各种方式进行操作，包括插入、删除、查找、更改等，也包括对数据元素进行分析。在进行数据处理时，实际需要处理的数据元素一般很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。

算法是一个十分古老的研究课题，然而计算机的出现为这个课题注入了青春和活力，使算法的设计和分析成为计算机学科中最为活跃的研究热点之一。针对实际问题，例如要编制一个高效率的处理程序，那就需要解决如何合理地组织数据，建立合适的数据结构，设计好的算法来提高程序执行的效率这样的问题。

1.1.1 算法

算法（algorithm）是对解题方案的准确而完整的描述。但它不等于程序，也不等于计算方法。通常，程序的编制不可能优于算法的设计。算法是指令的有限序列，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。

1.算法的基本特征

一个算法，一般应具有以下几个基本特征：

1）可行性：算法的可行性，是指算法中指定的操作都可以通过基本运算执行有限的次数后实现。针对实际问题设计算法时必须考虑它的可行性，因为人们总是希望能够达到满意的结果。

2）确定性：算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

3）有穷性：算法的有穷性，是指一个算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。另外，算法的有穷性还应包括合理的执行时间，如果一个算法需要执行很长时间甚至上千年才能终止，就失去了实用价值。

4）拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够，一般来说，当算法拥有足够的情报时，此算法才是有效的，否则，可能无效。

2.算法的基本要素

1）算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下4类：

●算术运算：主要包括加、减、乘、除等运算。

●逻辑运算：主要包括“与”、“或”、“非”等运算。

●关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。

●数据传输：主要包括赋值、输入、输出等操作。

2）算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。

算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

3.算法设计的基本方法

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计方法，在实际应用时，各种方法之间往往存在着一定的联系。

（1）列举法

列举法的基本思想是，针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验哪些是必需的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等求解不定方程的问题，均可采用列举法解决。

其特点是原理比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出一些有用的信息，就可以大大减少列举量。

列举算法虽然是一种比较笨拙而原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、查找、搜索等问题），局部使用列举法却是很有效的。因此，列举算法是计算机算法中的一个基础算法。

（2）归纳法

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后归纳出一般的关系。显然，归纳法比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。

（3）递推法

递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，工程上许多递推关系式实际上是通过对实际问题的分析与归纳得到的。因此，递推关系式通常是归纳的结果。

递推算法在数值计算中是极为常见的。例如，裴波那契数列是采用递推的方法解决问题的。但是，对于数值型的递推算法必须注意数值计算的稳定性问题。

（4）递归

在解决一些复杂问题或问题的规模比较大时，为了降低问题的复杂程序，通常将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是在解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。

递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。递归过程能将一个复杂的问题归纳为若干较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到归结出最简单的问题为止。由此可以看出，递归的基础也是归纳。在实际工程中，许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法设计中占很重要的地位。

（5）减半递推技术

实际问题的复杂程序往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。

所谓“减半”，即将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。例如，一元二次方程的求解，求解过程见下例。

例如，设方程f(x)=0在区间[a，b]上有实根，且f(a)与f(b)异号。利用二分法求该方程在区间[a，b]上的一个实根。

用二分法求方程实根的减半递推过程如下：

首先取给定区间的中点c=(a+b)/2。

然后判断f(c)是否为0.若f(c)=0，则说明c即为所求的根，求解过程结束；如果f(c)≠0，则根据以下原则将原区间减半：

若f(a)f(c)＜0，则取原区间的前半部分；

若f(b)f(c)＜0，则取原区间的后半部分。

最后判断减半后的区间长度是否已经很小：

若|a-b|＜ε，则过程结束，取(a+b)/2为根的近似值；

若|a-b|≥ε，同重复上述的减半过程。

（6）回溯法

前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果，而减半递推技术也是归纳法的一个分支。在工程上，有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能无限地列举。对于这类问题，只能采用“试探”的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换其他路线进行试探。这种方法即称为回溯法。

回溯法在处理复杂数据结构方面有着广泛的应用，如人工智能中的机器人下棋。

4.算法复杂度

算法的复杂度主要分为时间复杂度和空间复杂度。

（1）算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

为了能够比较客观地反映出一个算法的效率，一个算法的工作量不仅与所使用的计算机、程序设计语言以及程序编制者无关，而且还应与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量，而算法所执行的基本运算次数是问题规模的函数，即

算法的工作量=f(n)

其中n是问题规模。例如，两个n阶矩阵相乘所需要的基本运算次数为n3，即计算量为n3，也就是时间复杂度为n3。

另外，在同一问题规模下，若算法执行所需的基本运算次数取决于某一特定的输入数据，则可以用平均性态分析和最坏情况分析两种方法来分析算法的工作量。顾名思义，平均性态分析即输入所有可能的平均值，相应的时间复杂度为算法的平均时间复杂度；最坏情况分析则是以最坏的情况估算算法执行时间的一个上界。一般情况下，后者更为常用。

（2）算法的空间复杂度

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中，除了需要存储数据本身之外，还需要存储链接信息）。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

在许多实际问题中，为了减少算法的内存空间，一般采用压缩存储技术，以便尽量减少不必要的额外空间。

1.1.2 数据结构

数据结构（data structure）是指反映数据元素之间关系的数据元素集合的表示，其作为计算机的一门学科，主要研究和讨论以下3个方面的问题：

1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。

2）各数据元素在计算机中的存储关系，即数据的存储结构。

3）对各种数据结构进行的运算。

讨论以上问题的主要目的是提高数据处理的效率。提高数据处理的效率主要包括两个方面：一是提高数据速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。

1.什么是数据结构

在数据处理领域中，建立数学模型有时并不十分重要，事实上，许多实际问题是无法表示成数学模型的。人们最感兴趣的是知道数据集合中各数据元素之间存在什么关系，应如何组织它们，即如何表示所需要处理的数据元素。

数据的组织方式不同，通常对它进行处理时的效率也不同。例如，在对两个存放了相同元素的表进行查找时，如果一个表中的所有数据元素是没有规律的，而另外一个表中的元素是经过排序的，则对前者进行查找时，只能从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素与被查数都进行了比较且都不相等（即查找失败）为止。而对于后者，由于有序表中的元素是从小到大进行排列的，在查找时可以利用这个特点，使比较次数大大减少。可见数据元素在表中的排列顺序对查找效率是有很大影响的。

要理解数据结构，还需要理解以下基本概念：

●数据（data）是对客观事物的符号表示，是信息的载体，它能够被计算机识别、存储和加工处理。在计算机学科中，数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。

●数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，描述一年四季的季节名：春、夏、秋、冬可以作为季节的数据元素。

●数据对象（data object）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象，数据元素是数据元素类的一个实例。

●数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素的集合。

一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系（即连续），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。例如，在考虑一年四个季节的顺序关系时，“春”是“夏”的前件（即直接前驱，下同），而“夏”是“春”的后件（即直接后继，下同）。同样，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。在考虑家庭成员间的辈分关系时，“父亲”是“儿子”和“女儿”的前件，而“儿子”与“女儿”都是“父亲”的后件。

前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

2.数据的逻辑结构

前面提到，数据结构是指反映数据元素之间关系的数据元素集合的表示。通俗地说，数据结构是指带有结构的数据元素的集合。结构实际上是指数据元素之间的前后件关系。

一个数据结构应包含以下两方面信息：

1）表示数据元素的信息。

2）表示各数据元素之间的前后件关系。

所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。由前面的叙述可以知道，数据的逻辑结构有两个要素：一是用D表示数据元素的集合，二是用R表示数据元素之间的前后件关系。即一个数据结构可以表示为B=(D，R)，其中B表示数据结构。这就是一个二元关系的表示方式。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。

例如，一年四季的数据结构可以表示成

B={D，R}

D={春，夏，秋，冬}

R={(春，夏)，(夏，秋)，(秋，冬)}

例如，家庭成员数据结构可以表示成

B=(D，R)

D=｛父亲，儿子，女儿｝

R=｛(父亲，儿子)，(父亲，女儿)｝

例如，n维向量X=(x1，x2，…，xn)也是一种数据结构，即X={D，R}，

其中数据元素集合为

D={x1，x2，…，xn}

关系为

R={(x1，x2)，(x2，x3)，…，(xn-1，xn)}

3.数据的存储结构

在进行数据处理时，计算机所处理的数据总是存放在计算机的存储空间中，一个数据结构中的各元素在计算机存储空间中的位置关系与逻辑关系有可能是不同的。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等，采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

4.数据结构的图形表示

数据结构除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

例如，一年四季的数据结构可以用如图1-1所示的图形来表示。

又例如，反映家庭成员间辈分关系的数据结构可以用如图1-2所示的图形表示。

显然，用图形方式表示一个数据结构是很方便的，并且也比较直观。

在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。例如，在图1-1所示的数据结构中，元素“春”所在的结点（简称为结点“春”，下同）为根结点，结点“冬”为终端结点；在图1-2所示的数据结构中，结点“父亲”为根结点，结点“儿子”与结点“女儿”均为终端结点。数据结构中除了根结点与终端结点外的其他结点一般称为内部结点。

通常，一个数据结构中的结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。在对数据结构的处理过程中，不仅数据结构中结点（即数据元素）的个数在动态变化，而且，各数据元素之间的关系也有可能在动态变化。例如，一个无序表可以通过排序处理而变成有序表；一个数据结构中的根结点被删除后，它的某一个后件可能变成了根结点；在一个数据结构中的终端结点后插入一个新的结点后，则原来的那个终端结点就不再是终端结点而成为内部结点了。有关数据的基本运算将在后面讲到具体数据结构时再介绍。

5.线性结构与非线性结构

如果一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。一个空的数据结构中插入一个新的元素后，该数据结构就变为非空数据结构；在只有一个数据元素的数据结构中，将该元素删除后，该数据结构就变为空的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构与非线性结构。

如果一个非空的数据结构满足如下两个条件：

1）有且只有一个根结点。

2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称为线性表。

由此可以看出，在线性结构中，各数据元素之间的前后件关系是很简单的。例如，图1-1中一年四季这个数据结构就属于线性结构。

特别需要说明的是，在一个线性结构中插入或删除任何一个结点后还应是线性结构。根据这一点，如果一个数据结构满足上述两个条件，但在此数据结构中插入或删除任何一个就不满足这两个条件时，则该数据结构不能称为线性结构。例如，图1-3的数据结构显然是满足上述两个条件的，但它不属于线性结构，因为在这个数据结构中删除结点A后，就不满足上述的条件1）了。

如果一个数据结构不是线性结构，则称为非线性结构。例如，图1-2中的家庭成员间辈分关系的数据结构不是线性结构，而是非线性结构。显然，在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。

线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是线性结构，还是非线性结构，要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。

1.1.3 线性表

线性表的特点是数据元素之间的关系是线性的，数据元素可以看成是排列在一条线或一个环上。线性表（linear list）是最简单、最常用的一种数据结构。

1.线性表的基本概念

线性表由一组数据元素构成。数据元素的含义很广泛，在不同的情况下，它可以有不同的含义。例如，一个n维向量（x1，x2，…，xn）是一个长度为n的线性表，其中的每一个分量就是一个数据元素。又例如，英文小写字母表（a，b，c，…，z）是一个长度为26的线性表，其中的每一个小写字母就是一个数据元素。再如，一年中的4个季节（春、夏、秋、冬）是一个长度为4的线性表，其中的每一个季节名就是一个数据元素。

数据元素可以是简单项（如上述例子中的数字、字母、季节名等）。在稍微复杂的线性表中，一个数据元素还可以由若干数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性别、年龄、班级5个数据项，如表1-1所示。在这种复杂的线性表中，由若干数据项组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。因此，上述学生情况登记表就是一个文件，其中每一个学生的情况就是一个记录。

表1-1 学生情况登记表

综上所述，线性表是一个线性结构，它是一个含有n（n≥0）个结点的有限序列。对于其中的结点，有且仅有一个根结点，没有前件但有一个后件；有且仅有一个终端结点，没有后件但有一个前件。其他的结点都有且仅有一个前件和一个后件。一般地，一个线性表可以表示成一个线性序列：a1，a2，…，an，其中a1是根结点，an是终端结点。

线性结构的基本特征如下：

1）有且仅有一个根结点，无前件。

2）有且仅有一个终端结点，无后件。

3）除终端结点外，其他所有结点均有且仅有一个后件。

4）除根结点外，其他所有结点均有且仅有一个前件。

由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列称为线性表，其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表（n>0）记作：（a1，a2，…，an）。

2.线性表的顺序存储

在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构具备如下两个基本特征：

1）线性表中的所有元素所占的存储空间是连续的。

2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。如果线性表中各数据元素所占的存储空间（字节数）相等，则要在线性表中查找某一个元素是很方便的。

假设线性表中的第一个数据元素的存储地址（指第一字节的地址，即首地址）为ADR（a1），每个元素需要占用k个存储单元，则线性表中第i个元素ai在计算机存储空间中的存储地址为

ADR(ai)=ADR(a1)+(i-1)×k

即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。一般来说，长度为n的线性表（a1，a2，…，an），设每个数据元素在内存中占4字节，起始元素的存储地址为1010，则该线性表在计算机中的顺序存储结构如图1-4所示。

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。在一般情况下，如果线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时，要考虑到线性表在动态变化过程中可能达到的最大长度。

在线性表的顺序存储结构下，可以对线性表做以下运算：

1）在线性表的指定位置处加入一个新的元素（即线性表的插入）。

2）在线性表中删除指定的元素（即线性表的删除）。

3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）。

4）对线性表中的元素进行排序（即线性表的排序）。

5）将一个线性表分解成多个线性表（即线性表的分解）。

6）将多个线性表合并成一个线性表（即线性表的合并）。

7）复制一个线性表（即线性表的复制）。

8）逆转一个线性表（即线性表的逆转）等。

线性表的基本运算是插入运算和删除运算，下面两小节主要讨论这两种运算。

3.线性表的插入运算

线性表的插入运算是指在表的第i（1≤i≤n+l）个位置上，插入一个新结点x，使长度为n的线性表：

（a1,…,ai－1,ai,…,an）

变成长度为n+1的线性表：（a1…,ai-1,x,a,…,an）

首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。

例如，图1-5a是一个长度为8的线性表，顺序存储在长度为10的存储空间中。现在要求在第2个元素（即18）之前插入一个新元素35。其插入过程如下：

首先从最后一个元素开始直到第2个元素，将其中的每一个元素均依次往后移动一个位置，然后将新元素35插入第2个位置。

插入一个新元素后，线性表的长度变成了9，如图1-5b所示。

如果要再在线性表的第9个元素之前插入一个新元素22，则采用类似的方法：将第9个元素往后移动一个位置，然后将新元素插入第9个位置。插入后，线性表的长度变成了10，如图1-5c所示。

现在，为线性表开辟的存储空间已经满了，不能再插入新的元素了。如果再要插入，则会造成称为“上溢”的错误。

一般来说，设长度为n的线性表为

（a1，…，ai-1，ai，…，an）

现要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表为

（a1′，a2′，…，aj′，aj+1′，…，an′，an+1′）

则插入前后的两线性表中的元素满足如下关系：

在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素，共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入第i项。插入结束后，线性表的长度就增加了1。

下面分析插入算法的时间复杂度。顺序表的插入运算，其时间主要花费在了数据的移动上，在第i个位置插入b，从ai到an都要向后移动一个位置，共需要移动n-i+1个元素，而i的取值范围为1≤i≤n，即有n+1个位置可以插入。假设在第i个位置上做插入操作的概率为pi，则平均移动数据元素的次数为：

设pi=1/(n+1)，即为等概率情况，则

这说明，在顺序表上进行插入操作大约需要移动表中一半的数据元素，显然该算法的时间复杂度为O(n)。

4.线性表的删除运算

线性表的删除运算是指将表的第i（1≤i≤n）个元素从线性表中去掉，删除后使原来长度为n的线性表：

（a1，…，ai－1，ai，…，an）

变成长度为n-1的线性表：（a1，…，ai－1，ai＋1，…，an）

首先举一个例子来说明如何在顺序存储结构的线性表中删除一个元素。

例如，图1-6a为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素（即删除元素26）。其删除过程如下：

从第2个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。此时，线性表的长度变成了7，如图1-6b所示。

如果要再删除线性表的第6个元素，则采用类似的方法：将第7个元素往前移动一个位置。此时，线性表的长度变成了6，如图1-6c所示

一般来说，设长度为n的线性表为

（a1，…，ai－1，ai，…，an）

现要删除表中的第i个元素，删除后得到长度为n-1的线性表为

（a1′，a2′，…，aj′，…，an-1′）

则删除前后的两线性表中的元素满足如下关系：

在一般情况下，在删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。

下面分析删除算法的时间复杂度。与插入运算相同，其时间主要花费在了数据的移动上，当删除第i个位置时，从ai+1到an都要向前移动一个位置，共需要移动n-i个元素，而i的取值范围为1≤i≤n，即有n个位置可以删除。假设在第i个位置上做删除操作的概率为pi，则平均移动数据元素的次数为：

在等概率情况下，pi=1/n，则：

这说明，在顺序表上进行删除操作时大约需要移动表中一半的元素，显然该算法的时间复杂度也是O(n)。

1.1.4 栈和队列

栈和队列是两种特殊的线性结构。从数据结构的角度看，它们是线性表。从操作的角度看，它们是操作受限的线性表。在日常生活中经常会遇到栈或队列的实例，另外栈和队列还广泛应用于各种软件系统中。

1.栈及其基本运算

栈实际上也是线性表，是一种特殊的线性表。这种特殊的线性表的插入与删除运算都只能在表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈。

栈（stack）是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶（top），而不允许插入与删除的另一端称为栈底（bottom），如图1-7所示。当表中没有元素时称为空栈。

假设栈S=（al，a2，a3，…，an），则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…，an的次序进栈，退栈的第一个元素应为栈顶元素。栈顶总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才被删除的元素。即栈是按照“先进后出”（First In Last Out，FILO）或“后进先出”（Last In First Out，LIFO）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。

向栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。栈顶指针top动态反映了栈中元素的变化情况。

栈这种数据结构在日常生活中也是常见的。例如，子弹夹是一种栈结构，最后压入的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。又如，在用羽毛球筒（一端为封闭另一端为开口的容器）装羽毛球时，也是遵循“先进后出”或“后进先出”原则的。

2.栈的顺序存储及其运算

与一般线性表一样，在程序设计语言中，用一维数组作为栈的顺序存储空间。通常，栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）。图1-8a是容量为10的栈顺序存储空间，栈中已有6个元素；图1-8b与图1-8c分别为入栈与退栈后的状态。在栈的顺序存储空间中，bottom通常为栈底元素，top通常为栈顶元素。top=0表示栈空。

栈的操作主要有入栈运算、退栈运算（出栈）和读栈顶元素。

1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针加1（即top加1），然后将新元素插入栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。

2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减1（即top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的“下溢”错误。

3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。

3.什么是队列

在计算机系统中，如果一次只能执行一个程序，则在多个用户程序需要执行时，这些用户程序必须按照到来的顺序进行排队等待。这通常是由计算机操作系统来管理的。

在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：

1）初始时线性表为空。

2）当有用户程序来到时，将该用户程序加入线性表的末尾进行等待。

3）当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。

由这个例子可以看出，在这种线性表中，需要加入的元素总是插入线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。

队列（queue）是指允许在一端插入，而在另一端删除的线性表。允许插入的一端叫做队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端叫做队头（也称为排头），通常也用一个队头指针（front）指向队头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先被删除，反之，最后插入的元素最后才被删除。因此队列又称为“先进先出”（First In First Out，FIFO）或后进后出（Last In Last Out，LILO）的线性表。它体现了“先来先服务”的原则。在队列中，队尾指针rear与队头指针front共同反映了队列中元素动态变化的情况。当队列中没有元素时，称为空队列。图1-9是具有4个元素的队列示意图。

向队列的队尾插入一个元素称为入队运算，从队列的队头删除一个元素称为出队运算。

图1-10是在队列中进行插入与删除的示意图。由图1-10可以看出，在队列的末尾插入一个元素（入队运算）只涉及队尾指针rear的变化，删除队列中的队头元素（出队运算）只涉及队头指针front的变化。

与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。

4.循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图1-11所示。

在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入第一个位置，即将存储空间的第一个位置作为队尾。

在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。因此，从队头指针front指向的后一个位置到队尾指针rear指向的位置之间的所有元素均为队列中的元素。

循环队列的初始状态为空，即rear=front=m，如图1-11所示。

循环队列主要有两种基本运算：入队运算与出队运算。

每进行一次入队运算，队尾指针就进1。当队尾指针rear=m+1时，则置rear=1。

每进行一次出队运算，队头指针就进1。当队头指针front=m+1时，则置front=1。

图1-12a是一个容量为8的循环队列存储空间，且其中已有6个元素。图1-12b是在图1-12a的循环队列中又加入了2个元素后的状态。图1-12c是在图1-12b的循环队列中退出了1个元素后的状态。

由图1-12中循环队列动态变化的过程可以看出，在循环队列中进行出队、入队操作时，头尾指针仍要加1，向前移动。只不过当头尾指针指向向量上界（m）时，其加1操作的结果是指向向量的下界0。

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过front=rear来判断队列是“空”还是“满”。在实际使用循环队列时，为了能区分队列是满还是空，通常还需增加一个标志s，定义如下：当s=0时，表示队列空；当s=1时，表示队列非空。

由此可以得出队列空与队列满的条件如下：

队列空的条件为s=0；

队列满的条件为s=1且front=rear。

下面具体介绍循环队列入队与出队的运算。

假设循环队列的初始状态为空，即s=0，且front=rear=m。

（1）入队运算

入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进1（即rear=rear+1），且当rear=m+l时，置rear=1；然后将新元素插入队尾指针指向的位置。当循环队列非空（s=l），且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。

（2）出队运算

出队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进1（即front=front+1），且当front=m+1时，置front=1；然后将队头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行出队运算，这种情况称为“下溢”。

（3）求队列长度

求队列长度是指求出当前循环队列中存储元素的个数。在循环队列中，存储空间可以重复利用，随着入队和出队运算的操作，队头指针和队尾指针的位置不断变化，可能会出现队尾指针小于队头指针的情况，所以在循环队列中，计算所存储的元素个数分两种情况：

1）当队尾指针大于队头指针时：

队列中的元素个数为（rear-front），如图1-13a所示。

2）当队尾指针小于队头指针时：

队列中的元素个数为（rear-front+m）%m，其中，m为循环队列的容量，如图1-13b所示。

1.1.5 线性链表

前面主要讨论了线性表的顺序存储结构以及在顺序存储结构下的运算。本节主要介绍线性链表的存储方式和基本操作。

1.线性表

线性表的顺序存储结构具有简单、运算方便的优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。但是，线性表的顺序存储结构在某些情况下就不那么方便，运算效率不那么高了。实际上，线性表的顺序存储结构存在以下几方面的缺点：

1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入和删除过程中需要移动大量的数据元素。对于大的线性表，特别是在元素插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。

2）当为一个线性表分配顺序存储空间后，在线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。显然这种情况的出现对运算是很不利的。也就是说，在顺序存储结构下，线性表的存储空间不便于扩充。

3）在实际应用中，往往是同时有多个线性表共享计算机的存储空间。例如，在一个处理中，可能要用到若干线性表（包括栈与队列）。在这种情况下，存储空间的分配将是一个难题。如果将存储空间平均分配给各线性表，则有可能造成有的线性表的空间不够用，而有的线性表的空间根本用不着或用不满，这就使得在有的线性表空间无用而处于空闲的情况下，另外一些线性表的操作由于“上溢”而无法进行。这种情况实际上是计算机的存储空间得不到充分利用。如果多个线性表共享存储空间，对每一个线性表的存储空间进行动态分配，则为了保证每一个线性表的存储空间连续且顺序分配，会导致在对某个线性表进行动态分配存储空间时，必须移动其他线性表中的数据元素。这就是说，线性表的顺序存储结构不便于对存储空间进行动态分配。

由于线性表的顺序存储结构存在以上缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用下面将要介绍的链式存储结构。

2.线性链表

线性表的链式存储结构称为线性链表。

假设数据结构中的每一个数据结构对应于一个存储单元，这种存储单元称为存储结点，简称结点。

线性表的链式存储是用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了适应这种存储结构，计算机存储空间被划分为一个一个小块，每一个小块占若干字节，通常称这些小块为存储结点。

为了存储线性表中的每一个元素并且能正确表示结点间的逻辑关系，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此，将存储空间中的每一个结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件元素，称为指针域。线性表的链式存储中存储一个数据元素的结点结构如图1-14表示，存储线性表中所有数据元素的存储空间结构如图1-15所示。

由此可知，线性表的链式存储结构中，存储元素所需空间比线性表的顺序存储结构所需空间要多，多出的部分即是用来存放后件元素地址的，而线性表的顺序存储结构中只需数据元素的值，不需要存储数据元素后件元素的地址，从而节省存储空间。

在线性链表中，用一个专门的指针HEAD指向线性链表的第一个数据元素的结点（即存储线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。链表通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起，其逻辑结构如图1-16所示。

由于上述链表的每一个结点只有一个链域，所以将这种链表称为单链表（single linked）或线性链表。

下面举一个例子来说明线性链表的存储结构。

设线性表为（a1，a2，a3，a4），其存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图1-17a所示。为了直观地表示该线性链表中各元素之间的前后件关系，还可以用如图1-17b所示的逻辑状态来表示，其中每一个结点上面的数字表示该结点的存储序号（简称结点号）。

一般来说，在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性中第一个结点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。对于线性链表可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。但是由这个指针只能找到后件结点，不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向扫描，这会给某些问题的处理带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。

为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其后件结点。这样的线性链表称为双向链表，其逻辑状态如图1-18所示。

3.带链的栈

栈也是线性表，也可以采用链式存储结构。图1-19是栈在链式存储时的逻辑状态示意图。

在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。由于可利用栈链接了计算机存储空间中的所有空闲结点，因此，当计算机系统或用户程序需要存储结点时，就可以从中取出栈顶结点，如图1-20a所示，当计算机系统或用户释放一个存储结点（该元素从表中删除）时，则要将该结点放回到可利用栈的栈顶，如图1-20b所示。由此可知，计算机中的所有可利用空间都可以以结点为单位链接在可利用栈中。随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈与入栈操作。

4.带链的队列

与栈类似，队列也是线性表，也可以采用链式存储结构。图1-21a是队列在链式存储时的逻辑状态示意图。图1-21b是将新结点p插入队列的示意图。图1-21c是将队头结点p退出队列的示意图。

5.在线性链表中查找指定元素

线性链表的运算包括在线性链表中指定元素结点之前插入元素、在线性链表中删除指定元素、将两个线性链表按要求合并成一个线性链表、将一个线性链表按要求进行分解、逆转线性链表、复制线性链表、线性链表的排序与查找。

在对线性链表进行插入或删除的运算中，首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。

在非空线性链表中，寻找包含指定元素x的前一个结点p的基本方法是：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。

因此，使用这种方法找到的结点p有两种可能：

1）当线性链表中存在包含元素x的结点时，找到的p为第一次遇到的包含元素x的前一个结点序号。

2）当线性链表中不存在包含元素x的结点时，找到的p为线性链表中的最后一个结点序号。

6.线性链表的插入

线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。

为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便于存储该元素的值。新结点可以从可利用栈中取得，然后将存放新元素值的结点链接到线性链表中指定的位置。

假设可利用栈与线性链表如图1-22a所示。现在要在线性链表中包含元素x的结点之前插入一个新元素b。其插入过程如下：

1）从可利用栈取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中），并置结点p的数据域为插入的元素值b。经过这一步后，可利用栈的状态1-22b所示。

2）在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。线性链表如图1-22b所示。

3）最后将结点p插入结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：

①使结点p指向包含元素x的结点（即结点q的后件结点）。

②使结点q的指针域内容改为指向结点p。

这一步的结果如图1-22c所示。此时插入完成。

由线性链表的插入过程可以看出，由于插入的新结点取自可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。

7.线性链表的删除

线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。

为了要在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回可利用栈。

假设可利用栈与线性链表如图1-23a所示。现在要在线性链表中删除包含元素x的结点，其删除过程如下：

1）在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。

2）将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点。

经过上述两步后，线性链表如1-23b所示。

3）将包含元素x的结点p送回可利用栈。经过这一步后，可利用栈的状态如图1-23c所示。此时线性链表的删除完成。

从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，可利用栈用于收集计算机中的所有空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲结点，应将空闲结点送回可利用栈。

8.循环链表的结构及其基本运算

在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中，对空表和第一个结点的处理必须单独考虑，这使得空表与非空表的运算不统一。

因此，可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点（或第一个结点）的地址，就使得整个链表构成一个环，而且没有增加额外的存储空间，满足这样条件的链表叫做循环链表（circular linked list）。

循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：

1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

2）循环链表中最后一个结点的指针域不为空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。

图1-24是循环链表的示意图。其中图1-24a是一个非空的循环链表，图1-24b是一个空的循环链表。在此，空表与非空表是针对线性表中的元素而言的。

在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表的运算统一。

循环链表的插入和删除与线性单链表基本相同。但由循环链表的特点可以看出，在对循环链表进行插入和删除的过程中，实现了空表与非空表的运算统一。

1.1.6 树与二叉树

树（tree）是一种简单的非线性结构。在树中，所有数据元素之间的关系具有明显的层次特性。图1-25为一棵树的示例。由图1-25可以看出，用图形表示的这种数据结构，很像自然界中的树，只不过是一棵倒长的树，因此，这种数据结构就用“树”来命名。

1.树的基本概念

树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：

1）有一个特定的称为根（root）的结点。它只有直接后件，但没有直接前件。

2）除根结点以外的其他结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm－1，每个集合Ti（i=0，1，…，m-l）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。

在树的图形表示中，总是认为在用直线连起来的两端结点中，上端结点是前件，下端结点是后件，这样，表示前后件关系的箭头就可以省略。

在现实世界中，能用树这种数据结构表示的例子很多。例如，图1-26中的树表示了学校行政关系结构；图1-27中的树反映了一本书的层次结构。

由于树具有明显的层次关系，因此，具有层次关系的数据都可以用树这种数据结构来描述。在所有的层次关系中，人们最熟悉的是血缘关系，按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系，因此，在描述树结构时，也经常使用血缘关系中的一些术语。

下面介绍树中的一些基本特征，同时介绍有关树结构的基本术语。

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。例如，在图1-25中，结点A是树的根结点。每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。例如，在图1-25中，结点C、D、E、F、H、I均为叶子结点。

在树结构中，一个结点所拥有的后件个数称为该结点的度。在树中，所有结点中最大的度称为树的度。例如，在图1-25中，根结点A和结点G的度为2，结点B的度为3，叶子结点C、D、E、F、H、I的度为0，在此树中，结点B的度最大为3，所以此树的度为3。

树是一种具有明显层次关系的数据结构。在树结构中，一般按如下原则分层：

根结点在第1层。

同一层上所有结点的所有子结点都在下一层。例如，在图1-25中，根结点A在第1层；结点B、F、G在第2层；结点C、D、E、H、I在第3层。

树的最大层次称为树的深度。例如，图1-25的树的深度为3。

在树中，以某一结点的一个子结点为根构成的树称为该结点的一棵子树。例如，在图1-25中，结点A有3棵子树，它们分别以结点B、F、G为根结点；结点B有3棵子树，它们分别以结点C、D、E为根结点；结点G有2棵子树，它们分别以结点H、I为根结点。在树中，叶子结点没有子树，如结点C、D、E、F、H、I。

若将树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是有序树；否则称为无序树。

2.二叉树的基本性质

二叉树（binary tree）是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构相似，并且，树结构的所有术语都可以用到二叉树上。

二叉树由n（≥0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，如图1-28b所示。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树具有如下两个特点：

1）非空二叉树只有一个根结点，如图1-28a所示。

2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即叶子结点。

性质1：在二叉树的第k层上至多有2k-1（k≥1）个结点。

根据二叉树的特点，这个性质是显然的。

性质2：深度为m的二叉树至多有2m-1个结点。

深度为m的二叉树是指二叉树共有m层。根据性质1，只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即

21-1+22-1+…+2m-1=2m-1

性质3：对于任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。

对这个性质说明如下：

假设二叉树中有n0个叶子结点，n1个度为1的结点，n2个度为2的结点，则二叉树中总的结点数为

n=n0+n1+n2 （1）

由于在二叉树中除了根结点外，其余每一个结点都有唯一的一个分支进入。设二叉树中所有进入分支的总数为m，则二叉树中总的结点数为

n=m+1 （2）

又由于二叉树中这m个进入分支是分别由非叶子结点发出的。其中度为1的每个结点发出1个分支，度为2的每个结点发出2个分支。因此，二叉树中所有度为1与度为2的结点发出的分支总数为n1+2n2。而在二叉树中，总的发出分支数应与总的进入分支数相等，即

m=n1+2n2 （3）

将（3）第代入（2）式有

n=n1+2n2+1 （4）

最后比较（1）式和（4）式有

化简后得

n0=n2+1

即在二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

例如，在图1-28所示的二叉树中，有3个叶子结点，有2个度为2的结点，度为0的结点比度为2的结点多一个。

性质4：具有n个结点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。

这个性质可以由性质2直接得到。

3.满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。例如，图1-29a、图1-29b、图1-29c分别是深度为2、3、4的满二叉树。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。

2）完全二叉树：除最后一层外，每一层上的结点数均达到最大值；最后一层只缺少右边的若干结点，如图1-30a、b所示。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右由自然数进行连续编号，则深度为m，且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1～n的结点一一对应时，称为完全二叉树。也就是说，一棵具有n个结点的深度为k的完全二叉树，它的每一个结点都与深度为k的满二叉树中编号为1～n的结点一一对应。

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其左右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1。

由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

完全二叉树还具有以下两个性质：

性质5：具有n个结点的完全二叉树深度为[log2n]+1或[log2(n+1)]。

性质6：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对于任意结点i（1≤i≤n），有：

1）如果i=1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点[i/2]。

2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。

3）如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1。

根据完全二叉树的这个性质，如果按从上到下，从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。

4.二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。

用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。图1-31为二叉树存储结点示意图

在图1-31中，L(i)为结点i的左指针域，即L(i)为结点i的左子结点的存储地址；R(i)为结点i的右指针域，即R(i)为结点i的右子结点的存储地址；V(i)为数据域。

由于二叉树存储结构中的每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。图1-32a、图1-32b、图1-32c分别表示了一棵二叉树、二叉链表的逻辑状态、二叉链表的物理状态。其中BT称为二叉链表的头指针，用于指向二叉树根结点（即存放二叉树根结点的存储地址）

对于满二叉树与完全二叉树来说，根据完全二叉树的性质6，可以按层次进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。

5.二叉树的遍历

所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。

由于二叉树是一种非线性结构，因此，对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中，当访问到某个结点时，再往下访问可能有两个分支，那么先访问哪一个分支呢？对于二叉树来说，需要访问根结点、左子树上的所有结点、右子树上的所有结点，在这三者中，究竟先访问哪一个？也就是说，遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏地访问到二叉树中的所有结点。

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。下面分别介绍这3种遍历的方法。

（1）前序遍历

前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。

下面是二叉树前序遍历的简单描述。

若二叉树为空，则结束返回。

否则，1）访问根结点；2）前序遍历左子树；3）前序遍历右子树。

在此特别要注意的是，在遍历左右子树时仍然采用前序遍历的方法。例如，对图1-32a中的二叉树进行前序遍历，则遍历的结果（即前序序列）为A、B、D、E、G、C、F、H、I。

（2）中序遍历

中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。

下面是二叉树中序遍历的简单描述。

若二叉树为空，则结束返回。

否则，1）中序遍历左子树；2）访问根结点；3）中序遍历右子树。

在此也要特别注意的是，在遍历左右子树时，仍然采用中序遍历的方法。例如，对图1-32a中的二叉树进行中序遍历，则遍历的结果（即中序序列）为D、B、G、E、A、H、F、I、C。

（3）后序遍历

后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。

下面是二叉树后序遍历的简单描述。

若二叉树为空，则结束返回。

否则，1）后序遍历左子树；2）后序遍历右子树；3）访问根结点。

在此也要特别注意的是，在遍历左右子树时仍然采用后序遍历的方法。例如，对图1-32a中的二叉树进行后序遍历，则遍历的结果（即后序序列）为D、G、E、B、H、I、F、C、A。

1.1.7 查找

查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。

所谓查找，是指在一个给定的数据结构中查找某个指定的元素。在查找的过程中，涉及查找的方法等问题，通常根据不同的数据结构，采用不同的查找方法。

1.顺序查找

顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法为从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到（即查找成功）；若线性表中的所有元素与被查找元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查找元素是线性表中的最后一个元素，或者被查找元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。

由此可以看出，对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找。

1）如果线性表为无序线性表（即表中元素的排列是无序的），则不管是顺序存储结构，还是链式存储结构，都只能用顺序查找。

2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。

2.二分法查找

二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减（即从小到大，但允许相邻元素值相等）排列。

设有序线性表的长度为n，被查元素为x，则对分查找的方法如下。

将x与线性表的中间项进行比较：

●若中间项的值等于x，则说明查到，查找结束。

●若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。

●若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）时为止。显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。

1.1.8 排序

排序也是数据处理的重要内容。它为数据查找操作提供方便，因为排序后的数据在进行查找操作时效率较高。

所谓排序，是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模及对数据处理的要求，可以采用不同的排序方法。在排序技术方面，主要考查插入排序、选择排序、冒泡排序、快速排序和堆排序等方法。

1.简单插入排序

简单插入排序（straight insertion sort）算法的思路是：初始可认为线性表中的第1个元素已排好序，然后将第2个元素到第n个元素依次插入由已排序的元素组成的线性表中。在对第i个元素ai进行插入时，a1、a2、…、ai-1已排序，将元素ai与已经排好序的元素从右向左依次比较，找到ai应插入的位置，将该位置以后直到ai-1各元素顺序后移，空出该位置让ai插入。

例如，使用简单插入排序对312、126、272、226、28、165、123共7个元素按照从小到大排序。简单插入排序的执行过程示意图如图1-33所示。图中画有方框的元素表示刚被插入有序子表中。

在简单插入排序中，每一次比较后最多移掉一个逆序，最坏情况下，需要进行n(n-1)/2次比较。

2.希尔排序

希尔排序法（shell sort）属于插入类排序，但它对简单插入排序做了较大的改进。

希尔排序法的基本思想如下：

将整个无序序列分割成若干小的子序列分别进行插入排序。

子序列的分割方法如下：

将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。

增量序列一般取ht=n/2k（k=1，2，…，[log2n]），其中n为待排序序列的长度。

例如，使用希尔排序对7、19、24、13、31、8、82、18、44、63、5、29共12个元素按照从小到大排序。希尔排序的执行过程示意图如图1-34所示。

在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一趟比较，就有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。

希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏的情况下，希尔排序所需要的比较次数为O(n1.5)。

3.冒泡排序法

冒泡排序法是一种最简单的交换类排序方法，它通过相邻数据元素的交换逐步将线性表变成有序。

冒泡排序法的基本过程如下：

首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，这样就消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后将线性表中的最大者换到了最后，这也是线性表中最大元素应有的位置。

然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将线性表中的最小者换到了最后，这也是线性表中最小元素应有的位置。

对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时线性表已经变为有序。

在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。

假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。

图1-35是冒泡排序的示意图。图中有方框的元素位置表示扫描过程中最后一次发生交换的位置。由图1-35可以看出，整个排序实际上只用了2遍从前往后的扫描和2遍从后往前的扫描就完成。

4.快速排序法

在前面所讨论的冒泡排序法中，由于在扫描过程中只对相邻两个元素进行比较，因此，在互换两个相邻元素时，只能消除一个逆序。如果通过两个（不是相邻的）元素的交换，能够消除线性表中的多个逆序，就会大大加快排序的速度。显然，为了通过一次交换消除多个逆序，就不能像冒泡排序法那样对相邻两个元素进行比较，因为这只能使相邻两个元素交换，从而只能消除一个逆序。下面介绍的快速排序法可以实现通过一次交换而消除多个逆序。

快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称为快速排序法。

快速排序法的基本思想如下：

从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中所有元素均不小于T。

如果对分割后的子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。

由此可知，快速排序法的关键是对线性表进行分割，以及对各分割出的子表进行再分割，这个过程如图1-36所示。

在对线性表或子表进行实际分割时，可以按如下步骤进行：

首先，在表的第一个、中间一个与最后一个元素中选取中间项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。

然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：

1）将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)<T为止，将P(j)移到P(i)的位置上。

2）将i逐渐减小，并逐次比较P(i)与T，直到发现一个P(i)>T为止，将其移到P(j)的位置上。

上述两个操作交替进行，直到指针i与j指向同一个位置(即i=j)为止，此时将T移到P(i)的位置上。

在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。在对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表（实际上只是该子表的第一个元素与最后一个元素的位置）进行分割。这个过程直到栈空为止，此时说明所有子表为空，没有子表再需要分割，排序就完成了。

5.简单选择排序法

选择排序法的基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。

对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。这种排序法的示意图如图1-37所示，图中有方框的元素是刚被选出来的最小元素。

简单选择排序法在最坏情况下需要比较n(n-1)/2次。

6.堆排序法

堆排序是一种树形选择排序。堆的定义如下：

设有n个元素的序列（h1，h2，…，hn），当且仅当满足

（i=1，2，…，n/2）时称为堆。本节只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。

在实际处理中，可以用一维数组来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。

例如，序列（87，75，60，39，46，35，26，18）是一个堆，它所对应的完全二叉树如图1-38所示。

由图1-38可以看出，在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左、右子树的根结点值，因此，堆顶（完全二叉树的根结点）元素必为序列的n个元素中的最大项。

在具体讨论堆排序法之前，先讨论这样一个问题：在一棵具有n个结点的完全二叉树（用一维数组H(1：n)表示）中，假设结点H(m)左右子树均为堆，现在将以H(m)为根结点的子树也调整为堆。这是调整建堆的问题。

例如，假设图1-39a是某完全二叉树的一棵子树，显然，在这棵子树中，根结点49的左、右子树均为堆。现在为了将整个子树调整为堆，首先将根结点49与其左、右子树的根结点值进行比较，此时由于左子树根结点95大于右子树根结点63，且它又大于根结点49，因此，根据堆的条件，应将元素49与95交换，如图1-39b所示。经过这一次交换后，破坏了原来左子树的堆结构，需要对左子树再进行调整，将元素81与49进行交换，调整后的结果如图1-39c所示。

由这个例子可以看出，在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。

有了调整建堆的算法后，就可以将一个无序序列建成为堆。

假设无序序列H(1:n)以完全二叉树表示。从完全二叉树的最后一个非叶子结点（即第n/2个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆，最后就可以得到与该序列对应的堆。

根据堆的定义，可以得到堆排序的方法如下：

1）首先将一个无序序列建成堆。

2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第2）步，直到剩下的子序列为空为止。

堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。

7.各种排序方法的比较

各种排序方法的时间复杂度和空间复杂度比较如表1-2所示。

表1-2 各种排序算法的比较