基础数据结构
# 基础数据结构
# 什么是数据结构
我们知道数据存储于计算机内存中，数据结构决定了数据在内存中的顺序和位置关系。简单来说，数据结构使得数据个体之间拥有了某种关系（数据结构 = 个体 + 个体关系）。
算法与数据结构是紧密相连的，算法可以说是对存储数据的一种操作，我们可以狭义地认为算法依附于一种数据结构的基础上。我们知道算法是解决问题的步骤和方式，而数据结构能够帮助我们将现实中大量而复杂的问题 以 特定的数据类型 和 特定的存储结构 保存到内存中，而算法能在此基础上为实现某个功能（比如查找/删除某个匀速或者对所有元素进行排列）而执行相应的操作，最终解决问题。
举些例子：
- 电话簿-》数组
- 保存5W个人的信息 -》链表
- 人事信息管理 -》树
- 交通图，导航 -》图
上述例子的数据结构不是一成不变的。因为将数据存储于内存的时候，需要根据目的去选择合适的数据结构以提高内存的利用率。
到此，对于公式：程序 = 数据结构 + 算法。 应该可以有个更直白的理解：程序 = 数据的存储 + 数据的操作。
注意还需要有个认知概念是：数据在内存中实际是呈线性排列的，但是我们可以使用指针、结构体、动态分配内存（C语言）等等“道具”，构造链表、树、图等复杂的数据结构，下文会介绍一些基本的数据结构。
# 数据结构的地位
数据结构是软件工程中最核心的课程。很多编程语言中，都有一个基本的概念：栈和堆。所谓的栈内存和堆内存实际上是分配内存的算法不同，如果是以压栈、出栈的方式去分配的内存，那么就是栈内存，如果是堆排序的方式分配的内存，那么就是堆内存。此外像函数调用运行的原理是栈，操作系统的队列，编译原理的语法树，数据库等等都离不开数据结构。但是它们其实本质上就是 数据结构+算法 的内容。
数据库的重要性不言而喻。数据库可以说是数据结构的脚踏板，它对数据结构进行了封装，让我们对数据结构的问题狭窄了。
字段：反映一个事物的属性
记录：反映一个整体的事物
表：同一类事物的集合
视图：简化查询工具
常见的数据结构按逻辑和存储结构分类大致可以分为线性结构和非线性结构两大类。线性结构是一个有序等数据元素集合，除了第一个元素和最后一个元素之外，其他元素与元素之间首尾相连，常见的线性结构数据有链表、数组、栈、队列。非线性结构各个元素不再保持首尾相连的顺序，而是一个元素和其他0或多个元素之间互相连接，常见的非线性结构有树、图。
# 链表
链表 (opens new window)的数据呈线性排列，在链表中添加和删除都较为方便，访问比较耗费时间。
链表每个数据都有一个“指针”指向下一个数据的地址。
分散存储：在链表中，数据一般是分散存储于内存中的，无需存储在连续的空间内。
顺序访问：因为数据在内存中分散存储，所以要想访问数据，只能从第一个数据开始，顺着指针指向一一访问。这种访问方式又称顺序访问。
操作：无论是新增还是删除数据，只需要改变添加位置或者删除位置前后的指针指向就可以。
(最基本）链表操作时间复杂度，记数据量为n：
- 访问数据：$$O(n)$$。访问数据需要从头开始访问（线性查找），如果目标数据在链表最后的话，就是$$O(n)$$。
- 新增、删除数据：$$O(1)$$。无论是新增还是删除，只需要更改两个指针的指向，所以时间复杂度与n无关。
上述是最基本的一种链表，除此之外，还有几种扩展的列表：
- 循环链表：在基础的链表基础上尾部使用指针，并指向链表头部的数据，将链表变成环形。循环链表没有头和尾的概念。常用于保存数量固定的最新数据。
- 双向链表：每个数据结点有两个指针，分别指向前后点数据。可以从前往后或者从后往前遍历数据。缺点：指针数的增加会导致存储空间需求增加，添加和删除数据需要改变更多的指针指向。
# 数组
数组 (opens new window)也是一种呈线性排列的一种数据结构。数组访问数据十分简单，添加和删除数据比较复杂。
假如有数组a[], a是数组的名称，“[]”中的数字称为数组下标，从0开始，表示该数据是数组中的第几个数据。
连续存储：数组的数据在内存中是连续存储的。
随机访问：数组由于数据是连续存储在空间内的，所以每个数据的内存地址可以直接通过数组下标算出，直接访问目标数据，这种访问方式又称随机访问。
操作：可以随机访问，只需指定数组下标，便能直接访问。 添加和删除数据操作比链表复杂，如果添加数据，首先需要在尾部增加需要的存储空间，然后将已有数据一个个移开给新数据腾出空间，最后写入新数据； 如果要删除数据，将目标数据删除后，再将后面的数据一个个往前移，最后再删除多余的空间。
数组操作时间复杂度，记数据量为n：
- 访问数据：$$O(1)$$。随机访问。
- 新增/删除数据：$$O(n)$$。
链表和数组对比：
| 访问 | 添加 | 删除 | |
|---|---|---|---|
| 链表 | 慢 | 快 | 快 |
| 数组 | 快 | 慢 | 慢 |
# 栈
栈 (opens new window)也是一种数据呈线性排列的数据结构，栈就像生活中的一摞书、一杯水、枪支的子弹匣等等，这种数据结构只能访问最新添加的数据。
入栈：往栈中添加数据的操作。 出栈：从栈中取出数据的操作。
后进先出（Last In First Out，LIFO）：像栈这种最后添加的数据最先被取出，即“后进先出”称为LIFO。
操作：添加和删除操作只能一端进行，访问数据也只能访问到顶端的数据。要想要访问中间的数据必须通过出栈操作将目标数据移动到栈顶才行。
特点：栈特别适合只访问最新数据的场景。比如字符串括号处理、深度优先搜索算法候补顶点管理（选择最新数据作为候补顶点）、函数方法执行等等。
# 队列
队列 (opens new window)中的数据也是一种呈现线性排列的数据结构。 队列同栈一样，也是一个受限的线性表，与栈有些相似，但是队列中添加和删除数据的操作分别是在两端进行的，队列的处理总是从第一名开始往后进行，而新来的数据只能排在队尾（表头删除、表尾插入）。 我们可以理解为一条水管、没有底的子弹匣。
入队：往队列中添加数据的操作，在表尾部插入数据。 出队：从队列中删除数据的操作，在表头部删除数据。
先进先出（First In First Out，FIFO）：队列这种数据最先进去的数据最先被取出来，即“先进先出”的结构，我们称为FIFO。
操作：队列操作受限，队列中的数据分别在两端进行，队尾插入数据，对头删除数据，队列也不能直接访问中间的数据，必须通过出队操作将目标数据变成对首后才能访问。
应用：先进先出表示着“先来的数据先处理”的思路，应用范围很广泛，例如广度优先搜索算法的候补顶点管理（通常从搜索候补中选择最早的数据作为下一个顶点）
# 哈希表
哈希表 (opens new window)这种数据结构存储的是由键（key）和值（value）组成的数据，通过“哈希函数”使得数据的查询效率得到显著提升。 一般来说，可以把键当成数据的标识符，把值当成数据的内容。
我们知道呈现线性排列的数据结构（例如数组、链表）随着数据量越大，线性查找消耗的时间就越长，哈希表就是为了解决这个问题而产生的数据结构。 它通常是“数组” + “链表”的组合形式，数组用来存储数据，链表来“解决哈希冲突”。一般通过哈希函数计算数据元素的键，将得到的哈希值和数组的长度取余，得到的结果就是数组的下标。 不可避免的是，这种计算下标的方式会出现存储位置重复的情况，也成“哈希冲突”，遇到这种情况，可使用链表在已有数据的后面继续存储新的数据（链表）。 重复上述操作，知道所有数据被存储下来，最后就形成了哈希表的数据结构。
线性存储+分散存储：“数组” + “链表”的组合形式。（JDK1.8之后，HashMap改进了，某种情况下链表会改二叉树存储）
操作：查询数据的速度很快，可以利用哈希函数计算键快速访问到数组的目标数据，如果发生冲突，就使用链表来进行存储。
解决冲突：
- “链地址法”：利用链表在已有数据（数组元素）的后面插入新数据来解决冲突。
- “开放地址法”：当发生冲突，一次或多次使用哈希函数或者“线性探测法”等方法计算候补地址，直至没有冲突再将数据存进去。
# 堆
堆 (opens new window)是一种图的树形结构，被用于实现“优先队列”。 优先队列是一种数据结构，可以自由添加数据，但是取出数据的时需要从最小值开始按顺序取出。数据存储于每个树形结构的顶点中，称之为“结点”。
堆中结点内存储着数据，每个结点最多有两个子结点。树的形状、高度取决于数据的个数。结点的排列顺序为从上到下，同一行里则为从左到右。
规则 ：子结点必须大于夫结点。故此有规律：最小值被存储在顶点的根结点中。
操作：
- 添加数据：为了遵循上述规则，往堆中添加数据堆时候，一般会把新数据放在最下面一行靠左堆位置，当最下面一行没有对于空间的时候，往下另起一行将数据加在这行最左端。（尾端添加，往上调整）
- 取出数据：取出最小的数据，堆重新调整，以遵循上述规则。（顶端取出，往下调整）
时间复杂度：
- 取出最小值：$$O(1)$$。始终从根结点取出最小值。
- 取出数据，调整树：$$O(logn)$$。取出数据后需要将最后的数据移到顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据时间和树的高度成正比。 假设数据量为n，根据堆的形状特点可知树的高度为$$O(log_{2}n)$$，那么重构树的时间复杂度为$$O(logn)$$。
- 添加数据，调整树：$$O(logn)$$。同取出数据一样，在堆最后添加数据的时候，数据会一边比较它与父结点大小，一边往上移动，直到满足堆条件为止。
应用：堆适合频繁从数据中取出最小值的应用场景。例如：狄克斯特拉算法，每一步都需要从候补顶点中选择距离起点最近的顶点。
# 二叉查找树
二叉查找树 (opens new window)（二叉搜索树或二叉排序树）是一种采用了图的树形结构。同样数据存储于每个结点中。
两个性质：
- 每个结点的值均大于其左子树上任意一个结点的值。
- 每个结点的值均小于其右子树上任意一个结点的值。
由性质得到结论：
- 二叉查找树的最小结点应从顶端开始，往其左下的末端寻找。
- 二叉查找树的最大结点应从顶端开始，往其右下的末端寻找。
操作：
- 添加操作：新增数据从顶点开始进行比较（遵循二叉查找树的规则），寻找添加数字的位置。
- 删除操作：如果删除的结点没有子结点，直接删除。如果有一个子结点，先删除目标结点，再把子结点移到被删除结点位置即可。 如果有两个或两个以上的结点，先删除目标结点，再寻找左子树下最大的结点或右子树的最小结点移动到被删除结点位置，如果移动的结点还有子结点，则递归前面操作即可。
- 查询操作：依据二叉查找树的性质，从顶点开始搜索即可。
二叉查找树可以当作二分查找算法思想的树形结构体现。二分查找算法同样具有上述的两个性质，所以在查找数据或者寻找合适添加数据的位置的时候， 只需要将其和现有数据进行比较大小，就可以根据比较结果得知往哪里移动。
二叉查找树时间复杂度，记数据量为n：
- 添加、删除、查询：$$O(logn)$$或$$O(n)$$。操作次数取决于比较的次数，比较次数取决于树的高度。 如果树的形状比较均衡，比较大小和移动的次数最多就是$$O(log_{2}n)$$，所以时间复杂度为$$O(logn)$$。 如果树的形状朝着单侧纵向延伸，树就会变得很高，所以时间复杂度为$$O(n)$$。
有很多以平衡二叉树为基础拓展的数据结构：
- “平衡二叉树”：修正形状不均衡的树，让其始终保持均衡状态，以提高查找效率。
- “B树”：平衡二叉树一个结点最多有两个结点，这里将子结点数扩展为m，这种子结点数可以自由设定，并且形状均衡的树便是B树。