第1章 引言 1
1.1 算法与数据结构 1
1.1.1 数据的逻辑结构 2
1.1.2 数据结构的运算 3
1.2 存储实现 4
1.3算法分析 4
1.3.1 时间复杂度的概念 5
1.3.2 算法运算量的计算 6
1.3.3 渐进表示法 8
1.3.4 时间复杂度的计算 10
1.3.5 算法的优化 11
1.4 面向对象的方法 15
1.4.1 面向对象的概念 15
1.4.2 用面向对象的思想讨论数据结构 16
1.4.3 面向对象方法中数据结构的描述和实现 16
1.5 本书的结构和特点 17
1.6 本书采用的算法描述工具 17
1.7 总结 17
1.8 习题 18
第一部分 线性表 21
第2章 线性表 21
2.1 线性表的基本概念 21
2.2 线性表的顺序实现 22
2.2.1 顺序表的存储实现 22
2.2.2 基本运算在顺序表上的实现 23
2.2.3 顺序实现的算法分析 26
2.3 线性表的链接实现 26
2.3.1 单链表 27
2.3.2 双链表 31
2.3.3 循环链表 32
2.4 线性表类的实现 33
2.4.1 线性表的抽象类 33
2.4.2 顺序表类的实现 35
2.4.3 双链表类的实现 37
2.5 STL中的线性表 41
2.5.1 容器和迭代器的概念 41
2.5.2 vector类和list类 42
2.5.3 vector类和list类的使用 44
2.5.4 双端队列-deque 47
2.6 线性表的应用：文本编辑系统 47
2.7 小结 48
2.8 习题 48
第3章 栈 51
3.1 栈的基本概念 51
3.2 栈的顺序实现 52
3.3 栈的链接实现 53
3.4 栈类的实现 54
3.4.1 栈的抽象类 54
3.4.2 顺序栈类的实现 54
3.4.3 链接栈类的实现 56
3.5 STL中的栈 57
3.6 栈的应用 59
3.6.1 递归消除 59
3.6.2 括号配对 62
3.6.3 简单的计算器 72
3.7 总结 82
3.8 习题 83
第4章 队列 84
4.1 队列的概念 84
4.2 队列的顺序实现 85
4.2.1 队头位置固定的顺序实现 85
4.2.2 队头位置不固定的顺序实现 86
4.2.3 循环队列 87
4.3 队列的链接实现 89
4.4 队列类的实现 90
4.4.1 队列的抽象类 90
4.4.2 循环队列类的实现 91
4.4.3 链接队列类的实现 93
4.5 STL中的队列 95
4.6 队列的应用：排队系统的模拟 96
4.7 总结 101
4.8 习题 101
第二部分 树形结构 105
第5章 树 105
5.1 树的概念 105
5.1.1 树的定义 105
5.1.2 树的基本术语 106
5.1.3 树的基本运算 107
5.2 二叉树 107
5.2.1 二叉树的基本概念 107
5.2.2 二叉树的主要性质 109
5.2.3 二叉树的基本运算和二叉树的遍历 111
5.2.4 二叉树的顺序实现 114
5.2.5 二叉树的链接实现 116
5.2.6 二叉树类的实现 118
5.2.7 二叉树遍历的非递归实现 126
5.3 二叉树的应用：计算表达式 129
5.4 哈夫曼树和哈夫曼编码 140
5.4.1 前缀编码 141
5.4.2 哈夫曼算法 143
5.4.3 哈夫曼树类的实现 146
5.5 树和森林 150
5.5.1 树的存储实现 150
5.5.2 树的遍历 152
5.5.3 树、林与二叉树的关系 153
5.6 总结 155
5.7 习题 155
第6章 优先级队列 158
6.1 基本的优先级队列 158
6.2 二叉堆 158
6.2.1 二叉堆的结构性 158
6.2.2 二叉堆的有序性 159
6.2.3 基于二叉堆的优先级队列的实现 160
6.3 D堆 168
6.4 归并优先级队列 169
6.4.1 左堆 169
6.4.2 斜堆 171
6.4.3 贝努里队列 172
6.5 STL中的优先级队列 176
6.6 多服务台排队系统的模拟 177
6.7 总结 182
6.8 习题 183
第三部分 集合 187
第7章 集合与静态查找表 187
7.1 集合的基本概念 187
7.2 查找的基本概念 187
7.3 静态表查找 188
7.4 无序表的查找 188
7.4.1 顺序查找 188
7.4.2 顺序查找的时间复杂度分析 189
7.5 有序表的查找 190
7.5.1 顺序查找 190
7.5.2 二分查找 190
7.5.3 插值查找 192
7.5.4 分块查找 192
7.6 静态查找表的实现 193
7.7 STL中的静态表 194
7.8 总结 196
7.9 习题 196
第8章 查找树 197
8.1 二叉查找树 197
8.1.1 二叉查找树的定义 197
8.1.2 二叉查找树的操作 198
8.1.3 二叉查找树的性能 203
8.1.4 二叉查找树类的实现 204
8.2 AVL树 209
8.2.1 AVL树的定义 209
8.2.2 AVL树的插入操作 211
8.2.3 AVL树的删除操作 217
8.2.4 AVL树类的实现 221
8.3 红黑树 227
8.3.1 红黑树的定义 227
8.3.2 红黑树的插入操作 228
8.3.3 红黑树的删除操作 234
8.3.4 红黑树类的实现 239
8.4 AA树 249
8.4.1 AA树的定义 249
8.4.2 AA树的插入操作 250
8.4.3 AA树的删除操作 253
8.4.4 AA树类的实现 256
8.5 伸展树 260
8.5.1 伸展树的定义 260
8.5.2 伸展操作的实现 262
8.6 B树和B＋树 265
8.6.1 B树 266
8.6.2 B＋树 267
8.7 STL中的查找表 273
8.7.1 set 273
8.7.2 map 274
8.8 总结 275
8.9 习题 276
第9章 散列表 278
9.1 基本概念 278
9.2 散列函数 279
9.3 碰撞的解决 281
9.3.1 线性探测法 281
9.3.2 二次探测法 283
9.3.3 再散列法 285
9.3.4 开散列表 285
9.4 散列表类的实现 286
9.4.1 散列表类的抽象类 286
9.4.2 闭散列表的实现 287
9.4.3 开散列表的实现 290
9.5 散列表类的应用 293
9.6 总结 295
9.7 习题 295
第10章 排序 297
10.1 引言 297
10.2 插入排序 298
10.2.1 直接插入排序 298
10.2.2 二分插入排序 300
10.2.3 希尔排序 300
10.2.4 希尔排序的性能 302
10.3 选择排序 302
10.3.1 直接选择排序 303
10.3.2 堆排序 304
10.4 交换排序 307
10.4.1 冒泡排序 307
10.4.2 快速排序 308
10.5 归并排序 314
10.6 外排序 317
10.6.1 外排序的基本过程 317
10.6.2 预处理阶段 317
10.6.3 归并阶段 319
10.7 总结 321
10.8 习题 321
第11章 不相交集 323
11.1 等价关系与等价类 323
11.2 不相交集 324
11.3 不相交集的实现 324
11.3.1 不相交集的存储实现 324
11.3.2 不相交集的运算实现 325
11.3.3 改进的union算法 325
11.3.4 改进的find算法 327
11.4 不相交集类的实现 327
11.5 不相交集的应用 329
11.5.1 生成迷宫 329
11.5.2 最近的共同祖先问题 331
11.6 总结 332
11.7 习题 332
第四部分 图 335
第12章 图的基本概念 335
12.1 图的定义 335
12.2 图的基本术语 336
12.3 图的基本运算 338
12.4 图的存储 339
12.4.1 邻接矩阵表示法 339
12.4.2 邻接表表示法 343
12.5 图的遍历 347
12.5.1 深度优先搜索DFS 348
12.5.2 广度优先搜索BFS 351
12.6 图的遍历的应用 353
12.6.1 无向图的连通性 353
12.6.2 欧拉回路 353
12.6.3 有向图的连通性 359
12.6.4 拓扑排序 360
12.7 总结 363
12.8 习题 364
第13章 最小生成树 366
13.1 生成树和最小生成树 366
13.2 Kruskal算法 367
13.3 Prim算法 370
13.4 算法的正确性 374
13.5 总结 375
13.6 习题 375
第14章 最短路径问题 376
14.1 单源最短路径 376
14.1.1 非加权图的最短路径 376
14.1.2 加权图的最短路径 382
14.1.3 带有负权值的图 387
14.1.4 无环图 388
14.2 所有顶点对的最短路径 390
14.3 总结 393
14.4 习题 393
第五部分 算法设计基础第15章 算法设计基础 397
15.1 枚举法 397
15.2 贪婪法 398
15.3 分治法 399
15.3.1 最大连续子序列和的问题 399
15.3.2 整型数的乘法问题 401
15.3.3 平面上的最近点问题 401
15.4 动态规划 402
15.4.1 硬币找零问题 404
15.4.2 最优二叉查找树 406
15.5 回溯法 409
15.6 随机算法 413
15.6.1 跳表 414
15.6.2 素数检测 416
15.7 总结 418
15.8 习题 418
参考文献 420