目录

第1章　数据结构与算法     1

1.1　数据结构     1

1.1.1　什么是数据结构     1

1.1.2　数据结构的发展     2

1.1.3　数据基本特性     3

1.1.4　数据的逻辑结构和存储结构     4

1.1.5　数据结构的研究对象     5

1.2　算法     6

1.2.1　什么是算法     6

1.2.2　算法的特性     6

1.2.3　算法的时间复杂度和空间复杂度     7

1.2.4　算法的描述方法     8

1.3　算法分析     9

1.3.1　算法的复杂度分析     9

1.3.2　常用的算法设计方法     10

1.3.3　算法分析在竞赛中的应用     10

1.4　数据结构与算法的关系     11

1.5　牛刀小试     13

第2章　算法编程基础     15

2.1　基本数据类型     15

2.1.1　基本数据类型的分类     15

2.1.2　竞赛真题实战     17

2.2　变量与常量     17

2.2.1　变量的命名与赋值     17

2.2.2　常量     18

2.2.3　输入与输出     19

2.2.4　竞赛真题实战     21

2.3　运算符和表达式     21

2.3.1　算术运算符     21

2.3.2　逻辑运算符     22

2.3.3　关系运算符     22

2.3.4　条件运算符     22

2.3.5　赋值运算符     24

2.3.6　位运算符     24

2.3.7　竞赛真题实战     25

2.4　流程控制     25

2.4.1　顺序结构     25

2.4.2　条件分支结构     26

2.4.3　循环结构     27

2.4.4　竞赛真题实战     27

2.5　数组     28

2.5.1　一维数组     28

2.5.2　二维数组     29

2.5.3　竞赛真题实战     31

2.6　函数     31

2.6.1　函数定义     32

2.6.2　函数的使用     32

2.6.3　函数重载     33

2.6.4　竞赛真题实战     33

2.7　牛刀小试     34

第3章　栈和队列     37

3.1　栈     37

3.1.1　顺序栈     38

3.1.2　链栈     38

3.1.3　栈的基本操作     39

3.1.4　使用数组实现栈     44

3.1.5　使用链表实现栈     48

3.1.6　竞赛真题实战     52

3.2　队列     53

3.2.1　顺序队列     53

3.2.2　链式队列     54

3.2.3　队列的基本操作     54

3.2.4　使用数组实现队列     62

3.2.5　使用链表实现队列     65

3.2.6　竞赛真题实战     69

3.3　竞赛真题：栈实现队列     70

3.4　竞赛真题：队列实现栈     71

3.5　优先队列     73

3.5.1　优先队列的基本操作     73

3.5.2　竞赛真题实战     77

3.6　牛刀小试     78

第4章　树与二叉树     81

4.1　树     81

4.1.1　树的定义     81

4.1.2　树的存储     83

4.1.3　竞赛真题实战     87

4.2　二叉树     87

4.2.1　二叉树的定义     88

4.2.2　二叉树的性质     89

4.2.3　二叉树的存储结构     92

4.2.4　二叉树的遍历     93

4.2.5　竞赛真题实战     101

4.3　二叉查找树     102

4.3.1　二叉查找树的定义     102

4.3.2　二叉查找树的基本操作及性能分析     102

4.3.3　竞赛真题实战     107

4.4　平衡二叉树     108

4.4.1　平衡二叉树的定义     108

4.4.2　平衡二叉树的基本操作     109

4.4.3　红黑树的定义及性能分析     117

4.4.4　竞赛真题实战     118

4.5　森林     119

4.5.1　森林的定义     119

4.5.2　森林的遍历     119

4.5.3　树、森林与二叉树的转换     120

4.5.4　竞赛真题实战     122

4.6　牛刀小试     122

第5章　图的存储、遍历和连贯性     125

5.1　图     125

5.1.1　图的定义     125

5.1.2　图的分类     126

5.1.3　竞赛真题实战     127

5.2　图的存储     128

5.2.1　邻接矩阵     129

5.2.2　边集数组     132

5.2.3　邻接表     133

5.2.4　十字链表     138

5.2.5　链式前向星     141

5.2.6　竞赛真题实战     144

5.3　图的遍历     145

5.3.1　广度优先遍历     145

5.3.2　深度优先遍历     148

5.3.3　竞赛真题实战     151

5.4　图的连通性     152

5.4.1　基本定义与分类     152

5.4.2　Tarjan算法     153

5.4.3　竞赛真题实战     157

5.5　牛刀小试     158

第6章　图的应用     162

6.1　最小生成树     162

6.1.1　Prim算法     162

6.1.2　Kruskal算法     168

6.1.3　竞赛真题实战     171

6.2　最短路径     172

6.2.1　Dijkstra算法     172

6.2.2　Floyd算法     177

6.2.3　竞赛真题实战     180

6.3　有向无环图     181

6.3.1　拓扑排序     181

6.3.2　关键路径     184

6.3.3　竞赛真题实战     188

6.4　牛刀小试     189

第7章　排序算法     193

7.1　排序算法的基础     193

7.1.1　排序的目的     193

7.1.2　排序的分类     194

7.2　冒泡排序     194

7.2.1　冒泡排序的思想     194

7.2.2　冒泡排序的实现     195

7.3　选择排序     196

7.3.1　选择排序的思想     196

7.3.2　选择排序的实现     197

7.4　插入排序     198

7.4.1　插入排序的思想     198

7.4.2　插入排序的实现     199

7.5　快速排序     200

7.5.1　快速排序的思想     200

7.5.2　快速排序的实现     201

7.6　归并排序     202

7.6.1　归并排序的思想     202

7.6.2　归并排序的实现     203

7.7　希尔排序     204

7.7.1　希尔排序的思想     205

7.7.2　希尔排序的实现     205

7.8　竞赛真题实战     206

7.9　牛刀小试     209

第8章　贪心算法     213

8.1　贪心算法的定义和应用场景     213

8.1.1　贪心算法的定义     213

8.1.2　经典应用场景     214

8.2　哈夫曼编码     214

8.2.1　哈夫曼编码的原理     214

8.2.2　哈夫曼编码的实现     215

8.2.3　竞赛真题实战     220

8.3　竞赛真题：货币选择问题     220

8.4　竞赛真题：最优装载问题     221

8.5　竞赛真题：区间调度问题     222

8.6　竞赛真题：汽车加油问题     223

8.7　竞赛真题：背包问题     224

8.8　牛刀小试     225

第9章　动态规划算法     228

9.1　动态规划算法的核心思想和算法步骤     228

9.1.1　动态规划的核心思想与特性     228

9.1.2　动态规划的算法步骤     229

9.2　背包动态规划     229

9.2.1　0-1背包     229

9.2.2　完全背包     233

9.2.3　竞赛真题实战     233

9.3　竞赛真题：线性动态规划     235

9.4　竞赛真题：区间动态规划     236

9.5　竞赛真题：树状动态规划     237

9.6　牛刀小试     238