---

一、数据结构思维导图（文字超清版）

1️⃣ 绪论

数据结构
├── 基本概念
│ ├── 数据 / 数据元素 / 数据项
│ ├── 逻辑结构（集合、线性、树、图）
│ └── 存储结构（顺序、链式、索引、散列）
├── 算法
│ ├── 特性（有穷、确定、可行）
│ ├── 时间复杂度 O(1)/O(n)/O(logn)/O(n²)
│ └── 空间复杂度

---

2️⃣ 线性表

线性表
├── 顺序表
│ ├── 随机访问 O(1)
│ └── 插入删除 O(n)
├── 链表
│ ├── 单链表
│ ├── 双链表
│ └── 循环链表
└── 重点
├── 头插/尾插
├── 快慢指针
└── 链表反转🔥

---

3️⃣ 栈 & 队列

栈（LIFO）
├── 顺序栈 / 链栈
├── 应用
│ ├── 括号匹配
│ ├── 表达式求值
│ └── 递归

队列（FIFO）
├── 循环队列🔥
├── 队满：(rear+1)%n=front
└── 双端队列

---

4️⃣ 串

串
├── 基本操作
├── BF算法
└── KMP🔥
├── next数组
└── 部分匹配思想

---

5️⃣ 树

树
├── 二叉树
│ ├── 性质🔥
│ ├── 遍历（前中后层）🔥
│ └── 存储结构
├── 特殊树
│ ├── 完全二叉树
│ ├── BST🔥
│ ├── AVL🔥
│ └── 哈夫曼树🔥

---

6️⃣ 图

图
├── 存储
│ ├── 邻接矩阵
│ └── 邻接表🔥
├── 遍历
│ ├── DFS
│ └── BFS🔥
├── 应用
│ ├── 最小生成树（Prim/Kruskal）
│ ├── 最短路径（Dijkstra🔥）
│ └── 拓扑排序🔥

---

7️⃣ 查找

查找
├── 顺序查找
├── 折半查找🔥
└── 哈希🔥
├── 冲突处理
└── 装填因子

---

8️⃣ 排序🔥🔥🔥

排序
├── 插入排序
├── 冒泡排序
├── 快速排序🔥
├── 归并排序🔥
├── 堆排序🔥
└── 重点
├── 时间复杂度
├── 稳定性
└── 最坏情况

---

二、各章节必做100题（精编高频题）

---

① 线性表（12题）

1. 顺序表插入第i个元素移动次数
2. 删除元素时间复杂度分析
3. 单链表逆置（必考）
4. 找链表中点（快慢指针）
5. 判断链表是否有环
6. 合并两个有序链表
7. 删除重复节点
8. 双链表插入操作
9. 循环链表判断尾节点
10. 静态链表理解
11. 链表长度计算
12. 头插 vs 尾插区别

---

② 栈和队列（12题）

1. 判断出栈序列是否合法🔥
2. 栈实现表达式计算
3. 中缀→后缀转换🔥
4. 括号匹配问题
5. 递归转非递归
6. 循环队列判满🔥
7. 队列长度计算🔥
8. 双端队列输出序列
9. 两个栈实现队列
10. 栈溢出判断
11. 队列溢出判断
12. 最小栈设计

---

③ 串（10题）

1. BF算法匹配过程
2. KMP next数组求法🔥
3. nextval优化
4. 模式匹配步骤
5. 子串查找
6. 字符串比较
7. 最长公共前缀
8. 字符串逆置
9. 字符统计
10. KMP时间复杂度分析

---

④ 树（18题🔥）

1. 前中序 → 建树🔥
2. 中后序 → 建树🔥
3. 二叉树遍历（递归+非递归）🔥
4. 层序遍历
5. 二叉树高度计算
6. 叶子节点数计算
7. 完全二叉树判断
8. BST查找
9. BST删除🔥
10. AVL旋转🔥
11. 哈夫曼树构造🔥
12. WPL计算🔥
13. 先序线索化
14. 判断是否平衡树
15. 树转二叉树
16. 最近公共祖先
17. 路径长度计算
18. 节点层次判断

---

⑤ 图（18题🔥）

1. DFS遍历🔥
2. BFS遍历🔥
3. 邻接矩阵→邻接表
4. 判断连通图
5. 生成树概念
6. Prim算法🔥
7. Kruskal算法🔥
8. Dijkstra步骤🔥🔥
9. Floyd算法
10. 拓扑排序🔥
11. 判断有环
12. 入度计算
13. 最短路径树
14. 关键路径（AOE网）
15. 边数计算
16. 图的存储选择
17. 强连通分量
18. 图遍历复杂度

---

⑥ 查找（10题）

1. 顺序查找成功/失败比较次数
2. 折半查找过程🔥
3. 判定树构造
4. 哈希冲突处理🔥
5. 装填因子计算🔥
6. 查找长度ASL
7. 开放定址法
8. 链地址法
9. 查找性能分析
10. 静态查找表

---

⑦ 排序（20题🔥🔥🔥）

1. 快速排序过程🔥
2. 快排最坏情况🔥
3. 归并排序过程🔥
4. 堆排序建堆🔥
5. 冒泡排序优化
6. 插入排序步骤
7. 各排序时间复杂度🔥
8. 稳定性判断🔥
9. 排序趟数计算
10. 堆调整过程
11. 分治思想理解
12. 外排序
13. 基数排序
14. 希尔排序
15. 排序比较次数
16. 最优/最坏情况
17. 排序应用选择
18. 链表适合排序
19. 数据规模分析
20. 排序算法对比🔥

---

三、冲刺建议（非常关键🔥）

你现在应该这样做：

• 第1遍：看思维导图（建立体系）
• 第2遍：刷这100题（每天10题）
• 第3遍：专攻👇
  • 树（建树+遍历）
  • 图（Dijkstra+拓扑）
  • 排序（快排+归并）

数据结构考研核心知识点总结

---

第一章：绪论

本章是基础，主要考察基本概念的理解和算法复杂度的计算。

1. 数据结构三要素

逻辑结构（与计算机无关）：

集合结构：元素同属一个集合，无其他关系。

线性结构：一对一（如线性表、栈、队列）。

树形结构：一对多（如二叉树、堆）。

图状/网状结构：多对多（如图）。

存储结构（物理结构）：

顺序存储：逻辑相邻则物理相邻（数组），支持随机访问。

链式存储：指针表示逻辑关系（链表），不支持随机访问。

索引存储：建立索引表（关键字，地址）。

散列存储：通过哈希函数计算地址。

数据运算：定义在逻辑结构上，实现于存储结构上（如增删改查）。

2. 算法分析

时间复杂度 T(n)T(n)T(n)：

常见排序：O(1)<O(log⁡2n)<O(n)<O(nlog⁡2n)<O(n2)<O(n3)<O(2n)O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n)O(1)<O(log2​n)<O(n)<O(nlog2​n)<O(n2)<O(n3)<O(2n)。

计算规则：加法法则（取最大量级）、乘法法则（嵌套循环相乘）。

空间复杂度 S(n)S(n)S(n)：

包括固定部分（代码、常量）和可变部分（动态分配空间、递归栈）。

递归算法的空间复杂度 = 递归深度 ×\times× 每次递归所需辅助空间。

---

第二章：线性表

线性表是基础，重点在于顺序表与链表的对比及操作实现。

1. 顺序表

特点：随机访问 O(1)O(1)O(1)，插入删除需移动元素 O(n)O(n)O(n)，存储密度高。

核心操作：

插入：判断表满 -> 移动元素（从后向前） -> 赋值 -> 长度+1。

删除：判断表空 -> 保存删除值 -> 移动元素（从前向后） -> 长度-1。

2. 链表

单链表：

头结点：引入头结点可使首元节点的操作与其他节点一致，简化代码。

头插法：新节点插入头结点之后（会导致逆序）。

尾插法：增加尾指针，新节点插入尾部（保持顺序）。

双链表：

节点包含 prior 和 next 指针。

插入/删除：需同时修改前驱和后继的指针，注意操作顺序（先连后断）。

循环链表：

尾结点的 next 指向头结点。

判空：L->next == L（带头结点）。

静态链表：

用数组实现，游标（next）模拟指针。适用于不支持指针的语言或特定场景。

3. 顺序表 vs 链

存取方式：顺序表支持随机存取；链表仅支持顺序存取。

查找效率：按值查找两者均为 O(n)O(n)O(n)；按位查找顺序表 O(1)O(1)O(1)，链表 O(n)O(n)O(n)。

插入删除：顺序表 O(n)O(n)O(n)；链表找到位置后 O(1)O(1)O(1)。

---

第三章：栈、队列与数组

1. 栈

特性：后进先出（LIFO）。

● 

存储结构：

顺序栈：top 指针指向栈顶元素。判满 top == MaxSize-1，判空 top == -1。

共享栈：两个栈共用一维数组，栈底分别在两端，向中间增长。判满条件：top1 + 1 == top2。

链栈：通常采用带头结点的单链表，头插法入栈，头删法出栈。

应用：括号匹配、表达式求值（中缀转后缀/前缀）、递归（系统栈）。

2. 队列

特性：先进先出（FIFO）。

存储结构：

循环队列（顺序存储）：解决“假溢出”。

判空：front == rear。

判满：(rear + 1) % MaxSize == front（牺牲一个单元）。

入队：rear = (rear + 1) % MaxSize。

链队列：带头结点，队头出队，队尾入队。

双端队列：两端均可进出。

3. 数组与矩阵

数组：顺序存储，计算地址（行优先/列优先）。

特殊矩阵压缩存储：

对称矩阵：只存下三角（或上三角），k=i(i−1)/2+j−1k = i(i-1)/2 + j - 1k=i(i−1)/2+j−1。

三对角矩阵：带状存储。

稀疏矩阵：三元组顺序表（行、列、值）或十字链表。

4. 串

模式匹配：

BF算法：朴素匹配，回溯，O(mn)O(mn)O(mn)。

KMP算法：主串指针不回溯。

Next数组：表示模式串的最长相等前后缀长度。

Nextval数组：对Next的优化，避免重复字符的无效比较。

---

第四章：树与二叉树

1. 二叉树性质

第 iii 层最多有 2i−12^{i-1}2i−1 个节点。

深度为 kkk 的二叉树最多有 2k−12^k - 12k−1 个节点。

完全二叉树：叶子节点只出现在最下两层，且最下层叶子集中在左侧。

满二叉树：每一层节点数都达到最大值。

2. 存储结构

顺序存储：适用于完全二叉树，利用数组下标关系（iii 的左孩子 2i2i2i，右孩子 2i+12i+12i+1）。

链式存储：二叉链表（lchild, data, rchild）。

3. 遍历

先序/中序/后序：递归实现简单，非递归实现需借助栈。

层序遍历：借助队列实现。

线索二叉树：利用空指针域存放前驱或后继线索，加快查找前驱/后继的速度。

4. 特殊树

二叉排序树：左 < 根 < 右。查找、插入、删除效率取决于树高。

平衡二叉树：左右子树高度差绝对值 ≤1\le 1≤1。调整方法：LL、RR、LR、RL旋转。

哈夫曼树：带权路径长度（WPL）最短。构造方法：每次选两个权值最小的节点合并。

森林与二叉树转换：左孩子右兄弟表示法。

---

第五章：图

1. 存储结构

邻接矩阵：适合稠密图，判断边存在 O(1)O(1)O(1)，空间 O(n2)O(n^2)O(n2)。

邻接表：适合稀疏图，空间 O(n+e)O(n+e)O(n+e)，查找边需遍历链表。

十字链表（有向图）、邻接多重表（无向图）。

2. 遍历

深度优先搜索：类似树的先序遍历，用栈（递归）。

广度优先搜索：类似树的层序遍历，用队列。

3. 重要算法

最小生成树：

Prim算法：加点法，适合稠密图，复杂度 O(n2)O(n^2)O(n2)。

Kruskal算法：加边法（并查集），适合稀疏图，复杂度 O(elog⁡e)O(e \log e)O(eloge)。

最短路径：

Dijkstra：单源最短路径（权值非负），贪心策略。

Floyd：多源最短路径，动态规划，复杂度 O(n3)O(n^3)O(n3)。

拓扑排序：AOV网，检测有向环（入度为0的顶点入队）。

关键路径：AOE网，求最早/最晚发生时间，确定关键活动。

---

第六章：查找

1. 静态查找

顺序查找：O(n)O(n)O(n)。

折半查找：仅适用于有序顺序表，O(log⁡2n)O(\log_2 n)O(log2​n)。判定树为平衡二叉树。

分块查找：块间有序，块内无序。

2. 动态查找

二叉排序树：查找效率 O(h)O(h)O(h)。

B树与B+树：多路平衡查找树，主要用于数据库和文件系统索引。

      B树：关键字分布在所有节点，搜索可能在非叶子节点结束。

      B+树：关键字仅在叶子节点，且叶子节点链式连接，适合范围查找。

3. 哈希表

哈希函数构造：直接定址、除留余数法等。

冲突处理：

     开放定址法：线性探测（易聚集）、平方探测。

     链地址法：拉链法，适合插入删除频繁。

    查找效率：取决于装填因子 α\alphaα = 表中记录数 / 哈希表长度。

---

第七章：排序

1. 插入排序

       直接插入：稳定，O(n2)O(n^2)O(n2)，适合基本有序。

       希尔排序：缩小增量排序，不稳定，O(n1.3)O(n^{1.3})O(n1.3)。

2. 交换排序

       冒泡排序：稳定，O(n2)O(n^2)O(n2)。

       快速排序：不稳定，平均 O(nlog⁡n)O(n \log n)O(nlogn)，最坏 O(n2)O(n^2)O(n2)（有序时）。空间复杂度 O(log⁡n)O(\log n)O(logn)（递归栈）。

3. 选择排序

     简单选择：不稳定，O(n2)O(n^2)O(n2)，比较次数固定。

    堆排序：不稳定，O(nlog⁡n)O(n \log n)O(nlogn)。 

  大顶堆：升序排列。

     应用：Top K问题、优先级队列。

4. 归并排序

    二路归并，稳定，O(nlog⁡n)O(n \log n)O(nlogn)，空间 O(n)O(n)O(n)。

5. 基数排序

    多关键字排序，稳定，O(d(n+r))O(d(n+r))O(d(n+r))。

6. 排序

稳定排序：直接插入、冒泡、归并、基数。

不稳定排序：希尔、快速、简单选择、堆。

辅助空间：堆排序 O(1)O(1)O(1)，快速排序 O(log⁡n)O(\log n)O(logn)，归并排序 O(n)O(n)O(n)。