散列表
散列表的优缺点 优点是查找效率高 缺点是空间浪费大 散列表如何解决冲突问题 开放地址法：有冲突就找空位 线性探测法：有冲突就顺序查找下一个空位存入。 二次探测法：有冲突就按照增量序列移动位置继续探测。 伪随机探测法：有冲突就随机位移几位看看是否有空位 链地址法：相同哈希值的记录连成一个链表 散列表的查找依据哈希值取数，如果查到的不是目标数据，就依据事先定好的冲突方法，继续查找。 如果目标地址为空，则停止查找，说明没有相关记录。
线性表与树表
查找根据给定的值，在查找表中确定一个关键字等于给定值的数据元素。 关键字：唯一标识一个记录的关键字 次关键字：用以识别若干记录的关键字称之为次关键字。 查找表可以分为两类——静态查找表和动态查找表（查不到要增加，或者查到了就删除） 如何评价查找算法？平均查找长度：也称为平均比较次数。 线性表的查找顺序查找也就是遍历查找 每次循环中都要判断是不是越界了，就影响效率，优化是把关键字放在表头，到头了就得到关键字，省去了每次查找的判断越界。 二分查找 ALS（平均查找长度）=log2(n) 缺点:只适用于有序表，且为顺序存储结构。 分块查找建立索引，索引指向目标附近。 适用情况：快速查找且动态变化的表。 优点：适用于链表。 树表之二叉排序树。二叉排序树二叉排序树满足以下条件：其左树的子节点值均小于该节点，右树的子节点值均大于该节点。 性质：中序遍历二叉排序树，得到一个递增有序的序列。 最多比较次数为树的深度。 ALS的长度与树形态有关，从log2(n)到o(n)不等。 插入操作查找直到某个叶子节点的左子树或者右子树为空为止，然后将该节点插入为该节点的子树。 删除操作 若 ...
最短路径，拓扑排序，关键路径
Dijkstra算法该算法核心是通过不断地将路径最短（可一步到达）的点加入到已知最短路径点的集合中。 弗洛伊德算法 拓扑排序有向无环图：无环的有向图。 拓扑排序方法 从起始点开始，循环删除没有前驱的点，并输出这个点。 检验AOV点中是否存在环的方法：若网中所有点都在拓扑序列中，则网中必定不存在环。 关键路径对于AOE网，关键路径指路径长度最长的路径。 若网中某个时间的时间余量为0，则他就在关键路径上。
图的遍历与最小生成树
辅助数组记录哪些点访问过 深度优先 从某一起始顶点开始后，优先访问没有访问过的点 到某一点的所有邻点都被访问后，回退，看看上一个点有没有没有访问的邻点 进行与前述相似的访问逻辑 时间效率邻接矩阵时间复杂度为O(n**2)，适合访问稠密图 邻接表时间复杂度O(n+e)，适合访问稀疏图。 广度优先从起始点开始，访问他的一级邻居，然后访问他的二级邻居，以此类推。 时间效率与深度优先相同。 最小生成树生成树：不存在回路的连通图 无向图的生成树：遍历时通过的边组成的集合 最小生成树：在一个网络中，在所有生成树中，使得各边权值之和最小的生成树，也叫最小代价生成树。 MST性质 普利姆算法构建最小生成树的方法，使用贪心算法，每次总是选择两个集合之间权值最小的边，一步步构筑最小生成树。 时间复杂度：O(n**2) 克鲁斯卡尔算法更直接的贪心算法 直接叫所有顶点组成一个集合，在所有的边中从小到大添加到集合中，若形成环则跳过这个边，直到所有的顶点都联通。 时间复杂度O(e)
图的存储结构
邻接表 在每一个节点的指针域，指向一个链表，记录了该点的邻节点 数据依然有冗余 无向图邻接表特点 邻接表不唯一 存储空间为O(n+2e) 节点的度就是单链表的节点数 有向图邻接表 统计出度很简单，入度很麻烦 逆邻接表刚好相反 十字链表 有点绕 简单来说就是将弧也作为一个个体，保存了弧的上一个弧和下一个弧。 邻接多重表 每条边只储存一次，指针比较多。
图和他的邻接矩阵表示法
四种逻辑结构 图的定义G=(V,E) Graph=(Vertex,Edge) 图=顶点的有穷集合+边的有穷集合 图的种类无向图/有向图 完全图/稠密图/稀疏图 网：边/弧带权的图 图的术语顶点的度：与该顶点关联的边的数目，在有向图中则细分为入度和出度 路径：持续的边构成的顶点序列 连通图：任何两顶点均存在路径 子图：顶点集合或者边为父图的子集合的图 可以说是很不说人话了 人话就是，彼此不相连的，不可分割的个体。 图的遍历分为深度优先遍历和广度优先遍历，后面展开讲 图的存储结构邻接矩阵建立一个顶点表存储顶点信息，再建立一个邻接矩阵记录个顶点的关系（也就是边或者弧） 无向图的邻接矩阵是对称的——甲能到达乙，乙自然可以到达甲（可以压缩存储空间） 顶点的度就是该行的“1”的数目 对于有向图，入度是该行“1”的数目，出度是该列的“1”的数目 对于有权图，不相邻的两顶点，矩阵对应值为“∞” 邻接矩阵的缺点 不便于增加删除 浪费空间（稀疏） 浪费时间——统计有多少边时
哈夫曼树及其应用
路径从书中一个节点到另一个节点之间的分支构成两个节点的路径 结点的路径长度两节点间路径的分支 树的路径长度从树根到每一个结点的路径之和 节点数目相等时，完全二叉树最路径长度最短 节点的带权路径长度路径长度x权重 树的带权路径长度所有结点的带权路径长度之和 哈夫曼树带权路径长度最小的二叉树 哈夫曼树的构造方法 说人话就是从小到大，合并（搭建）哈夫曼树 需要注意的是，每次合并，都是选择权值最小的两个树（无论是否为单节点） 哈夫曼编码 构造不等长的前缀编码