数据结构学习笔记1
视频学习链接：算法学习1
Word笔记-资源链接：数据结构与算法学习笔记.docx-互联网文档类资源-CSDN下载
目录
1）堆：
1.1）什么是堆？
堆这种数据结构非常的简单，可以把堆看成是一个二叉树，也可以看成是一个数组，因为堆就是一个使用完全二叉树结构来维护的一个一维数组。
堆的每个节点最多有两个子节点。
堆分为大顶堆和小顶堆。它的基本思想就是，对于任何一棵子树而言，父节点永远都大于它的任何一个子节点，这就是一个大顶堆。反之的话，就是一个小顶堆。
如图所示：
（大顶堆）
1.2）堆排序：
1.2.1）如何往堆中添加数据：
往堆中添加数据时，一般将新结点添加到最下边一行叶子结点的靠左的位置，如果最后一行没有合适的空间的时候，则另起一行在最左边进行添加。
1.2.2）用于排序：
升序排序用大顶堆；降序排序用小顶堆；
1.2.3）大顶堆的构建过程：
1）从最后一个非叶子节点开始调整；
从当前堆的最后一个非叶子节点，开始调整；
最后一个非叶子节点怎么找？数组的长度/2 -1得到的索引位置，就是当前堆的最后一个非叶子节点。
比如说： [3, 7, 16, 10, 21, 23] 。
堆结构如下：
数组的长度为6，除以2等于3，再-1，等于2；
所以下标索引2所在的节点，一定就是当前堆的最后一个非叶子节点。即节点16。
2）构建过程；
- 先比较当前索引位置的节点与左子结点，如果当前节点小于左子结点，则交换位置；
- 然后比较当前这个新左子结点是否满足堆的性质，如果不满足则从头重新开始调整堆；
- 再比较当前索引位置的节点与右子节点，如果当前新父节点小于右子节点，则交换位置；
- 然后比较当前这个新右子节点是否满足堆的性质，如果不满足则从头开始重新调整堆。
- 如果当前索引位置的节点大于左子结点与右子节点，则继续找下一个非叶子节点，即索引位置-1；
- 一直到无需调整的时候，大顶堆构建完成。
1.2.4）大顶堆的排序思想：
第 1 步：先 将n 个元素的无序序列，构建成大顶堆；
第 2 步：将根节点与最后一个元素交换位置，然后将最大元素"沉"到数组末端；
第 3 步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的 n-1 个元素重新构建成大顶堆
第 4 步：重复第 2 步、第 3 步直到整个数组排序完成。
2）线索化二叉树：
这是中序线索化二叉树，相应的还有前序线索化二叉树，以及后序线索化二叉树。
我们将前边和后边都一分为二，比如说0标识左右子树，1标识前驱节点或后继结点。
4）赫夫曼树：
4.1）赫夫曼树的概述：
赫夫曼树是非常重要的一个数据结构，它的主要用途是赫夫曼编码，赫夫曼编码是我们数据压缩领域的一种非常重要的思想。
赫夫曼树是以赫夫曼树的创建者赫夫曼命名的，赫夫曼树其实就是最优二叉树。最优二叉树的意思是，它是n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。
叶节点的带权路径指的是：从根节点出发，到该叶节点经过的节点数量（不算根节点、算叶节点）*该叶节点的权值，称为该叶节点的带权路径。
比如说：
A节点的带权路径是：2*9(权值)=18；
B节点的带权路径是：2*4(权值)=8；
C节点的带权路径是：2*5(权值)=10；
D节点的带权路径是：2*2(权值)=4；
树的带权路径长度WPL指的是：树中所有叶子结点的带权路径长度之和。
最优二叉树：带权路径长度WPL最小的树，我们就称之为最优二叉树，也就是赫夫曼树。
比如说：对于（a）（b）（c）这三个树来说，谁是最优二叉树？
分析：
（a）树：9*2+4*2+5*2+2*2=40；
（b）树：9*1+5*2+4*3+2*3=37；
（c）树：4*1+2*2+5*3+9*3=50；
很明显，权值最大的节点离根节点越近的二叉树才是最优二叉树。即（b）树。
如何让WPL变小一点呢：我们让权值大的节点离根节点近一些，让权值小的节点离根节点远一些。
4.2）构建一棵最优二叉树的过程：
1，这里有一个数组，首先，将数组内的所有元素排好序，将数组内的每一个元素当成一个树中的一个节点；
将数组内最小的两个元素拿出来，组成一颗新的二叉树，两个元素分别为该二叉树的两个叶子节点；根节点为两个叶子结点的和——8；
3，将根节点拿回数组中，将数组重新进行排序，然后继续将权值最小的两个元素拿出来，组成新的二叉树、求根节点，再重新拿回到数组中进行重新排序...。
...
...
...
...
4，最终，我们就组成了一个二叉树：
这棵二叉树其实就是我们的赫夫曼树。我们之前数组中的所有元素都是这棵二叉树的叶子结点。我们也可以发现，原来数组中较大的元素都在离根节点最近的叶子结点上，原来数组中最小的那些元素都在离根节点最远的叶子结点上。这样一来，我们的这棵二叉树的WPL值就是最小的，那么这棵树就是最优二叉树，即我们的赫夫曼树。
5）赫夫曼编码：
5.1）概述：
赫夫曼编码是数据通信领域和数据压缩领域的一个非常典型的技术手段，
5.2）定长编码：
首先说定长编码：（比如说这里的定长-8位字节）
（定长编码其实方式有很多种，这里只演示其中一种）
如图所示，我们要将这一句话发出去，首先，我们先要将这句话的每个字都转为ASCII码，转为ASCII之后还是不够的，因为计算机只识别二进制，所以我们继续将99 97...这一串ASCII转为一串八位八位的字节（实际是没有空格的，图中只是为了演示方便），这样的话就可以了。
那边的计算机收到之后，将每八位的字节转为一个ASCII码，然后再将ASCII转为相应的字符；
缺点：这样的传输，数据量太大而且冗余巨大，比如说，这么简单的一句话，就要传输396个字节！太长了！
5.3）非定长编码：
然后说非定长编码，因为定长编码存在着即使一个字符很短但是也是需要固定的长度，这是会造成了浪费。
非定长编码，首先，将这一个字符串中每个字符出现的次数列举出来：
将上边的字符都挨个转为一个字节，我们设定让经常出现的字符短一点，不经常出现的字符往后靠、长一点：比如说a为0，空格为1，n为10,...
然后接下来，我们将字符串按照刚才的转换规则，转为一串字节，如图所示：
这就是非定长编码。
但是对于非定长编码，是有规定的，不能随便就编码，比如说这里，其实转为一串字节以后是不存在空格的，实际上传输的这一串字节为1101011...
这样的话，就存在一个问题，接收的计算机怎么识别？开始的时候，是把1识别为空格？还是把11识别为c？还是把110识别为y，...，所以在这种情况下我们虽然编码很成功，但是不好进行解码。
所以对于非定长编码有一个要求：每一个字符的编码都不能是其他字符的编码的前缀，符合此要求的编码叫做前缀编码。
只有在这种情况下，才可以进行非定长编码。
5.4）赫夫曼编码：
赫夫曼编码：
首先，同样的，我们依次先将字符串中每个字符出现的次数进行一个计数：
接下来，我们将每个字符作为一棵赫夫曼树的一个叶节点，去进行构建一个赫夫曼树，将每个字符出现的次数作为该节点的权值，按照权值越大离根节点越近、权值越小离根节点越远的规律去进行构建，如图所示：
然后，我们再将每个非叶子节点到它的左结点的路径定义为0，到右节点的路径定义为1，
这样的话，我们就可以将根节点到每个叶节点的路径和该叶子节点进行一一对应。如图所示：
（可以发现，出现次数较多的比较短，出现次数较少的比较长。）
通过这种方式转换出来的字节，我们就叫做赫夫曼编码（或者叫赫夫曼编码表）。
此时，我们再将最初的那一串字符串，按照我们的赫夫曼编码表，去进行一个编码：
这样的一串字节，是不会存在非定长编码中的前缀的问题的，因为每个字符对应的编码都是唯一的，都不会是其他字符的编码的前缀。
所以，接收的计算机只需要按照这个赫夫曼编码表去进行解码，就可以了。
这就是赫夫曼编码的典型应用，它的长度只有122，相比一开始的定长编码的396，它压缩了70%，而且它做到了无损压缩。
6）二叉排序树：
对于顺序存储，不排序的情况下查找困难，排序的情况下删除插入困难；
对于链式存储，虽然删除插入方便，但是无论是否排序，查找都是困难的；
二叉排序树是一个查找和删除插入都兼顾的一种数据结构，什么是二叉排序树？二叉排序树也叫作二叉查找树、二叉搜索树，简写BST，对于任何一个非叶子节点来说，要求左子结点的值都小于当前节点，右子节点的值都大于等于当前节点。
7）平衡二叉树AVL树：
7.1）二叉排序树存在的缺陷：
二叉排序树在插入数据的时候其实是在进行一个一个的对比，然后把新节点插进去。但是如果存在一种情况呢，比如说：[1 2 3 4 5 6 7 8]，我们如果用这一组数据来创建一个二叉排序树的话，其实是长这个样子的：
我们知道，原来二叉排序树的优点在于：查找效率相对比较高，插入删除也不错。
但是对于这一种情况来说，那么二叉排序树失去了查找的高效率，比如说要找8这个节点，那么要从根节点依次挨个找一遍，与链式存储几乎一样了。
7.2）平衡二叉树：
平衡二叉树首先必须是一棵二叉排序树，其次要求：对于任何一个节点而言，它的左子树和右子树的高度差的绝对值不能超过1。这就是一棵平衡二叉树。
平衡二叉树可以保证我们的查找效率比较高。
举例：
eg1：比如说这个，这个直接是一个满二叉树（完全二叉树），它的任何一颗子树的左右子树的高度差都为0，一定是一个平衡二叉树。
eg2：比如说这个，这个也是一个平衡二叉树，最大的高度差为1。
eg3：比如说这个，就不是一个平衡二叉树，因为对于A节点而言，它的左子树的高度为3（B-E-F），它的右子树的高度为1（C），高度差为2，大于1，所以它不是一个平衡二叉树。
7.3）构建平衡二叉树-单旋转：
我们现在要根据 [1 2 3 4 5 6 7 8] 这个数组，构建出一个平衡二叉树：
1）什么是左旋：
左旋：对X节点进行左旋，意味着，将 X 的右孩子（Y节点） 设为 X 的父节点 ；而 X 节点变成了 它原来的右孩子 的左节点！
因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
2）
首先，当添加到3这个节点的时候，此时对于1这个节点来说，左子树的高度为0，右子树的高度为2，不平衡了。
我们对其进行单旋转，因为左子树的高度小于右子树，所以我们进行左旋转：将1节点的右子节点设为新的父节点，而原来的1节点变成了它原来右节点的左子结点。
左旋中的“左”，意味着“被旋转的节点将变成它原来右子节点的左节点”。
如图所示：
对1节点进行左旋之后：
3）
当添加到5这个节点的时候，又不平衡了，因为对于此时的2这个节点来说，左子结点的高度为1，右子树的高度为3。左子树的高度小于右子树了，所以对父节点2进行左旋：将2节点的右子节点变更为新的父节点，将2节点变更为新父节点的左子结点。
如图所示：
左旋：
4）
此时是一个平衡二叉树吗？不是的。
因为对于3这个节点来说，是平衡的；但是对于4这个节点来说，是不平衡的，它的左子树的高度为0，右子树的高度为2。
因为4这个节点的左子树的高度小于右子树，所以我们要对4这个节点进行左旋，将4节点的右子节点5变更为新的父节点，将4节点变更为5节点的左子节点，如图所示：
5，右旋：
右旋：对 Y节点 进行右旋，意味着，将 Y节点的左孩子 设为 Y的父节点，而 Y节点 变成了 它原来的左孩子的右节点！
因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
比如：
此时不是一个平衡二叉树了，要进行旋转，因为A节点的右子树的高度小于A节点的左子树，所以对A节点进行右旋：
将A节点的左子结点变更为新的父节点，将A节点变更为它原来的左子结点的右节点：
比如：
对于这个二叉排序树，如何变成一个平衡二叉树呢？
对于节点8来说，左子树的高度为3，右子树的高度为1，右子树的高度小于左子树，此时对节点8进行右旋，将节点8的左子结点即节点6变更为新的父节点，将节点8变更为它原来的左子结点的右子节点。
但是此时节点8和节点7冲突了，我们知道，节点7一定是一个大于节点6且小于节点8的一个节点，所以此时我们将节点7变更为节点8的左子节点。如图所示：
7.4）构建平衡二叉树-双旋转：
存在这么一种情况：
此时，仅仅是对节点A进行右旋是不行的，可以先试一下：
可以看出，此时仅仅只对A节点进行一次右旋是不行的，旋转了之后还是不平衡。
所以这种情况，需要进行双旋转：
什么情况呢？因为我们本来是要对A节点进行右旋转，但是在对A节点进行右旋转之前，我们需要先检查一下A节点的左子节点的左右子树的高度，如果左子结点的右子树的高度大于左子树的高度，那么我们就需要先对A节点的左子结点进行一下左旋转，之后再对A节点进行右旋转。这就是双旋转。
比如说：
此时，我们本来是要对A节点进行一个右旋转，但是在对A节点进行右旋转之前，我们需要先检查一下A节点的左子结点即B节点的左右子树的高度，此时发现B节点的左子树的高度为1，小于右子树的高度2，所以此时我们需要先对B节点进行左旋转，然后才再对A节点进行右旋转。
如图所示：
先对B节点进行左旋转：
再对A节点进行右旋转：
此时，就是一棵平衡二叉树了。
8）2-3树
B树中要求所有的叶节点都在同一层；
2-3树是B树中的一项特例。2-3树分为两种，一种是2节点，一种是3节点。有两个子节点的节点叫二节点，有三个子节点的节点叫三节点。
比如说像这种节点，有三个子节点，就是三节点；
像6这种节点，只有两个子节点，就是二节点。
2-3树的要求：
二节点要么有两个子节点，要么没有子节点；
三节点要么有三个子节点，要么没有子节点。
（同理，四节点就是要么有四个子节点，要么没有子节点。）
举例：
比如说这种情况，如果将10这个节点追加到6这个节点的下边，就不符合2-3树的要求了。
所以正确的做法应该是将6这个二节点与10这个节点合并为一个三节点：
9）B树与B+树
2-3树、2-3-4树这些其实都是B树，只不过都是B树的一种特例。
什么是B树呢，其实就是2-3树、2-3-4树、2-3-4-5树...等等等等，将这些统称为B树。
在B树中，最大的节点的数字，称之为该B树的阶。比如说2-3树是3阶的B树、2-3-4树就是4阶的B树；
9.1）什么是B+树呢？
B+树是B树的一种变形。它相比于B树主要有两个变化。
1，非叶子结点只存储索引信息，不存储数据；
比如说这颗B+树，真正的数据只存储于它的叶子结点中，它的所有的非叶子结点只存储索引信息、只是用来帮助找到相应的数据用的。
2，每一个叶子节点最右边的指针，指向下一个相邻的叶子结点。
比如说0001这个节点指向它右边的那个节点——0002、0003、0003；
0002、0003、0003这个节点指向它右边的那个节点——0004、0005；
......
也就是说，所有的叶子结点组成了一个有序链表。
9.2）B树与B+树的区别：
9.3）B+树的优点：
当真正的数据存储在硬盘中的时候，当将B+树中所有的非叶子结点的信息也就是索引的信息都存储到内存中以后，当我们想要找某一条数据的时候，只需要通过一次硬盘IO就可以读取到相应的数据了。就是说我们将更多的索引信息存储到内存中以后，我们就可以通过索引去快速的找到相应的数据。
而如果是普通的B树的话，可能就需要去一次一次的读取数据和对比数据了。
而在实际情境下很可能的情况是数据量非常大、索引量很小，所以我们就可以采用B+树的数据结构，将索引信息都存储在非叶子结点中，将数据都存储在叶子节点中，这样就可以快速的去找到相应的数据了。
当然B+树和B树各有优缺点，各自适用于不同的实际场景中。
10）散列表/哈希表：
10.1）什么是散列函数：
哈希表也叫散列表。
这里有一个数组，我们要将右边的数据存入到一个数组中，如何确定每个元素在数组中的存储位置呢？
这里有一个公式：存储位置=fun(关键字)
关键字指的就是可以标识出我们的每一条数据的一个标识；
这个fun()就是我们的散列函数/哈希函数。散列函数有多种，比如说直接定址法、数字分析法、平方取中法、取余法、随机数法等等。
10.2）散列冲突的解决方案
我们知道，无论使用那种散列函数去存储数据，都有可能产生地址冲突的问题。
那么散列冲突的解决方案分为两种，①开放地址法和②链地址法。
其中开放地址法又分为三种，线性探测法、平方探测法、以及再哈希法。
线性探测法：
所谓的线性探测法就是，将产生冲突的数据存入紧接着的下一个位置：
比如：
?-->
比如：21，先来到11的位置，冲突了，再往后存，与12又冲突了，那就继续往后存，与22也冲突了，继续往后存，直到没有冲突。
如图所示：
比如说23这个数据：本来应该存入下标为3的位置，但是发现已经有数据了冲突了，那就继续往后存，直到没有冲突为止。
可以发现，线性探测法会导致大量的数据聚集在那一片区域，所以导致解决冲突的效率并不是很高。
平方探测法：
上边的线性探测法是将下标索引往后边多找一位，平方探测法就是将下标索引往后多找1的平方、2的平方、3的平方这样往后找。
比如：21这条数据，与11冲突了，往后多找1的平方，到了12所在的位置，仍然冲突，继续往后找，下标在12的位置基础上去加上2的平方，所以到了这个位置，如图所示：
再哈希法：
再哈希法的意思就是，我们不止有一个哈希函数，可能有两个或者三个甚至更多，（一般最多三个就可以解决大部分的问题）。
当将要存入的这个数据与已有的数据产生了哈希冲突时，此时将该数据通过第二个哈希函数进行哈希计算，按照第二个哈希函数计算出来的位置重新存入数据，如果还是冲突，再继续通过第三个哈希函数进行计算...。
有没有可能出现使用了所有的哈希函数之后还是存在哈希冲突的情况，有的，不过概率很低，如果真的出现了，那么可以再接着使用线性探测法或者平方探测法去解决这个哈希冲突。
链地址法：
链地址法就是，首先，我们新建一个数组，但是数组中不再直接存储数据，而是存储一个指针指向数据的位置：比如说1这个下标存储的指针指向11这个数据，2这个下标存储的指针指向12这个位置；
?
当22这个数据要存储的时候，与12这个数据产生了哈希冲突了，此时使用链地址法该怎么办呢，是将12这个数据的指针指向22这个数据，从而形成了一个链表。如图所示：
这就是链地址法。要解决散列冲突的问题，实际上使用的时候更多的是使用链地址法。因为不管是线性探测法还是平方探测法，都会导致数据产生一系列的偏移，不利于后期的查找。而链地址法的话，数据都还是在数组中的同一个位置，这样的话更符合散列函数的定义。
11）图
11.1）什么是图结构
图中的一个一个的点称为顶点；这一条一条的线，代表着顶点之间的关系，我们将其称之为边。
如果两个顶点之间可以通过一条边进行连通，那么就将这两个点称为是邻接的，反之就不是邻接的。比如说B和C、B和A这些顶点之间就是邻接的，而A和D就不是邻接的。
有向图和无向图指的就是边是否是有方向的。如图所示：
带权图指的就是，我们可以给图中的边，给它标识上一个有意义的数据值，比如说是A城市（顶点）到B城市（顶点）所需要的时间，等等，这就是带权图。
11.2）图的数据如何存储：
要实现图这种数据结构，首先就是要思考图是如何去存储数据的，是使用链表进行存储，还是使用数组进行存储呢？
使用链表是不行的，因为我们将图中的每个顶点都是链表中的一个节点，那么图中的每个节点都可能连接有多个其他的顶点，这个时候这个连接关系我们如何使用链表来进行表示？在链表中即使是双向链表也只是指向了上一个下一个节点，无法指向其他的节点。所以说如果用链表来存储数据的话，指针的部分就不太好写。
图结构我们都是这样设计的：
首先，我们定义一个数组，将图中的顶点都放入这个数组中。
然后我们再单独找一个地方来单独存放顶点与顶点之间的关系。比如说A顶点和B顶点之间有没有边，A顶点和D顶点之间有没有边，这些。
存放的方式有两种，一种是邻接表，一种是邻接矩阵。
邻接表示例：
将每个节点从该节点出发可以到达的所有的顶点的路径都一一列举出来。
邻接矩阵示例：
将每个节点与其他的节点依次进行判断，是邻接的顶点，则标记为1，不是邻接的顶点则标记为0。
11.3）图的遍历：
图的遍历分为①深度优先搜索算法和②广度优先搜索算法，两种方式。
举例说明：
对于这样一个图。
深度优先遍历的方式为：先从A节点出发，到B节点，再接着从B节点出发，到达C节点，再接着从C节点出发，到达C的下一个节点，发现没有了，则退回到C的上一个节点B节点，从B节点到D节点，再接着到D节点的下一个节点，发现D没有下一个节点了，则退回到D节点的上一个节点B节点，再到B节点的下一个未被遍历过的节点E节点，再接着到达E节点的下一个节点，发现E节点没有了，于是退回到E节点的上一个节点B节点，B节点下边的节点也没有了，于是退回到B节点的上一个节点A节点，然后遍历A节点的下一个节点C节点，再之后A节点的下一个节点也遍历完了，于是整个图遍历完成。
广度优先遍历的方式为：先从A节点出发，到下一级节点B节点，然后退回到A节点，再遍历A节点的未被遍历的下一级节点C节点，A节点的下一级的所有节点被遍历完成之后，再开始从下一级节点比如说是B节点开始，遍历B节点的下一级的所有节点。最终完成图的遍历。
深度优先遍历和广度优先遍历的区别：
①，深度优先遍历是一直先遍历某一个节点的下一个节点，直到没有了下一个节点，再退回到上一级节点，最终遍历完成。
②，广度优先遍历是先遍历完第一个节点的下一级的所有节点，然后再依次遍历完成下下一级的所有节点，是一级一级的完成遍历。
③，深度优先遍历相当于是由线到面，广度优先遍历相当于是由面到线。