数据结构

---

时间轴

2025-09-28

add 绪论

2025-10-18

add 线性表，栈，队列，数组，串

2025-10-20

add 树，图

2025-11-09

add DSU 并查集

---

绪论

数据的逻辑结构

数据的逻辑结构是指数据元素之间的关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的

• 线性结构
  • 线性表
    • 数组
    • 栈
    • 队列
• 非线性结构
  • 集合
  • 树形结构
    • 一般树
    • 二叉树
  • 图状结构
    • 有向图
    • 无向图

数据的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构

• 顺序存储

顺序存储是指把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中；

• 链式存储

链式存储借助指示元素存储地址的指针来表示元素之间的逻辑关系；

• 索引存储

索引存储是指在存储元素信息的同时，还建立附加的索引表。索引表中的每项都称为索引项，索引项的一般形式是(关键字 key，地址 address);

• 散列存储

散列存储是根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。

算法的基本概念

• 有穷性

有穷性是指一个算法必须总在执行有穷步后结束，且每一步都在有穷时间内完成；

• 确定性

确定性是指算法中每条指令都必须有正确的含义，对于相同的输入只能得出相同的输出；

• 可行性

可行性是指算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

• 输入

输入是指一个算法有0或多个输入，这些输入取自于某个特定的对象的集合

• 输出

输出是指一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法效率的度量

时间复杂度

$$T(n) = O(f(n))$$

加法规则：

$$T(n) = T_1(n)+T_2(n)=O(f(n)) + O(g(n)) = O(max(f(n),g(n)))$$

常见的渐进时间复杂度

$$O(1) < O(log_2^n) < O(n) < O(nlog^n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

空间复杂度

$$S(n) = O(g(n))$$

线性表

定义：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

线性表一般表示为：

$$L = (a_1,a_2,a_3,...,a_i,a_{i+1}, ..., a_n)$$

线性表的顺序表示

线性表的顺序存储也称顺序表，其特点是表中元素的逻辑顺序与其物理顺序相同。线性表是一种随机存取的存储结构

C语言描述

• 静态分配

#define MAX_SIZE 50
typedef struct{
  ElemType data[MaxSize];
  int length;
}SqList;

• 动态分配

#define InitSize 100
typedef struct{
    ElemType *data;
    int capacity;
    int length;
}SeqList;

C++描述

一般使用标准库vector，也可以自定义

template <typename T>
class LinearList {
private:
    T *data;  
    int length;
    int capacity;

    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size; i++) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity = new_capacity;
    }

public:
    SeqList() : data(nullptr), size(0), capacity(0) {}

    ~SeqList() {
        delete[] data;
    }

};

Rust描述

Rust中一般用标准库的Vec，自己写要用许多unsafe API

基本操作时间复杂度

操作	最好情况	最坏情况	平均情况	备注
按位置插入	O(1)（表尾）	O(n)（表头）	O(n)	表尾插入均摊 O(1)
按位置删除	O(1)（表尾）	O(n)（表头）	O(n)	表尾删除 O(1)
按下标访问	O(1)	O(1)	O(1)	数组随机访问
查找（顺序）	O(1)	O(n)	O(n)	如果无序只能顺序查找

经典题目

对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素

一种解法：用k记录顺序表L中不等于x的元素的个数，扫描时将不等于x的元素移动到下标k的位置，并更新k值。扫描结束后修改L的长度。

void del_x(Sqlist &L, ElemType x){
    int k = 0, i;
    for(i = 0 ; i < L.length ; i++){
        if(L.data[i] != x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

线性表的链式表示

单链表

线性表的链式存储又称单链表。

C语言描述

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

这个C语言定义的效果是

部分	含义
struct Node { ... };	定义了一个结构体类型，标签名是 Node（即 struct Node）
LNode	给 struct Node 起了一个类型别名
*LinkList	给 struct Node*（即该结构体指针）起了一个别名为LinkList

C++描述

TODO

Rust描述

TODO

头结点

通常用头指针来标识一个单链表，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头节点。

• 头节点的数据域可以不设置任何信息，也可以记录表长等信息。

• 引入头节点可以带来两个优点：

  • 由于第一个数据节点的位置被放在头节点的指针域中，因此在链表上的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理
  • 无论链表是否为空，其头指针都是指向头节点的非空指针（空表中头节点的指针域为NULL）,因此空表和非空表的处理也就得到了统一。

头插法建立单链表

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

// 头插法建立单链表
LinkList LinkListInit_HeadInsert(void) {
  LinkList L;
  LNode *node;
  int x;

  L = (LNode *)malloc(sizeof(LNode));
  L->next = NULL;

  while (scanf("%d", &x) != EOF) {
    node = (LNode *)malloc(sizeof(LNode));
    node->data = x;
    node->next = L->next;
    L->next = node;
  }
  return L;
}

尾插法建立单链表

双链表

单链表中只有一个指向其后继的指针，使得单链表只能从头节点依次顺序地向后遍历。双链表节点中有两个指针prior和next，分别指向前驱节点和后继节点。

C语言描述

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

C++描述

TODO

Rust描述

TODO

循环链表

循环单链表

循环单链表和单链表的区别在于，表中的最后一个节点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环。

C语言描述

C++描述

Rust描述

循环双链表

循环双链表相比于循环单链表，其头节点的prior指针要指向尾节点

C语言描述

C++描述

Rust描述

静态链表

静态链表借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next，与前面的链表中的指针不同的是，这里的指针是节点的相对地址（数组下标），又称游标。和顺序表相同，静态链表也要预先分配一块连续的内存地址空间。

例如：

下标	data	next
0		4
1	头结点	2
2	10	3
3	20	5
4		6
5	30	-1
6		-1

主链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=1│ data │ next │ ---> │ idx=2│  10  │ next │ ---> │ idx=3│  20  │ next │ ---> [idx=5│ 30 │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘      └──────┴──────┴──────┘

空闲链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=0│  —   │  4   │ ---> │ idx=4│  —   │  6   │ ---> [idx=6│ — │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘

C语言描述

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

C++描述

Rust描述

经典题目

检测单链表是否存在环

单链表有环是指单链表的最后一个结点的指针指向了链表中的某个节点（通常单链表的最后一个节点的指针是空的）。试编写算法判断单链表是否存在环

求两个单链表的公共节点

栈，队列和数组

栈

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

• 栈顶（Top） 线性表允许进行插入删除的那一端
• 栈底（Bottom） 固定的。不允许进行插入和删除的另外一端

栈的特性可以明显的概括为后进先出（Last In First Out，LIFO）

栈的数学性质：

n 个不同元素进栈，其可能的出栈序列个数为第 n 个 Catalan 数（卡特兰数）

公式为：

$$C_n = \frac{1}{n+1} C_{2n}^n = \frac{(2n)!}{n! (n+1)!}$$

栈的顺序存储结构

C语言描述

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
    // 栈顶指针
	int top;
}SqStack;

C++描述

TODO

Rust描述

TODO

共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

下标:   0   1   2   3   4   5   6   7   8   9
        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
Stack1→ │10 │20 │30 │   │   │   │   │   │40 │50 │ ←Stack2
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
         ↑                   ↑                   ↑
       base1                mid                base2
         ↑                                       ↑
       top1=2                               top2=8

共享栈是为了更有效地利用地址空间。当且仅当两个栈相邻时发生栈满上溢。

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点

• 便于多个栈共享存储空间和提高效率
• 不存在栈满上溢的情况

链栈通常采用单链表实现，并规定所有操作都是在表头进行。

C语言描述

这里规定链栈没有头节点

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LiStack;

C++描述

TODO

Rust描述

TODO

经典应用

括号匹配

表达式求值

递归转为栈实现

队列

队列（Queue）也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的一端进行删除。

• 队头（Front） 允许删除的一端，也称队首

• 队尾（Rear） 允许插入的一端

• 入队（EnQueue） 向队尾插入元素

• 出队（DeQueue） 队头删除元素

队列的特性可简单概括为先进先出（First In First Out，FIFO）

队列的顺序存储结构

C语言描述

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

C++描述

TODO

Rust描述

判断队空

Q.rear == Q.front==0

判断队满

由于：

• 进队操作：队不满时，先送值到队尾元素，再将队尾指针+1
• 出队操作：队不为空时，先取队头元素值，再将队头指针+1

因此不能用“Q.rear==MaxSize ”作为队列满的条件，整个问题使用循环队列来解决

循环队列

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列

• 当队首指针 Q.front == MaxSize -1后，再前进一个位置到0
• 初始化：Q.front = Q.rear = 0
• 队首指针进1：Q.front = (Q.front + 1) % MaxSize
• 队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize

• 判断队满三种方式

  • 牺牲一个单元来区分队空队满，入队时少用一个队列单元，这是较为普遍的做法，约定以”队头指针在队尾指针的下一位置作为队满的标志”

    • 队满条件 : (Q.rear + 1) % MaxSize == Q.front
    • 队空条件: (Q.front == Q.rear)
    • 队列中元素的个数: (Q.rear - Q.front + MaxSize) % MaxSize

  • 新增一个表示元素个数的数据成员size，这样队空队满的情况下都有Q.rear == Q.front

    • 队满条件 : Q.size == MaxSize
    • 队空条件: Q.size = 0
    • 队列中元素的个数: size

  • 新增tag数据成员。tag为0时表示最近执行了一次删除；tag为1时表示最近执行了一次插入

    • 队满条件 : 当tag等于0时，若因删除导致Q.front == Q.rear则队空；
    • 队空条件: 当tag等于1时，因插入导致Q.front == Q.rear则为队满；

    • 队列中元素个数

      $$\text{队列中元素个数} = \begin{cases} 0, & \text{if } (front == rear \text{ and } tag == 0) \\ MaxSize, & \text{if } (front == rear \text{ and } tag == 1) \\ (rear - front + MaxSize) \% MaxSize, & \text{otherwise} \end{cases}$$

队列的链式存储结构

通常将链式队列设计成一个带头结点的单链表。

C语言描述

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}*LinkQueue;

C++描述

TODO

Rust描述

TODO

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。将队列的两端称为前端和后端。

输入受限的双端队列

允许在一端进行插入和删除，但在另一端只允许插入。

输出受限的双端队列

允许在一端进行插入和删除，但在另一端只允许删除。

优先队列(堆)

堆就是利用完全二叉树的结构来维护的一维数组。

堆可以分为大顶堆和小顶堆。

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值。

• 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

以大顶堆为例：

大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。

用数组表示待排序序列，则最后一个非叶子结点的位置是：数组长度/2-1

比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树；交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构；

再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树；交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构；

无需交换调整的时候，则大顶堆构建完成。

#include <vector>
using std::vector;

void heapify(vector<int> &vec, int curr, int n)
{
        int left = curr * 2 + 1;
        int right = curr * 2 + 2;
        int largest = curr;

        if (left < n && vec[left] > vec[largest]) {
                largest = left;
        }

        if (right < n && vec[right] > vec[largest]) {
                largest = right;
        }

        if (largest != curr) {
                std::swap(vec[largest], vec[curr]);
                //由于交换了父节点和子节点，因此可能对子节点的子树造成影响，所以对子节点的子树进行调整。
                heapify(vec, largest, n);
        }
}

void buildMaxHeap(vector<int> &vec)
{
        int n = vec.size();
        // 最后一个节点的位置为n-1，所以父节点的位置为(n-1-1)/2。
        for (int i = (n - 2) / 2; i >= 0; i--) {
                heapify(vec, i, n);
        }
}

#include <stdio.h>

int main()
{
        vector<int> nums = { 9, 8, 2, 1, 5, 3, 0, 10, 22, 5 };
        int n = nums.size();
        buildMaxHeap(nums);

        for (int i = 0; i < n; i++) {
                // pop
                std::swap(nums[0], nums[n - i - 1]);
                heapify(nums, 0, n - i - 1); // 堆长度为 n-i-1
        }
        // 输出已排序数组
        for (int i = 0; i < n; i++)
                printf("%d ", nums[i]);
        printf("\n");
}

经典应用

层次遍历

数组与特殊矩阵

数组

大多数语言都提供了数组数据类型。

特殊矩阵的压缩

对称矩阵（Symmetric Matrix）

• 性质：矩阵 $A = [a{ij}]$ 满足 $a{ij} = a_{ji}$。
• 压缩方法：只存储矩阵的上三角或下三角部分，例如存储上三角（包括对角线）的元素。

如果矩阵是 $n \times n$，元素按行存储上三角：

$$\text{存储顺序： } a_{11}, a_{12}, \dots, a_{1n}, a_{22}, a_{23}, \dots, a_{2n}, \dots, a_{nn}$$

• 下标映射公式（存储到一维数组 B[k]）：

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

其中 $i, j$ 从 1 开始计数。

• 存储空间：$\frac{n(n+1)}{2}$ 个元素。

三角矩阵（Triangular Matrix）

• 性质：
  • 上三角矩阵：所有元素 $a_{ij} = 0$ 当 $i > j$
  • 下三角矩阵：所有元素 $a_{ij} = 0$ 当 $i < j$
• 压缩方法：只存储非零的三角部分。

上三角矩阵按行存储公式：

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

下三角矩阵按行存储公式：

$$k = \frac{i(2n-i+1)}{2} + (j-i) \quad (i \ge j)$$

• 存储空间：$\frac{n(n+1)}{2}$ 个元素。

---

三对角矩阵 / 带状矩阵（Tridiagonal / Banded Matrix）

• 性质：矩阵只有主对角线、上对角线和下对角线有非零元素，其余为 0。

$$A = \begin{bmatrix} a_1 & b_1 & 0 & \dots & 0 \\ c_1 & a_2 & b_2 & \dots & 0 \\ 0 & c_2 & a_3 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & b_{n-1} \\ 0 & 0 & 0 & c_{n-1} & a_n \end{bmatrix}$$

• 压缩方法：存三个一维数组：
  • A[1..n] 存主对角线 $a_i$
  • B[1..n-1] 存上对角线 $b_i$
  • C[1..n-1] 存下对角线 $c_i$
• 访问公式：

$$a_{i,i} = A[i], \quad a_{i,i+1} = B[i], \quad a_{i+1,i} = C[i]$$

• 存储空间：$3n - 2$ 个元素，比普通 $n^2$ 大幅节省。

稀疏矩阵

矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即$s \gg t$的矩阵称为稀疏矩阵。

若采用常规方法存储稀疏矩阵相当浪费空间，因此仅存储非零元素。但通常非零元素的分布非常没有规律，所以还要存储非零元素的行和列。

因此，将非零元素及对应的行和列构成一个三元组

$$(\text 行标, 列标, 值)$$

然后按某种规律存储这个三元组。稀疏矩阵压缩存储后失去了随机存取的特性。

稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

三元组顺序表（数组存储）

• 将稀疏矩阵中的非零元素按照行优先或列优先顺序存储为三元组 (行标, 列标, 值)。
• 常用顺序：
  • 行优先：按行从上到下、每行从左到右存储。
  • 列优先：按列从左到右、每列从上到下存储。
• 适用于矩阵非零元素不频繁修改的情况。

十字链表存储（Cross Linked List / Orthogonal List）

• 对于动态修改的稀疏矩阵较适用。
• 每个非零元素节点包含：
  • 值
  • 行标
  • 列标
  • 行指针（指向同一行的下一个非零元素）
  • 列指针（指向同一列的下一个非零元素）
• 可以实现行和列的快速遍历，适合矩阵乘法和转置等操作。

并查集

Disjoint Set Union，DSU / Union-Find

并查集是一种 动态维护若干不相交集合 的数据结构，支持两种主要操作：

操作	功能说明
find(x)	查找元素 x 所在集合的代表（根节点）
union(x, y) / join(x, y)	合并两个元素所属的集合
（可选）connected(x, y)	判断两个元素是否属于同一集合（即 find(x) == find(y)）

数据结构定义

#include <vector>
#include <algorithm>

using std::vector;

class DSU {
    public:
	vector<int> parent; // 每个节点的父节点
	vector<int> rank; // （可选）用于按秩合并或记录集合大小

	DSU(int n)
	{
		parent.resize(n);
		rank.resize(n, 0);
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	int find(int x)
	{
		// 路径压缩，使查找复杂度接近 O(1)
		if (parent[x] != x) {
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	void join(int x, int y)
	{
		// 按秩合并
		int rootX = find(x);
		int rootY = find(y);
		if (rootX == rootY) {
			return;
		}

		if (rank[rootX] < rank[rootY]) { //两个集合的秩中最大的为rootX
			std::swap(rootX, rootY);
		}

		parent[rootY] = rootX;//秩小的挂在秩大的下面

		if (rank[rootX] == rank[rootY]) { //如果两个集合秩相等，合并后的集合的秩+1
			rank[rootX]++;
		}
	}

	bool connected(int x, int y)
	{
		return find(x) == find(y);
	}
};

技巧：

技术	说明	效果
路径压缩 (Path Compression)	在 find() 时将查找路径上所有节点的父节点都指向根节点	显著降低树高，几乎摊还 O(1)
按秩合并 (Union by Rank/Size)	在 union() 时让“矮树”挂到“高树”下	保持树的平衡，进一步优化查找效率

时间复杂度

操作	均摊时间复杂度
find()	近似 O(1)
union()	近似 O(1)
connected()	近似 O(1)

严格来说，是 O(α(n))，但 α(n) ≤ 5 对任何实际规模的 n。

串

串的模式匹配

子串的定位操作通常称为串的模式匹配，它求的是子串（通常称为模式串）在主串中的位置。

朴素模式匹配算法

模式串 p 与主串 s

S: a b a b c a b c a c b a b
P: a b c a c
   ↑ 从这里开始和主串对齐

步骤1：
S: a b a b c a b c a c b a b
P: a b c a c
   a = a ✅
     b ≠ a ❌ 失配 → 模式右移一位

步骤2：
S: a b a b c a b c a c b a b
  P: a b c a c
     a ≠ b ❌ → 继续右移一位

步骤3：
S: a b a b c a b c a c b a b
    P: a b c a c
       a = a ✅
         b = b ✅
           c = a ❌ → 右移一位

步骤4：
S: a b a b c a b c a c b a b
      P: a b c a c
         b ≠ a ❌ → 右移一位

步骤5：
S: a b a b c a b c a c b a b
        P: a b c a c
           c = a ❌ → 右移一位

步骤6：
S: a b a b c a b c a c b a b
          P: a b c a c
             a = a ✅
               b = b ✅
                 c = c ✅
                   a = a ✅
                     c = c ✅ ✅ 匹配成功！

代码：

#include <stdio.h>
#include <string.h>

int naive_match(const char *s, const char *p) {
    int i=0,j=0;
    int s_len = strlen(s);
    int p_len = strlen(p);

	while(i<s_len && j<p_len){
        if(s[i]==p[j]){
            i++;
            j++;
        }else{
            i = i - j + 1;//退回去重新匹配
            j = 0;
        }
    }
    if(j == p_len){
        return i - j;
    }
    return -1; 
}

最坏情况：$O(n \cdot m)$，其中 $n$ 是主串长度，$m$ 是模式串长度。

• 例如主串 "aaaaaaab" 和模式串 "aaaab"，每次匹配失败都需要回溯多个字符。

平均情况：通常小于最坏情况，但仍然可能接近 $O(n \cdot m)$。

KMP算法

推荐讲解非常好的文章：

朴素模式匹配算法中，每次匹配失败都是将模式串（要匹配的子串）后移一位从头开始比较。

几个概念：

• 前缀：包含首字母，不包含尾字母的所有子串
• 后缀：包含尾字母，不包含首字母的所有子串
• PM(Partial Match) 部分匹配值，即下面的表格

下面以”ABCDABD”作为要匹配的子串来举例：

子串	前缀集合（不含完整串）	后缀集合（不含完整串）	最长相等前后缀长度
A	（空）	（空）	0
AB	A	B	0
ABC	A, AB	C, BC	0
ABCD	A, AB, ABC	D, CD, BCD	0
ABCDA	A, AB, ABC, ABCD	A, DA, CDA, BCDA	1（A）
ABCDAB	A, AB, ABC, ABCD, ABCDA	B, AB, DAB, CDAB, BCDAB	2 (AB)
ABCDABD	A, AB, ABC, ABCD, ABCDA, ABCDAB	D, BD, ABD, DABD, CDABD, BCDABD	0

则PM表为

编号	0	1	2	3	4	5	6
String[i]	A	B	C	D	A	B	D
PM	0	0	0	0	1	2	0

• 如果给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：

• 1. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功：

• 1. 继续往后匹配，当模式串最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符数为6个（ABCDAB），然后根据PM表可得失配字符D的上一位字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位，从PM[i] = 2 即下标为2的地方重新开始匹配

我们可以定义一个next数组：当模式串的第j个(从0开始)匹配失败时，从模式串的第next[j]个继续向后匹配。

KMP 里的 next 数组有两种写法：

PM 表 = 前缀函数 π(i)（也叫lps 数组，Longest Prefix Suffix）。

• 有些教材里 next 就等于 PM（lps）

• 有些教材里 next 是 PM 的变形

  • next[0] = -1 （表示完全重新开始匹配）

  • next[i] = PM[i-1]

#include <string.h>

void GetNext(char *p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1) {
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k]) {
			++k;
			++j;
			next[j] = k;
		} else {
			k = next[k];
		}
	}
}

int KmpSearch(char *s, char *p, int next[])
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen) {
		//如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
		if (j == -1 || s[i] == p[j]) {
			i++;
			j++;
		} else {
			//如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
			//next[j]即为j所对应的next值
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

树与二叉树

术语

graph TD
    A[A] --> B[B]
    A --> C[C]
    B --> D[D]
    B --> E[E]
    C --> F[F]
    C --> G[G]
    E --> H[H]
    E --> I[I]

    style A fill:#f9f,stroke:#333,stroke-width:2px
    style D fill:#9f9,stroke:#333
    style F fill:#9f9,stroke:#333
    style G fill:#9f9,stroke:#333
    style H fill:#9f9,stroke:#333
    style I fill:#9f9,stroke:#333

• 结点的分类

  • 根节点 (Root)

    • 树的顶端节点。

    • 示例：A 是根节点。

  • 双亲 (Parent)

    • 节点的直接上一层节点。

    • 示例：B 的父节点是 A。

  • 兄弟 (Sibling)

    • 具有同一个父节点的节点互为兄弟。

    • 示例：D 和 E 是兄弟，F 和 G 是兄弟。

  • 子节点

    • 子节点：父节点直接连接的节点。
    • 示例：D、E 是 B 的子节点。

  • 子孙

    • 节点的所有后代，包括子节点。
    • 示例：H、I 是 B 的子孙。
  • 分支节点 (Internal Node)
    • 有子节点的节点。
    • 示例：A、B、C、E 都是分支节点。
  • 叶节点 (Leaf Node)
    • 没有子节点的节点。
    • 示例：D、F、G、H、I 是叶节点。

• 结点的属性

  • 结点的深度 (Depth)

    • 从根节点到该节点的路径长度（边数）。（自顶向下）

    • 示例：A 深度 0，B 深度 1，D 深度 2。

  • 结点的高度 (Height)

    • 从该节点到最深叶节点的最长路径长度。（自底向上）

    • 示例：B 高度 2（最长路径 B→E→H 或 B→E→I）。

    • 结点的层次 (Level)

      • 层次 = 深度 + 1

      • 示例：根节点 A 层次 1，B 层次 2。

    • 度 (Degree)

      • 一个节点拥有子节点的个数。
      • 示例：B 的度是 2（D、E）。

• 树的分类

  • 度为m的树

    • 任意结点度数不大于m
    • 至少有一个结点的度数为m
    • 一定为非空树，因此至少有m+1个结点

  • m叉树

    • 任意节点度数不大于m
    • 可以是空树

  • 有序树 / 无序树 (Ordered / Unordered Tree)

    • 有序树：树中结点的各个子树从左到右是有次序的，不能互换，即子节点有固定顺序。

    • 无序树：子节点顺序不重要。

  • 森林 (Forest)

    • 多棵互不相连的树组成的集合。

    • 如果去掉根节点 A，就形成两棵树 B 树和 C 树，组成森林。

• 其他概念

  • 路径 (Path)
    • 从一个节点到另一个节点经过的节点序列。
    • 示例：A→B→E→H 是一条路径。
  • 路径长度 (Path Length)
    • 路径上边的数量。
    • 示例：A→B→E→H，路径长度 = 3。

树的性质

1. 树中的结点数等于所有结点度数之和+1
   • 证明很简单，除了根节点，其他所有节点头上都有一条边

2. 度为 $m$ 的树第 $i$ 层上至多有 $m^{i-1}$ 个结点($i \ge 1$)

3. 高度为 $h$ 的 $m$ 叉树至多有 $ \frac{m^h-1}{m-1}$ 个结点

4. 具有 $n$ 个结点的 $m$ 叉树的最小高度是 $ \lceil log_m^{(n(m-1)+1)} \rceil$

   • 证明：高度最小的情况下，尽量让每个节点都有 $m$ 个孩子那么：
   • $\frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1} $

二叉树

二叉树是有序树

术语

• 满二叉树

  graph TD
      style A fill:#f9f,stroke:#333,stroke-width:2px
      style B fill:#9cf,stroke:#333,stroke-width:1px
      style C fill:#9cf,stroke:#333,stroke-width:1px
      style D fill:#9cf,stroke:#333,stroke-width:1px
      style E fill:#9cf,stroke:#333,stroke-width:1px
      style F fill:#9cf,stroke:#333,stroke-width:1px
      style G fill:#9cf,stroke:#333,stroke-width:1px
      style H fill:#9f9,stroke:#333,stroke-width:1px
      style I fill:#9f9,stroke:#333,stroke-width:1px
      style J fill:#9f9,stroke:#333,stroke-width:1px
      style K fill:#9f9,stroke:#333,stroke-width:1px
      style L fill:#9f9,stroke:#333,stroke-width:1px
      style M fill:#9f9,stroke:#333,stroke-width:1px
      style N fill:#9f9,stroke:#333,stroke-width:1px
      style O fill:#9f9,stroke:#333,stroke-width:1px
  
      A((1)) --> B((2))
      A --> C((3))
      B --> D((4))
      B --> E((5))
      C --> F((6))
      C --> G((7))
      D --> H((8))
      D --> I((9))
      E --> J((10))
      E --> K((11))
      F --> L((12))
      F --> M((13))
      G --> N((14))
      G --> O((15))

• 高度为 $h$ ，且含有$ 2^h-1$个结点的二叉树称为满二叉树

• 满二叉树除了叶子节点外每个结点的度数为2

• 可以对满二叉树进行按层序编号, 对于节点编号为 $i$ 的结点：

  • 左孩子编号：$2i$

  • 右孩子编号：$2i+1$

  • 父节点编号：$\lfloor i/2 \rfloor$

• 完全二叉树

  graph TD
      style A fill:#f9f,stroke:#333,stroke-width:2px
      style B fill:#9cf,stroke:#333,stroke-width:1px
      style C fill:#9cf,stroke:#333,stroke-width:1px
      style D fill:#9cf,stroke:#333,stroke-width:1px
      style E fill:#9cf,stroke:#333,stroke-width:1px
      style F fill:#9cf,stroke:#333,stroke-width:1px
      style G fill:#9cf,stroke:#333,stroke-width:1px
      style H fill:#9f9,stroke:#333,stroke-width:1px
      style I fill:#9f9,stroke:#333,stroke-width:1px
      style J fill:#9f9,stroke:#333,stroke-width:1px
      style K fill:#9f9,stroke:#333,stroke-width:1px
      style L fill:#9f9,stroke:#333,stroke-width:1px
  
      A((1)) --> B((2))
      A --> C((3))
      B --> D((4))
      B --> E((5))
      C --> F((6))
      C --> G((7))
      D --> H((8))
      D --> I((9))
      E --> J((10))
      E --> K((11))
      F --> L((12))

• 高度为$h$，有$n$个结点的二叉树，当且仅当其每个结点都与高度为$h$的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树
• 若$ i \le \lfloor \frac{n}{2} \rfloor$ ，则结点 $i$ 为分支结点
• 叶节点只可能在层次最大的两层出现，对于最大层次的叶节点，都一次排列在该层最左边的位置上。
• 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子。
• 按层序编号后，一旦出现某个结点（序号为 $i$ ）为叶子结点或只有左孩子，则编号大于 $i$ 的结点均为叶结点
• 若 $n$ 为奇数，则每个分支节点都右左孩子和右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $\frac{n}{2}$ ）只有左孩子，没有右孩子 其余结点左右孩子都有
• 一棵完全二叉树的两棵子树（根节点的左子树和右子树），至少有一棵是满二叉树

• 二叉排序树
  • 左子树上所有结点的关键字均小于根节点的关键字，右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又都是一棵二叉排序树。
• 平衡二叉树
  • 树上任意一个结点的左子树和右子树的深度之差不超过1

性质

1. 非空二叉树上的叶节点数等于度为2的结点数加1，即 $ n_0 = n_2+1 $

2. 非空二叉树上第 $ k $ 层上至多有 $2^{(k-1)}$ 个结点（$ k \ge 1 $）

3. 高度为 $h$的二叉树之多有 $2^h-1$个结点（$h\ge1$）

4. 具有$n$个结点的完全二叉树的高度为 $ \lceil log_2^{(n+1)} \rceil$ 或 $ \lfloor log_2^n \rfloor + 1 $

5. 对完全二叉树结点进行编号，有如下关系

项目	1-based 编号（根=1）	0-based 编号（根=0）
左孩子	$\text{left}(i)=2i $	$ \text{left}(i)=2i+1 $
右孩子	$ \text{right}(i)=2i+1 $	$ \text{right}(i)=2i+2 $
父节点	$ \text{parent}(i)=\lfloor i/2 \rfloor（i>1）$	$ \text{parent}(i)=\lfloor (i-1)/2 \rfloor（i>0）$
至少有左孩子的条件	$ 2i \le n $	$ 2i+1 < n $
右孩子存在条件	$ 2i+1 \le n $	$ 2i+2 < n $
叶节点条件	$i > \lfloor n/2 \rfloor$	$ i > \lfloor (n-2)/2 \rfloor $或 $2i+1 \ge n$
只有左孩子条件	$2i = n $	$ 2i+1 < n $ 且 $ 2i+2 \ge n $
深度（root 层=1）	$ \lfloor \log_2 i \rfloor +1 $	$ \lfloor \log_2 (i+1) \rfloor +1 $
深度（root 层=0）	$ \lfloor \log_2 i \rfloor $	$ \lfloor \log_2 (i+1) \rfloor $

存储结构

顺序存储结构

数组存储，按照完全二叉树的方式来存储，用0或-1表示空结点。

链式存储

C语言描述

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

容易验证，在含有$n$个结点的二叉链表中，含有 $n+1$个空指针域。

n个结点，2n个指针域，n-1个结点头上有一个指针指向自己，故有n+1个空指针域

C++描述

TODO

Rust描述

TODO

二叉树的遍历

先序遍历

先访问根节点，再遍历左子树，再遍历右子树

递归写法

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

非递归写法

void PreOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)){//栈不为空或p不为空时循环
        if(p){
            visit(p);
            Push(S, p);
            p = p->lchild;
        }else{
            Pop(S, p);
            p = p->rchild;
        }
        
    }
    DestroyStack(S);
}

rust语言描述

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}


use std::cell::RefCell;
use std::rc::Rc;

pub fn preorder(root: &mut Option<Rc<RefCell<TreeNode>>>, visit:  &impl Fn(&mut Rc<RefCell<TreeNode>>)) {
    // 先序遍历
    let mut stack = Vec::new();
    let mut p = root.clone();

    // 先序遍历
    while let Some(node) = p {
        visit(node);
        // 把右子节点压入栈中
        if let Some(right) = node.borrow().right.clone() {
            stack.push(right);
        }
        // 左子节点压入栈中，如果左子节点为空则退栈，否则p = Some(left)
        if let Some(left) = node.borrow().left.clone() {
            p = Some(left);
        } else {
            p = stack.pop();
        }
    }
}

中序遍历

先访问左子树，再访问根节点，再访问右子树

递归写法

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

非递归写法

1. 沿着根结点的左孩子，依次入栈，直到左孩子为空，说明已经可以找到可以输出的结点
2. 栈顶元素出栈并访问，若其有右孩子则继续执行1，否则继续执行2

void InOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)){//栈不为空或p不为空时循环
        if(p){
            Push(S, p);
            p = p->lchild;
        }else{
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
        
    }
    DestroyStack(S);
}

后序遍历

先访问左子树，再访问右子树，再访问根节点

递归写法

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

非递归写法

1. 沿着根的左孩子，依次入栈，直到左孩子为空；
2. 读栈顶元素：若其右孩子不为空，且未被访问过，将右子树执行1，否则栈顶元素出栈并访问

若栈顶元素想要出栈访问，要么右子树为空，要么右子树已经访问完（此时左子树早已访问完）因此我们需要用一个辅助指针，表示最近一次访问的结点：

void PostOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTNode *p = T;
    BiTNode *r= NULL;
    while(p || !isEmpty(S)){//栈不为空或p不为空时循环
        if(p){
            Push(S, p);
            p = p->lchild;
        }else{
            GetTop(S,p);
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                Pop(S, p);
            	visit(p);
                r = p;
            	p = NULL;
            }
        }
        
    }
    DestroyStack(S);
}

层次遍历

按照从第一层到最后一层，从左到右的顺序进行遍历

void LevelOrder(BiTree T){
    Queue *Q;
    InitQueue(Q);
    EnQueue(Q, T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
            EnQueue(Q, p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q, p->rchild);
        }
    }
    DestroyQueue(Q);
}

如果需要在每层访问完成时记录或进行一些操作：

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
		: val(0)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x)
		: val(x)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
		: val(x)
		, left(left)
		, right(right)
	{
	}
};
#include <vector>
#include <queue>
using std::vector;
using std::queue;

class Solution {
    public:
	vector<int> rightSideView(TreeNode *root)
	{
		int i, n;
		vector<int> res;
		queue<TreeNode *> que;
		TreeNode *p;
		if (root == nullptr) {
			return res;
		}
		que.push(root);

		while (!que.empty()) {
			n = que.size();
			res.push_back(que.back()->val);
			for (i = 0; i < n; i++) {
				p = que.front();
				if (p->left) {
					que.push(p->left);
				}
				if (p->right){
				que.push(p->right);
				}
				que.pop();
			}
		}
		return res;
	}
};

图

术语

基本概念

术语	解释
有向图（Directed Graph）	图中的边有方向，如 $A \rightarrow B$
无向图（Undirected Graph）	边没有方向，如 $A - B$，表示双向关系

按边结构分类

术语	解释
简单图（Simple Graph）	不允许 自环（从自己连自己）和 重边（两点之间多条边）
多重图（Multigraph）	允许自环和重边

---

特殊图

术语	解释
完全图（Complete Graph）	任意两个顶点之间都有一条边。无向完全图记作 $K_n$，有 $\frac{n(n-1)}{2}$ 条边
子图（Subgraph）	从原图中取部分顶点和边组成的图

图的连通性

术语	解释
连通（Connected）	无向图中，任意两顶点都有路径相连
连通图	图是整体连通的
连通分量	无向图中极大的连通子图（不能再扩大的连通片）
强连通图	在有向图中，任意两点 $u$ 和 $v$ 都存在互相可达的路径
强连通分量	有向图中最大的强连通子图

树相关

术语	解释
生成树（Spanning Tree）	连通无向图中包含所有顶点且边数最少（$n-1$）的树
生成森林（Spanning Forest）	对于不连通的图，由各连通分量分别生成树组成的集合

顶点和边性质

术语	解释
顶点的度（Degree）	与顶点相连的边数（无向图中）
入度（In-degree）	有向图中指向该顶点的边数
出度（Out-degree）	有向图中从该顶点指出去的边数
边的权（Weight）	边上附加的值（如距离、时间、费用等）
网（Network）	权图（带边权的图）又称网
稠密图（Dense Graph）	边数很多的图，模糊的概念
稀疏图（Sparse Graph）	边数很少的图，模糊的概念

路径与距离

术语	解释
路径	顶点序列，任意相邻两点间有边连接
路径长度	该路径上边的数量（或权值总和）
回路（Cycle）	起点和终点相同的路径
简单路径	路径中顶点不重复
简单回路	回路中除起点终点外其他顶点不重复
距离	两顶点间最短路径的长度

存储

邻接矩阵法

无向图：

• 如果 i 和 j 有边：Edge[i][j] = Edge[j][i] = 1
• 如果无边：Edge[i][j] = Edge[j][i] = 0

有向图：

• 如果有 i → j 的边：Edge[i][j] = 1
• 如果没有：Edge[i][j] = 0

网（带权图）：

• 如果 i → j 的权为 w，则 Edge[i][j] = w
• 无边时一般设为 ∞（或一个非常大的数）

C语言描述

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];              // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵
}MGraph;

C++描述

TODO

Rust描述

TODO

邻接表法

C语言描述

#define MaxVertexNum 100
typedef struct ArcNode{//边表结点
    int adjvex; //该弧指向的顶点
    struct ArcNode *next;
    // InfoType info // 边权值
}ArchNode;
typedef struct VNode{//顶点表结点
    VertexType data; // 顶点信息
    ArchNode *first; //指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;///邻接表
    int vexnum, arcnum;
}ALGraph;

C++描述

Rust描述

十字链表法

#define MaxVertexNum 100

typedef struct ArcNode {
    int tailvex;             // 弧尾（出发点）
    int headvex;             // 弧头（终点）
    struct ArcNode *hlink;   // 指向下一个以同一个弧头为头的弧
    struct ArcNode *tlink;   // 指向下一个以同一个弧尾为尾的弧
    int info;                // 权值（可选）
} ArcNode;

typedef struct VexNode {
    char data;               // 顶点信息
    ArcNode *firstin;        // 指向第一个入弧
    ArcNode *firstout;       // 指向第一个出弧
} VexNode;

typedef struct {
    VexNode xlist[MaxVertexNum]; // 顶点表
    int vexnum, arcnum;          // 顶点数、弧数
} OLGraph; // Orthogonal List Graph

邻接多重表

邻接多重表是无向图的另一种链式存储结构

typedef struct ENode {
    int ivex, jvex;                 // 边的两个顶点编号
    struct ENode *ilink, *jlink;   // 分别指向连接ivex和jvex的下一条边
} ENode;

typedef struct VNode {
    char data;                     // 顶点信息
    ENode *firstedge;             // 第一条依附该顶点的边
} VNode;

typedef struct {
    VNode adjList[MaxVertexNum];
    int vexnum, edgenum;
} AMLGraph;  // 邻接多重表：Adjacency Multilist Graph

图的遍历

广度优先搜索

bool visited[MAX_VERTEX_NUM];

void BFSTraverse(Graph G)
    Queue *Q;
    for(i = 0;i<G.vexnum;i++){
        visited[i] = false;
    }
    InitQueue(Q);
	for(i = 0;i<G.vexnum;i++){//对每个连通分量调用BFS
        if(!visited[i]){
            BFS(G,i);
        }
    }   
    DestroyQueue(Q);
}

void BFS(Graph G, int v){//从顶点v触发，广度优先遍历G
    visit(v);
    visited[v] = TRUE;
    Enqueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w//将v的所有未访问的邻接点入队
            if(!visited[w]){
                visit(w);
                visited[w] = true;
                EnQueue(Q,w);
            }
        }
    }
}

如果图为非带权图，可以通过BFS来求单源最短路径问题，主要利用广度优先遍历是按照距离从进到远来遍历图中每个顶点的的性质来决定的。

深度优先搜索

递归形式

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    for(v = 0;v<G.vexnum;v++){
        visited[v]=false;
    }
    for(v = 0;v<G.vexnum;v++){
        if(!visited[v]){
            DFS(G,v);
        }
    }
}
void DFS(Graph G, int v){
    visit(v);
    visited[v] = true;
  	for(w = FirstNeighbor(G,v); w>=0 ; w = NextNeighbor(G,v,w)){
        if(!visited[w]){
            DFS(G,w);
        }
    }
}

非递归形式

void DFS_Non_RC(AGraph &G, int v){
    int w;
    Stack *S;
    InitStack(S);
    for(i = 0;i<G.num;i++){
        visited[i] = false;
    }
    Push(S,v);
    visited[v] = true;//表示已经入栈
    while(!isEmpty(S)){
        k = Pop(S);
        visit(k);
        for(w = FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){
           if(!visited[w]){
               Push(S,w);
               visited[w] = true;
           } 
        }
        
    }
    DestroyStack(S);
}

最小生成树

Prim算法

思想：从一个点开始，每次选择代价最小的边把新的顶点加入生成树

更适合：稠密图（邻接矩阵）

Kruskal算法

思想：把图的所有边按权值排序，从小到大选择边，只要不成环就选

适合：稀疏图

用到并查集避免形成环路

最短路径

Dijkstra算法

单源最短路径问题

Floyd算法

各个顶点之间的最短路径

拓扑排序

关键路径