【数据结构期末例题】

前言

  本文是博主自己在准备学校数据结构考试时的总结，各个知识点都贴有对应的详细讲解文章以供大家参考；当然文中还有许许多多的截图，这些是博主对主要内容的摘取，对于那些基础较好的同学可以直接看截图，减少跳转对应文章浏览全文的时间，感谢本文引用文章的各位大佬，希望可以让更多同学看到这些优质文章并且得以受益。

---

1.KMP算法

求next数组（存储的是序号）：

1. 对数据进行编号，从1开始；
2. 前两个必定为 0,1；
3. 往后字符：找它的前一个和前一个的next数组对应序号的字符进行比较；
4. 若不相同，则继续找前一个的next所对应的next，若相等，则所需位的next为当前比较字符的next值加1；
5. 若果到第一个都没有匹配，则next为1。
   
   本部分截图来源：讲解例题

---

2.二叉树

堆

知识点参考文章：堆与二叉树

二叉排序树/二叉搜索树/二叉查找树

AVL树

自平衡二叉查找树

补充：二叉线索树

任然采用左右孩子的存储形式，
当该节点的左孩子为空时可以指向它的前驱节点，
当该节点的右孩子为空时可以指向它的后继节点。
二叉线索树根据遍历顺序的不同会有所改变。

二叉树和森林的转换

---

3.折半查找

判定树：查找数据的路程图。

---

4.哈夫曼树

举个栗子：

---

5. 排序

一轮希尔排序：eg:步长为4的时候进行一次完整的插入排序，而非只进行一轮插入排序。

---

6.哈希表

重点知识：哈希冲突 和 平均查找时间

哈希冲突



哈希冲突优质文章：解决哈希冲突的四种方法
截图来源：数据结构 哈希表

平均查找时间
如果查找每个元素的概率相同，则查找各个元素的平均查找时间（或者平均查找次数）
举例：链地址法：
各个节点在对应链表上的位置的累加和。

---

7.广义表

表头、表尾

截图来源文章：广义表的表头和表尾是什么？

长度、深度

长度：包含数据元素（原子或子表）个数；
深度：最多嵌套括号层数。

截图来源文章：广义表的广度（长度）和深度的计算

---

8.图

图中顶点与边的关系

上方截图来自：图中结点、边和度之间的关系总结

顶点的度

无向图：顶点的度为顶点具有边的条数；
有向图：分为入度和出度，有向图顶点的度为入度和出度之和。
其实都是顶点具有边的条数。

连通与强连通

连通讲的是：无向图
强连通讲的是：有向图

截图来源：强连通分量

关键路径

关键路径：从源点到终点的最长路径。

优质文章：数据结构 – 关键路径详解

---

9.邻接矩阵与邻接表

邻接矩阵
对于图 G=(V, E) 而言，其中 V 表示顶点集合，E 表示边集合。

1. 申请一个大小为O(n^2)的二维数组，来存放节点之间的连通关系以及权值（不需要存放权值的直接使用bool值表示）；
2. 无向图的邻接矩阵是关于主对角线对称的，因此可以只存储一半关系来节省空间；

行表示该节点的出度，
列表示该节点的入度。

邻接表

使用邻接表需要申请[V]个列表

1. 每个列表存储所有从顶点出发的所以相邻顶点，列表总存储顶点数为[E]；
2. 无向图的列表总存储顶点数为2*[E]。
   

两者的比较

根据邻接表和邻接矩阵的结构特性可知，当图为稀疏图、顶点较多，即图结构比较大时，更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时，或者不需要记录图中边的权值时，使用邻接矩阵作为存储结构较为合适。

深度优先遍历 和 广度优先遍历

遍历方法：

例题

最小生成树

最小生成树概念：带权值的图中，连接所有顶点后花费最小的生成树。
注意：不同算法得到的最小生成树可能相同也可能不同。

优质文章：数据结构–最小生成树详解

---

10.拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

注意：只有有向无环图才有拓扑排序。

---

细碎知识点补充

---