第1章 算法与数据结构引论 1
1.1 算法及其复杂性的概念 1
1.1.1 算法与程序 1
1.1.2 算法复杂性的概念 1
1.1.3 算法复杂性的渐近性态 2
1.2 数据结构与抽象数据类型 3
1.3 用C++描述数据结构与算法 4
1.3.1 指针和引用 4
1.3.2 函数与参数传递 4
1.3.3 C++的类 5
1.3.4 类的对象 6
1.3.5 模板 6
1.3.6 动态存储分配 7
1.4 递归 8
1.5 标准模板库STL与泛型算法 9
1.5.1 STL概述 9
1.5.2 容器 10
1.5.3 迭代器 10
1.5.4 泛型算法 11
1.5.5 函数对象 14
1.6 应用举例 19
1.6.1 用C++的类实现抽象数据类型 19
1.6.2 顺序搜索与二分搜索算法的设计与分析 23
1.6.3 递归算法的设计与分析 25
习题1 26
数据结构与算法实验1 27
数据结构与算法实验题1.1 实系数复变多项式问题 27
数据结构与算法实验题1.2 平面几何问题 28
数据结构与算法实验题1.3 m进制数问题 29
第2章 向量 30
2.1 向量的基本概念 30
2.2 抽象数据类型向量 30
2.3 向量的迭代器 30
2.4 向量的实现方法 31
2.5 矩阵与多维向量 35
2.6 高精度整数 36
2.7 应用举例 47
2.7.1 搜索公共元素问题 47
2.7.2 同色方块识别问题 48
2.7.3 全排列问题 49
习题2 49
数据结构与算法实验2 50
数据结构与算法实验题2.1 前缀与后缀和问题 50
数据结构与算法实验题2.2 投票选举问题 50
数据结构与算法实验题2.3 稳定婚姻问题 51
数据结构与算法实验题2.4 凸多边形的三角剖分问题 52
第3章 双端队列 53
3.1 双端队列的基本概念 53
3.2 抽象数据类型双端队列 53
3.3 双端队列的实现方法 54
3.4 双端队列的迭代器 60
3.5 应用举例 62
3.5.1 双端队列的简单应用 62
3.5.2 简单多边形的凸壳问题 63
习题3 65
数据结构与算法实验3 65
数据结构与算法实验题3.1 排队购票问题 65
数据结构与算法实验题3.2 循环向量的极值问题 66
第4章 线性表 68
4.1 表的基本概念 68
4.2 用数组实现表 69
4.3 用指针实现表 73
4.3.1 用指针实现单链表的方法 73
4.3.2 单链表的迭代器 75
4.4 用间接寻址方法实现表 79
4.4.1 间接寻址方法的基本思想 79
4.4.2 间接寻址表的迭代器 82
4.5 用游标实现表 84
4.5.1 用游标实现表的基本思想 84
4.5.2 游标实现的表的迭代器 89
4.6 循环链表 90
4.6.1 实现单循环链表的基本思想 90
4.6.2 单循环链表的迭代器 92
4.7 双链表 94
4.7.1 实现双向循环链表的基本思想 94
4.7.2 双向循环链表的迭代器 97
4.8 应用举例 101
4.8.1 多项式函数 101
4.8.2 Josephus排列问题 106
习题4 107
数据结构与算法实验4 108
数据结构与算法实验题4.1 实系数一元多项式问题 108
数据结构与算法实验题4.2 Josephus排列问题1 109
数据结构与算法实验题4.3 向量分类问题 110
数据结构与算法实验题4.4 条形图轮廓问题 110
数据结构与算法实验题4.5 Josephus排列问题2 111
第5章 栈 113
5.1 栈的基本概念 113
5.2 栈的实现方法 114
5.3 应用举例 115
5.3.1 等价类划分问题 115
5.3.2 模拟递归问题 117
5.3.3 电路板布线问题 119
习题5 121
数据结构与算法实验5 121
数据结构与算法实验题5.1 车皮编序问题 121
数据结构与算法实验题5.2 单柱Hanoi塔问题 122
数据结构与算法实验题5.3 多栈模拟问题 123
数据结构与算法实验题5.4 亲兄弟问题 124
第6章 队列 125
6.1 队列的基本概念 125
6.2 队列的实现方法 125
6.3 应用举例 126
6.3.1 最优电路布线问题 126
6.3.2 和谐短信问题 129
习题6 130
数据结构与算法实验6 130
数据结构与算法实验题6.1 组队列问题 130
数据结构与算法实验题6.2 双栈队列问题 131
数据结构与算法实验题6.3 猴子分桃问题 132
数据结构与算法实验题6.4 逆序表问题 132
第7章 排序与选择 134
7.1 简单排序算法 134
7.1.1 冒泡排序算法 134
7.1.2 插入排序算法 135
7.1.3 选择排序算法 136
7.1.4 简单排序算法的计算复杂性 136
7.2 快速排序算法 137
7.2.1 算法基本思想及实现 137
7.2.2 算法性能分析 139
7.2.3 随机快速排序算法 139
7.3 合并排序算法 140
7.3.1 算法基本思想及实现 140
7.3.2 消除递归 141
7.3.3 自然合并排序算法 141
7.4 链表排序与索引排序算法 142
7.4.1 链表排序算法 142
7.4.2 索引排序算法 149
7.5 线性时间排序算法 151
7.5.1 计数排序算法 151
7.5.2 桶排序算法 152
7.6 中位数与第k小元素 152
7.6.1 平均情况下的线性时间选择算法 153
7.6.2 最坏情况下的线性时间选择算法 154
7.7 泛型排序算法 156
7.7.1 排序算法的泛化方法 156
7.7.2 泛型合并排序算法 158
7.7.3 泛型快速排序算法 159
7.7.4 泛型选择算法 160
7.8 应用举例 161
7.8.1 区间覆盖问题 161
7.8.2 输油管道问题 161
习题7 162
数据结构与算法实验7 163
数据结构与算法实验题7.1 交换排序问题 163
数据结构与算法实验题7.2 DNA排序问题 163
数据结构与算法实验题7.3 邮局选址问题 164
数据结构与算法实验题7.4 最优服务次序问题 165
第8章 树 166
8.1 树的定义 166
8.2 树的遍历 168
8.3 树的表示法 170
8.3.1 父结点数组表示法 170
8.3.2 儿子链表表示法 170
8.3.3 左儿子右兄弟表示法 171
8.4 二叉树的基本概念 171
8.5 二叉树的运算 173
8.6 二叉树的实现 174
8.6.1 二叉树的顺序存储结构 174
8.6.2 二叉树的结点度表示法 175
8.6.3 用指针实现二叉树 176
8.7 线索二叉树 179
8.8 应用举例——信号增强装置布局问题 181
习题8 184
数据结构与算法实验8 185
数据结构与算法实验题8.1 层序列表问题 185
数据结构与算法实验题8.2 最近公共祖先问题 186
数据结构与算法实验题8.3 子树问题 187
数据结构与算法实验题8.4 同构二叉树问题 187
数据结构与算法实验题8.5 后序中序遍历问题 188
第9章 二叉搜索树 189
9.1 有序集与二叉搜索树 189
9.1.1 抽象数据类型字典 189
9.1.2 用数组实现字典 189
9.1.3 二叉搜索树的基本概念 190
9.2 实现二叉搜索树 190
9.3 二叉搜索树的迭代器 199
9.4 二叉搜索树的效率 205
9.5 应用举例——条形图统计问题 207
习题9 209
数据结构与算法实验9 209
数据结构与算法实验题9.1 装箱问题 209
数据结构与算法实验题9.2 电路板连线问题 210
数据结构与算法实验题9.3 字典问题 211
第10章 平衡搜索树 212
10.1 红黑树 212
10.1.1 红黑树的定义和性质 212
10.1.2 旋转变换 213
10.1.3 红黑树的插入运算与重平衡 216
10.1.4 红黑树的删除运算与重平衡 218
10.2 AVL树 223
10.2.1 AVL树的定义和性质 223
10.2.2 AVL树的插入运算与重平衡 224
10.2.3 AVL树的删除运算与重平衡 226
10.3 应用举例 229
10.3.1 条形图统计问题 229
10.3.2 动态选择问题 230
10.3.3 Josephus排列问题 232
习题10 233
数据结构与算法实验10 234
数据结构与算法实验题10.1 逆序计数问题 234
数据结构与算法实验题10.2 k后继问题 234
数据结构与算法实验题10.3 圆内相交弦问题 235
数据结构与算法实验题10.4 最小间隙问题 236
数据结构与算法实验题10.5 图形周长问题 237
数据结构与算法实验题10.6 动态选择问题 237
第11章 集合 239
11.1 集合的基本概念 239
11.2 用位向量实现集合 240
11.3 用平衡二叉搜索树实现集合 246
11.3.1 直接应用红黑树实现集合 246
11.3.2 平衡二叉搜索树的泛化 247
11.3.3 符合STL标准的集合 252
11.4 多重集合 254
11.5 泛型集合运算 256
11.6 应用举例 259
11.6.1 Eratosthenes筛法 259
11.6.2 子集和问题 260
11.6.3 拼写检查问题 260
11.6.4 软件产品数据库问题 261
习题11 262
数据结构与算法实验11 263
数据结构与算法实验题11.1 半数集问题 263
数据结构与算法实验题11.2 账单支付问题 263
数据结构与算法实验题11.3 张贴海报问题 264
数据结构与算法实验题11.4 三色棋游戏问题 265
第12章 映射 266
12.1 映射的基本概念 266
12.2 用平衡二叉搜索树实现映射 266
12.2.1 二叉搜索树的进一步泛化 266
12.2.2 符合STL标准的映射 272
12.3 多重映射 274
12.4 应用举例 275
12.4.1 种群分布统计问题 275
12.4.2 电子字典问题 276
习题12 278
数据结构与算法实验12 278
数据结构与算法实验题12.1 工作薪酬问题 278
数据结构与算法实验题12.2 扑克游戏智能分析问题 279
数据结构与算法实验题12.3 最优行驶路线问题 280
数据结构与算法实验题12.4 库存调整问题 281
数据结构与算法实验题12.5 双字符字频分析问题 282
数据结构与算法实验题12.6 英文词汇分析问题 283
第13章 散列 285
13.1 符号表 285
13.2 开散列 286
13.3 闭散列 292
13.4 散列函数的效率 297
13.5 重新散列 298
13.6 散列集 299
13.6.1 用散列表实现集合 299
13.6.2 用散列表实现多重集合 300
13.7 散列映射 301
13.7.1 开散列表的泛化 301
13.7.2 用散列表实现映射 307
13.7.3 用散列表实现多重映射 308
13.8 应用举例 309
13.8.1 字符串频率统计问题 309
13.8.2 拼写检查问题 310
13.8.3 种群分布统计问题 311
13.8.4 电子字典问题 312
习题13 313
数据结构与算法实验13 313
数据结构与算法实验题13.1 伪随机排列问题 313
数据结构与算法实验题13.2 字符串散列问题 314
数据结构与算法实验题13.3 英文文本分析问题 314
数据结构与算法实验题13.4 最长模式串问题 315
第14章 堆与优先队列 316
14.1 优先队列的基本概念 316
14.2 优先级树和堆 316
14.3 堆的顺序存储方式 317
14.4 堆的有关算法 318
14.5 堆的泛型算法 323
14.6 用堆实现优先队列 326
14.7 可并优先队列 327
14.7.1 左偏树的定义 327
14.7.2 用左偏树实现可并优先队列 328
14.7.3 泛化左偏树 331
14.8 应用举例 332
14.8.1 优先队列的比较模式 332
14.8.2 哈夫曼编码问题 334
14.8.3 活动安排问题 337
习题14 338
数据结构与算法实验14 338
数据结构与算法实验题14.1 区间相交问题 338
数据结构与算法实验题14.2 整数字典问题 338
数据结构与算法实验题14.3 最小权语言问题 339
数据结构与算法实验题14.4 二叉搜索堆问题 339
数据结构与算法实验题14.5 区间覆盖问题 340
数据结构与算法实验题14.6 批作业调度问题 341
第15章 并查集 342
15.1 并查集的基本概念 342
15.2 用父结点向量实现并查集 343
15.3 应用举例——离线最小值问题 346
习题15 347
数据结构与算法实验15 348
数据结构与算法实验题15.1 二进制方程问题 348
数据结构与算法实验题15.2 网络连通问题 349
数据结构与算法实验题15.3 朋友问题 349
数据结构与算法实验题15.4 等价类划分问题 350
第16章 图 352
16.1 图的基本概念 352
16.2 抽象数据类型图 355
16.3 图的表示法 355
16.3.1 邻接矩阵表示法 355
16.3.2 邻接表表示法 356
16.3.3 紧缩邻接表 356
16.4 用邻接矩阵实现图 357
16.4.1 用邻接矩阵实现图的方法 357
16.4.2 邻接矩阵图的顶点迭代器 359
16.5 用邻接表实现图 360
16.5.1 用邻接表实现图的方法 360
16.5.2 邻接表图的顶点迭代器 362
16.6 用邻接矩阵实现赋权图 362
16.6.1 用邻接矩阵实现赋权图的方法 362
16.6.2 邻接矩阵赋权图的顶点迭代器 365
16.7 用邻接表实现赋权图 365
16.7.1 用邻接表实现赋权图的方法 365
16.7.2 邻接表赋权图的顶点迭代器 368
16.8 图的遍历搜索算法 369
16.8.1 广度优先搜索 369
16.8.2 深度优先搜索 370
16.9 最短路径算法 371
16.9.1 单源最短路算法 371
16.9.2 Bellman-Ford最短路算法 374
16.9.3 所有顶点对之间的最短路算法 375
16.10 无圈有向图DAG 376
16.10.1 拓扑排序 376
16.10.2 DAG的最短路径 378
16.10.3 DAG的最长路径 379
16.10.4 DAG所有顶点对之间的最短路径 379
16.11 最小支撑树 380
16.11.1 最小支撑树的性质 380
16.11.2 最小支撑树的Prim算法 380
16.11.3 最小支撑树的Kruskal算法 382
16.12 图匹配算法 383
16.13 应用举例 386
16.13.1 最长嵌套序列问题 386
16.13.2 套汇问题 388
习题16 388
数据结构与算法实验16 390
数据结构与算法实验题16.1 图的二着色问题 390
数据结构与算法实验题16.2 有向赋权图中心问题 390
数据结构与算法实验题16.3 最长简单路径问题 391
数据结构与算法实验题16.4 计算机网络问题 392
数据结构与算法实验题16.5 差分约束问题 393
数据结构与算法实验题16.6 有截止时间的工作排序问题 393
数据结构与算法实验题16.7 无向图的连通分支问题 394
参考文献 396