实际上就是我们在一个复杂的地图中寻找一条能够从起点到达终点的路径。可以看到从起点开始，每到一个路口，可能都会出现多个分叉，可能有的分叉就会走进死胡同，有的分叉就会走到下一个路口。 那么我们人脑是怎么去寻找到正确的路径呢？ 我们首先还是会从起点开始看，我们会尝试去走分叉路的每一个方向，如果遇到死胡同，那么我们就退回到上一个路口，再去尝试其他方向，直到能一直往下走为止。经过不断重复上述的操作，最后我们就肯定能够到达迷宫的出口了。 而图的搜索，实际上也是类似于迷宫这样的形式，我们需要从图的某一个顶点出发，去寻找到图中对应顶点的位置，这一部分，我们将对图的搜索算法进行讨论。 深度优先搜索（DFS
前面我们介绍了图的一些基本概念，我们接着来看如何在程序中对图结构进行表示，这一部分可能会涉及到某些在《线性代数》这门课程中出现的概念。 邻接矩阵 有向图邻接矩阵 邻接矩阵实际上就是用矩阵去表示图中各顶点之间的邻接关系和权值。假设有一个图 $G=(V,E)$，其中有N个顶点，那么我们就可以使用一个N×N的矩阵来表示，比如下面有A、B、C、D四个顶点的图： 此时我们需要使用邻接矩阵来表示它，就像下面这样： 对于一个不带权值的图来说： $$G_{ij} = \begin{cases} 1, & \text{无向图的 } (v_i, v_j) \text{ 或有向图
地图盘根错节，错综复杂，不同的道路相互连接，我们可以自由地从这些道路通过，从一个地点到达另一个地点。当然除了地图，我们的计算机网络、你的人际关系网等等，这些都可以用图结构来表示。 图也是由多个结点连接而成的，但是一个结点可以同时连接多个其他结点，多个结点也可以同时指向一个结点，跟我们之前讲解的树结构不同，它是一种多对多的关系： 它比树形结构更加复杂，没有明确的层次关系，结点与结点之间的连接关系更加自由，图结构是任意两个数据对象之间都有可能存在某种特定关系的数据结构。 基本概念 图（Graph）一般由两个集合共同构成，一个是非空但是有限的顶点集合V（Vertex），另一个是描述顶点之间连接关
什么是哈希冲突 前面我介绍了哈希函数，通过哈希函数计算得到一个目标的哈希值，但是在某些情况下，哈希值可能会出现相同的情况： 这种情况，我们称为哈希碰撞（哈希冲突） 这种情况是不可避免的，我们只能通过使用更加高级的哈希函数来尽可能避免这种情况，但是无法完全避免。当然，如果要完全解决这种问题，我们还需要去寻找更好的方法。 线性探测法 我们可以选择退让，不去进行争抢，我们可以去找找哈希表中相邻的位置上有没有为空的，只要哈希表没装满，那么我们肯定是可以找到位置装下这个元素的，这种类型的解决方案我们统称为线性探测法 既然第一次发生了哈希冲突，那么我们就继续去找下一个空位： $$h_i(\text{
我们之前认识的查找算法，最快可以达到对数阶 $O(logN)二分$，那么我们能否追求极致，让查找性能突破到常数阶呢？这里就要介绍到我们的散列（也可以叫哈希 Hash）它采用直接寻址的方式，在理想情况下，查找的时间复杂度可以达到常数阶 $O(1)$。 散列表也就是哈希表有什么用 散列（Hashing）通过散列函数（哈希函数）将要参与检索的数据与散列值（哈希值）关联起来，生成一种便于搜索的数据结构，我们称其为散列表（哈希表），也就是说，现在我们需要将一堆数据保存起来，这些数据会通过哈希函数进行计算，得到与其对应的哈希值，当我们下次需要查找这些数据时，只需要再次计算哈希值就能快速找到对应的元素了：
什么是哈夫曼树 各位了解文件压缩吗？它是怎么做到的呢？我们都会在这一节进行探讨。 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree） 啥叫带权路径长度达到最小？就是树中所有的叶结点的权值乘上其到根结点根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数） 这里我们分别将叶子结点ABCD都赋予一个权值，我们来尝试计算一下，计算公式如下： $$WPL = \sum_{i=1}^{n} \big( value(i) \times depth(i) \big)
什么是平衡二叉树 利用二叉查找树，我们在搜索某个值的时候，效率会得到巨大提升。但是虽然看起来比较完美，也是存在缺陷的，比如现在我们依次将下面的值插入到这棵二叉树中： 120 15 13 8 6 3 在插入完成后，我们会发现这棵二叉树竟然长这样： 其说它是一棵二叉树，不如说就是一个链表，如果这时我们想要查找某个结点，那么实际上查找的时间并没有得到任何优化，直接就退化成线性查找了。 所以，二叉查找树只有在理想情况下，查找效率才是最高的，而像这种极端情况，就性能而言几乎没有任何的提升。我们理想情况下，这样的效率是最高的： 所以，我们在进行结点插入时，需要尽可能地避免这种一边倒的情况，这里就需要
什么是二叉查找树 二叉查找树本质就是通过二分搜索的方法来快速查找 二叉查找树也叫二叉搜索树或是二叉排序树，它具有一定的规则： 左子树中所有结点的值，均小于其根结点的值。 右子树中所有结点的值，均大于其根结点的值。 二叉搜索树的子树也是二叉搜索树。 一棵二叉搜索树长这样： 查找值为15的结点： 从根结点18开始，因为15小于18，所以从左边开始找。 接着来到10，发现10比15小，所以继续往右边走。 来到15，成功找到。 实际上，我们在对普通二叉树进行搜索时，可能需要挨个进行查看比较，而有了二叉搜索树，查找效率就大大提升了，它就像我们前面的二分搜索那样。 因为二叉搜索树要求比较严格，所
线索化二叉树 我们知道一棵二叉树实际上可以由多个结点组成，每个结点都有一个左右指针，指向其左右孩子。我们在最后也讲解了二叉树的遍历，包括前序、中序、后序以及层序遍历。只不过在遍历时实在是太麻烦了，我们需要借助栈来帮助我们完成这项遍历操作。 一棵二叉树的某些结点会存在NULL的情况，我们可以利用这些为NULL的指针，将其线索化为某一种顺序遍历的指向下一个按顺序的结点的指针，这样我们在进行遍历的时候，就会很方便了。 线索化的规则为： 结点的左指针，指向其当前遍历顺序的前驱结点。 结点的右指针，指向其当前遍历顺序的后继结点。 在线索化之后，G的指向情况如下： 这样，G原本两个为NULL的指针就
树与森林 树的介绍 树是一种全新的数据结构，它就像一棵树的树枝一样，不断延伸。 一棵树就像下面这样连接： 可以看到，现在一个结点下面可能会连接多个节点，并不断延伸，就像树枝一样，每个结点都有可能是一个分支点，延伸出多个分支，从位于最上方的结点开始不断向下，而这种数据结构，我们就称为树（Tree)，不能与其他分支上的结点相交 我们一般称位于最上方的结点为树的根结点（Root）因为整棵树正是从这里开始延伸出去的。 每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度。 每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）比如结
