第1章 数据结构与算法

第一章 数据结构与算法

1.1.1 算法的基本概念

算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。 程序的编制不可能优于算法的设计。 1．算法的基本特征

(1)可行性：算法中要执行的每一个步骤都可以在有限时间内完成，且正确，否则是不会得到满意结果的。

N=-10;

for( k=1;k<=n;k++ )

c=c+1;

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

X=a·b/c·d X=a·b/(c·d) X=a·(b/c)·d

(3)有穷性：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

算法的有穷性还应包括合理的执行时间的含义。 for( k=1;k<=n;k++ ) c=c+1;

下例是无限循环：

for( k=1;k<=-10;k++ ) c=c+1;

(4)拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。 2，算法的基本要素

一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。

(1)算法中对数据的运算和操作

计算机算法就是计算机能处理的操作所组成的指令序列。

一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。程序：是使用某种程序设计语言对一个算法或多个算法的具体实现。

在一般的计算机系统中，基本的运算和操作有以下四类： ①算术运算：主要包括加、减、乘、除等运算。 ②逻辑运算：主要包括“与”、“或”、“非”等运算。 ⑧关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 ④数据传输：主要包括赋值、输入、输出等操作。

描述算法工具：如流程图，专门的算法描述语言，甚至用自然语言等来描述算法。 算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。

计算机算法则是使用一些最基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。

(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构

算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。

描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 3．算法设计基本方法 (1)列举法 ，

列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。

(2)归纳法

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。 归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。归纳是一种抽象，即从特殊现象中找出一般关系。归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。

(3)递推

所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。

递推关系式往往是归纳的结果。 (4)递归

将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。

递归分为直接递归与间接递归两种。

如果一个算法P显式地调用自己则称为直接递归。

如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。

递推与递归的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。

(5)减半递推技术

所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。 所谓“减半”，是指将问题的规模减半，而问题的性质不变。 所谓“递推”，是指重复“减半”的过程。 (6)回溯法

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。

1.1.2 算法复杂度

算法的复杂度主要包括时间复杂度和空间复杂度。 1．算法的时间复杂度 ·

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个程序在计算机上运算所消耗的时间主要取决下述因素： (1) 程序运行时所需要输入的数据总量消耗时间。 (2) 对源程序进行编译所需要的时间。 (3) 计算机执行每条指令所需要的时间。 (4) 计算机关键指令重复执行的次数。 分析算法的工作量。 (1)平均性态

所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。

设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为

A(n)=∑p(x)t(x)

当规模为n时，算法执行时所有可能输入的集合。p(x)必须由经验或用算法中有关的一些特定信息来确定。如果确定p(x)比较困难，则会给平均性态的分析带来困难。

(2)最坏情况复杂性(Worst-CaseComplexity)

所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为

w(n)=max{t(x)} 算法分析 x=y+10 x=y*y+100

可是，在算法分析时，我们无论是计算拿一个x都认为是“一个操作步骤”，这样做是为了突出分析的重点，忽略细节。

为此，我们引入语句频度的概念（frequency count）。所谓语句频度即为“操作步骤”或“语句”重复执行的次数。为描述算法的时间复杂性，我们可以将复杂性用函数T(n)表示，n表示算法中处理数据对象的数量或问题的规模的度量，如一算法时间复杂性是： T(n)= 2n3+3n2+2n+1

当n足够大时，有T(n)≈2n3，或者g(n)=2n3

因为，当n足够大时，2n3的复杂度大大超过3n2+2n+1 ，或者说，T(n)数量级与n3数量级相同。所以，当n足够大时，可以忽略复杂性函数中复杂性较低的部分，而只用复杂度高的部分表示。

为此，我们进而引入渐进符号 “O”，用大写O字母表示函数T(n)的上限函数，即当n足够大时的函数，记为：O(g(n))= O(n3)

下面给出几种典型的复杂性函数的表示（a,b,c为已知数）： 线性函数：O(g(n))= O(a*n+b) =O(n) 平方函数：O(g(n))= O(a*n2+b*n)= O(n2)

指数函数：O(g(n))= O(an + b*n2+c*n)=O(an) 常数函数：O(g(n))= O(9+12)= O(1)

对数函数：O(g(n))= O((a*n*log2n +b*n)= O(n*log2n)

常数函数是指算法的复杂性与算法中处理数据对象的数量无关，比如，

T(n)= 15 T(n)= 20056

两个T(n)函数中，无论n的值如何，函数值始终为一常量，这时认为算法的复杂性是

O(1)，注意，不是T(n)函数的常量值。

例如，两个n×n的矩阵相乘，其算法可描述如下： void matrix-product（int a[][]，int b[][]，int c[][],int n）； { for( i=1;i<=n;i++ ) for ( j=1;j<=n;j++ ) { c[i][j] =0; for( k=1;k<=n;k++ ) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } 重复次数 n+1 n(n+1) n2 n2(n+1) n3 再如，下面有三个简单的程序段。 （a）x=x+1;

（b）for (i=1;i<=n;i++)

{ x=x+1;}

（c）for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{ x=x+1;}

假定（a）中语句x=x+1不在任何的循环中，则语句频度为１，其执行时间是一个常数，因此，其时间复杂性是常量级，即O(1)。

在（b）中，同一语句x=x+1执行了n次，其频度为n，其时间复杂性依赖于n，所以，时间复杂性为O(n)。

在（c）中，语句x=x+1执行了n*n次，频度为n2 ，其时间复杂性依赖于n2 ，因此，时间复杂性为O(n2)。

通常情况下：

无循环结构，时间复杂性为量，记为：O（1） 单循环结构，时间复杂性为量，记为：O（n） 双循环结构，时间复杂性为量，记为：O（n2） 三层循环结构，时间复杂性为量，记为：O（n3） 2. 算法空间复杂性

算法执行所需要的内存空间 空间复杂性的组成 1) 程序空间

程序空间是指用来存储经过编译之后的程序指令所需的空间。指令空间一般不是数据结构所讨论的问题。

2) 数据空间

数据空间是指用来存储所有常量和变量所需要的空间。数据空间分成两部分： ? 存储常量和简单变量所需要的空间。 ? 存储复合变量所需要的空间。

这一部分空间又由两部分组成：一是数据结构定义的数据元素信息本身存储所需存储空间，二是动态分配的空间时存储链接空间。

1. 2 数据结构的基本概念

定义：数据结构就是研究计算机中大量数据存储的组织形式，并定义且实现对数据的相应的运算，以提高计算机的数据处理能力的一门科学。

数据结构相关事例

问题一：电话号码簿的使用及字典的使用。

党政机关 大学 企业 7 12 25 7 省委 市委 区委 55 127 224 55 省委办公厅一处 88060001 省委办公厅二处 88060002 · · · 市委办公二处 · · · 430 武汉大学 · · · · · · 127 市委办公一处 85800203 85800105 旅游 32 12 综合类大学 325 325 华中科技大学 理工大学 87870001 86880206 图1.1.1 电话号码簿

问题二：某省各城市之间要架设电话通信线路，要保证各城市间互通，又要使设成本最少。就是数据结构中讨论的图结构的应用－－最小生成树。

25 A B B A 45 12

25 12

7 11 5 E 7 5 E 11 34

78 C D C D 44

图1.1.3 城市连接及距离 图1.1.4 最小生成树

结构类型

数据结构中讨论的结构类型分为两个层面，一是逻辑层面的数据结构，简称逻辑结构；另一个是物理层面的数据结构，简称物理结构。

1. 逻辑结构

逻辑结构描述数据元素与数据元素之间的关联方式，简称为关系，表示的是事物本身的内在联系。逻辑结构又可以分为：线性结构和非线性结构两大类。

线性结构的特点表现为，线性结构中数据元素之间的正逆关系都是“一对一”的。 线性结构又可再分为：线性表、堆栈、队列等。

非线性结构的特点表现为：数据元素不一定存在确定的前后次序，甚至是无序的，数据元素之间存在从属或互为从属的关系或离散关系。

非线性结构又可再分为树形结构、图状或网状结构、纯集合结构。 在树型结构中，数据元素之间存在着“一对多”的关系。 在图或网状结构中，数据元素之间存在着“多对多”的关系。 在纯集合结构中，数据元素具有“同属于一个集合”的关系。 2. 存储结构 存储结构，是逻辑结构的数据元素在计算机的物理存储空间上地映象，映象不仅包含数据元素本身，而且包含着数据元素之间的关联方式，即关系的映象。

映象表现为两种方式：顺序映象和非顺序映象。 1) 顺序映象

顺序映象是指数据元素在一块连续地物理存储空间上存储，物理存储空间只用于存放数据元素本身，数据元素之间的关联以两个数据元素存储的相邻关系来表示或通过某个函数来表示。或者说，利用数据元素在存储空间上的相对位置来表示数据元素之间的逻辑关系。

如一组成绩信息，每个数据由姓名和成绩两个数据项构成： ｛｛彭亮，97｝，｛王明，95｝，｛李智，90｝，｛刘丹，88｝，｛肖象，78｝｝ 数据元素是按成绩从高至低的顺序排列，即按成绩从高至低关联，在物理存储空间上的存储映象如图1.2.2所示，

彭亮，97 王明，95 李智，90 刘丹，88 肖象，78

图1.2.2 成绩信息的顺序映象

再如,有一个下三角矩阵：

1 2 3 4 5

1 0 0 0 0 0

2 A 0 0 0 0 3 B C 0 0 0 4 D E F 0 0

5 G H I J 0

在物理存储空间上存放为如图1.2.3所示，数据元素存储的空间是连续地，每个数据元素以相邻方式存储，数组元素按行优先法则存储。如要查找第i行，第j列（1

F（i,j）=((i-1)*(i-2))/2+j A B C D E F G H I J 顺序映象的最大优点就是空间的利用率最高，但一旦要在中间插入数据元素或删除中间图1.2.3 下三角矩阵的顺序映象 数据元素，就必须移动大量数据元素，这种运算在计算机中是相当耗时的。

2) 非顺序映象

非顺序映象是指数据元素在物理存储空间上非连续地存储，物理存储空间不仅存放数据元素本身，而且为实现数据元素之间的关联，在每个数据元素存储的相邻空间中存储该数据元素关联的另一个或多个数据元素的起始地址。也可以说数据元素之间的关系是由附加“链接或指针”来表示。

非顺序映象存储结构中，数据元素的逻辑结构一般在物理空间上不是以物理空间的相邻来表现，而是在每个数据元素本身所占用空间的相邻空间中，存放该数据元素所关联的另一个或多个数据元素的位置，通常将这个空间称为链地址空间。最后一个数据元素的链地址空间指向空地址。可以看出数据元素在物理存储上是离散的，且物理顺序不一定与逻辑顺序保持一致。

成绩信息的物理映象如图1.2.4

第一个数据元素地址

刘丹，88 彭亮，97 李智，90 王明，95 肖象，78

空

图1.2.4 成绩信息的非顺序映象

D B A B C D E F 图1.2.5 二分枝的树逻辑结构 树的起点地址 空 空 空 A C F E 空

图1.2.6 树的存储结构

3. 数据域和链接域 1) 数据域

数据域是物理存储空间中存储数据元素中数据值的空间，如成绩数据问题中，存储姓名和成绩两个数据项，所占用的空间大小（字节数）依实际应用的数据元素中包含的信息量的大小而定。

2) 链接域

链接域又称指针域，是非顺序存储映象时表示数据元素之间关系的地址存储空间，是额外的空间付出。在顺序存储映象结构中，链接域是不存在的，数据元素之间关系是以物理存储的邻接方式隐含表示的。

线性表及其存储结构

1.3.1线性表的基本概念 线性表是有限元素（e1, ...,ei,...,en）的有序序列的集合。其中n是有穷自然数，ei是表中的元素，每个元素具有相同的特性，表中元素占用空间大小相同（记为：size），n是表的长度。当n=0时，表为空；当n>0时，e1是第一个元素（前件），en 是最后一个元素（后件）。

数据元素通常称为结构或记录类型。而包含多个结构或记录的线性表也可以称为文件。 线性表是一种线性结构。 特征：

1) 有且只有一个根结点e0，它无前件； 2) 有且只有一个终端结点en，它无后件；

3) 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

1.3.2 线性表顺序存储结构

在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： ①线性表中所有元素所占的存储空间是连续的；

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

线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的。

在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间<字节数)相等，线性表中查找某一个元素是很方便的。

元素ei的地址则可以立即由下面公式求出。

location(ei)=location(e1)+（i-1）×size

n ? 1 i ? e1 ? ei ? en

图2.2.1 线性表顺序存储

线性表中第k个数据元素之后插入元素x运算

它是指在线性表的元素ek+1和元素ek之间插入一个新的元素x。即要在元素ek+1的地方插入一个元素。

插入过程：首先需要将元素ek+1及以后的所有元素都要向后移动一个元素的位置，移动以后，空出ek元素的存储空间才能存入新的元素x。需要注意，实现元素的插入是有前提条件的，就是要求在线性表的元素en的后面还有空闲的存储单元可以使用，否则插入是无法进行的。插入后线性表的长度加1。

线性表中删除第k个数据元素运算

一般说来，删除运算是指需要删除线性表中的第K个数据元素。删除的办法是将ek后所有元素ek+1，?，en依次向前移动一个元素的位置，然后修改线性表的长度（减1）。

在顺序存储线性表的删除运算中，不用专门进行存储空间的释放，事实上，移动数据元素的同时，被删除元素的空间同时已被释放了，释放到线性表数据元素尾端，即线性表中删除前最后一个数据元素的空间。

线性表顺序存储方式下，由于相邻元素之间是紧邻的，而无可利用的“空闲”空间。因此，进行元素的插入或删除运算时，有着大量元素的移动，移动元素的多少取决于插入或删除元素的位置，而这种大量元素的移动是十分费时的，所以有着频繁的插入或删除运算的线性表，是不适合采用顺序存储方式的。

①在线性表的指定位置处加入一个新的元素(即线性表的插入)； ②在线性表中删除指定的元素(即线性表的删除)：

⑧在线性表中查找某个(或某些)特定的元素(即线性表的查找)； ④对线性表中的元素进行整序(即线性表的排序)；

⑤按要求将一个线性表分解成多个线性表(即线性表的分解)； ⑥按要求将多个线性表合并成一个线性表(即线性表的合并)； ⑦复制一个线性表(即线性表的复制)： ⑧逆转一个线性表(即线性表的逆转)等。

1.4

1.4.1栈及其基本运算 1. 堆栈的定义 堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（bottom）。

故也称栈为后进先出表或先进后出表，简称LIFO（Last in first out）或FILO（First in last out）表。

进栈 出栈

top D

C

B

bottom A 图3.1.1 堆栈

2. 堆栈顺序存储

堆栈顺序存储方式，是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保

证堆栈数据元素逻辑上的有序性。

假设堆栈中每个数据元素占用size字节空间，top指向堆栈中进栈元素的栈顶元素，即栈顶元素的地址，MaxSize表示堆栈可以存储元素的最大空间。一般约定下标为1的元素空间就是栈底，这样就不再另设一变量再来记录栈底指针bottom。

3. 堆栈顺序存储运算 1) 判断堆栈是否为空

所谓堆栈为空，是指堆栈中没有一个数据元素，即栈顶指针top指向数据空间的第一个位置的前面。如堆栈不空，top总是指向栈顶元素。

2) 判断堆栈是否为满

所谓堆栈为满，是指堆栈的所有数据空间已经全部用完，即栈顶指针top指向数据空间的最大下标位置。如堆栈不满，top总是指向栈顶元素（top的值小于MaxSize）。

3) 进栈（又称压入）运算

进栈运算是将一新元素x存储到当前top所指的空间的“上”一个位置，即top+1的的元素空间中。进栈时，首先要判断堆栈中是否存在元素存放的空间，即先判断栈是否满，不满时，x可以进栈，否则出错（上溢）。x进栈前，top指针要先做相应地移动。

4) 出栈（又称弹出）运算

出栈运算是将栈顶元素取出，且将栈顶指针top向“下”移动一个位置，即取出top所指的元素，然后，top的值减1。出栈时，首先要判断堆栈中是否存在元素可取，即先判断栈是否空，不空时，可以出栈，否则出错（下溢）。出栈后，top指针要做相应地移动。

5) 返回栈顶元素的值

返回堆栈栈顶元素的值，是指将top所指的堆栈元素的值取出，但是top指针不移动，当然，能够取得栈顶值的前提是栈中有元素存在（先判断栈是否空）。

这个算法与出栈算法有所不同，两个算法都可以取得栈顶指针所指的元素值，但此算法取值后不会移动top指针，即栈中元素的个数不发生改变。

1.4.2 队列及其基本运算

1. 队列的定义

队列是一个线性表，其数据元素只能从这个线性表的一端插入，而从另一端删除，删除端称为队列的队头（front），插入端称为队列的队尾（rear）。

取数据时（删除），又称出队，总是从队列中front所指的位置取走数据。插入数据时，又称进队，总是在队列中rear所指的位置后面添加。取走数据与放入时的顺序恰好相同，故也称队列为先进先出表，简称FIFO（First in first out）表。

2. 循环队列及其运算 1. 循环队列由来 0 1 2 3 4 MaxSize-1

X A B C D ?

front↑ rear↑

图3.7.1 队列出队前

0 A front↑

1 B 2 C 3 D 4 rear↑

图3.7.2 队列出队后（元素前移）

? MaxSize-1

0 1 2 3 C 4 D ? MaxSize-1 不可用存储空间 front↑ rear↑

图3.7.3 队列“爬过”存储空间

0 rear↑ 1 2 3 4 D front↑ ? X MaxSize-1 Y 图3.7.4 队列指针转向

0 1 2 3 4 MaxSize-1 rear↑ front↑ 图3.7.5 队列为空

0 Z 1 AA 2 BB 3 CC 4 DD ? X MaxSize-1 Y rear↑ front↑ 图3.7.6 队列为满

0 front↑ 1 A 2 B 3 C 4 D rear↑ 图3.7.7 循环队列

0 1 front↑ 2 B 3 C 4 D rear↑ 图3.7.8 循环队列

0 1 2 3 4 ? MaxSize ? MaxSize ? MaxSize front↑ ↑rear 图3.7.9 循环队列为空状态

1 2 3 4 MaxSize 0

Z B C D ? F J

rear↑ front↑

图3.7.10 循环队列

2. 队列运算

1) 判断队列是否为空

所谓队列为空，是指队列中没有数据元素，即队列队头指针和队尾指针指在同一个位置，即front=rear。

2) 判断队列是否为满

所谓队列为满，是指队列的所有数据空间已经全部用完，即队列队头指针和队尾指针的关系是：front= rear+1或1。

3) 进队运算

进队列运算是将一新元素x存储到当前rear所指空间的“下一个”位置。进队时，首先要判断队列中是否存在元素存放的空间，即先判断队列是否满，不满时，x可以进队列，否则出错。

4) 出队运算

出队运算是将队列中队头指针所指的“下一个”位置的元素取出。做法是：首先将队列队头指针front先向“下一个” 位置移动，然后，取出移动后front所指的数据元素。出队时，首先要判断队列中是否存在元素可取，即先判断队列是否空，不空时，可以出队，否则出错。

1.5 线性链表

线性表的顺序存储方式，它有着逻辑关系上相邻的两个数据元素在物理位置上也相邻的特征。因此，只要知道第一个元素的位置（即下标），则可以利用寻址公式高效地存取一个元素。但是，通过其插入，删除算法的分析也可以看出，它存在着一些缺点：

其一，在插入或删除的过程中有着大量元素的移动，运算时间较长。

其二，在为长度可变化的线性表预先分配空间时，必须按最大表长空间分配，因而造成存储空间得不到充分利用。

第三，表的空间不容易扩充。

为此，在有着频繁插入、删除运算时，不宜采用顺序存储结构。

线性链式存储结构时，物理存储空间的分配可以是静态存储空间分配，也可以是动态存储空间分配。

1. 简单线性链表

在动态链式结构中，数据元素是由两部分构成的，一是数据元素的数据域；二是数据元素的链接域。链接域指向下一个数据元素存储空间的起始地址，数据元素又被称为结点。

k

L

? ∧

e0 e1 e2 en-2 e n-1

图2.3.2 简单链表

*first *link

data Hdata

数据元素结点结构 表头结点结构

图2.3.1 数据元素及表头结点结构

当某个结点后面没有结点时（无后继结点），该结点的link值为空（用NULL，或0，或用符号∧表示）。

一个链表除了数据元素结点外，通常将这个特殊结点称为“表头结点”，表头结点的链接域的类型是指向数据结点的指针类型，表头结点的数据域可以与数据结点的数据域的类型不同，用于存放线性表的有关“综合”信息。

2. 双向链表的存储

Rlink指向直接后继结点，Llink指向直接前驱结点。链表中最后一个结点的Rlink域为NULL，第一个结点的Llink域为NULL。

这样定义后，某结点直接前驱结点地址由该结点的Llink指出，不须从表头开始追踪，提高了运算效率。由这样定义的结点组成的链表称为双向链表，因为它的每个结点均有向前、向后的指针。双向链表结点的连接如图2.4.1和图2.4.2所示。

L ∧ A ? Z ∧ B Y Llink A Rlink

图2.4.2双向链表 图2.4.1双向链表结点结构

3. 链式栈

给出了一个链式栈S的结构，表头链接域top始终指向栈顶结点，即链表的第一个结点。对链式栈，一般不存在栈满问题，除非存储空间全部被耗尽；链式栈空表现为链式栈的表头结点链接域top的值为空，即链表为空。

? top ∧ S en-1 en-2 en-3 e1 e 0

图3.3.2 链式栈

4. 链式队列

给出了一个链式队列q的结构，表头链接域front始终指向队列顶结点，即链表的第一个结点。对链式队列，一般不存在队列满问题，除非存储空间全部被耗尽；链式队列空表现为链式队列的表头结点链接域front的值为空，即链表为空。

? ∧ q头指针 front e0 e1 en-1 rear 图3.8.1 链式队列

1.5.2 线性表的基本运算

1. 简单链表L中查找元素值为X的结点

设定一个指针p，用于指向链表中的一个数据结点，当p所指的结点值等于x值时，表示已经找到了数据元素。

当p为空时，说明指针已经指到了链表的最后一个结点的后面，说明不存在这个数据结点，查找失败。

p

L ? ∧ e0 e1 e2 en-2 e n-1 图2.3.2 简单链表

2. 简单链表L中数据元素x之前插入元素b 1) 在表中找x结点的前一个结点（q指向） 2) 当找到后，在q后面插入一个新的元素p

3) 插入一个新的元素p时，将新结点数据值b填入其中，然后分别修改结点p和新结点q的链接域即可。

q

L

∧ ?

ek-1 x en-2 e n-1

p

b (b) 插入后

图2.3.3 简单链表插入

3. 从简单链表中删除一个数据元素

只要将x的直接前驱元素q找到，然后对q的链接域作下述修改，即执行： q->link=current->link

的操作就可以删除结点p。实际上，它是将p的直接前驱结点q的链接指针直指p的直接后继元素结点。链表中的被删除结点从链表中断开后，还要将结点空间释放。

q p L ? ? ∧ ek-2 x ek en-2 e n-1 (b) 删除后 图2.3.4 删除链表中结点

1.5.3 单向循环链表的存储及其运算

若将最后一个结点的链接域值定义为指向开头（表头结点或第一个数据结点）。则形成一个环，称为单向循环链表或称为循环链表。如图2.5.1所示。

p L L ? e0 e1 e2 en-2 e n-1 图2.5.1 单向循环链表（循环至表头）及空表

特点：

表头指针指向第一结点，最后一个结点的指针不为空，指向表头结点。所有结点指针构成一个环。链表为空时，表头指针指向自身。

1.6 树与二叉树

1.6.1 树的基本概念

定义：一棵树是非空的有限元素的集合T，其中： ? 有一个元素称为该树的根（root）。

? 除根以外，其余元素（如果存在）分成k≥0个不相交的集合T1，T2，?，Tk 。而每一个集合Ti又都是树。树 T1，T2，……，Tk 称为根的子树。

树是一种简单的非线性结构 学院

工信金人会财法商息融文计税 学学学学学学学院 院院院院院院

计信统 算息计机 系系系

图5.1.1 一棵学院信息的

结点的度：一个结点的子树的个数称为该结点的度。即一个结点的分枝数。 树的度：树中各结点的度的最大值称为该树的度。 终端结点（叶子结点）：度为零的结点称为终端结点或叶结点。 分支结点：度不为零的结点称为分枝结点。

孩子和双亲：某结点的子树的根结点为该结点的孩子，反之该结点为孩子的双亲（也称

父亲或父结点）。

结点层次：树中的每个结点相对树的根结点都有一定的层次，我们定义： ? 树的根结点为第1层。

? 树中的其它结点都比它的父结点多一层。 树的深度（或高度）：树中结点的最大层次称为树的深度（或高度）。

第1层 A 第2层 B C D 第3层 E F G H

第4层 I 图5.1.2 树的层次

单目运算符：运算符只有一个运算对象，如 NOT； 双目运算符：运算符有二个运算对象，如 +，*； 双目运算符：运算符有三个运算对象，如 f(x,y,z)；

1.6.2二叉树定义及性质 1. 二叉树定义

一棵二叉树是有限元素的集合，它可以为空，当二叉树非空时，其中有一个称为二叉树根结点的元素，并且剩余的元素（如果存在）被分成两个不相交的子集，每个子集又是一棵二叉树，这两个子集被称为根的左子树和右子树。二叉树的每个元素被称为一个结点。

A B C

D E F

G

图5.2.1 一棵二叉树

2. 二叉树的定义与树的定义的区别 ? 二叉树存在着空树；但树不能为空。

? 二叉树中的每一个结点只可能有0个，1个或2个孩子，也就是说，二叉树不存在度大

于2的结点；而树中的每个结点可以有多个子树。

? 二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。 3. 满二叉树的定义

若二叉树中所有分枝结点的度数都为2，且叶子结点都在同一层上，则称这类二叉树为满二叉树。

A B D E F C G

一棵满二叉树是除了最深一层上有叶子结点外，其它层次上都是分枝结点。如图5.2.2所示。

4. 完全二叉树的定义

完全二叉树是指这样二叉树，除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

如果对满二叉树从上至下，从左至右地从1开始编号，如图5.2.3所示，如有一棵包含有n个结点的二叉树与这样一棵满二叉树对比，结果是每个结点都可以与满二叉树中编号为1至n的结点一一对应，则称这类二叉树为顺序二叉树，如图5.2.4所示。

8 9 10 11 12 13 14 15 4 5 6 7 2 3 1 图5.2.3 一棵从上至下，从左至右地从1开始编号的满二叉树 1 1 2 3 2 3 4 5 6 7 4 5 6 7 8 9 10 11 12 8 9 12 图5.2.4 一棵完全二叉树 图5.2.5 一棵非完全二叉树

满二叉树一定是完全二叉树，反之不然。 5. 退化二叉树的定义

如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子，则称这棵二叉树为退化的二叉树。如图5.2.8所示。

A 12

B 47 D 52 28 (a) (b) I

图5.2.8 退化的二叉树

二叉树的性质 1) 性质1

k-1

在二叉树的第 k 层上最多有2个结点（k≥1）。

2) 性质2

m

深度为m的二叉树至多有2-1个结点。 可以由性质1推出上述结论。显然，深度为h的二叉树的最大结点应为各层最大结点之和即为：

i?1?h（第i层上的最大结点数）=

i?1?h2=2-1

i-1h

3) 性质3

包括n（n>0）个元素的二叉树的边数为n-1。

证明：二叉树中每个元素（除根结点外）有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一条边，因此包含n个元素的二叉树的边数是n-1。

4) 性质4

对于任何一棵二叉树，若其终端结点数为n0，其度为2的结点数为n2，则有： n0=n2+1。 证明：设二叉树的度为1的结点数为n1，又由于二叉树中所有结点的度数都小于或等于2，所以其结点总数n应为：

n=n0+n1+n2 (5.1)

除根结点外其余结点都有一个枝进入，则二叉树中的分枝总数b为：

b=n-1 (5.2)

又由于度为1的结点发出一个枝，度为2的结点发出两个枝，所以有：

b=n1+2n2 (5.3) 从5.2式和5.3式得到n-1= n1+2n2，整理得

n=2n2+n1+1 (5.4)

由5.1式和5.4式整理后可得n0=n2+1，所以得证。 5) 性质5

若一棵满二叉树有n个结点，则其深度h应为：h=?log2n?+1 6) 性质6

一棵有n个结点的完全二叉树，如从左至右、从上至下的，对每个结点从1开始编号，对于其中任意编号为i的结点（1≤i≤n）有：

(1) 若i?1,则i的父亲是?i/2?；若i=1，则i是根结点，无父亲。 (2) 若2i≤n，则i的左孩子是2i；若2i>n，则i无左孩子。

(3) 若2i+1≤n，则i的右孩子是2i+1；若2i+1>n，则i无右孩子。 ?i/2? 152

i 17 85 i+1

2i 25 2i+1 7 77 2i+2

图5.2.9 顺序二叉树父子关系

1.6.3 二叉树的链式存储结构

由于二叉树的每个结点的最大度数为2，因此，统一给出二叉树的每个结点的模式，不管二叉树中结点的度数为0，为1还是为2，我们定义二叉树中的结点类型，如图5.3.7所示。

指向左孩子指针 结点信息值 指向右孩子指针

图5.3.7 二叉树链式结点结构

如二叉树的某个结点有左右孩子，则左右指针不空，如果二叉树的某个结点只有左或右孩子，则其右或左指针就为空，如果某个结点是叶子结点，则其左右指针都为空。

对于满二叉树或完全二叉树，可以按层序进行顺序存储，节省在存储空间。 1. 二叉树的前序、中序和后序遍历

所谓遍历，是指按一定的规律和秩序访问树中的每一个结点，且仅仅只访问一次，在访问每个结点时，可以修改它的内容，打印信息或做其它的工作。

为此，必须先对二叉树的各个结点按某种规律排序。若我们用L代表左孩子，R代表右孩子，D代表根结点，则二叉树有以下六种排序方法：

DLR（根左右），LDR（左根右），LRD（左右根） DRL（根右左），RDL（右根左），RDL（右根左）

为了简化，我们规定排序只能先左后右, 则只剩下三种排序方法： DLR（根左右），LDR（左根右），LRD（左右根）

如果再以根结点在排序中的位置来称呼这三种排序（遍历）方法，则有， ? DLR（根左右）称为前根排序（前序） ? LDR（左根右）称为中根排序（中序） ? LRD（左右根）称为后根排序（后序）

A 根 B C

D E F G 左子树 右子树 I J 图5.4.1 一棵二叉树

L M 图5.4.2 二叉树递归结构

在讨论二叉树的遍历时，一定要明白二叉树的递归性。遍历时，“根”不是唯一的，整棵二叉树有一个唯一的根，而每个子树（左了树和右子树）也有各自的一个根，即多级子树对应多个“根”；每遍历到某个“根”的孩子时，如果孩子本身又是一棵子树时，又需要将这棵孩子子树按遍历规则重新当作一棵树来遍历。

1) 前根排序（DLR）规则 首先访问二叉树的根结点，然后按前根遍历的规则访问其左子树，如果所有的左子树都已遍历，则按前根遍历的规则遍历右子树。按前根排序的规定，图5.4.1所示二叉树遍历结

果为：ABDIECFJGLM。

按照前序遍历规则：

首先访问根结点，然后遍历左子树，最后遍历右子树。 2) 中根排序（LDR）规则

首先按中根遍历的规则访问二叉树的左子树，如果左子树都已遍历，则访问左子树的根结点，然后，按中根遍历的规则访问二叉树的右子树。图5.4.1所示二叉树中根遍历结果为：DIBEAJFCLGM。

按照中序遍历规则：

首先遍历左子树，然后访问根结点，最后遍历右子树。 3) 后根排序（LRD）规则

首先按后根遍历的规则访问二叉树的左子树，如果左子树都已遍历，则按后根遍历的规则访问二叉树的右子树，然后，访问二叉树的根结点。图5.4.1所示二叉树后根遍历结果为：IDEBJFLMGCA。

按照后序遍历规则：

首先遍历左子树，然后访问根结点，最后遍历右子树。

1.7 查找技术

查找(Searching)是确定在数据元素集合（查找表）中是否存在一个数据元素关键字等于给定值关键字的过程。

查找的过程实际上是将给定值与记录集合中各记录的关键字相比较，从而确定给定值在记录集合中是否存在，以及存在时它在记录集合中的位置。

如果在记录集合中能找到与给定值相等的关键字，此时我们称该查找是成功，否则称该查找是失败的。 1.7.1 顺序查找

顺序查找的方法是，从顺序表的一端开始，用给定值的关键字逐个顺序地与表中各记录的关键字相比较，若在表中找到某个记录的关键字与给定值的关键字值相等，表明查找成功;若找遍了表中的所有记录，也未找到与给定值的关键字值相等的关键字，表明查找失败。当得到查找成功或失败的结论时，查找结束。

可见，顺序查找适用于表中数据元素无序或链表结构的情况。 时间复杂度:O(n/2) 1.7.2 二分法查找

二分查找又称为折半查找（Binary Search），是一种效率较高的有序顺序表上的查找方法。

设置三个变量low，high和mid，它们分别指向表的当前待查范围的下界、上界和中间位置。初始时，令low=1，high=n1，设待查数据元素的关键字为SearchKey。

(l)令mid=[low+hiqh]/2。（[]表示下限取整） (2)比较SearchKey与mid位置的值的大小，

若mid位置的值=SearchKey，则查找成功，结束查找;

若mid位置的值

若mid位置的值>SearchKey，表明关键字为SearchKey的记录只可能存在于记录mid的前半部，修改查找范围，令high=mid-1，变量low的值保持不变。

(3)比较当前变量low与high的值，若low≤high，重复执行第(1)和(2)步，若low>high，表明整个表已查找完毕，表中不存在关键字为SearchKey的记录，查找失败。

例9.2.1设顺序表中有15个记录，它们的关键字依次为：

{6，8，15，17，27，34，45，66，74，89，100，112，124，144，160}

用二分查找法在该顺序表中查找关键字为27（存在）和130（不存在）的记录。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

6 8 15 17 27 34 45 66 74 89 100 112 124 144 160

low mid high

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

6 8 15 17 27 34 45 66 74 89 100 112 124 144 160

low mid high

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

6 8 15 17 27 34 45 66 74 89 100 112 124 144 160

low mid high

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

6 8 15 17 27 34 45 66 74 89 100 112 124 144 160

low mid high

图9.2.1(a) 查找关键字为27的记录

时间复杂度:O(log2n)

1.8 排序技术

排序(sorting)是把一个无序的数据元素序列整理成有规律的按排序关键字递增(或递减)排列的有序序列的过程。

1.8.1 交换类排序法 1. 冒泡排序

冒泡排序:这种排序方法的基本思想是:

将待排序序列中第一位置的关键字R1.key与第二个位置的关键字R2.key作比较， 如果R1.key>R2.key，则交换记录R1和R2在序列中的位置，否则不交换； 然后继续对当前序列中的第二个记录和第三个记录作同样的处理，依次类推，直到序列中最后一个记录处理完为止，我们称这样的过程为一次冒泡排序。

通过第一次冒泡排序，最大（或最小）的记录排到了序列的最后一个位置上。然后对序列中的前n-1个记录重复进行冒泡排序，对于具有n个记录的序列，进行n-1次冒泡排序。

当进行某次冒泡排序时，若没有任何两个记录交换位置，则表明序列巳按记录关键字非递减的顺序排列，此时排序也可结束。

例 有八个记录，它们的初始关键字序列为{38,5,19,26,49,97,1,66},用冒泡排序法对它们进行排序。

该序列的冒泡排序过程如图8.4.1所示。 初始关键字序列: 38 5 19 26 49 97 1 66 第一次排序结果 5 19 26 38 49 1 66 [97] 第二次排序结果 5 19 26 38 1 49 [66 97] 第三次排序结果 5 19 26 1 38 [49 66 97] 第四次排序结果 5 19 1 26 [38 49 66 97] 第五次排序结果 5 1 19 [26 38 49 66 97] 第六次排序结果 1 5 [19 26 38 49 66 97] 第七次排序结果 1 5 19 26 38 49 66 97

2. 快速排序

快速排序(quick sort)又叫作分区交换排序，是目前已知的平均速度最快的一种排序方法，它是对冒泡排序方法的一种改进。快速排序方法的基本思想是:

从待排序的n个记录中任意选取一个记录Ri(通常选取序列中的第一个记录)作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri.key，排在Ri后面的记录的关键字都大于等于Ri.key，我们把这样的一个过程称作一次快速排序。在第一次快速排序中，确定了所选取的记录Ri 最终在序列中的排列位置，同时也把剩余的记录分成了两个子序列。分别进行快速排序，又确定了两个记录在序列中应处的位置。并将剩余记录分成了四个子序列。如此重复下去。当各个子序列的长度为1时。全部记录排序完毕。

60

(初始序列) 60 55 48 37 10 90 84 36

i j

(1) 36 55 48 37 10 90 84 □

i j

(2) 36 55 48 37 10 90 84 □

i j

(3) 36 55 48 37 10 90 84 □

j i

(4) 36 55 48 37 10 90 84 □

i j

(5) 36 55 48 37 10 90 84 □

i j

(6) 36 55 48 37 10 □ 84 90

i j

(7) 36 55 48 37 10 □ 84 90

i j

(8) 36 55 48 37 10 60 84 90

图8.4.2 第一次快速排序

初始关键字序列[60 55 48 37 10 90 84 36]

(1) [36 55 48 37 10] 60 [84 90]

(2) [10] 36 [48 37 55] 60 [84 90]

(3) 10 36 [37 48 55] 60 [84 90]

(4) 10 36 [37] 48 [55] 60 [84 90]

(5) 10 36 37 48 [55] 60 [84 90]

(6) 10 36 37 48 55 60 [84 90] (7) 10 36 37 48 55 60 84 [90] (8) 10 36 37 48 55 60 84 90 图8.4.3 快速排序

1. 简单（直接）插入排序

直接插入排序的基本思想是：顺序地把待排序序列中的各个记录按其关键字的大小，插入到已排序的序列的适当位置。

假设待排序序列为R1，R2，?，Rn，开始排序时，认为序列中第一个记录已排好序，它组成了排序的初始序列；

现将第二个记录的关键字与第一个记录的关键字进行比较，若R1.key＞ R2．key，则交换这两个记录的位置，否则不交换，这样就将第二个记录插入到了已排序的序列中。

依次类推，对序列中的第i个记录Ri排序时，Ri前面的i－1个记录已组成了有序序列R1'，R2'，?，Ri-1'，将Ri．key依次与Ri-1'.key，Ri-2'.key?进行比较，找出一个合适的j（1<=j<=i-1)，使得Ri-1'.key<=Ri.key

例 已知有6个待排序的记录，它们的关键字分别为65，4，8，78，6，26，用直接插入法进行排序。

初始关键字序列：[65] 4 8 78 6 26

第一次排序： [4 65] 8 78 6 26

第二次排序： [4 8 65] 78 6 26

第三次排序： [4 8 65 78] 6 26

第四次排序： [4 6 8 65 78] 26

第五次排序： [4 6 8 26 65 78]

图8.3.1 直接插入排序

2

直接插入排序的时间复杂度为O(n)或n(n+1)次比较。

2. 希尔排序

希尔（shell排序）又称作缩小增量排序，它的基本思想是：不断把待排序的记录分成若干个小组，对同一组内的记录进行排序，在分组时，始终保证当前组内的记录个数超过前面分组排序时组内的记录个数。

希尔排序具体的作法是：先设置一个整数量d1，称之为增量，将待排序的记录序列中所有距离为d1的记录放在同一组中。例如，若 d1=5，则记录R1,R6,R11?放在同一组中，记录R2,R7，R12?放在另一组中，如此类推。然后对各组内的记录分别进行排序，这样的一次分组排序过程称为一次排序。再设置另一个新的增量d2，使d2< d1，采用上述相同的方法继续进行第二次排序?如此进行下去，当最后一次排序时，设置的增量di=1时，表明序列中全部记录放在了同一组内，该次排序结束时，整个序列的排序工作完成。在希尔排序的各次排序过程中，组内记录的排序可以采用前面介绍的直接插入排序法，也可采用其他合适的方法。

例 设待排序的序列中有12个记录，它们的关键字分别为65，34，25，87，12，38，56， 46，14，77，92，23，用希尔排序法进行排序。

图8.3.2给出了该序列的希尔排序过程示意图，图中在同一连线上的关键字表示它们所属的记录放在同一组中。

缩小增量一般取: ht=n/2(k=1,2,,log2n)

1.5

次数接近于O(n) 初始关键字序列 65 34 25 87 12 38 56 46 14 77 92 23 65 34 25 87 12 38 56 46 14 77 92 23 结果序列 56 34 14 77 12 23 65 46 25 87 92 38 (a) 第一次排序 56 34 14 77 12 23 65 46 25 87 92 38 结果序列 56 12 14 65 34 23 77 46 25 87 92 38 (b) 第二次排序 56 12 14 65 34 23 77 46 25 87 92 38 (c) 第三次排序

图8.3.2 希尔排序

1.8.3 选择排序

选择排序的基本思想是:不断从待排序的序列中选取关键字最小的记录放到已排序的记录序列的后面，直到序列中所有记录都巳排序为止。

两种常用的选择排序方法是直接选择排序和堆排序。堆排序是一种时间复杂度为O(n(log2n))的排序方法。 1. 简单（直接）选择排序

直接选择排序(straight selection sort)是一种简单且直观的排序方法。直接选择排序的做法是:从待排序的所有记录中，选取关键字最小的记录并将它与原始序列中的第一个记录交换位置；然后从去掉了关键字最小的记录的剩余记录中，选择关键字最小的记录并将它与原始序列中第二个记录交换位置??如此重复下去，直到序列中全部记录排序完毕。

例 用直接选择法进行排序。

图8.5.1为直接选择排序过程示意图，其中方括号[]中为已排序的记录的关键字。

初始关键字序列: [65] 4 8 78 6 26

第一次排序结果: [4] 65 8 78 6 26

第二次排序结果: [4 6] 8 78 65 26

第三次排序结果: [4 6 8] 78 65 26

第四次排序结果: [4 6 8 26] 65 78

第五次排序结果: [4 6 8 26 65] 78

最后结果序列: [4 6 8 26 65 78]

图8.5.1 直接选择排序

k

2. 堆排序 堆树的定义

1. 最大树和最小树定义

52 8

30

30 50 52 20 12 17

17 5 4 52 50

5

(a) (b) (c)

52 52

30 52 30 52

17 5 4 17 5 4

(d) (e)

图5.7.5 最大树或最小树 堆树的定义

堆树简称为堆，是一棵二叉树。堆有如下特征： 堆树是一棵完全二叉树，如果一棵完全二叉树本身又满足最大树的条件，则这棵完全二叉树就是最大堆；如果一棵完全二叉树本身又满足最小树的条件，则这棵完全二叉树就是最小堆。

唯一满足堆树要求的是(d)所示的二叉树，它是一棵完全二叉树，且它满足最大树的概念，也就是说，它是最大堆。

堆排序问题是数据排序的一种经典方法。这种方法的思想是：

首先将堆顶元素（最大结点）移到结果数据存储空间，再从堆中余下的结点（左子树或右子树）中选出一个最大结点，移到堆顶，即将堆中余下的结点重新“调整”为一个新堆，再将堆顶结点移到结果数据存储空间的下一个空间位置，如此下去，直到所有的结点都被移到结果数据存储空间。那么，结果存储空间中的数据就是按从大至小的排列。

在堆排序中有两个关键的问题：实际中很难碰到一棵开始就是堆的树，如何构造一个初始堆树就是第一个关键问题；有了初始堆，在排序时，当移走根结点时，对余下的树又如何再“调整”为一棵新堆，这是第二个关键问题。

构造N所指结点为根的堆算法思想：

A. 先将N所指结点的值复制到一个工作空间中临时存放。

B. 再将N所指结点的孩子中，值较大的与工作空间中的值比较：

(1) 如果工作空间中值更大，新堆已经形成，就将工作空间中的值存放到N所指的

位置，结束。

C. 如果某个孩子的结点值更大，则将这个值存放到这个孩子双亲的结点位置，即N

位置。此时，工作空间中的结点还未找到存放位置，再将上移的孩子结点位置作为N所指的新位置，转到B步骤。

52 52

12 5 12 5

79 55 24 15 15 62 38 “当前”层→ 79

36 16 62 12 38 36 16 55 12 24

0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 52 12 5 79 55 24 15 36 16 62 12 38 52 12 5 79 62 38 15 36 16 55 12 24

(a) 原始堆树 (b) 调整“当前”层子树为

调整时从24开始，然后是55，79，? 三个子堆；38↑，62↑，79为根

图5.7.6 初始化堆过程

52 “当前”层→ 79

38 62 38 “当前”层→ 79

15 15 36 62 24 36 55 24

16 16 12 55 12 5 12 52 12 5

0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 79 62 38 36 55 24 15 12 16 52 12 5 52 79 38 36 62 24 15 12 16 55 12 5

(c) 调整“当前”层子树为 (d) 调整“当前”层子树为

二个子堆； 38↑，79↑为根 最后堆；79↑为根

图5.7.6 初始化堆过程

52 “当前”层→ 79 38 62 38 “当前”层→ 79 15 15 36 62 24 36 55 24 16 16 12 55 12 5 12 52 12 5 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 52 79 38 36 62 24 15 12 16 55 12 5 79 62 38 36 55 24 15 12 16 52 12 5

(d) 调整“当前”层子树为

(e) 调整“当前”层子树为

最后堆；79↑为根

二个子堆； 38↑，79↑为根

图5.7.6 初始化堆过程

堆排序

堆排序的过程，是利用删除堆顶结点来完成的。堆顶结点是整个堆中最大的一个结点，删除它的同时，将它移到另一个结果存储区中存放，然后，再将删除堆顶后的堆重新调整为一个堆。如果重复删除，移至结果区下一个存储空间存储，直到堆中的所有结点被全部删除，最后在结果存储区中的数据就是按从大至小地排列。

79 62

62 38 56 38

15 15 56 55 24 52 55 24

16 16 52 12 52 12 79

0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 79 62 38 56 55 24 15 12 16 52 52 62 56 38 52 55 24 15 12 16 79

(a) 原始堆 (b) 第一个堆顶移下

56 55

55 38 52 38

15 15 52 16 24 12 16 24

62 16 62 12 12 79 56 79

0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 16 56 55 38 52 16 24 15 12 62 79 12 55 52 38 12 16 24 15 56 62 79

(c) 第二个堆顶移下 (d) 第三个堆顶移下

图5.7.9 三个堆顶移下排序的过程

堆排序比较次数据为O（nlog2n）

本文来源：https://www.bwwdw.com/article/5m76.html