散列表的优缺点

• 优点是查找效率高
• 缺点是空间浪费大

散列表如何解决冲突问题

• 开放地址法：有冲突就找空位
  • 线性探测法：有冲突就顺序查找下一个空位存入。
  • 二次探测法：有冲突就按照增量序列移动位置继续探测。
  • 伪随机探测法：有冲突就随机位移几位看看是否有空位
• 链地址法：相同哈希值的记录连成一个链表

散列表的查找

依据哈希值取数，如果查到的不是目标数据，就依据事先定好的冲突方法，继续查找。

如果目标地址为空，则停止查找，说明没有相关记录。

查找

根据给定的值，在查找表中确定一个关键字等于给定值的数据元素。

• 关键字：唯一标识一个记录的关键字
• 次关键字：用以识别若干记录的关键字称之为次关键字。

查找表可以分为两类——静态查找表和动态查找表（查不到要增加，或者查到了就删除）

如何评价查找算法？

平均查找长度：也称为平均比较次数。

线性表的查找

顺序查找

也就是遍历查找

每次循环中都要判断是不是越界了，就影响效率，优化是把关键字放在表头，到头了就得到关键字，省去了每次查找的判断越界。

二分查找

• ALS（平均查找长度）=log2(n)
• 缺点:只适用于有序表，且为顺序存储结构。

分块查找

建立索引，索引指向目标附近。

适用情况：快速查找且动态变化的表。

• 优点：适用于链表。

树表之二叉排序树。

二叉排序树

二叉排序树满足以下条件：其左树的子节点值均小于该节点，右树的子节点值均大于该节点。

• 性质：中序遍历二叉排序树，得到一个递增有序的序列。
• 最多比较次数为树的深度。
• ALS的长度与树形态有关，从log2(n)到o(n)不等。

插入操作

查找直到某个叶子节点的左子树或者右子树为空为止，然后将该节点插入为该节点的子树。

删除操作

• 若节点为叶子节点，直接删除。
• 若只有一个子树，将子树替换它。
• 若有两个子树，**使用左子树中最大的值(或者右子树中最小的值)替换它，**然后对那个子节点执行删除操作。

失衡二叉树的调整

一个平衡二叉树，在增加一个节点之后，可能发生失衡，这时候就需要调整节点关系，使二叉树保持平衡。

具体操作不好文字描述，略。

Dijkstra算法

该算法核心是通过不断地将路径最短（可一步到达）的点加入到已知最短路径点的集合中。

弗洛伊德算法

拓扑排序

有向无环图：无环的有向图。

拓扑排序方法

从起始点开始，循环删除没有前驱的点，并输出这个点。

检验AOV点中是否存在环的方法：

若网中所有点都在拓扑序列中，则网中必定不存在环。

关键路径

对于AOE网，关键路径指路径长度最长的路径。

若网中某个时间的时间余量为0，则他就在关键路径上。

辅助数组

记录哪些点访问过

深度优先

1. 从某一起始顶点开始后，优先访问没有访问过的点
2. 到某一点的所有邻点都被访问后，回退，看看上一个点有没有没有访问的邻点
3. 进行与前述相似的访问逻辑

时间效率

邻接矩阵时间复杂度为O(n**2)，适合访问稠密图

邻接表时间复杂度O(n+e)，适合访问稀疏图。

广度优先

从起始点开始，访问他的一级邻居，然后访问他的二级邻居，以此类推。

时间效率

与深度优先相同。

最小生成树

生成树：不存在回路的连通图

无向图的生成树：遍历时通过的边组成的集合

最小生成树：在一个网络中，在所有生成树中，使得各边权值之和最小的生成树，也叫最小代价生成树。

MST性质

普利姆算法

构建最小生成树的方法，使用贪心算法，每次总是选择两个集合之间权值最小的边，一步步构筑最小生成树。

时间复杂度：O(n**2)

克鲁斯卡尔算法

更直接的贪心算法

直接叫所有顶点组成一个集合，在所有的边中从小到大添加到集合中，若形成环则跳过这个边，直到所有的顶点都联通。

时间复杂度O(e)

邻接表

在每一个节点的指针域，指向一个链表，记录了该点的邻节点

数据依然有冗余

无向图邻接表特点

• 邻接表不唯一
• 存储空间为O(n+2e)
• 节点的度就是单链表的节点数

有向图邻接表

• 统计出度很简单，入度很麻烦
• 逆邻接表刚好相反

十字链表

有点绕

简单来说就是将弧也作为一个个体，保存了弧的上一个弧和下一个弧。

邻接多重表

每条边只储存一次，指针比较多。

四种逻辑结构

图的定义

G=(V,E)

Graph=(Vertex,Edge)

图=顶点的有穷集合+边的有穷集合

图的种类

无向图/有向图

完全图/稠密图/稀疏图

网：边/弧带权的图

图的术语

顶点的度：与该顶点关联的边的数目，在有向图中则细分为入度和出度

路径：持续的边构成的顶点序列

连通图：任何两顶点均存在路径

子图：顶点集合或者边为父图的子集合的图

可以说是很不说人话了

人话就是，彼此不相连的，不可分割的个体。

图的遍历

分为深度优先遍历和广度优先遍历，后面展开讲

图的存储结构

邻接矩阵

建立一个顶点表存储顶点信息，再建立一个邻接矩阵记录个顶点的关系（也就是边或者弧）

• 无向图的邻接矩阵是对称的——甲能到达乙，乙自然可以到达甲（可以压缩存储空间）
• 顶点的度就是该行的“1”的数目
• 对于有向图，入度是该行“1”的数目，出度是该列的“1”的数目
• 对于有权图，不相邻的两顶点，矩阵对应值为“∞”

邻接矩阵的缺点

• 不便于增加删除
• 浪费空间（稀疏）
• 浪费时间——统计有多少边时