7.2 数据结构与算法

 

7.2  数据结构与算法

对于程序设计而言，无论是系统软件开发还是应用软件开发，其核心就是数据结构及其算法。简单地说，一个数据结构就是一类数据的表示及其相关操作。在编写程序时，选择不同的数据结构可能会产生很大的差异。本节将循序渐进地介绍算法、数据结构的基本概念以及常用的数据结构及算法。

7.2.1  算法及复杂度

1．算法

程序设计的本质在N·沃恩的“算法+数据结构=程序”的公式中被揭示了出来，该公式指出了计算机程序设计的双重特性：一个程序由描述如何用计算机处理信息的算法与在计算机中怎样组织信息的数据结构组成。算法与数据结构是相互依赖、相互联系、相互影响的。

所谓算法是指解题方案的准确而完整的描述。算法是指令的有限序列，每一条指令表示一个或多个操作，计算机解题的过程就是在实施某种算法。

很多时候，程序设计者所面临的问题就是寻找一个合适的算法。对他而言，计算机语言的编程规则已经清楚，他所面对的核心问题是寻找一种可以解决问题的算法。

作为算法一般具有以下几个基本特征。

（1）可行性（effectiveness）：针对实际问题而设计的算法，执行后能够得到满意的结果。

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

（3）有穷性（finiteness）：算法必须在有限时间内做完，即算法必须能在执行有限个步骤之后终止。当然有穷性是指在合理的范围之内，比如设计了一个算法是有限的，但按照目前计算机的水平要计算1000年才能完成，这样的情况可以视为无穷。

（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报，当算法拥有足够的情报时，此算法才有效；而当提供的情报不够时，算法可能无效。一般要求一个算法可以有零个或多个输入，但要有输出结果，没有输出的算法是没有意义的。

而算法的基本要素由以下两要素组成：

（1）对数据对象的运算和操作。

一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。

在计算机系统中，基本的运算和操作有以下4类。

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

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

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

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

（2）算法的控制结构。

算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构反映了算法的基本框架。通常一个算法可以用顺序、选择、循环3种基本控制结构组合而成，而算法的描述工具一般采用传统流程图、N-S结构化流程图、算法描述语言等。

下面介绍几种工程上常用的算法设计方法，在实际应用中，这些方法可以相互渗透。

① 列举法。

该法的基本思路是：针对问题，先将所有的可能情况列举出来，再用条件检验哪些是符合的，哪些是不符合的。

在实际应用中要注意当列举的情况较多时，会大大增加算法的工作量，因此，如何使算法优化是一个重点问题。

② 归纳法。

该法的基本思路是：通过对少量具有代表性的情况进行分析，总结出一条通用性较强的式子。   

③ 递推法。

该法的基本思路是：从已知的初始条件出发，逐次推出所要求的各个中间结果和最终结果。递推本质上也属于归纳法。

④ 递归法。

该法的基本思路是：将一些复杂问题逐层分解，最后归结为一些最简单的问题，当解决了那些最简单的问题后，再沿着原来分解的逆过程逐步“返回”，返回到“出发点”后才求得结果。例如求解5!，可以将问题分解为5*4！，而4!继续分解为4*3!，……，依次下去，一直分解为求1!，当解出1!后，就“原路返回”，求解2!、3!、4!，最终求得5!的结果。

⑤ 减半递推法。

所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

⑥ 回溯法。

该法的基本思路是：针对一些具有复杂数据结构的问题，很难用前面的方法解决，这种情况下只有采用“试”的方法。对问题进行分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。

在进行算法的设计时，如何衡量一个算法的好坏呢？通常一个好的算法应达到如下目标：

（1）正确性（correctness）。

正确性可分为以下几个方面；

① 程序不含逻辑错误。

② 程序对于不同的几组输入数据都能够得到符合要求的结果。

③ 程序对于精心选择的典型、苛刻的几组输入数据都能得到符合要求的结果。

（2）可读性（readability）。

算法的可读性好有助于用户对算法的理解，便于交流，否则往往难以调试和修改。

（3）健壮性（robustness）。

健壮性指算法具有抵御“恶劣”输入信息的能力。当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。

（4）高效率与低存储量的需求。

高效率和低存储量是优秀程序员追求的目标。效率指的是算法执行时间，存储量需求指算法执行过程中所需要的最大存储空间。存储量最小、运算时间最少的算法显然是最好的算法。但在实际工作中，效率和存储量需求往往是一对矛盾，需要我们根据实际问题尽量找到一个比较好的平衡点。

在程序设计时，对算法进行分析是十分重要的，因为对于一个具体的应用实例，通常可能有若干个算法可以选用，而所选用算法的质量优劣将影响到算法乃至程序的效率。因此进行算法分析的目的在于选择合适算法并改进算法。一个算法的评价主要从时间复杂度和空间复杂度两方面来考虑。下面我们就来了解一下算法的复杂度。

2．复杂度

（1）算法的时间复杂度。

一个算法执行所耗费的时间，只有通过上机运行测试才能知道，但我们不可能也没有必要对每个算法都进行上机测试，我们只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

一个算法花费的时间与算法在执行过程中所需基本运算的执行次数成正比。一个算法所执行的基本运算次数称为时间频度，记为T(n)，n表示问题的规模。当n不断变化时，时间频度T(n)也会不断变化。为了了解T(n)的规律，我们引入算法的时间复杂度的概念。

算法的时间复杂度，是指执行算法所需要的计算工作量，它是问题规模的函数。假设有某个辅助函数f(n)，当n趋近于无穷大时，使得T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记为T(n)=O(f(n))，O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。另外要注意的情况是，虽然时间频度不相同，但时间复杂度有可能相同，如T(n)=n²+3n+4与T(n)=4n²+2n+1的频度不同，但时间复杂度相同，都为O(n²)。按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log₂n)，线性阶O(n），线性对数阶O(nlog₂n)，平方阶O(n²)，立方阶O(n³)，……，k次方阶O(n^k)，指数阶O(2ⁿ)。显然，时间复杂度为指数阶0(2ⁿ)的算法效率极低，当n值稍大时就无法应用。

在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。这时通常用以下两种方法来分析算法的工作量。

·    平均性态（Average Behavior）

平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设x是所有可能输入中的某个特定输入，p(x)是x出现的概率（即输入为x的概率），t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为A(n)=

，其中D_n表示当规模为n时，算法执行的所有可能输入的集合。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

·    最坏情况复杂性（Worst-case Complexity）

最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

（2）算法的空间复杂度。

算法的空间复杂度是指执行这个算法所需要的内存空间，它也是问题规模n的函数。类似于时间复杂度，将渐近空间复杂度也简称为空间复杂度，记作：S(n)=O(f(n))。

算法的时间复杂度和空间复杂度合称为算法的复杂度。

7.2.2  数据结构的概念

数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。

一般在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。例如表示月份的“一月、二月、三月、……十二月”这十二个名称可以作为月份的数据元素，而且相互之间具有顺序关系：一月是二月的前件，二月是一月的后件；二月是三月的前件，三月是二月的后件，……。再例如求学的经历“幼儿园、小学、中学、大学”可以作为求学过程的数据元素，而其中每个元素之间也存在顺序关系：幼儿园是小学的前件，小学是幼儿园的后件；小学是中学的前件，中学是小学的后件，……。

前后件关系是数据元素之间的一个基本关系，一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面。

1．数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系。

数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

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

（1）数据元素的集合，通常记为D。

（2）各数据元素之间的前后件关系，通常记为R，也就是D上的关系。

这样可以将数据结构的形式定义为一个二元组：B=(D，R)，B表示数据结构。

例如求学经历的数据结构可以表示成：

B=（D，R）

D={幼儿园，小学，中学，大学}

R={（幼儿园，小学），（小学，中学），（中学，大学）}

例如某蛋糕房的供货关系可以表示成：

B=（D，R）

D={樱桃蛋糕房，白果园超市，水木小学，万和小区}

R={（樱桃蛋糕房，白果园超市），（樱桃蛋糕房，水木小学），（樱桃蛋糕房，万和小区）}

2．数据的存储结构

数据的存储结构是指数据元素及其关系在汁算机存储器内的表示。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。常用的存储结构有顺序、链接、索引等。

3．数据的运算

数据的运算即对数据施加的操作。

数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的插入、删除、查找、分类、合并、分解、复制和修改等运算。

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

在数据结构的图形表示中，数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称为结点；对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。图7-1分别表示了求学经历和蛋糕房供货关系的数据结构。

在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称为叶子结点）。例如上图中，“幼儿园”、“樱桃蛋糕房”是根结点；“大学”、“白果园超市”、“水木小学”、“万和小区”是终端结点。其他结点一般称为内部结点。

一般根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。插入与删除是对数据结构的两种基本运算。

（a）求学经历数据结构的图形表示

（b）蛋糕房供货关系数据结构的图形表示

图7-1  数据结构的图形表示

在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型。

（1）线性结构。

若结构满足以下两个条件：一、有且仅有一个根结点和一个终端结点；二、所有结点都最多只有一个直接前件和一个直接后件，则这样的结构就称为线性结构，线性结构中的元素之间存在一对一的关系。

要说明的是，在一个线性结构中插入或删除任何一个结点后仍然是线性结构。所以图7-2所示的结构虽然满足两个基本条件，但是如果删除A结点后，就不满足基本条件了，所以它不属于线性结构。

图7-2  不属于线性结构的一种情况

线性表是一个典型的线性结构。栈、队列、串等都是线性结构。

（2）非线性结构。

非线性结构的逻辑特征是：一个结点可能有多个直接前件和直接后件。所以如果一个数据结构不是线性结构，就是非线性结构。数组、广义表、树和图等数据结构都是非线性结构。

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

7.2.3  常见的数据结构及其基本运算

1．线性表及线性表的顺序存储结构

（1）线性表的基本概念。

线性表（Linear List）是常见数据结构中最简单、最常用的数据结构，它是由若干个数据元素组成的有限序列。例如，26个英文字母组成的字母表：

（A,B,C,D,…,Y,Z）

就是一个线性表。又如，每个星期的七天常用缩写：

（Sun,Mon,Tue,Wed,Thu,Fri,Sat）

来表示。再如，某个学期的课程情况，如表7-1所示。

表7-1  某个学期的课程情况

表7-1也是一个线性表。线性表中的数据元素在不同情况下是不同的，有时仅仅是单个的字母、数字、单词等，如上述前两个例子，但数据元素也可以是复杂的或具有结构的，即数据元素可以由若干个数据项（Item）所组成，如上述第三个例子。

作为一般情况，可将线性表记为：

（a₁, a₂, …, a_i-1, a_i , a_i+1, …, a_n-1, a_n）

线性表中的各个数据元素也常常称为结点，它们必须具有相同的特性，各个结点之间具有固定的先后关系。通常，将a₁称为线性表的表头（根结点），a_n称为线性表的表尾（终端结点），n（线性表中数据元素的个数）称为线性表的长度（当n=0时称为空表）。在线性表中，a_i-1,称为a_i的直接前驱（也常叫做前件），a_i+1称为a_i的直接后继（也常叫做后件）。

所以，非空线性表具有如下特性：

①有且只有一个根结点，它无直接前驱。

②有且只有一个终端结点，它无直接后继。

③除根结点和终端结点外，其他所有结点都有且只有一个直接前驱和直接后继。

（2）线性表的顺序存储结构。

线性表在存储时通常采用两种存储方法：顺序存储和链式存储。通常将线性表的顺序存储结构称为顺序表。线性表在进行顺序存储时，需要一整块连续的存储区域，假设线性表的每个数据元素需要占用k个存储单元，则该存储区域的大小必须大于（或等于）k′n，线性表的各个数据元素在该区域中按照先后顺序依次连续存储，使得逻辑上相邻的元素在存储位置上也相邻。

假设线性表的第一个元素的存储位置为ADR（a₁）、第i个元素的存储位置为ADR(a_i)、第i+1个元素的存储位置为ADR(a_i+1)，则存在如下关系：

ADR(a_i) = ADR(a₁) + k(i-1)

ADR(a_i+1) = ADR(a_i) + k

所以，该线性表在存储器中的存储情况如图7-3所示。

图7-3  线性表的顺序存储结构

在各种程序设计语言中，一维数组就是使用连续的存储空间来存储数组数据的，所以线性表的顺序存储结构对应了一维数组，这样也给程序设计语言处理线性表带来方便。

线性表的顺序存储结构具有简单、运算方便的特点，常用于小型线性表或长度变化不大且插入删除操作相对较少的线性表。

线性表的顺序存储结构在实际应用中也存在如下所述的缺陷：

①如果要在顺序存储的线性表中插入或者删除一个数据元素，为了保持“逻辑上相邻的元素在存储位置上也相邻”的特点，就需要对某些元素进行移动，对于较大的线性表并且插入删除操作比较频繁情况下，会大大降低运行效率。

②在顺序存储的线性表中插入一个数据元素时，如果分配给该线性表的存储空间已满，就会发生“溢出”错误。这时首先需要对存储空间进行扩展或重新分配，这将给系统操作带来麻烦。

③在实际的应用系统中，常常有若干个线性表共同占用计算机的数据存储空间，而现实中往往无法预知各个线性表所需要的最大存储空间，如何有效地进行顺序存储的线性表的存储空间分配，做到既能保证各个线性表的正常需求，又能有效利用有限的存储空间，并且最大限度地提高程序的运行效率，是操作系统中存储分配策略的一个难题。

（3）顺序表的插入运算。

顺序表的插入运算是在顺序表的第i个位置上插入一个新元素，以构成一个新的顺序表。整个操作过程如图7-4所示。

图7-4  顺序表的插入运算

由于插入位置i=3，所以要从最后一个元素开始直到第3个元素都依次向后移动一个位置，然后在第3个位置插入新元素，插入操作使顺序表的长度由原来的n变为n+1。

就插入操作的一般情况而言，如果插入位置位于表头（i=1），则需要移动所有的数据元素（移动元素的操作次数为n），如果插入位置位于表尾（i=n），则不需要移动数据元素（移动元素的操作次数为0），在平均情况下（假设为等概率），需要移动表中的一半元素（移动元素的操作次数为n/2）。

（4）顺序表的删除运算。

顺序表的删除运算是删除顺序表的第i个位置上的元素，以构成一个新的顺序表。整个操作过程如图7-5所示。

图7-5  顺序表的删除运算

由于删除位置i=3，所以要从第4个位置开始直到最后一个位置，将各个元素都依次向前移动一个位置，被删除位置的元素被覆盖，其余元素的相对位置保持不变，删除操作使顺序表的长度由原来的n变为n-1。

就删除操作的一般情况而言，如果删除位置位于表头（i=1），则需要移动所有剩余数据元素（移动元素的操作次数为n-1），如果删除位置位于表尾（i=n），则不需要移动数据元素（移动元素的操作次数为0），在平均情况下（假设为等概率），需要移动表中的约一半元素（移动元素的操作次数为(n-1)/2）。

2．栈和队列

（1）栈的基本概念。

栈（stack）是限定在一端进行插入与删除的线性表。有时也将栈称为堆栈，它是一种特殊的线性表，就像子弹夹一样，子弹只能从一端装入，也只能从这一端弹出，另一端是封闭的，不能进行操作，如图7-6所示。

图7-6  栈的示意图

在堆栈中，不允许进行操作的一端称为栈底，用指针bottom来指示其位置，允许进行操作的一端称为栈顶，用指针top来指示其位置，插入操作称为入栈，删除操作称为出栈。在堆栈的操作过程中，栈底位置是固定不变的，栈顶位置却随着插入删除操作的进行而动态变化。由于操作只在一端进行，所以最先插入的元素只能在最后被删除，最先删除的元素总是最后插入的。栈的这个操作特征被称为“后入先出”（Last In First Out，LIFO）。

（2）栈的基本运算。

和一般的线性表类似，栈也有顺序存储（顺序栈）和链式存储（链栈）两种存储表示方式。

栈的基本操作有入栈、出栈、读取栈顶元素三种，如图7-7所示。

图7-7  堆栈操作示意图

入栈运算是在栈顶位置插入新的数据元素。

在顺序栈的入栈操作中，首先需要修改栈顶指针（将其取值加1）使其指向新的栈顶位置，然后将新元素插入到栈顶指针所指的位置。在入栈操作时，如果栈顶指针已经位于栈空间的最上端，表示堆栈已满，不能进行入栈操作，否则会发生溢出错误（称为上溢）。

出栈运算是取出栈定位置的数据元素。

在顺序栈的出栈操作中，首先读出栈顶指针所指位置的数据元素将其赋值给指定变量，然后需要修改栈顶指针（将其取值减1）使其指向新的栈顶位置。在出栈操作时，如果栈顶指针已经位于栈空间的下方，表示堆栈已空，不能进行出栈操作，否则也会发生溢出错误（称为下溢）。

读取栈顶元素的操作相对比较简单，只要读出栈顶指针所指位置的数据元素，并将其赋值给制定变量即可，堆栈本身并不发生变化。

（3）队列的基本概念。

图7-8  队列示意图

队列（queue）是限定在一端进行插入在另一端进行删除的线性表。

在队列中，允许插入的一端称为队尾，允许删除的一端称为队头，如图7-8所示。为了标明队头、队尾的位置，设置一个队头指针front，使其指向将要删除元素的前一个位置，设置一个队尾指针rear，使其指向最后插入的元素。队列的插入操作称为入队，删除操作称为退队。

与堆栈不同，数据元素的入队顺序与退队顺序是相同的，所以队列的操作特征被称为先入先出（First In First Out，FIFO）。

（4）队列的基本运算。

和一般的线性表类似，队列也有顺序存储（顺序队列）和链式存储（链队列）两种存储表示方式。

在实际应用中，顺序队列通常采用循环队列的方式进行，将队列空间的最后位置与开始位置逻辑对接，形成一个圆环，提供给队列存储数据元素。由于队头指针总是其指向队头元素的前一个位置，所以，当队头指针与队尾指针指向同一个位置时表示队列为空，当队尾指针值减对头指针值加1等于队列空间长度时或队尾指针比对头指针小1时表示队列已满。循环队列及其操作示意图如图7-9所示。

图7-9  循环队列及其操作示意图

队列的基本操作有入队、退队、求队列长度三种。

入队运算是在队尾插入一个新元素。循环队列入队操作前先要判断队列是否为满，队列满时不能进行操作。入队操作时首先修改队尾指针，使指针值加1，如果加1后的值大于队列空间长度，则使指针值为1，然后将新数据元素插入到指针所指的位置。

退队运算是在队头取出一个数据元素。循环队列退队操作前先要判断队列是否为空，队列空时不能进行操作。退队操作时首先修改队头指针，使指针值加1，如果加1后的值大于队列空间长度，则使指针值为1，然后将指针所指的位置的数据元素读出并赋值给指定变量。

循环队列的队列长度按照下列方式计算：

队列长度＝(队尾指针值-队头指针值+队列空间长度) % 队列空间长度

其中，%表示整除取余。

3．线性链表

（1）线性链表的基本概念。

链式存储结构是线性表的另一种常用存储方式，线性表的链式存储结构称为线性链表。在线性链表中，线性表的存储空间可以是不连续的，各个数据元素的存储顺序也可以和其逻辑顺序不一致。在这种存储方式下，每个存储的结点由两个部分组成：一部分是数据域，用来存储结点的数据元素；另一部分是指针域，用来存储指明其他结点存储位置的指针，线性表各个结点的逻辑关系就是用这些指针来表示的。指针域可以是一个（单链）或两个（双链）。在一个指针域的情况下，指针通常指向该结点的直接后继（后件），如果是两个指针域，则一个指向直接前驱（前件），另一个指向直接后继。

由于链式存储结构可以将各个结点分散存储，所以可以有效利用存储空间。另外，链式存储结构还可以用来存储一些比较复杂的非线性数据结构。

（2）单链表及其基本运算。

单链表是最简单、最基本、使用最广泛的线性链表，如图7-10所示。

图7-10  单链表示意图

单链表的结点由两部分组成，数据域用来存储线性表结点的数据元素，指针域用来存储指向本结点直接后继的指针。由于各个结点分散存储，所以设置一个专门指针head（头指针）用来指向线性表的第一个结点。由此，从头指针开始，依照各个指针的指示可以依次访问到线性表中的各个结点。单链表的最后一个结点的指针域要设置为空（NULL）以表示该结点为线性表的表尾。如果头结点的值为空，则表示这是一个没有结点的空链表。在实际应用中，为了使链表的所有数据结点可以用同一种方法操作，常使用带头结点的单链表，如图7-11所示。

图7-11  带头结点的单链表

单链表的最主要基本运算有查找、插入、删除三种。

查找运算是对单链表进行搜索，查找包含指定元素并确定其前一个结点（前件）位置的操作。查找时从头指针head开始沿指针依次向后进行扫描，查看结点数据的值是否与待查找数据相同。基本方法是：若头指针为空，表示链表为空，查找失败；否则，判断指针所指结点的数据域的值是否与待查找值相等，若相等，则查找成功，返回指针数据；否则，修改指针值为所指结点的指针域的值，然后重复上述操作直至查找成功活失败。由此可见，查找操作的时间复杂度在最坏情况下为n。

插入运算是在单链表的指定位置插入数据元素的操作，其基本情况如图7-12所示。

图7-12  单链表的插入操作

插入操作的基本方法是：首先查找指定数据X所在位置，返回指向其前件的指针q，并申请一个指针p所指的结点存储空间，使其数据域取值为待插入的数据Y，然后使指针p所指结点的指针域取值为指针q所指结点的指针域（图7-12中的①），再使指针q所指结点的指针域取值为p（图7-12中的②），使新结点连入链表。

插入运算是在单链表的指定位置删除数据元素的操作，其基本情况如图7-13所示。

图7-13  单链表的删除操作

删除操作的基本方法是：首先查找指定数据X所在位置，返回指向其前件的指针q，将指针q所指结点的指针域的值赋值到p中以保留被删除结点的位置，然后使指针q所指结点的指针域取值为指针p所指结点的指针域的值（如图中虚线箭头所示），使指定结点从链表中删除，最后读取指针p所指结点的数据域的数值并释放该结点所占据的存储空间。

单链表的插入运算和删除运算都要以查找为基础，在进行插入删除时不需要移动数据元素，只需要修改相关的指针值即可，操作的效率较高，适用于插入删除操作比较频繁的线性表。另外，由于结点分散存储，可以使多个链表共享同一个存储空间，以利于存储空间的动态分配。

（3）双向链表及循环链表。

在单链表中，由于结点只有一个指向其后件的指针域，所以查找只能沿一个方向进行而不能回溯，为了改善这种状况，可以改进结点的指针域组成，形成双向链表，如图7-14所示。

图7-14  双向链表示意图

在双向链表中，结点具有两个指针域，其中一个指向其前件，另一个指向其后件。在进行查找操作时，不仅可以沿后件指针向后进行，还可以沿前件指针进行回溯。在进行结点的插入和删除操作时则需要修改两个方向的指针。

对单链表的另一种改进是循环链表，如图7-15所示。

图7-15  循环链表示意图

循环链表的特点是表中最后一个结点的指针域不是为空，而是指向第一个结点，整个链表形成一个环。虽然链表的结点只有一个指针域，但从任一结点出发，都可以访问到表中的所有结点。循环链表的各种运算与单链表基本相同，只是在判断结点是否为表尾时，其条件应由结点的指针域是否为空改为是否等于头指针head。

4．树与二叉树

（1）树的基本概念。

树是数据结构中一类重要的非线性数据结构。直观来看，树具有以分支关系定义的层次结构。在现实世界中，人类的家族谱系、社会组织结构等都具有树结构的特征。图7-16就是一个树结构的抽象例子。

图7-16  树结构的图形表示

树（Tree）是由n个结点组成的有限集合，当n=0时称为空树。在任一非空树中，有且仅有一个被称为“根”（Root）的结点没有前件（直接前驱），其他结点都只有一个前件，结点的前件被称为该结点的“父结点”。在任一非空树中，任一结点都可以有若干个后件（直接后继），也可以没有后件，结点的后件被称为该结点的“子结点”，没有子结点的结点被称为“叶结点”。一个结点的后件个数被称为“结点的度”，树中结点的度的最大值被称为“树的度”。例如，在图7-16中，C结点的度为2，X结点的度为1，B结点的度为3，整个数的度为3。

在树的图形表示中，根结点位于第一层，根的子结点位于第二层，每一层的结点之间没有横向联系，各层结点的子结点都位于其下一层。树的最大层次数被称为树的“深度”。

在树结构中，某个结点及其下属结点也构成一棵树，该树被称为原树结构的子树。例如，上面图中的J、I、V、S、H就构成一棵子树，而I、S、H又构成该子树的子树。当然，叶结点是没有子树的。

（2）二叉树及其基本性质。

二叉树（Binary Tree）是另一种树形数据结构（如图7-17所示），它属于抽象数据类型，它的结点最多只有两棵子树（二叉树中不存在度大于2的结点），并且其子树有左右之分，不可颠倒混淆。

图7-17  二叉树示例

二叉树具有下列特点：

①任何非空二叉树只有一个根结点。

②树中每个结点最多有左右两棵子树，分别为该结点的左子树和右子树。

二叉树具有下列基本性质：

①第k层上最多有2^k-1个结点。

②深度为m的二叉树最多有2^m-1个结点。

③任何二叉树叶结点总比度为2的结点多一个。

④具有n个结点的二叉树的深度至少为[log₂n]+1，其中括号[ ]表示取不大于其值的整数。

除了一般的二叉树外，二叉树还有两种特殊形态，满二叉树和完全二叉树。

满二叉树（如图7-18所示）的各层结点数都达到最大值。所以，满二叉树的叶结点都在最后一层，其余各层中结点都有左右两个子结点。满二叉树的结点数为2^m-1个。

完全二叉树（如图7-18所示）是在满二叉树的基础上去除最下层右侧的某些结点后的二叉树。所以，完全二叉树的叶结点只会出现在最下两层上，完全二叉树某个结点的右子树的深度或是与左子树的深度相同或是比其深度小一。另外，完全二叉树还具有下列性质。

图7-18  满二叉树和完全二叉树示例

①具有n个结点的完全二叉树的深度为[log₂n]+1。

②若对具有n个结点的完全二叉树按照自上而下逐层从左到右的顺序编号，则对任一结点i（1≤i≤n），有：

·    若i=1，则为根结点，无父结点；否则，其父结点为[i/2]。

·    若2i＞n，则该结点无左子树（为叶结点）；否则，其左子结点为2i。

·    若2i+1＞n，则该结点无右子树；否则，其右子结点为2i+1。

（3）二叉树的存储结构。

二叉树属于非线性结构，而计算机的存储器属于线性结构，所以二叉树在计算机中通常采用链接方式存储。二叉树的链接式存储结构通常称为二叉链表。因为二叉树的结点最多可有两个后件，所以二叉树结点在存储时除了要有数据域data外，还需要设置两个指针域lChild和rChild，以分别指向其左右子结点，如图7-19所示。

图7-19  二叉树结点的存储结构

如果结点没有左子结点或右子结点，则相应的指针设置为空或0。为了能够找到整个二叉树的根结点，还必须设置一个指针bt以指向其根结点。图7-20就是前面所示的二叉树按照二叉链表方式存储时的逻辑状态和实际存储状态的一个示例。

图7-20  二叉树的链式存储结构示意图

此外，对于满二叉树和完全二叉树这些特殊形态的二叉树，在进行存储时，可以按照逐层顺序编号的次序进行顺序存储，不仅可以节约存储空间，而且方便计算操作。

（4）二叉树的遍历。

所谓遍历二叉树（Traversing Binary Tree）是指按照某个搜索路径访问二叉树中的每个结点，并且使得每个结点均被访问一次并只被访问一次。

在二叉树的实际应用中，常常需要查找树中的某个结点，对树中的某些结点进行一些处理，或者进行结点的插入删除操作等。这些操作都需要以遍历操作为基础。

由于二叉树的结点都可以具有左右两棵子树，所以在遍历过程中规定按照先左后右的原则，并且依据访问根结点的先后顺序，将遍历方式分为三种：先序遍历、中序遍历和后序遍历。

先序遍历的操作过程为：

首先判断二叉树是否为空，若为空则结束操作，否则：

①访问根结点。

②先序遍历左子树。

③先序遍历右子树。

中序遍历的操作过程为：

首先判断二叉树是否为空，若为空则结束操作，否则：

①中序遍历左子树。

②访问根结点。

③中序遍历右子树。

后序遍历的操作过程为：

首先判断二叉树是否为空，若为空则结束操作，否则：

①后序遍历左子树。

②后序遍历右子树。

③访问根结点。

图7-21  二叉树的遍历路径示意图

需要指出的是，以上操作过程是递归的，即访问子树时的访问方式也必须按照既定的访问方式进行，直到结点没有子树为止。例如，对于前面所示的二叉树示意图，按照先序遍历方式，先访问根结点A，然后访问左子树BDEG，再访问右子树CFHI；在访问左子树BDEG时，也要先访问根B，然后访问左子树D，再访问右子树EG；依此类推，可得到先序访问该二叉树各结点访问顺序为ABDEGCFHI。所以，按照中序遍历的规则，这个二叉树的中序遍历结果为DBGEACHFI；按照后序遍历的规则，后序遍历结果为DGEBHIFCA。

图7-22  依据先序遍历结果和中序遍历结果还原的二叉树

另外，判断二叉树遍历结果还有一个比较直观的方法。就是按照图7-21所示的方法，在二叉树的图示上按照访问路线画出一条曲线，如果某个结点没有左子树或右子树，曲线也要向左下或右下弯一小圈。然后观察曲线经过结点的顺序，曲线第一次经过结点的顺序就是先序遍历的结点顺序，曲线第二次经过结点的顺序就是中序遍历的结点顺序，曲线第三次经过结点的顺序就是后序遍历的结点顺序。

如果已知某二叉树的先序遍历结果及中序遍历结果，就可以还原该二叉树。例如，某二叉树的先序遍历结果为CAEBHFD，中序遍历结果为EACHFBD，则依据先序结果可判断其根为C，再从中序结果中可知该树的左子树由EA组成、右子树由HFBD组成；从先序结果中的AE和中序结果中的EA可知，该左子树的根为A，E为左子树，其下再无结点；然后依据先序结果中的BHFD和中序结果中的HFBD，判断出该树的右子树的根为B，B的左子树由HF组成，B的右子树为D；最后由先序结果中的HF和中序结果中的HF，得到H为根，F为右子树。还原该二叉树如图7-22所示。

同样，依据某二叉树的中序遍历结果及后序遍历结果，也可以还原该二叉树。

7.2.4  查找和排序算法

查找是指在一个给定的数据结构中查找某个指定的元素。下面介绍两种常用的查找方法。

（1）顺序查找。

顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次将线性表中的元素与给定值K相比较，若相等则表示查找成功；若扫描结束后，线性表中所有的元素都不等于K，则查找失败。

顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。

在等概率情况下，pi＝1/n(1≤i≤n)，查找成功的平均查找长度为(n+…+2+1)/n＝(n+1)/2，即查找成功时的平均比较次数约为表长的一半。若K值不在表中，则须进行n+1次比较之后才能确定查找失败。

（2）二分法查找。

二分法查找只适用于顺序存储的有序表。有序表指线性表中的元素按值由小到大或由大到小排列。

二分法查找的基本思想是：设有序线性表的长度为n，并且元素由小到大排列。将给定值k与线性表中间项的元素值进行比较，中间项的位置值是(1+n)/2。若中间项的值等于k，则查找成功；若k小于中间项的值，则在线性表的前半部分子表（位置编号是1～(1+n)/2-1）以相同的方法进行查找；若k大于中间元素的值，则在线性表的后半部分子表（位置编号是(1+n)/2+1～n）以相同的方法进行查找。上述过程一直进行到查找成功或子表长度为0（说明查找失败）结束。

例如有一组数：4、10、11、25、42、59、64、71、73、86，要求用二分法查找11，查找过程如图7-23所示；如再要求用二分法查找69，查找过程如图7-24所示。

显然，有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log₂n次，而顺序查找需要比较n次。

图7-23  二分法查找示例1

图7-24  二分法查找示例2

如果对无序的顺序线性表进行二分法查找，首先要对该线性表进行排序，那么什么是排序呢？排序是指将一个无序序列整理成按值大小顺序排列的有序序列。排序的方法很多，下面分别介绍几种常用的排序方法（注：以下排序均以升序为例）。

（1）交换类排序法。

交换类排序的基本思想：两两比较待排序的数据项，若两个数据项的次序相反时即进行交换，直到没有反序的数据项为止。应用交换类排序基本思想的主要排序方法有：冒泡排序和快速排序。

·    冒泡排序

冒泡排序的基本过程如下：假设表中有n个元素，首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换。第一趟扫描结束后，线性表中的最大值就换到了表的最后位置，也就是第n个位置。接着开始第二趟扫描，此时的扫描范围是1号元素至n-1号元素，以同样的方式扫描结束后，将整个表中的第二大值换到了第n-1个位置上；……，重复上面的步骤，总共进行n-1趟扫描，使得线性表变得有序。在上述过程中，可以增设一个状态监视变量，如果某一趟扫描过程中没有出现元素交换的情况，说明线性表已经有序，那么排序算法执行完毕。

若初始线性表的初始状态是正序的，一趟扫描即可完成排序。元素的比较次数为n-1次，元素的交换次数为0，这两者均达到最小值；若初始线性表是反序的，需要进行n-1趟排序，每趟排序要进行n-i次元素的比较（1≤i≤n-1），且每次交换都必须移动元素三次来达到交换位置的目的。在这种情况下，元素的比较次数为n(n-1)/2次，元素的交换次数为3n(n-1)/2，这两者均达到最大值，所以冒泡排序的最坏时间复杂度为O(n²)。而该算法的平均时间复杂度为O(n²)。冒泡法排序过程如图7-25所示，横线部分表示扫描范围，即参与扫描的元素。

图7-25  冒泡排序法示例

·    快速排序

快速排序的基本思想：从线性表中选取一个元素，设为k，将k后面小于其的元素移到k的前面，而k前面大于其的元素移到k的后面，这样就以k为分界线，将线性表分成前后两个子表，且前子表中的所有元素均小于等于k，而后子表中的所有元素均大于等于k，这样的过程称为线性表的分割。对分割后产生的子表按上述原则继续进行分割，直至所有子表为空，则线性表变成有序表，算法结束（如图7-26所示）。

图7-26  快速排序算法简单示意图

那么如何对表（子表）进行分割呢，步骤如下：

首先，选取表的中间项，设为P(k)，并将P(k)的值保存在temp中，再将表中的第一个元素移到P(k)的位置上。然后设置两个指针i和j分别指向表的起始位置与最后位置。

以下步骤交替进行，反复操作：将j逐渐减小，并逐次比较P(j)与temp，直到发现一个P(j)< temp为止，将P(j)移到P(i)位置上；将i逐渐增大，并逐次比较P(i)与P(k)，直到发现一个P(i)> P(k)为止，将P(i)移到P(j)位置上。

当指针i与j 指向同一个位置（即i=j）时上述步骤停止，将temp的值存入P(i)，至此分割结束。

当快速排序时，随着分割的不断进行，产生的子表会越来越多，而每次只能对一个子表进行分割，所以就要采用栈来实现整个算法。将要分割的子表放入栈中，当栈空即说明没有子表再需要分割，排序就已经完成了。

快速排序法的平均时间复杂度为O(nlgn)。快速排序的最坏时间复杂度为O(n²)。

（2）插入类排序法。

插入类排序的基本思想：将线性表中每一个待排序的数据项，插入到之前已经排好序的子表中，并使得子表依然有序，当所有数据项都插入表中，算法结束。本文介绍两种插入法：简单插入排序法、希尔排序法。

·    简单插入排序

线性表中，只包含第1个元素的子表显然是有序表，接下来要做的就是将线性表中的第2个元素至最后一个元素依次插入到前面已经有序的子表中。

假设线性表中前j-1元素已经有序，现在要将线性表中第j个（2≤j）元素插入到前面的有序子表中，插入过程如下：首先将第j个元素值保存在变量temp中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与temp进行比较，如果第i个（1≤i≤j-1）元素大于temp，则将第i个元素向后移动一个位置；如果第i个（1≤i≤j-1）元素小于等于temp，则将temp插入刚移出的空位置i+1中，或者子表中所有元素都大于temp，则temp插入到1号位置中，这样原线性表中的第j个元素就插入完毕，有序子表的长度变为j。

插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌（无序区）中摸最上面的1张并插入左手的牌（有序区）中正确的位置上。为了找到这个正确的位置，需自左向右（或自右向左）将摸来的牌与左手中已有的牌逐一比较。

该算法时间复杂度主要考虑元素值的比较次数和元素的移动次数，在线性表是正序的情况下，其移动次数为0，比较次数为n-1，时间复杂度为O(n)；在文件是逆序的情况下，其移动次数为(n-1)(n+4)/2，比较次数为(n+2)(n-1)/2，时间复杂度为O(n²)。故简单插入排序法的平均时间复杂度为O(n²)，空间复杂度为O(1)。

·    希尔排序

希尔排序的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量k的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当k减到1时，进行一次插入排序，排序就完成。增量序列一般取k=n/2^t（t=1,2,…[log₂n]，其中n为待排序序列的长度。

希尔排序在最坏情况下，需要的比较次数为O(n^1.5)。

（3）选择类排序法。

选择类排序的基本思想：每一趟从线性表(子表)中选出最小的元素，将它放到表的最前面，直到子表空，算法结束。常用的选择类排序方法有简单选择排序法和堆排序法。

·    简单选择排序

假设线性表长度为n，简单选择排序共需要扫描n-1趟。第i趟扫描（1≤i≤n-1），扫描范围从第i个元素开始至第n个元素结束，找出其中的最小元素，将其与扫描范围中的第1个元素（即线性表中第i个元素）进行交换。这样，n个元素的线性表经过n-1趟简单选择排序得到有序结果。简单选择法排序过程如图7-27所示，横线部分表示扫描范围，即参与扫描的元素。

图7-27  简单选择排序法示例

无论线性表初始状态如何，在第i趟排序中需做n-i次比较选出最小元素，因此，总的比较次数为：n(n-1)/2=O(n²)。若初始线性表为正序则移动次数为0；为反序则每趟排序均要执行交换操作，总的移动次数取最大值是3(n-1)。简单选择排序的平均时间复杂度为O(n²)。

·    堆排序

首先介绍一下什么是堆，堆的定义如下：具有n个元素的序列（h1,h2,…,hn），当且仅当满足，（i=1,2,…,n/2）时称之为堆。本书只讨论满足前者条件的堆。在实际处理中，可以用一位数组或者完全二叉树来直观地表示堆的结构。例如堆（126，109，98，69，60，56，30，26，19，2），它所对应的完全二叉树如图7-28所示。

图7-28  用完全二叉树表示的堆

堆排序的方法：首先将一个无序序列建成堆，然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调准为堆。反复执行第（2）步，真到剩下的子序列为空，算法结束。

堆排序法适用于规模较大的线性表，在最坏情况下算法需要比较的次数为O(nlog₂n)。