DataStructure

$\mathscr {score:}$

• 平时 20%（出勤、作业、实验）
• 期中 20%
• 期末 60%

数据结构

完整实现代码：https://github.com/Explorer-Dong/DataStructure

一、绪论

1.1 数据分析+结构存储+算法计算

1.1.1 逻辑结构

对于当前的数据之间的关系进行分析，进而思考应该如何存储，有以下几种逻辑结构：集合、线性结构、树形结构、图结构。

1.1.2 存储结构

设计一定的方法存储到程序中，需要思考：存什么？怎么存？

• 存什么？数值存储、数据与数据之间关系域的存储
• 怎么存？顺序存储、链式存储、树形存储、图存储

1.1.3 算法实现

设计算法计算实现

1.2 数据类型

约束：值集 + 运算集

数据类型 $\text{(Data Type, 简称 DT)}$：一般编程语言已经实现好了

抽象数据类型 $\text{Abstract Data Type, 简称 ADT}$：数据结构 + 算法操作

1.3 算法方法

1. 正确性

2. 健壮性（鲁棒性）：对于不合法、异常的输入也有处理能力

3. 可读性

4. 可扩展性

5. 高效率

   1. 空间复杂度

   2. 时间复杂度 $T(n)=O(f(n))$，其中有三种表示时间复杂度的公式

      • $O()$ upper bound：最坏的时间复杂度
      • $\Omega()$ lower bound：最好的时间复杂度
      • $\Theta()$ average bound：平均时间复杂度

二、线性表

2.1 线性表的逻辑结构

有一个头结点，尾结点，且每一个结点只有一个前驱结点和一个后继结点。

2.2 线性表的存储结构

2.2.1 顺序存储结构

存储在一维地址连续的存储单元里

特点：逻辑位置相邻，物理位置也相邻

数据结构：一个一个一维数组 + 一个长度变量 n

template<class T, int MaxSize>
class SeqList
{
    T data[MazSize];
    int length;
public:
    ...
}

顺序表可以直接存储元素与关系。链表的元素存储也是可以直接实现的，但是关系要通过指针域来实现

2.2.2 链式存储结构

1. 单链表：默认有一个头结点，不存储数据

2. 循环链表

3. 双向链表

2.3 线性表的操作算法

2.3.1 顺序表的操作算法

1. 初始化构造

2. 求顺序表长度

3. 按位查找

4. 按值查找

5. 遍历顺序表

6. 插入

7. 删除

2.3.2 链表的操作算法

1. 单链表初始化构造

   head = new Node<T>;
   head->next = nullptr;

   • 头插法

     head = new Node<T>;
     head->next = nullptr;

   • 尾插法

     head = new Node<T>;
     rear = head;

2. 求单链表长度

3. 按位查找

4. 按值查找

5. 遍历单链表

6. 插入

7. 删除

8. 单链表的析构函数

9. 其他操作

10. 双向链表操作

    • 插入

      

      // 插入当前结点 s
      s->prior = p;
      s->next = p->next;
      p->next->prior = s;
      p->next = s;

    • 删除

      

      // 删除当前结点 p
      p->next->prior = p->prior;
      p->prior->next = p->next;

三、栈和队列

3.1 栈

3.1.1 栈的基本概念

卡特兰数：假设 $f(k)$ 表示第 k 个数最后一个出栈的总个数，则 $f(k)=f(k-1)f(n-k)$

$$f(n) = \sum_{k=1}^{n} f(k-1) f(n-k)=\frac{1}{n+1} C_{2n}^{n}$$

3.1.2 栈的存储结构

顺序存储

链式存储

3.1.3 栈的操作算法

1. 顺序栈的操作
2. 链栈的操作

3.1.4 栈的应用

1. 括号匹配

2. 算数表达式求值

   • 中缀表达式求值

     双栈思路，算符优先法

     • 遇到数字，直接入数栈

     • 遇到符号

       • 如果是括号，左括号直接入栈，右括号进行运算直到遇到左括号
       • 如果是算符，在入算符栈之前，需要进行运算操作直到算符栈顶元素等级小于当前算符等级

   • 中缀表达式转后缀表达式

     算符栈即可

     后缀先遇到就直接计算的运算符 $\to$ 中缀表达式需要先算的运算符，于是转化思路就是：

     • 遇到数字，直接构造后缀表达式
     • 遇到算符
       • 如果是括号，左括号直接入栈，右括号进行后缀表达式构造直到遇到左括号
       • 如果是算符，在入算符栈之前，需要进行后缀表达式构造操作直到算符栈顶元素等级小于当前算符等级

   • 后缀表达式求值

     数栈即可

     遇到数字直接入数栈，遇到算符直接进行运算

3. 栈与递归

   递归工作栈

3.2 队列

3.2.1 队列的基本概念

先进先出

3.2.2 队列的存储结构

顺序存储

链式存储

3.2.3 队列的操作算法

1. 循环队列的操作

   循环队列的三个注意点

   • 解决假溢出：采用循环队列，即在入队的时候不是单纯的指针 +1，而是+1后 % MaxSize
   • 解决队空队满的冲突（真溢出）：
     1. 浪费一个元素空间：测试rear+1是否==head，
     2. 设置一个辅助标志变量
     3. 设置一个计数器

   1. 初始化：头尾全部初始化为0
   2. 入队push
   3. 出队pop
   4. 取队头front
   5. 长度size
   6. 队空empty

2. 链队列的操作

3.2.4 队列的应用

1. 报数问题：报到 0 的出队，报到 1 的重新入队，求解出队顺序

2. 迷宫最短路问题：开一个记忆数组 $d[i][j]$ 表示从起点 $(0,0)$ 到终点 $(i,j)$ 点的最短路径的长度。可以将求最短路看做一个波心扩散的物理场景，队列中的每一个点都可以作为一个波心，从而实现“两点之间线段最短”的物理场景

   • 为什么用队列：逐层搜索，每次搜素到的点就是当前点可以搜索到的最短的点，先搜到的点先扩展，于是就是队列的数据结构
   • 为什么最短：对于每一个点探索到的点都是最短的点，最终的搜索出来的路径就是最短的路径

四、串

4.1 串的基本概念

由字符组成的串：子串、主串、位置

4.2 串的存储结构

4.2.1 串的顺序存储

使用固定长度的数组来存储，3种存储字符串长度的方法如下：

4.2.2 串的链式存储

$$\text{存储密度} = \frac {\text{串值所占的内存}}{\text{一个结点的总内存}}$$

非压缩形式：一个结点存一个字符

// 存储密度为：1/9 （64位操作系统）
struct String {
    char data;
    String* next;
};

压缩形式（块链）：一个结点存储指定长度的字符

// 存储密度为：4/12 （64位操作系统）
const int MaxSize = 4;
struct String {
    char data[MaxSize];
    String* next;
}

4.3 串的操作算法

4.3.1 串的基本操作算法

串连接、串比较、串拷贝

4.3.2 串的模式匹配

BF算法（Brute - Force）

// 返回匹配上的所有位置下标（下标从0开始）
vector<int> BF(string& s, string& t) {
	vector<int> res;
	int i = 0, j = 0, n = s.size(), m = t.size();
    
	while (i < n && j < m) {
		if (s[i] == t[j]) i++, j++;
		else i = i - j + 1, j = 0;
            
		if (j == m) {
			res.emplace_back(i - j);
			j = 0;
		}
	}

    return res;
}

KMP算法

优化思想：

先看暴力思想，我们需要每次将模式串 t 后移一位重新进行比较，其中浪费了已匹配的串数据，优化就是从这块已匹配的串数据入手。而已匹配的串数据就是模式串本身的串数据，因为我们可以直接从模式串本身入手。

初步猜想：

根据模式串的性质，构造一个数表 next，存储模式串应该后移的指针数 k

算法实现：

1. 递推求 next 数组
2. KMP 中 i 指针不回溯，j 回溯到 next[j]

// 求 next 数组	下标从1开始
for (int i = 2, j = 0; i <= m; i++) {
    while (j && t[i] != t[j + 1])
        // 未匹配上则不断回溯
        j = ne[j];
    
    if (t[i] == t[j + 1])
        // 匹配上了则j指针后移一位
        j++;
    
    ne[i] = j;
}

// KMP 匹配		 下标从1开始
for (int i = 1, j = 0; i <= n; i++) {
    while (j && news[i] != newt[j + 1])
        // 未匹配上则不断回溯
        j = ne[j];
    
    if (news[i] == newt[j + 1])
        // 匹配上了则j指针后移一位
        j++;

    if (j == m) {
        // 匹配完全，则统计并且回溯
        cnt++;
        j = ne[j];
    }
}

五、数组和特殊矩阵

5.1 数组

5.1.1 数组的基本概念

typedef int arr[m][n];
// 等价于
typedef int arr1[n];
typedef arr1 arr2[m];

5.1.2 数组的存储结构

1. 行优先：按行存储
2. 列优先：按列存储

可以按照下标的关系，只需要知道第一个元素的地址，通过矩阵的大小关系即可直接计算出 $a_{ij\cdots}$ 的地址

5.2 特殊矩阵的压缩存储

对于多个相同的非零元素只分配一个存储空间，对零元素不分配空间

5.2.1 对称矩阵的压缩存储

假设现在有一个 n*n 的对称矩阵

存：行优先存储 data[n * (n + 1) / 2]

取：我们如果要取 data[i][j]

• 对于上三角

  • i >= j：data[i * (i + 1) / 2 + j]

  • i < j：data[j * (j + 1) / 2 + i]

• 对于下三角

  • i >= j：data[i * (i + 1) / 2 + j]

  • i < j：data[j * (j + 1) / 2 + i]

5.2.2 三角矩阵的压缩存储

假设现在有一个 n*n 的三角矩阵（上三角或下三角为常数c）

存：行优先存储，常数 c 存储到最后 data[n * (n + 1) / 2 + 1]

5.2.3 对角矩阵的压缩存储

假设现在有一个 n*n 的对角矩阵（围绕主对角线有数据，其余数据均为0）

5.2.4 稀疏矩阵的压缩存储

假设现在有一个 n*m 的稀疏矩阵（很多零的一个矩阵）

1. 三元组顺序表

   按行存储两个信息，一个是非零元素的数值，还有一个是具体的坐标 (i, j)

2. 十字链表

   定义两个指针数组，定义两个指针数组，存储行列的头指针即可 vector<CrossNode<T>*> cheads, rheads

六、广义表

6.1 广义表的概念

与以往的线性表的区别在于：线性表的元素只能是 DT 或 ADT。而对于广义表，元素还可以是一个广义表，即可递归结构。

表头、表尾。对于当前序列，第一个元素就是表头，其余元素的集合就是表尾

特点：层次结构、共享结构、递归结构

6.2 广义表的存储结构

6.2.1 广义表中结点的结构

采用联合结构体存储结点类型

6.2.2 广义表的存储结构

6.3 广义表的操作算法

• 直接递归法 - 原子直接操作，子表循环成原子进行操作
• 减治法 - 先处理第一个元素（原子：直接操作 $or$ 子表：递归操作），最后递归操作剩余的元素

6.3.3 广义表的其他操作算法

复制广义表、计算广义表的长度、计算广义表的深度、释放广义表的存储空间

七、树和二叉树

7.1 树的概念和性质

7.1.1 树的定义

7.1.2 树的基本术语

1. 结点的度和树的度
   • 结点的度：每一个结点孩子结点的数量
   • 树的度：一棵树中结点度数的最大值
2. 孩子、双亲、兄弟结点
3. 路径和路径长度
4. 子孙结点和祖先结点
5. 结点的层次和树的高度
6. 有序树和无序树
   • 有序树：子集不可以随意交换
   • 无序树：子集可以随意交换
7. 森林
   • 多棵树

7.1.3 树的基本性质

7.2 二叉树的概念和性质

7.2.1 二叉树的定义

7.2.2 二叉树的基本性质

1. 根是第一层。第 $i$ 层最多有 $2^{i - 1}$ 个结点

2. 树中叶子结点的个数为 $n_0$，度数为2的结点的个数为 $n_2$。已知树的点数为 $n$，边数为 $m$，则 $n = m + 1$。而 $n=n_0+n_1+n_2$，$m=n_1+2n_2$，则 $n_0+n_1+n_2 = n_1+2n_2 +1$，则

   $$n_0=n_2 + 1$$

3. 满二叉树：每一层都是满结点

   

4. 完全二叉树：对于一个 $k$ 层的二叉树，$1\to k-1$ 都是满的，第 $k$ 层从左到右连接叶子结点

   

   结点数固定，则完全二叉树的形状唯一

   

   若 $i$ 为奇数，且 $i\neq1$，则左兄弟就是 $i-1$

   若 $i$ 为偶数，则右兄弟就是 $i+1$

7.3 二叉树的存储结构

7.3.1 二叉树的顺序存储结构

• 对于一般的二叉树，将其转化为完全二叉树进行存储即可
• 插入删除操作都不方便

7.3.2 二叉树的链式存储结构

7.4 二叉树的遍历

7.4.1 二叉树遍历的概念

7.4.2 二叉树遍历算法

1. 先中后遍历
   1. 递归遍历
   2. 栈式遍历
2. 层序遍历

7.4.3 二叉树的构造和析构

1. 由含空指针标记的单个遍历序列构造二叉树

   可以从遍历的逻辑进行逆推。在遍历到空指针的时候输出一个编制符号，然后在构造的时候按照遍历序列进行递归构造即可，如图

   先序序列进行构造：按照遍历的思路来，对于先序序列而言，第一个元素一定是根元素，因此首先根据“当前局面”的第一个元素创建根结点，接着递归创建左子树和右子树即可。注意传递的序列起始下标是引用类型的变量

   

   

   中序序列进行构造：

   不可以，因为不能确定根节点以及左子树和右子树的部分

   后序序列进行构造：与上述先序序列进行构建的逻辑一致，只不过有一个小 trick，即我们从后序序列的最后一个元素开始创建，那么得到的第一个元素就是根结点的值，然后首先递归创建右子树，再递归创建左子树即可。同样需要注意的是传递参数时，序列起始下标是引用类型的变量

   与先序序列构造逻辑相同，只是递归的顺序需要调整一下

2. 由两个遍历序列构造二叉树

   • 先+中：构造逻辑与上述带标记的序列构造逻辑几乎一致，只不过区别在于如何进行递归中参数的传递。传递的参数除了先序和中序的字符串，还有当前局面先序序列的起始下标与当前局面中序序列的起始下标，以及以当前序列进行构造时子树的结点个数。很容易就可以找到当前序列的根结点，接着就是利用很简单的下标关系得到上述的三个参数的过程，最后将新得到的三个参数传递给递归函数进行递归构建左右子树即可，当前的根结点是 pre[ipre]
   • 后+中：逻辑与上述一致，只不过当前的根结点是 post[ipost+n-1]

3. 由顺序结构构造链式结构

4. 拷贝构造

5. 析构

7.5 二叉树的其他操作算法

1. 计算二叉树的结点数
   • 有返回值的递归
   • 无返回值的递归
2. 计算二叉树的高度
   • 有返回值的递归
   • 无返回值的递归
3. 根据关键值查找结点
4. 查找结点的父结点

7.6 线索二叉树

7.6.1 线索二叉树的概念

将空指针域用前驱 or 后继结点的地址进行覆盖

7.6.2 线索二叉树的存储结构

依旧是链式存储，只不过增加了结点域中的指针类型，分为链接类型Link与线索类型Thread

7.6.3 线索二叉树的操作算法

以中序线索化的二叉树为例，涉及到以下几种算法：

1. 线索化：设置一个全局变量 pre，为了简化思维，我们可以将一个中序遍历的过程想象成一个线性结构。前驱为 pre，当前为 p

   • p 的左子树为空，则 p 的前驱为 pre
   • pre 的右子树为空，则 pre 的后继为 p

2. 求后继结点和前驱结点

3. 遍历

4. 求父结点

   • 首先，若已知当前是左子树，则父结点一定是当前右孩子的中序前驱线索；若已知当前是右子树，则父结点一定是当前左孩子的中序前驱线索
   • 但是在未知当前结点的位置（未知左右子树）时，同时搜索两边的父结点，然后根据试探出来的父结点，特判父结点的子结点是否是当前结点即可

7.7 树的存储结构与算法

7.7.1 树的存储结构

1. 多叉链表表示法：将每一个结点的子结点都预设置为一个定值（树的最大度数）：浪费空间

2. 孩子链表表示法：自顶向下存储边的信息

   template<class T>
      struct CTBox {
          T data;
          CTNode* firstchild;
      };
      struct CTNode {
          int child;
          CTNode* next;
      };

   

3. 双亲表示法：自下向上存储边的信息

   

4. 孩子兄弟表示法：左结点存储孩子，右结点存储兄弟

7.7.2 树的操作算法

构造、计算树的高度、计算树中所有结点的度

7.8 哈夫曼树与哈夫曼编码

7.8.1 哈夫曼树的定义

树的路径长度：叶子结点到根结点的路径之和

1. 树的带权路径长度 $WPL$ ：叶子结点到根结点的路径之和 $\times$ 叶子结点的权重，整体之和
2. $WPL$ 最小的树就叫做哈夫曼树：对于一个结点序列n，每次选择其中的两个权值最小的两个结点进行合并，在进行了n-1次以后，得到的二叉树就是哈夫曼树
3. 哈夫曼编码：
   • 编码：利用二叉树进行前缀编码 - 避免解码时的二义性
   • 解码：根据编码的二叉 trie 树，进行解码

7.8.2 操作算法

构造 Huffman 树、编码、解码

八、图

8.1 图的基本概念

8.1.1 图的定义

$$Graph = (V,E)$$

完全无向图：$edge=n(n-1)/2$

完全有向图：$edge=n(n-1)$

8.1.2 图的基本术语

• 带权图称为网

• 无向图：连通图和连通分量

  • 连通图：每一个顶点之间都有路径可达
  • 连通分量：极大连通子图

• 有向图：强连通图和强连通分量

  • 强连通图：每一个顶点之间都有路径可达

• 强连通分量：极大强连通子图

8.2 图的存储结构

教材中的点编号统一从 $0$ 开始

8.2.1 邻接矩阵

无向图的度：第 $i$ 行（列）的非标记数的个数

有向图的度：入度为第 $i$ 行的非标记数的个数；出度为第 $i$ 列的非标记数的个数

类定义：

8.2.2 邻接表

存储出边表称为邻接表，存储入编表称为逆邻接表

类定义：

8.3 图的遍历

8.3.1 图遍历的概念

每个结点只能访问一次，故需要开启标记数组用来记录是否访问的情况

8.3.2 深度优先搜索

邻接矩阵：

• 时间复杂度：$O(n^2)$

• 针对邻接矩阵的一个无向连通图的搜索代码示例

  

邻接表：

• 时间复杂度：$O(n+e)$

• 针对邻接表的一个无向连通图的搜索代码示例

  template<class T>
  void ALGraph::DFS(int v, bool* visited) {
      cout << vexs[v];
      visited[v] = true;
      // 遍历所有的边
  }

8.3.3 广度优先搜索

通过队列实现、时间复杂度与上述 DFS 算法类似

8.3.4 图遍历算法的应用

1. 求 (u,v) 的所有简单路径：dfs + 回溯法的简单应用

2. 染色法求二部图：bfs 的简单应用。当然 dfs 也是可以的，只需要在染色之后判断是否有相同颜色的邻接点即可

8.4 最小生成树

8.4.1 最小生成树的概念及其性质

$Minimum\ Spanning\ Tree(MST)$

证明：

对于上述的一个割，选择其中权值最小的交叉边。从而对于所有的状态，每次选择最小交叉边即可。

8.4.2 Prim算法

算法标签：$greedy$

• 构造 $n-1$ 个割的状态

• 起始状态为：顶点集合 $U$ 含 $1$ 个顶点，顶点集合 $V-U$ 含 $n-1$ 个顶点

• 状态转移为：

  • 选完最小交叉边之后，将这条边在集合 $V-U$ 中的顶点加入到最小生成树集合 $U$ 中
  • 更新最小交叉边数组 $miniedges[\ ]$

• 时间复杂度：$O(n^2)$

8.4.3 Kruskal算法

算法流标签：$greedy,dsu$

• 初始化 $n$ 个顶点作为 $n$ 个连通分量
• 按照边的权值升序进行选择
  • 如果选出的边的两个顶点不在同一个集合，则加入最小生成树
  • 如果选出的边的两个顶点在同一个集合，则不选择（如果选了就会使得生成树形成回路）
• 时间复杂度：$O(e\log e)$

8.5 最短路径

8.5.1 最短路径的概念

单源最短路

$Dijkstra$ 算法无法求解含负边权的单源最短路

$Bellman-Ford$ 算法支持负边权的单源最短路求解

$Spfa$ 算法同样支持负边权的单元最短路，属于 $Bellman-Ford$ 算法的优化

多源最短路

$Floyd$ 适用于求解含负边权的多源最短路

8.5.2 单源最短路径 - $Dijkstra$ 算法

算法标签：$greedy$ $dp$

其实就是 $Prim$ 的另一种应用

• $Prim$ 是只存储交叉边的最小值
• $Dijkstra$ 是存储交叉边的最小值 $+$ 这条边在集合 S 中的点已经记录的值

1. 朴素版：

   • 邻接矩阵

   • 定义 $d[i]$ 表示从起点到当前i号点的最短路径的长度

   • 将顶点分为两个集合，$S$ 和 $V-S$，其中 $S$ 表示已经更新了最短路径长度的顶点集合

   • 迭代更新过程：依次更新每一个结点，对于当前结点 $v_i$，在集合 $S$ 中的所有结点中，选择其中到当前结点路径最短的顶点 $v_j$，则 d[i]=d[j]+edges[j][i]

   • 时间复杂度：$O(n^2)$

2. 堆优化：

   • 邻接表

   • 时间复杂度：$O(e \log e)$

8.5.3 多源最短路径 - $Floyd$ 算法

算法标签：$dp$

多阶段决策共 $n$ 个阶段，dp[i][j] 表示每一个阶段 $k$，从 $i$ 到 $j$ 的选择前 $k$ 个顶点后的最短路径的长度

对于当前阶段 $k$，我们利用阶段 $k-1$ 的状态进行转移更新，其实就是对于新增加的顶点 $v_k$ 是否选择的过程

• 选择 $v_k$，则 dp[i][j] = dp[i][k] + dp[k][j]
• 不选 $v_k$，则 dp[i][j] 就是 $k-1$ 状态下的 dp[i][j]

8.6 AOV网与拓扑排序

8.6.1 有向无环图与AOV网的概念

• 有向无环图：$DAG$
• AOV网： $(activity\ on\ vertex\ network)$
• 应用场景：在时间先后上有约束关系的工程管理问题

8.6.2 拓扑排序

• 定义：顶点线性化
• 应用：判环、判断一个图是否可以进行动态规划
• 算法设计：对于有向图，从所有的入度为 0 的点开始删点删边，到最后判断有多少点被删除即可
• 算法实现：可以采用 dfs 进行缩点删边，也可以采用 bfs 进行缩点删边
• 时间复杂度：$O(n+e)$

九、查找

9.1 静态查找表

定义：只支持查询和修改，不支持删除与插入

9.1.1 顺序查找

9.1.2 折半查找

9.1.3 分块查找

结合顺序查找与分块查找的一种方法

• 索引表可以折半或者顺序查找
• 块内部只能顺序查找

9.2 动态查找表

9.2.1 二叉排序树

定义：根结点比左子树所有结点的值都大，比右子树所有结点的值都小。关键字唯一

操作：查找、插入、删除

判定：想要判定一棵二叉树是否为二叉排序树，只需要判断中序遍历的结果是不是递增的即可，可以采取中序遍历序列比对的方法，也可以在递归遍历二叉树的过程中通过记录前驱结点的值直接进行比较判断。时间复杂度：$O(n)$

9.2.2 平衡二叉树

定义：平衡因子为左子树的高度 - 右子树的高度，平衡二叉树的平衡因子绝对值 <= 1

构建：当插入结点进行构建时出现了有结点平衡因子的绝对值超过了1，则进行“旋转”调整，旋转共分为4种

尝试模拟一遍下列序列的构造过程就可以理解了

9.3 Hash 查找

定义：装填因子 $\alpha=\frac{n}{m}$，其中 $n$ 表示待填入表中的结点数，$m$ 表示哈希表的空间大小

哈希函数应该满足以下两点：第一、映射出来的地址不会越界；第二、映射出来的地址是唯一的

9.3.1 构造表

常用的哈希函数

1. 直接地址法 - 线性函数一对一映射

   优点。计算简单且不可能产生冲突

   缺点。对于空间的要求极高，如果数据过于离散，则会造成很大的空间浪费

2. 数字分析法 - 按照数位中的数值分布情况进行哈希

   缺点。需要预先知道数据的数字分布情况

3. 平方取中法 - 对于 $10^m$ 的哈希空间，可以将数字平方后取中间 $m$ 位进行哈希存储

4. 折叠法

   • 移位法：将一个数字按照数位拆分为几个部分，然后将几个部分的数值累加出一个数即可，高位抹去不用

   • 间隔法：与移位法几乎一致，只不过将其中的部分意义间隔的进行数值反转，最后累计即可，高位抹去不用

5. 除留余数法 - 按照数值 $\text{mod}\ p$ 后的数值进行哈希，假设哈希表空间大小为 $m$ ，则 $p$ 一般取 $\le m$ 的质数

处理冲突

1. 开放定址法 - 探测开放地址，一般有三种
   • 连续序列进行线性探测
   • 左右倍增序列进行探测
   • 伪随机序列进行探测
   • 双 hash 探测法
2. 拉链法
   • 定义：将产生 hash 冲突的元素放入同一个子集，通过单链表进行存储
   • 优点：没有堆积现象，从而减少了很多不必要的比价，提升比较效率；适合一开始不知道表长的情况；除结点更加容易。

9.3.2 查找表

按照构造相同的逻辑进行查找即可

十、排序

10.1 排序的基本概念

关键字：

• 主关键字：每一个待排序的该关键字是独一无二的
• 次关键字：每一个待排序的该关键字可能是重复的

稳定性：

• 场景：只针对次关键字的情况
• 稳定：按照次关键字排序后，原来相同关键字的顺序不变
• 不稳定：按照次关键字排序后，原来相同关键字的顺序可能会改变

内外排序：

• 内排序：数据全部存放在内存
• 外排序：数据量过大时，待排序的数据在内存与外存之间不断转换

10.2 冒泡排序

稳定的。基于交换的思路进行

10.3 选择排序

• 选择第 1 小的数放在第一个位置，…，选择第 i 小的数放在第 i 个位置

• 共选择 n-1 次

10.4 插入排序

稳定的。

• 直接插入排序：依次向前缀已经排好序的序列中进行插入 - $O(n^2)$
• 折半插入排序：同上，只是选择插入位置的使用二分 - $O(n\log n)$
• 递归插入排序：排序 [1,i] 等价于先排好 [1,i-1]，然后插入当前 num[i] 即可

10.5 希尔排序

不稳定。

基于插入直接排序的优点：

1. 当序列基本有序时，效率很高
2. 当待排序数很少时，效率很高

于是希尔（Shell）就得出来以下的希尔排序算法：

1. 将序列划分一定次数，从 d<n 到 1
2. 每次划分都对组内的元素进行直接插入排序
3. 最后分为 1 组时，直接排序一趟以后就可以得到 sortrd sequence

10.6 快速排序

不稳定。

分治法三步骤：divide、conquer and combine

每次选择一个 pivot 进行 partition，递归两个 partition

void Sort(int l, int r) {
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);            
    }
    
    Sort(l, j), Sort(j + 1, r);
}

10.7 堆排序

不稳定。

堆与堆排序的定义：首先我们得知道什么是堆结构。堆是具有下面性质（对于任意的 $1\le i \le n/2$ ）的完全二叉树

• $k_i \le k_{2i},k_i \le k_{2i+1}$ 叫做 小顶堆
• $k_i \ge k_{2i},k_i \ge k_{2i+1}$ 叫做 大顶堆
• 因此一个堆结构可以采用线性的单元进行存储与维护。而堆排序利用堆顶是最值这一性质，通过不断的取堆顶，调整堆的方式获得最终的排好序的序列

建立初始堆：由于完全二叉树中，每一个叶子结点都已经是堆结构，因此直接从第一个非叶子结点开始建堆即可。对每一个元素与左孩子、 右孩子进行比较

• 如果当前结点的值比左右孩子都大，那么无需修改，当前位置就是堆顶
• 如果当前结点的值比左孩子或者右孩子中的最大值小，则将最大的孩子作为堆顶，并将当前值不断的“下沉”即可

交换堆顶与记录位置后重新建堆：交换记录值获取当前堆中最值以后，需要将除了已记录的值的结点以外的所有结点重新调整为堆结构

• 调整为堆结构的过程与上述初始建堆的过程完全一致，只是结点数每次 -1

时间复杂度：$O(n \log n)$

10.8 归并排序

稳定的。

递归：同样采用分治法，我们按照分治法的三个步骤进行讨论

• divide：将当前序列划分为左右两部分
• conquer：递归处理上述划分出来的两部分
• combine：归并上述递归完的两部分

非递归：就是模拟上述递归的过程，可以拆分为三步

• 归并
• 按照指定的长度处理整个序列
• 划分局部排序的长度

时间复杂度：$O(n \log n)\leftarrow T(n)=2T(\frac{n}{2}) + O(n)$