经典好文已翻新——新·数据结构强化笔记（New Quick Tutorial of Data Structures and Algorithms）。继承2312精神，再创佳绩！本教程以原理剖析为主，大量使用叙述性的伪代码或冗余编码，实际应用请参阅常用算法代码模板。

1 绪论

在开始前请先阅读附录“0 C/C++强化补充”

1.1 数据结构基础

1.2 算法与算法分析

---

2 线性表

2.1 顺序表

2.2 单链表

2.3 其他链表结构

---

3 栈与队列

3.1 栈

3.2 队列

3.3 栈与队列的应用

---

4 串与模式匹配算法

4.1 串

4.2 模式匹配

---

5 扩展线性表结构

5.1 数组

5.2 矩阵

5.3 广义表

---

6 树与二叉树

6.1 树的逻辑结构

6.2 二叉树

6.3 树与森林

6.4 树与二叉树的应用

---

7 图

7.1 图论重要概念

7.2 图的存储结构

7.2.1 邻接矩阵

7.2.2 邻接表

7.2.3 其他存储结构

7.3 图的遍历

7.3.1 广度优先遍历（BFS）

7.3.2 深度优先遍历（DFS）

7.3.3 BFS、DFS的应用

7.4 图的应用

7.4.1 最小生成树

7.4.1.1 Prim算法

7.4.1.2 Kruskal算法

7.4.2 最短路径

7.4.2.1 Dijkstra算法

7.4.2.2 Floyd算法

7.4.3 有向无环图存储表达式

7.4.4 拓扑排序

7.4.5 关键路径

---

8 查找

8.1 简单查找

8.1.1 顺序查找

8.1.2 折半查找

8.1.3 分块查找

8.2 树型查找

8.2.1 二叉排序树（BST）

8.2.2 平衡二叉树（AVL树）

8.2.3 红黑树

8.3 B树与B+树

8.3.1 B树

8.3.2 B+树的基本概念

8.4 散列表

8.4.1 散列函数与冲突

8.4.2 散列性能分析

---

9 排序

9.1 插入类排序

9.1.1 直接插入排序

9.1.2 折半插入排序

9.1.3 希尔排序

9.2 交换类排序

9.2.1 起泡排序

9.2.2 快速排序

9.3 选择类排序

9.3.1 简单选择排序

9.3.2 堆排序

9.4 归并排序

9.5 基数排序

9.6 外部排序

---

0 C/C++强化补充

源自“第0章 C语⾔强化补充笔记”，运算符优先级表新增了部分C++内容（范围解析）。

0.1 数据类型的⻓度

以下几类数据类型的长度随操作系统而变：

操作系统\数据类型	int	long	long long	指针
16位	2B	4B	/	2B
32位	4B	4B	8B	4B
64位	4B	8B	8B	8B

以下几类数据类型在任意操作系统（double除外，在16位机器上不存在）均为固定长度：

数据类型	char	short	float	double
固定长度	1B	2B	4B	8B

结构体补齐：结构体变量的总大小为结构体变量中最大基本数据类型成员所占字节数的整数倍

0.2 运算符优先级

下表中数字越⼩，优先级越⾼（即“越先算”）：

优先级	运算符	结合方向
0	::（C++范围解析）	自左向右
1	i++（后缀自增） i--（后缀自减） ()（圆括号/函数调用运算符） []（数组下标） .（成员） ->（指向成员）	++ --：自右向左 其他：自左向右
2	++i（前缀自增） --（前缀自减） +（正号） -（负号） !（逻辑非） ~（按位取反） (type)（强制类型转换） *（指针） &（取地址/C++引用） sizeof（按字节确定大小）	自右向左
3	*（乘） / %	自左向右
4	+（加） -（减）	自左向右
5	<<（按位左移） >>（按位右移）	自左向右
6	< <= > >=	自左向右
7	== !=	自左向右
8	&（按位与）	自左向右
9	^（按位异或）	自左向右
10	|（按位或）	自左向右
11	&&（逻辑与）	自左向右
12	||（逻辑或）	自左向右
13	? :（三目条件运算符）	自右向左
14	= += -= *= /= %= &= ^= |= <<= >>=	自右向左
15	,（逗号运算符）	自左向右

0.3 数据的输⼊输出

0.3.1 格式化输⼊（scanf）

格式字符串：%[*][宽度][类型长度]类型

1. 类型（Type）：

数据类型格式	说明	进制数格式	说明
%d	整型（int）	%o	八进制
%ld	长整型（long int）	%#o	带前导的八进制
%f	单精度浮点型（float）	%x	十六进制
%lf	双精度浮点型（double）	%#x	带前导的十六进制
%c	字符（char）
%s	字符串

0.3.2 格式化输出（printf）

0.3.3 转义字符

0.4 文件操作