数据结构重点-学习笔记

1. 基本概念

数据的逻辑结构

• 与存储无关的数据逻辑关系，仅对外业务逻辑关心。
• 如线性结构、一般线性表（有序表）、栈、队列、树、有向图、集合等等

数据的存储结构

• 计算机中的表示或者映像，也称物理结构，业务逻辑不用关心，实现业务逻辑时才关心。
• 如顺序存储（和线性、有序区别开）、链式存储、索引存储、散列存储

数据的运算

• 针对逻辑结构定义的运算

算法特性

• 有穷、确定、可行

原地工作法

• 算法需要的额外空间是常量

2. 线性表

顺序存储

• 算法
  • 用 3 次逆置来循环移动（无需额外空间）

链式

• 种类
  • 单双链表
  • 是否带头节点
  • 是否循环链表
  • 静态链表
  • 有趣问题
    • 判断单链表是否有环

3. 栈和队列

栈

• 基本操作
  • 初始化，判断是否空栈，进栈，出栈，读栈顶元素
• 特殊结构
  • 共享栈
• 出栈序列的可能数量：卡特兰数

\begin{align}
\frac{1}{n+1}\dbinom{2n}{n}
\end{align}

队列

• 基本操作
  • • 初始化，判断是否空，入队（EnQueue），出队（DeQueue）,读队头
  • 循环队列
    • 区别队空和队满
      • 牺牲一个位置
      • 增加一个tag
  • 双端队列

栈和队列应用

• 括号匹配：栈
  • 表达式求值：栈
    • 中缀表达式转后缀表达式
  • 层次遍历：队列
  • 缓冲：队列

数组（为啥放栈和队列章，太短了？）

• 普通矩阵
  • 特殊矩阵
    • 对称矩阵
    • 三角矩阵
    • 三对角矩阵
    • 稀疏矩阵
  • 注意点
    • 计算后用特殊值代入以验证

易错点

• 栈和队列具有相同的逻辑结构 – 线性结构。但有不同的运算方式。

4. 串

存储结构

• 固定最大长度
  • 用字符数组
• 动态长度
  • 堆分配
  • 块链

基本操作

• 赋值，复制，判空，比较，求长，根据位置求子串内容，连接串，根据内容定位子串，清空，销毁
• 模式匹配
  • 暴力匹配
  • KMP 算法
    • next 数组最直接的记录内容为对应字符匹配失败时，需移动目标穿越指针指目标串的位置。

5. 树与二叉树

术语

• 前驱
  • 双亲（父节点）
• 后继
  • 直接孩子节点
• 祖先、子孙、双亲（父节点）、孩子、兄弟
• 度
  • 节点孩子的个数
• 深度
  • 自根节点向下
• 高度
  • 自叶节点向上
• 层次
  • 按深度划分
• 有序树
  • 不能交换孩子顺序
• 路径
  • 两节点经过的节点序列
• 路径长度
  • 路径对应的边的个数
• 树的路径长度
  • 根节点到每个节点的路径长度总和

节点和度的关系

• 当总节点数量为 \(n_{total}\) ， 度为 i 的节点的个数为 \(n_i\)，且节点最大的度为 k 时，从度的角度出发有

\begin{cases}
n_{0} &= \sum_{i = 2}^{i = k}(i – 1)*n_i + 1 \\
n_{total} &= \sum_{i = 0}^{i = k}n_i
\end{cases}

• 特别对于二叉树而言

\begin{cases}
n_{0} &= n_2 + 1 \\
n_{total} &= n_0 + n_1 + n_2
\end{cases}

• 结合起来可以解决大部分问题
• 注意点
  • 计算时找特例，或者找特例验证

二叉树

• 特殊类别
  • 满二叉树
  • 完全二叉树
• 存储结构
  • 顺序
  • 链式
• 遍历
  • 二叉树遍历
  • 线索二叉树

树和森林

• 存储结构
  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法
• 树森林与二叉树的转换
• 注意点
  • 对树而言，由于不会没有大儿子只有小儿子的情况，先根序和后跟序可以唯一的确定一棵树，这和二叉树不同（二叉树可以只有右儿子没有左儿子）。

树与二叉树的应用

• 普通二叉排序树
• 平衡二叉树
  • 默认平衡因子为左树高度减右树高度
  • 高度为 h 的平衡二叉树最少节点数量为（思路相当于生成一棵最不平衡的平衡二叉树，此时所有非叶子节点的平衡因子绝对值为1）

$$n_h = \begin{cases}
1 &,h = 1 \\
2 &,h = 2 \\
n_{h-1} + n_{h-2} +1 &,h > 2
\end{cases}$$

• 哈夫曼树和哈夫曼编码
  • 可变长编码
  • 前缀编码
  • 度为m的哈夫曼树
    • 每个节点的度要么0要么m

6. 图

图定义

• 有向图
• 无向图
• 简单图
  • 无重复边，无顶点到自身的边
• 多重图
  • 与简单图相对
• 完全图
  • 任意两个顶点正反直连
  • 不等同于强连通图
• 子图
  • 顶点和边都是子集
• 连通
• 连通图
• 连通分量
  • 无向图中最大连通子图
  • 连通分量是子图不是量
• 强连通图
  • 有向图中任意两个顶点都有以各自为起点的路径连通
  • 不等同于完全图
• 强连通分量
• 生成树
  • 含全部顶点的极小连通子图，一定为树
• 度
  • 入度和出度
• 带权图
• 稠密/稀疏图
• 路径
  • 顶点序列
  • 路径长度（经过的边）
  • 回路或环
    • 路径的第一个节点和最后一个节点相同
  • 距离
    • 最短路径
• 有向树
  • 除一个顶点以外，其余顶点的入度都为1

图存储

• 邻接矩阵
  • 无向图的邻接矩阵对称，存储时仅需存储一半
  • 带权邻接矩阵
    • 0 与 \(\infty\) 都视为不存在边
  • 特殊性质
• 邻接表
• 十字链表
  • 每个节点和弧都有专门的节点
  • 方便求入度和出度
• 邻接多重表

图基本操作

• 判断是否存在边(Adjacent)，列出相邻的边(Neighbors)，插入顶点，删除顶点，添加边，删除边，第一个邻居，获取边的权值，设置边的权值
• 遍历
  • 广度优先搜索(Breath-First-Search,BFS)
    • 广度优先生成树
    • 单源最短路径问题
  • 深度优先搜索
    • 深度优先生成树
  • 连通性

图的应用

• 最小生成树(minimum-spanning-tree,MST)
  • 所有弧的权值总和最小的树
  • Prim算法
    • 找到集合最短的且不在集合内的点加入
    • 适合边多点少
  • Kruskal算法
    • 将边按长度排序，从短到长依次检查
    • 适合点少边多
  • Dijkstra算法
    • 类似Prim，只是距离都以到单点进行计算
  • Floyd算法
    • 求所有点到所有点
    • 先不中转长度，再检查可中转1次的最短长度，再检查可中转2次的最短长度，直到n次
• 有向无环图
  • DAG 图(Directed Acyclic Graph)
    • 拓扑排序
      • 必须找没有前驱的点作为开始
    • 表达式
  • AOV 网（Activity On vertex Network）
    • 点为事件
    • 边仅为逻辑关系，没有权值
  • AOE 网（Activity On Edge Network）
    • 点为事件
    • 边为时间代价
    • 特征
      • 事件最早发生时间
      • 事件最迟发生时间
      • 活动最早开始时间
      • 活动最迟发生时间p
      • 活动时间余量
      • 关键路径

易错点

• 邻接表指链表，邻接矩阵才指矩阵数组

7. 查找

基本概念

• 静态/动态 查找表
• 平均查找长度

基本查找方式

• 顺序查找
  • 最无脑的查找
  • 可设置“哨兵”，减少循环中的判断
• 有序表顺序查找
• 折半查找
  • 折半查找判定树
    • 判断一个形态是否能成为折半查找判定树
      • 满足平衡二叉树形态
      • 由于二分取下标区间 \([a,b]\) 中点时，要么是 \(\lfloor\frac{a+b}{2}\rfloor\)，要么是 \(\lceil\frac{a+b}{2}\rceil\)，总之不会两者混用，所以可以手动按中序标出下标，检查形态对应的算法是否有混杂
• 分块查找
• B树
• B+树
  • 节点关键字数量和子树数量一致
• 散列表
  • 散列函数
    • 直接定址法
    • 除留余数法
    • 数字分析法
    • 平方取中法
  • 冲突处理
    • 开放定址：
      • 冲突后加一个增量，增量可以是线性也可以是平方增加，也可以是再散列法确定下一位地址，或者是伪随机序列定址
    • 拉链法
  • 装填因子 = 表中记录数n / 散列表长度m

易错点

• 顺序查找时，无论是否有序，查找成功的平均时间是相同的，仅失败的平均时间有差异。

8. 排序

基本概念

• 分类
  • 根据元素是否全在内存：内部排序，外部排序
    • 归并排序为外部排序
  • 根据同关键字元素是否顺序被破坏：不稳定排序，稳定排序
    • 稳定只关乎分类，和好坏无关

具体算法

• 插入排序
  • 思想
    • 将后方新元素插入前方已经排好的序列
  • 直接插入排序
    • 稳定
    • 从短至长版的冒泡
    • 特征
      • 某一端内部有序化
  • 折半插入排序
    • 稳定
    • 特征
      • 某一端内部有序化
  • 希尔排序
    • 不稳定
    • 时间复杂度约为 \(O(n^{1.3})\)
    • 按步长间隔分组，而非直接画区间分组
    • 缩短步长至1
    • 判断特征
      • 间次有序化
• 交换排序
  • 思想
    • 通过比较和交换两元素位置排序
  • 冒泡排序
    • 稳定
    • 判断特征
      • 某一段不断有序化
    • 如果某一趟没有发生交换，则已经有序
  • 快速排序
    • 不稳定
    • 平均性能最优
    • 当原序列接近有序时，效果最差
    • 判断特征
      • 每次可以把基准元素放在最终位置
• 选择排序
  • 思想
    • 每一次在后方选最大或最小的，交换至未排好区间的最前方位置
  • 简单选择排序
    • 不稳定
  • 堆排序
    • 不稳定
    • 由根与子树比较和改动
    • 建堆时间复杂度 \(O(n)\)
    • 排序时间复杂度无论好坏情况均为 \(O(nlog_2n)\)
• 归并排序
  • 稳定
  • 时间复杂度 \(O(n log_2 n)\)
  • 空间复杂度 \(O(n)\)
  • \(n\) 路归并
    • 每次归并 \(n\) 组元素
• 基数排序
  • 稳定
  • 思想
    • 基于稳定收集和拼接操作，从低优先级关键字至高优先级关键字依次收集和拼接
  • 空间复杂度 \(O(r)\)，其中 \(r\) 为关键字集合大小。
  • 时间复杂度 \(Od(r+n)\) ，其中 \(d\) 为关键字的不同数量。
• 外部排序
  • 选用归并的原因
    • 可以将归并完成的部分随时存回外部，无需等待全部完成再存回
    • 归并时仅需少量外部，无需全部取出
  • 多路平衡归并
    • 解决问题：为减少 I/O，而增大归并路数后会增大内部归并时间。
    • 败者树：类似堆的思想
  • 置换-选择排序
    • 目标：减少初始归并段数量
    • 缓冲段选择排序思路
  • 最佳归并树
    • 在经过 置换-选择 排序后会得到长度不等的多个段，可以利用类哈夫曼树的思想，以最少的比较次数完成后续归并，不过这里会用多叉树
    • 当节点数量不足时，需要增添长度为0的虚段

9. 参考资料

《2021王道数据结构考研复习指导》