# 数据结构 ## 数组 ### 如何实现随机访问？ 数组是最常用的数据结构,创建数组必须要内存中一块**连续**的空间,并且数组中必须存放**相同**的数据类型 随机快速读写是数组的一个重要特性,但是要随机访问数据,必须知道数据在数组中的下标。如果我们只是知道数据的值,想要在数组中找到这个值,那么就只能遍历整个数组,时间复杂度为 O(N) 数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。 ### 低效的“插入”和“删除” #### 插入 如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法 搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个 存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模 的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最 后，把新的元素直接放入第 k 个位置。 #### 删除 实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次 删除操作集中在一起执行，删除的效率是不是会提高很多呢？ #### 警惕数组的访问越界问题 ## 链表 链表可以使用零散的内存空间存储数据。 链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。 因为链表是不连续存储的,要想在链表中查找一个数据,只能遍历链表,所以链表的查找复杂度总是 O(N)。 在链表中插入或者删除一个数据是非常容易的,只要找到要插入(删除)的位置,修改链表指针就可以了。 ### 单链表 把第一个结点叫作头结点，把最后一个结点叫作尾结 点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结 点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表 上最后一个结点。 ### 循环链表 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾 结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表 的尾结点指针是指向链表的头结点。 ### 双向链表 双向链表，顾名 思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前 驱指针 prev 指向前面的结点。 从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特 点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。 用空间换时间的设计思想。当内 存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较 高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在 手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。 ### 如何写链表 #### 理解指针或引用的含义 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中 存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 #### 警惕指针丢失和内存泄漏 ![lianbiao_zhizhen.png](/images/lianbiao_zhizhen.png) 如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。 ``` p->next = x; // 将 p 的 next 指针指向 x 结点； x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点； ``` 初学者经常会在这儿犯错。p->next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整 个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。 #### 利用哨兵简化实现难度 如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨 兵结点。我们也把这种有哨兵结点的链表叫**带头链表**。相反，没有哨兵结点的链表就叫作不 **带头链表**。 #### 重点留意边界条件处理 我经常用来检查链表代码是否正确的边界条件有这样几个： 如果链表为空时，代码是否能正常工作？ 如果链表只包含一个结点时，代码是否能正常工作？ 如果链表只包含两个结点时，代码是否能正常工作？ 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？ #### 举例画图，辅助思考 #### 多写多练，没有捷径 * 单链表反转 * 链表中环的检测 * 两个有序的链表合并 * 删除链表倒数第 n 个结点 * 求链表的中间结点 ## 栈 栈就是在线性表的基础上加了这样的操作限制条件:后面添加的数据,在删除的时候必须先删除,即通常所说的“后进先出” 栈在线性表的基础上增加了操作限制,具体实现的时候,因为栈不需要随机访问、也不需要在中间添加、删除数据,所以可以用数组实现,也可以用链表实现。 用数组实现的栈，我们叫作**顺序 栈**，用链表实现的栈，我们叫作**链式栈**。 ### 如何实现一个栈 ``` // 基于数组实现的顺序栈 public class ArrayStack { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; // 栈的大小 // 初始化数组，申请一个大小为 n 的数组空间 public ArrayStack(int n) { this.items = new String[n]; this.n = n; this.count = 0; } // 入栈操作 public boolean push(String item) { // 数组空间不够了，直接返回 false，入栈失败。 if (count == n) return false; // 将 item 放到下标为 count 的位置，并且 count 加一 items[count] = item; ++count; return true; } // 出栈操作 public String pop() { // 栈为空，则直接返回 null if (count == 0) return null; // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一 String tmp = items[count-1]; --count; return tmp; } } ``` 存储数据只需要一个大小为 n 的数组就够了。在入栈和出 栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。 注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空 间外，算法运行还需要额外的存储空间。 时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈 只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。 ### 栈在函数调用中的应用 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种 结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入 栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了让你更好地理 解，我们一块来看下这段代码的执行过程。 ### 栈在表达式求值中的应用 ### 栈在括号匹配中的应用 ## 队列 队列是先进先出 ### 如何理解队列 栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持 的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出 队 dequeue()，从队列头部取一个元素。 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用 链表实现的栈叫作链式栈。同样，用数组实现的队列叫作**顺序队列**，用链表实现的队列叫作 **链式队列**。 ``` // 用数组实现的队列 public class ArrayQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head 表示队头下标，tail 表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为 capacity 的数组 public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 如果 tail == n 表示队列已经满了 if (tail == n) return false; items[tail] = item; ++tail; return true; } // 出队 public String dequeue() { // 如果 head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了 String ret = items[head]; ++head; return ret; } } ``` ### 循环队列 在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？ 队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。 当队满时，(tail+1)%n=head，tail 指向的位置实际上是没有存储数据的。所以，循 环队列会浪费一个数组的存储空间。 ### 阻塞队列和并发队列 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队 头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已 经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返 回。 阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在 线程安全问题，那如何实现一个线程安全的队列呢？ 线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、 dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操 作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。 这也是循环队列比链式队列应用更加广泛的原因 ## hash表 Hash 表中数据以 Key、Value 的方式存储 Hash 表的物理存储其实是一个数组,如果我们能够根据 Key 计算出数组下标,那么就可以快速在数组中查找到需要的 Key 和 Value。 不同的 Key 有可能计算得到相同的数组下标,这就是所谓的 Hash 冲突,解决 Hash 冲突常用的方法是链表法。 因为数组要求存储固定数据类型,主要目的是每个数组元素中要存放固定长度的数据。 所以,数组中存储的是 Key、Value 数据元素的地址指针。一旦发生 Hash 冲突,只需要将相同下标,不同 Key 的数据元素添加到这个链表就可以了。查找的时候再遍历这个链表, 匹配正确的 Key。 ## 递归 ### 递归需要满足的三个条件 1. 一个问题的解可以分解为几个子问题的解 2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 3. 存在递归终止条件 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写 出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一 层层的调用关系，不要试图用人脑去分解递归的每个步骤。 ### 递归代码要警惕堆栈溢出 最大允许的递归深度跟当前线程剩余的栈空间大小有 关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最 大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。 ### 递归代码要警惕重复计算 ## 排序 ### 冒泡排序 ![maopao_liucheng.png](/images/maopao_liucheng.png) 可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数 据的排序，我们只要进行 6 次这样的冒泡操作就行了。 ![maopao.png](/images/maopao.png) ``` // 冒泡排序，a 表示数组，n 表示数组大小 public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循环的标志位 boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交换 int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true; // 表示有数据交换 } } if (!flag) break; // 没有数据交换，提前退出 } } ``` **第一，冒泡排序是原地排序算法吗？** 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。 **第二，冒泡排序是稳定的排序算法吗？** 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定 性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会 改变顺序，所以冒泡排序是稳定的排序算法。 **第三，冒泡排序的时间复杂度是多少？** 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束 了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列 的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。 对于包含 n 个数据的数组，这 n 个数据就有 n! 种排列方式。不同的排列方式，冒泡排序执 行的时间肯定是不同的。比如我们前面举的那两个例子，其中一个要进行 6 次冒泡，而另 一个只需要 4 次。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就 会很复杂。我这里还有一种思路，通过“有序度”和“逆序度”这两个概念来进行分析。 有序度是数组中具有有序关系的元素对的个数。 同理，对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有 序的数组，比如 1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是 15。我们把这种完全 有序的数组的有序度叫作满有序度。 **逆序度 = 满有序度 - 有序度。** ### 插入排序 ![charu.png](/images/charu.png) ``` // 插入排序，a 表示数组，n 表示数组大小 public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置 for (; j >= 0; --j) { if (a[j] > value) { a[j+1] = a[j]; // 数据移动 } else { break; } } a[j+1] = value; // 插入数据 } } ``` **第一，插入排序是原地排序算法吗？** 从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复 杂度是 O(1)，也就是说，这是一个原地排序算法。 **第二，插入排序是稳定的排序算法吗？** 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素 的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。 **第三，插入排序的时间复杂度是多少？** 如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数 据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下， 最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。 ### 选择排序 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序 每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。 ![xuanze.png](/images/xuanze.png) 首先，选择排序空间复杂度为 O(1)，是一种原地排序算法。选择排序的最好情况时间复杂 度、最坏情况和平均情况时间复杂度都为O(n2) 选择排序是一种不稳定的排序算法。从我前面画的那张图中，你可以看出 来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏 了稳定性。 ### 归并排序 如果要排序一个数组，我们先把数组从中间分成前后两 部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有 序了。 ### 快速排序 如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。 如果我们用递推公式来将上面的过程写出来的话，就是这样： ``` 递推公式： quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1, r) 终止条件： p >= r ``` 我将递推公式转化成递归代码。跟归并排序一样，我还是用伪代码来实现，你可以翻译成你 熟悉的任何语言。 ``` // 快速排序，A 是数组，n 表示数组的大小 quick_sort(A, n) { quick_sort_c(A, 0, n-1) } // 快速排序递归函数，p,r 为下标 quick_sort_c(A, p, r) { if p >= r then return q = partition(A, p, r) // 获取分区点 quick_sort_c(A, p, q-1) quick_sort_c(A, q+1, r) } ``` ## 树 非线性表