作者：whisper

链接：https://www.qingyu.blue/article/1060

声明：请尊重原作者的劳动，如需转载请注明出处

---

第1 章绪论

第1 章 绪论

1.1 数据结构的研究内容

1.2 基本概念和术语

1.3 抽象数据类型的表示与实现

1.1 数据结构的研究内容

N.沃思（Niklaus Wirth）教授提出：

程序=算法+数据结构

《数据结构》所处的地位：

介于数学、计算机硬件和计算机软件三者之间的 一门核心课程

1.2 基本概念和术语

（1）数据（data）—所有能输入到计算机中去的描述客观事物的符号

—数值性数据

—非数值性数据（多媒体信息处理）

（2）数据元素（data element）—数据的基本单位，也称结点（node）或记录（record）

（3）数据项（data item）—有独立含义的数据最小单位，也称域（field）

（4）数据对象（Data Object）：相同特性数据元素的集合，是数据的一个子集

整数数据对象

N = { 0，±1，±2，… }

学生数据对象

⑩学生记录的集合

（5）数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集

合。

数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关

系。

数据结构2+1（两个层次和一个操作）

逻辑结构

数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题

抽象出来的数学模型。

存储结构（物理结构）

数据元素及其关系在计算机存储器中的存储方式。

操作 （运算、行为）

执行不同功能的算法

划分方法一

（1）线性结构 ----

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后

继。

例如：线性表、栈、队列、串

（2）非线性结构 ----

一个结点可能有多个直接前趋和直接后继。

例如：树、图

划分方法二

集合 ——数据元素间除“同属于一个集合”外，无其它关系

线性结构 ——一个对一个，如线性表、栈、队列

树形结构 ——一个对多个，如树

图形结构 ——多个对多个，如图

存储结构分为：

顺序存储结构 ——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系

链式存储结构 ——借助指示元素存储地址的指针表示数据元素间的逻辑关系

索引存储结构 ——字典中单词存储关系

散列存储结构 ——地址与散列函数之间建立的一种映射

链式存储

数据类型

定义：在一种程序设计语言中，变量所具有的数据种类

C 语言：

基本数据类型： char int float double void

构造数据类型：数组、结构体、共用体、文件

数据类型是一组性质相同的值的集合， 以及定义于这个集合上的一组运算的总称

抽象数据类型

抽象数据类型 （ADTs: AbstractData Types）

—更高层次的数据抽象

—由用户定义，用以表示应用问题的数据模型

—由基本的数据类型组成， 并包括一组相关的操作

抽象数据类型可以用以下的三元组来表示：

说明：抽象数据类型的表示与实现

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。

如何学习抽象数据类型？

1.3 算法和算法分析

算法定义

一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列

算法的特性

输入 有0 个或多个输入

输出 有一个或多个输出（处理结果）

确定性 每步定义都是确切、无歧义的

有穷性 算法应在执行有穷步后结束

有效性 每一条运算应足够基本

算法设计的评价

正确性

可读性

健壮性

高效性 （时间代价和空间代价）

算法效率的度量

算法效率：时间和空间来度量

时间复杂度

空间复杂度

算法效率的度量：时间复杂度

算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量

事后统计

事前分析估计

方式1.事后统计 ：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同

的统计数据区分

缺点：

①必须先运行依据算法编制的程序

②所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的劣

方式2.事前分析估计 ：

一个高级语言程序在计算机上运行所消耗的时间取决于：

①依据的算法选用何种策略

②问题的规模

③程序语言

④编译程序产生机器代码质量

⑤机器执行指令速度

时间复杂度的渐进表示法

一般情况下，算法中基本操作重复执行的时间是问题规模n 的某个函数f（n），算法

执行的时间的增长率和f（n）的增长率相同，称渐近时间复杂度。

时间复杂度的表示方法有两种：

方法1：大O 法 T（n） = O（f（n））

它表示随问题规模n 的增大，算法执行时间的增长率和f（n）的增长率相同，称作算

法的渐进时间复杂度，简称时间复杂度。

方法2：语句频度法

计算该语句重复执行的次数，又叫频度统计法。

说明：

数学符号“O”的定义为：若T（n）和f（n）是定义在正整数集合上的两个函数，则

T（n）= O（f（n））表示存在正的常数C 和n0，使得当n≥n0 时都满足

0≤T（n）≤Cf（n）。

n * n 阶矩阵加法：

for（ i = 0; i < n; i++）

for（ j = 0; j < n; j++）

c[i][j] = a[i][j] + b[i][j];

语句的频度（Frequency Count ）: 重复执行的次数：

n*n;

T（n）= O（n^2）

即：矩阵加法的运算量和问题的规模n 的平方是同一个量级

分析算法时间复杂度的基本方法

找出语句频度最大的那条语句作为基本语句

计算基本语句的频度得到问题规模n 的某个函数f（n）

取其数量级用符号“O”表示

for （ int i = 0; i < n; i++ ）

for （ int j = 0; j < n; j++ ）

y ++;

f（n）=n^2

T（n）= O（n^2）

引例与分析

1）{++x; s=0;}

++x 的频度为1

2）for （i=1; i<=n; ++i） {++x; s+=x;}

++x 的频度为n

3）for （j=1;j<=n;++j）

for （k=1;k<=n;++k） {++x; s+=x;}

++x 的频度为n^2

时间复杂度是由嵌套最深层语句的频度决定的

算法效率的度量：空间复杂度

（1）定义

（2）三个组成部分

存储算法本身所占用的空间

算法的输入/输出数据占用的空间

算法在运行过程中临时占用的辅助空间

（3）原地工作 ：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。

说明：若所占空间量依赖于特定的输入，按最坏情况来分析

算法设计的要求

（1）正确性

（2）可读性

首先是给人读，然后才是机器执行

（3）健壮性，容错性

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

重点1：基本术语：数据结构

重点2：抽象数据类型

重点3：算法优劣的评价标准

重点4：数据结构的学习方法

重点3：算法优劣的评价标准：时间复杂度

（1）当f（n）为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受

的，称这些算法是有效算法；当f（n）为指数函数或阶乘函数时，算法的运行时间是不可

接受的，称这些算法是无效的算法。

（2）随着n 值的增大，增长速度各不相同，n 足够大时，存在下列关系：

对数函数<幂函数<指数函数

常见函数的增长率

增长率由慢到快

尽量少用指数阶的算法

第2 章 线性表

线性结构的定义

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最

多只有一个直接前趋和一个直接后继。

可表示为：（a1，a2，……，an）

线性结构表达式：（a1，a2，……，an）

线性结构的特点

① 只有一个首结点和尾结点；

② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。

线性结构反映结点间的逻辑关系是一对一

线性结构包括线性表 、堆栈 、队列 、字符串 、数组 等等。

其中，最典型、最常用的是 线性表

线性表的定义和特点

线性表的定义：用数据元素的有限序列表示

例如：分析26 个英文字母组成的英文表

（ A，B，C，D，……，Z）

数据元素都是字母; 元素间关系是线性

同一线性表中的元素必定具有相同特性

2.2 案例引入

案例2.1 ：一元多项式的运算

案例2.2：稀疏多项式的运算

多项式非零项的数组表示

2.3 线性表的类型定义

线性表的类型定义

线性表的顺序存储

线性表的链式存储

线性表的重要基本操作

1. 初始化 2.取值 3. 查找 4. 插入 5. 删除

2.4 线性表的顺序表示和实现

线性表的顺序表示又称为顺序存储结构或顺序映像。

顺序存储 定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结

构。

简言之，逻辑上相邻，物理上也相邻

顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]

来实现。

顺序表的类型定义

#defineMAXSIZE 100 //最大长度

typedef struct {

ElemType *elem; //指向数据元素的基地址

int length; //线性表的当前长度

}SqList；

以图书表的顺序存储结构类型为例

#define MAXSIZE 10000 //图书表可能达到的最大长度

typedef struct //图书信息定义

{

char no[20]; //图书ISBN

char name[50]; //图书名字

float price; //图书价格

}Book;

typedef struct

{

Book *elem; //存储空间的基地址

int length; //图书表中当前图书个数

}SqList; //图书表的顺序存储结构类型为SqList

2.4 线性表的顺序表示和实现

线性表的重要基本操作

1. 初始化
2. 取值
3. 查找
4. 插入
5. 删除

重要基本操作的算法实现

初始化 线性表L（参数用引用）

Status InitList_Sq（SqList &L）{ //构造一个空的顺序表L

L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间

if（!L.elem） exit（OVERFLOW）; //存储分配失败

L.length=0; //空表长度为0

return OK;

}

初始化 线性表L （参数用指针）

Status InitList_Sq（SqList *L）{ //构造一个空的顺序表L

L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间

if（! L-> elem） exit（OVERFLOW）; //存储分配失败

L-> length=0; //空表长度为0

return OK;

}

补充：几个简单基本操作的算法实现

销毁 线性表L

void DestroyList（SqList &L）

{

if （L.elem） delete[]L.elem; //释放存储空间

}

清空 线性表L

void ClearList（SqList &L）

{

L.length=0; //将线性表的长度置为0

}

求线性表L 的长度

int GetLength（SqList L）

{

return （L.length）;

}

判断线性表L 是否为空

int IsEmpty（SqList L）

{

if （L.length==0） return 1;

else return 0;

}

取值 （根据位置i 获取相应位置数据元素的内容）

获取线性表L 中的某个数据元素的内容

int GetElem（SqList L，int i，ElemType &e）

{

if （i<1||i>L.length） return ERROR;

//判断i 值是否合理，若不合理，返回ERROR

e=L.elem[i-1]; //第i-1 的单元存储着第i 个数据

return OK;

查找 （根据指定数据获取数据所在的位置）

顺序查找图示

在线性表L 中查找值为e 的数据元素

int LocateELem（SqList L，ElemType e）

{

for （i=0;i< L.length;i++）

if （L.elem[i]==e） return i+1;

return 0;

}

查找算法时间效率分析 ？？？

插入 （插在第 i 个结点之前）

插第 4 个结点之前，移动6－4+1 次

插在第 i 个结点之前，移动 n-i+1 次

【算法步骤】

（1）判断插入位置i 是否合法。

（2）判断顺序表的存储空间是否已满。

（3）将第n 至第i 位的元素依次向后移动一个位置，空出第i 个位置。

（4）将要插入的新元素e 放入第i 个位置。

（5）表长加1，插入成功返回OK

【算法描述】

在线性表L 中第i 个数据元素之前插入数据元素e

Status ListInsert_Sq（SqList &L，int i ，ElemType e）{

if（i<1 || i>L.length+1） return ERROR; //i 值不合法

if（L.length==MAXSIZE） return ERROR; //当前存储空间已满

for（j=L.length-1;j>=i-1;j--）

L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移

L.elem[i-1]=e; //将新元素e 放入第i 个位置

++L.length; //表长增1

return OK;

}

【算法分析】

算法时间主要耗费在移动元素的操作上

若插入在尾结点之后，则根本无需移动（特别快）；

若插入在首结点之前，则表中元素全部后移（特别慢）；

若要考虑在各种位置插入（共n+1 种可能）的平均移动次数，该如何计算？

删除 （删除第 i 个结点）

删除第 4 个结点，移动 6－4 次

删除第 i 个结点，移动 n-i 次

【算法描述】

将线性表 L 中第 i 个数据元素删除

Status ListDelete_Sq（SqList &L，int i）{

if（（i<1）||（i>L.length）） return ERROR; //i 值不合法

for （j=i;j<=L.length-1;j++）

L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移

--L.length; //表长减 1

return OK;

}

【算法分析】

算法时间主要耗费在移动元素的操作上

若删除尾结点，则根本无需移动（特别快）；

若删除首结点，则表中 n-1 个元素全部前移（特别慢）；

若要考虑在各种位置删除（共n 种可能）的平均移动次数，该如何计算？

查找、插入、删除算法的平均时间复杂度为O（n）

显然，顺序表的空间复杂度S（n）=O（1）

（没有占用辅助空间）

顺序表（顺序存储结构）的特点

（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性

表的逻辑结构与存储结构一致

（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以

粗略地认为，访问每个元素所花时间相等

这种存取元素的方法被称为随机存取法

顺序表的优缺点

优点：

存储密度大（结点本身所占存储量/结点结构所占存储量）

可以随机存取表中任一元素

缺点：

在插入、删除某一元素时，需要移动大量元素

浪费存储空间

属于静态存储形式，数据元素的个数不能自由扩充

为克服这一缺点 链表

2.5 线性表的链式表示和实现

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像。

例 画出26 个英文字母表的链式存储结构

逻辑结构：（a，b，…，y，z）

链式存储结构：

各结点由两个域组成：

数据域 ：存储元素数值数据

指针域 ：存储直接后继结点的存储位置

与链式存储有关的术语

（1）结点 ：数据元素的存储映像。由数据域和指针域两部分组成

（2）链表 ： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线

性表的链式存储结构

（3）单链表 、双链表 、循环链表 ：

结点只有一个指针域的链表，称为单链表或线性链表

有两个指针域的链表，称为双链表

首尾相接的链表称为循环链表

循环链表示意图：

（4）头指针、头结点和首元结点

头指针 是指向链表中第一个结点的指针

首元结点 是指链表中存储第一个数据元素a1 的结点

头结点 是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息

讨论1. 如何表示空表？

有头结点时，当头结点的指针域为空时表示空表

讨论2. 在链表中设置头结点有什么好处？

第一：便于首元结点的处理

首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它

位置一致，无须进行特殊处理;

第二：便于空表和非空表的统一处理

无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也

就统一了。

讨论3. 头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表

长度值。

链表的优缺点

优点

—数据元素的个数可以自由扩充

—插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点

—存储密度小

—存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行

访问（顺藤摸瓜）

2.5.1 单链表的定义和实现

非空表

空表 L

单链表的存储结构定义

typedef struct LNode{

ElemType data ; //数据域

struct LNode *nex t ; //指针域

}LNode，*LinkList; / / *LinkList为 Lnode类型的指针

LNode *p LinkList p

注意区分指针变量和结点变量两个不同的概念

LNode *p

p：表示什么？

*p：表示什么？

若p->data=ai， 则p->next->data=？

注意区分指针变量和结点变量两个不同的概念

LNode *p

•指针变量p：表示结点地址

•结点变量*p：表示一个结点

若p->data=ai， 则p->next->data= ai+1

2.5.2 单链表基本操作的实现

（1）初始化

（2）取值

（3）查找

（4）插入

（5）删除

（1） 初始化（构造一个空表 ）

【算法步骤】

（1）生成新结点作头结点

（2）用头指针L 指向头结点

（3）头结点的指针域置空

【算法描述】

Status InitList_L（LinkList &L）

{

L=new LNode;

L->next=NULL;

return OK;

}

补充：几个简单基本操作的算法实现

第一：销毁

Status DestroyList_L（LinkList &L）{

LinkList p;

while（L）

{

p=L;

L=L->next;

delete p;

}

return OK;

}第二：清空 // 将L 重置为空表

Status ClearList（LinkList & L）{

LinkList p，q;

p=L->next; //p 指向第一个结点

while（p）

{ q=p->next; delete p; p=q; }

L->next=NULL; //头结点指针域为空

return OK;

}

第三：求表长

intListLength_L（LinkList L）{

//返回L 中数据元素个数

LinkList p;

p=L->next;

i=0;

while（p）{

i++;

p=p->next; }

return i;

}

第四：判断表是否为空

int ListEmpty（LinkList L）{

//若L 为空表，则返回1，否则返回0

if（L->next） //非空

return 0;

else

return 1;

}

（2） 取值 （根据位置i 获取相应位置数据元素的内容）

//获取线性表L 中的某个数据元素的内容

Status GetElem_L（LinkList L，int i，ElemType &e）{

p=L->next; j=1; //初始化

while（p&&j<i）{ //向后扫描，直到p 指向第i 个元素或p 为空

p=p->next; ++j;

}

if（!p || j>i）return ERROR; //第i 个元素不存在

e=p->data; //取第i 个元素

return OK;

}//GetElem_L

（3）查找（根据指定数据获取数据所在的位置）

//在线性表L 中查找值为e 的数据元素

LNode *LocateELem_L （LinkList L，Elemtype e） {

//返回L 中值为e 的数据元素的地址，查找失败返回NULL

p=L->next;

while（p &&p->data!=e）

p=p->next;

return p;

}

【算法描述】

//在线性表L 中查找值为e 的数据元素

int LocateELem_L （LinkList L，Elemtype e） {

//返回L 中值为e 的数据元素的位置序号，查找失败返回0

p=L->next; j=1;

while（p &&p->data!=e）

{p=p->next;j++; }

if（p） return j;

else return 0;

}

（4） 插入 （插在第 i 个结点之前）

//在L 中第i 个元素之前插入数据元素e

Status ListInsert_L（LinkList &L，int i，ElemType e）{

p=L;j=0;

while（p&&j<i−1）{p=p->next;++j;} //寻找第i−1 个结点

if（!p||j>i−1）return ERROR; //i 大于表长+ 1 或者小于1

s=new LNode; //生成新结点s

s->data=e; //将结点s 的数据域置为e

s->next=p->next; //将结点s 插入L 中

p->next=s;

return OK;

}//ListInsert_L

（5） 删除 （删除第 i 个结点）

找到ai-1 存储位置p

临时保存结点ai 的地址在q 中，以备释放

令p->next 指向ai 的直接后继结点

将ai 的值保留在e 中

释放ai 的空间

【算法描述】

//将线性表L 中第i 个数据元素删除

Status ListDelete_L（LinkList &L，int i，ElemType &e）{

p=L;j=0;

while（p->next &&j<i-1）{//寻找第i 个结点，并令p 指向其前驱

p=p->next; ++j;

}

if（!（p->next）||j>i-1） return ERROR; //删除位置不合理

q=p->next; //临时保存被删结点的地址以备释放

p->next=q->next; //改变删除结点前驱结点的指针域

e=q->data; //保存删除结点的数据域

delete q; //释放删除结点的空间

return OK;

} //ListDelete_L

链表的运算时间效率分析

（1）查找:因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂

度为O（n）。

（2）插入和删除:因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂

度为 O（1）。

但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间

复杂度为O（n）

单链表的建立（前插法 ）

从一个空表开始，重复读入数据：

—生成新结点

—将读入数据存放到新结点的数据域中

—将该新结点插入到链表的前端

单链表的建立（前插法）

【算法描述】

void CreateList_F（LinkList &L，int n）{

L=new LNode;

L->next=NULL; //先建立一个带头结点的单链表

for（i=n;i>0;--i）{

p=new LNode; //生成新结点

cin>>p->data; //输入元素值

p->next=L->next; L->next=p; //插入到表头

}

}//CreateList_F

单链表的建立（尾插法 ）

从一个空表L 开始，将新结点逐个插入到链表的尾部，尾指针r 指向链表的尾结点。

初始时，r 同L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插

入到尾结点后，r 指向新结点。

【算法描述】

void CreateList_L（LinkList &L，int n）{

//正位序输入n 个元素的值，建立带表头结点的单链表L

L=new LNode;

L->next=NULL;

r=L; //尾指针r 指向头结点

for（i=0;i<n;++i）{

p=new LNode; //生成新结点

cin>>p->data; //输入元素值

p->next=NULL; r->next=p; //插入到表尾

r=p; //r 指向新的尾结点

}

}//CreateList_L

2.5.3 循环链表

（a） 非空单循环链表

（b） 空表

说明 从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不

到；

说明对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后

一个结点

如何查找开始结点和终端结点？

示例：循环链表的合并

示例： 循环链表的合并

LinkList Connect（LinkList Ta，LinkList Tb）

{//假设Ta、Tb 都是非空的单循环链表

p=Ta->next; //①p 存表头结点

Ta->next=Tb->next->next; //②Tb 表头连结Ta 表尾

deleteTb->next; //③释放Tb 表头结点

Tb->next=p; //④修改指针

returnTb;

}

2.5.4 双向链表

typedef struct DuLNode{

ElemType data;

struct DuLNode *prior;

struct DuLNode *next;

}DuLNode， *DuLinkList

（a）空双向循环链表

（b） 双向循环链表

d->next->prior = L->prior->next = L

双向链表的插入

双向链表的插入

（1）s->prior=p->prior;

（2）p->prior->next=s;

（3）s->next=p;

（4）p->prior=s;

双向链表的删除

双向链表的删除

p->prior->next=p->next;

p->next->prior=p->prior;

双向链表的删除

Status ListDelete_DuL（DuLinkList &L，int i，ElemType &e）{

if（!（p=GetElemP_DuL（L，i））） return ERROR;

e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

delete p;

return OK;

}

2.6 顺序表和链表的比较

2.7 线性表的应用

应用1：线性表的合并

应用2：有序表的合并

应用3：有序链表的合并

2.7.1 顺序表的合并

应用1：问题描述： 假设利用两个线性表La 和Lb 分别表示两个集合A 和B，现要

求一个新的集合

A=A∪B

La=（7， 5， 3， 11）

Lb=（2， 6， 3）

La=（7， 5， 3， 11， 2， 6）.

【算法步骤】

依次取出Lb 中的每个元素，执行以下操作：

在La 中查找该元素

如果找不到，则将其插入La 的最后

O（ListLength（LA）× ListLength（LB））

【算法步骤】

依次取出Lb 中的每个元素，执行以下操作：

在La 中查找该元素

如果找不到，则将其插入La 的最后

【算法描述】

定义了一个SqList，作为把SqList 当成一个数据类型，它有相应的运算

【算法步骤】【算法描述】

依次取出Lb void union（SqList &La， SqList Lb）{

中的每个元素， La_len=ListLength（La）;

执行以下操作： Lb_len=ListLength（Lb）;

在La 中查找 for（i=1;i<=Lb_len;i++）{

该元素 GetElem（Lb，i，e）;

如果找不到， if（!LocateElem（La，e））

则将其插入 La ListInsert（&La，++La_len，e）;

的最后 }

}

2.7.2 有序表的合并

应用2：问题描述： 已知线性表La 和Lb 中的数据元素按值非递减有序排列，现要

求将La 和Lb 归并为一个新的线性表Lc，且Lc 中的数据元素仍按值非递减有序排列.

La=（1 ，7， 8）

Lb=（2， 4， 6， 8， 10， 11）

Lc=（1， 2， 4， 6， 7 ， 8， 8， 10， 11）.

【算法描述】

void union（SqList &La， SqList Lb）

{

}

【算法步骤】－有序的顺序表合并

（1） 创建一个空表Lc

（2） 依次从La 或 Lb 中“摘取”元素值较小的结点插入到Lc 表的最后，直至其

中一个表变空为止

（3） 继续将La 或 Lb 其中一个表的剩余结点插入在Lc 表的最后

时间复杂度？

【算法步骤】－有序的顺序表合并

（1） 创建一个空表Lc

（2） 依次从La 或 Lb 中“摘取”元素值较小的结点插入到Lc 表的最后，直至其

中一个表变空为止

（3） 继续将La 或 Lb 其中一个表的剩余结点插入在Lc 表的最后

时间和空间复杂度？

【算法描述】－有序的顺序表合并

T（n）= O（ListLength（LA） + ListLength（LB））

S（n）= O（n）

应用3：有序链表合并－－重点掌握

—将这两个有序链表合并成一个有序的单链表。

—要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。

—表中允许有重复的数据。

【算法描述】－有序的链表合并

void MergeList_L（LinkList &La，LinkList &Lb，LinkList &Lc）{

pa=La->next; pb=Lb->next;

pc=Lc=La; //用 La 的头结点作为 Lc 的头结点

while（pa && pb）{

if（pa->data<=pb->data）{pc->next=pa;pc=pa;pa=pa-

next;}

else{pc->next=pb; pc=pb; pb=pb->next;}

pc->next=pa?pa:pb; //插入剩余段

delete Lb; //释放 Lb 的头结点

}

T（n）= O（ListLength（LA） + ListLength（LB））

S（n）= O（1）

两道思考题：

问题 1：要求合并后的表无重复数据，如何实现？

提示：要单独考虑

pa->data = =pb->data

问题2：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？

要求结果链表仍使用原来两个链表的存储空间， 不另外占用其它的存储空间。

表中允许有重复的数据。

疑问：那就两两比较“摘取”大的元素不就行了？

【算法步骤】

（1）Lc 指向La

（2） 依次从La 或 Lb 中“摘取”元素值较小的结点插 入到Lc 表的表头结点之后，

直至其中一个表变空为止

（3） 继续将La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后

（4） 释放Lb 表的表头结点

作业：

【算法描述】

【时间与空间复杂度】

2.8 案例分析与实现

案例2.1 ：一元多项式的创建

P（x） = 10 + 5x - 4 x2 + 3 x3 + 2 x4

数组表示

（每一项的指数i 隐含在其系数pi 的序号中）

如何创建一元多项式？

案例 2.3： 图书信息管理系统，如何管理数据和组织数据

图书顺序表

小结

重点1：掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表

示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。

重点2：熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元

结点的区别及循环链表、双向链表的特点等。

重点3：熟练掌握顺序表的查找、插入和删除算法

重点4：熟练掌握链表的查找、插入和删除算法

重点5：能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

第3 章 栈和队列

3.1 栈（Stack）

（1）定义

（2）逻辑结构

（3）存储结构

（4）运算规则

（5）主要操作 （5）主要操作

3.1.1 栈的定义和特点

（1） 定义 只能在表的一端（栈顶）进行插入和删除运算的线性表

（2）逻辑结构 与线性表相同，仍为一对一关系

（3）存储结构 用顺序栈或链栈存储均可，但以顺序栈更常见

（4）运算规则 只能在栈顶运算，且访问结点时依照后进先出 （LIFO）或先进后出

（FILO）的原则

（5）主要操作 入栈 和出栈 函数，具体实现依顺序栈 或链栈 的不同而不同

基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

3.1.2 栈的表示和操作实现

“进”＝压入=PUSH（）

“出”＝弹出=POP（ ）

顺序栈的表示

top 指示真正的栈顶元素之上的下标地址栈满时的处理方法：

1、报错，返回操作系统。

2、分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

第一种存储结构：顺序栈 的表示

#define MAXSIZE 100

typedef struct

{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

操作1：顺序栈初始化（构造一个空栈）

【算法步骤】

（1）分配空间并检查空间是否分配失败，若失败则返回错误

（2）设置栈底和栈顶指针

S.top = S.base;

（3）设置栈大小

【算法描述】顺序栈初始化

Status InitStack（ SqStack &S ）

{

S.base =new SElemType[MAXSIZE]；

if（ !S.base ） return OVERFLOW;

S.top = S.base;

S.stackSize = MAXSIZE;

return OK;

}

操作2：判断顺序栈是否为空

【算法步骤】

判断顶与底两个指针是否相等

【算法描述】判断顺序栈是否为空

bool StackEmpty（ SqStack S ）

{

if（S.top == S.base） return true;

else return false;

}

操作3：求顺序栈的长度

【算法步骤】

栈顶和栈底两个指针相减

【算法描述】求顺序栈的长度

int StackLength（ SqStack S ）

{

return S.top – S.base;

}

操作4：清空 顺序栈

【算法步骤】

让栈顶和栈底有相同指向，都指向栈底

【算法描述】清空顺序栈

Status ClearStack（ SqStack S ）

{

if（ S.base ） S.top = S.base;

return OK;

}

操作5：销毁 顺序栈

【算法步骤】

（1）释放所有内存空间

（2）顺序栈的三个成员变量要置零

销毁顺序栈

Status DestroyStack（ SqStack &S ）{

if（ S.base ）

{

delete S.base ;

S.stacksize = 0;

S.base = S.top = NULL;

}

return OK;

}

操作6： 顺序栈进栈

【算法步骤】

（1）判断是否栈满，若满则出错top

（2）元素e 压入栈顶

（3）栈顶指针加1

【算法描述】顺序栈进栈

Status Push（ SqStack &S， SElemType e）

{

if（ S.top - S.base== S.stacksize ） // 栈满

return ERROR;

*S.top++=e;

return OK;

}

操作7： 顺序栈出栈

【算法步骤】

（1）判断是否栈空，若空则出错

（2）获取栈顶元素 e

（3）栈顶指针减 1

【算法描述】顺序栈出栈

Status Pop（ SqStack &S， SElemType &e）

{

if（ S.top == S.base ） // 栈空

return ERROR;

e＝ *--S.top;

return OK;

}

操作8： 取顺序栈栈顶元素

【算法步骤】

（1） 判断是否空栈，若空则返回错误

（2） 否则通过栈顶指针获取栈顶元素

【算法描述】取顺序栈栈顶元素

Status GetTop（ SqStack S， SElemType &e）

{

if（ S.top == S.base ） return ERROR; // 栈空

e = *（ S.top – 1 ）;

return OK;

}

第二种存储结构：链栈 的表示

运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针

就是链表的头指针

typedef struct StackNode {

SElemType data;

struct StackNode *next;

} StackNode，*LinkStack;

LinkStack S;

操作1：链栈的初始化 （构造一个空栈）

【算法步骤】

【算法描述】链栈的初始化

void InitStack（LinkStack &S ）

{

S=NULL;

}

操作2：判断链栈是否为空

【算法步骤】

（1）链栈为空返回真，否则返回假

【算法描述】判断链栈是否为空

Status StackEmpty（LinkStack S）

{

if （S==NULL） return TRUE;

else return FALSE;

}

操作3：链栈进栈

【算法步骤】

（1）申请一个结点，由p 指向

（2）如果申请成功

（3）进栈

读入元素

先连指针

再修改栈顶指针

【算法描述】链栈进栈

Status Push（LinkStack &S ，SElemType e）

{

p=new StackNode;

if （!p） exit（OVERFLOW）;

p->data=e;

p->next=S;

S=p;

return OK;

}

操作4：链栈出栈

【算法步骤】

（1）判断栈是否为空

（2）出栈

（3）修改栈顶指针，并删除原来栈顶指针

【算法描述】链栈出栈

Status Pop （LinkStack &S，SElemType &e）

{if （S==NULL） return ERROR;

e = S-> data;

p = S;

S =S-> next;

delete p; return OK;}

操作5：取链栈栈顶元素

【算法步骤】

（1）判断栈是否为空

（2）如果不空，读取栈顶元素

【算法描述】取链栈栈顶元素

SElemType GetTop（LinkStack S）

{

if （S==NULL） exit（1）；

else return S–>data;

}

3.1.3 栈与递归

递归 的定义 若一个对象部分地包含它自己，或用 它自己给自己定义，则称这个对

象是递归的；若一个过程直接地或间接地调用自己， 则称这个过程是递归的过程。

long Fact （ long n ） {

if （ n == 0） return 1;

else return n * Fact （n-1）; }

递归举例：

2 阶Fibonaci 数列:

求解递归问题方法

分治 法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的

子问题来求解

必备的三个条件

（1）能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同

的仅是处理的对象，且这些处理对象是变化有规律的

（2）可以通过上述转化而使问题简化

（3）必须有一个明确的递归出口，或称递归的边界

分治法求解递归问题算法的一般形式：

void p （参数表） {

if （递归结束条件）可直接求解步骤；-----基本项

elsep（较小的参数）；------归纳项

}

long Fact （ long n ） {

if （ n == 0） return 1; //基本项

else return n * Fact （n-1）; //归纳项

}

求解阶乘n! 的过程

if （n == 0）

return 1;

else return n * Fact （n-1）;

举例1： 设有一个递归算法如下:

int X（int n）

{ if（n<=3） return 1;

else return X（n-2）+X（n-4）+1

}

则计算X（X（8））时需要计算X 函数______次.

A. 8 B.9 C.16 D.18

举例2

如果一个栈的输入序列为123456，

能否得到435612 和135426 的出栈序列？

举例3：

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，

若p1=n，则pi 为 C

Ａ．i Ｂ．n-I Ｃ．n-i+1 Ｄ．不确定

3.2 队列（Queue）

（1）定义

（2）逻辑结构

（3）存储结构

（4）运算规则

（5）主要操作

队列 是一种先进先出（FIFO） 的线性表.在表一端插入，在另一端删除

3.2.1 栈和队列的定义和特点

（1） 定义只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线

性表

（2） 逻辑结构 与线性表相同，仍为一对一关系

（3） 存储结构用顺序队列或链队存储均可

（4）运算规则 先进先出（FIFO）

（5）主要操作入队和出队函数，具体实现依顺序队或链队的不同而不同

栈、队列与一般线性表的区别

栈、队列是一种特殊（操作受限）的线性表

区别：仅在于运算规则不同

3.2.2 队列的表示和操作的实现

举例1：

设栈S 和队列Q 的初始状态为空，元素e1、e2、e3、e4、e5 和e6 依次通过S，一个

元素出栈后即进入Q，若6 个元素出队的序列是e2、e4、e3、e6、e5 和e1，则栈S 的容

量至少应该是（ ）。

（A）2 （B）3 （C）4 （D）6

队列的抽象数据类型

ADT Queue {

数据对象: D={ai | ai∈=ElemSet，i=1，2，…，n，n≥0}

数据关系: R1={<ai −1，ai > | ai-1,ai∈D，i=1，2，…， n}

基本操作: 约定a1 端为队列头，an 端为队列尾

（1） InitQueue （&Q） //构造空队列

（2） DestroyQueue （&Q）//销毁队列

（3） ClearQueue （&S） //清空队列

（4） QueueEmpty（S） //判空. 空--TRUE，

队列的抽象数据类型

（5） QueueLength（Q） //取队列长度

（6） GetHead （Q，&e） //取队头元素，

（7） EnQueue （&Q，e） //入队列

（8） DeQueue （&Q，&e） //出队列

（9） QueueTraverse（Q，visit（）） //遍历

}ADT Queue

栈的抽象数据类型

ADT Stack {

数据对象:

数据关系:

基本操作:

} ADT Stack

第一种存储结构：顺序队列的表示－－用一维数组base[M]

#define M 100 //最大队列长度

Typedef struct {

QElemType*base; //初始化的动态分配存储空间

int front; //头指针

int rear; //尾指针

}SqQueue;

第一种存储结构：顺序队列 的表示－－用一维数组base[M]

front=rear=0

空队标志：front= =rear. 入队：base[rear++]=x;

出队：x=base[front++];

存在的问题： 设大小为M

front=0 front=0

rear=M 时 rear=M 时

再入队—真溢出 再入队—假溢出

解决的方法－－循环队列

base[0]接在base[M-1]之后

若rear+1==M

则令rear=0;

第二种存储结构：循环队列 ——顺序循环队列

#define MAXQSIZE 100 //最大长度

Typedef struct {

QElemType*base; //初始化的动态分配存储空间

int front; //头指针

int rear; //尾指针

}SqQueue;

操作1：循环队列初始化

【算法步骤】

（1）申请一个空队

（2）设置空队的队首、队尾标志

【算法描述】循环队列初始化

Status InitQueue （SqQueue &Q）{

Q.base =new QElemType[MAXQSIZE]

if（!Q.base） exit（OVERFLOW）;

Q.front=Q.rear=0;

return OK;

}

操作2：求循环队列的长度

【算法步骤】

（1）实际长度

（2）最大长度

（3）循环队列为空

（4）循环队伍为满

（5）循环队列入队

（6）循环队列出队

【算法描述】求循环队列的长度

int QueueLength （SqQueue Q）{

return （Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;

}

操作3： 循环队列入队

【算法设计步骤】

（1）满队不能入队

（2）队尾入队

（3）队尾指针移动

【算法描述】循环队列入队

Status EnQueue（SqQueue&Q，QElemTypee）{

if（（Q.rear+1）%MAXQSIZE==Q.front）

return ERROR;

Q.base[Q.rear]=e;

Q.rear=（Q.rear+1）%MAXQSIZE;

return OK;

}

操作4： 循环队列出队

【算法设计步骤】

（1）满队不能入队

（2）队首出队

（3）队首指针移动

【算法描述】循环队列出队

Status DeQueue （LinkQueue &Q，QElemType &e）{

if（Q.front==Q.rear） return ERROR;

e=Q.base[Q.front];

Q.front=（Q.front+1）%MAXQSIZE;

return OK;

}

第二种存储结构：循环队列——链循环队列

typedef struct QNode{

QElemType data;

struct Qnode *next;

}Qnode， *QueuePtr;

typedef struct {

QueuePtr front; //队头指针

QueuePtr rear; //队尾指针

}LinkQueue;

链循环队列

（a） 空队列

（b） 元素 x 入队列

（c） 元素 y 入队列 Q.frontxy

（d） 元素 x 出队列 Q.front x y

操作 1：链队列初始化

【算法描述】

Status InitQueue （LinkQueue &Q）{

Q.front=Q.rear=（QueuePtr） malloc（sizeof（QNode））;

if（!Q.front） exit（OVERFLOW）;

Q.front->next=NULL;

return OK;

}

操作2：销毁 链队列

【算法描述】

Status DestroyQueue （LinkQueue &Q）{

while（Q.front）{

Q.rear=Q.front->next;

free（Q.front）;

Q.front=Q.rear; }

return OK;

}

操作3：判断链队列是否为空

【算法描述】

Status QueueEmpty （LinkQueue Q）{

return （Q.front==Q.rear）;

}

操作4：求链队列的队头元素

【算法描述】

Status GetHead （LinkQueue Q， QElemType&e）{

if（Q.front==Q.rear） return ERROR;

e=Q.front->next->data;

return OK;

}

操作 5：链队列入队

Status EnQueue（LinkQueue

&Q，QElemTypee）{

p=（QueuePtr）malloc（sizeof（QNode））;

if（!p） exit（OVERFLOW）;

p->data=e; p->next=NULL;

Q.rear->next=p;

Q.rear=p;

return OK;

}

操作 6：链队列出队

Status DeQueue （LinkQueue &Q，QElemType &e）{

if（Q.front==Q.rear） return ERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if（Q.rear==p） Q.rear=Q.front;

delete p;

return OK;

}

第4 章 串、数组和广义表

4.1 串的定义

由零个或多个字符组成的有限序列。

记作 S=’a1a2…an’ （n≥0）

串 的术语：

（1）串名 ：S；

（2）串值 ：用单引号括起来的字符序列。

（3）长度：串中字符的数目。

（4）空串 ：含零个字符的串

（5）空格串 ：由一个或多个空格组成的串。

（6）子串 ：串中任意个连续的字符组成的子序列。

（7）字符在串的位置：字符在序列中的序号。

（8）子串在串的位置：子串的第一个字符在串中的位置。

（9）相等：当且仅当两个串的值相等。

串的举例：

a=‘BEI’

b=‘JING’

c=‘BEIJING’

d=‘BEI JING’

长度分别为3、4、7、8；

a 和b 都是c 和d 的子串；

a 在c 和d 中的位置都是1；

b 在c 和d 中的位置是4 和5；

a、b、c、d 彼此不相等。

串的比较：

通过组成串的字符之间的比较来进行的

给定两个串：X=“x1x2…xn”和Y=“y1y2…ym”，则：

1）当n=m 且x1=y1，…，xn=ym 时，称X=Y；

2） 当下列条件之一成立时，称X＜Y：

n＜m 且xi=yi（1≤i≤n）；

存在k≤min（m，n），使得xi=yi（1≤i≤k-1）且xk＜yk。

例：S1=“ab12cd”，S2=“ab12”，S3=“ab13”

串与线性表区别：

串的数据对象约束为字符集。

串的基本操作与线性表有很大差别

线性表的基本操作中，大多以“单个元素”作为操作对象，如查找某个元素、在某个

位置上插入一个元素和删除一个元素。

串的基本操作中，通常以“串的整体”作为操作对象。

如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串。

知识点1：串的表示

串的表示：3 种方法

方法1：定长顺序存储 表示

用一组地址连续的存储单元存储串值的字符序列。

（1）非压缩形式：一个数组单元存储一个字符——浪费空间。

（2）压缩形式：一个数组单元存储多个字符——算法复杂。

如何表示串的长度？

方案1：用一个变量来表示串的实际长度。

方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。

方案3：用数组的0 号单元存放串的长度，从1 号单元开始存放串值。

方法2：堆分配存储 表示

系统开辟一个串值存储空间（串值可利用空间），同时建立一个符号表；

建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用

空间的位置、串长度等信息。

方法3：串的链式存储表示 也称作：串的块链式存储表示

用链表方式存储串值，每个结点大小相同。

结点分为两个域

data 域 next 域

知识点2：串的模式匹配

模式匹配：给定主串S=“s1s2…sn”和模式T=“t1t2…tm”，在S 中寻找T 的过程称为

模式匹配。如果匹配成功，返回T 在S 中的位置，如果匹配失败，返回0。

假设串采用顺序存储结构，串的长度存放在数组的0 号单元，串值从1 号单元开始存

放；

模式匹配问题的特点：

⑴算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹

配；

⑵算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。

介绍两种方法：

方法1：BF 算法

方法2：KMP 算法

方法1：模式匹配——BF 算法

①基本思想

从主串S 的第一个字符开始和模式T 的第一个字符进行比较，若相等，则继续比较两

者的后续字符；否则，从主串S 的第二个字符开始和模式T 的第一个字符进行比较，重复

上述过程，直到T 中的字符全部比较完毕，则说明本趟匹配成功；或S 中字符全部比较完，

则说明匹配失败。

例：主串S=“ababcabcacbab”，模式T=“abcac”

例：主串S=“ababcabcacbab”，模式T=“abcac”

例：主串S=“ababcabcacbab”，模式T=“abcac”

例：主串S=“ababcabcacbab”，模式T=“abcac”

例：主串S=“ababcabcacbab”，模式T=“abcac”

方法1：模式匹配——BF 算法

② 算法过程

STEP1：在串S 和串T 中设比较的起始下标i 和j；

STEP2：循环直到S 或T 的所有字符均比较完；

2.1 如果S[i]=T[j]，继续比较S 和T 的下一个字符；

2.2 否则，将i 和j 回溯，准备下一趟比较；

STEP3：如果T 中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，

匹配失败，返回0；

③ BF 算法步骤

入口函数（主串、模式串、起始位置）

（1）两个变量，一个是在主串下标变量i，一个是子串下标变量j

（2）在两个串中比较

如果相同，下标下移；否则退回

（3）匹配成功返回在主串中的位置；否则返回0 表示失败

【BF 算法描述】

int Index_BF （SString S，SString T， int pos）

{

i= pos，j =1;

while （i<=S[0] && j<=T[0]） {

if （S[i]==T[j]） { i++;j++; }

else {i=i-j-2; j=1;}

}

if （j>T[0]） return i-T[0]; /匹配成功/

else return 0; /返回不匹配标志/

}

小结方法1：模式匹配——BF 算法

③算法性能

设串S 长度为n，串T 长度为m，在匹配成功的情况下，考虑两种极端情况：

情况1：最好情况，即不成功匹配都发生在串T 的第1 个字符。

设匹配成功发生在si 处，则在i-1 趟不成功的匹配中共比较了i-1 次，第i 趟成功的匹

配共比较了m 次，所以总共比较了i-1+m 次，所有匹配成功的可能情况共有n-m+1 种，则：

情况2：最坏情况，不成功匹配都发生在串T 的最后一个字符。

方法2：模式匹配——KMP（Knuth Morris Pratt）算法

① 分析过程

改进思想：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部

分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。

方法2：模式匹配——KMP（Knuth Morris Pratt）算法

方法2：模式匹配——KMP（Knuth Morris Pratt）算法

为此，定义next[j]函数，表明当模式中第j 个字符与主串中相应字符“失配”时，在

模式中需重新和主串中该字符进行比较的字符的位置。

① 小结1：next[j]函数的意义

next[j]函数表征着模式 P 中最大相同首子串和尾子串（真子串）的长度。可见，模

式中相似部分越多，则next[j]函数越大，它既表示模式串中的字符之间的相关度越高，模

式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。

②小结2：回溯模式串，也就是子串

第一，主串中的i 可以不回溯，模式向右滑动到的新比较起点k ，并且k 仅与模式

串P（模式串）T 有关！

第二，关注两个问题：

问题1：如何由当前部分匹配结果确定模式向右滑动的新比较起点k？

问题2：模式应该向右滑多远才是最高效率的?

③ 计算next[j]的方法

情形1：

当j=1 时，next[j]=0；

next[j]=0 表示根本不进行字符比较

情形2：

当j>1 时，next[j]的值为：

模式串的位置从1 到j-1 构成的串中所出现的首尾相同的子串的最大长度加1。

情形3：

当无首尾相同的子串时next[j]的值为1。

next[j]=1 表示从模式串头部开始进行字符比较

【KMP 算法描述】

int Index_KMP （SString S，SString T， int pos）

{

i= pos，j =1;

while （i<=S[0] && j<=T[0]） {

if （j==0 || S[i]==T[j]） { i++;j++; }

else j=next[j]; /i 不变，j 后退/

}

if （j>T[0]） return i-T[0]; /匹配成功/

else return 0; /返回不匹配标志/

}

void get_next（SString T， int &next[]）

{

i= 1; next[1] = 0; j = 0;

while（ i<T[0]）{

if（j==0 || T[i] == T[j]）{

++i; ++j;

next[i] = j;

}

else

j = next[j];

}

}

④举例说明计算next[j]

例题2：

S=“a c a b a a b a a b c a c a a b c“

T=“a b a a b c a c"

求模式T 的next[j]，写出KMP 匹配过程

练习1：

设目标串s=“cddcdc”，模式串t=“cdc”。s 的长度为

n（n=6），t 的长度为m（m=3）。用指针i 指示目标串s 的当前比较字符位置，用指

针j 指示模式串t 的当前比较字符位置。BF 模式匹配过程如下所示。

练习2：设目标串s=“aaabaaaab”，模式串

t=“aaaab”。s 的长度为n（n=9），t 的长度为m（m=5）。用指针i 指示目标串s 的

当前比较字符位置，用指针j 指示模式串t 的当前比较字符位置。KMP 模式匹配过程如下

所示。

分析：模式“aaaab”在和主串“aaabaaaab”匹配时，当i=4，j=4 时，s.data[4]≠

t.data[3]，由next[j]的指示还需进行i=4、j=3，i=4、j=2，i=4、j=1 等三次比较。实际上，

因为模式中的第1、2、3 个字符和第4 个字符都相等，因此，不需要再和主串中第4 个字

符相比较，而可以将模式一次向右滑动4 个字符的位置直接进行i=5，j=1 时的字符比较。

所以：上述定义的next[]在某些情况下尚有缺陷!

next 函数的改进

next[j] = k，而pj=pk，则主串中si 和pj 不等时，不需再和pk 进行比较，而直接和pnext[k]

进行比较。

小结： 这就是说，若按上述定义得到next[j]=k，而模式中pj=pk，则为主串中字符si

和pj 比较不等时，不需要再和pk 进行比较，而直接和pnext[k]进行比较，换句话说，此时的

next[j]应和next[k]相同。

为此将next[j]修正为nextval[j]：

比较t.data[j]和t.data[k]，

若不等，则nextval[j]=next[j];

若相等，则nextval[j]=nextval[k];

举例：

next[j]修正为nextval[j]：

比较t.data[j]和t.data[k]，

若不等，则 nextval[j]=next[j];

若相等，则 nextval[j]=nextval[k];

复习1：串的模式匹配KMP 思想

设有主串s 和子串t，子串t 的定位就是要在主串s 中找到一个与子串t 相等的子串。

通常把主串s 称为目标串，把子串t 称为模式串，因此定位也称作模式匹配。模式匹配成

功是指在目标串s 中找到一个模式串t；不成功则指目标串s 中不存在模式串t。

复习2：串的模式匹配算法流程

STEP1：在串S 和串T 中分别设比较的起始下标i 和j；

STEP2：循环直到S 中所剩字符长度小于T 的长度或T 中所有字符均比较完毕

如果S[i]=T[j] ，继续比较S 和T 的下一个字符；否则将j 向右滑动到next[j]位置，即

j=next[j]；

如果j=0，则将i 和j 分别加1，准备下一趟比较；

STEP3：如果T 中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；

复习3：求next[ ]函数

void get_next（SString T， int &next[ ]）

{

i= 1; next[1] = 0; j = 0;

while（ i<T[0]）{

if（j==0 || T[i] == T[j]）{

++i; ++j;

next[i] = j;

}

else

j = next[j];

}

}

复习4： KMP 算法的时间复杂度

设主串s 的长度为n，模式串t 长度为m，在KMP 算法中求next 数组的时间复杂度为

O（m），在后面的匹配中因主串s 的下标不减即不回溯，比较次数可记为n，所以KMP

算法总的时间复杂度为O（n+m）。

4.3 数组

（1）数组 的概念

数组是由一组个数固定，类型相同的数据元素组成阵列。 以二维数组为例：二维数

组中的每个元素都受两个线性关系的约束

即行关系和列关系，在每个关系中，每个元素aij 都有且仅有一个直接前趋，都有且

仅有一个直接后继。

（2）数组的顺序存储结构

设A 是一个具有m 行n 列的元素的二维数组:

（1）以行为主序的方式：

（1）以行为主序的方式：

（2）以列为主序的方式：

（3）数组元素存储地址的计算

假设二维数组A 每个元素占用s 个存储单元， Loc（aij ）为元素aij 的存储地址，

Loc（a00 ） 是a00 存储位置， 也是二维数组A 的基址。

若以行序为主序的方式存储二维数组，则元素aij 的存储位置可由下式确定：

Loc（aij ） = Loc（a00 ） +（n* i+j ）*s

若以列序为主序的方式存储二维数组，则元素aij 的存储位置可由下式确定：

Loc（aij ） = Loc（a00） +（m* j+i ）*s

说明：一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多

维数组使用相对较少，对于高维数组的顺序存储方法，可以将二维的情形加以推广便能够

得到。

矩阵 的压缩存储

（1）第一类：特殊矩阵 的压缩存储

（2）第二类：稀疏矩阵 的压缩存储（三元组表的存储结构、十字链表的存储结构）

第一类：特殊矩阵

值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵

例如：对称矩阵 、 上（下）三角矩阵 、带状矩阵 都是特殊矩阵

举例1：特殊矩阵压缩存储 ——对称矩阵为例

对称矩阵是满足下面条件的n 阶矩阵: aij=aji 0≤ i，j≤ n-1

对称矩阵元素可以只存储下三角部分，共需n（n+1）/2 个单元的空间（三角矩阵的

存储方式类似）

以一维数组sa[ ]作为n 阶对称矩阵A 的存储结构，A 中任意一元素aij 与它的存储位

置 sa[k] 之间存在着如下对应关系：

例如，a53 在 sa[ ]中的存储位置是：

以一维数组sa[ ]作为n 阶对称矩阵A 的存储结构，A 中任意一元素aij 与它的存储位

置 sa[k] 之间存在着如下对应关系：

例如，a53 在 sa[ ]中的存储位置是：k=5*（5+1）/2+3=18

sa[18]= a53

举例2：特殊矩阵压缩存储——带状矩阵为例

所有非0 元素都集中在以主对角线为中心的带状区域，半带宽为d 时， 非0 元素有

第二类：稀疏矩阵

有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵

称为稀疏矩阵。

方法1：稀疏矩阵的三元组 顺序表图示

举例说明：三元组表（i， j， aij ）

A=（（0，1，12）， （0，2，9）， （2，0，-3），（2，5，14），

（3，2，24）， （4，1，18）， （5，0，15）， （5，3，-7） ）

加上行、列数6，7

存在问题：以三元组表示的稀疏矩阵，在运算中，若非0 元素的位置发生变化，会引

起数组元素的频繁移动。

解决方法：采用十字链表的存储结构

方法2：十字链表 的存储结构

在十字链表中，表示非0 元素的结点除了三元组，还有两个指针域：

向下域（down）链接同一列下一个非0 元素

向右域（right）链接同一行下一个非0 元素

稀疏矩阵中同一行的非0 元素结点通过向右域，链接成一个带头结点的行循环链表

同一列的非0 元素结点通过向下域，链接成一个带头结点的列循环链表

4.4 广义表

（1）广义表

定义：广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。

记作：LS= （d0，d1，d2，. . . . . .dn-1）。其中di 既可以是单个元素，也可以是广义表。

说明：

（1）广义表的定义是一个递归定义，因为在描述广义 表时又用到了广义表；

（2）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素， 称

为单元素（原子），也可以是广 义表，称为广义表的子表；

（3）n 是广义表长度；

举例说明：

A = （） 空表，表长为0；

B = （a，（b，c，d））

B 的表长为2，两个元素分别为 a 和子表（b，c，d）；

C = （e）

C 中只有一个元素e，表长为1；

D = （A，B，C，f ）

D 的表长为4，它的前三个元素 A，B，C 广义表，第四个是单元素； E=（ a ，E ）

递归表.

（2）广义表的运算：

若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。

对非空广义表：称第一个元素为L 的表头 ，其余元素组成的表称为LS 的表尾；

B = （a，（b，c，d））表头：a 表尾 （（b，c，d））

练习1：

A=（ ） GetHead 和GetTail 均无定义

A=（a，b） GetHead（A）=a GetTail（A）=（b）

A=（a） GetHead（A）=a GetTail（A）=（ ）

A=（（a）） GetHead（A）=（a） GetTail（A）=（ ）

A=（a，b，（c，d），（e，（f，g）））

GetHead（GetTail（GetHead（GetTail（GetTail（A）））））

练习2：求长度

（3） 广义表的存储结构

由于广义表中数据元素可以具有不同结构，故 难以用顺序结构表示广义表。通常采

用链表存储方式

如何设定链表结点？广义表中的数据元素可能为单元素（原子）或子表，由此需

要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素

广义表的存储结构示例

第5 章 树与二叉树

5.1 树的基本概念

5.2 二叉树的基本概念与逻辑结构

5.3 二叉树的存储结构

5.4 操作1：遍历二叉树

5.5 操作2：线索二叉树

5.6 操作3：哈夫曼树及其应用

5.7 操作4：二叉树、树和森林相互转换

5.1 树的基本概念（5 个知识点）

5.1.1 树的定义

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

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

（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，

Tm-1，每个集合Ti（i=0，1，…，m-1）又是一棵树，称为根的子树，每棵子树的根结点有

且仅有一个直接前驱，但可以有0 个或多个直接后继。

树的示意图

（a）空树 （b）仅含有根结点的树 （c）含有多个结点的树图

在图 5-1（a）的树中有多少子树？

在图 5-1（a）的树中有多少子树？

5.1.2 树的描述

树的逻辑结构可以用二元组 描述为：

tree =（K，R）

K={ki∣1≤i≤n;n≥0，ki∈elemtype}

R={r}

如何描述图5-1（a）的树？

如何描述图5-1（a）的树结构？

答：对图5-1（a ）的树结构，可以二元组表示为：

K={A，B，C，D，E，F，G，H，I，J，K，L，M}

R={r}

r={（A，B）， （A，C）， （A，D）， （B，E）， （B，F）， （C，G）， （D，

H）， （D，I），（E，J），（E，K），（E，L），（H，M）}

5.1.3 树的基本术语

（1）结点

指树中的一个数据元素，一般用一个字母表示。

（2）度

一个结点包含子树的数目，称为该结点的度。

（3）树叶（叶子 ）

度为0 的结点，称为叶子结点或树叶，也叫终端结点。

（4）孩子结点

若结点X 有子树，则子树的根结点为X 的孩子结点，也称为孩子。

图5-1（a）中A 的孩子为？

答：图5-1（a）中A 的孩子为B，C，D

（5）双亲结点

若结点X 有子女Y，则X 为Y 的双亲结点。

（6）祖先结点

从根结点到该结点所经过分枝上的所有结点为该结点的祖先。

图5-1（a）中L 的祖先有？

（7）子孙结点

某一结点的子女及子女的子女都为该结点子孙。

（8）兄弟结点

具有同一个双亲的结点，称为兄弟结点。

（9）树的度

树中结点度的最大值称为树的度。

（10）树的层数

根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。

（11） 树的高度（深度）

树中结点所处的最大层数称为树的高度。

（12）有序树与无序树

若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序，称该树为有序树；

反之称为无序树。

（13）森林 （树林）

若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。

5.1.4 树的表示：逻辑结构表示

5.1.5 树的性质

树的性质通过二叉树的性质进行学习和掌握。
什么是二叉树？

5.2 二叉树的基本概念与逻辑结构

5.2.1 二叉树的定义

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵
分别称为左子树和右子树的、互不相交的二叉树组成。

特点：1）每个结点的度≤2；
2）是有序树；

说明：二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大
于2 的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。

5.2.2 二叉树的形态

5.2.3 二叉树的性质

性质3：对任意一棵二叉树，如果叶子结点个数为n0，度为2 的结点个数为n2，则有
n0=n2+1
证明：设二叉树中度为1 的结点个数为n1，根据二叉树的定义可知，该二叉树的结点
数n=n0+n1+n2。
又因为在二叉树中，度为0 的结点没有孩子，度为1 的结点有1 个孩子，度为2 的结
点有2 个结孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2，而一棵二叉树中，除根
结点外所有都为孩子结点，故该二叉树的结点数应为孩子结点数加1 即：
n=n0*0+n1*1+n2*2+1
因此，有 n=n0+n1+n2=n0*0+n2*1+n2*2+1， 最后得到n0=n2+1。

性质4： 如果将一棵有n 个结点的完全二叉树的结点按层序（自顶向下，同一层自左
向右）连续编号1，2，…，n，然后按此结点编号将树中各结点顺序地存放于一 个一维数
组中， 并简称编号为i 的结点为结点i（1≤i≤n）。则有以下关系：
如果将一棵有n 个结点的完全二叉树的结点按层序（自顶向下，同一层自左向右）连
续编号1，2，…，n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中， 并
简称编号为i 的结点为结点i （1≤i≤n）。则有以下关系：
若i == 1，则i 是二叉树的根，无双亲
若i > 1， 则i 的双亲为⌊i /2⌋
若2i≤n，则i 的左孩子为2i，否则无左孩子
若2i+1≤n，则i 的右孩子为2i+1，否则无右孩子
若i 为偶数，且i != n， 则其右兄弟为i+1
若 i 为奇数，且i != 1， 则其左兄弟为i-1

根据性质4，定义特殊的两类二叉树：
第一类二叉树满二叉树（Full Binary Tree）
第二类二叉树完全二叉树（Complete Binary Tree）

若设二叉树的深度为h，则共有h 层。除第h 层外，其它各层（0~h-1）的结点数都达
到最大个数，第h 层从右向左连续缺若干结点，这就是完全二叉树。
第一类二叉树满二叉树（Full Binary Tree）
第二类二叉树完全二叉树（Complete Binary Tree）

5.3 二叉树的存储结构

5.3.1 顺序存储结构（实质就是数组表示）

二叉树顺序存储结构的表示与步骤：
步骤1：二叉树的性质4
步骤2：数组表示二叉树

5.3.2 链式存储结构（指针表示）

5.4 操作1：遍历二叉树

二叉树的四大操作：
遍历化、线索化、最优化、转换化

第一个操作：
二叉树的遍历（（Traversing Binary Tree） ）

操作1：二叉树的遍历（（Traversing Binary Tree） ）

所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一
次。
遍历的结果：产生一个关于结点的线性序列。
设访问根结点记作D
遍历根的左子树记作L
遍历根的右子树记作R
则可能的遍历次序有
先序 DLR 逆先序 DRL
中序 LDR 逆中序 RDL
后序 LRD 逆后序 RLD
按层遍历方法

5.4.1 先序遍历/前序遍历 （Preorder Traversal）

先序遍历二叉树算法的框架是若二叉树为空，则空操作;
否则
访问根结点（D）;
先序遍历左子树（L）;
先序遍历右子树（R）;

5.4.2 中序遍历 （Inorder Traversal）

中根遍历二叉树的历算法描述为：
若二叉树为空，则算法结束；否则
(1)中根遍历左子树（L）;
(2)输出根结点（D）;
(3)中根遍历右子树（R）。

5.4.3 后序遍历 （Postorder Traversal）

后序遍历二叉树的历算法描述为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树（L）;
（2）后序遍历右子树（R）；
（3）访问根结点（D）;

例题1：写出如图所示二叉树的三种遍历序列为

例题2：写出如图所示二叉树的三种遍历序列为：

例3:由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例，先序序列
（ABHFDECKG）和中序序列（HBDFAEKCG），构造二叉树过程如下：

问题1: 如何可唯一地确定一棵二叉树？
答：先序+中序或后序+中序均可唯一地确定一棵二叉树。
问题2: 二叉树的二叉树链表存储结构中，有多少个指针域未利用？
答：二叉树的二叉链表存储结构中，有n+1 个指针域未利用，已经使用的有n-1 个指
针域，共有2n 个指针域。

5.5 操作2：线索二叉树

5.5.1 线索二叉树（ThreadedBinary Tree ）引入

问题1：为什么二叉树中加入线索？

答：原来的左、右孩子域有许多空指针又没有利用起来。 为了不浪费存存贮空间，
利用原有的孩子指针为空时来 存放直接前驱和后继，这样的指针称为“线索”，加线 索
的过程称为线索化，加了线索的二叉树，称为线索二 叉树，对应的二叉链表称为线索二
叉链表。

问题2：如何在二叉树中加入线索？

答：线索（Thread）: 指向结点前驱和后继的指针若结点有左孩子，则lchild 指示其左
孩子，否则lchild 中存储该结点的前驱结点的指针；
若结点有右孩子，则rchild 指示其右孩子，否则rchild 中存储指向该结点的后继结点
的指针
实质：对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这
些线性序列中有且仅有一个直接前驱和直接后继。
说明：在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继。

5.5.2 线索二叉树类型

根据遍历的不同要求，线索二叉树可以分为：

（1）前序线索二叉树（前序的前驱和后继都要标出）
（2）中序线索二叉树（中序的前驱和后继都要标出）
（3）后序线索二叉树（后序的前驱和后继都要标出）

5.5.3 线索二叉树链式存储

二叉链表中每个结点还是有5 个域，但其中只有2 个 指针，增加线索后的二叉链表
结点结构可描述如下：

5.5.4 线索二叉树举例

例1：中序线索二叉树

例3：后序线索二叉树

5.6 操作3：哈夫曼树及其应用

一种最优的二叉树，最优是指WPL 最小！

5.6.1 基本概述

（1）路径长度 （Path Length）：两个结点之间的路径长度是连接两 结点的路径上的
分支数。
（2）树的路径长度是各结点到根结点的路径长度之和。
（3）结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘
积。

5.6.3 哈夫曼树构造

假设给定的叶子结点的权分别为1，5，7，3，则构造哈夫曼树过程如下图所示。

5.6.4 哈夫曼树应用——哈夫曼树编码

在哈夫曼树中，规定往左编码为0，往右编码为1，则得到
叶子结点编码为从根结点到叶子结点中所有路径中0 和1 的顺
序排列。

例如，给定权{1，5，7，3}，求哈夫曼树及编码 （假定权
值就代表该字符名字）。

例如，给定权{1，5，7，3}，得到的哈夫曼树及编码见下图（假定权值就代表该字符
名字）。

例题：哈夫曼编码实现数据压缩，设给出一段报文：

CAST CAST SAT AT A TASA
分析过程：
字符集合是{ C， A， S， T }，各个字符出现的频度（次数）是W＝{ 2， 7， 4，
5 }。
数据编码方案1：若给每个字符以等长编码
A : 00 T : 10C : 01S : 11
则总编码长度为（ 2+7+4+5 ）* 2 = 36.

数据编码方案2：若按各个字符出现的概率不同而给予不等长编

分析：因各字符出现的概率为{ 2/18， 7/18， 4/18， 5/18}，化整为 { 2， 7， 4， 5 }，
以它们为各叶结点上的权值，建立哈夫曼树。左分支赋0，右分支赋 1，得哈夫曼编码（变
长编码）。

数据编码方案2：若按各个字符出现的概率不同而给予不等长编。

分析：因各字符出现的概率为{ 2/18， 7/18， 4/18， 5/18}，化整为 { 2， 7， 4， 5 }，
以它们为各叶结点上的权值，建立哈夫曼树。左分支赋0，右分支赋 1，得哈夫曼编码（变
长编码）。
A : 0 T : 10 C : 110 S : 111
它的总编码长度：71+52+（ 2+4 ）*3 = 35。
结论：比等长编码的情形要短。同时，哈夫曼编码是一种前缀编码，解码时不会混淆！

5.7 操作4：二叉树、树和森林相互转换

5.7.1 树的表示法

（1） 双亲表示

以一组连续的存储单元来存放树中的结点，每个结点有两个域：一个是data 域，存放
结点信息，另一个是parent 域，用来存放双亲的位置（指针）。

（2） 孩子表示法

将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，
每个单链表有一个表头结点，所有表头结点用一个数组来描述。

（3） 双亲孩子表示

将第1、2 两种方法结合起来，则得到双亲孩子表示法。

（4）孩子兄弟表示法

类似于二叉链表，但第一根链指向第一个孩子，第二根链指向下一个兄弟。将下图的
树用孩子兄弟表示法 表示。

5.7.2 树、森林和二叉树的转换

（1） 树转换成二叉树
可以分为三步：
第一步：连线
指相邻兄弟之间连线。
第二步：抹线
指抹掉双亲与除左孩子外其它孩子之间的连线。
第三步：旋转
只需将树作适当的旋转。

（2） 森林转换成二叉树

可以分为两步：
第一步：将森林中每一棵树分别转换成二叉树这在刚才的树转换成二叉树中已经介绍
过。

第二步：合并

使第n 棵树接入到第n-1 棵的右边并成为它的右子树，第n-1 棵二叉树接入到第n-2 棵
的右边并成为它的右子树，…，第2 棵二叉树接入到第1 棵的右边并成为它的右子树，直
到最后剩下一棵二叉树为止。

（2） 森林转换成二叉树（举例）

练习：森林转换成二叉树

（3） 二叉树还原成树或森林

可以分为两步：
右链断开
step1.将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉
树上。
二叉树还原成树
step2.将step1 中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相
反。）

（3） 二叉树还原成树或森林举例说明：

5.7.3 树和森林的遍历

在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，即
树和森林只有先序遍历和后序遍历。
（1）先序遍历
①树的先序遍历
若树非空，则先访问根结点，然后依次先序遍历各子树。
②森林的先序遍历
若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着
先序遍历第二棵树、第三棵树、…、直到最后一棵树。
（2） 后序遍历
① 树的后序遍历
若树非空，则依次后序遍历各子树，最后访问根结点

② 森林的后序遍历
按顺序后序遍历中的每一棵树。
另外，请注意，树和森林的先序遍历等价于它转换成的二叉树的先序遍历，树和森林
的后序遍历等价于它转换成的二叉树的中序遍历。

第6 章 图

6.1 图的定义和基本术语

（1） 图的定义
图是由顶点集V 和顶点间的关系集合E（边 的集合）组成的一种数据结构，可以用
二元组定义为：G=（V，E）
例如，对于图6-1 所示的无向图G1 和有向图G2，它们的数据结构可以描述为：
G1=（V1，E1），
其中 V1={a，b，c，d}，E1={（a，b），（a，c），（a，d），（b，d），（c，d）}，
而G2=（V2，E2），其中
V2={1，2，3}，
E2={<1，2>，<1，3>，<2，3>，<3，1>}

（2）图的基本术语

①有向图和无向图
在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。
②完全图、稠密图、稀疏图
具有n 个顶点，n（n-1）/2 条边的图，称为完全无向图；
具有n 个顶点，n（n-1）条弧的有向图，称为完全有向图。
完全无向图和完全有向图都称为完全图。
对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n（n-1）/2。
对于一般有向图，顶点数为n，弧数为e，则 0≤e≤n（n-1） 。
当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，
则称它为稀疏图
③度、入度、出度
在图中，一个顶点依附的边或弧的数目，称为该顶点的度。
在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数
目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。

6.2 图的存储结构

顺序存储结构： 数组表示法（邻接矩阵）

（1）第一类：邻接矩阵

图的邻接矩阵表示
在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关
系。
若（i，j）∈E（G）或〈i，j〉∈E（G），则矩阵中第i 行第j 列元素值为1，否则为
0。
图的邻接矩阵定义为：

例如， 对下图所示的无向图和有向图，写出它们的邻接矩阵

讨论1：从无向图的邻接矩阵可以得出如下结论：
①矩阵是对称的;
②第i 行或第i 列1 的个数为顶点i 的度;

③矩阵中1 的个数的一半为图中边的数目;
④容易判断顶点i 和j 之间是否有边相连（看矩阵中i 行j 列值是否为1）。

讨论2：从有向图的邻接矩阵可以得出如下结论
①矩阵不一定是对称;
②第i 行中1 的个数为顶点i 的出度;
③第i 列中1 的个数为顶点i 的入度;
④矩阵中1 的个数为图中弧的数目;
⑤很容易判断顶点i 和顶点j 是否有弧相连。

网的邻接矩阵表示

类似地可以定义网的邻接矩阵为：

图/网的邻接矩阵数据类型描述

struct mgraph
{ 图中顶点数;
图中边数;
存放顶点信息v1，v2，….vn;
邻接矩阵;
};

（2）第二类：邻接表（链式）表示法

对每个顶点vi 建立一个单链表，把与vi 有关联的边的信息链接起来，每个结点设为3
个域；

每个单链表有一个头结点（设为2 个域），存vi 信息；
每个单链表的头结点另外用顺序存储结构存储

无向图的邻接表表示

注：邻接表不唯一，因各个边结点的链入顺序是任意的

有向图的邻接表表示

空间效率为O（n+e）
出度：OD（Vi）＝邻接点域为Vi 的弧尾个数
入度：ID（Vi）＝邻接点域为Vi 的弧头个数度：TD（Vi） = OD（ Vi ）+I D（ Vi ）
邻接表表示法的特点
优点：空间效率高，容易寻找顶点的邻接点；
缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
邻接矩阵与邻接表表示法的关系
① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接
表不唯一（链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为O（n^2），而邻接表的空间复杂度为O（n+e）。
③ 邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

6.3 图的遍历

（1）定义
从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，就叫做图的遍
历（Traversing Graph）。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等
算法的基础。
两条遍历图的算法：深度优先搜索、广度优先搜索
（2）深度优先搜索遍历算法（类似于树的先序遍历）
深度优先搜索遍历算法思想：
（1） 首先访问顶点i，并将其访问标记置为访问过，即visited[i]=1；
（2） 然后搜索与顶点i 有边相连的下一个顶点j，若j 未被访问过， 则 访 问 它 ，
并将j 的访问标记置为访问过，visited[j]=1，然后从j 开始重复此过程，若j 已访问，再看
与i 有边相连的其它顶点；
（3） 若与i 有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，
直到图中所有顶点都被访问完止。
例如，对下图所示无向图，从顶点0 出发的深度优先搜索遍历序列可有多种，下面仅
给出三种，其它可作类似分析。

（3）广度优先搜索遍历算法
广度优先搜索的思想：采用队列

①开始时要将其置空。
②在每访问一个顶点时，要将其入队。
③在访问一个顶点的所有后继时，要将其出队。
④若队列为空时，说明每一个访问过的顶点的所有后继均已访问完毕，因而本次遍历
可以结束。若此时还有未访问的顶点，需要另选起点进行遍历。
例如，对下图所示无向图，从顶点1 出发的广度优先搜索遍历序列可有多种，下面仅
给出三种，其它可作类似分析。

6.4 图的应用

应用1：生成树

在图论中，常常将树定义为一个无回路连通图。
例如，下面两个图就是无回路的连通图。是树？
只要选定某个顶点做根并以树根为起点对每条边定向，就可以将它们变为通常的树。

如何生成树呢？
两种遍历的算法可以获得生成树：
深度优先（搜索）生成树、广度优先（搜索）生成树

应用2：最小生成树（两种）

在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生
成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。
下面将介绍求最小生成树的两种方法：
第一种最小生成树：普里姆算法
第二种最小生成树：克鲁斯卡尔算法

第一种最小生成树算法：普里姆算法
普里姆（prim）算法思想：
下面以无向网的最小生成树问题为例：
普里姆方法的思想是：在图中任取一个顶点K 作为开始点，令U={k}，W=V-U，其
中V 为图中所有顶点集，然后找一个顶点在U 中，另一个顶点在W 中的边中最短的一条，
找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U 集合中，并从
W 中删去这些顶点，然后重新调整U 中顶点到W 中顶点的距离， 使之保持最小，再重复
此过程，直到W 为空集止。

举例：选择开始顶点1，求最小生成树
首先U={1}，W={2，3，4，5，6}

第二种最小生成树算法：克鲁斯卡尔（kruskal）

克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值
较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条
边，再去选后面权值较大的边，n 个顶点的图中，选够n-1 条边即可。

举例：对下图的无向网，用克鲁斯卡尔算法求最小生成树

应用3：最短路径（两种）

问题：在交通网络中常常提出从甲地到乙地之间是否有公路连通?在有多条通路的情
况下，哪一条路最短?

问题解答：交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连
通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间
的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。

说明1：存在三种情况：两个顶点之间有边；两个顶点之间没有边，则认为两个顶点
无通路；两个顶点之间有可能有间接通路（从其它顶点达到）。
说明2：路径上的开始顶点（出发点）称为源点，路径上的最后一个顶点称为终点，
并假定讨论的权值不能为负数。

方法有两个：
方法1：单源点最短路径；
方法2：所有顶点对的最短路径；

第一种单源点最短路径：迪杰斯特拉（Dijkstra）算法

（1） 定义
单源点最短路径是指：给定一个出发点（单源点）和一个有向网G=（V，E），求出
源点到其它各顶点之间的最短路径。
问题：那么怎样求出单源点的最短路径呢？
解答：将源点到终点的所有路径都列出来，然后在里面选最短的一条即可。但是这样
做，用手工方式可以，当路径特别多时，显得特别麻烦，并且没有什么规律，不能用计算
机算法实现。
方法：迪杰斯特拉（Dijkstra）在做了大量观察后，首先提出了按路长度递增序产生各
顶点的最短路径算法，我们称之为迪杰斯特拉算法。

（2）迪杰斯特拉算法的基本思想

算法思想：设V 为网中所有顶点集合，设置并逐步扩充一个集合S，存放已求出其最
短路径的顶点，则尚未确定最短路径的顶点集合是V-S；按最短路径长度递增的顺序逐个
把V-S 中的顶点加到S 中，直到S 中包含全部顶点，而V-S 为空。

习题：利用迪杰特斯拉算法，对下图所示的有向图求解最短路径，并给出算法中各个
参量的初始化结果和求解过程中的变化：

迪杰特斯拉算法过程：设源点为Vl，则S 中只包含顶点Vl，令W=V-S，则W 中包含
除Vl 外图中所有顶点，Vl 对应的距离值为0，W 中顶点对应的距离值是这样规定的：若
图中有弧<Vi，Vj>则Vi，Vj 顶点的距离为此弧权值，否则为∞（一个很大的数），然后
每次从W 中的顶点中选一个其距离值为最小的顶点Vm 加入到S 中，每往S 中加入一个
顶点Vm，就要对W 中的各个顶点的距离值进行一次修改。若加进Vm 做中间顶点，使<Vi，
Vm>+<Vm，Vj>的值小于<Vi，Vj>值，则用<Vi，Vm>+<Vm，Vj>代替原来Vj 的距离，
修改后再在W 中选距离值最小的顶点加入到S 中，如此进行下去，直到S 中包含了图中
所有顶点为止。

第二种所有顶点对之间的最短路径：Floyd 算法

（1）顶点对之间的最短路径概念
所有顶点对之间的最短路径是指：对于给定的有向网G=（V，E），要对G 中任意一
对顶点有序对V、W（V≠W），找出V 到W 的最短距离和W 到V 的最短距离。
解决此问题有效方法：轮流以每一个顶点为源点，重复执行迪杰斯特拉算法n 次，即
可求得每一对顶点之间的最短路径，总的时间复杂度为O（n^3），效率太低！
另一个方法是Floyd 算法

（2）Floyd 算法思想
将v1 到vj 的最短路径长度初始化，即D[i][j]为顶点i 到j 的路径长度，然后进行n 次
比较和更新。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

【Floyd 算法步骤】

①在vi 和vj 间加入顶点v0，比较（vi，vj）和（vi，v0，vj）的路径长度，取其中较
短者为vi 到vj 的中间顶点序号不大于0 的最短路径。
②在vi 和vj 间加入顶点v1，得到路径（vi，…，v1）和（v1，…，vj），其中（vi，…，
v1）是vi 到v1 的且中间顶点的序号不大于0 的最短路径，（v1，…，vj）是v1 到vj 的且
中间顶点的序号不大于0 的最短路径，这两条路径已经在上一步中求出。比较（vi，…，
v1，…，vj）与上一步求出的vi 到vj 且的中间顶点序号不大于0 的最短路径，取其中较短
者作为vi 到vj 的中间顶点序号不大于1 的最短路径。
③以此类推，在vi 和vj 间加入结点vk，得到路径（vi，…，vk）和（vk，…，vj），
其中（vi，…，vk）是vi 到vk 的且中间顶点的序号不大于k-1 的最短路径，（vk，…，vj）
是vk 到vj 的且中间顶点的序号不大于k-1 的最短路径。将（vi，…，vk，…，vj）与已经
求出的vi 到vj 的中间顶点序号不大于k-1 的最短路径，取其中较短者作为vi 到vj 的中间
顶点序号不大于k 的最短路径。这样，经过n 次比较后，最后求得的必是从vi 到vj 的最
短路径。按此方法，可以同时求得各个顶点间的最短路径。

【Floyd 算法步骤】

①在vi 和vj 间加入顶点v0，比较（vi，vj）和（vi，v0，vj）的路径长度，取其中较
短者为vi 到vj 的中间顶点序号不大于0 的最短路径。
②在vi 和vj 间加入顶点v1，得到路径（vi，…，v1）和（v1，…，vj），其中（vi，…，
v1）是vi 到v1 的且中间顶点的序号不大于0 的最短路径，（v1，…，vj）是v1 到vj 的且
中间顶点的序号不大于0 的最短路径，这两条路径已经在上一步中求出。比较（vi，…，
v1，…，vj）与上一步求出的vi 到vj 且的中间顶点序号不大于0 的最短路径，取其中较短
者作为vi 到vj 的中间顶点序号不大于1 的最短路径。
③以此类推，在vi 和vj 间加入结点vk，得到路径（vi，…，vk）和（vk，…，vj），
其中（vi，…，vk）是vi 到vk 的且中间顶点的序号不大于k-1 的最短路径，（vk，…，vj）
是vk 到vj 的且中间顶点的序号不大于k-1 的最短路径。将（vi，…，vk，…，vj）与已经
求出的vi 到vj 的中间顶点序号不大于k-1 的最短路径，取其中较短者作为vi 到vj 的中间
顶点序号不大于k 的最短路径。这样，经过n 次比较后，最后求得的必是从vi 到vj 的最
短路径。按此方法，可以同时求得各个顶点间的最短路径。

应用4：拓扑排序

通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程
常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就
完成了。
例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，
其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关
系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学
则必须先并行学完高等数学、程序设计基础课程。

AOV 网介绍：

在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表
示活动的网络（Actire On Vertices）简称为AOV 网。
在AOV 网中，<i，j>有向边表示i 活动应先于j 活动开始，即i 活动必须完成后，j
活动才可以开始，并称i 为j 的直接前驱，j 为i 的直接后继。这种前驱与后继的关系有传
递性，此外，任何活动i 不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱
和后继的传递性和反自反性来看，AOV 网中不能出现有向回路（或称有向环），对工程
而言，将无法进行；对程序流程而言，将出现死循环。

AOV 网应用规则：

对给定的AOV 网，应先判断它是否存在有向环。判断AOV 网是否存在有向环的方法
是对该AOV 网进行拓扑排序，将AOV 网中顶点排列成一个线性有序序列，若该线性序列
中包含AOV 网全部顶点，则AOV 网无环，否则，AOV 网中存在有向环，该AOV 网所
代表的工程是不可行的。

拓扑排序的步骤：

①在AOV 网中选一个入度为0 的顶点且输出之；
②从AOV 网中删除此顶点及该顶点发出来的所有有向边；
③重复①、②两步，直到AOV 网中所有顶点都被输出或网中不存在入度为0 的顶点。
从拓扑排序步骤可知，若在第3 步中，网中所有顶点都被输出，则表明网中无有向环，
拓扑排序成功。若仅输出部分顶点，网中已不存在入度为0 的顶点，则表明网中有有向环，
拓扑排序不成功。

应用5：关键路径

知识点1：AOE 网

若以带权有向图的顶点代表事件（event）或工程进展状态，用弧表示活动，弧上的权
值表示完成该活动所需要的时间，则这样的带权有向图称为AOE 网（Activity On Edge
Network）。

知识点2：基本概念

知识点2：重要概念

由于AOE 网中的某些活动能够并行进行，故完成整个工程所必需的时间应从源点到
汇点的最长路径长度。这里的路径长度是指完成这条路径上各个活动所需的时间之和。从
源点到汇点的最长路径称为关键路径（Critical Path）。关键路径上的活动称为关键活动。

知识点3：5 个计算公式，6 个步骤

⑥关键活动构成关键路径
所以a1，a4，a7，a8，a10，a11 是关键活动，他们组成关键路径

求AOE 网中关键路径和关键活动的算法步骤为：
①利用拓扑排序求出AOE 网的一个拓扑序列；
②从拓扑序列的第一个顶点（源点）开始，按拓扑顺序依次计算每个事件的最早发生
时间ve[j]；
③从拓扑序列的最后一个顶点（汇点）开始，按逆拓扑顺序依次计算每个事件的最晚
发生时vl[j]；
④对每个活动<vi，vj>，求活动的最早开始时间e[k]；
④对每个活动<vi，vj>，求活动的最晚开始时间l[k]；
⑤求出活动余量时间
⑥确定关键活动构成关键路径，并输出。

第7 章 查找

7.1 查找的基本概念

（1）查找表
由同一类型的数据元素（或记录）构成的集合
（2）两类查找表
• 静态查找表：查找的同时对查找表不做修改操作（如 插入和删除）
• 动态查找表：查找的同时对查找表具有修改操作
（3）基本术语

关键字：记录中某个数据项的值，可用来识别一个记录
两类关键字：主关键字和次关键字
主关键字：唯一标识数据元素
次关键字：可以标识若干个数据元素

（4）查找算法的评价指标

关键字的平均比较次数，也称平均搜索长度ASL（Average Search Length）

n：记录的个数
pi：查找第i 个记录的概率 （ 通常认为pi =1/n ）
ci：找到第i 个记录所需的比较次数

方法一：顺序查找

应用范围：
顺序表或线性链表表示的静态查找表;
表内元素之间无序;
①顺序表的表示
typedef struct {
ElemType *R; //表基址
int length; //表长
}SSTable;
②第2 章在顺序表L 中查找值为e 的数据元素
int LocateELem（SqList L，ElemType e）
{ for （i=0;i< L.length;i++）
if （L.elem[i]==e） return i+1;
return 0;
}

改进：把待查关键字key 存入表头（“哨兵”），从后向前逐个比较，可免去查找过
程中每一步都要检测是否查找完毕，加快速度。
int Search_Seq（SSTable ST ， KeyType key）{
ST.R[0].key=key;
for（ i=ST.length; ST.R[i].key!=key; --i ）;
return i;
}

③顺序查找的性能分析

空间复杂度：一个辅助空间。
时间复杂度：
1） 查找成功时的平均查找长度
设表中各记录查找概率相等

2）查找不成功时的平均查找长度ASLf =n+1
④顺序查找算法有特点
算法简单，对表结构无任何要求（顺序和链式）
当n 很大时查找效率较低
改进措施：二分查找，分块查找

查找概率相等时，ASL 相同；
查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其ASL
要比无序表ASL 小。

方法二：折半查找

折半查找的前提条件是：查找表有序

① 思想

折半查找（Binary Search）是用待查找元素的key 与查找表的“中间位置”的元素的
关键字进行比较，若它们的值相等，则查找成功。若查找元素key 大于查找表的“中间位
置”的元素的关键字的值，则在查找表的中间位置的后端范围内，继续使用折半查找。否
则，则在查找表的中间位置的前端范围内，继续使用折半查找。直到查找成功或者失败为
止。

② 举例过程

例如，假设给定有序表中关键字为8，
17，25，44，68，77，98， 100，115，125，
将查找K=17 和K=120，描述如下所示：

查找K=120

查找K=120 的示意图（查找不成功）

③二分查找的性能分析

为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中
点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间
再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，给定的关键字序列
8，17，25，44，68，77，98，100，115，125，它的判定树是什么？

③ 二分查找的性能分析

从左图可知，查找根结点68，需一次查找，查
找17 和100，各需二次查找， 查找8、25、77、
115 各需三次查找，查找44、98、125 各需四次查
找。因此，可以得到结论：二叉树第K 层结点的查
找次数各为k 次（根结点为第1 层），而第k 层结
点数最多为2^(k-1) 个。假设该二叉树的深度为h， 则二分查找的成功的平均查找长度为（假
设每个结点的查找概率相等）：

【算法步骤】折半查找（非递归算法）

STEP1: 设表长为n，low、high 和mid 分别指向待查元素 所在区间的上界、下界和
中点，k 为给定值初始时，令low=1，high=n，mid=[（low+high）/2]
STEP2: 让k 与mid 指向的记录比较
若k==R[mid].key，查找成功
若k<R[mid].key，则high=mid-1
若k>R[mid].key，则low=mid+1
STEP3: 重复上述操作，直至low>high 时，查找失败

【算法描述】折半查找（非递归算法）
int Search_Bin（SSTable ST，KeyType key）{
//若找到，则函数值为该元素在表中的位置，否则为0
low=1;high=ST.length;
while（low<=high）{
mid=（low+high）/2;
if（key==ST.R[mid].key） return mid;
else if（key<ST.R[mid].key） high=mid-l;
else low=mid+l;
}
return 0;
}

【算法描述】折半查找（递归算法）

int Search_Bin （SSTable ST， keyType key， int low， int high）
{ if（low>high） return 0; //查找不到时返回0
mid=（low+high）/2;
if（key 等于ST.elem[mid].key）return mid;
else if（key 小于ST.elem[mid].key）
……..//递归
else…….//递归
}

折半查找的性能分析

查找过程：每次将待查记录所在区间缩小一半，比顺序查找效率高，时间复杂度O
（log2n）
适用条件：采用顺序存储结构的有序表，不宜用于链式结构

方法三：分块查找（块间有序，块内无序）

分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内
部未必有序）。
然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址
（即头指针）。
分块查找（块间有序，块内无序）

分块查找过程

①对索引表使用折半查找法（因为索引表是有序表）；
②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无
序表）；
分块查找性能分析

例如，当n=9，s=3 时，ASLbs=3.5，而折半法为3.1，顺序法为5

分块查找优缺点
优点：插入和删除比较容易，无需进行大量移动。
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

7.2 树表的查找

① 思想

若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则
查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此
步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成
功。

方法1： 二叉树排序查找

二叉排序树查找：前提是将查找表组织成为一棵二叉排序树。

① 思想

若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则
查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成
功。

那么二叉排序树的特点是什么？

【补充说明】二叉排序树的特点

二叉排序树或是空树，或是满足如下性质的二叉树：
（1）若其左子树非空，则左子树上所有结点的值均小于根结点的值；
（2）若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
（3）其左右子树本身又各是一棵二叉排序树

方法1：二叉树排序查找
二叉排序树查找：前提是将查找表组织成为一棵二叉排序树。
① 思想
若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则
查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此
步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成
功。

② 举例过程

例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序
树过程如下图所示。

例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序
树过程如下图所示。

【算法思想】二叉排序树

（1）若二叉排序树为空，则查找失败，返回空指针。
（2）若二叉排序树非空，将给定值key 与根结点的关键字T->data.key 进行比较：
①若key 等于T->data.key，则查找成功，返回根结点地址；
②若key 小于T->data.key，则进一步查找左子树；
③若key 大于T->data.key，则进一步查找右子树。

③二叉排序树查找的性能分析

在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n 个结点的二
叉排序树的深度，最多为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O
（log2 n），最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O（log2 n），
比顺序查找效率要好，但比二分查找要差。

④结论

二叉排序树的存在问题
这退化成一个顺序查找了，效率很低，如何解决

方法2：平衡二叉排序树查找（平衡二叉树查找）

平衡二叉树查找：前提是首先要调整成一棵平衡二叉排序树。

① 思想
若平衡二叉树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，
则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复
此步骤，若在查找过程中遇到平衡二叉树的叶子结点时，还没有找到待找结点，则查找不
成功。

② 举例过程
第一步：调整成一棵平衡二叉排序树
第二步：平衡二叉树查找
平衡二叉树定义：
若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二
叉树为平衡二叉树。

平衡因子：
将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子（balancefactor）。

说明：一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1 时，则该二叉排序树
就是一棵平衡二叉树。

第一步：非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，
就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。
处理的原则应该是处理与扦入点最近的、而平衡因子又比1 大或比-1 小的结点。下面
将分四种情况讨论平衡处理。
情况1：LL 型的处理（左左型）
情况2：LR 型的处理（左右型）
情况3：RR 型的处理（右右型）
情况4：RL 型的处理（右左型）

情况1：LL 型 的处理（左左型）

如下图所示，在结点C 的左孩子B 上扦入一个左孩子结点A，使C 的平衡因子由1
变成了2，成为不平衡的二叉树序树。
这时的平衡处理为：将C 顺时针旋转，成为B 的右子树，而原来B 的右子树则变成C
的左子树，待扦入结点A 作为B 的左子树。

情况2：LR 型的处理（左右型）

如下图，在结点C 的左孩子A 上扦入一个右孩子B，使的C 的平衡因子由1 变成了2，
成为不平衡的二叉排序树。
这是的平衡处理为：将B 变到A 与C 之间，使之成为LL 型，然后按第（1）种情形
LL 型处理。

情况3：RR 型的处理（右右型）

如下图所示，在A 的右孩子B 上扦入一个右孩子C，使A 的平衡因子由-1 变成-2，
成为不平衡的二叉排序树。
这时的平衡处理为：将A 逆时针旋转，成为B 的左子树，而原来B 的左子树则变成A
的右子树，待扦入结点C 成为B 的右子树。

情况4：RL 型的处理（右左型）

如下图所示，在A 的右孩子C 上扦入一个左孩子B，使A 的平衡因子由-1 变成-2，
成为不平衡的二叉排序树。
这时的平衡处理为：将B 变到A 与C 之间，使之成为RR 型，然后按第
（3） 种情形RR 型处理。

给定一个关键字序列4，5，7，2 ，1，3，6，试生成一棵平衡二叉树。

③平衡二叉树的查找及性能分析

平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查
找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O（n），它的
时间复杂度与二叉排序树的最好时间复杂相同，都为O（log2n）

④ 结论

通过对比分析两种方法的性能。
对比举例：对给定的关键字序列4，5，7，2，1，3，6 的二叉排序树和平衡二叉树：

从二叉排序树可知，查找6 需4 次，平均查找长度ASL=（1+2+2+3+3+3+4）/7=18/7
≈2.57。
从平衡二叉树可知，查找6 需2 次，平均查找长度
ASL=（1+2+2+3+3+3+3）=17/7≈2.43。
从结果可知，平衡二叉树的查找性能优于二叉排序树

③平衡二叉树的查找及性能分析

平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查
找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O（n）。平衡
二叉树最好最坏时间复杂相同均为O（log2n）。

④ 结论

通过对比分析两种方法的性能。
二叉排序树O（n）
平衡二叉树 ASLSucc≈log2（n＋1）–1≈log2n

方法3：B-树

②举例：B-树是一种平衡的多路查找树

③B-树的操作
操作1：B-树的插入
操作2：B-树的删除

插入方法：B-树中[m/2]-1≤节点中的关键字个数≤m-1，并且整个B-树可以看成全部
由关键字组成的树，每次插入一个关键字不是在树中添加一个叶子节点，而是在查找的过
程中找到叶子节点所在层的上一层（叶子节点是记录，上一层是关键字最后一层），在某
个节点中添加一个关键字，若结点的关键字个数不超过m-1，则插入完成，否则产生节点
的分裂。

B-树的最下面一层是空指针
举例：如在3 阶B-树中依次插入关键字30，26，85，7

删除方法：假设删除关键字不在最下层，设关键字为Ki，则可以用Ai 指向子树的最
小关键字或Ai-1 指向子树的最大关键字替换Ki，再删去这个关键字即可，而该关键字必定
在最下层，所以只需讨论删除最下层节点关键字的情况。 假设删除节点在最下层，删除
后仍满足B-树定义则删除结束，否则要进行合并节点的操作，合并可能自下向上层层进行。

举例：在3 阶B-树中依次删除关键字12，50，53，37（可分为三种情况）

方法4： B+树

关键字个数和子树个数一样多
所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本
身依关键字的大小自小而大顺序链接。
所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字。

操作：B+树的查找、插入、删除
在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。

查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。
因此，在B+树种，不管查找成功与否，每次查找都是走一条从根节点到叶结点的路径。
B+树查找的分析类似于B-树。
插入：仅在叶子结点上进行插入，当结点中的关键字个数大于m 时要分裂成两个结点，
他们所含关键字的个数分别为⌊（m+1）/2⌋和⌈（m+1）/2 ⌉ ；并且，他们的双亲结点应同时
包含这两个结点中的最大关键字。
删除：B+树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其在非
终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少
于⌈m/2⌉时，其他兄弟结点的合并过程亦和B-树类似。

（4）散列查找（hash 查找）

优点：不通过大量无效比较，直接找到待查关键字的位置的查找方法
基本术语：
① Hash 方法：通过函数计算存储位置
② Hash 函数：在Hash 方法中使用的函数。
③ Hash 表：按Hash 方法构造出来的表称为Hash 表
④ Hash 地址：通过Hash 函数计算记录的存储位置，称为Hash 地址
⑤ 冲突（Collision）：不同记录的关键字经过Hash 函数的计算可能得到同一Hash 地
址，即key1≠key2 时，H（key1）＝H（key2）

学习Hash 方法需要掌握三个知识点：
知识点1：如何构造Hash 函数
要求：对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的Hash
函数，避免或尽量减少冲突。
知识点2：拟订解决冲突的方案。
要求：允许冲突，但要有解决冲突的方法
知识点3：Hash 函数的性能
知识点1：Hash 函数构造
构造Hash 函数应注意以下几个问题：
①计算Hash 函数所需的时间；
② 关键字的长度；
③ Hash 表的大小；
④ 关键字的分布情况；
⑤ 记录的查找频率。

①直接定址法

此类方法取记录中关键码的某个线形函数值作为
Hash 地址：
Hash（key）=a*key+b
其中：a，b 为常数
这类Hash 函数是一对一的映射，一般不会产生冲突。但是，它要求Hash 地址空间的
大小与关键码集合的大小相同，这种要求一般很难实现。

②除留余数法

设Hash 表中允许的地址数为m，取一个不大于m，但最接近或等于m 的质数p，或
选取一个不含有小于20 的质因子的合数作为除数。这样的Hash 函数为：
Hash（key） = key % p（p≤m）

其中：“%”是整数除法取余的运算，要求这时的质数p 不是接近2 的幂。
这是一种常用的构造Hash 函数的方法。
③ 数字分析法
设有n 个d 位数，每一位可能有r 种不同的符号。这r 种不同的符号在各位上出现的
频率不一定相同。可根据Hash 表的大小，选取其中各种符号分布均匀的若干位作为Hash
地址。计算各位数字中符号分布均匀度的公式：

④ 平方取中法

先计算构成关键码的表示符的内码的平方，然后按照Hash 表的大小取中间的若干位
作为Hash 地址。在平方取中法中，一般取Hash 地址为2 的某次幂。

⑤折叠法——有两种方法：

第一种：移位法是把各部分的最后一位对齐相加。
第二种：分界法是把各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相
加的结果当作散列地址

⑥随机数法

所谓随机数法（random）是指为Hash 表中的关键字选取一个随机函数值作为其Hash
地址。
即：H（key）＝random（key）
其中：random 为随机函数
通常在Hash 表中的关键字长度不等时，采用此方法构造Hash 函数比较合适。

知识点2：拟订解决冲突的方案

原因：散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能
出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关
键字无法存贮，我们把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免
的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。
我们把相互发生冲突的关键字互称为“同义词”。
虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。
发生冲突的可能性却与三个方面因素有关：
第一是与装填因子α有关，所谓装填因子是指散列表中己存入的元素个数n 与散列表
的大小m 的比值，即α=n/m。当α越小时，发生冲突的可能性越小，α越大（最大为1）
时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将α变得太小，这样将
会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。
第二是与所构造的散列函数有关。
第三是与解决冲突的方法有关。

解决冲突的方法

①开放地址法

② 链地址法

链地址法处理冲突的方法是，将通过Hash 函数计算出来的Hash 地址相同的关键码通
过链表链接起来，各链表表头结点组成一个向量。向量的元素个数与关键字个数相同。
举例：设Hash 函数为：H（key）＝key % 7，Hash 表地址范围为0 到6，对关键字序
列（25，6，42，11，15，31，14）按链地址法解决冲突构造的Hash 表。

③ 建立公共溢出区

建立公共溢出区是指当冲突发生时，将这些关键字存储在另设立的一个公共溢出区
中。具体的做法是：假设Hash 地址区间为0 到m-1，设向量HashTable[m]为基本表，每
一个分量存放一个记录，另外设一个向量OverTable[n]为溢出表。将所有与基本表中关键
字冲突的记录，都存放在该溢出表中。
例：设Hash 函数为：H（key）＝key % 7，Hash 表的地址范围为0 到6，对关键字序
列（25，6，42，11，15，31，14）按建立公共溢出区解决冲突构造Hash 表。

建立公共溢出区解决冲突构造的Hash 表示例

④ 再Hash 法

所谓再Hash 法是指当冲突发生时，采用另一个Hash 函数计算关键字的Hash 地址。
即构造一系列的Hash 函数H1（key），H2（key），…，Hk（key），当冲突发生时，依次检查所构造一系列的Hash 函数所得到的Hash 地址是否为空。这种方法不易产生“淤积”
现象，但却增加了计算时间。

知识点3：Hash 查找性能分析（散列查找的性能分析）

散列查找按理论分析，它的时间复杂度应为O（1），它的平均查找长度应为ASL=1，
但实际由于冲突的存在，平均查找长度将会比1 大。

① 线性探查法的性能分析
由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m 无
关，只与所选取的散列函数H 及装填因子α的值和该处理方法有关，成功平均查找长度为：
ASL=1/2 （1+1/（1- α））。
② 拉链法查找的性能分析
由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个
结点次数为2，其余依次类推。平均查找长度为： ASL=1+α/2

练习题：给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查
找、二叉排序树查找、平衡二叉树查找、散列查找（用线性探查法和拉链法）来实现查找，
试画出它们的对应存储形式（顺序查找的顺序表，二分查找的判定树，二叉排序树查找的
二叉排序树及平衡二叉树查找的平衡二叉树，两种散列查找的散列表），并求出每一种查
找的成功平均查找长度。散列函数H（k）=k%11。

解答1：顺序查找的顺序表（一维数组）如下图所示：

顺序存储的顺序表
从上图可以得到顺序查找的成功平均查找长度为：
ASL=（1+2+3+4+5+6+7+8）/8=4.5

解答2：二分查找的判定树
（中序序列为从小到大排列的有序序列）如下图所示。

从上图可以得到二分查找的成功平均查找长度为：
ASL=（1+22+34+4）/8=2.625

解答3：二叉排序树如下图（a），平衡二叉树如下图（b）：

解答4：线性探查法解决冲突的散列表如下图所示。

从上图可以得到线性探查法的成功平均查找长度为：
ASL=（1+1+2+1+3+2+1+8）/8=2.375

解答4：拉链法解决冲突的散列表

从上图可以得到拉链法的成功平均查找长度为：
ASL=（16+22）/8=1.25

散列查找按理论分析，它的时间复杂度应为O（1），它的平均查找长度应为ASL=1，
但实际上由于冲突的存在，它的平均查找长度将会比1 大。下面将分析几种方法的平均查
找长度。

第8 章 排序

8.1 概述

（1）什么是排序？

（2）排序的目的是什么？ ——便于查找！
（3）什么叫内部排序？什么叫外部排序？
若待排序记录都在内存中，称为内部排序；
若待排序记录一部分在内存，一部分在外存，则称为外部排序。
注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然
外部排序要复杂得多。

（4）排序算法的好坏如何衡量？三个指标
时间效率——排序速度（比较次数与移动次数）
空间效率——占内存辅助空间的大小
稳定性——A 和B 的关键字相等，排序后A、B 的先后次序保持不变，则称这种排序
算法是稳定的。

（5）排序算法存储结构：记录序列以顺序表存储

define MAXSIZE 20 //设记录不超过20 个

Typedef int KeyType ; //设关键字为整型量（int 型）
Typedef struct { //定义每个记录（数据元素）的结构
KeyType key ; //关键字
InfoType otherinfo; //其它数据项
}RedType ;
Typedef struct { //定义顺序表的结构
RedType r [ MAXSIZE +1 ]; //存储顺序表的向量，
//r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList ;

（6）排序算法分类
规则不同
插入排序
交换排序
选择排序
归并排序
基数排序
时间复杂度不同

简单排序O（n^2）

先进排序O（ nlog2n）

8.2 插入排序

基本思想：

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适
当位置上，直到对象全部插入为止。
即边插入边排序，保证子序列中随时都是排好序的
插入排序的基本思想：

插入排序的基本步骤：
STEP1：在R[1..i-1]中查找R[i]的插入位置， -1].key；
STEP2：将R[j+1..i-1]中的所有记录均后移一个位置；
STEP3：将R[i] 插入到R[j+1]的位置上。
具体实现时又根据不同的算法描述，分为三种插入算法！

具体实现的三种不同算法：

直接插入排序（基于顺序查找）
折半插入排序（基于折半查找）
希尔排序（基于逐趟缩小增量）

第一种：直接插入排序
排序过程：整个排序过程为n-1 趟插入，即先将序列中第1 个记录看成是一个有序子
序列，然后从第2 个记录开始，逐个进行插入，直至整个序列有序。

直接插入排序举例

直接插入排序
从R[i-1]向前进行顺序查找，监视哨设置在R[0]

直接插入排序（程序重新输入）
void InsertSort（SqList &L）
{int i，j;
for（i=2;i<=L.length;++i）
if （ L.r[i] .key<L.r[i-1]. key） //将L.r[i]插入有序子表
{ L.r[0]=L.r[i]; // 复制为哨兵
L.r[i]=L.r[i-l];
for（j=i-2; L.r[0].key<L.r[j].key;--j）
L.r[j+1]=L.r[j]; // 记录后移
L.r[j+l]=L.r[0]; //插入到正确位置
}
}

算法分析 for（i=2;i<=L.length;++i）
设对象个数为n，则执行n-1 趟 if（ L.r[i].key<L.r[i-1].key）
比较次数和移动次数与初始排列有关
最好情况下：
每趟只需比较1 次，不移动
总比较次数为n-1

算法分析

最坏情况下：第i 趟比较i 次，移动i+1 次

比较次数

移动次数

直接插入排序算法分析

若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况
平均情况比较次数和移动次数为n^2/4
时间复杂度为 o（n^2）
空间复杂度为 o（1）
是一种稳定的排序方法

直接插入排序

第二种：折半插入排序

在插入r[i] 时，利用折半查找法寻找 r[i] 的插入位置

void BlnsertSort （ SqList &L ）
{ for （ i = 2; i <= L.length ; ++i ）
{ L.r[0] = L.r[i]; low = 1 ; high = i-1;
while （ low <= high ）
{ m = （ low + high ）/ 2 ;
if （ L.r[0].key < L.r[m]. key ）high = m -1 ;
else low = m + 1;
}
for （ j=i-1; j>=high+1;--j ）
L.r[j+1] = L.r[j];
L.r[high+1] = L.r[0];
}
} // BlnsertSort

算法分析

折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快
它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。
在插入第i 个对象时，需要经过⌊log2i+1⌋次关键码比较，才能确定它应插入的位置
当n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情
况要差
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序
执行的关键码比较次数要少
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

折半插入排序算法分析

减少了比较次数，但没有减少移动次数
平均性能优于直接插入排序
时间复杂度为 o（n^2）
空间复杂度为 o（1）
是一种稳定的排序方法

第三种：希尔排序

算法思想的出发点：
直接插入排序在基本有序时，效率较高
在待排序的记录个数较少时，效率较高

基本思想：
先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的
记录“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序技巧：
子序列的构成不是简单地“逐段分割”
将相隔某个增量dk 的记录组成一个子序列

让增量dk 逐趟缩短（例如依次取5，3，1）

直到dk＝1 为止。

优点：

小元素跳跃式前移
最后一趟增量为1 时，序列已基本有序
平均性能优于直接插入排序

例如，n=8，数组R 的八个元素分别为：17，3，30，25，14，17，20，9 给出希尔排
序算法执行过程。

希尔排序算法（思想）

（1）主程序要执行多个dk，从dk 初始值计算到1
（2）每一个dk，都是插入排序
但不是相邻，是相距dk 的元素划分为一组执行排序
程序两部分构成，一部分是主程序，一部分是每个dk
希尔排序算法（主程序）

void ShellSort（SqList &L，int dlta[ ]，int t）{
//按增量序列dlta[0…t-1]对顺序表L 作Shell 排序
for（k=0；k<t；++k）
ShellInsert（L，dlta[k]）；
//增量为dlta[k]的一趟插入排序
} // ShellSort

希尔排序算法（其中某一趟的排序操作）
void ShellInsert（SqList &L， int dk）
{ for（i=dk+1; i<=L.length; ++ i） //开始将r[i]插入有序增量子表
if（L.r[i].key <L.r[i-dk].key） {
L.r[0]=L.r[i]; //暂存在r[0]
for（j=i-dk; j>0 &&（L.r[0].key<L.r[j].key）; j=j-dk）
L.r[j+dk]=L.r[j]; //关键字较大的记录在子表中后移.
L.r[j+dk]=L.r[0]; //在本趟结束时将r[i]插入到正确位置
}
}

算法分析

时间复杂度是n 和d 的函数：

空间复杂度为 o（1）
是一种不稳定的排序方法
如何选择最佳d 序列，目前尚未解决
最后一个增量值必须为1，无除1 以外的公因子
不宜在链式存储结构上实现

8.3 交换排序

基本思想

两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

第一种：起泡排序O（n^2）
第二种：快速排序O（ nlog2n ）

第一种：冒泡排序示例

void main（） {
int a [11]; /a[0]不用，只用a[1]~a[10]/;
int i，j，t;
printf（"\nlnput 10 numbers: \n"）;
for（i=1;i<=10;i++）
scanf（"%d"，&a[i]）;
for（i =1;i <=9; i++）
for（j=1;j<=10-i;j++）
if（a[j]>a[j+l]） {
t = a [ j ] ; a [ j ] = a [ j+ l ] ; a [ j + l ] = t;
}
for（i=l;i<=10;i++）
printf（"%d "，a[i]）;
}

第一种：冒泡排序示例

for（i =1;i <=9;j ++）
for（j=10;j>i;j--）
if（a[j]<a[j-1]）
{a[j] <-> a[j-1]}

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元
素；
一旦下趟没有交换，还可提前结束排序

void bubble_sort（SqList &L） {
int m，i，j，flag=1; RedType x;
m=n-1;
while（（m>0）&&（flag==l））
{ flag=0;
for（j=1;j <=m;j ++）
flag=1;
x=L.r[ j ] ;L.r[j ]=L.r[:j+l]; L.r[j+l]=x; //交换
} //endif
m--;
} //endwhile
}

算法分析
设对象个数为n
比较次数和移动次数与初始排列有关最好情况下：
只需1 趟排序，比较次数为n-1，不移动

冒泡排序算法分析
最坏情况下：
需 n-1 趟排序，第i 趟比较n-i 次，移动3（n-i）次

时间复杂度为o（n^2）
空间复杂度为o（1）
是一种稳定的排序方法

第二种：快速排序

基本思想：
任取一个元素（如第一个） 为中心
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个
快速排序的特点：
①每一趟的子表的形成是采用从两头向中间交替式逼近法；
②由于每趟中对各子表的操作都相似，可采用递归算法。

快速排序示例

例如，给定排序码为（46，55，13，42，94，05，17，70）

快速排序思想：

（1）递归
（2）每一次剖分是一个核心过程枢轴值的选择

先从后边开始，交替相向行进

void main （ ）
{ QSort （ L， 1， L.length ）; }
void QSort （ SqList &L，int
{ if（ low < high ）
{ pivotloc = Partition（L， low， high ） ;
Qsort （L， low， pivotloc-1） ;
Qsort （L， pivotloc+1， high ）
}
}

int Partition （ SqList &L， int low， int high ） {
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while （ low < high ）
{ while （ low < high && L.r[high].key >= pivotkey ）
--high;
L.r[low] = L.r[high];
while （ low < high && L.r[low].key <= pivotkey ）
++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[0];
return low;
}

算法分析

可以证明，平均计算时间是O（nlog2n）。
实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最
好的一个。

快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low 和high）。
最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O（log2n） 。
最好：划分后，左侧右侧子序列的长度相同
最坏：从小到大排好序，递归树成为单支树，每次划分只得到一个比上一次少一个对
象的子序列，必须经过 n-1 趟才能把所有对象定位，而且第i 趟需要经过n-i 次关键码比
较才能找到第i 个对象的安放位置

快速排序算法分析：
时间效率：O（nlog2n） —每趟确定的元素呈指数增加
空间效率：O（log2n）—递归要用到栈空间
稳 定 性： 不稳定—可选任一元素为支点。

8.4 选择排序

基本思想：
每一趟在后面 n-i +1 个中选出关键码最小的对象， 作为有序序列的第i 个记录

简单选择排序示例

例如，n=8，数组R 中的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序
过程

简单选择排序

void SelectSort（SqList &K）
{
for （i=l; i<L.length; ++i）
{ / / 在L.r[i..L.length]中选择key 最小记录
k=i;
for（ j=i+l;j<=L.length ; j++）
if （ L.r[j].key <L.r[k].key） k=j;
if （k!=i）L.r[i]<-> L.r[k];
}
}

算法分析
移动次数
最好情况：0
最坏情况：3（n-1）

比较次数：

时间复杂度：O（n²）
空间复杂度：O（1）
稳定

第二种：堆排序

什么是堆？

n 个元素的序列{k1，k2，…，kn}，当且仅当满足下列关系时，成为堆：

如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。

关键字初始序列为：88，47，37，56，21，15 初始堆的建立示例

例如排序码46，55，13，42，94，05，17，70，建立初始大顶堆

注：初始从非叶节点开始调整

对排序码46，55，13，42，94，05，17，70，建成大根堆后，堆排序过程：

将其结果按完全二叉树形式输出，则得到结果为：05，13，17，42，46，55，70，94，
即为堆排序的结果
堆的重新调整
如何在输出堆顶元素后调整，使之成为新堆？

输出堆顶元素后，以堆中最后一个元素替代之
将根结点与左、右子树根结点比较，并与小者交换
重复直至叶子结点，得到新的堆

算法分析
时间效率：O（nlog2n）空间效率：O（1）
稳 定 性：不稳定
适用于n 较大的情况

8.5 归并排序

归并：将两个或两个以上的有序表组合成一个新有序表2-路归并排序

排序过程
初始序列看成n 个有序子序列，每个子序列长度为1
两两合并，得到⌊n/2⌋个长度为2 或1 的有序子序列
再两两合并，重复直至得到一个长度为n 的有序序列为止

算法分析
时间效率：O（nlog2n）
空间效率：O（n）
稳定性：稳定

8.6 基数排序

前面的排序方法主要通过关键字值之间的比较和移动而基数排序不需要关键字之间
的比较

多关键字排序

方法1：最高位优先MSD （ Most Significant Digit first ）
方法2：最低位优先LSD （ Least Significant Digit first）
方法3：链式基数排序：用链表作存储结构的基数排序

方法1：最高位优先法

先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的
k1 值；
然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；
最高位优先法
依次重复，直至就每个子序列对最低位关键字kd 排序，就可以得到一个有序的序列。
十进制数比较可以看作是一个多关键字排序

最高位优先法

方法2：最低位优先法

首先依据最低位排序码Kd 对所有对象进行一趟排序再依据次低位排序码Kd-1 对上一
趟排序结果排序依次重复，直到依据排序码K1 最后一趟排序完成，就可以得到一个有序
的序列。
这种方法不需要再分组，而是整个对象组都参加排序

最低位优先法

方法3：链式基数排序

先决条件：
— 知道各级关键字的主次关系
—知道各级关键字的取值范围
利用“分配”和“收集”对关键字进行排序:
首先对低位关键字排序，各个记录按照此位关键字的值‘分配’到相应的序列里。
按照序列对应的值的大小，从各个序列中将记录‘收集’，收集后的序列按照此位
关键字有序。
在此基础上，对前一位关键字进行排序。

链式基数排序步骤

设置10 个队列，f[i]和e[i]分别头指针和尾指针
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至
10 个链队列中，每个队列记录的关键字的个位相同
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队
头记录，重新将10 个队列链成一个链表
重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到
一个有序序列

算法分析

n 个记录
每个记录有d 位关键字
关键字取值范围rd（如十进制为10）
重复执行d 趟“分配”与“收集”
每趟对n 个记录进行“分配”，对rd 个队列进行“收集”
需要增加n+2rd 个附加链接指针。
链式基数排序算法分析
时间效率：O（d（ n+rd））
空间效率：O（n+rd）
稳 定 性：稳定

（1）排序算法比较

（数据不是顺次后移时将导致方法不稳定）

（2）排序算法比较

O（n2）、O（nlogn）、O（n^(1+ε) ）、O（n）

快速排序是基于比较的内部排序中平均性能最好的
基数排序时间复杂度最低，但对关键字结构有要求

知道各级关键字的主次关系
知道各级关键字的取值范围

（3）排序算法比较

为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构
直接插入排序、归并排序、基数排序
不宜采用链表作为存储结构的
折半插入排序、希尔排序、快速排序、堆排序

（4）排序算法选择规则

n 较大时

① 分布随机，稳定性不做要求，则采用快速排序
② 内存允许，要求排序稳定时，则采用归并排序
③ 可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序

n 较小时

① 基本有序，则采用直接插入排序
② 分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排
序

8.7 外部排序

（1）外部排序基本思想
前面的讨论都是内部排序的方法，及整个排序过程都是 在内存中完成的，并不涉及
数据的内外存交换问题，但如果待排序的记录数目很大，无法一次性调入内存，整个排序
过程就必须借用外存分批调入内存才能完成

（2）算法步骤

外部排序基本上由两个相对独立的阶段组成：
STEP1:首先，按可用内存大小， 将外存上含n 个记录的文件分成若干长度为l 的子文
件或段（segment），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序
后得到的有序子文件重新写入外存， 通常称这些有序子文件为归并段或顺串（run）；
STEP2:然后， 对这些归并段进行逐躺归并， 使归并段（有序的子文件）逐渐由小至
大， 直到得到整个有序文件为止。
例：一文件含10000 记录， 通过10 次内部排序得到10 个初始归并段R1…R10， 其
中每一段都含有1000 个记录

然后作两两归并：

由10 个初始归并段到一个有序文件， 共进行了4 趟归并，每一趟都从m 个归并段得
到ceil（m/2）个归并段。这种归并方法称为2-路平衡归并。
外存上信息的读/写是以“物理块”为单位进行的， 假设每个物理块可以容纳200 个
记录，则每一趟归并需进行50 次“读”和50 次“写”， 4 趟归并加上内部排序时所需进
行的读/写使得在外排序中总共需进行500 次读/写。

分析d 和“归并过程”的关系：
若对上例进行5 路平衡归并：

仅需两趟归并， 总的读/写次数便减少为：
2x100+100=300， 比2 路归并减少了200 次的读/写。
对同一文件， 进行外排序时所需读/写

可见：若能增加k 或减少m 便能减少s， 因此减少d.
但是，是不是K 越大就越好呢？我们来看看算法的时间复杂度。

下面分析一下：

将40 个文件编号1-40，1 和2 归并，3 和4 归并...39 和40 归并，生成了20 个文件，
再将这20 个文件继续两路归并。
从40 个文件变成20 个文件，相当于把所有10G 的数据从磁盘读出，写到磁盘上，从
20 个文件到10 个文件，也相当于把10G 的数据从磁盘读出，再写到磁盘。这种磁盘IO
操作一共要执行6 次。（2^6=64>40）
再来考虑K 路归并。所谓K 路归并，就是一次比较K 路数据，选出最小的。例如当
K=10，则是将40 个文件分成1-10，11-20，21-30，31-40。对1-10，由于已序，故只要比
较出这10 个文件的第一个数，看哪个最小，哪个就写到新文件，再进行下一轮的比较。
只要2 次磁盘IO 可以
假设我们将文件分为m 份，使用K 路归并，则磁盘IO 的次数就是⌈logkm⌉。我们当然
是希望这个值越小越好。但是是不是K 越大就越好呢？我们来看看算法的时间复杂度。
对于总共n 个数据的K 路归并，每次需比较K-1 次，才能得出结果中的一个数据，n
个数据就需要比较（n-1）（K-1）次对于总共n 个数据，分为m 份，使用K 路归并，总共需要比较：
⌈logkm⌉* （n-1）（K-1）= （logm/logK）*（n-1）（K-1） = logm*（n-1）*（K-1）/logK
当K 增大时，（K-1）/logK 是增大的，也即时间复杂度是上升的。
因此要么K 不能太大，要么找出一个新的方法，使得每次不用比较K-1 次才得出结果
中的一个数据。我们选择后者，这种方法就是失败树。

多路平衡归并的实现与问题，解决方法：

---

亲爱的读者：有时间可以点赞评论一下