【总结笔记】数据结构核心

【总结笔记】数据结构核心知识点

本部分涵盖：复杂度分析、C语言指针与链表、排序算法模板、图的存储与算法、AOE关键路径、散列表查找、树与动态内存、数据结构选型、逻辑运算符vs位运算符。

---

一、时间复杂度与空间复杂度

1.1 大O计算三大铁律

1. 只保留最高阶：$O(3n^2+5n+10)\to O(n^2)$
2. 常数系数化为1：$O(5n)\to O(n)$
3. 串行取大：$O(f)+O(g)=O(\max (f,g))$；嵌套相乘：$O(f)\times O(g)=O(f\cdot g)$

1.2 常见量级速查（从快到慢）

$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$

代码特征	复杂度	典型例子
无循环/常数次循环	$O(1)$	数组随机访问、基本运算
变量每次乘/除常数	$O(\log n)$	二分查找、while(i<n) i*=2
单层循环	$O(n)$	遍历数组/链表
外$O(n)$内$O(\log n)$	$O(n\log n)$	快速排序/归并排序（平均）
双层嵌套循环	$O(n^2)$	冒泡/插入/选择排序
分治双侧递归 $T(n)=2T(n/2)+O(n)$	$O(n\log n)$	归并排序
分治单侧递归 $T(n)=T(n/2)+O(n)$	$O(n)$	快速选择（QuickSelect）

1.3 空间复杂度

• 只计额外申请的空间，不计输入数组本身
• 几个局部变量 → $O(1)$
• 申请$n$大小辅助数组（malloc）→ $O(n)$
• 递归空间 = 递归树最大深度（最易遗漏！）
  • 线性递归（链表递归）→ $O(n)$
  • 平衡分治递归（快排平均）→ $O(\log n)$，最坏 $O(n)$

考场救命策略：卡住时先牺牲空间开辅助数组，用$O(n)$空间换时间，大题至少拿8-10分。

---

二、C语言指针与链表

2.1 指针三口诀

符号	含义	比喻
&a	取变量a的地址	查房号
p	指针变量，存储地址	装门牌号的纸条
*p	解引用，取地址处的数据	拿钥匙开门取数据

-> 箭头：指针访问结构体成员的语法糖

• slow->data 等价于 (*slow).data（开门取单间里的物品）
• 只要是指针就用 -> ；只要是实体结构体变量就用 .

2.2 链表标准定义（默写级）

typedef struct LNode {
    int data;           // 数据域
    struct LNode *link; // 指针域（内部必须用struct LNode*，不能用LNode*）
} LNode, *LinkList;
// LNode：结点实体；LinkList：头指针（等价于LNode*）

为什么内部必须写 struct LNode *？

• 在定义末尾前别名LNode尚未生效，必须用完整名称
• 必须是指针（*），不能是实体（固定大小，编译器可计算）

2.3 标准答题模板

int Solution(LinkList list, int k) {
    LNode *p, *q;          // 变量集中声明（兼容老编译器）
    // 异常拦截（必写！）
    if (list == NULL || list->link == NULL || k <= 0) return 0;
    // 指针初始化（跨过头结点）
    p = list->link;
    q = list->link;
    // ... 核心逻辑（快慢指针/双指针等）...
    return 1;
}
// 考研笔试：写到这里就行，不要写main函数！

常见链表技巧：

• 快慢指针：快指针先走k步，然后同速，快到末尾时慢指针正好在倒数第k
• 链表逆置：用三指针（prev、curr、next）逐个反转

---

三、排序算法对比与模板

3.1 排序算法复杂度速查

算法	平均时间	最坏时间	空间	稳定性
快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定

比较排序时间下限：$O(n\log n)$

3.2 快速排序模板（必背）

int Partition(int A[], int low, int high) {
    int pivot = A[low];  // 枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) --high; // >=必须带等号
        A[low] = A[high];
        while (low < high && A[low] <= pivot) ++low;   // <=必须带等号
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}
void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pos = Partition(A, low, high);
        QuickSort(A, low, pos - 1);
        QuickSort(A, pos + 1, high);
    }
}

内层while必须有 low < high：防止指针越界（极端情况下high会冲过low）

3.3 直接插入排序模板

void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        if (A[i] < A[i-1]) {
            temp = A[i];
            for (j = i-1; j >= 0 && A[j] > temp; j--)
                A[j+1] = A[j];
            A[j+1] = temp;
        }
    }
}

---

四、图的存储与算法

4.1 存储结构对比

对比项	邻接矩阵	邻接表
空间	$O(	V
适用	稠密图	稀疏图
查边	$O(1)$（直接查表）	$O(度数)$
有向图入度	按列求和，简单	极其麻烦，需遍历全图
遍历序列	唯一（按编号扫描）	不唯一（链表插入顺序影响）

十字链表：解决有向图邻接表找入度难的问题
邻接多重表：解决无向图邻接表一条边存两次的问题

4.2 图遍历

BFS（广度优先）：

• 数据结构：队列
• 思路：水波纹扩散，按层访问
• 邻接矩阵→序列唯一；邻接表→序列不唯一

DFS（深度优先）：

• 数据结构：栈/递归
• 思路：不撞南墙不回头，走到底再回溯

4.3 最小生成树

算法	策略	适用	复杂度
Prim（普里姆）	以点带面，从一个点贪心吞并最近邻居	稠密图	$O(
Kruskal（克鲁斯卡尔）	全局上帝视角，从小到大选边，不成环则保留	稀疏图	$O(

4.4 最短路径

算法	功能	限制
Dijkstra	单源最短路（一个起点到所有点）	不能有负权边
Floyd	多源最短路（所有点对之间）	循环顺序：k在最外层

Floyd三层循环：for(k) { for(i) { for(j) { } } } —— k必须在最外层！

4.5 拓扑排序

1. 找入度为0的顶点，输出并删除其发出的边
2. 重复直到全部输出（若中途找不到入度为0的点→图中有环）

• 结果可能不唯一（多个入度为0时任选一个）

---

五、AOE网与关键路径

• 顶点（事件）：里程碑，不耗时
• 边（活动）：施工任务，有权值（耗时）
• 关键路径：从起点到终点所有路径中耗时最长的路径（决定项目完成时间）

极速解法：列出所有路径，取最大值

四大高频问题：

1. 最短完成时间：即关键路径长度（最长路径）
2. 关键活动：在关键路径上，最早开始时间 = 最晚开始时间（无时间余量）
3. 可同时进行：判断两活动时间区间是否有重叠
4. 缩短工期：缩短关键活动才能缩短工期；缩短非关键活动无效

---

六、散列表（哈希表）查找

6.1 解题四步法（口诀：α先算表长，成功看插入，失败探到空，分母看值域）

Step 1. 算表长：m = n / α（α为装填因子，n为关键字个数）
Step 2. 画表：逐个关键字算H(key)，冲突则线性探测，记录每个元素插入探测次数
Step 3. 算成功ASL = Σ(各元素探测次数) / n
Step 4. 算失败ASL：对散列函数值域内每个地址，探测到第一个空位，记次数；
        Σ(各地址探测次数) / 值域大小

6.2 核心陷阱

易错点	正确做法
看到α直接算ASL	先用 $m=n/\alpha$ 算出表长
失败ASL分母用表长m	失败ASL分母 = 散列函数值域大小（mod几就是几）
探测次数：直接命中算0次	第1次比较就算1次，直接命中也是1次
失败探测空位不算次数	到达空位本身也算1次（看到它才知道是空的）
成功ASL分母用值域	成功ASL分母 = 关键字个数n

---

七、树与动态内存管理

7.1 二叉树结构定义

typedef struct TreeNode {
    int weight;
    struct TreeNode *left;   // 内部必须写struct TreeNode*
    struct TreeNode *right;
} TreeNode, *BiTree;
// BiTree root; 等价于 struct TreeNode *root;

7.2 动态内存三件套

// 申请节点
BiTree node = (BiTree)malloc(sizeof(TreeNode)); // sizeof用实体类型！
// sizeof(BiTree) 只有4/8字节（指针大小），必须用sizeof(TreeNode)
 
// 释放节点（黄金法则：free后必须置NULL）
free(node);
node = NULL; // 防野指针！

销毁树/链表顺序：先子后父（后序遍历思想）

void destroyTree(BiTree root) {
    if (root == NULL) return;
    destroyTree(root->left);   // 先销毁左子树
    destroyTree(root->right);  // 再销毁右子树
    free(root);                // 最后释放自己
}

---

八、数据结构选型速查

逻辑结构（4种）

场景特征	逻辑结构
一对一关系、序列、排队	线性结构
分支/层次、目录、前缀编码	树形结构
多对多、网络拓扑、社交好友	图形结构
无逻辑关系的元素集合	集合

物理/存储结构选型

需求关键词	选用结构
先进后出、递归、回溯、括号匹配	栈
先进先出、缓冲、BFS层次遍历	队列
前缀编码、层次决策、哈夫曼	二叉树
查找极快$O(1)$、关键字直接映射	散列表
频繁中间插入/删除、不需随机访问	链表
稠密图、快速判断两点是否有边	邻接矩阵
稀疏图、节省空间	邻接表

---

九、逻辑运算符 vs 位运算符

符号	类型	短路特性	作用对象
&&	逻辑与	有（左假则停）	布尔条件
||	逻辑或	有（左真则停）	布尔条件
&	按位与	无	整数二进制位
|	按位或	无	整数二进制位

短路机制的重要性：

// 安全写法（&&有短路，p为NULL时不会访问p->data）
if (p != NULL && p->data == 5) { ... }
 
// 危险写法（&无短路，p为NULL时强行读p->data，崩溃！）
if (p != NULL & p->data == 5) { ... }

口诀：条件判断用双符号&&/||（带短路保护）；位操作用单符号&/|（逐位运算）

---

十、高频易错汇总

错误	正确做法
快排Partition等号漏掉	A[high]>=pivot 和 A[low]<=pivot 必须带等号，否则有重复元素时死循环
链表题直接用slow.data	指针必须用->：slow->data
函数内用sizeof(A)算数组长度	数组传参退化为指针，sizeof(A)=8（指针大小）！必须在main中算好n传参
递归函数空间复杂度写O(1)	递归有调用栈，至少$O(\log n)$（平衡树）或$O(n)$（线性递归）
散列失败ASL分母用表长	分母 = 散列函数值域大小（mod几就是几）
malloc用sizeof(BiTree)	必须用sizeof(TreeNode)，指针只有4/8字节！
free后指针不置NULL	free后必须node=NULL，防野指针崩溃
Floyd循环k放中间层	k必须在最外层：for(k) for(i) for(j)
邻接表BFS/DFS序列唯一	邻接表序列不唯一，只有邻接矩阵才唯一
关键路径取最短路径	关键路径 = 最长路径（决定工期下限）