1. 数据结构
1. 数据结构
- 数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构”
- 将数据存储于内存时，根据使用的目的选择合适的数据结构，可以调高内存的利用率
- 数据在内存中是呈线性排列的，但是我们 也可以使用指针等道具，构造出类似“树形”的复杂结构1
2. 链表
链表是数据结构之一，其中的数据呈线性排列；在链表中，数据的添加和删除都较为方便， 就是访问比较耗费时间
- 这就是链表的概念图。Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表中。每个数据都有 1 个 “指针”，它指向下一个数据的内存地址
- 在链表中，数据一般都是分散存储于内存中 的，无须存储在连续空间内
- 因为数据都是分散存储的，所以如果想要访问 数据，只能从第1个数据开始，顺着指针的指 向一一往下访问（这便是顺序访问）。比如，想 要找到Red这一数据，就得从Blue开始访问
- 如果想要添加数据，只需要改变添加位置前后 的指针指向就可以，非常简单。比如，在Blue 和Yellow之间添加Green
- 数据的删除也一样，只要改变指针的指向就可 以，比如删除Yellow；虽然 Yellow 本身还存储在 内存中，但是不管从哪里都无法访问这个数据，所以也就没有特意去删除它的必要了。今后需要用到 Yellow所在的存储空间时，只要用新数据覆盖掉就可以了
2.1 耗时
- 我们把链表中的数据量记成 n，访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后 的话，需要的时间就是 O(n)
- 添加数据只需要更改两个指针的指向，所以耗费的时间与 n 无关。如果已 经到达了添加数据的位置，那么添加操作只需花费 O(1) 的时间。删除数据同样也只需 O(1) 的时间
2.2 循环/双向链表
- 虽然上文中提到的链表在尾部没有指针，但我们也可以在链表尾部使用指针，并且 让它指向链表头部的数据，将链表变成环形，这便是“循环链表”，循环链表没有头和尾的概念，想要保存数量固定的最新数据时通常会使用这种链表
-
另外，上文链表里的每个数据都只有一个指针，但我们可以把指针设定为两个，并 且让它们分别指向前后数据，这就是“双向链表”。使用这种链表，不仅可以从前往后， 还可以从后往前遍历数据，十分方便
-
但是，双向链表存在两个缺点：一是指针数的增加会导致存储空间需求增加；二是 添加和删除数据时需要改变更多指针的指向
3. 数组
数组也是数据呈线性排列的一种数据结构，与前一节中的链表不同，在数组中，访问数据十分简单，而添加和删除数据比较耗工夫
- 这就是数组的概念图。Blue、Yellow、Red作为数据存储在数组中。
- 数据按顺序存储在内存的连续空间内。
- 由于数据是存储在连续空间内的，所以每个数 据的内存地址（在内存上的位置）都可以通过 数组下标算出，我们也就可以借此直接访问目 标数据（这叫作“随机访问”）。
- 比如现在我们想要访问Red。如果使用指针就 只能从头开始查找，但在数组中，只需要指定 a[2]，便能直接访问Red。
- 但是，如果想在任意位置上添加或者删除数 据，数组的操作就要比链表复杂多了。这里我 们尝试将Green添加到第2个位置上。
- 首先，在数组的末尾确保需要增加的存储空间。
- 为了给新数据腾出位置，要把已有数据一个个 移开。首先把Red往后移。
- 然后把Yellow往后移。
- 最后在空出来的位置上写入Green。添加数据的操作就完成了，反过来，如果想要删除Green……
- 首先，删掉目标数据（在这里指 Green）。
- 然 后 把 后 面 的 数 据 一 个 个 往 空 位 移。 先 把 Yellow往前移。
- 接下来移动Red。
- 最后再删掉多余的空间。这样一来Green便被删掉了。
3.1 耗时
- 假设数组中有 n 个数据，由于访问数 据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的 O(1)。
- 但另一方面，想要向数组中添加新数据时，必须把目标位置后面的数据一个个移 开。所以，如果在数组头部添加数据，就需要 O(n) 的时间。删除操作同理。
3.2 数组和链表对比
-
在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和 删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂。
-
我们可以根据哪种操作较为频繁来决定使用哪种数据结构。
4. 栈
栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数 据
- 这就是栈的概念图。现在存储在栈中的只有数据Blue。
- 然后，栈中添加了数据Green。
- 接下来，数据Red入栈。
- 从栈中取出数据时，是从最上面，也就是最新 的数据开始取出的。这里取出的是Red。
4.1 解说
- 像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为 Last In First Out，简称 LIFO
- 与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只 能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通 过出栈操作将目标数据移到栈顶才行
5. 队列
队列中的数据也呈线性排列。虽然与栈有些相似，但队列中 添加和删除数据的操作分别是在两端进行的，处理总是从第一名开始往后进行，而新来的人只能排在队尾
- 这就是队列的概念图。现在队列中只有数据Blue。
- 然后，队列中添加了数据Green。
- 从队列中取出（删除）数据时，是从最下面，也就 是最早入队的数据开始的。这里取出的是Blue。
5.1 解说
- 像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为 First In First Out，简称 FIFO
- 与栈类似，队列中可以操作数据的位置也有一定的限制。在栈中，数据的添加和删 除都在同一端进行，而在队列中则分别是在两端进行的。队列也不能直接访问位于中间 的数据，必须通过出队操作将目标数据变成首位后才能访问
6. 哈希表
- 哈希表存储的是由键（key）和值（value）组 成的数据。例如，我们将每个人的性别作为数 据进行存储，键为人名，值为对应的性别。
- 为了和哈希表进行对比，我们先将这些数据存 储在数组中
- 此处准备了 6 个箱子（即长度为 6 的数组）来存 储数据。假设我们需要查询Ally的性别，由于 不知道Ally的数据存储在哪个箱子里，所以只 能从头开始查询。这个操作便叫作“线性查找”
- 查找到4号箱子的时候，发现其中数据的键为 Ally。把键对应的值取出，我们就知道 Ally 的性 别为女（F）了。数据量越多，线性查找耗费的时间就越长。由 此可知 ：由于数据的查询较为耗时，所以此处 并不适合使用数组来存储数据。
- 但使用哈希表便可以解决这个问题。首先准备好数组，这次我们用5个箱子的数组来存储 数据。
- 使用哈希函数（Hash）计算 Joe的键，也就是 字符串“Joe”的哈希值。得到的结果为4928
- 将得到的哈希值除以数组的长度5，求得其余数。这样的求余运算叫作“mod 运算”。此处 mod运算的结果为3。
- 因此，我们将Joe的数据存进数组的3号箱子中。重复前面的操作，将其他数据也存进数组中。
- Nell键的哈希值为6276，mod 5的结果为1。本应将其存进数组的1号箱中，但此时1号箱中已经 存储了 Sue 的数据。这种存储位置重复了的情况便叫作“冲突”。
- 遇到这种情况，可使用链表在已有数据的后面 继续存储新的数据
- 想要查询Ally的性别时该怎么做呢？为 了找到它的存储位置，先要算出Ally键的哈希 值，再对其进行mod运算。最终得到的结果为3。
- 然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找，于是我们找到了键为Ally的数据。取出其对应 的值，便知道了 Ally 的性别为女（F）。
6.1 解说
- 在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希 冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。
- 如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也 会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此， 给数组设定合适的空间非常重要。
6.2 补充
- 在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据 来解决冲突。这种方法被称为“链地址法”。
- 除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地 址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数 据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通 过多次使用哈希函数或“线性探测法”等方法计算候补地址。
7. 堆
- 堆是一种图的树形结构，被用于实现“优先队列”（priority queues）
- 优先队列是一种数据结构，可以*添加数据，但取出数据时要从最小值开始按顺序取出
- 在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中
- 这就是堆的示例。结点内的数 字就是存储的数据。堆中的每个结点最多有两个子结点。树 的形状取决于数据的个数。另 外，结点的排列顺序为从上到 下，同一行里则为从左到右。
- 在堆中存储数据时必须遵守这 样一条规则 ：子结点必定大于父 结点。因此，最小值被存储在顶 端的根结点中。往堆中添加数据 时，为了遵守这条规则，一般会 把新数据放在最下面一行靠左 的位置。当最下面一行里没有多 余空间时，就再往下另起一行， 把数据加在这一行的最左端。
- 我们试试往堆里添加数 字5。
- 首先按照02的说明寻找新数据的位置。该图中最 下面一排空着一个位置，所以将数据加在此处。
- 如果父结点大于子结点，则不符合上文提到的 规则，因此需要交换父子结点的位置。
- 这里由于父结点的6大于子结点的5，所以交 换了这两个数字。重复这样的操作直到数据都 符合规则，不再需要交换为止。
- 从堆中取出数据时，取出的是最上面的数据。 这样，堆中就能始终保持最上面的数据最小。
- 由于最上面的数据被取出，因此堆的结构也需 要重新调整。
- 按照01中说明的排列顺序，将最后的数据（此 处为6）移动到最顶端，再经过一系列调整
- 这样，从堆中取出数据的操作便完成了。
7.1 耗时
- 堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都 为 O(1)。
- 另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据 的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为 n，根据堆的形状特点可知树的高度为 log2n ，那么重构树的时间复杂度便为 O(logn)。
- 添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大 小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度 成正比，也是 O(logn)。
8. 二叉查找树
- 二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构
- 数据存储于二叉查找树的各个结点中
- 这就是二叉查找树的示 例。结点中的数字便是 存储的数据。此处以不 存在相同数字为前提进 行说明。
- 二叉查找树有两个性质。第一个是每个结点的 值均大于其左子树上任意一个结点的值。比如 结点9大于其左子树上的3和8。同样，结点15也大于其左子树上任意一个结 点的值。
- 第二个是每个结点的值均小于其右子树上任意 一个结点的值。比如结点 15 小于其右子树上的 23、17和28。
- 根据这两个性质可以得到以下结论。首先，二 叉查找树的最小结点要从顶端开始，往其左下 的末端寻找。此处最小值为3。
- 反过来，二叉查找树的最大结点要从顶端开 始，往其右下的末端寻找。此处最大值为28。
- 下面我们来试着往二叉查找树中添加数据。比 如添加数字1。
- 首先，从二叉查找树的 顶端结点开始寻找添加 数字的位置。将想要添 加的1与该结点中的值 进行比较，小于它则往 左移，大于它则往右移。由于1＜9，所以将1往左移。由于1＜3，所以继续将1往左移，但前面已经没 有结点了，所以把 1 作为新结点添加到左下方。
- 这样，1的添加操作便完成了。接下来，我们再试试添加数字4。
- 于是4的添加操作也完成了。
- 接下来看看如何在二叉查找树中删除结点。比 如我们来试试删除结点28。如果需要删除的结点没有子结点，直接删掉该 结点即可。
- 再试试删除结点8。 如果需要删除的结点只有一个子结点，那么先 删掉目标结点……然后把子结点移到被删除结点的位置上即可。
- 最后来试试删除结点9。如果需要删除的结点有两个子结点，那么先删 掉目标结点……然后在被删除结点的左子树中寻找最大结 点……最后将最大结点移到被删除结点的位置上。这样一来，就能在满足二叉查找树性质的前提下删除结点了。 如果需要移动的结点（此处为4）还有子结点，就递归执行前面的操作（删除9的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据 二叉查找树的性质可知，移动“右子树中的最小结点”也没有问题。）
- 下面来看看如何在二叉查找树中查找结点。比 如我们来试试查找12。从二叉查找树的顶端结点开始往下查找。和添 加数据时一样，把12和结点中的值进行比较， 小于该结点的值则往左移，大于则往右移。
8.1 耗时
- 我们可以把二叉查找树当作是二分查找算法思想的树形结构体现，因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加 数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移 动了。
- 比较的次数取决于树的高度。所以如果结点数为 n，而且树的形状又较为均衡的话， 比较大小和移动的次数最多就是 log2n。因此，时间复杂度为 O(logn)。但是，如果树的 形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了 O(n)。
8.2 补充
- 有很多以二叉查找树为基础扩展的数据结构，比如“平衡二叉查找树”。这种数据 结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。
- 另外，虽然文中介绍的二叉查找树中一个结点最多有两个子结点，但我们可以把子 结点数扩展为 m（m 为预先设定好的常数）。像这种子结点数可以*设定，并且形状均 衡的树便是 B 树。
《我的第一本算法书》-- 宫崎修一 , 石田保辉