第1章 基础数据结构 1
1.1数组 1
1.1.1一维数组 1
1.1.2二维数组 2
1.1.3三维及更高维数组 3
1.2链表 4
1.2.1单向链表 5
1.2.2双向链表 14
1.3栈 19
1.3.1基于数组的栈 19
1.3.2基于链表的栈 21
1.4队列 23
1.4.1基于数组的队列 23
1.4.2基于链表的队列 26
第2章 递归与动态规划 28
2.1递归 28
2.1.1阶乘 28
2.1.2斐波那契数列 30
2.2动态规划 32
2.2.1斐波那契数列 33
2.2.2最长公共子序列 36
第3章 树 45
3.1二叉树 46
3.1.1完全二叉树 47
3.1.2满二叉树 48
3.1.3平衡二叉树 48
3.2二叉搜索树 49
3.2.1性质 49
3.2.2插入操作 50
3.2.3插入顺序性 51
3.2.4查找操作 53
3.2.5中序前驱节点 54
3.2.6中序后继节点 56
3.2.7删除操作 58
3.3AVL树 61
3.3.1性质 61
3.3.2二叉搜索树的平衡 62
3.3.3为什么要旋转 63
3.3.4插入类型及旋转 63
3.3.5插入操作 67
3.3.6查找操作 68
3.3.7删除操作 69
3.4红黑树 71
3.4.1性质 71
3.4.2旋转和变色 72
3.4.3插入操作 72
3.4.4查找操作 79
3.4.5删除操作 80
3.5 2-3树 86
3.5.1性质 86
3.5.2插入操作 87
3.5.3查找操作 89
3.5.4删除操作 91
3.6B树 98
3.6.1性质 98
3.6.2插入操作 99
3.6.3查找操作 102
3.6.4删除操作 102
3.7Trie树 109
3.7.1性质 109
3.7.2插入操作 109
3.7.3查找操作 111
3.7.4删除操作 113
第4章 堆 117
4.1二叉堆 117
4.1.1二叉堆的性质 117
4.1.2二叉堆的实现 118
4.1.3二叉堆的作用 118
4.1.4插入操作 118
4.1.5删除操作 121
4.1.6构建操作 123
4.2二项堆 125
4.2.1结构与性质 125
4.2.2插入与合并 126
4.2.3查找最大（小）值 129
4.2.4删除最大（小）值 131
4.3斐波那契堆 133
4.3.1结构及性质 133
4.3.2斐波那契数列 134
4.3.3插入操作 135
4.3.4获取最小节点 136
4.3.5合并两个斐波那契堆 136
4.3.6删除最小键值节点 136
4.3.7减小节点键值 139
4.3.8删除节点 142
第5章 图 143
5.1图的表示方式 144
5.2图的遍历 145
5.2.1广度优先搜索 146
5.2.2深度优先搜索 151
5.3图的最短路径 158
5.3.1Dijkstra算法 158
5.3.2Floyd算法 166
5.4最小生成树 177
5.4.1Prim算法 178
5.4.2并查集 185
5.4.3Kruskal算法 190
第6章 比较排序 196
6.1选择排序 196
6.1.1排序要点 196
6.1.2排序性能 197
6.1.3排序过程 197
6.1.4稳定性 199
6.2冒泡排序 200
6.2.1排序要点 201
6.2.2排序性能 201
6.2.3排序过程 201
6.3插入排序 203
6.3.1排序要点 203
6.3.2排序性能 204
6.3.3排序过程 204
6.4快速排序 207
6.4.1排序要点 207
6.4.2排序性能 207
6.4.3排序过程 208
6.5希尔排序 213
6.5.1排序要点 214
6.5.2排序性能 214
6.5.3排序过程 214
6.6合并排序 219
6.6.1排序要点 220
6.6.2排序性能 220
6.6.3排序过程 220
6.7堆排序 230
6.7.1排序要点 230
6.7.2排序性能 231
6.7.3排序过程 231
第7章 非比较排序 236
7.1计数排序 236
7.1.1不考虑稳定性的情况 236
7.1.2考虑稳定性的情况 239
7.1.3计数排序的局限 247
7.2基数排序 247
7.2.1排序性能 247
7.2.2排序方式 247
7.2.3基于计数排序的实现 248
7.2.4基于桶的实现 253
7.2.5MSD排序方式 257
7.3桶排序 260
7.3.1排序性能 260
7.3.2排序要点 261
7.3.3桶的区间 261
7.3.4排序过程 261