前言#

这篇笔记是我根据自己比较薄弱的内容，加上做往年卷子时遇到的一些易错点整理出来的复习资料。涵盖时间复杂度、线性表、栈与队列、串、递归、树与二叉树、图、查找和内排序等核心考点，不一定适合所有人，读者请批判性使用。

数据结构概述#

基础知识#

时间复杂度分析（大O）#

分析方法#

1. 对于顺序执行（顺序结构或无循环的选择结构）的代码，其复杂度为。
2. 对于循环次数与输入规模无关的单层循环，其复杂度也为。
3. 对于循环次数与输入规模有关的单层循环，其复杂度取决于步长，方法为：写出第k次迭代时循环变量index的通项公式，然后解不等式index <= n，解出的k就是时间复杂度。
4. 对于多层循环，若互不依赖，时间复杂度为，例如内层，外层，总时间复杂度；若相互依赖，则退回到内层每轮操作数求和。
5. 对于分治类（即平均划分子问题的递归类），使用主定理求解：
   • 令分裂子问题个数为，，，比较与的大小：
   • 上步中的“比较”是增长快慢的比较（即比较和），不是绝对的数值比较。
6. 对于非分治类递归算法（递归树不平衡，无法找到恒定的），则直接使用递归树求解：

• 若树不平衡，但每层总成本恒定，直接取最深递归树深度，
• 若树不平衡，每层总成本递减，可认为，无穷级数求和。
• 若树不平衡，递归划分非常复杂，考虑求有限项，归纳得解。

分析示例#

def func(n):
    count = 0
    for i in range(n):
        j = n
        while j > 0:
            count += 1
            j = j // 2
    return count

循环次数与有关，外层循环次，步长不变，内层步长倍增，

def func(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    # 递归调用：2个子问题，每个规模 n/2
    left_max = find_max(arr, left, mid)      # T(n/2)
    right_max = find_max(arr, mid + 1, right) # T(n/2)

    # 合并：只做一次比较，耗时 O(1)（这里就是 f(n)）
    return max(left_max, right_max)

递归类，平衡，，算出，故

def func(arr, left, right):
    if left >= right:
        return 0
    # 不等比划分：1/3 和 2/3
    mid1 = left + (right - left) // 3
    mid2 = right - (right - left) // 3

    # 递归调用：两个子问题规模不同
    res1 = uneven_divide(arr, left, mid1)
    res2 = uneven_divide(arr, mid2, right)

    # 假设合并时要遍历整个数组：O(n)
    total = 0
    for i in range(left, right + 1):
        total += arr[i]
    return res1 + res2 + total

递归类，不平衡，每层总规模为，总成本为，最高层高为，

常见算法#

排序#

查找#

图论算法#

一些数据结构的CRUD#

• 哈希表的随机访问是O(1)
• 二叉搜索树的平均时间复杂度是O(log n)，最坏情况退化成数组，O(n)
• 链表、数组、栈的性质不言自明，不多赘述

例题#

线性表#

基础知识#

线性表的三个特点为：

• 有穷性：线性表中元素总数有限
• 一致性：所有元素性质相同（实现角度：所有元素数据类型相同）
• 序列性：所有元素的相对位置是线性的，每个元素仅有一个前驱/后继，允许出现不同位置的相同元素。

衡量链表种类有以下几个维度：

• 头结点/尾结点：头结点/尾结点不存储数据，目的是让链表无须判空，简化处理逻辑。
• 单向/双向：单向链表每个元素只有next指针，可以指向后继元素，只能单向遍历，双向链表每个元素同时有prev和next两个指针，可以双向遍历
• 循环：将非循环链表的尾元素的next指向头元素即可。

常见算法#

• 链表的CRUD，其中插入有头插法和尾插法两种

例题#

栈和队列#

基础知识#

• 栈：FILO，先进后出，常用于深度优先搜索和递归的模拟（递归本质使用了编程语言的运行时栈）。栈可以使用数组+顶指针模拟。
• 单调栈：新元素准备入栈时从栈顶不断弹出不满足条件的元素，结束后将新元素入栈。（例如维护递增单调栈时弹出所有大于新元素的元素）
• 队列：FIFO，先进先出，常用于广度优先搜索，队列可以使用数组+首尾指针模拟
• 循环队列：通过让index > 数组长度n 的元素回绕到初始位置（例如做对n的取模），重复利用出队后在队头区域留下的空间，提高存储效率。

常见算法#

调度场算法#

中缀表达式转后缀表达式的经典算法，维护操作数和操作符（可视为单调栈）两个栈，对表达式串从前往后扫描，遇操作数直接放入操作数栈，遇操作符先暂存入操作符栈，当遇到同级或更高级操作符入栈（或右括号）再弹栈。

int evaluate(string s) {
	for (int i = 0; i < s.size(); i++) {
		char c = s[i];

		// 1. 数字：直接入栈（假设是单个数字）
		if (isdigit(c)) {
			num.push(c - '0');
		}

		// 2. 左括号：直接入栈
		else if (c == '(') {
			op.push(c);
		}

		// 3. 右括号：一直计算到左括号
		else if (c == ')') {
			while (!op.empty() && op.top() != '(') {
				calc();
			}
			op.pop(); // 弹出 '('
		}

		// 4. 运算符
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			while (!op.empty() && priority(op.top()) >= priority(c)) {
				calc();
			}
			op.push(c);
		}
	}

	// 5. 收尾计算
	while (!op.empty()) {
		calc();
	}

	return num.top();
}

深度优先搜索的栈版本#

该算法会在查找一节中提及，这里只做示范：

void DFS(int start) {
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (vis[u]) continue;
        vis[u] = true;

        // 访问结点
        cout << u << " ";

        // 将邻接点压栈（逆序/任意顺序都可以）
        for (int v : G[u]) {
            if (!vis[v]) {
                st.push(v);
            }
        }
    }
}

广度优先搜索的队列版本#

同上，放一个我写的层序遍历建树算法做示例：

Node *build_tree(int nums[], int n) {
  if (n == 0) return NULL;

  Node *queue[MAX_NODES];
  int front = 0, rear = 0;

  Node *root = new_node(nums[0]);
  queue[rear++] = root;

  int idx = 1;
  while (idx < n && front < rear) {
    Node *cur = queue[front++];

    // 左子结点
    if (idx < n) {
      if (nums[idx] != NaN) {
        cur->l_child = new_node(nums[idx]);
        queue[rear++] = cur->l_child;
      }
      idx++;
    }

    // 右子结点
    if (idx < n) {
      if (nums[idx] != NaN) {
        cur->r_child = new_node(nums[idx]);
        queue[rear++] = cur->r_child;
      }
      idx++;
    }
  }
  return root;
}

例题#

串#

基础知识#

• 串可存储为顺序串和链串

常见算法#

BF & KMP#

Bruteforce算法，纯暴力，将查找串的每个字符和模式串的每个字符比较，一旦有不匹配字符则重新比较。

KMP通过next[]数组“复用了已有匹配成果”，next[]数组中每一项表示“当不匹配时要跳到何处继续匹配”，将“后缀BA与当前位置匹配”变成“前缀BA与当前位置匹配”，避免主串指针回溯。

def build_pi(p):
    pi = [0] * len(p)
    j = 0

    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]

        if p[i] == p[j]:
            j += 1
            pi[i] = j

    return pi

def kmp(s, p):
    pi = build_pi(p)
    j = 0

    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = pi[j - 1]

        if s[i] == p[j]:
            j += 1

        if j == len(p):
            return i - j + 1  # 匹配起点

    return -1

例题#

递归#

基础知识#

• 直接调用自身称为直接递归，调用外部函数，外部函数调用自身称为间接递归。
• 递归思路是将大问题化为小问题解决
• 一次递归就是一次函数调用栈，会在操作系统提供的运行时栈上开辟一个新的栈帧，因此递归太深可能会爆栈。
• 递归到非递归的转换分为直接转换和间接转换，直接转换使用迭代（循环）代替递归，间接转换需要通过栈模拟递归结构。

常见算法#

深搜和广搜都是递归算法，二分查找，归并排序等也是经典的递归算法，图、树的遍历也都可以使用递归进行。

例题#

树和二叉树#

基础知识#

树的相关概念#

• 一个结点的度指的是该结点的子树的个数，可视为从该结点指出的箭头个数。
• 树的度是其所有结点度的最大值。度为m的树称为m次树。
• 叶子结点没有子树
• 二叉树和二次树的区别：
  1. 二次树必须有度为2的结点，二叉树不需要（二叉树甚至可以退化成一个链表）
  2. 二叉树严格区分左右子树，二次树无此要求。
• 满（Full）二叉树：每一层结点数达到最大，结点数为
• 完全（Complete）二叉树：仅允许缺口为右下角的小块区域，其他部分必须填满。
• 树的遍历分为：先根遍历、后根遍历，层序遍历（环形队列），对于二叉树，还有中序遍历。
• 所有树均可以通过孩子-兄弟表示法转化为二叉树，反之亦然。

树的相关公式#

几种二叉树#

线索二叉树#

通过二叉树遍历建立prev/next索引，将二叉树转化为链表，后续使用无须再遍历，避免重复递归消耗。

哈夫曼树#

个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树称为哈夫曼树。若令叶子结点到根结点的路径长度，权重，则定义，表示带权路径长度。

哈夫曼树的构造见常见算法。

并查集#

“并”即将两个二叉树合并，“查”即找两个元素的根，看是否相同。可通过parent[]数组进行路径压缩。

二叉搜索树#

二叉搜索树（Binary Search Tree, BST）满足以下性质：

• 对于任意结点，如果其左子树非空，则左子树所有结点的值均 小于 该结点的值；
• 对于任意结点，如果其右子树非空，则右子树所有结点的值均 大于 该结点的值；
• 任意结点的左右子树也都分别是二叉搜索树（递归定义）。

二叉搜索树的插入：从根开始，比较与当前结点的大小关系，决定往左/右子树插入，当“当前结点”为空时代表找到插入点，进行插入。

二叉搜索树的删除则复杂一些，当删除叶子结点，执行一次搜索并删除，删除仅一个子结点的结点时用子结点替代自己。删除有两个子结点的结点时，用左子树最大值或右子树最小值替换。（即左子树最右元素或右子树最左元素）。一般采用前一种做法。

平衡二叉树（AVL）#

定义一个结点左右子树高度差为平衡系数，即 。

平衡二叉树要求：一棵平衡二叉树及其所有子树（也为平衡二叉树）有。

插入元素，删除元素均与二叉搜索树一致，先执行一次搜索，再分情况操作。

除此之外，平衡二叉树有一个“恢复平衡”的操作。通过左旋 & 右旋进行平衡恢复。

例如，对于LL型，根结点进行一次右旋：

对于LR型，将根的左子树左旋可以转为LL型，再重复上述方法即可处理：

对于RL型和RR型，处理方法类似，不做赘述。

B- 树 & B+ 树#

B树的B不是二叉的意思，而是平衡的意思。B树是一种所有结点平衡因子均为0的多路平衡搜索树。

一棵阶B树要么是空树，要么满足以下条件：

• 除根结点外，每个非叶子结点至多有个孩子结点(该结点本身存储了个关键字，关键字之间的空隙为孩子结点的范围)，至少有个孩子结点。

  

• 每个结点至多有个孩子结点（包括叶子结点和根结点）。

• 根结点至少有两个孩子结点。

• 子结点存储的数据区间为插空存储，即从小到大形如：[[子1],p1,[子2],p2,...,p_n,[子n+1]]

• 所有外部结点处于同一层

B-树的CRUD#

B树的查找与二叉搜索树一致，落入外部结点时为查找失败。

B树的插入与二叉搜索树基本一致，先找到插入点（叶子结点层的某个结点），如果其关键字个数为，没有空位置，进行分裂：将第中位数个关键字上提为父结点（没有父结点则新建，有则在父结点关键字中新增一条）。如图所示：

B树的删除有两种特殊情况，一个是删除后不满足Min需求，可以考虑从兄弟结点借：

另一种是从兄弟结点借后兄弟结点不满足需求，即不能借，此时合并两兄弟结点（可看作将父结点某个关键字下提）：

B+树#

B+树放弃了存关键字，只存索引，所有值存在叶子结点，同时叶子结点层通过链表串联：

B+树的插入和删除都仅在叶结点上进行，方法与B-树类似。

堆#

堆是一种特殊的二叉树，其左右子树中所有元素均小于/大于堆顶元素（即二叉树根），其左右子树也是堆（递归定义） ，分为最大堆（大根堆）和最小堆（小根堆）。一般实践中使用数组存储。堆有上滤和下滤两种操作。

堆的上滤和下滤#

以最大堆为例：

• 上滤一个元素时，将其插入到数组末尾，不断比较其和父元素（第n/2个元素），其比父元素大时则交换位置。
• 下滤一个元素时，不断找其左右子元素中的较大值，如果当前值小于该较大值，则交换其与对应子元素位置。

常见算法#

哈夫曼算法#

哈夫曼算法用于构造一棵哈夫曼树，算法步骤如下：

1. 初始化：由给定的 个权值构造 棵只有一个根结点的二叉树，得到一个二叉树集合 。
2. 选取与合并：从二叉树集合 中选取根结点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值和。
3. 删除与加入：从 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 中。
4. 重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是哈夫曼树。注意，由于上述算法确保了内部节点同时有左右两个子节点，所以构造出的哈夫曼树节点个数为，没有度数为1的分支节点。

其余算法也并不复杂，都在上述内容中陈述过。

例题#

图#

基础知识#

• 有向图/无向图：结点之间存在“指向”关系的图为有向图，表现为结点用箭头连接。无向图则只表明了连接关系，不表明指向关系。表现为邻接矩阵，无向图始终有matrix[a][b]=matrix[b][a]。
• 入度/出度：指向当前元素的箭头数为其入度，指出箭头数为其出度。无向图中没有严格的入度/出度定义，可以认为入度=出度=度=当前结点连接结点数。
• 连通/非连通：往一个结点灌水，能流到的所有结点相互连通，组成一个最大连通分量，其子集为连通分量。最大连通分量覆盖所有结点的图为连通图。
• 最小生成树：遍历所有结点，不允许成环，总路径长度最小。

常见算法#

四个重量级。

Kruskal#

思路：所有边从小到大排，每次选最小边，如果两端元素不在同一个并查集中，则加入候选边集，以此类推，直到选出（n-1)条边。

Prim#

思路：存储每个结点到当前最小生成树的距离，每次遍历，找到树距离最小点，加入树，并更新其邻接树外结点到树的距离，直到所有结点在树中。

Dijkstra#

思路：设置起点到自身距离为0，其余点为∞。 每次从未访问的点中选择当前距离起点最小的点u，将其加入已确定集合（已得到最短路径），然后用u去更新它的邻接点到起点距离，直到所有点都被确定或不可再更新。

Floyd#

思路：设置dist[i][j]表示i -> j的最短距离，并枚举中间点k，当dist[i][k] + dist[k][j] < dist[i][j]，更新，直到所有点处理完毕。

拓扑排序#

要求：必须要是无环有向图，即有明确依赖结构，无循环依赖。

算法：每次找入度为0的点，选择它，并将邻接元素入度-1，重复直到排序完毕。

AOE网#

一个源点一个汇点，中间发散，用于求关键路径。例如：

最长权重的路径就是关键路径。图中为。

例题#

查找#

基础知识#

• 平均查找长度（ASL）：分为成功状况下的平均查找长度和不成功状况下的平均查找长度。理解为“比较次数的期望”。
  • 成功时，其中表示节点被查找的概率，表示查找节点 需进行的比较次数。
  • 失败时则看需要走多少步才能判错，对于顺序查找，，其他查找方式可分别分析。
• 顺序查找：for i in range(0,n): compare
• 折半查找：二分法，可用红蓝染色法理解，也可用二叉树表示查找过程，该类树称为判定树。
• 分块查找：在索引整体无序，分块后块间有序的情况下，可以分块查找。例如，对于[3,2,1,6,5,4,9,8,7]，分为三块，按块内最大值建立索引[3,6,9]，按照“先块间，再块内”缩小查找范围。分块查找性能介于二分和顺序查找之间。
• 基于树的查找已经在前文讲过了，其他查找算法比较基础，略去。

例题#

内排序#

基础知识#

• 基于比较的排序算法：插入、选择、交换、归并。
• 不基于比较的排序算法：基数排序。
• 引入序列，排序过程也可以用决策树表示。
• 使用基于比较的排序方法，最佳平均时间复杂度为。
• 排序前后相同关键字的元素相对位置发生改变的排序算法不稳定，反之稳定。

常见算法#

插入排序#

插入排序分直接插入、二分插入和希尔排序。

直接插入十分简明，略去；二分插入中“查找待排序元素在有序区的位置”使用二分查找操作，其余操作与直接插入相同。

希尔排序采用的思路是：等距分组（d=n/2）分别插入排序，依次将d折半，直到d=1（最后一趟执行了直接插入排序）。通过前面不断分组排序，让最后一趟插入排序需要移动的元素数量较少，不会有太大压力。

交换排序#

常见的交换排序算法有冒泡排序、快速排序两种。冒泡十分简明，略去。

快速排序分二路和三路，思路相近，不断进行哨兵划分，将待排序区域分为[<=pivot],[>pivot]两块（或者三块），递归排序。

选择排序#

分为简单选择排序和堆排序。简单选择排序的思路是从未排序区选出最小元素，插入有序区尾。堆排序将数组的未排序区视为堆，维护最小堆并不断将堆顶元素放到已排序区，直到堆空。

归并排序#

将一个表拆分成多块，分别递归排序，最后采用“每个表作为一个队列，取队首元素比较较小值”的方式合并为一个新表。根据拆分数n记为“n路归并”。

基数排序#

按位分桶（分最低位优先和最高位优先，最低位优先为：先排个位，再排十位…），低位优先时按桶顺序收集元素，再分桶。例如：

{123, 125(1号), 125(2号), 134, 137} -> {123, 134, 125(1号), 125(2号), 137} -> {123, 125(1号), 125(2号), 134, 137}

高位优先则递归分桶，不收集，而且我承认这块我真没搞明白，但是没关系，高位优先排序非常不常用，应该不会考的。

各算法特性#

时空复杂度#

稳定性#

希尔排序，快速排序，各种选择排序不稳定，其他稳定。

例题#