数据结构

原创Xenny约 1219 字大约 5 分钟

数据结构

2024考研「数据结构」笔记&复习要点。
完整笔记见考研数据结构open in new window，本文是一个简要大纲。

概论

复杂度

时间复杂度
- 常规的直接数
- 循环嵌套最好展开算前n项和和N的量级关系

线性表

双链表

前驱指针|数据|后继指针

顺序表

$O(1)$ 随机存取， $O(n)$ 增删。

栈、队列和数组

栈

入栈、出栈序列可相互判断是否可能

数组

稀疏矩阵
- 存储行数、列数和三元组

树

遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
定二求一
- 通过一个找到根，分割另一个序列
- 依次类推从根建树
- 得到新的遍历序列

哈夫曼树

带权路径长度为经过边数*权值
加权平均长度即带权长度和/权值和

哈夫曼编码

编码按是否等长分为：固定长度编码和可变长度编码
若前缀串无歧义（无须分隔符）则称为前缀编码
哈夫曼编码即根结点到每个结点的路径编码（例如左0右1），是一种可变长度前缀编码
哈夫曼树的WPL为二进制编码长度，构造出的哈夫曼树可能不同，但WPL一定相同。

图

存储

邻接矩阵
- 一维数组存储顶点信息，二位数组存储边的信息（带权图可以用0或 $\infty$ 代表不可达）
- 空间复杂度 $O(n^2)$
- 第 $i$ 行和代表第 $i$ 个顶点出度，第 $i$ 列和代表第 $i$ 个顶点入度

分类

无向图
- $|V| > |E|+1$ 一定不连通

搜索

BFS
- 若边权均为1，可得到 $v_s$ 到其他顶点的最短路径

最小生成树

最小边权和的连通子图

AOE网

性质
- 顶点表示时间，边表示活动，权值表示活动开销
- 只有顶点开始之后，该顶点出边的活动才能开始
- 只有顶点入边全部结束后，该顶点事件才能开始
- AOE中仅有一个入度为0的点（源点），仅有一个出度为0的点（汇点）
计算
- 最早开始时间 $ve(k)=\max\{ve(j) + W(v_j,v_k)\}$
- 最迟开始时间 $vl(k) = \min\{vl(j) - W(v_k,v_j)\}$
- 活动时间余量 $d(i) = vl(j) - ve(i) - W(i, j)$

查找

折半查找

平均成功长度为 $\log_2{(n+1)}-1$
最坏比较次数 $\lceil\log_2{n+1}\rceil$

散列表

散列函数

直接定址法
- H(key) = key或H(key)=a*key + b
- 计算简单不会冲突，适合关键字连续，否则会浪费空间。
除留余数法
- H(key) = key%p
- p为素数使关键字能够均匀分布
数字分析法
- 设r进制关键字，选取分布较均匀的若干位作为散列地址
- 需要已知关键字集合，更换关键字后需重新构造散列函数
平方取中法
- 取平方值中间几位
- 适合关键字每位都不均匀或小于散列地址位数时

冲突处理

开放定址法 $H_i = (H(k) + d_i) \bmod{m}$ $H_{i} = (H (k) + d_{i}) mod m$
- 线性探测法
  - $d_i=0,1,2,\dots,m-1$
  - 可能元素堆积，降低查找效率
- 平方探测法（二次探测法）
  - $d_i=0^2,1^2,-1^2,2^2,-2^2,\dots,k^2,-k^2,\ k\le m/2$
  - 要求 $m=4k+3$ 且为素数
  - 不能探测所有单元，但能至少探测一半
- 双散列法
  - $d_i = i\cdot H_2(k)$
  - 利用另一个散列函数计算增量序列
- 伪随机序列法
  - $d_i$ 等于伪随机序列
拉链法
- 冲突的关键字存储到线性表
开放定址不会删除元素，因为查找需要依赖冲突二次定位，所以求ASL时删除的算作正常元素求
影响ASL的因素
- 装填因子
- 散列函数
- 冲突解决策略

排序

分类

稳定：插入、冒泡、归并和基数排序
不稳定：简单选择、快速、希尔和堆排序

插入排序

直接插入排序（稳定）
- 从列表开始维护一个有序子序列直至完全有序
- 复杂度
  - 空间复杂度 $O(1)$
  - 时间复杂度：平均 $O(n^2)$
  - 最好：已经有序，元素较少，此时 $O(n)$

交换排序

快速排序（不稳定）
- 每次划分以 $p$ 为枢轴，小的放左边，大的放右边
- 不会产生有序子序列，但每次划分能将 $p$ 放在正确的位置
- 空间复杂度
  - 需要递归调用， $O(\log_2n)$ 栈空间，最坏 $O(n)$ 栈空间
- 时间复杂度
  - 平均 $O(n\log_2n)$
  - 最好：随机数据
  - 最坏：基本有序或基本逆序 $O(n^2)$ 时间， $O(n)$ 空间