大家好，今天来为大家解答图解数据结构这个问题的一些问题点，包括数据结构基本概念也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
本文目录
一、数据结构-堆
1、堆其实就是一棵完全二叉树，即若设二叉树的深度为h，除第 h层外，其它各层(1～h-1)的结点数都达到更大个数，第 h层所有的结点都连续集中在最左边。
2、定义为：具有n个元素的序列（h1,h2,...hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。完全二叉树的根结点称为堆的顶。
3、可以注意到，堆仅保证元素和其子结点之间的关系，并不保证兄弟结点之间的关系。
4、更大堆，顾名思义，堆顶的键值是所有堆结点键值中更大者。套用前面讲到过的规则，当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)，所有父结点的键值均大于子结点。
5、由更大堆的定义，可以很容易的理解最小堆，即所有父结点的键值均小于子结点。
6、堆的内存形式有两种，一种是链表，一种是数组。
7、对于一个堆，常用的 *** 作有两种， *** 一个新的结点和删除堆顶。
8、向堆 *** 一个结点，首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）构建完成才能继续添加下一层的结点。这就意味着完全二叉树新增加结点的位置是唯一固定的。对应数组来说，就是在数组的末尾增加一个元素。
9、进一步，对这个完全二叉树进行调整，即移动父结点和子结点的相互位置关系，使其满足条件而重新成为堆。这种调整可以简单的看成是一些列的上浮（shift-up） *** 作。可以看看下面这个简单的图。
10、可以看到，所谓的shift-up，就是将新 *** 的结点不停的和其父结点进行比较，如果子结点的键值大于（更大堆）/小于（最小堆）其父结点，那么就对二者进行交换，因为这里是数组，所以仅需要交换结点之间的键值，直到子结点的键值不大于（更大堆）/不小于（最小堆）其父结点。
11、和 *** 新的结点类似，删除堆顶，还是首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）全部删除之后才能继续删除上一层的结点。这就意味着完全二叉树删除的结点的位置是唯一固定的。对应数组来说，就是删除数组末尾的元素。
12、步骤1和2非常简单，执行完成之后，新的完全二叉树如图所示：
13、步骤3是问题的重点和难点，可以简单的看成是一些列的下沉（shift-down） *** 作。
14、对于某个结点（parent），所谓的shift-down，包括以下子步骤（这里以更大堆为例）：
15、构建堆有两种方式，一种是从无到有，也就是一个不断 *** 结点的过程；而另一种就是在原有完全二叉树的基础上，按照某种规则对结点进行调整。
16、从原理上说，从无到有的构建堆比较简单，对于每一个新增结点，对其进行 *** *** 作，结果必然是一个堆。
17、在原有的完全二叉树上进行调整，稍微复杂一些，可以从最后一个非叶结点开始，对每个非叶结点进行shift-down *** 作。
18、该 *** 作的难点在于如何找到“非叶结点”和“最后一个非叶结点”。考虑非叶结点的定义，一个结点如果有至少一个子结点，那么就称其为非叶结点。因此，我们只要遍历所有的结点（根结点除外）的父结点，就可以遍历所有的非叶结点。知道了如何找到“非叶结点”，找出“最后一个非叶结点”的 *** 显而易见，最后一个叶结点（数组的末尾）的父结点就是“最后一个非叶结点”。
19、通过之前的章节，不难看出，堆 *** 作的核心是两个步骤：shift-down和shift-up，更进一步，这两个 *** 作都是递归的。
20、不仅在面试中，堆在日常工作中也经常被使用。堆经常会被作为优先队列来使用，常见于例如任务调度，数组合并等场景。
21、在j *** a中，优先队列实现了堆的数据结构【1】。我之前的一篇文章 J *** a优先队列（PriorityQueue）对优先队列进行了简单介绍，可以参考。
22、【1】
23、【2】更大堆（创建、删除、 *** 和堆排序）
24、【6】更大堆的 *** /删除/调整/排序 *** 作(图解+程序)（J *** A）
二、<算法图解>
1、二分查找、大O分析法；数组和链表；递归、快速排序；分治、动态规划、贪婪算法；散列表（键值对组成的数据结构）；图算法（模拟 *** 的 *** ）：广度优先搜索、迪杰斯特拉算法（计算 *** 中两点之间最短距离）；K近邻（KNN，用于创建推荐 *** 、OCR引擎、预测股价、物件分类）。
2、二分查找的时间复杂度为log2n，多少个2相乘等于n。
3、有序数组，定义low和high，非一个元素，猜中，大了，小了。
4、选择排序：o(n方)，快速排序：o(nlo *** )，存储最小的值，存储最小元素的索引，找出最小的值，加到新数组中。
5、循环，程序的 *** 能更好，递归，程序更容易理解。栈有两种 *** 作：压入和弹出。
6、每个递归函数都有两部分：基线条件和递归条件，递归条件指的是函数调用自己，基线条件指的是函数不再调用自己，避免无限循环。
7、编程概念，调用栈，计算机在内部使用被称为调用栈的栈，递归是调用自己的函数。
8、调用栈可能占用大量内存，解决方案是编写循环代码，或者使用尾递归，但并非所有的语言都支持尾递归。
9、分治-递归式问题解决办法：步骤：找出基线条件，确定如何缩小问题的规模，使其符合基线条件。
10、涉及数组的递归函数，基线条件通常是数组为空或只包含一个元素。
11、快速排序-D&C算法：步骤：设置基线条件，数组小于2，选择基准值，将数组分成两个子数组：小于和大于基准值的元素，对这两个子数组进行快速排序，递归调用。
12、合并排序：o(nlo *** )，快速排序：o(nlo *** )：层数o(lo *** )乘每层需要的时间o(n)，但最差情况为o(n方)。
13、散列表-基本数据结构之一：内部机制：实现、冲突、散列函数。
14、散列表无序，数据结构：数组、列表、（栈、不能用于查找）、散列表（包含额外逻辑）。
15、数组和链表都直接映射到内存，但散列表使用散列函数来确定元素存储位置。
16、散列函数：不同的输入映射到不同的索引，输出不同的数字，散列表是散列函数和数组的结合，也称散列映射、映射、字典、关联数组。
17、缓存的数据存储在散列表中，访问页面时，先检查散列表是否存储了页面。
18、如果两个键映射到了同一个位置引发冲突，可以在这个位置存储一个链表，好的散列函数可以减少冲突。
19、填装因子为散列表元素/位置总数，因子越低，发生冲突的可能 *** 越小， *** 能越高。
20、广度优先搜索（BFS）的含义：解决最短路径问题的算法。
21、步骤：使用图来建立问题模型，使用广度优先搜索算法（是否有路径，哪个路径最短）。
22、所有算法中，图算法是最有用的。
23、队列（数据结构）：类似于栈，不能随机访问队列中元素，只支持入队和出队（压入和弹出），先加入的先出队，即先进先出（FIFO），而栈是后进先出（LIFO）。
24、有向图：关系是单向的，无向图：没有箭头，直接相连的节点互为邻居。
25、拓扑排序：根据图创建一个有序列表。
26、迪杰斯特拉算法：适用于加权图（提高或降低某些边的权重），找出加权图中的最短路径。
27、只适用于有向无环图，如果有负权边，不能使用迪杰斯特拉算法，因为算法假设处理过的节点，没有前往终点的最短路径，故，有负权边的可用贝尔曼-福特算法。
28、在未处理的节点找到开销最小的节点，遍历当前节点的所有邻居，如果经当前节点前往该邻居更近，就更新邻居开销，同时将该邻居的父节点设置为当前节点，将当前节点标记为处理过，找出接下来要处理的节点，并循环。
29、贪婪算法：每步都选择局部更优解，最终就是全局更优解，易于实现，运行快，是个不错的近似算法。
30、 *** 类似于列表，但是不包含重复的元素。
31、贪婪算法：o(n方)，NP完全问题：需要计算所有的解，从中选出最小距离，计算量大，更佳做法是使用近似算法。
32、动态规划：约定条件下找到更优解，在问题可分解为彼此 *** 且离散的子问题时，就可使用动态规划来解决。
33、动态规划解决方案涉及 *** ，每个单元格都是子问题，需考虑如何将问题分解为子问题。
34、K最近邻算法（KNN）： *** 推荐 *** 。
35、特征抽取：指标打分，计算距离（相似程度），N维。
36、应用：OCR光学字符识别（optical character reco *** ition），提取线段、点、曲线特征，找出与新图像最近的邻居；语音识别，人脸识别。
37、垃圾邮件过滤器：朴素贝叶斯分类器。
38、二叉查找树（binary search tree）：有序树状数据结构。
39、二叉查找树 *** 和删除 *** 作快于有序数组，但不能随机访问（没有索引）。
40、红黑树是处于平衡状态的特殊二叉树，不平衡时，如向右倾斜时 *** 能不佳。
41、反向索引：一个散列表，将单词映射到包含他的页面，常用于创建搜索引擎。
42、并行算法：速度的提升非线 *** ，因为并行 *** 管理开销和负载均衡。
43、分布式算法：特殊的并行算法， *** preduce（映射和归并函数），映射：任务多时自动分配多台计算机完成，将一个数组转换成另一个数组，归并是将一个数组转换成一个元素。
44、线 *** 规划：在给定约束条件下更大限度的改善指定指标，使用 *** x算法，图算法为线 *** 规划子集。
三、图解:数据结构与算法之字典树
1、字典树（Trie树）这一数据结构是不太常见但是十分好用<typo id="typo-32" data-origin="而" i *** oretag="true">而</typo>一种数据结构，博主也就是最近一段时间做了几道字节的题目才了解到字典树这一数据结构。并将自己的学习内容跟大家分享。
2、首先，何为字典树（Trie树）？顾名思义，就是在查询目标时，像字典一样按照一定排列顺序标准和步骤访问树的节点，举一个简单例子，英文字典查单词"He"，那么之一步你肯定要按照a-z的顺序先找到h这个首字母，然后再按照相同顺序找到e。博主所要介绍的字典树就是类似字典这样的结构。
3、上述查找单词的过程就是不断查找与所查单词相同前缀的字符串，直至查找到所查单词的最后一个字母。因此，字典树又称为前缀树(prefix Tree)。
4、以hell、hi、new、nop为例建立一个字典树，构造如下
5、根据上文所述可以得到字典树的结构 *** 质
6、字典树的构造其实较为简单，和一般树的构造没有太大区别。接下来将对字典树的 *** 、删除、查询 *** 作进行分析与讲解。
7、在没有字典树的时候，我们需要先构建出字典树。
8、再 *** 单词hit，过程如下，检查＝>存在则访问/不存在则建立新节点再访问＝>直到要 *** 的单词到达最后一个字符。
9、字典树的 *** *** 作比较简单，不需要考虑太多排序问题。
10、正如上文所说，按照一定的标准进行查询目标字符串，每个节点都储存一个字符，根节点到达子节点路径组成的字符串即为该节点所对应的字符串，那么查询目标字符串时按照从根节点一步一步访问相应字符所在的节点，其实也就是匹配字符串前缀的过程。
11、如下图，在字典树中，查询"hell"，
12、 [ *** 上传失败...(i *** ge-f028c4-161105761 *** 23)]
13、删除 *** 作相对于 *** 与查询复杂一点，但是也很简单，删除的前提是单词已经存在于字典树。
14、删除字典树节点的 *** 作需要考虑目标字符串最后一个字符是否是树中的叶子节点。
15、因为一个单词可能是另一个单词的前缀部分，如果不是叶子节点，我们只需要把该单词的单词标志位清空即可，无需删除整个“树枝”。
16、比如，想要删除"hell"这个单词，与之一种删除相同，只不过是从最后一个节点，'l'节点是叶子节点，开始往上进行节点删除 *** 作。
17、比如，想要删除"hi",那么与前两种其实一致，访问到叶子节点'i',删除叶子节点，并向 *** 问，访问到'h'，由于删除'i'以后，'h'依然不是叶子节点，因此不再继续删除节点。
18、比如，想要删除"nop",与前几种类似，先访问到叶子节点'p'删除，然后上移发现'o'是叶子节点，然而'o'有单词标记位，所以，这里不再继续删除。
19、有上面几种删除 *** 作，我们得到了删除的标准：
20、了解了这么多字典树的各种 *** 作，相信你对字典树的用途有个大概了解了，字典树更大作用是用于==字符串的各种匹配==，前缀匹配（模糊搜索），字符串查找（字典）等等。
21、博主只打出了“涓涓清泉”四个关键字，其搜索列表返回了诸多以涓涓清泉为首的选项
22、顾名思义，就是一个单纯的字典而已，不多举例。
23、字典树的构建，通过利用空间换时间的思想以及字符串的公共前缀减少无效的字符串比较 *** 作从而使得 *** 和查找字符串变得高效．其 *** 或者查找的时间复杂度为O(n)，n为字符串长度。
24、当然，字典树有着它的弊端，当所 *** 的单词没有很多公共前缀时，字典树的构建变得十分复杂和低效。
25、字典树的难度不是很大，但却是一种十分有用的数据结构，掌握之后，对于解决一些有关字符串匹配、公共前缀的问题十分有帮助。
26、当然我们也说了，字典树有着自己的弊端，由于用空间换时间，如果遇到了一堆公共前缀很少的单词进行字典树构造时，空间需求就显得十分大了。
好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！
