导图社区 数据结构（C语言版）
- 557
- 18
- 6
- 举报
数据结构（C语言版）
数据结构是计算机编程所必须掌握的重要内容。本图配套相关的代码和图解，对数据结构的基本知识体系进行了分类总结。全图总共分为11页导图，方便学习和查看。对于初学者来说无疑是必备的学习工具！
编辑于2021-03-10 14:57:27
- 相似推荐
- 大纲
数据结构（C语言版）
第1章 绪论
第2章 线性表
第3章 栈和队列
第4章 字符串
第5章 多维数组和广义表
第6章 树与二叉树
第7章 树与二叉树的应用
第8章 图
第9章 查找
第10章 排序
第1章 绪论
1.1 数据结构的概念及分类
1.1.1 为什么要学习数据结构
算法和数据结构是程序的核心
1.1.2 与数据结构相关的基本术语
1）数据
1. 定义
数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合
2. 分类
· 数值数据
整数
浮点数
复数
双精度数
...
主要用于工程和科学计算，商业事务处理
· 非数值数据
字符
字符串
文字
图像
图形
语音
...
2）数据元素
1. 定义
数据的基本单位是数据元素，它是计算机处理或访问的基本单位
2. 别名
· 元素
· 记录
· 结点
· 表项
3）数据项
1. 数据元素可以是单个元素（称为原子），也可以是由数据项构成
2. 别名
· 属性
· 字段
· 域
3. 分类
初等项
不能再分割的最小单位
组合项
初等项组合而成
4）数据对象
1. 定义
数据的子集。具有相同性质的数据成员（数据元素）的集合
5）数据结构
1. 定义
指某一数据元素集合中的所有数据成员之间的关系
完整的定义为：Data_Structure = { D，R，M }
D是某一数据元素的集合； R是该集合中所有数据成员之间的关系的有限集合； M是作用在该集合所有数据成员之上的方法（或操作）。
2. 数据结构是数据的组织形式
· 数据元素间的逻辑关系，即数据的逻辑结构； · 数据元素及其关系在计算机存储内的表示，即数据的物理结构； · 数据的运算，即对数据元素施加的操作。
3. 逻辑结构
数据的逻辑结构抛弃了数据元素及其关系的实现细节，只反映了系统的需求（从用户使用层面上）而不考虑如何实现
· 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关。 · 数据的的逻辑结构与数据元素的内容无关。 · 数据的逻辑结构与它所包含的数据元素个数无关。 · 数据的逻辑结构与数据元素所处位置无关。
逻辑结构分类
线性结构
线性表
非线性结构
（多维数组）
（广义表）
树
图（或网络）
无结构
集合
4. 存储（物理）结构
1）存储结构的三个任务
内容存储
存储各数据元素的内容或值，每个元素占据独立的存储空间。
关系存储
直接或简介地，显式或隐式地存储各数据元素之间的逻辑关系。
附加存储
为使施加于数据结构上的运算得以实现而附加的存储空间。
2）分类
顺序存储表示
用一个连续的空间来存储数据元素。通常用一维或二维数组来描述。
链接存储表示
不必事先分配存储空间，在运行时动态分配存储空间，链入到系统中。
这两种存储结构通常用于在内 存中辅助算法或程序的实现。
索引存储表示
用于对索引文件的实现。
散列存储表示
用于直接存取文件的实现。
这两种存储结构常用于外存中辅助算法或程序的实现。
6）数据类型
1. 定义
一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称
2. 分类
基本数据类型（原子类型）
· 字符型（char）
· 整型（int）
· 浮点型（float）
· 双精度型（double）
· 无值（void）
构造数据类型
7）抽象数据类型
1. 抽象
抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节
2. 定义
抽象数据类型由用户定义，用以表示应用问题的数据模型，又称数据抽象
3. 三大特征
· 信息隐蔽
把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会
· 数据封装
把数据和操作封装在一起，从语义上更加完整
· 使用与实现相分离
使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性
1.1.3 数据结构的分类
1. 分解和抽象（核心技术）
数据的分解和抽象
· 分解数据层次
数据-数据元素-数据项
· 抽象
舍弃数据元素与实现相关的细节，得到数据的逻辑结构
处理的分解和抽象
· 分解
将处理需求划分成各种功能
· 抽象
舍弃功能的实现细节
2. 逻辑结构与储存结构
3. 逻辑结构的分类
1）线性结构
· 线性表
· 向量
· 栈
· 队列
· 字典
2）非线性结构
· 树
· 图
· （多维数组）
· （广义表）
3）集合结构（数据元素没有联系）
直接存取结构
· 数组
· 文件
顺序存储结构
· 栈
· 队列
字典
1.1.4 数据结构的存储结构
1. 要素
1）访问频率
2）修改频率
3）安全保密
2. 储存方式
1）顺序存储方式
2）链接存储方式
3）索引存储方式
4）散列存储方式
1.1.5 定义在数据结构上的操作
1）创建
2）销毁
3）查找
4）插入
5）删除
6）排序
1.4 算法分析和度量
1.4.1 算法的评价标准
1）正确性
输入正确的数据，应得出正确的结果。每一个算法，要考虑前置条件和后置条件
前置条件：算法正确执行需满足的条件
后置条件：算法执行后应得到的正确结果
2）健壮性
算法必须能预见可能的错误，能对意外情况适当地做出反应和处理
3）可读性
算法的程序逻辑必须易于阅读和理解，这样才能正确地调试、更细和扩展
4）高效性
算法应具有良好的时空性能
时间复杂度度量
空间复杂度度量
5）简单性
算法的简单性直接与出错率相关
环路复杂度度量
代码行复杂度度量
1.4.2 算法的时间和空间复杂度
1. 算法的复杂度度量与问题规模
2. 时间复杂度度量
运行时间 = 算法每条语句执行时间之和
每条语句执行时间 = 该语句的执行次数（频度）× 语句执行一次所需时间
语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定
设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和
3. 空间复杂度度量
1）固定部分
附加存储空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占空间
2）可变部分
尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过malloc和free命令动态使用空间
1.4.3 算法的渐近分析
1. 渐近的时间复杂度
2. 大O渐进表示
T(n)=2n3+2n2+2n+1 算法的大O表示：T(n)=O(n3)
加法规则
乘法规则
3. 渐近的空间复杂度
1.3 算法和算法设计
1.3.1 算法的定义和特性
1. 算法定义
一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
算法 + 数据结构 = 程序
2. 特性
1）有输入
有 0 个或多个输入
2）有输出
有一个或多个输出（处理结果）
3）确定性
每步定义都是确切、无歧义的
4）有穷性
算法应在执行有穷步后结束
5）有效性（可行性）
每一条运算应足够基本，可用计算机指令实现
1.3.2 算法的设计步骤
1）理解需求
2）设计思路
3）算法框架
4）程序实现
5）程序调试
· 自顶向下，逐步求精
· 先全局后局部，先整体后细节
1.3.3 算法设计的基本方法
1. 穷举法
按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解
2. 迭代法
由一个量的原值求出它的新值，不断地再用新值替代原值求出它的下一个新值，直到得到满意的解
3. 递推法
由已知至i-1规模的解，通过递推，获得规模为i的解
4. 递归法
把规模为N的问题分解成一些规模较小的问题，然后从这些小问题的解构造出大问题的解
5. 动态规划
用表来记录所有已解决子问题的解，在需要时再找出已求得的解，可以避免大量的重复计算，从而得到时间复杂度为多项式级的算法
1.2 使用C语言描述数据结构
1.2.1 数据结构
1. 结构型（struct）
2. 联合型（union）
3. 指针型（pointer）
1.2.2 算法的控制结构
1. 顺序型
2. 选择型（if、switch）
3. 重复型（for、while、do-while）
1.2.3 算法的函数结构
1. 函数的一般形式
2. 函数的参数传递
3. 函数的返回值
1.2.4 动态储存分配
malloc函数
1.2.5 逻辑和关系运算的约定
1.2.6 输入和输出
第2章 线性表
2.1 概述
2.1.1 线性表的定义和特点
1. 定义
n（>=0）个数据元素的有限序列，记作（a1，a2，…，an）
2. 特点
1）线性表是一个有限序列，每相邻两个元素之间都有直接前驱和直接后继的逻辑关系
· 存在唯一的首元和尾元
· 除首元外，其他元素有且仅有一个直接前驱，首元没有直接前驱
· 除尾元外，其他元素有且仅有一个直接后继，尾元没有直接后继
2）线性表中每一个元素都有自己的数据类型
3）线性表中每一元素都有“位置”和“值”
4）线性表中元素的值与它的位置之间可以有关系，可以没有关系
2.1.2 线性表的主要操作（*）
2.2 顺序表
2.2.1 顺序表的定义和特点
1. 定义
将线性表中的元素相继存放在一个连续的存储空间中，即构成顺序表
2. 特点
1）各个元素的逻辑顺序与其存放的物理顺序一致
2）它是线性表的顺序存储表示，可利用一维数组描述存储结构
3）可顺序存取，可按下标直接存取
2.2.2 顺序表的结构定义
1. 静态存储表示
顺序表的静态结构定义 #define maxSize 100 //最大允许长度 typedef int DataType; //元素的数据类型 typedef struct { dataType data[maxSize]; //存储数组 int n; //当前表元素个数 } SeqList;
· 顺序表静态定义，假定L是一个类型 SeqList 的顺序表，一般用 L.data[i] 来访问它。 · 表一旦装满，不能扩充。
2. 动态存储表示
顺序表的动态结构定义 #define initSize 100 //最大允许长度 typedef int DataType; //元素的数据类型 typedef struct { DataType *data; //存储数组 int n; //当前表元素个数 int maxSize; //表的最大长度 } SeqList;
· 顺序表动态定义，它可以扩充，新的大小计入数据成员maxSize中。
2.2.3 顺序表主要操作的实现（*）
2.2.4 顺序表主要操作的性能分析
1. 查找操作的性能分析
2. 插入操作的性能分析
3. 删除操作的性能分析
2.2.5 顺序表的应用举例
2.4 顺序表与单链表的比较
1）储存分配方式
顺序表
可以是静态的，也可以是动态的
链表
只能是动态
2）储存密度）
（结点数据本身所占的存储量/结点结构所占的存储总量
顺序表
储存密度=1
链表
储存密度<1
3）存取方式
顺序表
可以随机存取，也可以顺序存取
链表
只能顺序存取
4）插入/删除时移动元素的个数
顺序表
移动接近一半的个数
链表
不移动元素，只改变指针
2.5 单链表的应用：一元多项式及其运算
2.5.1 一元多项式的表示
2.5.2 多项式的结构定义
1）静态定义
多项式的静态定义 const int maxDegree = 20; //最大允许阶数 typedef struct Polynomial { //多项式结构定义 int degree; //实际阶数 float coef [maxDegree+1]; //系数数组 }
2）动态定义
多项式的动态定义 #define DefaultSize 20; //默认数组大小 typedef struct data { //多项式的项定义 float coef; //系数 int exp; //指数 }; typedef struct Polynomial { //多项式结构定义 int maxSize; //数组最大保存项数 int n; //实际项数 data *Term; //项数组 }
3）链表定义
多项式链表的定义 typedef struct node { //多项式数据定义 float coef; //系数 int exp; //指数 struct node * link; //链接指针 } Term，*Polynomial;
2.5.3 多项式的加法
1）当pa和pb没有检测完各自的链表时，比较当前检测结点的指数域
· 指数不等
小者加入C链，相应检测指针pa或者pb进1
· 指数相等
对应项系数相加。若相加结果不为零，则结果（存于pa所指结点中）加入C链，否则不加入C链，检测指针pa与pb都进1
2）当pa或pb指针中有一个已经检测完自己的链表，把另一个链表的剩余部分加入到C链中
2.5.4 多项式的乘法（*）
2.3 单链表
2.3.1 单链表的特点
· 每个元素(表项)由结点(Node)构成
· 线性结构
· 结点可以连续，可以不连续存储
· 结点的逻辑顺序与物理顺序可以不一致
· 表可扩充
2.3.2 单链表的结构定义
单链表的结构定义 typedef char DataType; typedef struct node { //链表结点 DataType data; //结点数据域 struct node * link; //结点链域 } LinkNode，*LinkList; //链头指针
2.3.3 单链表中的插入与删除
1）插入
· 在第一个结点前插入
newnode->link = first ; first = newnode; //修改头指针
· 在链表中间插入
newnode->link = p->link; p->link = newnode；
· 在链表末尾插入
newnode->link = p->link; p->link = newnode；
2）删除
· 删除表中第1个元素
· 删除表中或表尾元素
2.3.4 带头结点的单链表
头结点位于表的最前端，本身不带数据，仅标志表头
设置目的
· 统一空表与非空表的操作
· 简化链表操作的实现
2.3.5 单链表的顺序访问与尾递归
1）前插法建立单链表
· 从一个空表开始，重复读入数据： · 生成新结点 · 将读入数据存放到新结点的数据域中 · 将该新结点插入到链表的前端 · 直到读入结束符为止
2）后插法（尾插法）建立单链表
· 每次将新结点加在插到链表的表尾； · 设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面； · 尾指针 r 初始时置为指向表头结点地址
2.3.6 单链表的应用举例（*）
2.3.7 循环单链表
循环单链表是单链表的变形。链表尾结点的link指针不是NULL，而是指向了表的前端。为简化操作，在循环单链表中往往加入头结点
注意事项
· 循环单链表的判空条件是： first->link == first
· 在搜寻过程中，没有一个结点的link域为空： for ( p = first->link; p != first; p = p->link ) do S;
· 在链表中将指针p定位于第i个结点的操作为： CircNode *p = first; int k = 0; //first是头结点 while ( p->link != first && k < i ) //回到头结点失败 { p = p->link; k++; } //否则 p 指到目标
图示与结构定义
循环单链表的结构定义 typedef int DataType; typedef struct node { //循环链表定义 DataType data; //结点数据 struct node *link; //后继结点指针 } CircNode，*CircList;
2.3.8 双向链表
结点结构
结构定义
循环双链表的定义 typedef int DataType; //每个元素的类型 typedef struct node { //结点定义 DataType data; //数据 int freq; //访问计数 struct node *lLink，*rLink; //指针 } DblNode，*DblList; //双向链表
2.3.9 静态链表
数组中每一个元素附加一个链接指针，就形成静态链表结构。链表的头结点在A[0]
结构定义
静态链表的结构 #define maxSize 100 //静态链表大小 typedef int DataType; typedef struct { DataType data; //结点数据 int link; //结点链接指针 } SLNode; typedef struct { SLNode elem[maxSize+1]; int avail; //当前可分配空间首地址 } StaticLinkList;
第3章 栈和队列
3.1 栈
3.1.1 栈的概念
1. 栈的定义
只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶 (top)，另一端称为栈底 (bottom)
2. 栈的特性
先进后出
3. 示意图
3.1.2 顺序栈
1. 结构定义
栈的顺序表示 — 顺序栈 #define initSize 100 #define increament 20 typedef int SElemType; typedef struct { //顺序栈定义 SElemType *elem; //栈数组 int top, maxSize; //栈顶指针及栈大小 } SeqStack;
2. 双栈共享一个栈空间
两个栈共享一个数组空间V[maxSize]，设立栈顶指针数组t[2]和栈底指针数组 b[2]
t[i]和b[i]分别指示栈i的栈顶与栈底（i = 0, 1）
初始 t[0] = b[0] = -1，t[1] = b[1] = maxSize
栈满条件：t[0]+1 == t[1] //栈顶指针相遇
栈空条件：t[0] = b[0] 或 t[1] = b[1] //退到栈底
3.1.3 链式栈
· 顺序栈有栈满问题，一旦栈满需要做溢出处理，扩充栈空间，时间和空间开销较大
· 链式栈无栈满问题，只要存储空间还有就可扩充
· 链式栈的栈顶 在链头，插入与删除仅在栈顶处执行
· 链式栈适合于多栈操作，无需大量移动存储
3.1.4 栈的混洗
1. 定义
通过控制入栈和退栈的时机，可以得到不同的退栈序列，这叫做栈的混洗
2. 退栈种数
一般地，有n个元素按序号1, 2, …, n 进栈，轮流让1在出栈序列的第1, 第 2, …第n位，则可能的出栈序列数为：
3.2 队列
3.2.1 队列的概念
1. 定义
队列是只允许在一端删除，在另一端插入的线性表
2. 特性
先进先出
3. 结构定义
队列的顺序存储表示 — 顺序队列 #define queSize 50; typedef int QElemType; //每个元素的数据类型 typedef struct { //顺序队列的结构定义 QElemType elem[queSize]; //队列存储数组 int rear, front; //队尾与队头指针 } SeqQueue, CircQueue;
4. 示意图
5. 2种进队出队方案
1）先加元素再动指针
· 进队时先将新元素按rear指示位置加入，再让队尾指针进一rear = rear + 1
· 队尾指针指示实际队尾的后一位置
· 出队时先将下标为front的元素取出，再将队头指针进一front = front + 1
· 队头指针指示实际队头的位置
2）先动指针再加元素
微软Visual C++ STL按此处理
· 进队时先让队尾指针进一rear = rear + 1，再将新元素按rear指示位置加入
· 队尾指针指示实际队尾的位置
· 出队时先将队头指针进一front = front + 1，再将下标为front的元素取出
· 队头指针指示实际队头的前一位置
队满时再进队出现的溢出往往是假溢出，即还有空间但用不上，为了有效利用队列空间，可将队列元素存放数组首尾相接，形成循环队列
3.2.2 循环队列
1. 说明
队列存放数组被当作首尾相接的环形表处理
队头、队尾指针加1时从queSize-1直接进到0，可用语言的取模（%）运算实现
注意，进队和出队时指针都是顺时针前进
2. 操作基本介绍
队头指针进1: front = (front+1) % queSize
队尾指针进1: rear = (rear+1) % queSize
队列初始化：front = rear = 0
队空条件：front == rear
队满条件：(rear+1) % queSize == front
3. 图示
3.2.3 链式队列
1. 说明
· 链式队列采用不带头结点的单链表存储队列元素，队头在链头，队尾在链尾
· 链式队列在进队时无队满问题，但有队空问题
· 队空条件为 front->link == NULL，不必判断是否 rear == front
· 链式队列特别适合多个队列同时操作的情形。在并行处理、排序等方面有用
2. 结构定义
链式队列的结构定义 typedef int QElemType; //元素的数据类型 typedef struct node { QElemType data; //队列结点数据 struct node *link; //结点链指针 } LinkNode; typedef struct { //队列结构定义 LinkNode *rear, *front; //队尾与队头指针 } LinkQueue;
3.7 优先队列
3.7.1 优先队列的概念
1. 定义
每次从队列中取出的是具有最高优先权的元素
2. 结构定义
优先队列的定义 #define maxPQSize 50 typedef int PQElemType; typedef struct { PQElemType elem[maxPQSize]; //存放数组 int n; //当前元素计数 } PQueue;
3. 说明
· 每次在优先队列中插入新元素时，新元素总是插入在队尾
· 在优先队列中每次从队列中查找权值最小的元素删除，再把队列最后元素填补到被删元素位置
3.7.2 优先队列的实现（*）
3.6 双端队列
3.6.1 双端队列的概念
1. 定义
双端队列（Deque）是对队列的扩展，它允许在队列的两端进行插入和删除。我们可以把双端队列视为底靠底的双栈，但它们相通，成为双向队列。两端都可能是队头和队尾
2. 图示
3.6.2 输入受限的双端队列
只能在双端队列的一端输入
3.6.3 输出受限的双端队列
只能在双端队列的一端输出
3.6.4 双端队列的储存表示
结构定义
顺序双端序列的结构定义 #include<stdio.h> #define maxSize 100 // 双端队列的最大容量 typedef int DQElemType; // 可在主程序定义 typedef struct{ // 队列结构定义 DQElemType elem[maxSize]; // 环形储存数组 int end1, end2; // 队头和队尾指针 } SeqDeque;
3.5 在算法设计中使用递归
3.5.1 汉诺塔问题与分治法
分治法
在解决一个规模比较大的问题时，首先研究问题的结构，把它分解为一个或几个规模比较小的同类型问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解
3.5.2 迷宫问题与回溯法
回溯法（试探法）
这种方法一步步向前试探，当某一步有多种选择时，可以先任意选择一种，只要这种选择暂时可行就继续向前，一旦发现到达某步后无法再前进，说明前面已经做的选择可能有问题，就可以后退，回到上一步重新选择（称为回溯）。
3.4 队列的应用
3.4.1 打印杨辉三角与逐行处理
3.4.2 电路布线与两点间的最短路径（*）
3.3 栈的应用
3.3.1 数制转换（*）
3.3.2 括号匹配
若用字符串描述的表达式为“(a+(b-c)*d)+e/f”， 设置一个栈S用于判断括号是否配对。然后从左向右 扫描表达式中的每一个字符
· 当遇到左括号“(”，进栈，扫描下一字符
· 当遇到右括号“)”，判断栈是否空？
· 若栈空，则“)”多于“(”，报错
· 若栈不空，则退栈顶的“(”，扫描下一字符
· 当遇到的不是括号，扫描下一字符
· 若表达式扫描完，栈不空，则“(”多于“)”，报错
3.3.3 表达式的计算与优先级处理
各个运算操作符的优先级
1. 应用后缀表达 式计算表达式的值
1）概述
从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果
在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现
2）过程
· 顺序扫描表达式的每一项， 根据它的类型做如下相应操作
· 若该项是操作数，则将其压栈
· 若该项是操作符<op>，则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果重新压栈
· 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果
3）举例
子主题
2. 中缀表达式转 换为后缀表达式
1）过程
操作符栈初始化，将结束符 ‘#’ 进栈。然后读入中缀表达式字符流的首字符ch
重复执行以下步骤，直到ch = ‘#’， 同时栈顶的操作符也是‘#’，停止循环
· 若ch是操作数，直接输出，读入下一个字符ch
· 若ch是操作符，判断ch的优先级icp 和位于栈顶的操作符op的优先级isp
· 若 icp (ch) > isp (op)，令ch进栈，读入下一个字符ch。 （看后面是否有更高的）
· 若 icp (ch) < isp (op)，退栈并输出。 （执行先前保存在栈内的优先级高的操作符）
· 若 icp (ch) == isp (op)，退栈但不输出。 若退出的是“(”号读入下一个字符ch。（销括号）
算法结束, 输出序列即为所需的后缀表达式
2）举例
3. 应用中缀表达 式计算表达式的值
1）概述
使用两个栈，操作符栈OPTR (operator)，操作数栈OPND(operand)
为了实现这种计算，仍需要考虑各操作符的优先级，参看前面给出的优先级表
2）过程
建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个“#”
扫描中缀表达式，取一字符送入ch
当ch != ‘#’ 或OPTR栈的栈顶 != ‘#’ 时, 执行以下工作, 否则结束算法
若ch是操作数，进OPND栈，从 中缀表达式取下一字符送入ch
若ch是操作符，比较icp(ch)的 优先级和isp(OPTR)的优先级
若icp(ch) > isp(OPTR)，则ch进OPTR栈，从中缀表达式取下一字符送入ch
若icp(ch) < isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出θ, 形成运算指令 (a1)θ(a2)，结果进OPND栈
若icp(ch) == isp(OPTR) 且ch == ')'，则从OPTR栈退出'('，对消括号，然后从中缀表达式取下一字符送入ch
3）举例
子主题
3.3.4 栈与递归的实现
1. 递归的定义
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程
2. 常用递归的三种情况
· 定义是递归的
阶乘函数n！
· 数据结构是递归的
单链表结构
· 问题的解法是递归的
汉诺塔问题
第4章 字符串
4.1 字符串的概念
4.1.1 字符串的基本概念
1. 字符串
n (>=0) 个字符的有限序列
2. 子串
任意个连续字符组成的子序列
3. 主串
包含子串的串
空串是任意串的子串，任意串是其自身的子串
4.1.2 字符串的初始化和赋值（*）
4.1.3 C语言中有关字符串的库函数
int strcpy(char* s1, char*s2) // 将s2复制到s1中
int strncpy(char*s1, char*s2, int n) // 将s2前n个字符复制到s1中
int strcat(char*s1, char*s2) // 将s2连接到s1后面
int strncat(char*s1, char*s2, int n) // 将s2前n个字符连接到s1后面
char* strchr(char* s1, char ch) // 在s1中搜寻ch并返回指向ch的指针，若失败则返回NULL
int strcspn(char* s1, char ch) // 在s1中搜寻ch并返回其第一次出现的位置（0开始计数），若失败则返回字符串长度
char* strrchr(char* s1, char ch) // 在s1中搜寻ch并返回其最后一次出现地址的指针，若失败则返回NULL
char* strpbrk(char* s1, char*s2) // 在s1和s2中搜寻首次共同出现的字符，返回在s1中的地址。找不到则返回NULL
char* strstr(char* s1, char*s2) // 在s1中寻找与s2匹配的子串，返回子串第一个字符在s1中的地址。若失败则返回NULL
int strlen(const char* s1) // 计算s1的长度
int strcmp(char* s1, char*s2) // 比较s1和s2的大小，返回值<0,=0,>0;对应s1<s2,s1=s2,s1>s2
4.1.4 字符串的自定义操作(*)
4.2 字符串的实现
4.2.1 定长顺序储存表示
· 即顺序串，使用静态分配的字符数组存储字符串中的字符序列。
· 字符数组的长度预先用 maxSize 指定，一旦空间存满不能扩充
结构定义
字符串的定长储存 #define maxSize 256 //顺序串的预设长度 Typedef struct { //顺序串的定义 char ch[maxSize+1]; //存储数组 int n; //串中实际字符个数 } SeqString;
4.2.2 堆分配储存表示
即堆式串。字符数组的存储空间是动态分配的。串的最大空间数 maxSize 和串中实际字符个数 n 保存在串的定义中
结构定义
堆分配字符串的结构定义 #define defaultSize 256; typedef struct { char *ch; //串的存储数组 int maxSize; //串数组的最大长度 int n; //串的当前长度 } HString;
4.2.3 块链储存表示
使用单链表作为字符串的存储表示，此即字符串的链接存储表示
链表的每个结点可以存储 1 个字符，称其“块的大小”为 1; 也可以存储 n 个字符，称其“块的大小”为 n
储存密度
存储密度越高，存储利用率越高
结点大小为 4 时，存储利用率高，但操作复杂，需要析出单个字符； 结点大小为 1 时，存储利用率低，但操作简单，可直接存取字符
结构定义
块链存储表示的结构定义 #define blockSize 1 //由使用者定义的结点大小 typedef struct block { //链表结点的结构定义 char ch[blockSize]; struct block *link; } Chunk; typedef struct { //链表的结构定义 Chunk *first, *last;//链表的头指针和尾指针 int n; //串的当前长度 } LinkString;
4.3 字符串的模式匹配
4.3.1 BF模式匹配算法
1. 过程
· 初始时让目标T的第 0 位与模式P的第 0 位对齐
· 顺序比对目标T与 模式P中的对应字符
· 若P与T比对发现对应位不匹配，则本趟失配。将P右移一位与T对齐，进行下一趟比对
· 若P与T对应位都相等，则匹配成功，返回T当前比较指针停留位置减去P的长度，即目标T中匹配成功的位置，算法结束
· 若P与T比对过程中，T后面所剩字符个数少于P的长度，则模式匹配失败
2. 示例
4.3.2 无回溯的KMP模式匹配算法
1. 算法的时间代价
· 若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m = n
· 若每趟第 m 个不匹配，总比较次数最坏亦达到 n
2. 示例
3. k的确定方法
· 对于不同的 j（P 中的失配位置），k 的取值不同，它仅依赖于模式 P 本身前 j 个字符的构成，与目标无关
· 可以用一个 next [ ] 失配函数来确定：当模式 P 中第 j 个字符与目标 T 中相应字符失配时，模式 P 中应当由哪个字符（设为第k+1个）与目标中刚失配的字符重新继续进行比较
· 设模式 P = p0p1...pm-2pm-1，next[]失配函数定义为：
4. next()失配处理
· 若 j > 0，那么在下一趟比较时模式P的起始比较位置是 pnext(j)，目标 T 的检测指针不回溯，仍指向上一趟失配的字符
· 若 j = 0，则目标T检测指针进一，模式P检测指针回到p0，进行下一趟匹配比较
5. 失配函数的计算
设模式P=p0 p1 p2…pm-1由m个字符组成，而next失配函数为next=n0 n1 n2…nm-1，表示了模式的字符分布特征
Next 失配函数从0, 1, 2, …, m-1逐项递推计算: · 当 j = 0时，n0 = -1。设 j > 0 时 nj-1 = k: · 当 k = -1或 j > 0且 pj-1 = pk，则 nj = k+1。 · 当 pj-1 != pk 且 k != -1，令 k = nk，并让③循环直到条件不满足。 · 当 pj-1 != pk 且 k = -1，则 nj = 0。
4.3.3 BM模式匹配算法(*)
第5章 多维数组和广义表
5.1 数组
5.1.1 一维数组
1. 定义
储存于一个连续储存空间中的相同数据类型的数据元素的集合
2. 特性
· 既是储存结构，又是逻辑结构
· 一维数组的数组元素为不可再分割的单元素时，是线性结构； 但它的数组元素是数组时，是多维数组，是非线性结构
· 一维数组是直接存取结构，数组的操作只有按下标“读/写“
· 数组可以看做<下标，值的集合>
5.1.2 多维数组
1. 定义
多维数组属于数组套数组，可以看做是一维数组的推广
2. 特点
· 每一个数据元素可以有多个直接前驱和多个直接后继
3. 动态二维数组
结构定义
动态二维数组的定义和输入 int **A; int m = 10, n = 6, i, j; *A = (int **) malloc (m * sizeof (int *)); for ( i = 0; i < m; i++ ) A[i] = (int *) malloc (n * (int)); for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ ) scanf (“%d”, &A[i][j] );
回收
for ( i = 0; i < m; i++) free (A[i]); free (A);
4. 连续存放
· 行优先存放
Loc (a[i][j]) = a+(i*m+j )*l 其中，m 是每行元素个数，即列数。
· 列优先存放
Loc(a[i][j]) = a+(j*n+i)*l 其中，n 是每列元素个数，即行数。
5.2 特殊矩阵
5.2.1 对称矩阵的压缩储存
1. 图示
2. 下三角矩阵
· i>=j
a[i][j]在数组B中的存放位置为: 1 + 2 +...+ i + j = (i + 1)* i / 2 + j
· i < j
A[i][j]在矩阵的上三角部分, 在数组B中没有存放，可以找它的对称元素: A[j][i] = j *( j +1 ) / 2 + i
3. 上三角矩阵
· i<=j
A[i][j]在数组B中的存放位置为: n + (n-1) + (n-2) +...+ (n-i+1) + j-i = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j
· i > j
子主题
A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此找它的对称元素: A[j][i] = (2*n-j-1) * j / 2 + i
5.2.2 三对角矩阵的压缩储存
1. 图示
2. 说明
· 三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素
· 将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]
· 在三条对角线上的元素aij 满足: 0<=i<=n-1, i-1<=j<=i+1
`A[i][j] 在B中位置为 k = 2*i + j
5.2.3 w对角矩阵的压缩储存
1. 图示
2. 说明
· 如果把它的w条对角线元素按行优先方式存放到一个一维数组B中，为找到元素ai,j 在B中位置，一种简化处理是先把w条对角线上的元素压缩在一个n×w的二维数组A'中，让a'0,0存放在B0，就可以简单地找到ai,j的存储位置了
· 对于一个w = 5的w对角矩阵，对应的A'矩阵如下图所示。从ai,j到a't,s的映射关系为： t = i, s = j-i+(w-1)/2
· 矩阵元素 a't,s 在B中对应的存放位置k为t*w+s,可得w对角矩阵元素ai,j在数组B中位置为： k = i*w+j-i+(w-1)/2
5.3 稀疏矩阵
5.3.1 稀疏矩阵的概念
设矩阵A中有s个非零元素。令e = s/(m*n)，称e为矩阵的稀疏因子
5.3.2 稀疏矩阵的顺序存储表示
1. 示例
2. 结构定义
稀疏矩阵的定义 # define maxTerms 30 //三元组表默认大小 typedef int DataType; //矩阵元素数据类型 typedef struct { //三元组定义 int row, col; //非零元素行号/列号 DataType value; //非零元素的值 } Triple; typedef struct { //稀疏矩阵结构定义 int Rows, Cols, Terms; //矩阵行、列、非零元素 Triple elem[maxTerms]; //三元组表 } SparseMatrix;
3. 带行指针数组的二元组表
5.3.3 稀疏矩阵的链接存储表示
1. 三元组表的双重缺陷
· 不能直接访问矩阵元素
· 插入或删除时可能发生大量元素移动
2. 链接存储表示
（1）头结点
· head = true是头结点的标识
· 第i行与第i列共用一个头结点，用next链接。 链表中按行列号顺序链接各行列的头结点
· right指向该行链表首元结点的指针
· down指向该列链表首元结点的指针
· 对链表扫描从头结点开始，最后以NULL结束
（2）元素结点
· head = false是稀疏矩阵元素结点的标识
· row和col是非零元素的行／列号，value是该非零元素的值
· right是在行链表中指向该行下一个非零元素结点的指针
· down是在列链表中指向该列下一个非零元素结点的指针
· 每一元素结点同时处于某行某列链表中
3. 图示
4. 转置
5. 算法思想
· 设矩阵列数为Cols，对矩阵三元组表扫描Cols次。第k次检测列号为k的项
· 第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，连同该元素的值，顺次存于转置矩阵三元组表
· 若设矩阵非零元素有Terms个，则上述二重循环执行的时间复杂性为O(Cols×Terms)
· 若矩阵有200行，200列，10,000个非零元素,总共有2,000,000次处理
6. 快速转置
· 对原矩阵a扫描一遍，按a中每一元素的列号，立即确定在转置矩阵b三元组表中的位置，并装入它
· 为加速转置速度，建立两个辅助数组rowSize和rowStart
· rowSize 记录矩阵转置前各列非零元素个数，转置后就是各行非零元素个数；
· rowStart 记录转置后各行非零元素在转置三元组表中开始存放位置，存放后其位置向后移一位，即+1。
5.4 广义表
5.4.1 广义表的概念
1. 概念
广义表是n(>=0)个表元素组成的有限序列，记作： LS (a1, a2, a3, …, an)
2. 说明
LS是表名，ai是表元素，可以是表（称为子表），可以是单元素（称为原子，不可再分）
n为表的长度。n = 0的广义表为空表
n > 0时，表的第一个表元素称为广义表的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail）
5.4.2 广义表的性质
1. 有次序性
2. 有长度
3. 有深度
4. 可递归
5. 可共享
5.4.3 广义表的头尾表示法
1. 结构图示
2. 说明
· 除空表外，广义表可以分为表头、表尾两部分。表头可以是单元素，也可以是子表，但表尾一定是子表
· 表结点
包括指向表头结点的指针hlink和指向表尾结点的指针tlink
· 元素结点
保存单元素数据值的data域
· 每个结点有一个标志域tag
tag = 0，表示该结点是单元素结点
tag = 1，表示该结点是表结点
· 空表没有结点，指向空表的头指针为空
· 非空表的头指针指向一个表结点。该结点的hlink指针指向表头元素结点，tlink指向表尾（该表尾肯定还是表）
· 如果有多个指针指向一个表结点，则出现共享情况；如果表中某元素是子表，其 hlink 又指向该表，则出现递归情况
3. 示例
5.4.4 广义表的扩展线性链表表示
1. 结构图示
2. 说明
tag = 0：单元素结点
value 存放元素的值，tlink 存放指向同一层下一表元素结点的指针
tag = 1：表结点
hlink 存放指向子表的指针hlink，tlink 与单元素结点tlink的含义相同
如果某表头元素为多个表结点共享，删除它后如何找到所有共享它的结点，以修改指向这个结点的所有指针，这种表示显然无法胜任
3. 优点
每个广义表都有一个起到“头结点”作用的表结点，即使空表，也有一个表结点
4. 缺点
每个对子表引用的指针没有指向子表的“头结点”，而是直接指向了广义表的表头元素结点（是第一个表元素结点），这样，造成对表头元素结点插入或删除时的困难
5. 示例
5.4.5 广义表的层次表示法
1. 结构图示
2. 说明
tag = 0：表头结点
info存放引用计数（ref），tlink指向该表第一个结点
tag = 1：原子结点
info存放数据值（value），tlink指向同一层下一个结点
tag = 2：子表结点
info存放指向子表头结点的指针（hlink），tlink指向同一层下一个结点
3. 示例
5.4.6 广义表的应用举例：三元多项式的表示（*）
第6章 树与二叉树
6.1 树的基本概念
6.1.1 树的定义和术语
1. 分类
（1）自由树
一棵自由树Tf可定义为一个二元组 Tf = (V, E) 其中V = {v1, ..., vn}是由n(n＞0)个元素组成的有限非空集合，称为顶点集合
E = {(vi, vj) | vi, vj ∈ V, 1<=i, j<=n}是n-1个序对的集合，称为边集合，E中的元素(vi, vj)称为边或分支
（2）有根树
一棵有根树 T，简称为树，它是n (n≥0) 个结点的有限集 合。当n = 0时，T 称为空树；否则，T 是非空树，记作:
r 是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱
根以外的其他结点划分为 m (m>=0) 个互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树
2. 特点
· 既是分层结构又是递归结构
· 每棵根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
3. 术语
· 结点（node）
包含数据元素的值及相关指针的存储单位
· 结点的度（degree）
结点所拥有的子树棵数
· 叶结点（leaf）
度为0的结点，又称终端结点
· 分支结点（branch）
除叶结点外的其他结点，又称为非终端结点或非叶结点
· 子女（child）
若结点x有子树，则子树的根结点即为结点x的子女
· 双亲（parent）
又称为父结点。若结点x有子女，它即为子女的双亲
· 兄弟（sibling）
同一双亲的子女互称为兄弟
· 祖先（ancestor）
从根结点到该结点所经分支上的所有结点
· 子孙（descendant）
某一结点的子女，以及这些子女的子女都是该结点的子孙
· 结点间的路径（path）
树中任一结点vi经过一系列结点v1, v2, ..., vk到vj，其中(vi, v1), (v1, v2), ..., (vk, vj)是树中的分支，则称vi, v1, v2, ..., vk, vj是vi与vj间的路径
· 结点的深度（depth）
结点所处层次，即从根到该结点的路径上的分支数加一。根结点在第1层
· 树的度（degree）
树中结点的度的最大值
· 有序树（ordered tree）
树中根结点的各棵子树T1, T2, …是有次序的，即为有序树。其中，T1叫做根的第1棵子树，T2叫做根的第2棵子树，…
· 无序树（unordered tree）
树中结点的各棵子树之间的次序是不重要的，可以互相交换位置
· 森林（forest）
m（m>=0）棵树的集合。在数据结构中，删去一棵非空树的根结点，树就变成森林（不排除空的森林）；反之，若增加一个根结点，让森林中每一棵树的根结点都变成它的子女，森林就成为一棵树
4. 说明
· 结点的深度和结点的高度是不同的。 · 结点的深度即结点所处层次，是从根向下逐层计算的； · 结点的高度是从下向上逐层计算的：叶结点的高度为1, 其他结点的高度是取它的所有子女结点最大高度加一
· 树的深度与高度相等。树的深度按离根最远的叶结点算，树的高度按根结点算，都是6
· 非叶结点包括根结点
6.1.2 树的基本操作（*）
6.2 二叉树及其储存表示
6.2.1 二叉树的概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。这个定义是递归的
· 满二叉树 (Full Binary Tree)
每一层结点都达到了最大个数。除最底层的结点度为0外，其他结点的度均为2
· 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树
6.2.2 二叉树的性质
1. 性质
性质1
若二叉树的层次从1开始, 则在二叉树的第i层最多有2i-1个结点。(i>=1)
性质2
高度为h的二叉树最多有2h-1个结点。(h>=1)
性质3
对任何一棵二叉树，如果其叶结点有n0个，度为2的非叶结点有n2个，则n0＝n2＋1
性质4
具有n(n>=0)个结点的完全二叉树的高度为
性质5
如将一棵有n个结点的完全二叉树自顶 向下，同一层自左向右连续给结点编号 : 0, 1, 2, …, n-1，则有以下关系
· i = 0
则 i 无双亲
· i > 0
则 i 的双亲为
· 2*i+1 < n
则 i 的左子女为 2*i+1
· 2*i+2 < n
则 i 的右子女为 2*i+2
· i为偶数, 且i != 0,
则其左兄弟为 i-1
· i为奇数, 且i != n-1
则其右兄弟为 i+1
2. 注意
如果完全二叉树各层次结 点从1开始编号：1, 2, 3, …, n，则有以下关系
· i = 1
则 i 无双亲
· i > 1
则 i 的双亲为
· 2*i <= n
则 i 的左子女为 2*i
· 2*i+1 <= n
则 i 的右子女为 2*i+1
· i为奇数, 且i != 1,
则其左兄弟为 i-1
· i为偶数, 且i != n
则其右兄弟为 i+1
3. 其他几种典型的二叉树
6.2.3 二叉树的主要操作（*）
6.2.4 二叉树的顺序存储表示
1. 完全二叉树
对于一棵完全二叉树，可将所有结点按其编号， 顺序存储到一维存储数组的对应位置
2. 一般二叉树
对于一般二叉树，必须仿照完全二叉树对结点编号， 即使有缺失也要编号，再按完全二叉树存储
6.2.5 二叉树的链接存储表示
1. 二叉链表表示
使用二叉链表，找子女的时间复杂度为O(1)，找双亲的时间复杂度为O(log2i)～O(i)，其中，i 是该结点编号
2. 三叉链表表示
使用三叉链表，找子女、双亲的时间都是O(1)。
3. 示例
6.3 二叉树的遍历
6.3.1 二叉树遍历的递归算法
1. 中序遍历
（1）算法框架
· 二叉树为空
空操作
· 否则
· 中序遍历左子树 (L)； · 访问根结点 (V)； · 中序遍历右子树 (R)
（2）图示
遍历结果： a + b * c - d - e / f
2. 先序遍历
（1）算法框架
· 二叉树为空
空操作
· 否则
· 访问根结点 (V)； · 中序遍历左子树 (L)； · 中序遍历右子树 (R)
（2）图示
遍历结果： - + a * b - c d / e f
3. 后序遍历
（1）算法框架
· 二叉树为空
空操作
· 否则
· 中序遍历左子树 (L)； · 中序遍历右子树 (R)； · 访问根结点 (V)
（2）图示
遍历结果： a b c d - * + e f / -
6.3.2 递归遍历算法的应用举例
从a+b*(c-d)-e/f 生成表达式树
(1) 先根据运算符的优先级对表达式加括号： ((a+(b*(c-d)))-(e/f))
(2) 脱一层括号， (a+(b*(c-d))) - (e/f)，取两个括号中间的“-”为根，将表达式分为两部分，左子树是(a+(b*(c-d))) ，右子树为(e/f)
(3) 对左子树递归执行步骤(2)；//若树空则不再递归
(4) 对右子树递归执行步骤(2)；//若树空则不再递归
6.3.3 二叉树遍历的非递归算法（*）
6.3.4 利用队列实现二叉树的层次序遍历（*）
6.3.5 二叉树的计数
1. 先序、中序序列确定二叉树
先序序列为ABHFDECKG，中序序列为HBDFAEKCG
先序序列第一个‘A’一定是根，它把中序序列一分为二： “HBDF”和“EKCG”，这就得到二叉树的左子树和右子树的中序序列，再看先序序列‘BHFD’…
2. 二叉树的计数
6.4 线索二叉树
6.4.1 线索二叉树的概念
1. 概念
希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前趋、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前趋、后继。为此，在二叉树存储结点中增加线索信息
2. 图示
3. 说明
改造树结点，将pred指针和succ指针压缩到lchild和rchild的空闲指针中，并增设两个标志ltag和rtag，指明指针是指示子女还是前趋/后继。后者称为线索
· ltag (或rtag) = 0
表示相应指针指示左子女（或右子女结点）
· ltag (或rtag) = 1
表示相应指针为前趋（或后继）线索
6.4.2 线索二叉树的种类
1. 先序线索树
2. 中序线索树
3. 后序线索树
4. 层次线索树
6.4.3 中序线索二叉树的建立和遍历
6.4.4 先序和后序线索二叉树
6.5 树与森林
6.5.1 树的存储表示
1. 双亲表示法
（1）图示
（2）说明
为了操作实现的方便，有时会规定结点的存放顺序。 例如，可以按树的先序次序存放树中的各个结点，或按树的层次次序安排所有结点
2. 子女链表表示法
（1）图示
（2）说明
· 无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点
· 一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理
· 为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）
· 这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费
3. 广义表表示法
（1）图示
（2）说明
· 广义表描述 A(B(E, F), C, D(G))
· 子表的头结点是子树的根，其后链接它的所有子女。
· 如果子女是叶结点（单元素或原子），结点中直接赋值，否则结点中是子表的头指针
4. 子女-兄弟链表表示法
（1）结点构造
（2）图示
（3）说明
· lchild 指向该结点的第一个子女结点。无序树的情形，可任意指定一个结点为第一个子女
· rsibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的
· 若想找某结点的所有子女，可先找lchild，再反复用rsibling 沿链扫描
· 树的子女-兄弟链表表示是双链表结构，与二叉树结点的定义类似，但语义是不同的。操作的含义自然也不同
6.5.2 森林与二叉树的转换
1. 森林->二叉树
2. 二叉树->森林
子主题
6.5.3 树与森林的深度优先遍历
1. 树
（1）先根次序遍历
非空
· 访问根结点 · 依次先根遍历根的各棵子树
空
· 返回
（2）后根次序遍历
非空
· 依次先根遍历根的各棵子树 · 访问根结点
空
· 返回
（3）举例
先根遍历：ABEFCDG
后根遍历：EFBCGDA
2. 森林
（1）先根次序遍历
非空
· 访问森林的根（也是第一棵树的根）r1； · 先根遍历森林第一棵树的根的子树森林{T11, …, T1k}； · 先根遍历森林中除第一棵树外其他树组成的森林{T2, ...,Tm}
空
返回
（2）中根次序遍历
非空
· 中根遍历森林F第一棵树的根结点的子树森林{T11, …, T1k}； · 访问森林的根结点r1； · 中根遍历森林中除第一棵树外其他树组成的森林{T2, ..., Tm}
空
返回
（3）举例
先根次序遍历的结果序列： ABCDE FG HIKJ
中根次序遍历的结果序列： BCEDA GF KIJH
6.5.4 树与森林的广度优先遍历
1. 树
广度优先次序遍历：ABCDEFG
2. 森林
广度优先次序遍历：AFH BCDGIJ EK
6.5.5 树遍历算法的应用举例（*）
第7章 树与二叉树的应用
7.1 Huffman树
7.1.1 带权路径长度的概念
（1）路径长度
结点的路径长度
两个结点之间的路径长度PL是连接两结点的路径上的分支数
树的路径长度
树的路径长度是各结点到根结点的路径长度之和PL
举例
左图中，结点4与结点6间的路径长度为3
PL=0+1+1+2+2+3+3+4=16
（2）带权路径长度（WPL）
7.1.2 Huffman树的概念
Huffman树又称最优二叉树或哈夫曼树，是一类加权路径长度最短的二叉树，在编码设计、决策、算法设计等领域有广泛应用
由给定n个权值 {w0, w1, w2, …, wn-1}，构造 具有 n 棵二叉树的森林 F = { T0, T1, T2, …, Tn-1 }，其中每棵二叉树 Ti 只有一个带权值 wi 的根结点, 其左、右子树均为空。 重复以下步骤, 直到 F 中仅剩一棵树为止： （1）在F中选取两棵根结点权值最小的二叉树，作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 （2）在F中删去这两棵二叉树。 （3）把新的二叉树加入F。
采用静态链表的Huffman树
建立Huffman树的算法 #define leafNumber 20 //默认权重集合大小 #define totalNumber 39 //树结点最大个数 typedef struct { char data; //结点的值 int weight; //结点的权 int parent, lchild, rchild; //双亲、左、右子女 } HTNode; typedef struct { HTNode elem[totalNumber]; //树存储数组 int num, root; //外结点数与根 } HFTree;
有关Huffman树的几个要点
· Huffman树的叶结点又称为外结点，分支结点又称为内结点。外结点是结果，内结点是过程。
· Huffman树是严格二叉树。有 n 个外结点，就有 n-1 个内结点，表示需要构造 n-1 次二叉树。树中总结点数为2n-1。
· Huffman算法每次选根结点权值最小的子树来构造新二叉树时，未明确规定谁做左子树，谁做右子树，所以构造出来的Huffman树可能不惟一。
· Huffman树的最小带权路径长度是惟一的。
7.1.3 最优判定树
· 利用Huffman树，可以在构造判定树（决策树）时让平均判定（比较）次数达到最小。 · 判定树是一棵扩展二叉树，外结点是比较结果，内结点是比较过程，外结点所带权值是概率
7.1.4 Huffman编码
主要用途
实现数据压缩
设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T } 各个字符出现的频度(次数)是W＝{ 2, 7, 4, 5 }。
· 等长编码
A: 00 T: 10 C: 01 S: 11 则总编码长度为(2+7+4+5)*2=36.
· 变长编码
各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 }，化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值，建立Huffman树。左分支赋0，右分支赋1，可得Huffman编码 (变长编码)。
A: 0 T: 10 C: 110 S: 111 它的总编码长度：7*1+5*2+(2+4)*3=35。 比等长编码的情形要短。
· 用Huffman编码得到的报文总编码长度正好等于Huffman树的带权路径长度WPL · Huffman编码是一种前缀编码，任何一个字符的编码不是其他字符编码的前缀，因此在解码时不会混淆
应用
7.2 堆
7.2.1 小根堆和大根堆
设有一个关键码集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从0开始连续编号。
小根堆：Ki<=K2i+1 && Ki<=K2i+2
大根堆：Ki>=K2i+1 && Ki>=K2i+2
小根堆的定义 #define heapSize 40 //堆的最大元素个数 typedef int HElemType; //堆中元素的数据类型 typedef struct { //堆结构的定义 HElemType elem[heapSize]; //小根堆存储数组 int curSize; //当前元素个数 } minHeap;
7.2.2 堆的建立
7.2.3 堆的插入
7.2.4 堆的删除
7.3 二叉查找树
7.3.1 二叉查找树的概念
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：
· 每个结点都有一个作为查找依据的关键码(key)，所有结点的关键码互不相同。
· 左子树（如果非空）上所有结点的关键码都小于根结点的关键码。
· 右子树（如果非空）上所有结点的关键码都大于根结点的关键码。
· 左子树和右子树也是二叉查找树。
二叉查找树的结构定义 typedef int TElemType; //结点关键码数据类型 typedef struct tnode { TElemType data; //结点值 struct tnode *lchild, *rchild; //左、右子女指针 } BSTNode, *BSTree;
7.3.2 二叉查找树的查找
从根结点开始，沿某一个分支逐层向下进行比较判等。它可以是一个递归的过程。
· 假设想要在二叉查找树中查找关键码为x的元素，查找过程从根结点开始。 · 如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较： · 如果给定值等于根结点的关键码值，则查找成功。 · 如果给定值小于根结点的关键码值，则继续递归查找根结点的左子树； · 否则。递归查找根结点的右子树。 · 查找成功时检测指针停留在树中某个结点。 · 可用判定树描述查找过程。内结点是树中原有结点，外结点是失败结点，代表树中没有的数据。 · 查找不成功时检测指针停留在某个失败结点。
7.3.3 二叉查找树的插入
· 每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。 · 为了向二叉查找树中插入一个新元素，必须先检查这个元素是否在树中已经存在。 · 为此，在插入之前先使用查找算法在树中检查要插入元素有还是没有。 · 查找成功：树中已有这个元素,不再插入。 · 查找不成功：树中原来没有关键码等于给定值的结点，把新元素加到查找操作停止的地方。
同样3个数据{ 1, 2, 3 }，输入顺序不同，建立起来的二叉查找树的形态也不同。这直接影响到二叉查找树的查找性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉查找树的高度达到最大。
7.3.4 二叉查找树的删除
· 在二叉查找树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉查找树的性质不会失去。 · 为保证在删除后树的查找性能不至于降低，还需要防止重新链接后树的高度增加。 （1）被删结点的右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。 （2）被删结点的左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。 （3）被删结点的左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点（所有比被删关键码大的关键码中它的值最小），用它的值填补到被删结点中，再来处理这个结点的删除问题。当然，也可以到它的左子树中寻找中序下的最后一个结点。
7.3.5 二叉查找树的性能分析
· 对于有n个关键码的集合，其关键码有n!种不同排列，可构成不同二叉查找树有
· 用树的查找效率来评价这些二叉查找树。
· 用判定树来描述查找过程，在判定树中，○表示内结点，它包含关键码集合中的某一个关键码；□表示外结点，代表各关键码间隔中的不在关键码集合中的关键码。它们是查找失败时到达的结点，物理上实际不存在。
· 在每两个外部结点间必存在一个内部结点。
例，已知关键码集合 { a1, a2, a3 } = { do, if, to }，对应查找概率 p1, p2, p3, 在各查找不成功间隔内查找概率分别为 q0, q1, q2, q3。可能的判定树如右图所示。
· 一棵判定树的查找成功的平均查找长度ASLsucc定义为该树所有内结点上的权值 p[i]与查找该结点时所需的关键码比较次数c[i] (= l[i])乘积之和：
· 查找不成功的平均查找长度ASLunsucc为树中所有外结点上权值q[j]与到达该外结点所需关键码比较次数c'[j] (= l'[j]-1)乘积之和：
· 图(b)的情形所得的平均查找长度最小。一般把平均查找长度达到最小的判定树称作最优二叉查找树。
· 在相等查找概率的情形下，最优二叉查找树的上面 h-1（h是高度）层都是满的，只有第 h 层不满。如果结点集中在该层的左边，则它是完全二叉树；如果结点散落在该层各个地方，则有人称之为理想平衡树。
7.7 八皇后问题与树的剪枝
7.7.1 八皇后问题的提出（*）
7.7.2 八皇后问题的状态树（*）
7.7.3 八皇后问题的算法（*）
7.6 等价类与并查集
7.6.1 等价关系与等价类（*）
7.6.2 确定等价类的方法（*）
7.6.3 并查集的定义及其实现
1. 三种支持的操作
Union (S, Root1, Root2) //合并操作
Find (S, x) //查找操作
initUFSets (S) //初始化函数
2. 说明
· 对于并查集来说，每个集合用一棵树表示
· 为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n是最大元素个数
· 在双亲表示中，第i个数组元素代表集合元素i。初始时，根结点的双亲为-1，表示集合中的元素个数
· 在同一棵树上所有结点所代表的集合元素在同一个子集合中
3. 举例
设 S1= {0, 6, 7, 8}, S2= {1, 4, 9}, S3= {2, 3, 5}
1）用初始化函数 initUFSets(S) 构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合
2）用Find(S, i) 寻找集合元素i的根。
如果有两个集合元素 i 和 j , Find(S, i) == Find(S, j)：表明这两个元素在同一个集合中
如果两个集合元素 i 和 j 不在同一个集合中： 可用 Union() 将它们合并到一个集合中
7.6.4 并查集操作的分析和改进
1. 分析
执行一次合并操作Merge所需时间是O(1)，n-1次Merge操作所需时间是O(n)
若再执行Find(0)，Find(1)，...，Find(n-1)，若被搜索的元素为 i，完成 Find(i) 操作需要时间为O(i)，完成 n 次搜索需要的总时间将达到
2. 改进方法
· 按树的结点个数合并
合并操作Merge(UFSets& S, int R1, int R2) 要求把两个不相交集合R1与R2合并为一个集合
原则
把元素少的集合合并入元素多的集合
R1和R2是两个不相交集合的根
· 按树的高度合并
若把根结点parent域存放的值视为该树的高度， 并查集合并操作把高度高的作为合并后的根
· 压缩元素的路径长度
把从元素i到根的路径上的所有祖先 结点的双亲指针都改为指向根结点
结点内的数字是该结点的双亲指针
7.5 表达式树
7.5.1 从中缀表达式建立表达式树（*）
7.5.2 从后缀表达式建立表达式树（*）
7.5.3 利用表达式树求值（*）
7.4 AVL树
7.4.1 AVL树的概念
定义
一棵AVL树又称为高度平衡的二叉查找树
性质
· 它的左子树和右子树都是AVL树
· 左子树和右子树的高度之差的绝对值不超过1
平衡因子
· 每个结点附加一个数字，给出该结点左子树的高度减去右子树的高度所得的高度差，这个数字即为结点的平衡因子bf（balance factor）
· AVL树任一结点平衡因子只能取 -1, 0, 1
· 如果一个结点的平衡因子的绝对值大于1，则这棵二叉查找树就失去了平衡，不再是AVL树
· 如果一棵二叉查找树是高度平衡的, 且有n个结点，其高度可保持在O(log2n),平均查找长度也可保持在O(log2n)
7.4.2 平衡化旋转
· 如果在一棵AVL树中插入一个新结点，造成了不平衡。必须调整树的结构，使之平衡化
分类
单旋转 (LL旋转和RR旋转)
1. 左单旋转（RR单旋）
· 在结点A的右子女C的右子树E中插入新结点，该子树高度增1导致结点A的平衡因子变成-2，出现不平衡
· 为使树恢复平衡，从A沿插入路径连续取3个结点A、C和E，以结点C为旋转轴，让结点A反时针旋转
2. 右单旋转（LL单旋）
· 在结点A的左子女的左子树D上插入新结点使其高度增1导致结点A的平衡因子增到+2，造成不平衡
· 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，以结点B为旋转轴，将结点A顺时针旋转
双旋转 (LR旋转和RL旋转)
1. 先左后右双旋转（LR双旋）
· 在结点A的左子女的右子树中插入新结点，该子树的高度增1导致结点A的平衡因子变为2，发生了不平衡
· 从结点A起沿插入路径选取3个结点A、B和E，先以结点E为旋转轴，将结点B反时针旋转，E顶替原B的位置。再以结点E为旋转轴，将结点A顺时针旋转
2. 先右后左双旋转（RL双旋）
· 在根结点A的右子女的左子树中F或G上插入新结点，该子树高度增1。结点A的平衡因子变为-2，发生了不平衡
· 从结点A起沿插入路径选取3个结点A、C和D。首以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。再以D为旋转轴，将结点A反时针旋转，恢复树的平衡
说明
· 每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子
· 如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点
· 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为LL旋转和RR旋转，其中一个是另一 个的镜像，其方向与不平衡的形状相关
· 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为LR旋转和RL旋转两类。
7.4.3 AVL树的插入
设新结点p的平衡因子为0，其父结点为pr。 插入新结点后pr的平衡因子值有三种情况
1）结点pr的平衡因子为0
说明刚才是在 pr 的较矮的子树上插入了新结点，此时不需做平衡化处理，返回主程序。子树的高度不变
2）结点pr的平衡因子的绝对值 |bf| = 1
说明插入前pr的平衡因子是0，插入新结点后，以pr为根的子树不需平衡化旋转。但该子树高度增加，还需从结点pr向根方向回溯，继续考查结点pr双亲(pr = Parent(pr))的平衡状态
3）结点pr的平衡因子的绝对值|bf| = 2
1. 若结点pr的bf = -2
· 若q的bf与pr同符号(=-1)，执行RR单旋
· 若q的bf与pr异符号(=1)，执行RL双旋
2. 若结点pr的bf = 2
· 若q的bf与pr同符号(=1)，执行LL单旋
· 若q的bf与pr异符号(=-1)，执行LR双旋
举例，输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }
7.4.4 AVL树的删除
1）结点的删除
1. 被删结点x没有子女
· 将结点x从树中删去
· x双亲结点的相应指针置为NULL
· 将原来以结点x为根的子树的高度减1
2. 被删结点x有一个子女
· 将结点x从树中删去
· 把x的双亲结点中原来指向结点x的指针改指到这个子女结点
· 将原来以结点x为根的子树的高度减1
3. 如果被删结点x有两个子女
· 查找结点x在中序次序下的直接前驱结点y (同样可以找直接后继)
· 把结点y的内容传送给结点x，把结点y当作被删结点x
· 结点y最多有一个子女，用上面1.2.给出的方法进行删除
2）回溯跟踪影响
1. 当前结点p的bf为0
· 左子树高度降低，bf设置为-1
· 右子树高度降低，bf设置为1
2. 当前结点p的bf不为0
较高子树的高度被降低
· p的bf改为0
· 向上回溯，看其双亲是否失去平衡
较矮子树的高度又被降低
令p的较高的子树 的根为q(该子树高 度未被降低)
q的bf为0
· 执行一个单旋转来恢复结点p的平衡
q与p的bf符号相同
· 执行一个单旋转来恢复平衡
· 结点p和q的bf均改为0
· 向上判断双亲结点是否失去平衡
p与q的bf的符号相反
· 执行一个双旋转来恢复平衡（先p后q）
· 新根结点的bf置为0
· 向上判断双亲结点是否失去平衡
3）举例（删除结点P）
7.4.5 AVL树的性能分析
1）AVL树的高度
Nh是高度为h的AVL树的最小结点个数 · N0 = 0 (空树) · N1 = 1 (仅有根结点) · Nh = Nh-1 + Nh-2 +1 , h > 1
斐波那契数列为F，则Nh = Fh+2 – 1
2）高度与结点数的关系
高度h固定，最少结点数为Nh；最多结点数为2h – 1，即满二叉树情形
结点数n固定，最小高度 log2(n+1)。最大高度不超过1.44*log2(n+2)
第8章 图
8.1 图的基本概念
8.1.1 与图有关的若干概念
1. 定义
图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V，E ) 其中，V = { x | x ∈ 某个数据对象} 是顶点的有穷非空集合；E = {(x，y) | x，y ∈ V } 或 E = {<x，y> | x，y ∈ V && Path (x，y)} 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x，y)表示从 x 到 y 的一条单向通路，它是有方向的。
2. 相关术语
· 有向图与无向图
在有向图中，顶点对 <x，y> 是有序的。在无向图中，顶点对(x，y)是无序的
· 完全图
若有 n 个顶点的无向图有 n(n-1)/2 条边，则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边，则此图为完全有向图
· 邻接顶点
如果 (u，v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点
· 子图
设有两个图 G＝(V，E) 和 G‘＝(V’，E‘)。若 V’ Í V 且 E‘ Í E，则称图G’是图G的子图
· 权
某些图的边具有与它相关的数，称之为权。这种带权图叫做网络
· 顶点的度TD(v)
一个顶点 v 的度是与它相关联的边的条数。在有向图中，顶点的度等于该顶点的入度与出度之和
· 顶点v的入度ID(v)
以 v 为终点的有向边的条数
· 顶点v的出度OD(v)
以 v 为始点的有向边的条数
· 路径
在图 G＝(V，E) 中，若从顶点 vi 出发，沿一些边经过一些顶点 vp1，vp2，…，vpm，到达顶点vj。则称顶点序列 (vi vp1 vp2 ... vpm vj) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi，vp1)、(vp1，vp2)、...、(vpm，vj) 应是属于E的边
· 路径长度
非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和
· 简单路径
若路径上各顶点v1，v2，...，vm均不互相重复，则称这样的路径为简单路径
· 回路
若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环
· 连通图
如果图中任意一对顶点都是连通的，则称此图是连通图
· 连通分量
非连通图的极大连通子图叫做连通分量
· 强连通图
在有向图中，若对于每一对顶点vi和vj，都存在一条从vi到vj和从vj到vi的路径，则称此图是强连通图
· 强连通分量
非强连通图的极大强连通子图叫做强连通分量
· 生成树
一个连通图的生成树是其极小连通子图，在 n 个顶点的情形下，有n-1条边
8.1.2 图的基本操作（*）
8.2 图的储存结构
8.2.1 邻接矩阵表示
1. 邻接矩阵
设图 A = (V，E)是一个有 n 个顶点的图，图的邻接矩阵是一个二维数组 A.edge[n][n]，定义：
2. 举例
3. 网络的邻接矩阵
8.2.2 邻接表表示
1. 无向图
2. 有向图
3. 网络（带权图）
8.2.3 邻接矩阵与邻接表的比较（*）
8.2.4 无向图的邻接多重表表示
1. 边结点
mark：处理标记； vertex1和vertex2：该边两顶点位置。 Path1：指向下一条依附vertex1的边； path2：指向下一条依附vertex2 的边
对于带权图还需设置一个存放与该边相关的权值的域 cost
2. 顶点结点
data：存放与该顶点相关的信息； Firstout：指示第一条依附该顶点的边的指针
3. 图示
8.2.5 有向图的十字链表表示
1. 边结点
mark：处理标记； vertex1和vertex2：该边两顶点位置。 nextout：指向同一顶点发出的下一条边的边结点； nextin：指向进入同一顶点的下一条边的边结点
需要时还可有权值域 cost
2. 顶点结点
data：存放与该顶点相关的信息； Firstout：指示以该顶点为始顶点的出边表的第一条边； Firstin：指示以该顶点为终顶点的入边表的第一条边
3. 图示
8.3 图的遍历
8.3.1 深度优先搜索（DFS）
1. 示例
2. 算法思路
（1）深度优先搜索算法在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至所有的邻接顶点都被访问过的顶点 u 为止。 （2）接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。 （3）重复上述过程，直到连通图中所有顶点都被访问过为止。
8.3.2 广度优先搜索（BFS）
1. 示例
2. 算法思路
BFS在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未被访问过的邻接顶点 w1，w2，…，wt，然后再顺序访问 w1，w2，…，wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止
3. 说明
（1）深度优先搜索是一种回溯的算法，而广度优先搜索不是，它是一种分层的顺序搜索过程，每向前走一步可能访问一批顶点。因此，广度优先搜索不是一个递归的过程
（2）为了实现逐层访问，广度优先搜索算法使用了一个队列，以记忆正在访问的这一层和下一层的顶点，以便于向下一层访问
（3）为避免重复访问，需要一个辅助数组visited[]，给被访问过的顶点加标记
（4）为了实现和控制广度优先搜索算法的执行，在图的遍历的主程序 void Graph_Traverse (ALGraph& G) 中把调用DFS (G，i，visited ) 改为调用BFS (G，i，visited ) 即可
8.3.3 连通分量
1. 说明
· 当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图（连通分量）的所有顶点。
· 若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。
2. 算法介绍
（1）求连通分量的算法需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量
（2）对于非连通的无向图，遍历每一个连通分量，得到一棵生成树，所有连通分量的生成树组成了非连通图的生成森林
（3）算法中用一个循环，检查各顶点是否访问过。每当遇到一个 visited[i] = 0 的顶点 i，就从该顶点出发做深度优先遍历，此顶点即为生成树的根
（4）做一次遍历可遍访该顶点所在连通分量的所有顶点，然后继续扫描 visited 数组，若遇到 visited[i] = 0 的顶点，即可开始下一个连通分量的遍历
8.3.4 双连通图
1. 关节点
在无向连通图 G 中，当且仅当删去 G 中的顶点 v及所有依附于 v 的所有边后，可将图分割成两个或两个以上的连通分量，则称顶点 v 为关节点
2. 双连通图
没有关节点的连通图叫做双连通图（重连通图）
3. 举例
4. 判断步骤
（1）从图中某一顶点（如 D）出发，做 DFS 遍历
（2）在生成树的每一结点旁边按深度优先遍历的顺序注明深度优先树
（3）判断关节点
根结点：子女>=2，则为关节点
叶子结点：不是关节点
其他结点：若任意子孙都可以绕过该结点到达该结点的祖先，则该结点不是关节点
（4）消除关节点
在非双连通图上，找到其深度优先生成树中的叶结点（其度为 1），用最少的连线把叶结点与其祖先的某结点（兄弟不可）连接起来，就能消除非双连通图中的关节点，形成双连通图
8.3.5 有向图的强连通分量（Kosaraju算法）
1. 首先对图进行一次DFS，在回退时记忆对结点回溯的顺序：EDCFBAIJHG
2. 把图的所有的有向边逆转：
3. 再对得到的图沿回溯顺序 EDCFBAIJHG 从编号最高的 G 开始，再进行一次 DFS，所得到的深度优先森林（树）即为强连通分量的划分
8.4 最小生成树
8.4.1 最小生成树求解和贪心法
1. 介绍
连通图中的每一棵生成树，都是原图的一个无环连通子图。从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条边，都会形成一个回路
2. 构造最小生成树的原则
必须使用且仅使用该带权图中的n-1 条边来联结网络中的 n 个顶点
不能使用产生回路的边
要求各边上的权值的总和达到最小
3. 贪心法（逐步求解）
（1）介绍
当追求的目标是一个问题的最优解时，设法对整个问题的求解工作分为若干个步骤来完成。在其中的每一个阶段都选择从局部来看是最优的方案，以期望通过各阶段的局部最优来达到整体最优
（2）说明
· 本质上不是追求最优解，而是快速筛选得到符合的解
· 特征是局部最优®整体最优，但往往做不到
· 体现了分而治之的思想
8.4.2 Kruskal算法
1. 算法思路
（1）设有一个有n个顶点的连通带权图N = { V，E }，先构造一个只有n个顶点，没有边的非连通图 T = { V，∅ }， 图中每个顶点自成一个连通分量。
（2）当在 E 中选到一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。
（3）如此重复下去，直到所有顶点在同一个连通分量上为止
2. 示例
8.4.3 Prim算法
1. 算法思路
从连通带权图N = { V，E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边 ( u0，v )，将其顶点加入到生成树顶点集合U中
以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u，v)，把它的顶点加入到集合U 中。如此继续下去，直到带权图中的所有顶点都加入到生成树顶点集合 U中为止
2. 示例
8.4.4 Rosenstiehl和管梅谷算法（破圈法）
1. 算法思路
对一个有 n 个顶点的连通带权图，按其权值从大到小顺序逐个删除各边，直到剩下n-1 条边为止。删除的原则是：要确保删除该边后各个顶点之间还是连通的
2. 示例
8.4.5 迪杰斯特拉(Dijkstra)算法
1. 算法思路
· 最初将带权图中每个顶点视为一个独立的连通分量，然后逐个检查各条边： · 如果该边的两个端点在不同的连通分量上，直接把它加入生成树； · 如果该边的两个端点在同一个连通分量上，加入它后会形成一个环，把该环上权值最大的边删除。 · 重复以上操作，直到所有边都检查完为止
2. 示例
8.5 最短路径
8.5.1 非负权值的单源最短路径 — Dijkstra算法
首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 · 若从源点v0到顶点 vi 有边，则dist[i]为该边上的权值； · 若从源点v0到顶点 vi 无边，则dist[i]为¥
8.5.2 边上权值为任意值的单源最短路径问题 — Bellman和Ford算法
Bellman-Ford 方法构造一个最短路径长度数组序列 dist1[u]，dist2[u]，…，distn-1[u]。其中， · dist1[u]是从源点 v 到终点 u 的只经过一条边的最短路径的长度， dist1[u] = Edge[v][u] · dist2[u]是从源点 v 出发最多经过两条边到达终点 u 的最短路径长度； · dist3[u]是从源点 v 出发最多经过不构成带负长度边回路的三条边到达终点 u 的最短路径长度，…， · distn-1[u]是从源点 v 出发最多经过不构成带负长度边回路的 n-1 条边到达终点 u 的最短路径长度。 算法的最终目的是计算出 distn-1[u]。 可以用递推方式计算 distk[u]
8.5.3 所有顶点之间的最短路径 — Floyd算法
Floyd算法的基本思想： 定义一个n阶方阵序列：A(0)，A(1)，…，A(n).其中 A(0)[i][j] = G.Edge[i][j]； A(k)[i][j] = min { A(k-1)[i][j]，A(k-1)[i][k] + A(k-1)[k][j] }，k = 1，2，…，n A(1)[i][j]是从顶点 vi 到 vj，中间可能绕过顶点 v1 的最短路径长度； A(k)[i][j]是从顶点 vi 到 vj，中间可能绕过顶点 v1，v2，…，vk 的最短路径的长度； A(n)[i][j]是从顶点vi 到vj 的最短路径长度
8.5.4 无权有向图的最短路径
广度优先搜索算法（*）
8.5.5 无权有向图的传递闭包
Warshall算法（*）
8.6 活动网络
8.6.1 AOV网络和拓扑排序
1. 工程与活动
计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了
2. AOV（Activity On Vertices）网络
可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi，Vj>表示活动Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络。 · 在AOV网络中不能出现有向回路， 即有向环。对给定的AOV网络，必须先判断它是否存在有向环。
3. 拓扑排序
将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。
4. 拓扑排序的方法
· 输入AOV网络。令 n 为顶点个数
· 在AOV网络中选一个没有直接前驱的顶点，并输出之
· 从图中删去该顶点，同时删去所有它发出的有向边
· 重复以上 ②、③步，直到 · 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成； 或 · 图中还有未输出的顶点，但已跳出处理循环。说明图中还剩下一些顶点，它们都有直接前驱。这时网络中必存在有向环
8.6.2 AOE网络与关键路径
1. AOE（Activity On Edges）网络
如果在无有向环的带权有向图中，用有向边表示一个工程中的活动 (Activity)，用边上权值表示活动持续时间 (Duration)， 用顶点表示事件 (Event)， 则这样的有向图叫做用边表示活动的网络，简称 AOE ( Activity On Edges ) 网络
2. 关键路径
完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)
3. 关键活动
关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径
4. 相关量
事件vi的最早可能开始时间Ve(i)
从开始点V1到顶点vi的最长路径长度
事件vi的最迟允许开始时间Vl[i]
在保证结束点Vn在Ve[n]时刻完成的前提下，事件vi的允许的最迟开始时间
活动ak的最早可能开始时间e[k]
设活动ak在边<vi，vj>上，则e[k]是从开始点V1到顶点vi的最长路径长度。因此 e[k] = Ve[i]
活动ak的最迟允许开始时间l[k]
它是在不会引起时间延误的前提下，该活动允许的最迟开始时间。 l[k] = Vl[j] - dur(<i，j>)。 其中，dur(<i，j>)是完成ak所需的时间
时间余量l[k] - e[k]
表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。l[k] == e[k] 表示活动ak是没有时间余量的关键活动
5. 说明
· 仅计算Ve[i]和Vl[i]是不够的，还须计算e[k]和l[k]，才能判断哪些是关键活动
· 如果同时存在几条关键路径，那么，不是任一关键活动加速一定能使整个工程提前
· 想使整个工程提前，要考虑加速各关键路径上的关键活动
· 如果关键路径上的任一关键活动延迟，整个工程将延迟
第9章 查找
9.1 查找的基本概念
9.1.1 查找的概念
1. 查找
· 所谓查找，就是在数据集合中寻找满足某种条件的数据元素。 · 查找的结果通常有两种可能： · 查找成功，即找到满足条件的数据元素。这时，作为结果，可报告该元素在结构中的位置，还可给出该元素中的具体信息。 · 查找不成功，或查找失败。作为结果，应报告一些信息，如失败标志、位置等。 · 通常称用于查找的数据集合为查找结构，它是由同一数据类型的元素（或记录）组成
2. 关键码
· 在每个元素中有若干属性，其中有一个属性，其值可唯一地标识这个元素。称为关键码（key）。 · 使用基于关键码的查找，查找结果应是唯一的。但在应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一
9.1.2 查找算法的性能分析
平均比较次数ASL（平均查找长度）
9.2 顺序查找
9.2.1 普通顺序表的顺序查找
1. 普通查找
顺序查找，若指针指向了n，则返回-1
2. 设置“监视哨”
在数据表L.data[0]..L.data[n-1] 中顺序查找关键码值与给定值 x 相等的数据元素，L.data[n]作为控制搜索自动结束的“监视哨”使用
每次判断条件少了i < n，n很大时，明显缩短了时间
9.2.2 有序顺序表的顺序查找
在有序顺序表中做顺序查找时，若查找不成功，不必检测到表尾才停止，只要发现有比它的关键码值大的即可停止查找
9.3 折半查找
9.3.1 折半查找方法
· 折半查找只适用于有序顺序表。 · 做折半查找时，先求位于查找区间正中的元素的下标mid，用其关键码值与给定值x比较: · L.data[mid].key == x，查找成功； · L.data[mid].key > x，把查找区间缩小到表的前半部分，继续折半查找； · L.data[mid].key < x，把查找区间缩小到表的后半部分，继续折半查找。 · 如果查找区间已缩小到一个元素，仍未找到想要查找的元素，则查找失败
9.3.2 最优二叉查找树
即路径长度最小的Huffman树（*）
9.3.3 次优二叉查找树
使得ASLsucc达到最小的静态查找树为静态最优二叉排序树。然而，求最优查找树的算法效率较低，达O(n3)，可求次优查找树，由上而下构建，其时间代价减低为O(nlog2n)
9.3.4 斐波那契查找和插值查找（*）
9.3.5 跳表
· 在一个有序顺序表中进行折半查找、斐波那契查找和插值查找，时间效率很高。但是在有序链表中进行搜索，只能顺序搜索，需要执行O(n) 次关键码比较。 · 如果在链表中部结点中增加一个指针，则比较次数可以减少到 n/2+1。在查找时，首先用要查找元素与中间元素进行比较，如果要查找元素小于中间元素，则仅需查找链表的前半部分，否则只要在链表的后半部分进行比较即可
9.4 B树
9.4.1 索引顺序表与分块查找
1. 稠密索引
一个索引项对应数据表中一个元素。当元素在外存中按加入顺序存放而不是按关键码值有序存放时必须采用稠密索引，这时的索引结构叫做索引非顺序结构
2. 稀疏索引
当元素在外存中有序存放时，可以把所有 n 个元素分为 b 个子表存放，一个索引项对应数据表中一组元素（子表）。第 i个索引项是第 i 个子表的索引项，i = 0，1，…，n-1。这种索引结构叫做索引顺序结构
3. 举例
（1）分块查找
· 先在索引表 ID 中查找给定值 K，确定满足：ID[i-1].max_key < K <= ID[i].max_key 的i值，即待查元素可能在的子表的序号 · 再在第i个子表中按给定值查找要求的元素
（2） ASLIndexSeq = ASLIndex + ASLSubList 其中，ASLIndex是在索引表中查找子表位置的平均查找长度，ASLSubList是在子表内查找元素位置的查找成功的平均查找长度
9.4.2 多级索引结构与m叉查找树
当数据元素数目特别大，索引表本身很大，在内存中放不下，需要分批多次读取外存才能把索引表查找一遍。必要时，还可以有 4 级索引，5 级索引，…。这种多级索引结构形成一种 m 叉树。树中每一个分支结点表示一个索引块，每个索引项给出各子树结点的最大关键码和结点地址
9.4.3 B树的概念
一棵 m 阶 B 树是一棵平衡的 m 路查找树，它或者是空树，或者是满足下列性质的树： · 除失败结点外，所有结点最多有 m 棵子树; · 根结点至少有 2 个子女; · 除根结点和失败结点外，所有结点至少有 ém/2ù 个子女。 · 所有的失败结点都位于同一层，它们是虚结点，是当查找值 x 不在树中时才能到达的结点。指向这些结点的指针为空。
9.4.4 B树上的查找
· 每个结点中最多有m-1个关键码，在一棵高度为 h 的 m 路查找树中关键码的最大个数为 mh-1，最大结点数为(mh-1)/(m-1) ∴ h>=logm(N +1) · 若树中关键码有 N 个，则失败结点数为 N+1，N+1 = 失败结点数 = 位于第 h+1 层结点数>=2 ém / 2ù h-1 ∴ h-1<=logém / 2ù((N +1) / 2) · 最大比较次数：logém / 2ù((N +1) / 2) + 1
9.4.5 B树上的插入
除失败结点外，每个结点的关键码个数都在[ém/2 -1ù，m-1]之间。新关键码插入在某个叶结点。如果在关键码插入后结点中的关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入
9.4.6 B树上的删除
9.4.7 B+树
1. 与B树的不同点
· 所有关键码都存放在叶结点中，上层的非叶结点的关键码是其子树中最大关键码的复写
· 叶结点包含了全部关键码及指向相应数据记录存放地址的指针，且叶结点本身按关键码从小到大顺序链接
2. 定义
一棵 m 阶B+ 树的结构定义如下： · 每个结点最多有 m 棵子树； · 根结点最少有 1 棵子树，除根结点外，其他结点至少有 ém/2ù 棵子树； · 有 n 个子树的结点有 n 个关键码。 · 所有非叶结点可以看成是叶结点的索引，结点中关键码Ki与指向子树的指针Pi构成对子树(即下一层索引块)的索引项(Ki，Pi)，Ki是子树中最大的关键码。 · 所有叶结点在同一层，按从小到大的顺序存放全部关键码，各个叶结点顺序链接。 叶结点中存放的是对实际数据记录的索引，每个索引项(Ki，Pi)给出记录的存储地址。
3. 举例
例如，在一棵4阶B+树中，除根结点外，所有非叶结点中的子树棵数2<=n<=4，其所有的关键码都出现在叶结点中，且在叶结点中关键码有序地排列。上面各层结点中的关键码都是其子树上最大关键码的副本
4. B+树的插入
5. B+树的删除
9.6 散列法
9.6.1 散列的概念
1. 散列、散列函数
· 散列方法在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash( )，使每个关键码与结构中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) · 在查找时，先对表项的关键码进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键码相等，则查找成功。在存放表项时，依相同函数计算存储位置，并按此位置存放。这种方法就是散列方法。 · 在散列方法中使用的转换函数叫做散列函数。按此方法构造出来的表或结构就叫做散列表 · 使用散列方法进行查找不必进行多次关键码的比较，查找速度比较快，可以直接到达或逼近具有此关键码的表项的实际存放地址
2. 冲突（碰撞）与同义词
· 散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突（碰撞）。 · 对不同的关键码，通过散列函数的计算，得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为同义词
3. 讨论的问题
（1）对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突
（2）拟订解决冲突的方案
9.6.2 常见的散列函数
1. 散列函数的要求
· 散列函数应是简单的，能在较短的时间内计算出结果
· 散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间
· 散列函数计算出来的地址应能均匀分布在整个地址空间中
2. 方法举例
（1）直接定址法
此类函数取关键码的某个线性函数值作为散列地址： Hash(key)＝a * key + b { a，b为常数 }
特点
· 这类散列函数是一对一的映射，一般不会产生冲突。 · 它要求散列地址空间的大小与关键码集合的大小相同。 · 适合关键码分布基本连续的情况，否则空间浪费大
（2）数字分析法
设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现的频率不一定相同。根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。 用aik表示第 i 个符号在第 k 位上出现的次数，n/r 表示各种符号在 n 个数中均匀出现的期望值。则计算各位数字中符号分布均匀度lk的公式为：
举例：
特点
· 需事先知道关键码每一位数值的分布情况
· 完全依赖于关键码集合，换一个关键码，则选取位数可能发生变化
（3）除留余数法
设散列表中允许地址数为m，取一个不大于 m，但最接近于或等于 m 的质数 p 作为除数，用以下函数把关键码转换成散列地址： hash (key) = key % p p <= m 其中，“%”是整数除法取余的运算，要求这时的质数 p 不是接近 2 的幂
示例: 有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p = 23。散列函数 hash(key) = key % p。则散列地址为 hash(962148) = 962148 % 23 = 12。 可按计算出的地址存放记录。注意，使用散列函数计算出的地址范围是 0 到 22，而 23、24 这几个地址实际上不能用散列函数计算出来，只能在处理冲突时达到这些地址
（4）平方取中法
它首先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。 设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同
（5）折叠法
此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。 有两种叠加方法： · 移位法：把各部分最后一位对齐相加； · 分界法：各部分不折断，沿各部分的分界来回折叠，然后对齐相加
假设地址空间为HT[400]，利用以上函数计算，取其中3位，取值范围在0～999，可能超出地址空间范围，为此必须将0～999压缩到0～399。可将计算出的地址乘以一个压缩因子0.4，把计算出的地址压缩到允许范围
9.6.3 解决冲突的开地址法
若设散列表中的编址为0到m-1，当要加入一个表项R2时，用它的关键码 R2.key，通过散列函数hash(R2.key)的计算，得到它的存放地址号j。 但在存放时发现此地址已被另一个表项 R1 占据，发生了冲突。为此，需把R2存放到表中“下一个”空位中。如果表未被装满，则在允许的范围内必定还有空位
1. 线性探查再散列
需要查找或加入一个表项时，使用散列函数计算地址：H0 = hash(key)；一旦发生冲突，在表中顺次向后寻找“下一个”空位 Hi 的公式为： Hi = (Hi-1 + 1) % m，i =1，2，…，m-1 查找时，若发生冲突，探查下一个地址。当循环 m-1 次后就会回到开始探查时的位置，说明待查关键码不在表内，而且表已满，不能再插入新关键码
示例
设给出一组表项，它们的关键码为 Burke，Ekers，Broad，Blum，Attlee，Alton，Hecht，Ederly。采用的散列函数是：取其第一个字母在字母表中的位置再除以2。 Hash(x)=ë(ord(x)-ord(‘A’)+1)/2û //ord() 是求字符内码的函数
性能分析
ASLsucc是指查找到表中已有表项的平均探查次数 ASLunsucc是指在表中查找不到待查的表项，但找到空着的插入位置的平均探查次数
优缺点分析
· 容易产生“堆积（聚集）” · 不能真正删除元素，会导致其他元素的查找结果发生变化
2. 二次探查再散列
首先通过某一个散列函数对表项的关键码 key 进行计算，得到散列地址，它是一个非负整数。 H0 = hash(key) 然后使用二次探查再散列在表中寻找“下一个”空位，其公式为： Hi = (H0 + i2) % m，Hi = (H0 - i2)% m， i = 1，2，3，…，(m-1)/2 m 是表的大小，它应是一个值为 4k+3 的质数，其中 k 是一个整数。这样的质数如3，7，11，19，23，31，43，59，127，251，503，…。 在做 (H0 - i2) % m 的运算时，当 H0 - i2＜0 时，可补充一个修正语句： if (( j = (H0 - i2)% m)＜0) j += m
优缺点分析
· 装载因子α<=0.5时，一定能够继续插入且没有重复
· 装载因子α > 0.5时，必须将表的长度扩充一倍，进行表的分裂
· 还是只能逻辑删除，不能真正删除表项
3. 双散列法
使用双散列法解决冲突时，需要两个散列函数。 第一个散列函数Hash()按表项关键码key计算表项所在的地址号H0=Hash(key)。 一旦冲突，用第二个散列函数ReHash()计算该表项到达“下一个”地址的间隔。 要求ReHash(key)的取值与key的值有关，它的取值应是小于地址空间大小m且与m互质的正整数。 设表的长度为m，在表中寻找“下一个”地址的迭代公式为： H0 = Hash(key)， Hi = ( Hi-1 + ReHash(key)) % m. 如果写成通项公式为 Hi = (H0 + i * ReHash(key) ) % m，i = 1，2，…，m-1
9.6.4 解决冲突的链地址法
链地址方法首先对关键码集合用某一个散列函数计算它们的散列地址。 通常把各地址相同的表项通过一个单链表链接起来，称之为同义词子表，各链表的表头结点组成一个向量。 向量的元素个数与散列地址数一致。地址为 i 的同义词子表的表头结点是向量中第 i 个元素
举例
示例：给出一组表项关键码 { Burke，Ekers，Broad，Blum，Attlee，Alton，Hecht，Ederly }。散列函数为： Hash (x)＝ë(ord (x)－ord ('A') +1) / 2û 用它计算可得： Hash(Burke) = 1 Hash(Ekers) = 2 Hash(Broad) = 1 Hash(Blum) = 1 Hash(Attlee) = 0 Hash(Hecht) = 4 Hash(Alton) = 0 Hash(Ederly) = 2 散列表为 HT[0..13]，m = 14
性能分析
· 节省空间 · 查找速度更快
9.6.5 散列法分析
· 实验结果表明，链地址法优于开地址法；
· 在散列函数中，用除留余数法作散列函数优于其它类型的散列函数
·
· Sn（ASLsucc）是查找一个随机选择的关键码xi(1<=i<=n)所需的关键码比较次数的期望值 · Un（ASLunsucc）是在长度为m的散列表中n个地址已装入表项的情况下，装入第n+1项所需执行的关键码比较次数期望值
· 平均性能好，但是最坏情况下查找需要O(n)的时间
· 散列表的查找性能，即平均查找长度依赖于散列表的装填因子，不直接依赖于n或m
9.5 其他查找树（*）
第10章 排序
10.1 排序的概念与算法性能
10.1.1 排序的概念
1. 排序
将一组杂乱无章的数据按一定的规律顺次排列起来
2. 数据表
它是待排序数据记录的有限集合
3. 排序码
通常数据记录有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分记录，作为排序依据。该域即为排序码
4. 稳定性
如果在记录序列中有两 个记录r[i]和r[j]，它们的排序码值k[i] == k[j]，且在排序之前，记录r[i]排在r[j]前面。如果在排序之后，记录r[i]仍在记录 r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的
5. 内排序
在排序期间数据记录全部存放在内存的排序
6. 外排序
在排序期间全部记录个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序
7. 排序算法分类
（1）有序区增长
将数据表分成有序区和无序区，在排序过程中逐步扩大有序区，缩短无序区，直到有序区扩大到整个数据表为止
如插入排序、选择排序、起泡排序、堆排序、归并排序等
（2）有序程度增长
数据表不能明确区分有序区和无序区，随着排序过程的执行，逐步调整表中元素的排列，使得表中的有序程度不断提高，直到完全有序
如快速排序、希尔排序、基数排序等
10.1.2 排序算法的性能
1. 内排序
用算法执行中的排序码比较次数KCN与数据移动次数RMN来衡量
2. 外排序
要看读写外存的次数
10.1.3 数据表的结构定义
#define maxSize 20 typedef int DataType; typedef struct { //数据表的类型定义 DataType data[maxSize]; //排序元素数组 int n; //排序元素个数 } DataList; void Swap ( DataList& L, int a, int b ) { //交换L.data[a]和L.data[b]中的内容 DataType temp = L.data[a]; L.data[a] = L.data[b]; L.data[b] = temp; }
10.2 插入排序
10.2.1 直接插入排序
1. 基本思想
当插入第i (i＞0) 个记录时，前面的data[0]，data[1]，…，data[i-1]已经排好序。这时，用data[i]的排序码与data[i-1]，data[i-2]，…的排序码顺序比较，找到插入位置即将data[i]插入，原来位置上的记录向后顺移
2. 图解
3. 算法
void InsertSort ( DataList& L ) { //依次将 L.data[i] 按其排序码插入到有序表L.data[0], //…, L.data[i-1]中，使得L.data[0]到L.data[i]有序。 DataType temp; int i, j; for ( i = 1; i <= L.n-1; i++ ) if ( L.data[i] < L.data[i-1] ) //逆序才找插入位置 { temp = L.data[i]; for ( j = i-1; j >= 0 && temp < L.data[j]; j-- ) L.data[j+1] = L.data[j]; //逆向寻找插入位置 L.data[j+1] = temp; //插入temp } }
4. 性能分析
1. 最好情况
总的排序码比较次数为 n-1, 记录移动次数为 0
2. 最坏情况
第 i 趟时第 i 个记录必须与前面 i 个记录都做排序码比较，并且每做 1 次比较就要做 1 次数据移动
3. 平均情况
10.2.2 表排序
1. 基本思想
· 对于元素序列elem[1]，…，elem[n]，若elem[1]，…，elem[i-1]已经通过指针link按其排序码从小到大链接起来。 · 现要插入elem[i]，i = 2，3，…，n，则必须在前面i-1个链接起来的元素当中，循链检测比较，找到elem[i]应插入的位置，把elem[i]链入，并修改相应链接指针。从而得到elem[1]，…，elem[i]的一个通过指针排好的链表。如此重复执行，直到把elem[n]也插入到链表中排好序为止
2. 图解
3. 算法
#include "StaticLinkList.h" void SLinkInsertSort( StaticLinkList& L ) { //对L.elem[1],...,L.elem[n]按其排序码key排序, 这个表 //是一个静态链表, L.elem[0]做为排序后各个元素所构 //成的有序循环链表的头结点使用。 int i, p, pre; L.elem[0].key = maxValue; L.elem[0].link = 1; L.elem[1].link = 0; //形成有一个元素的有序循环链表 for ( i = 2; i <= L.n; i++ ) //向有序链表中插入一个结点 { p = L.elem[0].link; pre = 0; while ( L.elem[p].key <= L.elem[i].key ) { pre = p; p = L.elem[p].link; } //沿链找插入点 L.elem[i].link = p; L.elem[pre].link = i ; } //结点 i 链入 pre 与 p 之间 }
10.2.3 折半插入（二分法）排序
1. 基本思想
设在顺序表中有一个记录序列data[0]，data[1]，…，data[n-1]。其中， data[0]，…，data[i-1]是已经排序的数据记录。 在插入data[i]时，不是利用顺序查找从后向前寻找插入位置，而是利用折半查找寻找data[i]的插入位置。 对于关键码随机分布的待排序元素序列，折半插入排序比直接插入排序所需要的排序码比较次数要少。但元素移动次数一点也不少
2. 图解（*）
3. 算法
void BinaryInsertSort ( DataList& L ) { //利用折半查找, 在L.data[0]到L.data[i-1]中找L.data[i] //应插入的位置, 再进行插入。 DataType temp; int i, j, low, high, mid; for ( i = 1; i <= L.n-1; i++ ) //逐步扩大有序表 { temp = L.data[i]; low = 0; high = i-1; while ( low <= high ) //寻找插入位置 { mid = (low+high) / 2; //取中点 if ( temp < L.data[mid] ) high = mid-1; //左缩区间 else low = mid+1; //否则, 右缩区间 } for ( j = i-1; j >= low; j-- ) //后移元素，为插 L.data[j+1] = L.data[j]; //入元素空出位置 L.data[low] = temp; //插入 } }
4. 性能分析
1. 最好情况
排序码比较次数为O(nlog2n)，元素移动次数RMN为 0
2. 最坏情况
排序码比较次数为O(nlog2n)，元素移动次数RMN与直接插入排序相同，为 n(n-1)/2
3. 平均情况
排序码比较次数为O(nlog2n)，元素移动次数RMN为O(n2)
10.2.4 希尔排序
1. 基本思想
设待排序记录序列有 n 个记录，首先取一个整数 gap < n 作为间隔，将全部记录分为 gap 个子序列，所有距离为 gap 的记录放在同一个子序列中，在每一个子序列中分别施行直接插入排序。 然后缩小间隔 gap，例如取 gap = ëgap/2û，重复上述的子序列划分和排序工作。直到最后取 gap = 1，将所有记录放在同一个序列中排序为止
2. 图解
3. 算法
void insertSort_gap ( DataList& L, int start, int gap ) { //对从start开始间隔为gap的子序列做直接插入排序 DataType temp; int i, j; for ( i = start+gap; i <= L.n-1; i = i+gap ) if ( L.data[i-gap] > L.data[i] ) //发现逆序 { temp = L.data[i]; j = i; //在前面有序表 do //寻找插入位置 { L.data[j] = L.data[j-gap]; j = j-gap; } while ( j-gap > 0 && L.data[j-gap] > temp ); L.data[j] = temp; } }
void ShellSort ( DataList& L, int delta[ ], int m ) { //按 delta[m] 中给出的间隔，对表 L 做希尔排序 int i, start, gap; for ( i = m-1; i >= 0; i-- ) { gap = delta[i]; for ( start = 0; start < gap; start++ ) insertSort_gap ( L, start, gap ); } //直到d[0] =1停止迭代 };
4. 性能分析
· 当n很大时，排序码平均比较次数和记录平均移动次数约在n1.25到1.6n1.25的范围内
· 运行时间在理论上证明可达到O(n3/2)，但实际模拟结果可达到O(n5/4)
· 希尔排序具有很高的效率，并且代码简单，容易执行，但不稳定
10.3 交换排序
10.3.1 冒泡（起泡）排序
1. 基本思想
设待排序记录序列中的记录个数为n。最多作n-1趟起泡，i = 1，2，...，n-1。在第 i 趟中从后向前，j = n-1，n-2，...，i，顺次两两比较data[j-1]和data[j]。如果发生逆序，即data[j-1]＞data[j]，则交换data[j-1]和data[j]
2. 图解
3. 算法
void BubbleSort ( DataList& L ) { //对L中的 n 个元素进行起泡排序, 执行 n-1 趟, 第 i 趟 //对L.data[L.n-1]～L.data[i]起泡 int exchange; int i, j; DataType tmp; for ( i = 0; i <= L.n-2; i++ ) { exchange = 0; //本趟设定无交换 for ( j = L.n-1; j >= i+1; j-- ) if ( L.data[j-1] > L.data[j] ) //逆序，有交换 { Swap ( L, j-1, j ); exchange = 1; } if ( !exchange ) return; //本趟无逆序, 停止处理 } }
4. 性能分析
1. 最好情况
在记录的初始排列已经按排序码的值从小到大排好序时，此算法只执行一趟起泡，做n-1次排序码比较，不移动记录。这是最好的情形
2. 最坏情况
算法执行n-1趟起泡，第i趟(1<=i＜n) 做 n-i 次排序码比较，执行 n-i 次记录交换
3. 时间复杂度
O(n2 )
· 所有简单排序方法中速度最慢的一个
10.3.2 快速排序
1. 基本思想
任取待排序记录序列中的某个记录(例如取第一个记录)作为基准，按照该记录的排序码值的大小，将整个记录序列划分为左右两个子序列： · 左侧子序列中所有记录的排序码值都小于或等于基准记录的排序码值； · 右侧子序列中所有记录的排序码值都大于基准记录的排序码值。 基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置) 然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止
2. 图解
3. 算法
int Partition ( DataList& L, int low, int high ) { int i = low, j = high; DataType pivot = L.data[low]; //基准元素 while ( i < j ) //扫描整个序列 { while ( i < j && L.data[j] >= pivot ) j--; //反向检测到排序码小于基准的元素 if ( i < j ) { L.data[i] = L.data[j]; i++; //把小于基准的元素移到左边去 while ( i < j && L.data[i] <= pivot ) i++; //正向检测到排序码大于基准的元素 if ( i < j ) { L.data[j] = L.data[i]; j--; } //把大于基准的元素移到右边去 } } L.data[i] = pivot; return i; //将基准元素就位 } void QuickSort ( DataList& L, int left, int right ) { if ( left < right ) { //序列长度小于或等于1不处理 int pivotpos = Partition ( L, left, right ); //一趟划分 QuickSort ( L, left, pivotpos-1 ); //左侧子序列 QuickSort ( L, pivotpos+1, right ); //右侧子序列 } }
4. 性能分析
· 函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言，快速排序是所有内排序方法中最好的一个
· 最大递归调用层次数与递归树高度一致，理想情况为élog2(n+1)ù 。故栈的存储开销为 O(log2n)
10.3.3 快速排序的改进（*）
10.8 外部排序（*）
10.7 内部排序算法的分析和比较
10.7.1 排序算法的下界
对n个元素进行排序，时间复杂度最小为O(nlog2n)
10.7.2 各种内部排序算法的比较
1. 时间复杂度比较
（1）排序码比较次数
不受排序码初始排列影响
· 折半插入排序（O(nlog2n)） · 简单选择排序（O(n2)） · 两路归并排序（O(nlog2n)） · 堆排序（ O(nlog2n) ） · 锦标赛排序（ O(nlog2n) ）
受排序码初始排列影响
· 直接插入排序（O(n)～O(n2)） · 快速排序（ O(nlog2n)～O(n2) ） · 起泡排序（O(n)～O(n2)）
（2）元素移动次数
不受排序码初始排列影响
· 两路归并排序（O(nlog2n)） · 堆排序（ O(nlog2n) ） · 表排序（0） · 锦标赛排序（0）
受排序码初始排列影响
· 直接插入排序（0～O(n2)） · 折半插入排序（0～O(n2) ） · 起泡排序（0～O(n2)） · 快速排序（ O(nlog2n)～O(n2) ） · 简单选择排序（0～O(n) ）
2. 空间复杂度比较
原地排序（附加空间达到O(1)）
· 直接插入排序 · 折半插入排序 · 希尔排序 · 起泡排序 · 简单选择排序 · 堆排序
需要 O(log2n)～O(n) 个元素附加空间
· 快速排序
需要 n 个元素附加空间
· 两路归并排序
需要 n-1 个整数附加空间
· 锦标赛排序
需要 n+1 个指针附加空间
· 表排序
需要 n+2rd 个指针附加空间
· 基数排序
3. 稳定性比较
不稳定
· 希尔排序 · 简单选择排序 · 快速排序 · 堆排序
稳定
· 直接插入排序 · 折半插入排序 · 起泡排序 · 锦标赛排序 · 归并排序 · 表排序
4. 规模n比较
方法简单、适用于 n 比较小
· 插入排序 · 起泡排序 · 简单选择排序
方法不简单，适用于 n 比较大
· 希尔排序 · 快速排序 · 堆排序 · 锦标赛排序 · 两路归并排序（适合 n 特别大的情形） · 基数排序
5. 其他方面的比较
排序过程中，每趟有一个元素“就位”，即达到最终位置的排序方法 · 起泡排序 · 快速排序 · 简单选择排序 · 堆排序 · 锦标赛排序
在 n 比较大时选出最小的几个元素，要求比较次数最少的排序方法 锦标赛排序 · 堆排序
在排序过程中有些元素会向相反方向移动的排序方法 · 起泡排序
当排序码的初始排列基本有序（绝大多数元素已经有序）时最快的排序方法 · 直接插入排序
平均情况下最快的排序方法 · 快速排序
对 n 个元素做堆排序时堆的高度是 h = élog2(n+1)ù
对 n 个元素做锦标赛排序时胜者树的高度是 h =élog2nù +1
6. 总结
10.6 基数排序
10.6.1 基数排序
1. 概念
基数排序是采用“分配”与“收集”的办法，用对多排序码进行排序的思想实现对单排序码进行排序的方法
2. 分类
MSD（最高位优先）
· 先根据最高位排序码K1排序，得到若干元素组，元素组中各元素都有相同排序码K1。 · 再分别对每组中元素根据排序码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的元素具有相同的K1和K2值。 · 依此重复，直到对排序码Kd完成排序为止。 · 最后，把所有子组中的元素依次连接起来，就得到一个有序的元素序列
LSD（最低位优先）
· 首先依据最低位排序码Kd对所有元素进行一趟排序，再依据次低位排序码Kd-1对上一趟排序的结果再排序，依次重复，直到依据排序码K1最后一趟排序完成，就可以得到一个有序的序列。 · 这种排序方法对每个排序码进行排序时，不需要再分组，而是整个元素组都参加排序
3. 图解
4. 性能分析
若每个排序码有 d 位, 需重复执行 d 趟“分配”与“收集”。每趟对 n 个元素进行“分配”，对rd个队列进行“收集”。总时间复杂度为O(d(n+rd))
10.5 归并排序
10.5.1. 二路归并排序
1. 二路归并排序的设计思路
归并排序采用典型的分而治之算法，描述如下: MergeSort (List) { if ( List的长度大于1 ) { 将序列List划分为等长的两个子序列 LeftList和Right List; MergeSort (LeftList); //对子序列递归排序 MergeSort (RightList); //对子序列递归排序 将两个子序列 LeftList和RightList归并为一个序列List; } }
· 当i和j都在两个表的表长内变化时，根据对应项的排序码的大小，依次把排序码小的记录排放到新表k所指位置中； · 当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中
· 算法总的时间复杂度为O(nlog2n)
2. 二路归并排序的递归算法
void Merge ( DataList& L, int left, int mid, int right ) { //L.data[left..mid]与L.data[mid+1..right]是两个有序 //表, 将它们归并成一个有序表L，仍放在原地。 int i = left, j = mid+1, k = 0, s = right-left+1; //i, j是检测指针, k是存放指针 DataType *L2 = ( DataType*) malloc ( s*sizeof ( DataType )); while ( i <= mid && j <= right ) //做两两比较 if ( L.data[i] <= L.data[j] ) //小者存入L2 L2[k++] = L.data[i++]; else L2[k++] = L.data[j++]; while ( i <= mid ) L2[k++] = L.data[i++]; //若第一个表未检测完, 复制 while ( j <= right ) L2[k++] = L.data[j++]; //若第二个表未检测完, 复制 for ( i = 0; i < s; i++ ) L.data[left+i] = L2[i]; //归并结果传送回L free (L2); } void doSort ( DataList& L, int left, int right ) { if ( left < right ) { int mid = (left+right)/2; //划分为两个子序列 doSort ( L, left, mid ); //左子序列递归排序 doSort ( L, mid+1, right ); //右子序列递归排序 Merge ( L, left, mid, right ); //合并 } } void mergeSort ( DataList& L ) { doSort ( L, 0, L.n-1 ); //对序列归并排序 };
3. 二路归并排序的迭代算法（*）
10.4 选择排序
10.4.1 简单选择排序
1. 基本思想
· 在一组记录 data[i]～data[n-1] 中选择具有最小排序码的记录； · 若它不是这组记录中的第一个记录，则将它与这组记录中的第一个记录对调; · 在这组记录中剔除这个具有最小排序码值的记录。在剩下的记录 data[i+1]～data[n-1] 中重复执行第①、②步，直到剩余记录只有一个为止
2. 图解
3. 算法
void SelectSort ( DataList& L ) { int i, j, k; DataType tmp; for ( i = 0; i < L.n-1; i++ ) { k = i; //在L[i..n-1]中找排序码最小的元素 for ( j = i+1; j <= L.n-1; j++ ) if ( L.data[j] < L.data[k] ) k = j; if ( k != i ) Swap ( L, k, i ); //交换 } }
4. 性能分析
1. 最好情况
RMN = 0
2. 最坏情况
RMN = 3(n-1)
· 不推荐
10.4.2 堆排序
1. 基本思想
· 根据初始输入数据，利用堆的筛选算法siftDown()形成初始堆; · 通过一系列的记录交换和重新调整堆进行排序。
2. 图解
3. 算法
void siftDown ( maxHeap& H, int start, int m ) { //从结点 start 开始到 m 为止, 自上向下筛选比较 if ( start == m ) return; //一个元素不调整 int i = start; int j = 2*i+1; // j 是 i 的左子女 DataType temp = H.data[i]; //暂存子树根结点 while ( j <= m ) { //逐层筛选 if ( j < m && H.data[j] < H.data[j+1] ) j++; if ( temp >= H.data[j] ) break; //纵向比较 else { H.data[i] = H.data[j]; i = j; j = 2*j+1; } } //大子女上移，i下降到大子女j位置 H.data[i] = temp; //回放 } void HeapSort ( maxHeap& H ) { //对大根堆 H.data[0] 到 H.data[H.n-1] 进行排序, 使 //得表中各个记录按其排序码非递减有序。 int i; for ( i = (H.n/2 -1; i >= 0; i-- ) siftDown ( H, i, H.n -1); //初始堆 for ( i = H.n-1; i >= 1; i-- ) { Swap ( H.data[0], H.data[i] );//交换 siftDown ( H, 0, i-1 ); //重建大根堆 } }
4. 性能分析
· 堆排序的时间复杂性为O(nlog2n)
10.4.3 锦标赛排序
1. 基本思想
锦标赛排序的思想与体育比赛时的淘汰赛类似。首先取得 n 个元素的排序码，进行两两比较，得到 én/2ù 个比较的优胜者（排序码小者），作为第一步比较的结果保留下来。然后对这 én/2ù 个元素再进行排序码的两两比较，…，如此重复，直到选出一个排序码最小的元素为止。 由于每次两两比较的结果是把排序码小者作为胜者上升到父结点，所以称这种比赛树为胜者树。 在胜者树中，外结点（最底层）保存待排序的所有排序码；内结点保存比较胜者的外结点号 胜者树最顶层是树的根，保存最后选择出来的具有最小排序码值的元素
2. 图解
3. 算法（*）
4. 性能分析
· 时间复杂度为O(nlog2n)