使用教材：《大话数据结构》
使用语言：C语言（C90标准）
代码编写工具：Visual Studio Code
使用编译器：gcc8.1.0
1. 数据结构以及算法的定义
- 程序设计 = 数据结构 + 算法
- 数据结构：指相互之间存在一种或多种特定关系的数据元素的集合
- 算法：解决特定问题求解步骤的描述
- 算法的五个基本特性：输入、输出、有穷性、确定性、可行性
- 算法可以有零个或多个输入，至少有一个输出
- 用大 O 记法来表示算法时间复杂度
- 推导大 O 阶：
- 用常数 1 取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是 1，则去除与这个项相乘的常数。最终得到的结果就是大 O 阶
- 常用时间复杂度分类：
- 常数阶：O(1)
- 线性阶：O(n)
- 对数阶：O(logn)
- 平方阶：O(n²)
- nlogn 阶：O(nlogn)
- 立方阶：O(n³)
- 指数阶：O(2^n)
- 常用时间复杂度按照耗费时间从小到大排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n) - 一般情况下说的时间复杂度都是最坏情况下的时间复杂度
- 算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求
- 算法的度量方法：事后统计方法（不科学、不准确）、事前分析估算方法
2. 线性表
2.1. 定义
零个或多个数据元素的有限序列。（序列表示线性表元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素有且只有一个前驱和后继。）
2.2. 数据类型定义
ADT 线性表(List)
Data
线性表的数据对象集合为 {a1,a2,...，an}，每个元素的类型均为 DataType。
其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。
数据元素之间的关系是一对一的关系。
Operation
InitList()：初始化操作，建立一个空的线性表L并返回。
ListEmpty(L)：若线性表为空，返回 true；否则返回 false。
ClearList(*L)：将线性表清空。
GetElem(L, i, *e)：将线性表 L 中的第 i 个位置元素值返回给 e。
LocationElem(L, e)：在线性表 L 中查找与给定元素值 e 相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则返回 -1。
end ADT
2.3. 线性表的两种物理结构
2.3.1. 顺序存储结构
2.3.1.1. 定义
用一段地址连续的存储单元依次存储线性表的数据元素。
/* 存储空间初始分配量 */
#define MAX_SIZE 20
/* ElemType 类型根据实际情况而定，这里假设为 int */
typedef int ElemType;
typedef struct
{
/* 数组存储数据元素，最大容量为 MAX_SIZE */
ElemType data[MAX_SIZE];
/* 线性表当前长度 */
int length;
} SqList;
注意：在任意时刻，线性表长度应该小于等于数组的长度。
2.3.1.2. 顺序线性表元素位置的计算
假设线性表中每一个元素占用 c 个存储单元，那么第 i+1 个数据元素与第 i 个数据元素的存储位置关系：
LOC(ai + 1) = LOC(ai) + c
因此，对于第 i 个数据元素 ai 的存储位置可以由 a1 推出：
LOC(ai) = LOC(a1) + (i - 1) * c
通过这个公式，可以得出该线性表的存取数据的时间复杂度为 O(1)，通常把具有这一特点的存储结构成为随机存取结构。
2.3.1.3. 顺序线性表获取元素(GetElem)的操作
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* Status 是函数的类型，其值是函数结果状态代码，如 OK 等 */
typedef int Status;
/* 初始条件：顺序线性表 L 已经存在，1 <= i <= ListLength(L) */
/* 操作结果：用 e 返回 L 中第 i 个数据元素的值 */
Status GetElem(SqList L, int i, ElemType *e)
{
if (L.length == 0 || i < 1 || i > L.length)
{
return ERROR;
}
*e = L.data[i - 1];
return OK;
}
2.3.1.4. 顺序线性表的插入(ListInsert)操作
思路：
1. 如果插入位置不合理，则抛出异常 2. 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量 3. 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置 4. 将要插入元素填入位置 i 处；线性表长度 +1实现代码：
/* 初始条件：顺序线性表 L 已存在， 1 <= i <= ListLength(L) */ /* 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */ Status ListInsert(SqList *L, int i, ElemType e) { int k; /* 顺序线性表已满 */ if (L->length == MAX_SIZE) { return ERROR; } /* 当 i 不在范围内时 */ if (i < 1 || i > L->length + 1) { return ERROR; } /* 若插入数据位置不在表尾 */ if (i <= L->length) { /* 将要插入位置后数据元素向后移动一位 */ for (k = L->length - 1; k >= i - 1; k--) { L->data[k + 1] = L->data[k]; } } /* 将新元素插入 */ L->data[i - 1] = e; L->length++; return OK; }
2.3.1.5. 顺序线性表的删除(ListDelete)操作
思路：
1. 如果删除位置不合理，抛出异常 2. 取出删除元素 3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置 4. 表长减一实现代码：
/* 初始条件：顺序线性表 L 已存在，1 <= i <= ListLength(L) */ /* 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减1 */ Status ListDelete(SqList *L, int i, ElemType *e) { int k; /* 线性表为空 */ if (L->length == 0) { return ERROR; } /* 删除位置不合理 */ if (i < 1 || i > L->length) { return ERROR; } *e = L->data[i - 1]; /* 如果删除的不是最后一个位置 */ if (i < L->length) { /* 将删除位置后继元素前移 */ for (k = i; k < L->length; k++) { L->data[k - 1] = L->data[k]; } } L->length--; return OK; }
分析可得出，线性表的顺序存储结构在插入、删除操作时的时间复杂度为 O(n)，说明它比较适合于元素个数不太变化，而更多的是存取数据的应用。
2.3.1.6. 线性表顺序存储结构的优缺点
优点：
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点：
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”
2.3.2. 链式存储结构
2.3.2.1. 定义
用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
为了表示 ai 与其直接后继元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素 ai 的存储映像，称为结点(Node)。n 个结点链结成一个链表，即为线性表的链式存储结构，只有一个指针域的称为单链表。
2.3.2.2. 头指针与头结点的区别
头指针：
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头节点的指针
- 头指针具有标识作用，所以常用头指针冠以链表的名字
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点：
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可以存放链表的长度）
- 有了头结点，对在第一元素结点前插入和删除第一结点，其操作与其它结点的操作就统一了
- 头结点不一定是链表必须要素
2.3.2.3. 线性表的单链表存储结构代码描述
/* 线性表的单链表存储结构 */
typedef struct Node
{
ElemType data;
struct Node *next;
} Node;
/* 定义LinkList */
typedef struct Node* LinkList;
2.3.2.4. 单链表的读取
获取链表第 i 个数据的算法思路：
1. 声明一个指针 p 指向链表第一个结点，初始化 j 从 1 开始 2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1 3. 若到链表末尾 p 为空，则说明第 i 个结点不存在 4. 若查找成功，返回结点 p 的数据实现代码：
/* 初始条件：顺序线性表 L 已存在，1 <= i <= ListLength(L) */ /* 操作结果：用 e 返回 L 中第 i 个数据元素的值 */ Status GetElem(LinkList L, int i, ElemType *e) { int j; /* 声明一个指针 p */ LinkList p; /* 让 p 指向链表 L 的第一个结点，因为假设 L 是带头结点的，所以 L->next 才是第一个结点 */ p = L->next; /* j 为计数器 */ j = 1; /* p 不为空且计数器 j 还没有等于 i 时，循环继续 */ while (p && j < i) { p = p->next; ++j; } /* 第 i 个结点不存在 */ if (!p || j > i) { return ERROR; } /* 取第 i 个结点的数据 */ *e = p->data; return OK; }
分析可得，单链表的读取时间复杂度为 O(n)。
2.3.2.5. 单链表的插入操作
思路：
1. 声明一指针 p 指向链表头结点，初始化 j 从 1 开始 2. 当j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1 3. 若到链表末尾 p 为空，则说明第i个结点不存在 4. 否则查找成功，在系统中生成一个空结点 s 5. 将数据元素 e 赋值给 s->data 6. 单链表的插入标准语句：s->next = p->next;p->next = s;（这两句话绝对不能交换顺序） 7. 返回成功实现代码：
/* 初始条件：顺序线性表 L 已存在，1 <= i <= ListLength(L) */ /* 操作结果：在 L 中第 i 个结点位置之前插入新的数据元素 e，L 长度加 1 */ Status ListInsert(LinkList *L, int i, ElemType e) { int j; LinkList p, s; p = *L; j = 1; /* 寻找第 i - 1 个结点 */ while (p && j < i) { p = p->next; ++j; } /* 第 i 个结点不存在 */ if (!p || j > i) { return ERROR; } /* 生成新结点 */ s = (LinkList)malloc(sizeof(Node)); s->data = e; s->next = p->next; p->next = s; return OK; }
2.3.2.6. 单链表的删除操作
思路：
1. 声明一指针 p 指向链表头结点，初始化 j 从 1 开始 2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1 3. 若到链表末尾 p 为空，则说明第 i 个结点不存在 4. 否则查找成功，将欲删除的结点 p->next 赋值给 q 5. 单链表的删除标准语句：p->next = q->next 6. 将 q 结点中的数据赋值给 e，作为返回 7. 释放 q 结点 8. 返回成功实现代码：
/* 初始条件：顺序线性表 L 已存在，1 <= i <= ListLength(L) */ /* 操作结果：删除 L 的第 i 个结点，并用 e 返回其值，L 的长度减 1 */ Status ListDelete(LinkList *L, int i, ElemType e) { int j; LinkList p, q; p = *L; j = 1; /* 遍历寻找第 i-1 个结点 */ while (p->next && j < i) { p = p->next; ++j; } /* 第 i 个结点不存在 */ if (!(p->next) || j > i) { return ERROR; } q = p->next; /* 将 q 的后继赋值给 p 的后继 */ p->next = q->next; /* 将 q 结点中的数据给 e */ *e = q->data; /* 让系统回收此结点，释放内存 */ free(q); return OK; }
分析可以得出，单链表的插入与删除时间复杂的都也是 O(n)。
乍一看与顺序表没啥优势，但是如果当同时插入多个数据，那么单链表只有第一次需要遍历寻找第 i 个结点的位置，时间复杂度为 O(n)。但是后面的几次就只需要简单的赋值移动指针完成了，时间复杂度为 O(1)。所以，对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。
2.3.2.7. 单链表的整表创建
思路：
1. 声明一指针 p 和计数变量 i 2. 初始化一空链表 L 3. 让 L 的头结点的指针指向 NULL，即建立一个带头结点的单链表 4. 循环： 4.1. 生成一新结点赋值给 p 4.2. 随机生成一数字赋值给 p 的数据域 p->data 4.3. 将 p 插入到头结点域前一新结点之间实现代码：
/* 随机产生 n 个元素的值，建立带表头结点的线性单链表 L （头插法） */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; /* 初始化随机数种子 */ srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); /* 先建立一个带头结点的单链表 */ (*L)->next = NULL; for (i = 0; i < n; i++) { /* 生成新节点 */ p = (LinkList)malloc(sizeof(Node)); /* 随机生成 100 以内的数字 */ P->data = rand() % 100 + 1; p->next = (*L)->next; /* 插入到表头 */ (*L)->next = p; } }/* 随机产生 n 个元素的值，建立带表头结点的线性单链表 L （尾插法） */ void CreateListTail(LinkList *L, int n) { LinkList p, r; int i; /* 初始化随机数种子 */ srand(time(0)); /* L 指整个单链表 */ *L = (LinkList)malloc(sizeof(Node)); /* r 为指向尾部的结点 */ r = *L; for (i = 0; i < n; i++) { /* 生成新节点 */ p = (LinkList)malloc(sizeof(Node)); /* 随机生成100以内的数字 */ P->data = rand() % 100 + 1; /* 将表尾终端结点的指针指向新结点 */ r->next = p; /* 将当前的新结点定义为表尾终端结点 */ r = p; } /* 表示当前链表结束 */ r->next = NULL; }
2.3.2.8. 单链表的整表删除
思路：
1. 声明一个指针 p 和 q 2. 将第一个结点赋值给 p 3. 循环： 3.1. 将下一结点赋值给 q 3.2. 释放 p 3.3. 将 q 赋值给 p实现代码：
/* 初始条件：顺序线性表 L 已存在，操作结果：将 L 重置为空表 */ Status ClearList(LinkList *L) { LinkList p, q; /* p 指向第一个结点 */ p = (*L)->next; /* 没到表尾 */ while (p) { q = p->next; free(p); p = q; } /* 将头结点的指针域设置为空 */ (*L)->next = NULL; return OK; }
2.3.3. 单链表结构与顺序存储结构的对比
存储分配方式：
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
- 查找：
- 顺序存储结构 O(1)
- 单链表 O(n)
- 插入和删除：
- 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)
- 单链表在找出某位置的指针后，插入和删除时间仅为 O(1)
- 空间性能：
- 顺序存储结构徐涛预分配存储空间，分大了，浪费，分小了易发生上溢
- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
- 查找：
通过上面的对比，可以得出一些经验性的总结：
- 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构
- 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，如果事先知道线性表的大致长度，用顺序存储结构效率会高很多
2.4. 静态链表
2.4.1. 定义
使用数组来代替指针，来描述单链表。
首先，让数组的元素都是由两个数据域组成，data 和 cur。
也就是说，数组的每一个下标都对应一个 data 和一个 cur。
数据域 data 用来存放数据元素；而游标 cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。
就把这种用数组表述的链表叫静态链表，还有起名叫做游标实现法。主要用于不支持指针的程序设计语言中。
2.4.2. 线性表的静态链表的存储结构
/* 线性表的静态链表存储结构 */
/* 假设链表的最大长度为 1000 */
#define MAX_SIZE 1000
typedef struct
{
ElemType data;
/* 游标，为 0 时表示无指向 */
int cur;
} Component, StaticLinkList[MAX_SIZE];
另外对数组第一个和最后一个元素作为特殊元素处理，不存数据。
通常把未被使用的数组元素称为备用链表。
数组第一个元素，即下标为 0 的元素 cur 就存放备用链表的第一个结点的下标；
而数组的最后一个元素的 cur 则存放第一个有数值元素的下标，相当于单链表中的头结点作用,当整个链表为空时，则为 0。
初始化的数组状态：
/* 将一维数组 space 中各分量链成一备用链表 */
/* space[0].cur 为头指针，"0" 表示空指针 */
Status InitList(StaticLinkList space)
{
int i;
for (i = 0; i < MAX_SIZE - 1; i++)
{
space[i].cur = i + 1;
}
/* 目前静态链表为空，最后一个元素的 cur 为 0 */
space[MAX_SIZE - 1].cur = 0;
return OK;
}
2.4.3. 静态链表的插入操作
思路： 为了辨明数组中哪些分量未被使用，解决办法是将所有未被使用过的及已被删除的分量用游标链成一个备用链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点
/* 若备用空间链表非空，则返回分配的结点下标，否则返回 0 */ int Malloc_SLL(StaticLinkList space) { /* 当前数组第一个元素的 cur 存的值，就是要返回的第一个备用空闲的下标 */ int i = space[0].cur; if (space[0].cur) { /* 由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用 */ space[0].cur = space[i].cur; } return i; }插入实现代码：
Status ListInsert(StaticLinkList L, int i, ElemType e) { int j, k, l; /* 注意 k 首先是最后一个元素的下标 */ k = MAX_SIZE - 1; if (i < 1 || i > ListLength(L) + 1) { return ERROR; } /* 获取空闲分量的下标 */ j = Malloc_SSL(L); if (j) { /* 将数据赋值给此分量的 data */ L[j].data = e; /* 找到第i个元素的位置 */ for (l = 1; l <= i - 1; l++) { k = L[k].cur; } /* 把第 i 个元素之前的 cur 赋值给新元素的 cur */ L[j].cur = L[k].cur; /* 把新元素的下标赋值给第 i 个元素之前元素的 cur */ L[k].cur = j; return OK; } return ERROR; }
2.4.4. 静态链表的删除操作
- 思路： 和前面一样，删除元素使，原来使需要释放结点的函数
free()。现在也得自己实现它 - 实现代码：
/* 删除在 L 中第 i 个数据元素 e */ Status LsitDelete(StaticLinkList L, int i) { int j, k; if (i < 1 || i > ListLegth(L)) { return ERROR; } k = MAX_SIZE - 1; for (j = 1; j <= i - 1; j++) { k = L[k].cur; } j = L[k].cur; L[k].cur = L[j].cur; Free_SSL(L, j); return OK; } /* 将下标为 k 的空闲结点回收到备用链表 */ void Free_SSL(StaticLinkList space, int k) { /* 把第一个元素 cur 值赋给要删除的分量 cur */ space[k].cur = space[0].cur; /* 把要删除的分量下标赋值给第一个元素的 cur */ space[0].cur = k; }
2.4.5. 静态链表的一些其他操作
比如 ListLength()
/* 初始条件：静态链表 L 已存在。操作结果：返回 L 中数据元素个数 */
int ListLength(StaticLinkList L)
{
int j = 0;
int i = L[MAX_SIZE - 1].cur;
while (i)
{
i = L[i].cur;
j++;
}
return j;
}
2.4.6. 静态链表的优缺点
- 优点： 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
- 缺点：
- 没有解决连续存储分配带来的表长难以确定的问题
- 失去了顺序存储结构随机存取的特性
2.5. 循环链表
2.5.1. 定义
将单链表中的终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
2.5.2. 其他
循环链表的判断条件不再是判断 p->next 是否为空，而是判断 p->next 是否等于头结点了
循环链表使用指向终端结点的尾指针而不使用头指针来表示循环链表，这样查找头结点和终端结点的时间复杂度都变为 O(1) 了，终端结点用尾指针 rear 指示，头结点就是 rear->next，开始结点就是 rear->next->
next。要想将两个循环链表合并成一个表时，使用尾指针就很方便了实现代码：
```c /* 保存 A 表的头结点 */ p = rearA->next; /* 将本来是指向B表的第一个结点（不是头结点）赋值给 rear->next */ rearA->next = rearB->next->next; /* 将原A表的头结点赋值给 rearB->next */ rearB->next = p; /* 释放 p */ free(p); ```
2.6. 双向链表
2.6.1. 定义
在单链表的每个结点中，再设置一个指向其前驱结点的指针域，即成为了双向链表。
2.6.2. 双向链表的存储结构
/* 线性表的双向链表存储结构 */
typedef struct DuLNode
{
ElemType data;
/* 直接前驱指针 */
struct DuLNode *prior;
/* 直接后继指针 */
struct DuLNode *next;
} DuLNode, *DulinkList;
2.6.3. 双向链表也有可以有循环链表
对于链表中的某一个结点 p，它的后继的前驱、前驱的后继都是它自己：p->next->prior = p = p->prior->next。
双向链表时单链表中扩展出来的结构，所以很多操作是相同的，比如求长度的 ListLength，查找元素的 GetElem，获得元素位置的 LocationElem
等，这些操作都只涉及一个方向的指针，另一指针也不能提供任何帮助。但是双向链表再插入和删除时要麻烦一些，需要修改两个指针变量。
2.6.4. 双向链表的插入操作
并不复杂，但是顺序很重要，不能写反了！！
假设存储元素 e 的结点 s，现在要实现将结点 s 插入到结点 p 和 p->next 之间：
实现代码：
/* 这四步的顺序千万不能换！ */
/* 把 p 赋值给 s 的前驱 */
s->prior = p;
/* 把 p->next 赋值给 s 的后继 */
s->next = p->next;
/* 把 s 赋值给 p->next 的前驱 */
p->next->prior = s;
/* 把 s 赋值给 p 的后继 */
p->next = s;
/* 总结顺序就是：先搞定 s 的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继 */
2.6.5. 双向链表的删除操作
若要删除结点 p 只需要两步。
实现代码：
/* 这里的 p 代表的是当前要删除的结点，与代码中的 p 不相同 */
/* 把 p->next 赋值给 p->prior 的后继 */
p->prior->next = p->next;
/* 把 p->prior 赋值给 p->next 的前驱 */
p->next->prior = p->prior;
/* 释放结点 */
free(p);
3. 栈与队列
3.1. 栈
3.1.1.定义
栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。
把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称 LIFO 结构。
3.1.2. 理解栈的定义需要注意
- 首先它是一个线性表，也就是说栈元素具有线性关系，即前驱后继关系。只不过是一特殊的线性表而已。定义中说的线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底
- 栈底是固定的，最先进栈的只能再栈底
- 栈的插入操作，叫做进栈，也称压栈、入栈
- 栈的删除操作，叫做出栈，也有的叫作弹栈
3.1.3. 栈的抽象数据类型定义
ADT 栈(Stack)
Data
栈的数据对象集合为{a1,a2,...，an}，每个元素的类型均为 DataType。
其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。
数据元素之间的关系是一对一的关系。
Operation
InitStack()：初始化操作，建立并返回一个空栈 S。
DestroyStack(*S)：若栈存在，则销毁它。
ClearStack(*S)：将栈清空。
StackEmpty(S)：若栈为空，返回 true，否则返回 false。
GetTop(S, *e)：若栈存在且非空，用 e 返回 S 的栈顶元素。
Push(*S, e)：若栈 S 存在，插入新元素 e 到栈 S 中并成为栈顶元素。
Pop(*S, *e)：删除栈 S 中栈顶元素，并用 e 返回其值。
StackLength(S)：返回栈 S 中的元素个数。
end ADT
3.1.4. 栈的顺序存储结构
3.1.4.1. 定义
栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。一般用数组下标为 0 的一端作为栈底比较好，因为首元素都在栈底，变化最小，所以让它作为栈底。
当栈存在一个元素时，top 为 0，通常将空栈的判定条件定为 top=-1。
3.1.4.2. 结构定义
/* SElemType 类型根据实际情况而定，这里假设为 int */
typedef int SElemType;
typedef struct
{
SElemType data[MAX_SIZE];
/* 用于栈顶指针 */
int top;
} SqStack;
3.1.4.3. 进栈操作
Statuc Push(SqStack *S, SElemType e)
{
// 如果栈已经满了
if (S->top == MAXSIZE - 1)
{
return ERROR;
}
// 栈顶指针加 1
S->top++;
// 将新插入元素赋值给栈顶空间
S->data[S->top] = e;
return OK;
}
时间复杂度 O(1)。
3.1.4.4. 出栈操作
Status Pop(SqStack *S, SElemType *e)
{
// 如果是空栈
if (s->top == -1)
{
return ERROR;
}
// 将要删除的栈顶元素赋值给 e
*e = S->data[S->top];
// 栈顶指针减一
S->top--;
return OK;
}
时间复杂度 O(1)。
3.1.5. 两栈共享空间
3.1.5.1. 做法
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为数组的末端之后，即下标为数组长度 n 处。
这样，两个栈如果增加元素，就是两端点向中间延伸。当 top1 = -1， top2 = n 的时候就是空栈，当 top1 + 1 = top2 的时候就是栈满。
3.1.5.2. 结构代码
/* 两栈共享空间结构 */
typedef struct
{
SElemType data[MAX_SIZE];
// 栈 1 栈顶指针
int top1;
// 栈 2 栈顶指针
int top2;
} SqDoubleStack;
3.1.5.3. push(入栈)操作
- 思路：除了要插入元素值参数外，还需要有一个判断是栈 1 还是栈 2 的栈号参数 stackNumber
- 实现代码：
/* 插入元素 e 为新的栈顶元素 */ Status Push(SqDoubleStack *S, SElemType e, int stackNumber) { // 栈已经满了，不能再 push 新元素了 if (S->top1 + 1 == S->top2) { return ERROR; } // 如果是栈 1 有元素进栈 if (stackNumber == 1) { // 若是栈 1 则先 top1 + 1 然后给数组元素赋值 S->data[++S->top1] = e; } // 如果是栈 2 有元素进栈 else if (stackNumber == 2) { // 若是栈 2 则先 top2 - 1 然后给数组元素赋值 S->data[--S->top2] = e; } return OK; }
3.1.5.4. pop(出栈)操作
/* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR */
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber)
{
if (stackNumber == 1)
{
// 栈 1 已经是空栈了
if (S->top1 == -1)
{
return ERROR;
}
// 将栈 1 的栈顶元素出栈
*e = S->data[S->top1--];
}
else if (stackNumber == 2)
{
// 栈 2 已经是空栈了
if (S->top2 == MAXSIZE)
{
return ERROR;
}
// 将栈 2 的栈顶元素出栈
*e = S->data[S->top2++];
}
return OK;
}
3.1.5.5. 使用场景
使用两栈共享空间这样的数据结构，通常都是当两个栈的空间需求有相反
关系时，也就是一个栈在增长时另一个栈正在缩短的情况，就像买卖股票一样，你买入时，一定是有人卖出的。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停的增长，就很快会因栈满而溢出了。
3.1.6. 栈的链式存储结构
3.1.6.1. 定义
又简称为链栈，在链栈中，头结点已经不需要了。
3.1.6.2. 链栈的结构代码
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
} StackNode, *LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
} LinkStack;
/* 链栈的操作绝大部分都和单链表类似，只是在插入和删除上特殊一些 */
3.1.6.3. 进栈(push)操作
假设元素值为 e 的新结点是 s，top 为栈顶指针。
实现代码：
/* 插入元素为 e 的新的栈顶元素 */
Status Push(LinkStack *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
// 把当前的栈顶元素赋值给新结点的直接后继
s->next = S->top;
// 将新结点 s 赋值给栈顶指针
S->top = s;
S->count++;
return OK;
}
时间复杂度 O(1)。
3.1.6.4. 出栈(pop)操作
- 思路：假设变量 p 用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放 p 即可
- 实现代码：
/* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR */ Status Pop(LinkStack *S, SElemType *e) { LinkStackPtr p; // 如果栈为空 if (StackEmpty(*S)) { return ERROR; } *e = S->top->data; // 将栈顶结点赋值给 p p = S->top; // 使栈顶指针下移一位，指向后一结点 S->top = S->top->next; // 释放结点 p free(p); S->count--; return OK; }
时间复杂度 O(1)。
3.1.7. 栈的应用
3.1.7.1. 递归
- 把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数
- 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出
3.1.7.2. 四则运算表达式求值
3.1.7.2.1. （后缀）逆波兰表达式(Reverse Polish Notation, RPN)
所有的符号都是在要运算数字的后面出现。例如：
正常表达式：9 + (3 - 1) * 3 + 10 / 2
其后缀表达式：9 3 1 - 3 * + 10 2 / +
3.1.7.2.2. 后缀表达式的计算规则
以上面的表达式为例：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
步骤：
- 初始化一个空栈。此栈用来对要运算的数字进出使用
- 后缀表达式中前三个都是数字，所以 9、3、1 依次进栈
- 接下来是 "-"，所以将栈中的 1 出栈作为减数，3 出栈作为被减数，并运算 3 - 1 得到 2，再将 2 进栈
- 接着是数字 3 进栈
- 后面是 "*"，也就意味着栈中的 3、2 依次出栈，2 与 3 相乘，得到 6，并将 6 进栈
- 下面是 "+"，所以栈中的 6、9 依次出栈，9 与 6 相加，得到 15，将 15 进栈
- 接着是 10、2 两数字依次进栈
- 接下来是符号 "/"，因此，栈顶的 2、10 依次出栈，10 与 2 相除，得到 5，将 5 进栈
- 结果是 20 出栈，栈变为空
3.1.7.2.3. 中缀表达式转后缀表达式
我们把平时所用的标准四则运算表达式，叫做中缀表达式。
- 规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先于加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止
- 步骤：
- 初始化一空栈，用来对符号进出栈使用
- 第一个字符是数字 9，输出 9，后面是符号 "+"，进栈
- 第三个字符是 "（"，依然是符号，因其只是左括号，还未配对，故进栈
- 第四个字符是数字 3，输出，总表达式为 9 3，接着是 "-"，进栈
- 接下来是数字 1，输出，总表达式为 9 3 1，后面是符号 "）"，此时，我们需要去匹配之前的 "（"，所以栈顶依次出栈，并输出，直到 "）" 出栈为止。此时左括号上方只有 "-"，因此输出 "-"。总的表达式为 9 3 1 -
- 接着是数字 3，输出，总的表达式为 9 3 1 - 3。紧接着是符号 "*"，因为此时的栈顶符号为 "+" 号，优先级低于 "*"，因此不输出，"*" 进栈
- 之后是符号 "+"，此时当前栈顶元素 "*" 比这个 "+" 的优先级高，因此栈中元素出栈并输出（没有比 "+" 号更低的优先级，所以全部出栈），总输出表达式为 9 3 1 - 3 *
+。然后将当前这个符号 "+" 进栈，也就是说，前面 6 步的栈底的 "+" 是指中缀表达式中开头的 9 后面那个 "+"，而当前一步的 "+" 是指最后的一个 "+" - 紧接着数字 10，输出，总表达式变为 9 3 1 - 3 * + 10。后面是符号 "/"，所以 "/" 进栈
- 最后一个数字 2，输出，总的表达式为 9 3 1 - 3 * + 10 2
- 因为已经到最后，所以将栈中符号全部出栈并输出。最终结果即：9 3 1 - 3 * + 10 2 / +
3.1.7.2.4. 总结
要想让计算机处理具有我们通常的标准（中缀)表达式的能力，最重要的就是两步：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）
3.2. 队列
3.2.1. 定义
队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
3.2.2. 队列的抽象数据类型定义
ADT 队列(Queue)
Data
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
InitQueue(*Q)：初始化操作，建立一个空队列 Q。
DestroyQueue(*Q)：若队列 Q 存在，则销毁它。
ClearQueue(*Q)：将队列 Q 清空。
QueueEmpty(Q)：若队列为空，返回 true，否则返回 false。
GetHead(Q, *e)：若队列 Q 存在且非空，用e返回队列 Q 的队头元素。
EnQueue(*Q, e)：若队列 Q 存在，插入新元素 e 到队列 Q 中并成为队尾元素。
DeQueue(*Q, *e)：删除队列 Q 中队头元素，并用 e 返回其值。
QueueLength(Q)：返回队列 Q 的元素个数。
end ADT
3.2.3. 循环队列的顺序存储结构
3.2.3.2. 定义
把队列头尾相接的顺序存储结构称为循环队列。
3.2.3.3. 队列为空的条件
rear == front
3.2.3.4. 队列为满的条件
(rear + 1) % QueueSize == front
3.2.3.5. 通用的计算队列长度公式
(rear - front + QueueSize) % Queue
3.2.3.6. 循环队列的顺序存储结构
/* QElemType 类型根据实际情况而定，这里假设为 int */
typedef int QElemType;
/* 循环队列的顺序存储结构 */
typedef struct
{
QElemType data[MAX_SIZE];
// 头指针
int front;
// 尾指针，若队列不空，指向队列尾元素的下一个位置
int rear;
} SqQueue;
3.2.3.7. 循环队列的初始化
/* 初始化一个空队列 Q */
Status InitQueue(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return OK;
}
3.2.3.8. 循环队列求队列长度
/* 返回 Q 中的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAX_SIZE) % MAX_SIZE;
}
3.2.3.9. 循环队列的入队列操作
/* 若队列未满，则插入元素 e 为 Q 新的队尾元素 */
Status EnQueue(SqQueue *Q, QElemType e)
{
// 队列满的判断
if ((Q->rear + 1) % MAX_SIZE == Q->front)
{
return ERROR;
}
// 将元素 e 赋值给队尾
Q->data[Q->rear] = e;
// rear 指针向后移一位置，若到最后则转到数组头部
Q->rear = (Q->rear + 1) % MAX_SIZE;
return OK;
}
3.2.3.10. 循环队列的出队列操作
/* 若队列不空，则删除 Q 中队头元素，用 e 返回其值 */
Status DeQueue(SqQueue *Q, QElemType *e)
{
// 队列空的判断
if (Q->front == Q->rear)
{
return ERROR;
}
// 将队头元素赋值给 e
*e = Q->data[Q->front];
// front 指针向后移一位置，若到最后则转到数组头部
Q->front = (Q->front + 1) % MAX_SIZE;
return OK;
}
3.2.4. 队列的链式存储结构
3.2.4.1. 定义
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。
为了操作的方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点。空队列时，front 和 rear 都指向头结点。
3.2.4.2. 链队列的结构
/* QElemType 类型根据实际情况而定，这里假设为 int */
typedef int QElemType;
/* 结点结构 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct
{
// 队头指针
QueuePtr front;
// 队尾指针
QueuePtr rear;
} LinkQueue;
3.2.4.3. 链队列的入队操作
就是在链表尾部插入结点
/* 插入元素 e 为 Q 的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
// 存储分配失败
if (!s)
{
exit(0);
}
s->data = e;
s->next = NULL;
// 把拥有元素 e 新结点 s 赋值给原队尾结点的后继
Q->rear->next = s;
// 把当前的 s 设置为队尾结点，rear 指向s
Q->rear = s;
return OK;
}
3.2.4.4. 链队列的出队操作
- 思路：出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将 rear 指向头结点
- 实现代码：
/* 若队列不空，删除 Q 的队头元素，用 e 返回其值，并返回 OK，否则返回 ERROR */ Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p; // 如果是空队列 if (Q->front == Q->rear) { return ERRROR; } // 将欲删除的对头结点暂存给 p p = Q->front->next; // 将欲删除的队头结点的值赋值给 e *e = p->data; // 将原队头结点后继 p->next 赋值给头结点后继 Q->front->next = p->next; // 若对头是队尾，则删除后将 rear 指向头结点 if (Q->rear == p) { Q->rear = Q->front; } free(p); return OK; }
3.2.4.5. 使用场景
总的来说，在可以确定那个队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。
4. 串
4.1. 定义
串(string)是由零个或多个字符组成的有限序列，又名叫字符串。
零个字符的串称为空串(null string),长度为零。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。
4.2. 对于两个串不相等时的大小判定
给定两个串：s = "a1a2...an"，t = "b1b2...bm"，当满足以下条件之一时，s < t。
n < m，且 ai = bi(i = 1, 2, ..., n)
存在某个 k <= min(m, n)，使得 ai = bi(i = 1, 2, ..., k-1)，ak < bk
4.3. 串的抽象数据类型
ADT 串(string)
Data
串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
StrAssign(T, *chars)：生成一个其值等于字符串常量 chars 的串 T。
StrCopy(T, S)：串 S 存在，由串 S 复制得串 T。
ClearString(S)：串 S 存在，将串清空。
StringEmpty(S)：若串 S 为空，返回 true，否则返回 false。
StrLength(S)：返回串 S 的元素个数，即串的长度。
StrCompare(S, T)：若 S > T，返回值 >0，若 S = T，返回 0，若S < T，返回值 <0。
Concat(T, S1, S2)：用 T 返回由 S1 和 S2 联接而成的新串。
SubString(Sub, S, pos, len)：串 S 存在，1 <= pos <= StrLength(S)，且 0 <= len <= StrLength(S) - pos + 1，用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
Index(S, T, pos)：串 S 和 T 存在，T 是非空串，1 <= pos <= StrLength(S)。若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中第 pos 个字符之后第一次出现的位置，否则返回 0。
Replace(S, T, V)：串 S、T 和 V 存在，T 是非空串。用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串。
StrInsert(S, pos, T)：串 S 和 T 存在，1 <= pos <= StrLength(S) + 1。在串 S 的第 pos 个字符之前插入串 T。
StrDelete(S, pos, len)：串 S 存在。1 <= pos <= StrLength(S) - len + 1。从串 S 中删除第 pos 个字符起长度为 len 的子串。
end ADT
4.4. Index 的实现算法(暴力匹配)
/* 若 T 为非空串。若主串 S 中第 pos 个字符之后存在与 T 相等的子串，则返回第一个这样的子串在 S 中的位置，否则返回 0 */
int Index(String S, String T, int pos)
{
int n, m , i;
String sub;
if (pos > 0)
{
// 得到主串 S 的长度
n = StrLength(S);
// 得到子串 T 的长度
m = StrLength(T);
i = pos;
while (i <= n - m + 1)
{
// 取主串第 i 个位置长度与 T 相等的子串给 sub
SubString(sub, S, i, m);
// 如果两串不相等
if (StrCompare(sub, T) != 0)
{
i++;
}
// 如果两串相等，则返回i值
else
{
return i;
}
}
}
// 若无子串与 T 相等，返回 0
return 0;
}
4.5. 串的顺序存储结构
直接看实现代码。
4.6. 串的链式存储结构
串的链式存储结构相对顺序存储结构来说不够灵活，性能也不如顺序存储结构好。
4.7. 朴素的模式匹配算法
前面已经用串的其他操作实现了模式匹配的算法 Index。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。
注意，我们假设主串 S 和压迫匹配的子串 T 的长度存在 S[0] 和 T[0] 中。实现代码如下：
/* 返回子串 T 在主串 S 中第 pos 个字符之后的位置。若不存在，则函数返回值为 0 */
/* T 非空，1 <= pos <= StrLength(S)。 */
int Index(String S, String T, int pos)
{
// i 用于主串 S 中当前位置下标，若 pos 不为 1，则从 pos 位置开始匹配
int i = pos;
// j 用于子串T中当前位置的下标值
int j = 1;
// 若 i 小于等于 S 长度且 j 小于等于 T 的长度时循环
while (i <= S[0] && j <= T[0])
{
// 两字母相等则继续
if (S[i] == T[i])
{
i++;
j++;
}
// 指针后退重新开始匹配
else
{
// i 退回到上次匹配首位的下一位
i = i - j + 2;
// j 退回到子串 T 的首位
j = 1;
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
4.8. KMP 模式匹配算法
/* 通过计算返回子串 T 的 next 数组。 */
void get_next(String T, int *next)
{
int i, j;
i = 1;
j = 0;
// 注意：next[0] 不存任何元素，当然也可以用来存长度
next[1] = 0;
// 此处 T[0] 表示串 T 的长度
while (i < T[0])
{
// T[i] 表示后缀的单个字符
// T[j] 表示前缀的单个字符
if (j == 0 || T[i] == T[j])
{
i++;
j++;
next[i] = j;
}
else
{
// 若字符不相同，则 j 值回溯
j = next[j];
}
}
}
/* 返回子串 T 在主串 S 中第 pos 个字符之后的位置。若不存在，则函数返回值为 0。 */
/* T 非空，1 <= pos <= StrLength(S) */
int Index_KMP(String S, String T, int pos)
{
// i 为主串 S 当前位置下标值，若 pos 不为 1，则从 pos 位置开始匹配
int i = pos;
// j 用于子串T中当前位置下标值
int j = 1;
// 定义一个 next 数组
int next[255];
// 对T作分析，得到next数组
get_next(T, next);
// 若 i 小于 S 的长度且 j 小于 T 的长度时，循环继续
while (i <= S[0] && j <= T[0])
{
// 两字母相等则继续判断，与朴素算法相比增加了一个 j==0 的判断
if (j == 0 || S[i] == T[j])
{
i++;
j++;
}
// 不相等则指针后退重新开始匹配
else
{
// j 退回到合适的位置，i 值不变
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
注意：KMP 算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出他的优势，否则两者差异并不明显。
4.9. KMP模式匹配算法改进
将 get_next 函数进行改良，使用 nextval 来取代 next。
改进代码：
/* 求模式串 T 的 next 函数修正值并存入数组 nextval */
void get_nextval(String T, int *nextval)
{
int i, j;
i = 1;
j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])
{
i++;
j++;
// 若当前字符与前缀字符不同，则当前的 j 为 nextval 在 i 位置的值
if (T[i] != T[j])
{
nextval[i] = j;
}
// 如果与前缀字符相同，则将前缀字符的 nextval 值赋给 nextval 在 i 位置的值
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}
}
实际匹配算法就只需要将 get_next(T, next); 改为 get_nextval(T, next); 即可。
总结改进过的 KMP 算法，它是在计算出 next 值的同时，如果 a 位字符与它的 next 值指向的 b 位字符相等，
则将该 a 位的 nextval 就指向 b 位的 nextval 值，如果不等，则该 a 位的 nextval 值就是它自己 a 位的 next 的值。
5. 树
5.1. 定义
树(Tree)是 n(n>=0) 个结点的有限集。n = 0 时称为空树。在任意一棵非空树中：
- 有且仅有一个特定的称为根(Root)的结点
- 当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集 T1、T2、...、Tm，其余每一个集合本身又是一棵树，并且称为根的子树(SubTree)
注意：
- 当 n > 0 时根节点是唯一的，不可能存在多个根节点
- m > 0 时，子树的个数没有限制，但它们一定是互不相交的
5.2. 结点、度
树的结点包含一个数据元素及若干指向其子树的分支
结点拥有的子树数称为结点的度(Degree)
度为 0 的结点称为叶结点(Leaf)或终端结点；度不为 0 的结点称为非终端结点或分支结点
除根节点外，分支结点也称为内部结点
树的度是树内各节点的度的最大值
5.3. 结点间关系
结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)
同一个双亲的孩子之间互称兄弟(Sibling)
结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙
5.4. 树的其他相关概念
- 结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某一结点在第 l 层，则其子树的根就在第 l+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度
- 如果将树种结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树
- 森林(Forest)是 m(m>=0) 棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林
5.5. 线性结构和树结构的区别
- 线性结构：
- 第一个数据元素：无前驱
- 最后一个数据元素：无后继
- 中间元素：一个前驱一个后继
- 树结构：
- 根节点：无双亲，唯一
- 叶结点：无孩子，可以多个
- 中间结点：一个双亲多个孩子
5.6. 树的抽象数据类型
ADT 树(tree)
Data
树是由一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
Operation
InitTree(*T)：构造空树 T。
DestroyTree(*T)：销毁树 T。
CreateTree(*T, definnition)：按 definition 中给出树的定义来构造树。
ClearTree(*T)：若树 T 存在，则将树 T 清为空树。
TreeEmpty(T)：若 T 为空树，返回 true，否则返回 false。
TreeDepth(T)：返回 T 的深度。
Root(T)：返回 T 的根节点。
Value(T, cur_e)：cur_e 是树 T 中的一个结点，返回此结点的值。
Assign(T, cur_e, value)：给树 T 的结点 cur_e 赋值为 value。
Parent(T, cur_e)：若 cur_e 是树 T 的非根节点，则返回它的双亲，否则返回空。
LeftChild(T, cur_e)：若 cur_e 是树 T 的非叶结点，则返回它的最左孩子，否则返回空。
RightSibling(T, cur_e)：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。
InsertChild(*T, *p, i, c)：其中 p 指向树 T 的某个结点，i 为所指结点 p 的度加上 1，非空树 c 与 T 不相交，操作结果为插入 c 为树 T 中 p 指结点的第 i 棵子树。
DeleteChild(*T, *p, i)：其中 p 指向树 T 的某个结点，i 为所指结点 p 的度，操作结果为删除 T 中 p 所指结点的第 i 棵子树。
end ADT
5.7. 树的存储结构
利用顺序存储结构和链式存储结构的特点实现树的存储结构表示。
三种表示方法：双亲表示法、孩子表示法、孩子兄弟表示法。
5.8. 双亲表示法
假设以一组连续空间存储树的结点，同时在每个结点这种，附设一个指示器指示其双亲结点在链表中的位置。
其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。
/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
// 树结点的数据类型，目前暂定为为整型
typedef int TElemType;
/* 结点结构 */
typedef struct PTNode
{
// 结点数据
TElemType data;
// 双亲位置
int parent;
} PTNode;
/* 树结构 */
typedef struct
{
// 结点数组
PTNode nodes[MAX_TREE_SIZE];
// 根的位置
int r;
// 结点数
int n;
} PTree;
由于根节点是没有双亲的，所以约定根节点的位置域设置为 -1，也就意味着所有的结点都存有它双亲的位置。
5.9. 孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。
然后 n 个头指针又构成一个线性表，采用顺序存储结构，存放进一个一维数组中。
因此设计两种结点结构，一个是孩子链表的孩子结点，其中 data 是数据域，用来存储某个结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下一个孩子结点的指针。
另一个是表头数组的表头结点，其中 data 是数据域，存储某结点的数据信息。firstchild 是头指针域，存储该结点的孩子链表的头指针。
/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
/* 孩子结点 */
typedef struct CTNode
{
int child;
struct CTNode *next;
} *ChildPtr;
/* 表头结构 */
typedef struct
{
TElemType data;
ChildPtr firstchild;
} STBox;
/* 树结构 */
typedef struct
{
// 结点数组
CTBox nodes[MAX_TREE_SIZE];
// 根的位置
int r;
// 结点数
int n;
} CTree;
5.10. 孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
其中 data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。
/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild;
struct CSNode *rightsib;
} CSNode, *CSTree;
这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。这样就可以充分利用二叉树的特性和算法来处理这棵树了。
5.11. 二叉树
5.11.1. 定义
二叉树(Binary Tree)是 n(n>=0) 个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
5.11.2. 特点
- 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树也是可以的
- 左子树和右子树是由顺序的，次序不能颠倒
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
5.11.3. 五种基本形态
- 空二叉树
- 只有一个根节点
- 根节点只有左子树
- 根节点只有右子树
- 根节点既有左子树又有右子树
5.11.4. 特殊二叉树
5.11.4.1. 斜树
顾名思义，斜树一定要是斜的。
所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
斜树很明显的特点就是每一层只有一个结点，结点的个数与二叉树的深度相同。线性表结构其实就可以理解为一种极其特殊的树的表现形式。
5.11.4.2. 满二叉树
5.11.4.2.1. 定义
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
5.11.4.2.2. 特点
- 叶子只能出现在最下一层。出现在其他层就不可能达成平衡
- 非叶子结点的度一定是 2
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多
5.11.4.3. 完全二叉树
5.11.4.3.1 定义
对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i(1<=i<=n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树这种位置完全相同，则这棵二叉树称为完全二叉树。
满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。
5.11.4.3.2. 特点
- 叶子结点只能出现在最下两层
- 最下层的叶子一定集中在左部连续位置
- 倒数二层，若有叶子结点，一定都在右部连续位置
- 如果结点度为 1，则该结点只有左孩子，即不存在只有右子树的情况
- 同样结点数的二叉树，完全二叉树的深度最小
5.11.4.3.3. 判断某二叉树是否是完全二叉树的方法
就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空挡，则说明不是完全二叉树，否则就是。
5.11.5. 二叉树性质(需要理解并记住)
- 在二叉树的第 i 层至多有
2^(i-1)个结点(i>=1) - 深度为 k 的二叉树至多有
2^k-1个结点(k>=1) - 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1
- 具有 n 个结点的完全二叉树的深度为 [log2n（这里是log以2为底n的对数）]+1，这里的 [x] 表示不大于x的最大整数
- 如果对一棵有n个结点的完全二叉树（其深度为 [log2n]+1 ）的结点按层序编号（从第 1 层到第 [log2n]+1 层，每层从左到右），对任一结点 i(1<=i<=n) 有：
- 如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点 [i/2]
- 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i
- 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i
5.11.6. 二叉树的顺序存储结构
一般只用于完全二叉树。
5.11.7. 二叉链表
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，称这样的链表叫做二叉链表。
其中 data 是数据域，lchild 和 rchild 都是指针域，分别存放指向左孩子和右孩子的指针。
/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef struct BiTNode
{
// 结点数据
TElemType data;
// 左孩子指针
struct BiTNode *lchild;
// 右孩子指针
struct BiTNode *rchild;
} BiTNode, *BiTree;
如果有需要还可以增加一个指向其双亲的指针域，那样就称为三叉链表。
5.11.8. 遍历二叉树
5.11.8.1. 定义
二叉树的遍历(traversing binary tree)是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
5.11.8.2. 遍历方法
- 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
- 中序遍历：规则是若二叉树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树
- 后续遍历：规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点
- 层序遍历：规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问
5.11.8.3. 前序遍历算法
/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
// 显示结点数据，可以更改为其他对结点的操作
printf("%c", T->data);
// 再前序遍历左子树
PreOrderTraverse(T->lchild);
// 最后前序遍历右子树
PreOrderTraverse(T->rchild);
}
5.11.8.4. 中序遍历算法
/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
// 先中序遍历左子树
InOrderTraverse(T->lchild);
// 显示结点数据，可以更改为其他对结点的操作
printf("%c", T->data);
// 最后中序遍历右子树
InOrderTraverse(T->rchild);
}
5.11.8.5. 后序遍历算法
/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
// 先后序遍历左子树
PostOrderTraverse(T->lchild);
// 然后后后序遍历右子树
PostOrderTraverse(T->rchild);
// 显示结点数据，可以更改为其他对结点的操作
printf("%c", T->data);
}
已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
5.11.9. 二叉树的建立
将二叉树的每个结点的空指针引出一个虚结点，其值为一个特定值，比如 "#"。我们称这种处理后的二叉树为原二叉树的扩展二叉树。
这样扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。
/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树，构造二叉链表表示二叉树 T */
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c", &ch);
if (ch == '#')
{
*T = NULL;
}
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
{
printf("内存分配失败。\n");
exit(0);
}
// 生成根节点
(*T)->data = ch;
// 构造左子树
CreateBiTree(&(*T)->lchild);
// 构造右子树
CreateBiTree(&(*T)->rchild);
}
}
当然也可以用中序或者后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交换一下。另外，输入的字符也要做相应的更改。
5.11.10. 线索二叉树
5.11.10.1. 定义
利用那些空的指针域来存放指向结点在某种遍历次序下的前驱和后继结点的地址。
把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。
将所有空指针域中的 rchild 改为指向当前结点的后继。
将所有空指针域中的 lchild 改为指向当前结点的前驱。
其实线索二叉树等于是把一棵二叉树转变成了一个双向链表。
5.11.10.2. 线索化
对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。
为了知道某一结点的 lchild 和 rchild 是指向它们的左右孩子还是指向前驱或者后继呢。需要再增设两个标志域 LTag 和 rTag。
其中：
- LTag 为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱
- rTag 为 0 时指向该结点的右孩子，为 1 时指向该结点的后继
5.11.8.7.3. 线索二叉树的结构实现
/* 二叉树的二叉线索存储结构定义 */
// Link==0，表示指向左右孩子指针
// Thread==1，表示指向前驱或后继的线索
typedef enum {Link, Thread} PointerTag;
typedef struct BiThrNode
{
// 结点数据
TElemType data;
// 左右孩子指针
struct BiThrNode *lchild, *rchild;
// 左右标志
PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;
由于前驱和后继的信息只有在遍历该二叉树的时候才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
5.11.8.7.4. 中序遍历线索化
注意：这段代码其实是不完整的，运行会因为 pre 未初始化数据会报错。正确的应该是将树的头结点赋值给 pre。
详细看实现代码。
// 全局变量，始终指向刚刚访问过的结点
BiThrTree pre;
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
if (p)
{
// 递归左子树线索化
InThreading(p->lchild);
// 没有左孩子
if (!p->lchild)
{
// 前驱线索
p->LTag = Thread;
// 左孩子指针指向前驱
p->lchild = pre;
}
// 前驱没有右孩子
if (!pre->rchild)
{
// 后继线索
pre->RTag = Thread;
// 前驱右孩子指针指向后继(当前结点p)
pre->rchild = p;
}
// 保持 pre 指向 p 的前驱
pre = p;
// 递归右子树线索化
InThreading(p->rchild);
}
}
和双向链表一样，在二叉树线索链表上添加一个头结点，并令其 lchild 域的指针指向二叉树的根节点，其 rchild 域的指针指向中序遍历时访问的最后一个结点。
令二叉树的中序序列中的第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。
这样既可以从第一个结点其顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
5.11.8.7.5. 遍历的代码实现
/* T 指向头结点，头结点左链 lchild 指向根节点，头结点右链 rchild 指向中序遍历的最后一个结点。 */
/* 中序遍历二叉线索链表表示的二叉树T */
int InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
// p 指向根结点
p = T->lchild;
// 空树或遍历结束时，p==T
while (p != T)
{
// 当 LTag==0 时循环到中序序列的第一个结点
while (p->LTag == Link)
{
p = p->lchild;
}
// 显示结点数据，可以更改为其他对结点的操作
printf("%c", p->data);
while (p->RTag == Thread && p->rchild != T)
{
p = p->rchild;
printf("%c", p->data);
}
// p 进至其右子树根
p = p->rchild;
}
return OK;
}
从代码可以看出，等于时一个链表的扫描，所以时间复杂度为 O(n)。
在实际问题中，如果所用的二叉树需要经常遍历或者查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉树的存储结构就是非常不错的选择。
5.11.11. 树、森林与二叉树的转换
5.11.11.1. 将树转换为二叉树
- 加线。在所有兄弟结点之间加一条连线
- 去线。对树中每个结点，只保留与它第一个孩子结点的连线，删除它与其他孩子结点之间的连线
- 层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子
5.11.11.2. 森林转换为二叉树
森林是由若干棵树组成的，完全可以理解为，森林中每一棵树都是兄弟，可以按照兄弟的处理办法来操作：
- 把每棵树转换为二叉树
- 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子，用线连起来，当所有二叉树连接起来后就得到了由森林转换来的二叉树
5.11.11.3. 二叉树转换为树
就是树转换为二叉树的逆过程：
- 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点...，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来
- 去线。删除原二叉树中所有结点与其右孩子结点的连线
- 层次调整。使之结构层次分明
5.11.11.4. 二叉树转换为森林
判断一棵二叉树能够转换成一棵树还是森林，标准很简单，就是只要看这颗二叉树的根节点有没有右孩子，有就是森林，没有就是一棵树。步骤如下：
- 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则重复上面的过程，直到把所有右孩子连线都删除为止，得到分离的二叉树
- 再将每棵分离后的二叉树转换为树即可
5.11.12. 树与森林的遍历
5.11.12.1. 树的遍历
分为两种：
- 先根遍历，即先访问树的根节点，然后依次先根遍历根的每棵子树
- 后根遍历：即先依次后根遍历每棵子树，然后再访问根节点
5.11.12.2. 森林的遍历
分为两种：
- 前序遍历：先访问森林中第一棵树的根节点，然后再依次先根遍历根的每棵子树，再依次用同样的方法遍历除去第一棵树的剩余树构成的森林
- 后序遍历：先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根节点，再依次同样方式遍历除去第一棵树的剩余树构成的森林
5.11.12.3. 结论
森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。
5.11.13. 赫夫曼树
5.11.13.1. 路径长度
赫夫曼大叔说，从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。
5.11.13.2. 树的路径长度
就是从树根到每一结点的路径长度之和。
5.11.13.3. 带权路径长度
如果考虑带权的结点，结点的带权的路径长度就是从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。
5.11.13.4. 赫夫曼数定义
将带权路径长度 WPL 最小的二叉树就称作赫夫曼树（也叫最优二叉树）。
5.11.13.5. 构造赫夫曼树的算法描述
- 根据给定的 n 个权值 {w1,w2,...,wn} 构成 n 棵二叉树的集合 F={T1,T2,...,Tn}，其中每棵二叉树 Ti 中只有一个带权为 wi 根节点，其左右子树均为空
- 在 F 中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和
- 在 F 中删除这两棵树，同时将新得到的二叉树加入F中
- 重复步骤 2 和步骤 3，直到 F 只含一棵树为止。这棵树便是赫夫曼树
5.11.13.6. 赫夫曼编码
一般地，设需要编码的字符集为 {d1,d2,...,dn}，
各个字符在电文中出现的次数或频率集合为 {w1,w2,w3...,wn} ，以 d1,d2,...,dn 作为叶子结点，
以 w1,w2,...,wn 作为相应叶子结点的权值来构造一棵赫夫曼树。
规定赫夫曼树的左分支代表 0，右分支代表 1，
则从根节点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是赫夫曼编码。
6. 图
6.1. 定义
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
6.2. 关于图的定义需要注意的地方
- 线性表中我们把数据元素叫元素，树中将数据元素叫结点，载图中数据元素，我们则称之为顶点(Vertex)
- 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。而在图结构中，不允许没有顶点。在定义中，若 V 是顶点的集合，则强调了顶点集合 V 有穷非空
- 线性表中,相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的
6.3. 各种图的定义
- 无向边：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边(Edge)，用无序偶对 (vi, vj) 来表示（由于无序反过来写也行）。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirevted
graphs) - 有向边：若从顶点 vi 到 vj 的边有方向，则称这条边为有向边，也成为弧(Arc)。用有序偶对 <vi, vj> 来表示，vi 称为弧尾(Tail)，vj 称为弧头(Head)
。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图(Directed graphs)
无向边用小括号表示，有向边用尖括号表示。
- 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。（接下来学习讨论的都是简单图）
- 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有 n 个顶点的无向完全图有 n*(n-1)/2 条边
- 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有 n 个顶点的有向完全图有 n*(n-1) 条边
因此可以得出结论：对于具有 n 个顶点和 e 条边数的图，无向图 0 <= e <= n*(n-1)/2，有向图 0 <= e <= n*(n-1)。
- 有很少条边或弧的图称为稀疏图，反之称为稠密图。这里的稀疏和稠密是模糊的概念，都是相对而言的
- 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)
- 假设有两个图 G=(V, {E}) 和 G'=(V', {E'})，如果 V' 包含于于 V 且 E' 包含于 E，则称 G' 为 G 的子图(Subgraph)
6.4. 图的顶点与边之间的关系
- 对于无向图 G=(V, {E})，如果边 (v, v') 属于 E，则称顶点 v 和 v' 互为邻接点(Adjacent)，即 v 和 v' 相邻接。边 (v, v') 依附(incident)于顶点 v 和 v'，或者说 (v,
v') 与顶点 v 和 v' 相关联。顶点 v 的度(Degree)是和 v 相关联的边的数目，记为 TD(v)
观察可得出结论：无向图中的边数 e 其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。
- 对于有向图 G=(V, {E})，如果弧 <v, v'> 属于 E，则称顶点 v 邻接到顶点 v'，顶点 v' 邻接自顶点 v。弧 <v, v'> 和顶点 v, v' 相关连。以顶点 v 为头的弧的数目称为 v 的入度(
InDegree)，记为 ID(v)；以 v 为尾的弧的数目称为 v 的出度(OutDegree)，记为 OD(v)；顶点 v 的度尾 TD(v) = ID(v) + OD(v)
结论：有向图中的边数e等于各顶点的出度和，也等于各顶点的入度和。
6.5. 环、简单路径、简单环
- 路径的长度是路径上的边或弧的数目
- 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)
- 序列中顶点不重复出现的路径称为简单路径
- 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称之为简单回路或简单环
6.6. 连通图
在无向图 G 中，如果从顶点 v 到顶点 v' 有路径，则称 v 和 v' 是连通的。如果对于图中任意两个顶点 vi、vj 属于 E，vi 和 vj 都是连通的，则称 G 是连通图(Connected Graph)。
无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调：
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
在有向图G中，如果对于每一对 vi、vj 属于 V，vi≠vj，从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。（注意抄写这个概念时教材的图是有错的，220
页图 1 和图 2 的 AB 之间的箭头指向画反了）
6.7. 连通图的生成树
所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，但只有足以构成一颗树的 n-1 条边。
6.8. 有向树
如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。
所谓入度为 0 其实就像相当于树中的根结点，其余顶点入度为 1 就是说树的非根结点的双亲只有一个。
一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。
6.9. 图的抽象数据类型
ADT 图(Graph)
Data
顶点的有穷非空集合和边的集合
Operation
CreateGraph(*G, V, VR)：按照顶点集 V 和边弧集 VR 的定义构造图 G。
DestroyGraph(*G)：图 G 存在则销毁。
LocateVex(G, u)：若 G 中存在顶点 u 则返回在图中的位置。
GetVex(G, v)：返回图 G 中顶点 v 的值。
PutVex(G, v, value)：将图 G 中顶点 v 赋值 value。
FirstAdjVex(G, *v)：返回顶点 v 的一个邻接顶点，若顶点在 G 中无邻接顶点返回空。
NextAdjVex(G, v, *w)：返回顶点 v 相对于顶点 w 的下一个邻接顶点，若 w 是 v 的最后一个邻接点则返回“空”。
InsertVex(*G, v)：在图 G 中增添新顶点 v。
DeleteVex(*G, v)：删除图 G 中顶点 v 及其相关的弧。
InsertArc(*G, v, w)：在图 G 中增添弧 <v, w>，若图 G 是无向图，还需要增添对称弧 <w, v>。
DeleteArc(*G, v, w)：在图 G 中删除弧 <v, w>，若 G 是无向图，泽海删除对称弧 <w, v>。
DFSTraverse(G)：对图 G 中进行深度优先遍历，在遍历过程中对每个顶点调用。
HFSTraverse(G)：对图 G 中进行广度优先遍历，在遍历过程中对每个顶点调用。
end ADT
6.10. 图的存储结构
6.10.1. 邻接矩阵及相关概念
图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息
设图 G 有 n 个顶点，则邻接矩阵是一个 n*n 的方阵，定义为：
arc[i][j] = 1(若 (vi, vj)∈E 或 <vi, vj>∈E) 或 0 （反之）。无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足 a(ij)=a(ji)，(0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的
有了这个矩阵:
- 要判定任意两顶点是否有边就很容易了
- 要知道某个顶点的度，其实就是这个顶点 vi 在邻接矩阵第 i 行（或第 i 列的元素之和）
- 求顶点 vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍，arc[i][j] 为 1 就是邻接点
有向图讲究入度与出度:
- 顶点 vi 的入度正好是第 vi 列各数之和。顶点 vi 的出度即第 vi 行的各数之和
- 判断顶点 vi 到 vj 是否存在弧，只需要查找矩阵中 arc[i][j] 是否为 1 即可
- 要求 vi 的所有邻接点就是将矩阵第 i 行元素扫描一遍，查找 arc[i][j] 为 1 的顶点
网（每条边上带有权的图叫做网）的处理：
设图 G 是网图，有 n 个顶点，则邻接矩阵是一个 n*n 的方阵，定义为：
arc[i][j] = W(ij)，若 (vi, vj)∈E 或 <vi, vj>∈E 或 0，若 i = j 或 ∞，反之
这里
W(ij)表示(vi, vj)或<vi, vj>上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。图的邻接矩阵存储的结构：
/* 顶点类型应有用户定义 */ typedef char VertexType; /* 边上的权值类型应由用户定义 */ typedef int EdgeType; /* 最大顶点数，应由用户定义 */ #define MAX_VEX 100 /* 用65535来表示∞ */ #define INFINITY 65535 typedef struct { /* 顶点表 */ VerTexType vexs[MAX_VEX]; /* 邻接矩阵，可看作边表 */ EdgeType arc[MAX_VEX][MAX_VEX]; /* 图中当前的顶点数和边数 */ int numVertexex, numEdges; } MGraph;
有了结构定义，构造一个图其实就是给顶点表和边表输入数据的过程。
下面是无向网图的构建代码。
/* 建立无向网图的邻接矩阵表示 */ void CreateMGraph(MGraph *G) { int i, j, k, w; printf("输入顶点数和边数：\n"); // 输入顶点数和边数 scanf("%d,%d", &G->numVertexes, &G->numEdges); for (i = 0; i < G->numVertexes; i++) { scanf("%d", &G->vexs[i]); } for (i = 0; i < G->numVertexes; i++) { for (j = 0; j < G->numVertexes; j++) { // 邻接矩阵初始化 G->arc[i][j] = INFINITY; } } // 读入 numEdges 条边，建立邻接矩阵 for (k = 0; k < G->numEdges; k++) { printf("输入边 (vi, vj) 的下标i，下标 j 和权 w：\n"); // 输入边 (vi, vj) 上的权w scanf("%d,%d,%d", &i, &j, &w); G->arc[i][j] = w; // 因为是无向图，矩阵对称 G->arc[j][i] = G->arc[i][j]; } }
从代码中可以得到，n 个顶点和 e 条边的无向网图的创建，时间复杂度为 O(n+n²+e)，其中对邻接矩阵 G.arc 的初始化耗费了 O(n²) 的时间。
6.10.2. 邻接表及相关概念
邻接矩阵对于边数相对顶点较少图，这种结构就存在对存储空间的极大浪费
类似于树的孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，这同样适用于图的存储。把这种数组与链表相结合的存储方法称为邻接表(Adjacency List)
邻接表的处理方法：
- 图中顶点用一个一维数组存储，当然，顶点也可以用单链表存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息
- 图中每个顶点 vi 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则成为顶点 vi 作为弧尾的出边表
顶点表中的各个结点由 data 和 firstedge 两个域表示，data 是数据域，存储顶点的信息，firstedge 是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由 adjvex 和 next
两个域组成。adjvex 是邻接点域，存储某结点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针根据邻接表的结构:
- 要想知道某个顶点的度，就去查找这个顶点的边表中结点的个数
- 若要判断 vi 到 vj 是否存在边，只需要测试顶点 vi 边表中的 adjvex 是否存在结点 vj 的下标 j 就行了
- 若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的 adjvex 域对应的顶点就是邻接点
对于有向图，邻接表结构是类似的。由于有向图有方向，我们是以顶点为弧尾来存储边表的，这样很容易得到每个顶点的出度。但有时为了方便确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接矩阵，即对每个顶点 vi 都建立一个链接为
vi 为弧头的表。（比如 a->b，那么 a 是弧尾，b 是弧头，参考上方有向边中的定义）对于有权值得网图，可以在边表结点定义中再增加一个 weight 的数据域，存储权值信息即可
关于结点定义的代码
/* 顶点类型应由用户定义 */ typedef char VertexType; /* 边上的权值类型应由用户定义 */ typedef int EdgeType; /* 边表结点 */ typedef struct EdgeNode { /* 邻接点域，存储该顶点对应下的下标 */ int adjvex; /* 用于存储权值，对于非网图可以不需要 */ EdgeType weight; /* 链域，指向下一个邻接点 */ struct EdgeNode *next; } EdgeNode; /* 顶点表结点 */ typedef struct VertexNode { /* 顶点域，存储顶点信息 */ VertexType data; /* 边表头指针 */ EdgeNode *firstedge; } VertexNode, AdjList[MAX_VEX]; /* 邻接表结构 */ typedef struct { /* 邻接表 */ AdjList adjList; /* 图中当前顶点数和边数 */ int numVertexes, numEdges; } GraphAdjList;邻接表的创建代码
/* 建立图的邻接表结构 */ void CreateALGraph(GraphAdjList *G) { int i, j, k; EdgeNode *e; printf("输入顶点数和边数：\n"); // 输入顶点数和边数 scanf("%d,%d", &G->numVertexes, &G->numEdges); // 输入顶点信息，建立顶点表 for (i = 0; i < G->numVertexes; i++) { // 输入顶点信息 scanf("%d", &G->adjList[i].data); // 将边表置为空表 G->adjList[i].firstedge = NULL; } // 建立边表 for (k = 0; k < G->numEdges; k++) { printf("输入边(vi, vj)上的顶点序号：\n"); scanf("%d,%d", &i, &j); // **************** // 以下代码采用头插法 // **************** // 向内存申请空间，生成边表结点 e = (EdgeNode *) malloc(sizeof(EdgeNode)); // 邻接序号为j e->adjvex = j; // 将 e 指针指向当前顶点指向的结点 e->next = G->adjList[i].firstedge; // 将当前顶点的指针指向e G->adjList[i].firstedge = e; // 向内存申请空间，生成边表结点 e = (EdgeNode *) malloc(sizeof(EdgeNode)); // 邻接序号为i e->adjvex = i; // 将 e 指针指向当前顶点指向的结点 e->next = G->adjList[j].firstedge; // 将当前顶点的指针指向 e G->adjList[j].firstedge = e; } }
由于对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对 i 和 j 分别进行了插入。本算法的时间复杂度，对于 n 个顶点 e 条边来说，是 O(n+e)。
十字链表：对于有向图来说，邻接表是有缺陷的，关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况，于是将邻接表与逆邻接表结合起来组成了十字链表(Orthogonal List)
- 重新定义顶点表结点结构：其中 firstin 表示入边表头指针，指向该顶点的入边表中第一个结点，firstout 表示出边表头指针，指向该顶点的出边表战中的第一个结点
- 重新定义边表结点结构：其中 tailvex 是指弧起点在顶点表的下标，headvex 是指弧重点在定点表中的下标，headlink 是指入边表指针域，指向终点相同的下一条边，taillink
是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个 weight 域来存储权值
邻接多重表：当更多的关注于边的操作时可以用这个结构
- 重新定义边表结点结构：其中 ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构
边集数组：边集数组是由两个一维数组构成。一个存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)
组成。这种结构更适合对边依次进行处理的操作，而不适合对顶点相关的操作。相关介绍在后面的克鲁苏卡尔(Kruskal)算法中介绍
6.10.3. 图的遍历
6.10.3.1. 定义
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。
6.10.3.2. 深度优先遍历(Depth_First_Search)
也有称为深度优先搜索，简称为 DFS。它从图中某个顶点 v 出发，访问此顶点，然后从 v 未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到。
事实上，我们这里讲到的是连通图，对于非连通图，只需要对他的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，
若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
6.10.3.2.1. 邻接矩阵的深度优先遍历算法
/* Boolean是布尔类型，其值是 TRUE 或 FALSE */
typedef int Boolean;
// 访问标志的数组
Boolean visited[MAX];
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
// 打印顶点，也可以其他操作
printf("%c ", G.vexs[i]);
for (j = 0; j < G.numVertexes; j++)
{
if (G.arc[i][j] == 1 && !visited[j])
{
// 对未访问的邻接顶点递归调用
DFS(G, j);
}
}
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
int i;
for (i = 0; i < G.numVertexes; i++)
{
// 初始所有顶点状态都是未访问过状态
visited[i] = FALSE;
}
for (i = 0; i < G.numVertexes; i++)
{
// 对未访问过的顶点调用 DFS，若是连通图，只会执行一次
if (!visited(i))
{
DFS(G, i);
}
}
}
6.10.3.2.2. 邻接表的深度遍历算法
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c ", GL->adjList[i].data);
p = GL->adjList[i].firstedge;
while (p)
{
if (!visited[p->adjvex])
{
DFS(GL, p->adjvex);
}
p = p->next;
}
}
/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
int i;
for (i = 0; i < GL->numVertexes; i++)
{
viisted[i] = FALSE;
}
for (i = 0; i < GL->numVertexes; i++)
{
// 对未访问过的顶点调用 DFS，若是连通图，只会执行一次
if (!visited[i])
{
DFS(GL, i);
}
}
}
比较上述两种结构，邻接矩阵要查找每个顶点的邻接点需要访问矩阵中所有元素，需要 O(n²) 时间，邻接表所需时间取决于顶点和边的数量，所以是 O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行的判断，算法上没有任何变化，完全可以通用的。
6.10.3.3. 广度优先遍历(Breadth_First_Search)
又称为广度优先搜索，简称 BFS。
如果说图的深度优先遍历类似于树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
6.10.3.3.1. 邻接矩阵结构的广度优先遍历算法
/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for (i = 0; i < G.numVertexes; i++)
{
visited[i] = FALSE;
}
// 初始化以辅助用的队列
InitQueue(&Q);
// 对每一个顶点做循环
for (i = 0; i < G.numVertexes; i++)
{
// 若是未访问过就处理
if (!visited[i])
{
// 设置当前顶点访问过
visited[i] = TRUE;
// 打印顶点，也可以其他操作
printf("%c ", G.vexes[i]);
// 将此顶点入队列
EnQueue(&Q, i);
// 若当前队列不为空
while (!QueueEmpty(Q))
{
// 将队中元素出队列，赋值给i
DeQueue(&Q, &i);
for (j = 0; j < G.numVertexes; j++)
{
// 判断其他顶点若与当前顶点存在边且未访问过
if (G.arc[i][j] == 1 && !visited[j])
{
// 将找到的此顶点标记为已访问
vivited[j] = TRUE;
// 打印顶点
printf("%c ", G.vexes[j]);
// 将找到的此顶点入队列
EnQueue(&Q, j);
}
}
}
}
}
}
6.10.3.3.2. 邻接表的广度优先遍历算法
/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for (i = 0; i < GL->numVertexes; i++)
{
visited[i] = FALSE;
}
INitQueue(&Q);
for (i = 0; i < GL->numVertexes; i++)
{
if (!visited[i])
{
visited[i] = TRUE;
printf("%c ", GL->adjList[i].data);
EnQueue(&Q, i);
while (!QueueEmpty(Q))
{
DeQueue(&Q, &i);
// 找到当前顶点边表链表头指针
p = GL->adjList[i].firstedge;
while (p)
{
// 若此顶点未被访问
if (!visited[p->adjvex])
{
visited[p->adjvex] = TRUE;
printf("%c ", GL->adjList[p->adjvex].data);
// 将此顶点入队列
EnQueue(&Q, p->adjvex);
}
// 指针指向下一个邻接点
p = p->next;
}
}
}
}
}
6.10.3.4. 两种遍历方法的区别
DFS 和 BFS 的时间复杂度是一样的，不同之处仅在于对顶点访问的顺序不同。
深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。
6.10.3.5. 最小生成树
6.10.3.5.1. 定义
把构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。
找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。
6.10.3.6.1. 普里姆(Prim)算法（数学描述看百科）
/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
// 保存相关顶点下标
int adjvex[MAX_VEX];
// 保存相关顶点间边的权值
int lowcost[MAX_VEX];
// 初始化第一个权值为 0，即 v0 加入生成树
// lowcost的值为0，在这里就是此下标的顶点已经加入生成树
lowcost[0] = 0;
// 初始化第一个顶点下标为 0
adjvex[0] = 0;
for (i = 1; i < G.numVertexes; i++)
{
// 将 v0 顶点与之有边的权值存入数组
lowcost[i] = G.arc[0][i];
// 初始化都为 v0 的下标
adjvex[i] = 0;
}
for (i = 1; i < G.numVertexes; i++)
{
// 初始化最小权值为 ∞
// 通常设置为不可能的大数字，如 32767、65535 等
min = INFINITY;
// j 用来做顶点下标循环的变量
j = 1;
// k 用来保存最小权值的顶点下标
k = 0;
// 循环全部顶点，找到与当前顶点相连权值最小的那条边
while (j < G.numVertexes)
{
// 如果权值不为 0 并且权值小于 min
// lowcost[j]!=0 表示已经是生成树的顶点不参与最小权值的查找
if ((lowcost[j] != 0) && (lowcost[j] < min))
{
// 则让当前权值成为最小值
min = lowcost[j];
// 将当前最小值的小标存入 k
k = j;
}
j++;
}
// 打印当前顶点边中权值最小的边
printf("(%d, %d)", adjvex[k], k);
// 将当前顶点的权值设置为 0，表示此顶点已经完成任务
lowcost[k] = 0;
// 循环所有顶点
for (j = 1; j < G.numVertexes; j++)
{
// 若下标为k顶点各边权值小于此前这些顶点未被加入生成树时的权值
if ((lowcost[j] != 0) && (G.arc[k][j] < lowcost[j]))
{
// 将较小权值存入 lowcost
low[j] = G.arc[k][j];
// 将下标为k的顶点存入 adjvex
adjvex[j] = k;
}
}
}
}
由代码中的循环嵌套可知此算法的时间复杂度为 O(n²)（这个其实只是基本实现最小生成树的构建，还可以优化）。
6.10.3.6.2. 克鲁斯卡尔(Kruskal)算法（数学描述看百科）
直接以边为目标去构建，只不过构建时要考虑是否会形成环路。此时需要使用图的存储结构中的边集数组结构。
edge 边集数据结构定义:
/* 对边集数组 Edge 结构的定义 */
typedef struct
{
int begin;
int end;
int weight;
}
于是算法代码如下：
/* Kruskal 算法生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
int i, n, m;
// 定义边集数组
Edge edges[MAX_EDE];
// 定义一个数组用来判断边与边是否形成环路
int parent[MAX_VEX];
// ...
// 此处省略了将邻接矩阵 G 转化为边集数组 edges 并按权由小到大排序的代码（实现见后面具体的代码文件）
// ...、
for (i = 0; i < G.numVertexes; i++)
{
// 初始化数组为 0
parent[i] = 0;
}
// 循环每一条边
for (i = 0; i < G.numEdges; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
// 假如 n 和 m 不等，说明此边没有与现有生成树形成环路
if (n != m)
{
// 就此边的结尾顶点放入下标为起点的 parent 中，表示此顶点已经在生成树集合中
parent[n] = m;
printf("(%d, %d) %d", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
while (parent[f] > 0)
{
f = parent[f];
}
return f;
}
6.10.3.6.3. 两种算法区别
对比两个算法， Kruskal 算法主要针对边来展开，边数少时效率会非常高，所以对于稀疏图有很多优势；
而 Prim 算法对于稠密图，即边数很多的情况会更好一些。
6.10.3.7. 最短路径
在网图和非网图中，最短路径的含义是不同的。
由于非网图没有边上的权值，所谓的最短路径，其实就是两顶点之间经过的边数最少的路径；
而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们成路径上的第一个顶点是源点，最后一个顶点是终点。
显然，研究网图更有实际意义，就地图而言，距离就是两顶点之间的权值之和。而非网图可以理解为所有边的权值都为 1 的网图。
6.10.3.7.1. 迪杰斯特拉(Dijkstra)算法
从某个源点到其余各顶点的最短路径问题
#define MAX_VEX 9
#define INFINITY 65535
/* 用于存储最短路径下标的数组 */
typedef int Pathmatrix[MAX_VEX];
/* 用于存储到各点最短路径的权值和 */
typedef int ShortPathTable[MAX_VEX];
/* Dijkstra 算法，求有向网 G 的 v0 顶点到其余各顶点 v 最短路径 P[v] 及带权长度 D[v] */
/* P[v] 的值为前驱顶点下标，D[v] 表示 v0 到 v 的最短路径长度和 */
void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *P, ShortPathTable *D)
{
int v, w, k, min;
// final[w] = 1 表示求得顶点 v0 至 vw 的最短路径
int final[MAX_VEX];
// 初始化数据
for (v = 0; v < G.numVertexes; v++)
{
// 全部顶点初始化为未知最短路径的状态
final[v] = 0;
// 将与 v0 点(v0=0)有连线的顶点加上权值
(*D)[v] = G.matrix[v0][v];
// 初始化路径数组 P 为 0
(*P)[v] = 0;
}
// v0 至 v0 路径为 0
(*D)[v0] = 0;
// v0 至 v0 不需要求路径
final[v0] = 1;
// 开始主循环，每次求得 v0 到某个 v 顶点的最短路径
for (v = 1; v < G.numVertexes; v++)
{
// 当前所知离 v0 顶点的最近距离
min = INFINITY;
// 寻找离 v0 最近的顶点
for (w = 0; w < G.numVertexes; w++)
{
if (!final[w] && ((*D)[w] < min))
{
k = w;
// w 顶点离 v0 顶点更近
min = (*D)[w];
}
}
// 将目前找到的最近的顶点置为 1
final[k] = 1;
// 修正当前最短路径及距离
for (w = 0; w < G.numVertexes; w++)
{
// 如果经过 v 顶点的路径比现在这条路径的长度短的话
if (!final[w] && (min + G.matrix[k][w] < (*D)[w]))
{
// 说明找到了更短的路径，修改 D[w] 和 P[w]
// 修改当前路径长度
(*D)[w] = min + G.matrix[k][w];
(*P)[w] = k;
}
}
}
}
该算法可以求得 v0 到其余任何一个顶点得最短路径，时间复杂度为 O(n²)
若要求任意两点之间得最短路径，相当于就是把每个点都当作源点 v0 来进行一次 Dijkstra 算法，时间复杂度为 O(n³)
6.10.3.7.2. 弗洛伊德(Floyd)算法
该算法求所有顶点到所有顶点的时间复杂度也是 O(n³)，但是该算法非常简洁优雅。
注意：因为是求所有顶点到所有顶点的最短路径，因此 Pathmatrix 和 ShortPathTable 都是二维数组。
typedef int Pathmatrix[MAX_VEX][MAX_VEX];
typedef int ShortPathTable[MAX_VEX][MAX_VEX];
/* Floyd 算法，求网图 G 中各顶点 v 到其余顶点 w 最短路径 P[v][w] 及带权长度 D[v][w] */
void ShortestPath_Floyd(MGraph G, Pathmatrix *p, ShortPathTable *D)
{
int v, w, k;
// 初始化 D 和 P
for (v = 0; v < G.numVertexes; v++)
{
for (w = 0; w < G.numVertexes; w++)
{
// D[v][w] 值即为对应点间的权值
(*D)[v][w] = G.matrix[v][w];
// 初始化 P
(*P)[v][w] = w;
}
}
// k 代表中转顶点的下标
// 比如，k=0 就是说所有顶点都进过 v0 中专计算是否有最短路径的变化
for (k = 0; k < G.numVertexes; k++)
{
// v 代表起始顶点
for (v = 0; v < G.nunmVertexes; v++)
{
// w 代表结束顶点
for (w = 0; w < G.numVertexes; w++)
{
// 如果经过下标为 k 的顶点的路径比原两点间的路径更短
if ((*D)[v][w] > ((*D)[v][k] + (*D)[k][w]))
{
// 将当前两点间权值设为更小的一个
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
// 路径设置经过下标为 k 的顶点
(*P)[v][w] = (*P)[v][k];
}
}
}
}
}
/* 利用上述算法将求得的最短路径打印出来 */
for (v = 0; v < G.numVertexes; v++)
{
for (w = v + 1; w < G.numVertexes; w++)
{
printf("v%d->v%d weight：%d ", v, w, D[v][w]);
// 获得第一个路径顶点下标
k = P[v][w];
// 打印源点
printf(" path：%d", v);
// 如果路径顶点下标不是终点
while (k != w)
{
// 打印路径顶点
printf(" -> %d", k);
// 获得下一个路径顶点下标
k = P[k][w];
}
// 打印终点
printf(" -> %d\n", w);
}
printf("\n);
}
6.10.3.8. 拓扑排序：研究没有环的图
6.10.3.8.1. AOV 网
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为 AOV 网(Activity On Vertex Network)。
6.10.3.8.2. 拓扑序列
设 G = {V, E} 是一个具有 n 个顶点的有向图，V 中的顶点序列 v1，v2，...，vn，满足若从顶点 vi 到 vj 有一条路径，则在顶点序列中顶点 vi 必在顶点 vj 之前。则我们称这样的顶点序列为一个拓扑序列
。
6.10.3.8.3. 拓扑排序
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
构造时会有两个结果：
- 如果此网的全部顶点被输出，则说明它是不存在环（回路）的 AOV 网
- 如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是 AOV 网
6.10.3.8.4. 拓扑排序算法
主要是为了解决一个工程问题能否顺利进行的问题。
- 基本思路：从 AOV 网中选择一个入度为 0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止
- 涉及的结构代码：
/* 边表结点 */
typedef struct EdgeNode
{
/* 邻接点域，存储该顶点对应的下标 */
int adjvex;
/* 用于存储权值，对于非网图可以不需要 */
int weight;
/* 链域，指向下一个邻接点 */
struct EdgeNode *next;
} EdgeNode;
/* 顶点表结构 */
typedef struct VertexNode
{
/* 顶点入度 */
int in;
/* 顶点域，存储顶点信息 */
int data;
/* 边表头指针 */
EdgeNode *firstedge;
} VertexesNode, AdjList[MAX_VEX];
typedef struct
{
AdjList adjList;
/* 图中当前顶点数和边数 */
int numVertexes, numEdges;
} graphAdjList, *GraphAdjList;
在算法中，还需要一个辅助数据结构--栈，用来存储处理过程中入度为 0 的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为 0 的顶点。
实现代码：
/* 拓扑排序，若 GL 无回路，则输出拓扑排序序列并返回 OK，若有回路返回 ERROR */
Status ToplogicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
// 用于栈指针下标
int top = 0;
// 用于统计输出顶点的个数
int count = 0;
// 建栈存储入度为 0 的顶点
int *stack;
stack = (int *)malloc(GL->numVertexs * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
{
if (GL->adjList[i].in == 0)
{
// 将入度为 0 的顶点入栈
// 这里从 1 开始存起走是因为下面 while 的结束条件是为 0，如果从 0 开始存，那下面的 while 条件就改为 -1
stack[++top] = i;
}
}
while (top != 0)
{
// 出栈
gettop = stack[top--];
// 打印此顶点
printf("%d -> ", GL->adjList[i].data);
// 统计输出顶点数
count++;
// 对此顶点弧表遍历
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k = e->adjvex;
// 将 k 号顶点邻接点的入度减一
if (!(--GL->adjList[k].in))
{
// 若为 0 则入栈，以便于下次循环输出
stack[++top] = k;
}
}
}
// 如果 count 小于顶点数，说明存在环
if (vount < GL->numVertexes)
{
return ERROR;
}
else
{
return OK;
}
}
对一个具有 n 个顶点 e 条弧的 AOV 网来说，算法时间复杂度为 O(n+e)。
6.10.3.9. 关键路径
6.10.3.9.1. 定义
解决工程完成需要的最短时间问题。
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为 AOE 网(Activity On Edge Network) 。
把 AOE 网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。一个工程，总有一个开始和结束，所以正常情况下，AOE 网只有一个源点和一个汇点。
把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动称为关键活动。
6.10.3.9.2. 关键路径算法原理
只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。
为此，我们需要定义如下几个参数：
- 事件的最早发生时间 etv(earliest time of vertex)：即顶点 vk 的最早发生时间
- 事件的最晚发生时间 ltv(latest time of vertex)：即顶点 vk 的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此事件将会延误整个工期
- 活动的最早开工时间 ete(earliest time of edge)：即弧 ak 的最早发生时间
- 活动的最晚开工时间 lte(latest time of edge)：即弧 ak 的最晚发生时间，也就是不推迟工期的最晚开工时间
我们是由 1. 和 2. 可以求得 3. 和 4. ，然后再根据 ete[k] 是否与 lte[k] 相等来判断 ak 是否是关键活动。
6.10.3.9.3. 关键路径算法
求事件的最早发生时间 etv 的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算 etv 和拓扑序列列表。
首先定义几个全局变量：
/* 事件最早发生时间和最迟发生时间数组 */
int *etv, *ltv;
/* 用于存储拓扑序列的栈，以便后面求关键路径时使用 */
int *stack2;
int top2;
以下是改进过的求拓扑序列算法：
/* 拓扑排序，用于关键路径计算 */
Status TopologicSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
/* 用于栈指针下标 */
int top = 0;
/* 用于统计输出顶点的个数 */
int count = 0;
/* 建栈将入度为 0 的顶点入栈 */
int *stack;
stack = (int *) malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
{
if (0 == GL->adjList[i].in)
{
stack[++top] = i;
}
}
// 初始化为 0
top2 = 0;
// 事件最早发生事件
etv = (int *) malloc(GL->numVertexes * sizeof(int));
for (i= 0; i < GL->numVertexes; i++)
{
// 初始化为 0
etv[i] = 0;
}
stack2 = (int *) malloc(GL->numVertexes * sizeof(int));
while (top != 0)
{
gettop = stack[top--];
count++;
// 将弹出的顶点序号压入拓扑序列的栈
stack2[++top2] = gettop;
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k = e->adjvex;
if (!(--GL->adjList[k].in))
{
stack[++top] = k;
}
// 求各顶点事件最早发生时间值
if ((etv[gettop] + e->weight) > etv[k])
{
etv[k] = etv[gettop] + e->weight;
}
}
}
if (count < GL->numVertexes)
{
return ERROR;
}
else
{
return OK;
}
}
可以得出计算顶点 vk 即求 etv[k] 的最早发生时间公式：
etv[k] = 0，当 k=0 时
或 max{etv[k] + len<vi, vk>}，当 k≠0 且 <vi, vk>∈P[k] 时，其中 P[k] 表示所有到达顶点 vk 的弧的集合，len<vi, vk> 是弧 <vi, vk> 上的权值
下面是求关键路径的算法代码：
/* 求关键路径，GL 为有向网，输出 GL 的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i, gettop, k, j;
// 声明活动最早发生时间和最迟发生时间变量
int ete, lte;
// 求拓扑序列，计算数组 etv 和 stack2 的值
TopologicalSort(GL);
// 事件最晚发生时间
ltv = (int *) malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
{
// 初始化 ltv
ltv[i] = etv[GL->numVertexes - 1];
}
// 计算 ltv
while (top2 != 0)
{
// 将拓扑序列出栈，后进先出
gettop = stack2[top2--];
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
// 求各顶点时间的最迟发生时间 ltv 值
k = e->adjvex;
if ((ltv[k] - e->weight) < ltv[gettop])
{
ltv[gettop] = ltv - e->weight;
}
}
}
// 求 ete，lte 和关键活动
for (j = 0; j < GL->numVertexes; j++)
{
for (e = GL->adjList[j].firstedge; e; e = e->next)
{
k = e->adjvex;
// 活动最早发生时间
ete = etv[j];
// 活动最迟发生时间
lte = ltv[k] - e->weight;
// 如果两者相等即在关键路径上
if (ete == lte)
{
printf("<v%d, v%d> length：%d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight);
}
}
}
}
在计算 ltv 时，其实是把拓扑序列倒过来进行的。计算顶点 vk 即求 ltv[k] 的最晚发生时间的公式是：
ltv[k] = etv[k]，当 k=n-1 时
或 min{ltv[j] + len<vk, vj>}，当 k < n-1 且 <vk, vj>∈S[k] 时，其中 S[k] 表示所有从顶点 vk 出发的弧的集合，len<vk, vj> 是弧 <vk, vj> 上的权值
7. 查找
7.1. 查找表及相关概念
- 查找表(Search Table)：是由同一类型的数据元素（或记录）构成的集合
- 关键字(Key)：是数据元素中某个数据项的值
- 主关键字(Primary Key)：若此关键字可以唯一地标识一个记录，则称此关键字为主关键字
- 次关键字(Secondary Key)：对于那些可以识别多个数据元素（或记录）的关键字，称之为次关键字
- 查找(Searching)：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）
7.2. 查找表分类
查找表按照操作方式分为两大种：
静态查找表(Static Search Table)：只做查找操作的查找表。主要操作有：
- 查询某个“特定的”数据元素是否在查找表中
- 检索某个“特定的”数据元素和各种属性
动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。主要操作有：
- 查找时插入数据元素
- 查找时删除数据元素
7.3. 顺序表查找(Sequential Search)
又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个对进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；
如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
7.4. 顺序查找算法
/* 顺序查找，a 为数组，n 为要查找的数组的元素个数，key 为要查找的关键字 */
int Sequential_Search(int *a, int n, int key)
{
int i;
for (i = 1; i <= n; i++)
{
if (a[i] == key)
{
return i;
}
}
return 0;
}
上述算法一个缺点是每次循环时都需要对 i 是否越界进行判断。
7.5. 顺序表查找优化
/* 有哨兵顺序查找 */
int Sequential_Search2(int *a, int n, int key)
{
int i;
// 设置 a[0] 为关键字值，我们称之为“哨兵”
a[0] = key;
// 循环从数组尾部开始
i = n;
while (a[i] != key)
{
i--;
}
// 返回0则说明查找失败
return i;
}
7.6. 有序表查找
7.6.1. 折半查找(Binary Search)
又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。
折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，知道查找成功，或所有查找区域无记录，查找失败为止。
/* 假设有一个有序表数组 {0,1,16,24,35,47,59,62,73,88,99}，除 0 下标外共 10 个数字。对它进行查找是否存在 62 这个数。 */
/* 折半查找 */
int Binary_Search(int *a, int n, int key)
{
int low, high, mid;
// 定义最低下标为记录首位
low = 1;
// 定义最高下标为记录末位
high = n;
while (low <= high)
{
// 折半
mid = (low + high) / 2;
// 若查找值比中值小
if (key < a[mid])
{
// 最高下标调整到中位下标小一位
high = mid - 1;
}
// 若查找值比中值大
else if (key > a[mid])
{
// 最低下标调整到中位下标大一位
low = mid + 1;
}
else
{
// 若相等则说明 mid 即为查找到的位置
return mid;
}
}
return 0;
}
7.6.2. 插值查找
相当于就是把折半查找中的 mid=1/2*(low+high)=low+1/2*(high-low) 替换成插值的计算公式：mid=low+(high-low)*(key-a[low])/(a[high]-a[low])。
7.6.3. 斐波那契查找(Fibonacci Search)
利用了黄金分割原理来实现的。
首先需要一个斐波那契数列：
| 列名 | 第 1 个 | 第 2 个 | 第 3 个 | ... | 第 9 个 | 第10 个 | 第 11 个 | ... |
|---|---|---|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | ... | 8 | 9 | 10 | ... |
| F | 0 | 1 | 1 | ... | 21 | 34 | 55 | ... |
/* 斐波那契查找 */
int Fibonacci_Search(int *a, int n, int key)
{
int low, high, mid, i, k;
// 定义最低下标位记录首位
low = 1;
// 定义最高下标为记录末位
high = n;
k = 0;
// 计算 n 位于斐波那契数列的位置
while (n > F[k] - 1)
{
k++;
}
// 将不满的数值补全
for (i = n; i < F[k] - 1; i++)
{
a[i] = a[n];
}
while (low <= high)
{
// 计算当前分隔的下标
mid = low + F[k] - 1;
// 若查找记录小于当前分隔记录
if (key < a[mid])
{
// 最高下标调整到 mid-1 处
high = mid - 1;
// 斐波那契数列下标减一位
k = k - 1;
}
// 若查找记录大于当前分隔记录
else if (key > a[mid])
{
// 最低下标调整到分隔下标 mid+1 处
low = mid + 1;
// 斐波那契数列下标减两位
k = k - 2;
}
else
{
if (mid <= n)
{
// 若相等则说明 mid 即为查找到的位置
return mid;
}
else
{
// 若 mid>n 说明是补全数值，返回 n
return n;
}
}
}
return 0;
}
7.6.4. 线性索引查找
7.6.4.1. 索引
就是把一个关键字与它对应的记录相关联的过程。
线性索引：就是将索引项集合组织为线性结构，也称为索引表。
7.6.4.2. 稠密索引
是指在线性索引中，将数据集中的每个记录对应一个索引项。对于稠密索引来说，索引一定是按照关键码有序的排列。
索引项有序也就意味着查找关键字时可以用折半、插值、斐波那契等有序查找算法来进行查找。
7.6.4.3. 分块索引
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。
- 分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
- 块内无序，即每一块内的记录不要求有序
- 块间有序，例如，要求第二块所有记录的关键字均要大于第二块的所有记录关键字
- 分块索引的索引项结构分为三个数据项：
- 最大关键码，它存储每一块中的最大关键字，这样的好处是可以使得在它之后的下一块中的最小关键字也能比这一块的最大的关键字要大
- 存储了块中的记录个数，以便于循环时使用
- 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历
- 分块索引表中进行查找，分两步进行：
- 在分块索引表中查找要查关键字所在的块。由于分块索引是块间有序的，因此很容易利用折半、插值等算法得到结果
- 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找
7.6.4.4. 倒排索引(inverted index)
记录号表存储具有相同关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的所用方法就是倒排索引。
7.6.4.5. 二叉排序树(Binary Sort Tree)
又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值
- 它的左、右子树也分别为二叉排序树
7.6.4.5.1. 二叉排序树的查找操作
二叉树结构：
/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode
{
// 结点数据
int data;
// 左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* 递归查找二叉排序树 T 中是否存在 key */
/* 指针 f 指向 T 的双亲，其初始调用值为 NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回 TRUE */
/* 否则指针 p 指向查找路径上访问的最后一个结点并返回 FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
// 查找不成功
if (!T)
{
*p = f;
return FASLE;
}
// 查找成功
else if (key == T->data)
{
*p = T;
return TRUE;
}
else if (key < T->data)
{
// 在左子树继续查找
return SearchBST(T->lchild, key, T, p);
}
else
{
// 在右子树继续查找
return SearchBST(T->rchild, key, T, p);
}
}
7.6.4.5.2. 二叉排序树的插入操作
/* 当二叉排序树 T 中不存在关键字等于 key 的数据元素时，插入 key 并返回 TRUE，否则返回 FALSE */
Status InsertBST(BiTree *T, int key)
{
BiTree p, s;
// 不存在关键字相等的记录
if (!SearchBST(*T, key, NULL, &p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p)
{
// 插入 s 为新的根节点
*T = s;
}
else if (key < p->data)
{
// 插入 s 为左孩子
p->lchild = s;
}
else
{
// 插入 s 为右孩子
p->rchild = s;
}
return TRUE;
}
else
{
return FALSE;
}
}
利用二叉排序树的插入操作建立一棵二叉排序树：
int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for (i = 0; i < 10; i++)
{
InsertBST(&T, a[i]);
}
7.6.4.5.3. 二叉排序树删除操作
对删除结点有三种情况：
- 叶子结点
- 仅有左或右子树的结点
- 左右子树都有的结点
/* 若二叉排序树T中存在关键字等于 key 的数据元素时，则删除该数据元素结点并返回 TRUE；否则返回 FALSE */
Status DeleteBST(BiTree *T, int key)
{
// 不存在关键字等于 key 的数据元素
if (!*T)
{
return FALSE;
}
else
{
// 找到关键字等于 key 的数据元素
if (key == (*T)->data)
{
return Delete(T);
}
else if (key < (*T)->data)
{
return DeleteBST(&(*T)->lchild, key);
}
else
{
return DeleteBST(&(*T)->rchild, key);
}
}
}
/* 从二叉排序树中删除结点 p，并重接它的左或右子树 */
Status Delete(BiTree *p)
{
BiTree q, s;
// 若右子树空则只需重接它的左子树
if ((*p)->rchild == NULL)
{
q = *p;
*p = (*p)->lchild;
free(q);
}
// 只需重接它的右子树
else if ((*p)->lchild == NULL)
{
q = *p;
*p = (*p)->rchild;
free(q);
}
// 左右子树均不为空
else
{
q = *p;
s = (*p)->lchild;
// 转左，然后向右到尽头（找待删结点的前驱）
while (s->rchild)
{
q = s;
s = s->rchild;
}
// S 指向被删结点的直接前驱
(*p)->data = s->data;
if (q != *p)
{
// 重接 q 的右子树
q->rchild = s->lchild;
}
else
{
// 重接 q 的左子树
q->lchild = s->lchild;
}
free(s);
}
return TRUE;
}
7.6.4.6. 平衡二叉树(AVL树)(Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree)
是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1。
7.6.4.6.1. 平衡因子(BF,Balance Factor)
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。AVL 树上所有结点的 BF 只可能是 -1, 0, 1。
7.6.4.6.2. 最小不平衡子树
距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，称之为最小不平衡子树。
7.6.4.6.3. 平衡二叉树实现原理
改进二叉排序树的结点结构，增加一个 bf，用来存储平衡因子。
/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode
{
// 结点数据
int data;
// 结点的平衡因子
int bf;
// 左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
右旋操作：
/* 对以 p 为根的二叉排序树作右旋处理 */
/* 处理之后 p 指向新的树根结点，即旋转处理之前的左子树的根节点 */
void R_Rotate(BiTree *P)
{
BiTree L;
// L 指向 P 的左子树根节点
L = (*P)->lchild;
// L 的右子树挂接为 P 的左子树
(*P)->lchild = L->rchild;
L->rchild = (*P);
// P 指向新的根节点
*P = L;
}
左旋操作：
/* 对以 p 为根的二叉排序树作左旋处理 */
/* 处理之后 p 指向新的树根结点，即旋转处理之前的右子树的根节点 */
void L_Rotate(BiTree *P)
{
BiTree R;
// R 指向 p 的右子树
R = (*P)->rchild;
// R 的左子树挂接为 P 的右子树
(*P)->rchild = R->lchild;
R->lchild = (*P);
// P 指向新的根节点
*P = R;
}
左平衡旋转处理：
/* 左高 */
#define LH +1
/* 等高 */
#define EH 0
/* 右高 */
#define RH -1
/* 对以指针所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针 T 指向新的根节点 */
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
// L 指向 T 的左子树根节点
L = (*T)->lchild;
switch (L->bf)
{
// 检查 T 的左子树的平衡度，并作相应平衡处理
// 新结点插入在 T 的左孩子的左子树上，要作单右旋处理
case LH:
(*T)->bf= L->bf = EH;
R_Rotate(T);
break;
// 新结点插入在 T 的左孩子的右子树上，要作双旋处理
case RH:
// Lr 指向 T 的左孩子的右子树根
Lr = L->rchild;
// 修改 T 及其左孩子的平衡因子
switch (Lr->bf)
{
case LH:
(*T)->bf = RH;
L->bf = EH;
break;
case EH:
(*T)->bf = L->bf = EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
// 对 T 的左子树作左旋平衡处理
L_Rotate(&(*T)->lchild);
// 对 T 作右旋平衡处理
R_Rotate(T);
break;
}
}
完整操作：
/* 若在平衡的二叉排序树 T 中不存在和 e 有相同关键字的结点，则插入一个 */
/* 数据元素为e的新结点并返回 1，否则返回 0。若因插入而使二叉排序树 */
/* 失去平衡，则作平衡旋转处理，布尔变量 taller 反应 T 长高与否 */
Status InsertAVL(BiTree *T, int e, Status *taller)
{
if (!*T)
{
// 插入新结点，树“长高”，置 taller 为 TRUE
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}
else
{
// 树中已经存在和e有相同关键字的结点则不再插入
if (e == (*T)->data)
{
*taller = FALSE;
return FALSE;
}
// 如果 e 小于当前关键字，则继续在T的左子树中进行搜索
if (e < (*T)->data)
{
// 未插入
if (!InsertAVL(&(*T->lchild, e, taller)))
{
return FALSE;
}
// 已插入到 T 的左子树中且左子树“长高”
if (taller)
{
// 检查 T 的平衡度
switch((*T)->data)
{
// 原本左子树比右子树高，需要作左平衡处理
case LH:
LeftBalance(T);
*taller = FALSE;
break;
// 原本左右子树等高，现因左子树增高而树增高
case EH:
(*T)->bf = LH;
*taller = TRUE;
break;
// 原本右子树比左子树高，现在左右子树等高
case RH:
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}
// 如果 e 大于当前关键字，应继续在 T 的右子树中进行搜索
else
{
// 未插入
if (!InsertAVL(&(*T)->rchild, e, taller))
{
return FALSE;
}
// 已插入到 T 的右子树且右子树“长高”
if (*taller)
{
// 检查 T 的平衡度
switch((*T)->bf)
{
// 原本左子树比右子树高，现在左、右子树等高
case LH:
(*T)->bf = EH;
*taller = FALSE;
break;
// 原本左、右子树等高，现因右子树增高而树增高
case EH:
(*T)->bf = RH;
*taller = TRUE;
break;
// 原本右子树比左子树高，需要作右平衡处理
case RH:
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
7.6.4.7. 多路查找树(multi-way search tree)
其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
7.6.4.7.1. 2-3树
其中的每一个结点都具有两个孩子（称为 2 结点）或三个孩子（称为 3 结点）。
- 一个 2 结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，不同之处在于这个 2 结点要么没有孩子，要么就有两个，不能只有一个孩子
- 一个 3 结点包含一大一小两个元素和三个孩子（或没有孩子），一个 3 结点要么没孩子，要么具有 3 个孩子。如果某个 3 结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素
- 2-3 树的插入实现，可分为三种情况：
- 对于空树，插入一个 2 结点即可
- 插入结点到一个 2 结点的叶子上。由于其本身就就只有一个元素，所以只需要将其升级为 3 结点即可
- 往 3 结点中插入一个新元素。因为 3 结点本身已经是 2-3 树的节点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素或插入元素中选择其一向上移动一层
- 2-3 树的删除实现，也分为三种情况：
- 所删除元素位于一个 3 结点的叶子结点上，只需要在该结点处删除该元素即可
- 所删除的元素位于一个 2 结点上，即要删除的是一个只有一个元素的结点，此时又分为四种情形：
- 情形一：此结点的双亲也是 2 结点，且拥有一个 3 结点的右孩子
- 情形二：此结点的双亲是 2 结点，它的右孩子也是 2 结点
- 情形三：此结点的双亲是一个 3 结点
- 情形四：如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不能满足 2-3 树的定义，需要考虑将 2-3 树的层数减少
- 所删除的元素位于非叶子的分支结点。通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让他们来补位即可
7.6.4.7.2. 2-3-4 树
就是 2-3 树的概念扩展，包括了 4 结点的使用，一个 4 结点包含小中大三个元素和四个孩子（或没有孩子），一个 4 结点要么没有孩子，要么具有 4 个孩子。
如果某个 4 结点有孩子的话，左子树包含小于最小元素的元素；
第二子树包含大于最小元素，小于第二元素的元素；
第三子树包含大于第二元素，小于最大元素的元素；
右子树包含大于最大元素的元素。
7.6.4.7.3. B树(B-Tree)
是一种平衡的多路查找树，2-3 树和 2-3-4 树都是 B 树的特例。
结点最大的孩子数目称为 B 树的阶(Order)，因此 2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树。
一个 m 阶 B 树具有如下属性：
- 如果根节点不是叶结点，则其至少有两棵子树
- 每一个非根的分支结点都有 k-1 个元素和 k 个孩子，其中 [m/2] <= k <= m。每一个叶子节点 n 都有 k-1 个元素，其中 [m/2] <= k <= m
- 所有叶子节点都位于同一层次
- 所有分支节点包含下列信息数据 (n,A0,K1,A1,K2,A2...,Kn,An)，其中：Ki(i=1,2,..,n) 为关键字，且 Ki < K(i+1)(i=1,2,...,n-1)；Ai(i=0,2,...,n)
为指向子树根节点的指针，且指针 A(i-1) 所指子树中所有结点的关键字均小于 Ki(i=1,2,..,n)，An 所指子树中所有结点的关键字均大于 Kn，n([m/2]-1 <= n <= m-1) 为关键字个数（或 n+1
为子树的个数）
7.6.4.7.4. B+ 树
是应文件系统所需而出的一种 B 树的变形树。
在 B+ 树中，出现在在分支结点中的元素会被当作它们在该分支节点位置的中序后继者（叶子结点）中再次列出。
另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
一棵 m 阶 B+ 树和 m 阶的 B 树的差异在于：
- 有 n 棵子树的结点中包含有 n 个关键字
- 所有叶子结点包含全部关键字信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
- 所有分支结点可以看成是索引，节点中仅含有其子树中的最大（或最小）关键字
7.6.4.8. 散列表查找（哈希表）
7.6.4.8.1. 散列技术、散列函数
存储位置=f(关键字),这样我们可以通过查找关键字不需要比较就可以获得需要的记录的存储位置。这就是一种新的存储计数--散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。查找时，根据这个确定的对应关系找到给定值 key 的映射 f(key)，若查找集合种存在这个记录，则必定在 f(
key) 的位置上。
我们把这种对应关系 f 称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash Table)
。那么关键字对应的记录存储位置我们称为散列地址。
7.6.4.8.2. 散列表查找步骤
整个散列过程其实就是两步：
- 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
- 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录
所以说，散列技术既是一种存储方法，也是一种查找方法。
散列技术最适合的求解问题是查找与给定值相等的记录。
时常会碰到两个关键字 key1≠key2，但是却有 f(key1)=f(key2)，这种现象称为冲突(collision)，并把 key1 和 key2 称为这个散列函数的同义词(synonym)。
7.6.4.8.3. 散列函数的构造方法
- 直接定址法：可以取关键字的某个线性函数值为散列地址，即 f(key) = a * key + b(a、b 为常数)
- 数字分析法：抽取关键字的一部分来计算散列存储位置，这个比较常用
- 平方取中法：假设关键字是 1234，平方为 1522756，然后抽取中间 3 位就是 227 用做散列地址
- 折叠法：是将关键字从左到右分割成位数相等的几部分（最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
- 除留余数法：此方法为最常用的构造散列函数方法，对于散列表长为m的散列函数公式为：f(key) = key mod p (p<=m)。mod 是取模（求余数）的意思，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模
很显然，本方法的关键就在于选择合适的 p，如果 p 选得不好，就可能会容易产生同义词。
根据前辈们的经验，若散列表表长为 m，通常 p 为小于或等于表长（最好接近 m）的最小质数或不包含小于 20 质因子的合数。
- 随机数法：选择一个随机数，取关键字的随机函数值为它的散列地址，也就是 f(key)=random(key)。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的
7.6.4.8.4. 处理散列冲突的方法
开放定址法：即一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
它的公式是：
fi(key) = (f(key) + di) MOD m (di=1,2,3...,m-1)这种本来都不是同义词缺需要争夺一个地址的情况，我们称这种现象为堆积。
可以增加平方运算使关键字不要都聚集再某一块区域，称这种方法为二次探测法：
fi(key) = (f(key) + di) MOD m (di = 1², -1², 2², -2²,...,q²,-q²,q<=m/2)还有一种方法是，在冲突时对于位移量 di 采用随机函数计算得到，称之为随机探测法。
再散列函数法：可以事先准备多个散列函数。fi(key) = RHi(key) (i = 1,2,...,k)，这里的 RHi 就是不同的散列函数
链地址法：将所有关键字为同义词的记录存储在一个单链表中，在散列表中只存储所有同义词子表的头指针
公共溢出区法：为所有冲突的关键字建立一个公共的溢出区域来存放
7.6.4.8.5. 散列表查找实现
- 算法实现： 首先需要定义一个散列表的结构以及一些相关常数。其中 HashTable 是散列表结构，结构中的 elem 是一个动态数组
#define SUCCESS 1
#define UNSUCCESS 0
// 定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
// 数据元素存储基质，动态分配数组
int *elem;
// 当前元素个数
int count;
} HashTable;
// 散列表表长，全局变量
int m = 0;
对散列表进行初始化：
/* 初始化散列表 */
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m * sizeof(int));
for (i = 0; i < m; i++)
{
H->elem[i] = NULLKEY;
}
return OK;
}
定义散列函数，可以根据不同情况更改算法：
/* 散列函数 */
int Hash(int key)
{
// 除留余数法
return key % m;
}
对散列表进行插入操作：
/* 插入关键字进散列表 */
void InsertHash(HashTable *H, int key)
{
// 求散列地址
int addr = Hash(key);
// 如果不为空，则冲突
while (H->elem[addr] != NULLKEY)
{
// 开放定址法的线性探测
addr = (addr + 1) % m;
}
// 直到有空位后插入关键字
H->elem[addr] = key;
}
通过散列表查找记录：
/* 散列表查找关键字 */
Status SearchHash(HashTable H, int key, int *addr)
{
// 求散列地址
*addr = Hash(key);
// 如果不为空，则冲突
while (H.elem[*addr] != key)
{
// 开放定址法的线性探测
*addr = (*addr + 1) % m;
// 如果循环回到原点
if ((H.elem[*addr] == NULLKEY) || (*addr == Hash(key)))
{
// 则说明关键字不存在
return UNSUCCESS;
}
}
return SUCCESS;
}
- 散列查找性能分析：散列查找的平均查找长度取决于以下几个因素：
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的装填因子：所谓的装填因子 α=填入表中的记录个数/散列表长度。α 标志着散列表的装满的程度。当填入表中的记录越多，α 就越大，产生冲突的可能性就越大
8. 排序
8.1. 内排序与外排序
8.1.1. 定义
根据在排序过程中待排序的记录是否全部都被放置在内存中，排序分为：内排序和外排序。
内排序是在整个排序过程中，待排序的所有记录全部被放置在内存中。
外排序是由于排序的记录数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
8.1.2. 内排序
对于内排序来说，排序算法的性能主要是受 3 个方面影响：
- 时间性能
- 辅助空间
- 算法的复杂性：这里指的是算法本身的复杂度，不是算法的时间复杂度
8.1.2.1. 内排序分类
- 根据排序过程中借助的主要操作，把内排序分为：
- 插入排序
- 交换排序
- 选择排序
- 归并排序
- 按照算法复杂度分为两大类：
- 冒泡排序、简单选择排序和直接插入排序属于简单算法
- 希尔排序、堆排序、归并排序、快速排序属于改进算法
8.1.2.2. 排序用到的结构与函数
/* 用于要排序的数组个数最大值，可根据需要修改 */
#define MAX_SIZE 10
typedef struct
{
// 用于存储要排序数组，r[0] 用作哨兵或临时变量
int r[MAX_SIZE + 1];
// 用于记录顺序表的长度
int length;
} SqList;
/* 交换 L 中数组 r 的下标为 i 和 j 的值 */
void swap(SqList *L, int i, int j)
{
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
8.1.2.3. 冒泡排序(Bubble Sort)
基本思想是两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
8.1.2.3.1. 冒泡排序初级版
/* 对顺序表 L 作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{
int i, j;
for (i = 1; i < L->length; i++)
{
for (j = i + 1; j <= L->length + 1; j++)
{
if (L->r[i] > L->r[j])
{
swap(L, i, j);
}
}
}
}
8.1.2.3.2. 正宗的冒泡算法
/* 对顺序表 L 作冒泡排序 */
void BubbleSort1(SqList *L)
{
int i, j;
for (i = 1; i < L->length; i++)
{
// 注意 j 是从后往前循环
for (j= L->length - 1; j >= i; j--)
{
// 若前者大于后者
if (L->r[j] > L->r[j + 1])
{
swap(L, j, j + 1);
}
}
}
}
8.1.2.3.3. 冒泡排序优化
避免已经有序的情况下的无意义判断。
/* 对顺序表 L 作改进冒泡算法 */
void BubbleSort2(SqList *L)
{
int i, j;
// flag 用来作为标记
Status flag = TRUE;
// 若 flag 为 true 则进入循环
for (i = 1; (i < L->length) && flag; i++)
{
// 初始化为 false
for (j = L->length - 1; j >= i; j--)
{
if (L->r[j] > L->r[j + 1])
{
swap(L, j, j + 1);
// 如果有数据交换，则 flag 为 true
flag = true;
}
}
}
}
冒泡排序复杂度：O(n²)
8.1.2.4. 简单选择排序
简单选择排序法(Simple Selection Sort)就是通过 n-i 次关键字间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i(1<=i<=) 个记录交换之。
/* 对顺序表 L 作简单选择排序 */
void SelectSort(SqList *L)
{
int i, j, min;
for (i = 1; i < L->length; i++)
{
// 将当前下标定义为最小值下标
min = i;
for (j = i + 1; j <= L->length; j++)
{
// 如果有小于当前最小值的关键字
if (L->r[min] > L->r[j])
{
min = j;
}
}
// 若 min 不等于 i，说明找到最小值，交换
if (i != min)
{
swap(L, i, min);
}
}
}
简单选择排序复杂度：O(n²)，性能上要略优于冒泡排序
8.1.2.5. 直接插入排序(Straight Insertion Sort)
基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。
/* 对顺序表 L 作直接插入排序 */
void InsertSort(SqList *L)
{
int i, j;
for (i = 2; i <= L->length; i++)
{
// 需将 L->r[i] 插入有序子表
if (L->r[i] < L->r[i - 1])
{
// 设置哨兵
L->r[0] = L->r[i];
for (j = i - 1; L->r[j] > L->r[0]; j--)
{
// 记录后移
L->r[j + 1] = L->r[j];
}
// 插入到正确位置
L->r[j + 1] = L->r[0];
}
}
}
时间复杂度因为 O(n²)，比冒泡和简单选择排序的性能要好一些
8.1.2.6. 希尔排序(Shell Sort)
将原本有大量记录数的记录进行分组，分成若干个子序列，然后在每个子序列内分别进行直接插入排序，当整个序列都基本有序时，再对全体记录进行一次直接插入排序。
- 基本有序：就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像 {2,1,3,6,4,7,5,8,9} 就可以称为基本有序了，但像 {1,5,9,3,7,8,2,4,6} 这样就谈不上基本有序了
- 需要采取跳跃分隔的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
- 希尔排序算法代码：
/* 对顺序表 L 作希尔排序 */
void ShellSort(SqList *L)
{
int i, j;
int increment = L->length;
do
{
// 增量序列
increment = increment / 3 + 1;
for (i = increment + 1; i <= L->length; i++)
{
// 需将 L->r[i] 插入有序增量子表
if (L->r[i] < L->r[i - increment])
{
// 暂存在 L->r[0]
L->r[0] = L->r[i];
for (j = i - increment; (j > 0) && (L->r[0] < L->r[j]); j -= increment)
{
// 记录后移，查找插入位置
L->r[j + increment] = L->r[j];
}
// 插入
L->r[j + increment] = L->r[0];
}
}
}
while (increment > 1);
}
时间复杂度为：O(n^(3/2))，要好于直接排序的 O(n²)。需要注意的是，增量序列的最后一个增量值必须等于 1 才行。
由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
8.1.2.7. 堆排序(Heap Sort)
就是对简单选择排序的一种改进。
- 堆结构：堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。从定义可知根节点一定是堆中所有结点的最大（小）值。较大（小）的结点靠近根节点
- 堆排序算法：就是利用堆（假设利用大顶堆)进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)
，然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次小值。如此反复执行，便能得到一个有序序列了 - 代码：
/* 对顺序表 L 进行堆排序 */
void HeapSort(SqList *L)
{
int i;
// 把 L 中的 r 构建成一个大顶堆
for (i = L->length / 2; i > 0; i--)
{
HeapAdjust(L, i, L->length);
}
for (i = L->length; i > 1; i--)
{
// 将堆顶记录和当前未经排序子序列的最后一个记录交换
swap(L, 1, i);
// 将 L->r[1...i-1] 重新调整为大顶堆
HeapAdjust(L, 1, i - 1);
}
}
/* 已知 L->r[s...m] 中记录的关键字除 L->r[s] 之外均满足堆的定义 */
/* 本函数调整 L->r[s] 的关键字，使 L->r[s...m] 成为一个大顶堆 */
void HeapAdjust(SqList *L, int s, int m)
{
int temp, j;
temp = L->r[s];
// 沿关键字较大的孩子结点向下筛选
for (j = 2 * s; j <= m; j *= 2)
{
if ((j < m) && (L->r[j] < L->r[j + 1]))
{
// j 为关键字中较大记录的下标
j++;
}
if (temp >= L->r[j])
{
break;
}
L->r[s] = L->r[j];
s = j;
}
// 插入
L->r[s] = temp;
}
堆排序的复杂度分析：最好、最坏和平均时间复杂度都为 O(nlogn)。
由于记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。由于初始构建堆所需的比较次数比较多，因此，它并不适合待排序序列个数较少的情况。
8.1.2.8. 归并排序(Merging Sort)
8.1.2.8.1. 定义
就是利用归并的思想实现的排序方法。
它的原理是假设初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，
得到 [n/2]（符号 [x] 表示不小于 x 的最小整数）个长度为 2 或 1 的有序子序列；再两两归并，...，如此重复，直至得到一个长度为 n 的有序序列为止。
这种排序方法称为 2 路归并排序。
8.1.2.8.2. 代码实现
/* 对顺序表 L 作归并排序 */
void MergeSort(SqList *L)
{
MSort(L->r, L->r, 1, L->length);
}
/* 将 SR[s...t] 归并排序为 TR1[s...t] */
void MSort(int SR[], int TR1[], int s, int t)
{
int m;
int TR2[MAX_SIZE + 1];
if (s == t)
{
TR1[s] = SR[s];
}
else
{
// 将 SR[s...t] 平分为 SR[s...m] 和 SR[m+1...t]
m = (s + t) / 2;
// 递归将 SR[s...m] 归并为有序的 TR2[s...m]
Msort(SR, TR2, s, m);
// 递归将 SR[m+1...t] 归并为有序的 TR2[m+1...t]
MSort(SR, TR2, m + 1, t);
// 将 TR2[s...m] 和 TR2[m+1...t] 归并到 TR1[s...t]
Merge(TR2, TR1, s, m, t);
}
}
/* 将有序的 SR[i...m] 和 SR[m+1...t] 归并为有序的 TR[i...n] */
void Merge(int SR[], int TR[], int i, int m, int n)
{
int j, k, l;
// 将 SR 中记录由小到大归并入 TR
for (j = m + 1, k = i; (i <= m) && (j <= n); k++)
{
if (SR[i] < SR[j])
{
TR[k]= SR[i++];
}
else
{
TR[k] = SR[j++];
}
}
if (i <= m)
{
for (l= 0; l <= m - i; l++)
{
// 将剩余的 SR[i...m] 复制到 TR
TR[k + 1] = SR[i + 1];
}
}
if (j <= n)
{
for (l= 0; l <= n - j; l++)
{
// 将剩余的 SR[j...n] 复制到 TR
TR[k + 1] = SR[j + 1];
}
}
}
归并排序复杂度分析：最好、最坏和平均时间复杂度都为 O(nlogn)。空间复杂度为 O(n+logn)。属于稳定的排序算法。
8.1.2.8.3. 非递归实现归并排序
/* 对顺序表 L 作非递归归并排序 */
void MergeSort2(SqList *L)
{
// 申请额外空间
int *TR = (int *)malloc(L->length * sizeof(int));
int k = 1;
while (k < L->length)
{
MergePass(L->r, TR, k, L->length);
// 子序列长度加倍
k = 2 * k;
MergePass(TR, L->r, k, L->length);
// 子序列长度加倍
k = 2 * k;
}
}
/* 将 SR[] 中相邻长度为 s 的子序列两辆归并到 TR[] */
void MergePass(int SR[], int TR[], int s, int n)
{
int i = 1;
int j;
while (i <= n - 2 * s + 1)
{
// 两两归并
Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
i= i + 2 * s;
}
// 归并最后两个序列
if (i < n - s + 1)
{
Merge(SR, TR, i, i + s - 1, n);
}
// 若最后只剩下单个子序列
else
{
for (j = i; j <= n; j++)
{
TR[j] = SR[j];
}
}
}
非递归方式的空间复杂度为 O(n)，并且避免递归在时间性能上有一定的提升。因此使用归并排序时，尽量考虑用非递归方法。
8.1.2.9. 快速排序(Quick Sort)
8.1.2.9.1. 定义
基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
8.1.2.9.2. 代码实现
/* 对顺序表 L 作快速排序 */
void QuickSort(sqList *L)
{
QSort(L, 1, L->length);
}
/* 对顺序表 L 中的子序列 L->r[low...high] 作快速排序 */
void QSort(SqList *L, int low, int high)
{
int pivot;
if (low < high)
{
// 将 L->r[low...high] 一分为二，算出枢轴值 pivot
pivot = Partition(L, low, high);
// 对低子表递归排序
QSort(L, low, pivot - 1);
// 对高子表递归排序
QSort(L, pivot + 1, high);
}
}
/* 交换顺序表 L 中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前（后）的记录不大（小）与它 */
int Partition(SqList *L, int low, int high)
{
int pivotkey;
// 用子表的第一个记录作枢轴记录
pivotkey = L->r[low];
// 从表的两端交替向中间扫描
while (low < high)
{
while ((low < high) && (L->r[high] >= pivotkey))
{
low--;
}
// 将比枢轴记录小的记录交换到低端
swap(L, low, high);
while ((low <high) && (L->r[low] <= pivotkey))
{
low++;
}
// 将比枢轴记录大的记录交换到高端
swap(L, low, high);
}
// 返回枢轴所在位置
return low;
}
Partition函数要做的，就是先选取当中的一个关键字，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字称为枢轴(pivot)。
快速排序算法的复杂度分析：最好情况下，快速排序算法的时间复杂度为 O(nlogn)，最坏情况下时间复杂度为 O(n²)。最好情况下的空间复杂为为 O(logn)，最坏情况下空间复杂度为 O(n)，平均情况下空间复杂度为 O(logn)。
也是一种不稳定的排序方法。
8.1.2.9.2. 快速排序优化
- 优化选取枢轴
- 优化不必要的交换
- 优化对小数组时的排序方案
- 优化递归操作
0 条评论