数据结构

参考资料

大话数据结构 - 精简而不缺, 精简版的算法 (第四版) - 4

数据结构绪论

数据结构是一门研究非数值计算的程序设计问题中的操作对象, 以及它们之间的关系和操作等相关问题的学科

数据, 数据元素, 数据项 ---- 类, 对象, 成员 (简单对比一下, 不严谨)
逻辑结构分为集合, 线性, 树形, 图形
物理结构分为顺序, 链式
ADT 抽象数据类型

算法

算法具有 5 个基本特性: 输入, 输出, 有穷性, 确定性, 可行性
优秀算法应该具有: 正确性, 可读性, 健壮性 (对抗不合法输入), 高效性 (时空)
简介时空复杂度, 不赘述 (注意空间复杂度是算法辅助空间对于输入量的阶, 这是我之前未明确的)

线性表

特性: 顺序 (前驱与后继), 有穷
基本方法: init,is_empty,clear,get,find,insert,delete,size/length, 其它方法都可以用基本方法建立
顺序实现需要: 起始位置, 最大容量 (数组大小), 长度 (线性表大小), 其为随机存储结构 (\(O(1)\) 时间存取), 缺点是插入删除 \(O(n)\)
链式实现基于 node,node 中有数据域与指针域, 还需要头指针, 可用头节点, 确定位置的插入删除 \(O(1)\), 读取 \(O(n)\)
静态链表就是数组的元素是节点, 保存数据与后继的下标, 对它的操作往往维护主链与备用链 (数组的首尾往往是它们的头), 元素不需实际移动, 难在表长难以确定
循环链表利于从任意 node 开始遍历, 维护时往往保存尾指针
双向链表也是常见思路

栈与队列

栈

stack,LIFO 后进先出, 为递归而生

基本方法: 受限制的线性表
在一个数组上建立对向生长的两个栈以共享空间, 当数据类型相同且数量关系相反时, 这及其有用
线性实现的空为 top == -1, 链式实现为 top == NULL
栈的一个重要应用是中缀表达式 -> 后缀表达式 (优先级隐藏在顺序中)-> 结果

队列

queue,FIFO 先进先出

基本方法: 受限制的线性表
为避免反复调整数组队列中的空间, 使用循环队列, 其为空与满的特点一致 —— 头指针与尾指针相等, 使用 flag 或者保留一个空位作为满的条件
注意循环队列的两个指针前后顺序不确定, 因而计算 length 需要特殊处理, 往往需要对 size 取余
链队列一切如常

在 C 专家编程中, 作者指出指针往往指向头与尾的下一个这一数据结构惯例

串

基本

串的比较规则为字典序, 注意 a < aa, 这个非常朴素, 但是我没有深入思考过
基本方法: init,is_empty,clear,get,find,insert,delete,size/length 这些和线性表很相像, 但注意操作对象是子串
- cat copy compare 这些是独特的, 但似乎也能用上面的方法实现, 真正特殊的在我看来在于拷贝构造和比较
标记串顺序存储的结束可以用 \0 或者记录长度, 链式存储往往在一个节点存放多个 char, 但总的来说不建议链式

串的模式匹配

朴素算法, 暴力匹配, 时间复杂度 \(O(nm)\), 非常朴素
KMP 算法, 时间复杂度 \(O(n+m)\), 计算模式串的 next 数组 (字符匹配失败后跳转到模式串的哪个位置) 以不再需要回溯主串
但是相同字符算 next 会形成链 (例如 aaaa 的 next 0123), 因此可以进一步优化, 计算 nextval 数组 (类似并查集的路径压缩)

树

节点的子树数是节点的度, 度为 0 的节点是叶节点 / 终端节点, 反之是非终端节点 / 分支节点, 非根的分支节点也叫内部节点
树的度是树内各节点度的最大值, 节点之间存在父子 / 兄弟 / 祖先子孙的关系, 根为第一层, 树最大节点层次是树的深度
树有序性指节点的左右子树是否有序
森林指不相交的树的集合
基本方法: init,is_empty,clear,create,depty,root,get,assign,parent,left,right,deltree,delnode,insert

树的存储结构

有三种表示法: 双亲表示法, 孩子表示法, 孩子兄弟表示法
- 双亲: 每个节点保存其父节点的索引, 并且按需要可以保存长子 / 兄弟等等
- 孩子: 每个节点保存其所有子节点的索引, 最优秀的保存方式是用数组保存节点, 用单链表保存孩子在数组的位置, 也可与双亲表示法结合 (加个 parent 域)
- 孩子兄弟: 将树变形为二叉树, 每个节点保存其长子与右兄弟的索引

二叉树

即节点度 <= 2, 有序的树

只有左 / 右的二叉树即斜树 (链表就是)
满二叉树: 所有叶节点都在同一层的二叉树 (\(2^n-1\) 个节点)
完全二叉树: 除了叶节点, 所有节点都有两个孩子的二叉树 (满二叉树的子集)

二叉树性质

第 \(i\) 层最多有 \(2^{i-1}\) 个节点
深度为 \(k\) 的二叉树最多有 \(2^k-1\) 个节点
\(叶节点数 = 度为 2 的节点数 + 1\)
\(n\) 个节点的完全二叉树深度为 \(\lfloor log_2n \rfloor + 1\)
有 \(n\) 个节点的完全二叉树, 按层序编号, 对任一节点 \(i\) 有:
- 若 \(i=1\), 则节点 \(i\) 是二叉树的根, 无双亲; 若 \(i>1\), 则其双亲是节点 \(i/2\)
- 若 \(2i>n\), 则节点 \(i\) 无左孩子, 否则其左孩子是节点 \(2i\)
- 若 \(2i+1>n\), 则节点 \(i\) 无右孩子, 否则其右孩子是节点 \(2i+1\)

二叉树存储结构

完全二叉树用数组存, 利用最后一个性质
一般二叉树用链式存储, 每个节点保存其左孩子与右孩子的索引

二叉树遍历

前序中序后序层序
- 前序: 根左右
- 中序: 左根右
- 后序: 左右根

给定前中 / 中后遍历的序列, 可唯一确定二叉树

void fun (tree* t) {
    if (t == NULL) return;
    // 前序工作
    fun(t->left);
    // 中序工作
    fun(t->right);
    // 后序工作
}
// 递归实现,只是业务代码位置不同

在遍历过程中建立节点即可实现二叉树建立 (根据给定节点序列, 在序列中用一定字符指示该子树为空, 方可 "转弯")
层序: 按层遍历

线索化

二叉树有大量的空指针, 浪费空间, 可以利用这些空指针来存储某种遍历的前驱 / 后继信息
但需要在二叉树的结构中增加两个标志域, 表示该节点的左右孩子是否为前驱 / 后继
线索化用于经常以某种次序遍历的情况

转化

二叉树是相对方便处理的一种树, 所以我们更希望将其它树 / 森林转化
树转化为二叉树的方法很简单, 每个节点保存其第一个孩子与右兄弟的索引, 反之亦可
森林转化为二叉树的方法, 将每棵树转化为根只有左孩子的二叉树, 然后将另一二叉树作为前一棵二叉树的右孩子, 反之亦可

赫夫曼树

赫夫曼编码是最基本的数据压缩算法, 其核心思想是用最短的编码表示出现频率最高的字符

带权路径长度即所有叶节点的权值与深度的乘积之和
带权路径长度最小的二叉树称为赫夫曼树
赫夫曼树的构造方法有固定的范式, 即每次从权值最小的两个节点 / 子树中取出, 合并为一个子树, 直到只剩下一个树 (向上生长)
将字符的出现频率作为权值, 即可构造赫夫曼树, 并以赫夫曼树的路径作为编码 (左 0 右 1), 确保编码是前缀码 (避免歧义)

图

概念

顶点 V (vertex), 图中节点有穷非空, 边 E 可空
边可有向 / 无向, 写作 <A,B>/(A,B) 有向边亦称弧, 两顶点作弧头弧尾
简单图 指无 (A,A) 且同一条边唯一
边 / 弧相对于点的数决定稀疏 / 稠密 (模糊概念)

完全图

任意两点都有边的无向图称_无向完全图_ (共 \((n*(n-1))/2\) 条边)
有向完全图类似 (共 \((n*(n-1))\) 条边)

权

带权 (指边 / 弧) 图亦称网

点边关系

无向图有边 (A,B), 称 AB 邻接, 边依附 / 关联 AB, 点相接边数为其度
有向图有弧 <A,B>, 称 A 邻接到 B,B 邻接自 A, 弧关联 AB, 点相接边数为其度, 分出度 / 入度

路径

路径即顶点序列, 其长度为边 / 弧数目, 顶点不重复为简单路径
头尾顶点一致为回路 / 环, 除去头顶点不重复为简单回路 / 环

连通

无向图两顶点有路径为连通
无向图任意两点连通为连通图
极大 (最多顶点) 连通子图 (包含依附的边) 称为图的连通分量

有向图类似概念要求双向存在路径

强连通图 / 强连通分量

生成树

连通图的极小 (包含所有点与此情况的最少边 \((n-1)\)) 连通子图称为生成树
有向图中有一顶点入度为 0, 其余为 1 称有向树
有向图去掉一些弧至其仅由有向树构成称其为图的有向森林

基本方法

clear,create,delgrapy,insert,delete,get,is_adjacent,get_adjacent,dfs,bfs...

存储结构

邻接矩阵

邻接矩阵即一维数组表示点信息, 二维数组表示两点间是否有边
无向简单图显然主对角线为 0, 且对于主对角线对称
对于有权图, 亦可用二维数组表示两点间权值并用一个特殊值表示两点间无边

邻接表

邻接表即一维数组分数据域与指针域, 指针域保存邻接点的索引
对于有向图, 可以建立两个邻接表分别表示出入

十字链表

将有向图的邻接表与逆邻接表合并为一个十字链表, 每个节点表示一条弧, 记录起点 / 终点 / 同起点下一条弧 / 同终点下一条弧
是对有向图邻接表的优化

邻接多重表

将无向图顶点的邻接表合并为一个邻接多重表, 每个节点表示一条边, 记录顶点 0 / 顶点 1 / 顶点 0 下一条边 / 顶点 1 下一条边
是对无向图邻接表的优化

边集数组

边集数组即两个一维数组分别保存点信息与边的起点 / 终点 / 权
对顶点处理很慢, 是处理边的特化

图的遍历

无论如何, 你总要用一个数组记录是否已经访问该顶点

深度优先搜索 (DFS)

dfs(图,位置){
    标记已访问
    工作
    枚举所有点
        如果邻接且未访问
            dfs(图,位置)
}
// 邻接矩阵时间O(n^2),邻接表时间O(n+e),考虑稀疏密集
main(){
    初始化
    枚举所有点
        如果未访问
            dfs(图,位置)
}

广度优先搜索 (BFS)

bfs(图){
    初始化
    枚举所有点
        如果未访问
            标记已访问
            工作
            入队
                while 队列非空
                    出队
                    枚举邻接且未访问
                        标记已访问
                        工作
                        入队
}

图的应用算法

最小生成树

最小生成树即权值最小的生成树

prim 算法

\(O(n^2)\)

从一个顶点开始, 每次选取新顶点与已访问顶点相连的最小权值的边, 直到所有顶点都被访问
实现中用一个数组记录连接顶点的顺序另一个数组记录所有顶点与已访问集合的最小权值
权为 0 的边表示已访问集合与该顶点相连, 权为无穷的边表示该顶点未被访问
每连接一个顶点就更新最小权值, 直至全为 0

kruskal 算法

\(O(eloge)\)

每次选取不成环的最小权值的边, 直到所有顶点都被访问
实现中用一个数组记录所有边的信息, 另一个数组记录顶点归属的集合 (初始化为 0)
对于边的两顶点, 根据集合路径查找归属, 相等即成环, 若为 0, 则返回顶点自身编号 (自身集合)
数组[begin] = end, 表示 begin 顶点归属 end 集合

最短路径

dijkstra 算法

单源 \(O(n^2)\), 多源 \(O(n^3)\)

实现中一个数组记录前驱路径, 一个数组记录最短路径权值, 一个数组标记是否已求得
每次选取最短路径的顶点, 更新其邻接顶点的最短路径权值, 并更新该顶点最短路径的上一顶点, 直至遍历完所有顶点
贪心选择较小本质是以局部的信息确定最短路径

floyd 算法

\(O(n^3)\)

两个二维数组, 一个记录最短路径权值 (正常初始化), 一个记录前驱路径 (随便)
三重循环, 判断 ij 两点间路过 k 是否能更短, 逐渐用 k 点 "连接" 路径,DP 思想

拓扑排序

AOV 网指顶点表示活动, 弧表示活动间的先后关系的有向图 (不可存在回路)
拓扑排序即对 AOV 网进行排序, 使得所有活动的前驱活动都排在该活动前面

拓扑排序算法

\(O(n+e)\)

对 AOV 网选取一个入度为 0 的顶点, 输出该顶点, 并将该顶点的后继顶点的入度减 1, 重复直至所有顶点都被输出
注意可以每次选出所有入度为 0 的顶点, 输出后一起减 1, 空间换时间

关键路径

AOE 网指顶点表示事件, 弧表示活动间的先后关系, 权值表示所需时间的有向图 (不可存在回路)
正常情况下,AOE 网应存在一个入度为 0 的顶点 (源点) 与一个出度为 0 的顶点 (汇点), 代表整个工程的开始与结束
关键路径即从源点到汇点的最长路径, 也即整个工程的最短时间

关键路径算法

\(O(n+e)\)

定义四个参数, 分别为事件 (顶点)/ 活动 (弧) 的最早发生时间 /(需要的) 最晚发生时间
对 AOE 网进行拓扑排序, 得所有事件的最早发生时间 (完成各前置活动的时间的最大值)
随后对拓扑排序的逆序进行遍历, 得所有事件的最晚发生时间 (后续事件 (最晚发生时间 - 活动时间) 的最小值) (最后一个事件的最晚发生时间设定为其最早发生时间)
随后对 AOE 网的所有弧遍历, 得所有工作的最早发生时间 (前置顶点的最早发生时间) 与最晚开始时间 (后置顶点的最晚发生时间 - 工作所需时间), 若两者相等, 则为关键路径

查找

查找表即同一类型数据元素的集合
关键字 / 键值 / Key 是数据的某个数据项的值, 可以标识数据, 如果查找表的数据元素是记录, 则关键字即为记录的某个数据项 (字段), 亦称关键码
根据是否能唯一标记,Key 分为主关键字与次关键字
查找表分为静态查找表与动态查找表
- 静态查找表即不插入 / 删除数据的查找表, 仅 count ()/get ()/find ()
- 动态查找表即插入 / 删除数据的查找表, 可 insert ()/remove ()/update ()
为优化查找效率, 我们面向查找表设计数据结构, 即查找结构

顺序表查找 (静态)

顺序表查找即遍历查找, 时间复杂度 \(O(n)\)
使用哨兵优化, 将查找表的最后一个元素置为 Key, 则可以省去判断是否越界的操作

有序表查找 (静态)

有序表查找即折半查找, 时间复杂度 \(O(logn)\), 但要求表有序
使用插值查找优化, 即根据 Key 与表中元素的分布情况, 选择合适的折半查找位置 mid=a[low]+(key-a[low]/a[high]-a[low])*(a[high]-a[low])
使用斐波那契查找优化, 即根据黄金分割比例, 选择合适的折半查找位置 mid=low+F[k-1]-1

斐波那契查找优化

计算目标在斐波那契数列中的位置, F[k]为大于等于 size 的最小数, 将表的长度扩充到 F[k], 并将扩充部分的元素置为最大值
mid=low+F[k-1]-1, 如果 a[mid]>key, 则 k=k-1 调整 high, 否则 k=k-2 调整 low, 重复直至 a[mid]=key (注意如果 mid>n, 则 return n 或者 low>high (return 0)

线性索引查找 (静态)

线性索引即将索引项 (主键 + 记录的位置) 组织为线性结构, 亦称索引表

稠密索引

\(O(n)\), 前提是索引表有序

将表中所有记录添加索引项, 索引表即为顺序表 (注意排序), 如果数据集太大, 则索引表也会很大, 反复访问磁盘会导致效率低下

分块索引

\(O(n^{0.5})\)

将表中记录分为若干块, 块内无序, 块间有序, 再建立块的索引表 (最大主键 + 记录位置 + 记录数量)

倒排索引

\(O(1)\)

将表中所有记录的所有可能字段映射到所有有本字段的记录, 搜索引擎的基本原理

二叉排序树查找 (动态)

\(O(logn)\)

二叉排序树 (二叉查找树) 即左子树所有节点的 Key 都小于根节点的 Key, 右子树所有节点的 Key 都大于根节点的 Key, 且左右子树也为二叉排序树
其中序遍历即为从小到大排序
判断是否找到, 根据大小递归调用, 判断左 / 右子树

插入

查找, 找到 return, 否则找到两数中间, 插入

删除

对于叶节点, 直接删除, 对于单子树节点, 以子树替代
否则, 选择中序遍历的前驱 / 后继 (左子树的最右 / 右子树的最左) 替代

平衡二叉树 (动态)(AVL 树)

为解决二叉排序树的不平衡 (退化趋近 \(O(n)\)) 问题, 引入平衡因子 (BF), 平衡因子为左子树高度 - 右子树高度, 所有节点的平衡因子的绝对值不大于一, 即平衡二叉树
插入节点后, 距离节点最近的失衡节点为根的子树为最小不平衡子树, 关键是解决它

平衡二叉树算法

为节点结构添加 BF, 定义左旋 / 右旋 / 双旋等操作
双旋是为了解决插入节点后失衡节点的 BF 与插入节点的父节点的 BF 符号相反的情况

多路查找树 (动态)(B 树)

多路查找树即每个节点的度可以大于 2 且每个节点可以存储多个元素, 但注意, 元素之间仍然有序

2-3 树

2-3 树即每个节点可以有 2/3 个子树,2 节点包含一个元素与两个子树, 并且左子树所有节点小于本节点, 右大于
3 节点包含两个元素 (一大一小) 与三个子树, 左子树所有节点小于本节点小元素, 右子树所有节点大于本节点大元素, 中节点介于中间
2-3 树的叶子节点在同一层
2-3 树的插入 / 删除操作较为复杂, 需要进行分裂 / 合并等操作, 但总能保证其特性

2-3-4 树

2-3-4 树即在 2-3 树的基础上增加 4 节点,4 节点包含三个元素与四个子树

B 树

以上两种树是 B 树的特例,2-3 树是 3 阶 B 树,2-3-4 树是 4 阶 B 树
其它特性一致, 只是节点的度无限推广
B 树的节点就像对表的分块, 大小顺序可以快速指引加载下一个节点, 可以极大减少磁盘访问次数
控制 B 树节点度与计算机的页可以容纳的元素数量一致, 使 \(n\) 节点 \(m\) 阶的 B 树最大查找节点树不大于 \(log_{\lceil \frac{m}{2} \rceil} {\frac{n+1}{2}} + 1\)

B + 树

B + 树即 B 树的变种, 叶子节点使用链表连接, 所有数据都在叶子节点, 非叶子节点只保存其子树的最大 / 最小元素作为指引
B + 树可以快速找到某位置后向后顺序遍历所有元素
B + 树预期说是树, 不如说是对链表建立树形索引

散列表查找 (动态)(哈希表)

散列表就是将关键字通过函数映射到内存位置
散列函数的难点在于避免冲突 (同义词)
优秀的散列函数应满足计算简单, 均匀分布

直接定址法 (了解 Key 分布, 均匀分布)

取关键字的某个线性函数值为散列地址, 即 \(H(key)=a*key+b\)

数字分析法 (了解 Key 分布, 部分均匀分布)

分析一组数据, 找出关键字中变化最大的部分, 将其 (或简单变形) 作为散列地址

平方取中法 (不了解 Key 分布, 位数少)

取关键字平方后的中间几位作为散列地址

折叠法 (不了解 Key 分布, 位数多)

将关键字从左到右分割成位数相等的几部分, 最后一部分位数不够可以短些, 然后将这几部分叠加求和, 并按散列表表长取后几位作为散列地址

除留余数法 (最通用)

取 \(p\) 为不小于散列表表长 \(m\) 的最小质数或不包含小于 20 的质因子的合数, \(H(key)=key%p\)

随机数法 (Key 没有规律)

取随机数作为散列地址,\(H(key)=random(key)\)

我们要考虑如下方面选择散列函数, 函数时间复杂度,key 长度, 表长度, 关键字分布情况, 查找频率

处理冲突

开放定址法 (线性探测再散列 (加减)/ 二次探测再散列 (再算一下)/ 伪随机探测再散列 (随机序列))
再散列法 (换一个散列函数)
链地址法 (位置上是个链表)
公共溢出区法 (将冲突的元素放入另一个表中)

散列表的理想查找效率为 \(O(1)\), 但受几方面影响, 散列函数是否均匀, 冲突处理是否高效, 表的装填因子 (填入表的元素 / 表长)

排序

排序即指使序列中关键字呈非递减 / 非递增顺序排列的行为
排序的稳定性即两元素关键字相等, 排序后原相对位置不变
内排序指所有记录保存在内存中, 外排序反之, 我们主要讨论内排序
排序性能的衡量指标为时间复杂度 (比较与移动) 与空间复杂度以及算法本身的复杂性

简单算法 (稳定, 常数空间)

冒泡排序

\(O(n^2)\) 最好 \(O(n)\) 最坏 \(O(n^2)\)

两两比较, 若逆序则交换, 每一趟将最大元素移到最右
两两比较能一定程度优化过程, 使过程中部分有序
但如果中间时间已经有序冒泡还是得进行 \(n\) 次, 可以设置一个标志位, 若某一趟没有交换, 则序列有序

选择排序

全为 \(O(n^2)\)

每次在未排序的部分寻找最小, 进行 \(n-1\) 次
性能较冒泡更好

插入排序

\(O(n^2)\) 最好 O(n) 最坏 \(O(n^2)\)

维护一个已排序的部分, 重复将未排序部分的第一个元素插入到已排序部分的合适位置
较插入排序时间更优

复杂算法

希尔排序 (不稳定, 常数空间)

\(O(nlogn~n^2)\) 最好 \(O(n^1.3)\) 最坏 \(O(n^2)\)

希尔排序是插入排序的优化, 将序列分为若干个子序列 (根据某个增量跳跃分割), 对子序列进行插入排序, 增量为 1 时排序完成
增量序列为 dlta[k]=2^k-1,k 为大于等于 \(log_2(n+1)\) 的整数开始递减的时候时间复杂度 \(O(1.5)\)

堆排序 (不稳定, 常数空间)

全为 \(O(nlogn)\)

选择排序的优化
堆为每个顶点不大于 / 不小于左右孩子的完全二叉树, 分别称小顶堆 / 大顶堆
堆用数组按层序遍历顺序保存, 以完全二叉树的性质优势 \(O(1)\) 找父亲孩子
堆的建立就是由下到上分治的建立子堆 (对于每个子堆, 由顶点向下逐步)
堆的插入同理 (向上), 堆顶的 pop 是将顶删除将末尾放上来, 然后向下逐步移动

归并排序 (稳定,\(O(n)\) 空间)

全为 \(O(nlogn)\)

分治, 部分排序, 最后合并 (只介绍二路归并)
递归 sort, 归并, 非常简单
但是迭代实现更加优秀, 去掉了 \(O(logn)\) 的栈空间

快速排序 (不稳定,\(O(logn)~O(n)\) 空间)

\(O(nlogn)\) 最好 \(O(nlogn)\) 最坏 \(O(n^2)\)

与冒泡排序同属交换排序
将待排记录分割成大小两部分 (内部无序), 分治处理
递归实现, 若 l<r , 算出枢轴值 p, 调用 qsort(list,l,p-1);qsort (list,p+1,r);
关键在于如何快速找到一个值的正确绝对位置
选一个枢轴值, 双指针将大于它 / 小于它往两边放

优化

关键是如何选择枢轴值, 可以随机 (观察可能排布) 选 3 个数, 取中值
二是枢轴值不反复移动, 反正最后空格就是它的位置
三是当子序列长度小于一定值 (如 7), 可以直接插入排序
四是使用尾递归 (尾递归是递归的一种优化, 尾递归是递归函数在函数尾部修改参数值, 利用原本的栈空间再运行一次)

当记录数量小的时候, 简单排序更强, 选择排序的记录交换次数最少 (复杂算法这点都差不多) 综合来看, 优化的快排是最优选择