数据结构知识收集尊享版（迅速了解回顾相关知识）

1、单链表、循环链表、双向链表，存储、逻辑结构

单链表、循环链表和双向链表都是线性表的链式存储结构，它们在存储和逻辑结构上有一些共同点和不同点。

存储结构

单链表：每个节点包含一个数据域和一个指针域，指针域指向下一个节点。最后一个节点的指针域为空（NULL），表示链表的结束。
循环链表：与单链表类似，每个节点包含一个数据域和一个指针域，但最后一个节点的指针域指向链表的头节点，形成一个闭环。
双向链表：每个节点包含一个数据域和两个指针域，一个指向前驱节点，一个指向后继节点。头节点的前驱指针为空，尾节点的后继指针为空。

逻辑结构

单链表：
- 优点：插入和删除操作只需要修改指针，不需要移动元素，时间复杂度为 (O(1))。
- 缺点：只能从头节点开始遍历，查找某个节点需要 (O(n)) 的时间复杂度。
循环链表：
- 优点：可以方便地从任意节点开始遍历整个链表，适合某些需要循环操作的场景（如循环队列）。
- 缺点：查找某个节点的时间复杂度仍然是 (O(n))，但可以避免链表为空时的特殊情况处理。
双向链表：
- 优点：可以从任意节点向前或向后遍历，插入和删除操作更加灵活，时间复杂度为 (O(1))。
- 缺点：每个节点需要额外的指针空间，占用更多的内存。

应用场景

单链表：适用于需要频繁插入和删除操作，且不需要频繁查找的场景。
循环链表：适用于需要循环操作的场景，如循环队列、圆形游戏等。
双向链表：适用于需要频繁双向遍历的场景，如浏览器的前进后退功能、某些双向队列等。

2、栈、循环队列，元素个数判断、空/非空判断、多次进出后存储情况

栈和循环队列也都是线性数据结构，但它们在元素的进出顺序和存储方式上有所不同。

栈

元素个数判断：栈的元素个数可以通过一个计数器来记录，每次入栈时计数器加1，出栈时计数器减1。
空/非空判断：
- 空判断：如果计数器为0，则栈为空。
- 非空判断：如果计数器大于0，则栈非空。
多次进出后的存储情况：
- 栈遵循后进先出（LIFO）的原则，即最后进入的元素最先被取出。
- 多次进出后，栈顶元素始终是最近一次入栈且未被取出的元素。
- 如果栈的容量有限，多次进出时需要注意栈满的情况，防止溢出。

循环队列

元素个数判断：循环队列的元素个数可以通过队尾指针和队首指针的差值来计算，但需要注意循环的情况。
- 如果队尾指针大于队首指针，元素个数为 rear - front。
- 如果队尾指针小于队首指针，元素个数为 rear - front + capacity，其中 capacity 是队列的容量。
空/非空判断：
- 空判断：如果队首指针等于队尾指针，则队列为空。
- 非空判断：如果队首指针不等于队尾指针，则队列非空。
多次进出后的存储情况：
- 循环队列遵循先进先出（FIFO）的原则，即先进入的元素最先被取出。
- 多次进出后，队首指针始终指向队列的第一个元素，队尾指针指向队列最后一个元素的下一个位置。
- 为了避免队列满时的判断错误，通常会牺牲一个存储空间来区分队列满和队列空的情况。例如，当 (rear + 1) % capacity == front 时，队列满。

应用场景

栈：适用于需要回溯或撤销操作的场景，如函数调用的堆栈、浏览器的后退功能、括号匹配等。
循环队列：适用于需要循环操作的场景，如任务调度、缓冲区管理等。

注意事项

栈：在使用栈时，需要注意栈溢出的情况，尤其是在递归调用深度较大的情况下。
循环队列：在使用循环队列时，需要注意队列满和队列空的判断条件，避免误判。

3、串next求取、BF及KMP模式匹配过程

串的next数组求取

KMP算法中的next数组用于记录模式串中每个字符的前缀和后缀的最大相同长度。具体求取过程如下：

初始化：
- next[0] = -1，表示第一个字符没有前缀和后缀可以比较。
- 初始化两个指针 j 和 k，其中 j 用于遍历模式串，k 用于记录前缀的长度。
计算next数组：
- 当 k == -1 或者模式串的第 j 个字符与第 k 个字符相等时，next[j] = k，然后 j 和 k 都加1。
- 如果不相等，则 k 更新为 next[k]，继续比较。
循环结束：
- 当 j 遍历完整个模式串时，next数组计算完成。

BF模式匹配过程

BF算法（暴力匹配算法）是最简单的字符串匹配算法：

初始化：
- 设置两个指针 i 和 j，分别指向文本串和模式串的起始位置。
匹配过程：
- 如果 text[i] 和 pattern[j] 相等，则 i 和 j 都向后移动一位。
- 如果不相等，则将模式串向后移动一位，即 j 重置为0，i 指向下一个字符。
匹配成功：
- 当 j 达到模式串的末尾时，表示匹配成功，返回 i - j 作为匹配位置的起始索引。
匹配失败：
- 如果 i 遍历完文本串，则表示没有匹配到模式串。

KMP模式匹配过程

KMP算法利用next数组来优化匹配过程：

初始化：
- 设置两个指针 i 和 j，分别指向文本串和模式串的起始位置。
- 计算模式串的next数组。
匹配过程：
- 如果 text[i] 和 pattern[j] 相等，则 i 和 j 都向后移动一位。
- 如果不相等，则 j 更新为 next[j]，i 保持不变。
匹配成功：
- 当 j 达到模式串的末尾时，表示匹配成功，返回 i - j 作为匹配位置的起始索引。
匹配失败：
- 如果 i 遍历完文本串，则表示没有匹配到模式串。

KMP算法通过next数组减少了不必要的比较，从而提高了匹配效率。

4、二维数组存储计算

二维数组在计算机中通常以一维数组的形式存储，主要有两种存储方式：按行存储和按列存储。不同的存储方式会影响元素的访问和计算方式。以下是对这两种存储方式的详细说明：

按行存储（Row-major Order）

存储方式：二维数组的元素按行顺序存储在一维数组中。首先存储第一行的所有元素，然后是第二行的所有元素，依此类推。
地址计算：假设二维数组 A 的大小为 m x n，每个元素占用 size 个字节，基地址为 base，则元素 A[i][j] 的地址可以通过以下公式计算：
Address(A[i][j])=base+(i×n+j)×size
其中，i 是行索引，j 是列索引。

按列存储（Column-major Order）

存储方式：二维数组的元素按列顺序存储在一维数组中。首先存储第一列的所有元素，然后是第二列的所有元素，依此类推。
地址计算：同样假设二维数组 A 的大小为 m x n，每个元素占用 size 个字节，基地址为 base，则元素 A[i][j] 的地址可以通过以下公式计算：
Address(A[i][j])=base+(j×m+i)×size
其中，i 是行索引，j 是列索引.

示例

假设有一个二维数组 A，大小为 3 x 4，每个元素占用 4 个字节，基地址为 1000。按行存储和按列存储的地址计算如下：

按行存储：
- A[1][2] 的地址：
  Address(A[1][2])=1000+(1×4+2)×4=1000+24=1024
按列存储：
- A[1][2] 的地址：
  Address(A[1][2])=1000+(2×3+1)×4=1000+28=1028

树的遍历

树的遍历主要有三种方式：先序遍历、中序遍历和后序遍历。这些遍历方式通常用于二叉树，但也可以扩展到多叉树。

先序遍历

定义：先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。
过程：
1. 访问根节点。
2. 先序遍历左子树。
3. 先序遍历右子树。

中序遍历

定义：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
过程：
1. 中序遍历左子树。
2. 访问根节点。
3. 中序遍历右子树。

后序遍历

定义：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
过程：
1. 后序遍历左子树。
2. 后序遍历右子树。
3. 访问根节点.

二叉树的顺序存储

二叉树的顺序存储是将二叉树的节点存储在一个一维数组中，按照从上到下、从左到右的顺序排列。这种存储方式适用于完全二叉树和满二叉树，但对于一般的二叉树可能会浪费空间。

存储规则

根节点：存储在数组的第一个位置（索引为0）。
左子节点：对于索引为 i 的节点，其左子节点的索引为 2i + 1。
右子节点：对于索引为 i 的节点，其右子节点的索引为 2i + 2。
父节点：对于索引为 i 的节点，其父节点的索引为 (i - 1) / 2（向下取整）.

示例

假设有一个二叉树，其节点值如下：

        1/ \2   3/ \   \4   5   6

其顺序存储的数组为 [1, 2, 3, 4, 5, 6]。

应用场景

先序遍历：常用于复制树结构、打印树结构等。
中序遍历：对于二叉搜索树，中序遍历可以得到节点值的有序序列。
后序遍历：常用于计算树的大小、删除树等。
顺序存储：适用于完全二叉树和满二叉树，如堆的实现.

注意事项

遍历递归实现：递归实现简单直观，但可能会导致栈溢出，尤其是在树的深度较大时。
非递归实现：可以使用栈来实现非递归遍历，避免递归调用的开销。
顺序存储空间浪费：对于一般的二叉树，顺序存储可能会浪费大量空间，因为需要为不存在的节点预留位置。

哈夫曼树的构建

哈夫曼树是一种用于数据压缩的无损编码方法，其构建过程如下：

初始化：
- 将每个字符及其出现的频率视为一个节点，初始化一个优先队列（最小堆），将所有节点加入队列。
构建过程：
- 从优先队列中取出两个权值最小的节点。
- 创建一个新的节点，其权值为两个取出节点的权值之和。
- 将新节点的左子节点和右子节点分别设置为取出的两个节点。
- 将新节点重新加入优先队列。
- 重复上述步骤，直到优先队列中只剩下一个节点，该节点即为哈夫曼树的根节点。

哈夫曼编码的求取

哈夫曼编码是通过哈夫曼树来确定每个字符的编码，具体步骤如下：

初始化：
- 从哈夫曼树的根节点开始，初始化一个空字符串作为编码路径。
编码过程：
- 从根节点向叶子节点遍历：
  - 如果向左子节点移动，则在编码路径上添加“0”。
  - 如果向右子节点移动，则在编码路径上添加“1”。
- 当到达叶子节点时，该叶子节点对应的字符的编码即为当前的编码路径。
编码结果：
- 每个字符的哈夫曼编码是唯一的，且通常较短的编码分配给出现频率较高的字符。

示例

假设有一组字符及其频率：A(5), B(9), C(12), D(13), E(16), F(45)，构建哈夫曼树并求取编码的过程如下：

构建哈夫曼树：
- 初始优先队列：A(5), B(9), C(12), D(13), E(16), F(45)
- 取出 A(5) 和 B(9)，创建新节点 AB(14)，加入队列：AB(14), C(12), D(13), E(16), F(45)
- 继续合并，直到构建完整棵树。
求取编码：
- 从根节点开始遍历，最终得到每个字符的编码：
  - F: 0
  - C: 100
  - D: 101
  - A: 1100
  - B: 1101
  - E: 111

邻接矩阵和邻接表

邻接矩阵

定义：邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。
存储方式：
- 对于无向图，邻接矩阵是对称的。A[i][j] 表示顶点 i 和顶点 j 之间的边的权重。如果 i 和 j 之间没有边，则 A[i][j] 为无穷大或一个特定的值（如0）。
- 对于有向图，邻接矩阵不一定对称。A[i][j] 表示从顶点 i 到顶点 j 的边的权重。
优点：
- 可以快速判断两个顶点之间是否存在边。
缺点：
- 空间复杂度高，尤其是对于稀疏图，会浪费大量空间。

邻接表

定义：邻接表是一个数组，每个数组元素是一个链表，用于存储与该顶点相邻的所有顶点。
存储方式：
- 对于无向图，每个顶点的邻接表中存储与其相连的所有顶点。
- 对于有向图，每个顶点的邻接表中存储其所有出边的目标顶点。
优点：
- 空间复杂度低，适合稀疏图。
缺点：
- 判断两个顶点之间是否存在边需要遍历链表，时间复杂度较高。

深度优先遍历（DFS）和广度优先遍历（BFS）

深度优先遍历（DFS）

过程：
- 从一个顶点开始，沿着一条路径尽可能深地搜索，直到无法继续前进。
- 回溯到上一个顶点，继续搜索其他未访问的路径。
实现：
- 使用递归或栈来实现。
- 标记已访问的顶点，避免重复访问。
应用：
- 用于寻找路径、检测图的连通性等。

广度优先遍历（BFS）

过程：
- 从一个顶点开始，逐层访问其所有邻接顶点。
- 访问完一层的所有顶点后，再访问下一层的顶点。
实现：
- 使用队列来实现。
- 标记已访问的顶点，避免重复访问。
应用：
- 用于寻找最短路径、检测图的连通性等。

最小生成树求取

Prim算法

过程：
- 从任意一个顶点开始，将其加入生成树。
- 在生成树的顶点集合中，选择一条连接生成树和非生成树顶点的最小权值边，将该边的非生成树顶点加入生成树。
- 重复上述步骤，直到所有顶点都加入生成树。
实现：
- 使用优先队列（最小堆）来优化选择最小权值边的过程。
应用：
- 适用于稠密图，因为每次只需要选择一个顶点。

Kruskal算法

过程：
- 将图中的所有边按权值从小到大排序。
- 依次选择权值最小的边，如果该边的两个顶点不在同一个连通分量中，则将其加入生成树。
- 重复上述步骤，直到生成树包含所有顶点。
实现：
- 使用并查集来检测连通分量。
应用：
- 适用于稀疏图，因为每次只需要选择一条边.

这两种算法都可以有效地求取无向图的最小生成树，选择哪种算法取决于图的稠密程度和具体的应用场景。

二叉排序树（也称为二叉查找树或二叉搜索树）是一种特殊的二叉树，其中每个节点的值大于其左子树中所有节点的值，小于其右子树中所有节点的值。以下是关于二叉排序树的生成和查找的详细说明：

二叉排序树的生成

插入过程

步骤：
1. 初始化：从根节点开始。
2. 比较：将要插入的值与当前节点的值进行比较。
  - 如果要插入的值小于当前节点的值，则移动到当前节点的左子节点。
  - 如果要插入的值大于当前节点的值，则移动到当前节点的右子节点。
3. 递归：重复上述比较和移动过程，直到找到一个空的子节点位置。
4. 插入：在找到的空位置插入新节点。

示例

假设我们要将以下值依次插入到一个空的二叉排序树中：50, 30, 20, 40, 70, 60, 80。

插入 50：作为根节点。
插入 30：小于 50，插入到 50 的左子节点。
插入 20：小于 30，插入到 30 的左子节点。
插入 40：大于 30，插入到 30 的右子节点。
插入 70：大于 50，插入到 50 的右子节点。
插入 60：小于 70，插入到 70 的左子节点。
插入 80：大于 70，插入到 70 的右子节点。

最终生成的二叉排序树如下：

        50/  \30    70/  \  /  \20  40 60  80

二叉排序树的查找

查找过程

步骤：
1. 初始化：从根节点开始。
2. 比较：将要查找的值与当前节点的值进行比较。
  - 如果要查找的值等于当前节点的值，则查找成功，返回当前节点。
  - 如果要查找的值小于当前节点的值，则移动到当前节点的左子节点。
  - 如果要查找的值大于当前节点的值，则移动到当前节点的右子节点。
3. 递归：重复上述比较和移动过程，直到找到目标节点或到达空节点。
4. 查找失败：如果到达空节点，则表示查找失败，返回空。

示例

假设我们要在上述生成的二叉排序树中查找值 40。

从根节点 50 开始。
40 小于 50，移动到左子节点 30。
40 大于 30，移动到右子节点 40。
找到目标节点 40，查找成功。

如果要查找值 45，则：

从根节点 50 开始。
45 小于 50，移动到左子节点 30。
45 大于 30，移动到右子节点 40。
45 大于 40，但 40 的右子节点为空，查找失败.

冒泡排序（Bubble Sort）

过程：
1. 比较相邻的元素，如果第一个元素大于第二个元素，就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

选择排序（Selection Sort）

过程：
1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

插入排序（Insertion Sort）

过程：
1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

希尔排序（Shell Sort）

过程：

1.选择一个增量序列 t1,t2,….,tk，其中 t> ti+1，且 tk =1。
2.按增量序列个数 k，对序列进行 k 趟插入排序。
3.每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度

快速排序（Quick Sort）

过程：
1. 选择一个基准值（pivot），通常选择序列的第一个元素或最后一个元素。
2. 将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数组的中间位置。
3. 递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。

归并排序（Merge Sort）

过程：
1. 将序列每相邻两个数字进行归并操作，形成 [n/2] 个序列，排序后每个序列包含两个元素。
2. 将上述序列再次归并，形成[n/4]个序列，每个序列大概包含四个元素。
3. 重复上述操作，直到所有元素排序完毕。

堆排序（Heap Sort）

过程：
1. 将待排序序列构建成一个大顶堆，此时，整个序列的最大值就是堆顶元素。
2. 将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端。
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行，直至整个序列有序。

基数排序（Radix Sort）

过程：
1. 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
2. 从最低位开始，依次进行稳定排序（通常使用计数排序）。
3. 重复上述过程，直到最高位排序完成。

桶排序（Bucket Sort）

过程：
1. 设置一个定量的数组当作空桶。
2. 遍历输入数据，并且把数据根据其特征值放入对应的桶中。
3. 对每个不为空的桶进行排序，可以使用其他排序算法，或者递归地使用桶排序。
4. 按顺序把桶中的数据拼起来。

哈希表是一种通过哈希函数将键（key）映射到值（value）的数据结构，具有高效的查找、插入和删除操作。当哈希冲突发生时，需要采用一定的解决方法。线性探测法和二次探测法是两种常用的解决哈希冲突的方法。

哈希表求取

选择哈希函数：
- 哈希函数将键映射到哈希表中的一个索引位置。常见的哈希函数包括除法哈希、乘法哈希等。
- 例如，除法哈希函数：hash(key) = key % table_size，其中 table_size 是哈希表的大小。
处理哈希冲突：
- 当两个不同的键映射到同一个索引位置时，发生哈希冲突。需要采用一定的方法解决冲突，如链表法、线性探测法、二次探测法等。

线性探测法

基本思想：
- 当发生哈希冲突时，线性探测法从冲突位置开始，线性地向后探测，直到找到一个空的槽位。
- 探测序列是线性的，即 h(key) + i，其中 i 是探测次数，从0开始递增。
插入过程：
1. 计算键的哈希值 h(key)。
2. 如果 h(key) 位置为空，则直接插入。
3. 如果 h(key) 位置已被占用，则从 h(key) 开始线性探测，直到找到一个空的槽位插入。
查找过程：
1. 计算键的哈希值 h(key)。
2. 从 h(key) 开始线性探测，直到找到目标键或探测到一个空槽位（表示查找失败）。

二次探测法

基本思想：
- 当发生哈希冲突时，二次探测法从冲突位置开始，按照二次方的步长进行探测，直到找到一个空的槽位。
- 探测序列是二次的，即 h(key) + i^2，其中 i 是探测次数，从1开始递增。
插入过程：
1. 计算键的哈希值 h(key)。
2. 如果 h(key) 位置为空，则直接插入。
3. 如果 h(key) 位置已被占用，则从 h(key) 开始二次探测，直到找到一个空的槽位插入。
查找过程：
1. 计算键的哈希值 h(key)。
2. 从 h(key) 开始二次探测，直到找到目标键或探测到一个空槽位（表示查找失败）。

优缺点比较

线性探测法：
- 优点：实现简单。
- 缺点：容易产生聚集现象，即多个键聚集在连续的槽位中，导致探测长度增加，性能下降。
二次探测法：
- 优点：可以减少聚集现象，探测序列更加分散。
- 缺点：实现相对复杂，且在某些情况下可能会探测到重复的位置（如当 i 和 j 的平方模 table_size 相等时）。