数据结构重点-学习笔记

1. 基本概念

数据的逻辑结构
  • 与存储无关的数据逻辑关系
  • 如线性结构、一般线性表、栈、队列、树、有向图等等
数据的存储结构
  • 计算机中的表示或者映像,也称物理结构
  • 如顺序存储、链式存储、索引存储、散列存储
数据的运算
  • 针对逻辑结构定义的运算
算法特性
  • 有穷、确定、可行
原地工作法
  • 算法需要的额外空间是常量

2. 线性表

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

3. 栈和队列

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

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

队列
  • 基本操作
      • 初始化,判断是否空,入队(EnQueue),出队(DeQueue),读队头
    • 循环队列
      • 区别队空和队满
        • 牺牲一个位置
        • 增加一个tag
    • 双端队列
栈和队列应用
  • 括号匹配:栈
    • 表达式求值:栈
      • 中缀表达式转后缀表达式
    • 层次遍历:队列
    • 缓冲:队列
数组(为啥放栈和队列章,太短了?)
  • 普通矩阵
    • 特殊矩阵
      • 对称矩阵
      • 三角矩阵
      • 三对角矩阵
      • 稀疏矩阵
    • 注意点
      • 计算后用特殊值代入以验证
易错点
  • 栈和队列具有相同的逻辑结构 – 线性结构。但有不同的运算方式。

4. 串

存储结构
  • 固定最大长度
    • 用字符数组
  • 动态长度
    • 堆分配
    • 块链
基本操作
  • 赋值,复制,判空,比较,求长,根据位置求子串内容,连接串,根据内容定位子串,清空,销毁
  • 模式匹配
    • 暴力匹配
    • KMP
      • next数组可以加1也可以不加
      • 进一步优化next为nextval

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王道数据结构考研复习指导》

Leave a Comment