「408」数据结构与算法知识归纳

该篇汇总了研究生考试计算机科学专业基础综合（408）中，数据结构与算法所要考察的知识点，用于个人复习与总结，同时希望能够帮助到需要的人。

身是菩提树，心如明镜台，时时勤拂拭，勿使惹尘埃。 ——神秀
菩提本无树，明镜亦非台，本来无一物，何处惹尘埃。 ——慧能

知识框架

*详细的思维导图见：数据结构与算法知识点思维导图

数据结构与算法在408考试中占45/150分，其对考生逻辑思维能力的考察效果显著。除计算机相关专业考研外，众互联网公司也将数据结构和算法列为重点的考察内容。

数据结构与算法的知识框架还是挺清晰的，还是有很多方法很固定的题，主要是能够理解题目内容和对相关概念十分清晰。

说一些个人的认识：我们弄一个数据结构这个东西，是为了让它对我们有用，用什么呢，用数据。先说我们是怎么用数据，其实不过增删改查（Create Retrieve Update Delete, CRUD）。我们手上拿着一打厚厚的学生档案，我们需要找个我们知道的地方放，以方便以后能找到，或者有新的档案能放进去。这就导致我们需要考虑一些问题：

但凡做事，都要考究一个效率问题，增删改查中，查是最体现效率的一个动作，因为删和改的前提都是把数据找到。那么，为了提升查的效率，让数据能更方便地被我们找到，那我们就可以对数据进行一些操作，比如让学生的档案按学号顺序堆放，这样我们就可以通过学号更方便地找到想要的学生档案。那么如果我们拿到的学生档案在存放之前是乱的，不按学号顺序排列咋办呢，这就催生出了算法这个东西，我们现在要干的事情是排序，所以需要排序算法。那我们找数据的时候是不是就一定得一个一个翻呢，是不是有更加方便的，让我们少翻几个就能找到目标数据的方法呢，这就催生了查找算法。我们在某些时候，为了更方便查找数据，特别是那些数据间看不出什么关系的数据，为了让他们产生关系，我们会在存数据的时候给每个数据多存一个字段，以便利我们的查找。但是多存的这个字段就造成了另一个问题：在保证效率的同时，怎么让占用的空间更少。

知识内容

概念、定义

这一部分的内容是为了拿到一个数据结构或者算法时，能马上在脑中想起它的大概模样。

数据结构

• 线性表：具有相同数据类型的n个数据的有限序列，n为表长。分顺序表和链表两种表示方式
• 顺序表：地址连续、依次存储
• 链表：非连续地址。因指针的数量和连接方式分三种
  • 单链表：线性表的链式存储，单个指针，只能从头往后
  • 双链表：俩指针，双向
  • 循环链表：头尾相接
• 静态链表：用数组来描述链式存储，连续内存空间，指针指向地址
• 栈：一端操作，后进先出（LIFO，Last In First Out）
• 队列：两端操作，先进先出（FILO，First In Last Out）
• 数组：由 n 个相同类型的数据元素构成的有限序列
• 矩阵的压缩存储：减少空间分配，对重复元素只分配一个，另元素不分配
  • 对称矩阵：同线性代数中的对称矩阵
  • 三角矩阵：同线性代数中的三角矩阵，分了上三角和下三角
  • 三对角矩阵：也叫带状矩阵，是沿主对角线均匀排布的元素带
• 串：字符串
  • 模式匹配：子串的定位操作
    • KMP算法：模式匹配，用一个 next[j] 数组来存放可能重复的子串以达到减少比较次数，提升匹配效率的效果
    • PS：当子串和模式串不匹配时，主指针 i 不回溯，模式串指针 j = next[j]
• 二叉树：空，或者每个结点至多俩子树，是有序树
• 有序树：左右子树点到，则成为另一颗不同的二叉树
• 满二叉树：除叶子结点外，所有结点都有俩孩子（度为2），且每层装满。是特殊的完全二叉树
• 完全二叉树：最后一层可以不满，但结点得从左排到右
• 二叉排序树(Binary Search Tree, BST)：所有结点关键字：左子树 < 根结点 < 右子树
• 平衡二叉树(Adelson-Velsky Landis, AVL)：任意结点左右子树高度差不超过 1
• 先序遍历：二叉树的遍历，根左右（NLR）。中序、后序同理
• 层序遍历：从上往下，从左往右
• 线索二叉树：也分先中后，多了俩指针，一个指向前驱，一个指向后继
• 树的表示法：反应树中结点间关系的方法
  • 双亲表示法：连续空间储存，结点设伪指针，指向双亲
  • 孩子表示法：将每个结点的孩子用单链表链接起来
  • 孩子兄弟表示法(二叉树表示法)：左侧连最左边的孩子，右边连这个孩子的兄弟（左孩子右兄弟）
• 带权路径长度（Weight Path Length, WPL）：从树的根到任意结点的路径长度与该结点上权值的乘积：

$$WPL = \displaystyle\sum_{i=1}^n w_i l_i$$

• 哈夫曼树：WPL 最小的二叉树（最优二叉树）
• 并查集：{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}，用以查询某个元素是否在集合中，并且能够知道是在哪个集合中而形成的集合。而它- 的维护对象是多个集合
  • 并查集可以进行集合合并的操作（并）
  • 并查集可以查找元素在哪个集合中（查）
  • 并查集维护的是一堆集合（集）
• 有向图：边为有向边（弧）带箭头，<v, w> <w, v>
• 无向图：边为无向边，(v, w) (w, v)
• 子图：用某图的顶点和边构成的图
• 生成子图：包含原图所有顶点的子图
• 连通：无向图，两顶点有路径，则连通；任意两顶点连通，就是连通图
• 连通分量：无向图的极大连通子图
• 强连通：有向图，两顶点往返都有路径。则强连通；任意两顶点强连通，就是强连通图
• 强连通分量：有向图的极大强连通子图
• 完全图：无向图中任意两顶点间都有边，有向图中任意两顶点间都有方向相反的两条弧
• 生成树：包含全部顶点的一个极小连通子图
• 回路（环）：A -> … -> A
• 简单路径：顶点不重复的路径
• 简单回路：除起始顶点外，顶点不重复的回路
• 有向树：一个顶点入度为 0，其余顶点入度为 1
• 图的存储：
  • 邻接矩阵法：用二维数组储存顶点间邻接关系，适合稠密图
  • 邻接表法：每个顶点建立一个单链表，指针指向相邻顶点，适合稀疏图
  • 十字链表法：有向图的一种链式存储结构
  • 邻接多重表：无向图的一种链式结构
• 图的遍历：
  • 广度优先搜索/遍历(Breadth-First-Search, BFS)：找到与一个顶点相邻的所有顶点，标记哪些顶点被访问过，需要一个辅助队列
  • 深度优先搜索/遍历(Depth-First-Search, DFS)：相邻顶点一个一个找，找完一条再找未被访问的顶点，需要一个递归工作栈
• 最小生成树(Minimum-Spanning-Tree, MST)：连通图的生成树，要求边的权值之和最小。最小生成树不唯一
  • Prim(普里姆)算法：将一离集合最近的顶点放入集合
  • Kruskal(克鲁斯卡尔)算法：每次选择一二叉排序树：条权值最小的边，使这条边两头连通
• 最短路径：
  • Dijkstra(迪杰斯特拉)算法：求一个点到其他任意点的最短路径。类似 Prim，只是每次找下一个顶点的时候会计算一下到已知点的最短路径是否变化。负权值边不适用
  • Floyd(弗洛伊德)算法：求各顶点之间的最短路径。递推生成 n 阶方阵，每次以其中一顶点作为中间顶点，更新方阵。负权值边适用，但不能组成回路
• 有向无环图(Directed Acyclic Graph, DAG)：没有环的有向图
• 顶点表示活动的网络(Activity On Vertex Network, AOV)：DAG 图表示工程，其顶点表示活动
• 拓扑排序：DAG 只有从前往后，无从后往前
• 用边表示活动的网络(Activity On Edge Network, AOE)：带权有向图中，顶点表示事件，有向边表示活动，边上的权值表示完成活动的开销（其实类似土木工程经济与项目管理中的工程进度网络图，包括其中的最早发生时间、最迟开始排序时间、关键路径等，都与单代号或者双代号网络图的计算类似）
• 关键路径：从头到尾，路径最大的一条路径，其上的活动称为关键活动

算法

查找

• 平均查找长度(Avarage Search Length, ASL)：所有查找过程中进行关键字比较次数的平均值

$$ASL = \displaystyle\sum_{i=1}^n P_i C_i$$

• 顺序查找：也叫线性查找，就是从头到尾挨个看
• 折半查找：也叫二分查找，有（low，mid，high）指针，每次取中值向目标值靠
• 分块查找：也叫索引顺序查找，将表分块，要求块内可以无序，但块间必须有序。先在块间用顺序或折半，在块内顺序
• 红黑树(RBT)：
  • 每个结点不是红就是黑
  • 根结点、叶结点黑
  • 没有相邻红结点
  • 每个结点到任意叶结点的简单路径所含黑结点数量相同
• B 树：也叫多路平衡查找树，所有结点的孩子个数最大值称 B 树的阶
  • 每个结点至多 m 棵子树，之多含 m-1 个关键字
  • 若根结点不是终端结点，则至少有两棵子树
  • 所有叶结点出现在同一层
• B+ 树：与B 树差异在于，分值结点包含他的各子结点中关键字的最大值，且所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序互相链接起来
• 散列表：也叫 Hash 表，就是将查找表中的关键字通过一个散列函数（Hash 函数）映射称一个地址

排序

• 插入排序：
  • 直接插入排序：找到插入的位置，该位置后面的所有元素依次后移，然后插入元素
  • 折半插入排序：相对直接插入排序，只是找位置的时候使用折半查找
  • 希尔排序：先按一步长分若干子表，子表直接插入排序，然后减小步长重复操作，直到步长为 1
• 交换排序：
  • 冒泡排序：从前往后（或相反），两两比较，找出最值，重复操作
  • 快速排序：取一枢纽（pivot），取值比较，小左大右（或相反），左右再重复操作
• 选择排序：
  • 简单选择排序：遍历全表，找其最值，固定趟数
  • 堆排序：大根堆，使小元素不断「下坠」，小根堆相反
    • 堆：Heap，顺序存储的完全二叉树
• 归并排序：将两个或以上的有序表组合成为一个新的有序表
• 基数排序：按照关键字的数位（个位、十位、百位……）依次进行排序
• 外部排序：对磁盘中的数据进行的排序

时间空间复杂度

算法的时间复杂度和空间复杂度是评价算法效率的重要手段，前者体现算法语句的频度，评价算法速度；后者评价算法所消耗的存储空间。

我们使用 O 表示法来量化地表示（其实 O 符号应该类似高等数这部分而学中，高阶无穷小的表示法，它更关注高阶部分带来的影响，而忽略低阶部分）

这一部分的内容主要是汇总各算法时间、空间复杂度，以方面查询，但并不鼓励死记硬背

算法种类	时间复杂度(最好/平均/最坏)	空间复杂度	稳定性
顺序表插入/删除/查找	$O(1)/O(n)/O(n)$	-	-
单链表头插法/尾插法	$O(n)$	-	-
单链表按序号/按值查找	$O(n)$	-	-
单链表插入/删除/求表长	$O(n)$	-	-
简单模式匹配	$O(nm)$	-	-
KMP算法	$O(n+m)$	-	-
二叉树的遍历	$O(n)$	-	-
邻接矩阵法	-	$O(n^2)$	-
邻接表法	-	$O(V+2E)$	-
BFS算法	邻接表$O(V+E)$/邻接矩阵$O(V^2)$	$O(V)$	-
DFS算法	邻接表$O(V+E)$/邻接矩阵$O(V^2)$	$O(V)$	-
Prim算法	$O(V^2)$	-	-
Kruskal算法	$O(E\log E)$	-	-
Dijkstra算法	$O(V^2)$	-	-
Floyd算法	$O(V^3)$	-	-
拓扑排序	邻接表$O(V+E)$/邻接矩阵$O(V^2)$	-	-
折半查找	$O({\log }_{2}n)$	$O(1)$	-
直接插入排序	$O(n)/O(n^2)/O(n^2)$	$O(1)$	是
冒泡排序	$O(n)/O(n^2)/O(n^2)$	$O(1)$	是
简单选择排序	$O(n)/O(n^2)/O(n^2)$	$O(1)$	否
希尔排序	-	$O(1)$	否
快速排序	$O(n{\log }_{2}n)/O(n{\log }_{2}n)/O(n^2)$	$O({\log }_{2}n)$	否
堆排序	$O(n{\log }_{2}n)/O(n{\log }_{2}n)/O(n{\log }_{2}n)$	$O(1)$	否
二路归并排序	$O(n{\log }_{2}n)/O(n{\log }_{2}n)/O(n{\log }_{2}n)$	$O(n)$	是
基数排序	$O(d(n+r))/O(d(n+r))/O(d(n+r))$	$O(r)$	是

声明

该文写作初衷是为了帮助自己复习总结学习的内容，其中不乏有错误荒谬之处，还请读者见谅，并恳请读者予以斧正，不吝赐教。

文中部分文字、图表为个人所作，更多想表达自己的理解。如果能对读者有所启发，则为甚好，若认为我的想法有所不妥也请勿强行理解。

参考文献

[1] 王道论坛组.2023年数据结构考研复习指导.北京:电子工业出版社,2021.
[2] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,2009.
[3] 王道计算机考研b站课程,2020.
[4] 帅地.什么是并查集？有哪些应用？[OL].腾讯云开发者社区,2019.