1.绪论 #
概述: 时间, 空间复杂度
考查形式: 算法题 + 选择题
2.线性表 #
概述: 单链表的表示、插入、删除
考查形式: 算法设计题(代码类)的重点
顺序表 #
具有相同数据类型的数据元素的有限序列
用顺序存储的方式实现线性表的顺序存储
逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
性质总结:
顺序表的查找:
- 按位(下标)查找 - 随机访问, o(1)
- 按只查找
顺序表的插入和删除:
链表 #
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *Linklist
// 增加一个新的结点：在内存中申请一个结点所需空间，并用指针 p 指向这个结点
struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));
两种实现:
- 带头节点 - 头节点数据为空, 作识别用
- 不带头节点
- 对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
- 对空表和非空表的处理需要用不同的代码逻辑
单链表的查找需要遍历
单链表的插入和删除 #
插入核心逻辑(以在 p 后插入 s 为例):
s->next = p->next
p-next = s
删除核心操作(以删除 p 后的 s 为例):
p->next = s->next
free(s) // s.next = null
单链表的建立 #
- 尾插法 - 设置一个表尾指针
- 头插法 - 头节点后插入
双链表 #
可以逆向检索
typedef struct DNode {
ElemType data;
struct DNode *prev, *next;
} DNode, *Dinklist
插入核心逻辑(以在 p 后插入 s 为例):
// 先建立 s 和后续节点的关系
s.next = p.next
s.next.prev = s
// 再建立 p 和 s 的关系
s.prev = p
p.next = s
删除核心操作(以删除 p 后的 s 为例):
p.next = s.next
p.next.prev = p
s.next = null // free(s)
循环链表 #
表尾结点的 next 指针指向头结点
若为循环双链表, 则额外令表头结点的 prior 指向表尾结点
静态链表 #
用数组的方式实现的链表, 分配一整片连续的内存空间，各个结点相邻存放
3 栈与队列 #
概述: 受限制的线性表
考点: 进栈出栈, 进队出队的操作
考查形式: 选择题为主，也可能出现算法设计题(代码类)
3.1 栈 #
只允许在一端(栈顶)进行插入或删除操作的线性表
栈的顺序存储实现 #
用静态数组实现, 并需要记录栈顶指针
栈的链式存储实现 #
栈的应用 #
括号匹配 #
表达式求值 #
三种表达式:
前缀表达式 #
也叫波兰表达式
中缀表达式 #
后缀表达式(重点) #
也叫逆波兰表达式
递归运算 #
如求阶乘
3.2 队列 #
只允许在一端进行插入, 在另一端删除的线性表
队列的顺序存储实现 #
循环队列 #
循环队列: 用模运算(取余)将存储空间在逻辑上变为环状
判空/满方法:
- 牺牲一个存储单元
- 增加 size 变量记录队列长度
- 增加 tag 标记最近一次操作是入队/出队
队列的链式存储实现 #
双端队列 #
只允许从两端插入、两端删除的线性表
考点: 对输出序列合法性的判断(在栈中合法的输出序列，在双端队列中必定合法)
快速排除方法:
- 两端入, 一边出: 根据目标出队序列, 构造入队顺序
- 两端出, 一边入: 根据目标出队序列, 构造出队顺序
3.3 特殊矩阵的压缩存储 #
二维数组的存储结构 #
行优先和列优先:
对称矩阵 #
即 $a_{ij} = a_{ji}$
因此只需存储主对角线和下三角区
存储策略: 按行优先原则将各个元素存入一维数组:
三角矩阵 #
即上/下三角矩阵有值, 令半个三角为常数
相对对称矩阵, 数组最后一个位置需要额外存储常量 c
三对角矩阵(带状矩阵) #
稀疏矩阵的压缩存储 #
稀疏矩阵即零元素占绝大多数的矩阵, 因此只需存储非零元素即可
两种压缩存储策略:
顺序存储 #
三元组<行, 列, 值>, 除此之外还需要存储行数和列数
链式存储 - 十字链表法 #
十字链表法:
4.串与数组 #
概述: 线性表的扩展(串即字符串, 是一种特殊的线性表，数据元素之间呈线性关系)
考点:
- bf算法
- KMP 算法求 next 函数
- 数组的按行存储, 按列存储，在内存中的表示
- 压缩存储从二维的对称矩阵，三角矩阵，对角矩阵对应到一维地址的计算
考查形式: 选择题为主
串的存储结构 #
顺序存储 #
链式存储 #
模式匹配算法(重点) #
在主串中找到与模式串相同的⼦串，并返回其所在位置
朴素模式匹配算法 #
KMP 算法 #
5.树与二叉树 #
概述: 层次结构
考点:
- 二叉树遍历(先序/中序/后序), 遍历序的转换
- 哈夫曼树
- 二叉树与树和森林的转换
考查形式: 选择题为主，也会涉及树的遍历和哈夫曼树的算法
5.1 树的基本概念 #
度 #
- 结点的度: 有几个孩子(分支)
1. - 树的度: 各结点的度的最大值
- 任意结点的度 <= 树的度
- 结点数=总度数+1
5.2 二叉树 #
5.2.1 二叉树的基本概念 #
二叉树是有序树
二叉树的性质:
- 叶子结点比二分支结点多一个
5.2.2 几种特殊的二叉树: #
满二叉树 #
高度为h，且含有 $2^n-1$个结点的二叉树
完全二叉树 #
完全二叉树: 叶子节点只能出现在层次最大的两层上出现
即相对满二叉树, 最后两层可能不是满的
例题:
已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是?(111)
前五层 + 第六层八个叶子节点24个子节点 + 第七层 48 个叶子节点
二叉排序树(BST) #
左子树上所有结点的值均小于根结点的值
右子树上所有结点的值均大于根结点的值
二叉搜索树 #
待补充
平衡二叉树 #
树上任一结点的左子树和右子树的平衡因子(深度之差的绝对值)不超过1
AVL 树 #
ref
即为平衡二叉树的二叉搜索树
解决了平衡二叉树在处理有序数列时, 退化为一条直线的问题
AVL 树插入:
ref
5.2.3 二叉树的存储结构 #
- 顺序存储 - 数组, 一定要把二叉树的结点编号与完全二叉树对应起来
-
- 链式存储
5.2.4 二叉树的先中后遍历 #
5.2.5 二叉树的层次遍历 #
5.2.5 线索二叉树 #
分前中后序二叉树
#
哈夫曼树 #
哈夫曼树构造规则:
注意下一层的数据小于上一层的最小值:
1, 因此新一轮最小的两个数若大于上一轮的和则和同层级
2. 否则与上一轮的两个最小值同层级
带权路径两种计算方法:
- 非叶子节点相加
- 叶子节点权值 * 路径长度的求和
加权平均长度: 每个节点到根节点路径长度与权值之积的和/权值之和
森林 #
例题:
将森林转换为对应的二叉树,若在二叉树中,结点是结点的父结点的父结点,则 在原来的森林中,u和v可能具有的关系是?()
森林与二叉树的转换规则: 左孩子右兄弟
6.图 #
概述: 网状结构
考点:
- 图的遍历(DFS,BFS)
- 图的应用
- 最小生成树(prim算法, 克鲁斯卡尔算法)
- 最短路径(狄杰斯算法, 弗洛伊德算法)
- 拓扑排序 AOV
- 关键路径 AOE
- 图的存储结构: 邻接表, 十字链表, 邻接多重表
考查形式: 选择题为主，图的遍历，应用分析题
6.1 图的基本概念 #
图 G=(V, E) 由顶点集V和边集E组成, 不能为空
节点的度:
- 无向图: 依附于该顶点的边的条数(度数一定为偶数)
- 有向图: 出度和入度之和
- 出度: 以节点为起点的有向边的数量
- 入度: 以节点为终点的有向边的数量
点到点的关系 #
- 路径: 顶点到顶点之间的一条顶点序列
- 回路(环): 第一个顶点和最后一个顶点相同的路径
- 简单路径: 顶点不重复出现的路径
- 简单回路: 除第一个顶点和最后一个顶点外, 其余顶点不重复出现的回路
- 路径长度: 路径上边的数目
- 点到点的距离: 从顶点u出发到顶点v的最短路径若的长度, 不存在路径为无穷(∞)
- 连通: 无向图中, 顶点到顶点有路径存在
- 强连通: 有向图中, 顶点之间双向都有路径存在
- 连通图: G中任意两个顶点都是连通的
- 是连通图，则最少有 n-1 条边
- 是非连通图，则最多可能有 $C_{n-1}^2$ 条边
- 强连通图: G中任意两个顶点都是强连通的
- 是强连通图，则最少有 n 条边(形成回路)
图的局部 #
子图
连通分量-极大连通子图
强连通分量-极大强连通子图
连通无向图的生成树-包含全部顶点的极小连通子图
非连通无向图的生成森林-各连通分量的生成树
几种特殊形态的图 #
- 完全图
- 无向完全图: 无向图中任意两个顶点之间都存在边(边数 = $C_n^2$)
- 有向完全图: 有向图中任意两个顶点之间都存在方向相反的两条弧
- 稠密图
- 稀疏图: 边很少的图
- 树
- 森林
6.2 图的遍历(重点) #
一些规则:
- 每个节点只能访问一次
- 对于非连通无向图, 执行几次 DFS 或 BFS, 图中就有几个连通分量
DFS-深度优先搜索 #
BFS-广度优先搜索 #
6.3 图的应用(重点) #
最小生成树 #
ref
在无向图中求一棵树:
- n-1 条边
- 无环
- 连通所有点
- 且这棵树的边权和最小(可能有多个树, 但边权和唯一)
普利姆(Prim)算法 #
也称为加点法:
- 可以从任何一个点开始
- 寻找离已点亮部分(集合)的最近的点
和 Dijkstra 算法关系:
- 都基于贪心算法, 寻找局部最优解(连通图性质证明可以转换为全局最优解)
- prim 是已有集合到点; dijstra 是点到点
特点:
- 以寻找点为核心
- 适合稠密图
克鲁斯卡尔(Kruskal)算法 #
也称为加边法:
- 按照边权值从小到大, 按顺序加入非同一个联通分量的边
特点:
- 以寻找边为核心
- 适合稀疏图
最短路径 #
单源最短路径算法: Dijkstra, BDS
多对顶点之间最短路径: Floyd
Dijkstra 算法 #
计算两点间最短带权路径(DP思想):
- 如果权值可能为负数, 则需要用
Bellman-Ford算法 - 如果是计算任意两点间最短带权路径, 则需要
Floyd算法
图示:
弗洛伊德算法 #
依次将每个点作为"中间点"去做更新
拓扑排序(AOV) #
将所有的点按先后顺序排成序列(必须是有向无环图)
规则:
- 选取入度为 0 的点, 删除它的出边
- 重复 1 直至所有节点输出
关键路径(AOE网) #
网: 边上有权值的图
相当于逆拓扑排序: 每次选出度为 0 的点, 删除这个点和它的入边
6.4 图的存储 #
邻接矩阵(重点) #
有向图: 第 i 行第 j 列表示节点 i 到节点 j 有边(也可存储边的权值)
无向图: 有向图的基础上, 为实对称矩阵
邻接矩阵:
缺点:
- 统计边的数量效率较低, 时间复杂度 o(n^2)
- 空间复杂度高, o(n^2)
邻接表 #
存储下标索引到连接的节点
以无向图的邻接表为例:
十字链表 #
邻接多重表 #
7.查找 #
考点:
- 线性表的查找
- 折半查找, 顺序查找, 分块查找
- 树表的查找
- 二叉排序树, 平衡二叉树, 红黑树, B 树, B+ 树
- 散列表的查找
查找⻓度: 在查找运算中, 需要对⽐关键字的次数称为查找⻓度
平均查找⻓度(ASL): 所有查找过程中进⾏关键字的⽐较次数的平均值(分成功/失败)
7.1 线性表的查找 #
顺序查找 #
两种情况下的优化思路:
- 有序 - 可提前判定结束查找
- 被查概率不相等 - 按被查概率降序排列
O(n)
折半查找(二分查找) #
仅适⽤于有序的顺序表, 比较 $log_2(n+1)$ 这也是完全二叉树的高度
分块查找(索引顺序查找) #
“索引表”中保存每个分块的最⼤关键字和分块的存储区间
7.2 树表的查找 #
B 树 #
⼜称多路(叉)平衡查找树，B树中所有结点的孩⼦个数的最⼤值称为B树的阶
相对于 AVL 和红黑树, 树的高度被压缩了, 减少了检索次数(适用硬盘场景)
于任何⼀个结点，其所有⼦树的⾼度都要相同
m 阶 B 树的核心特性:
- 平衡 - 所有叶节点在同一层
- 有序 - 节点内有序, 且任意元素的左子树小于它, 右子树大于它
- 多路
- 根节点的⼦树数∈[2, m]，关键字数∈[1, m-1]
- 其他结点的⼦树数∈[m/2, m]；关键字数∈⌈m/2-1, m-1⌉
另一角度上 m 阶 B 树的核⼼特性:
- 尽可能
满- 根节点的⼦树数∈[2, m]，关键字数∈[1, m-1]
- 其他结点的⼦树数∈[m/2, m]；关键字数∈⌈m/2-1, m-1⌉
- 尽可能
平衡- 对任⼀结点，其所有⼦树⾼度都相同
- 关键字的值：⼦树0<关键字1<⼦树1<关键字2<⼦树2<…. (类⽐⼆叉查找树 左<中<右)
- 含n个关键字的m叉B树，$log_m(n + 1) ≤ h ≤ log_{\frac{m}{2}}\frac{n + 1}{2} + 1$
B 树的查找:
- 访问节点在硬盘上进行
- 节点内的查找在内存中进行
B 树插入若溢出则选中间节点插入到父节点, 上溢出可能发生多次, 直至最后可能创建新的根节点
B 树的构建参考插入即可
B 树的删除可能出现下溢出(少于 m/2 个元素):
- 删除非叶节点数据, 用其前驱(比它小的第一个数)或后继替代(比他大的第一个数), 转换为删除叶节点
- 删除叶节点若出现下溢出
- 优先向兄弟节点借
- 兄弟不够则和兄弟节点合并, 此时父节点需要下移到左边的节点, 右边的兄弟节点合并过来
- 该过程可能导致夫节点也下溢出, 故需要向父节点的后兄弟借, 重复操作
B+树 #
叶结点之间通过指针链接(图为4阶B+树):
⼀棵m阶的B+树需满⾜下列条件:
- 每个分⽀结点最多有m棵⼦树(孩⼦结点)
- ⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 ⌈m/2⌉ 棵⼦树
- 结点的⼦树个数与关键字个数相等
- 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来
- 因此支持顺序查找
- 所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针
典型应用: 索引
B树B+树对比:
红黑树 #
7.3 散列表的查找 #
查找长度: 需要对比关键字的次数
平均查找成功长度:
查找失败平均长度: 对散列函数取模后可能的值进行计算取平均值
装填因子:
冲突处理的方法:
- 链接法: 所有同义关键词存储在一个链表中
-
- 开放定址法:
- 线性探测法: 一次往后探测相邻的下一个单元是否为空
- 可能出现冲突扎堆聚集的情况
- 删除元素时不能真的删除只能逻辑删除, 否则查找时发现为空会直接判断查找失败
- 易存在大量废弃数据
- 如果到最后一个位置也没找到空单元, 重回表头继续寻找
- 平方探测法: 每次冲突后依次向 $[n^2, -n^2] (n\in[0, \frac{散列表表长}{2}])$ 后插入
- 伪随机序列法
- 线性探测法: 一次往后探测相邻的下一个单元是否为空
例题1:
考查形式: 选择题为主
8.排序 #
考点:
- 内部排序
- 插入排序: 直接插入排序
- 交换排序: 冒泡，快速排序
- 选择排序: 简单选择排序和，堆排序(大根堆, 小根堆, 输出一个元素后怎么调整)
- 归并排序:
- 基数排序
- 基数排序: 按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位
- 外部排序
排序算法稳定性 排序前后两个相等的数相对位置不变，则算法稳定
不稳定算法: 选艾希, 堆攻速, 不稳定
考查形式: 选择题为主
8.1 插入排序 #
每趟排序后能确定前面的若干元素是有序的
8.2 交换排序 #
冒泡排序 #
每一趟都能确定一个元素的最终位置
快速排序 #
归并排序 #
二路归并排序: 第一趟排序结束都可以得到若干个有序子序列
8.3 基数排序 #
用 0-9 的桶存放各位
8.4 选择排序 #
每⼀趟在待排序元素中选取关键字最⼩(或最⼤)的元素加⼊有序⼦序列
简单选择排序 #
堆排序 #
堆: n个关键字序列 L[1-n] 满⾜
- L(i)≥L(2i) 且 L(i)≥L(2i+1) (1 ≤ i ≤n/2) - ⼤根堆
- L(i)≤L(2i) 且 L(i)≤L(2i+1) (1 ≤ i ≤n/2) - 小跟堆
因此非常适合用二叉树顺序存储:
- 节点序号 i 的左孩子为 2i
- 节点序号 i 的右孩子为 2i+1
大根堆的二叉树表示:
小根堆的二叉树表示:
建立大跟堆的思路:
- 先按顺序构建二叉树
- 把所有⾮终端结点(i <= n/2)都检查⼀遍，是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
- 检查当前结点是否满⾜ 根≥左、右, 若不满⾜则将当前结点与更⼤的⼀个孩⼦互换
- 若元素互换破坏了下⼀级的堆，则采⽤相同的⽅法继续往下调整(因此小元素不断向下变成叶子结点)
基于大跟堆进行排序:
- 每⼀趟将堆顶元素加⼊有序⼦序列(与待排序序列中的最后⼀个元素交换)
- 将待排序元素序列再次调整为⼤根堆(小元素下坠)
总的时间复杂度: $O(nlog_2^n)$
空间复杂度: O(1)
8.x #
408 考题分析 #
