第1章 概要 1
1.1 本书的主要内容 1
1.2 面向对象的设计 1
1.3 对象分级与设计方法 2
1.4 需要了解的C＋＋特性 3
1.5 本书是如何组织的？ 4
第2章 算法分析 5
2.1.1 基本公理 6
2.1 一个细化的计算机模型 6
2.1.2 例1：算术级数求和 8
2.1.3 数组下标操作 8
2.1.4 例2：霍纳（Horner）法则 9
2.1.5 分析递归函数 10
2.1.6 例3：找出数组中最大元素 11
2.1.7 平均运行时间 13
2.1.8 关于调和数 13
2.1.9 最佳情况与最差情况的运行时间 15
2.1.10 最后的公理 16
2.2.1 例1：求几何级数之和 17
2.2 一个简化的计算机模型 17
2.2.2 关于算术级数求和 18
2.2.3 例2：再次求几何级数之和 19
2.2.4 关于几何级数求和 20
2.2.5 例3：幂计算 20
2.2.6 例4：再三求几何级数之和 23
习题 24
设计项目 25
3.1 渐近上界——大O表示法 26
3.1.1 一个简单的例子 26
第3章 渐近表示法 26
3.1.2 大O表示法中的错误与陷阱 27
3.1.3 大O的特性 28
3.1.4 多项式 30
3.1.5 对数 31
3.1.6 紧凑大O界 32
3.1.7 大O表示法中更多的错误与陷阱 33
3.1.8 常用的大O表达式 34
3.2 渐近下界——Ω表示法 34
3.2.1 一个简单的例子 35
3.2.2 再次关于多项式 35
3.4 算法渐近分析 37
3.3 更多的表示法——Θ及小o表示法 37
3.4.1 运行时间分析的大O规则 38
3.4.2 例1：求级数的前项和 39
3.4.3 例2：Fibonacci数 41
3.4.4 例3：桶式排序 44
3.4.5 现实检查 45
3.4.6 检查你的分析 46
习题 47
设计项目 49
4.1 动态数组 50
第4章 基本数据结构 50
4.1.1 缺省构造函数 52
4.1.2 数组构造函数 52
4.1.3 备份构造函数 52
4.1.4 析构函数 53
4.1.5 数组成员函数 54
4.1.6 数组下标操作符 54
4.1.7 数组大小的重调 55
4.2 单链表 55
4.2.1 链表的实现 57
4.2.3 缺省构造函数 59
4.2.2 链表元素 59
4.2.4 析构函数与Purge成员函数 60
4.2.5 存取器 60
4.2.6 First与Last函数 61
4.2.7 前插 61
4.2.8 添加 62
4.2.9 备份构造函数与赋值操作符 62
4.2.10 析取函数 63
4.2.11 InsertAfter与InsertBefore函数 64
4.3.1 数组下标计算 66
4.3 多维数组 66
4.3.2 二维数组的实现 67
4.3.3 C＋＋中多维数组的下标 68
4.3.4 例：规范矩阵相乘 69
习题 71
设计项目 72
第5章 数据类型与抽象 73
5.1 抽象数据类型 73
5.2 设计模式 74
5.2.1 类层次 74
5.2.2 对象 74
5.2.3 NullObject单元集类 78
5.2.4 内嵌类型的对象包装 79
5.2.5 容器 81
5.2.6 访问者 82
5.2.7 迭代器 85
5.2.8 NullIterator类 87
5.2.9 直接存储与间接存储 88
5.2.10 被包含对象的所有权 89
5.2.11 关联 90
5.2.12 可搜索容器 93
习题 94
设计项目 95
第6章 栈、队列及双端队列 97
6.1 栈 97
6.1.1 栈的数组表示法 98
6.1.2 栈的链表表示法 103
6.1.3 应用 107
6.2 队列 110
6.2.1 队列的数组表示法 110
6.2.2 队列的链表表示法 113
6.2.3 应用 115
6.3 双端队列 117
6.3.1 双端队列的数组表示法 119
6.3.2 双端队列的链表表示法 121
6.3.3 双向链表及循环链表 122
习题 123
设计项目 124
第7章 有序线性表与排序表 127
7.1 有序线性表 127
7.1.1 有序线性表的数组表示法 128
7.1.2 有序线性表的链表表示法 136
7.1.3 比较ListAsArray和ListAsLinkedList 141
7.1.4 应用 142
7.2 排序表 145
7.2.1 排序表的数组表示法 146
7.2.2 排序表的链表表示法 149
7.2.3 比较SortedListAsArray和SortedListAsLinkedList 150
7.2.4 应用 151
习题 154
设计项目 155
第8章 散列、哈希表及分散表 156
8.1 散列的基本知识 156
8.1.1 关键字和散列函数 157
8.2 散列法 158
8.2.1 相除散列法 158
8.2.2 平方取中散列法 159
8.2.3 相乘散列法 160
8.2.4 Fibonacci散列法 161
8.3 散列函数的实现 162
8.3.1 整型关键字 163
8.3.2 浮点型关键字 163
8.3.3 字符串关键字 164
8.3.4 散列对象 167
8.3.5 散列容器 168
8.3.6 使用关联 168
8.4 哈希表 169
8.4.1 拉链法 170
8.4.2 平均情况分析 173
8.5 分散表 174
8.5.1 链式分散表 174
8.5.2 平均情况分析 181
8.6 使用开地址法的分散表 181
8.6.1 线性探查 182
8.6.2 二次探查 183
8.6.4 开地址法的实现 184
8.6.3 双散列法 184
8.6.5 平均情况分析 191
8.7 应用 192
习题 194
设计项目 195
第9章 树 197
9.1 基础 197
9.2 N叉树 200
9.4 树的遍历 203
9.3 二叉树 203
9.5 表达式树 205
9.6 树的实现 207
9.6.1 树的遍历 208
9.6.2 树迭代器 212
9.6.3 广义树 215
9.6.4 N叉树 218
9.6.5 二叉树 223
9.6.6 二叉树的遍历 225
9.6.7 树的比较 226
9.6.8 应用 227
习题 230
设计项目 231
第10章 查找树 233
10.1 基础知识 233
10.1.1 M路查找树 233
10.1.2 二叉查找树 233
10.2 搜索查找树 234
10.2.1 搜索M路查找树 234
10.2.2 搜索二叉树 235
10.3.1 搜索成功 236
10.3 平均情况分析 236
10.3.2 递归关系的求解——拓展递归法 237
10.3.3 搜索失败 238
10.3.4 查找树的遍历 239
10.4 查找树的实现 240
10.4.1 二叉查找树 241
10.4.2 在二叉查找树中插入数据项 243
10.4.3 从二叉查找树中删除数据项 244
10.5 AVL查找树 246
10.5.1 AVL树的实现 248
10.5.2 在AVL树中插入数据项 250
10.5.3 从AVL树中删除数据项 255
10.6 M路查找树 255
10.6.1 M路查找树的实现 256
10.6.2 在M路查找树中查找数据项 258
10.6.3 在M路查找树中插入数据项 260
10.6.4 从M路查找树中删除数据项 261
10.7 B树 263
10.7.1 B树的实现 264
10.7.2 在B树中插入数据项 265
10.7.3 从B树中删除数据项 270
10.8 应用 271
习题 273
设计项目 274
第11章 堆和优先队列 275
11.1 基础知识 275
11.2 二叉堆 277
11.2.1 完全树 277
11.2.2 二叉堆的实现 280
11.2.3 在二叉堆中插入数据项 281
11.2.4 从二叉堆中删除数据项 283
11.3 左翼堆 284
11.3.1 左翼树 285
11.3.2 左翼堆的实现 286
11.3.3 左翼堆的合并 287
11.3.4 在左翼堆中插入数据项 288
11.3.5 从左翼堆中删除数据项 289
11.4 二项队列 290
11.4.1 二项树 290
11.4.2 二项队列 293
11.4.3 实现 294
11.4.4 二项队列的合并 297
11.4.5 在二项队列中插入数据项 299
11.4.6 从二项队列中删除数据项 300
11.5 应用 301
11.5.1 离散事件模拟 301
11.5.2 实现 302
习题 304
设计项目 306
第12章 集合、多重集和分区 307
12.1 基础知识 308
12.1.1 集合的实现 308
12.2 数组和位矢量集合 309
12.2.1 位矢量集合 312
12.3 多重集 315
12.3.1 多重集的数组表示法 315
12.3.2 多重集的链表表示法 318
12.4 分区 320
12.4.1 用森林表示分区 322
12.4.2 折叠查找 326
12.4.3 按大小合并 328
12.4.4 按高度或层号合并 329
12.5 应用 330
习题 332
设计项目 333
第13章 动态存储分配：另一种堆 334
13.1 基础 334
13.1.1 C++ Magic 335
13.1.2 堆 338
13.2 单链自由存储器 339
13.2.1 实现 339
13.3 双链自由存储器 345
13.3.1 实现 346
13.4 伙伴存储管理系统 351
13.4.1 实现 353
13.5 应用 358
13.5.1 实现 359
习题 360
设计项目 361
第14章 算法模式和问题求解 363
14.1 蛮干算法和贪心算法 363
14.1.1 例1：数钱 363
14.1.2 例2：0/1背包问题 364
14.2.1 例1：平衡称 366
14.2 回溯算法 366
14.2.2 解空间的表示 367
14.2.3 抽象回溯求解程序 368
14.2.4 分支界限求解程序 371
14.2.5 例2：再次分析0/1背包问题 372
14.3 自顶向下算法：分治算法 373
14.3.1 例1：二分法查找 373
14.3.2 例2：求解Fibonacci数 374
14.3.3 例3：归并排序 376
14.3.4 分治算法的运行时间 377
14.3.5 例4：矩阵相乘 379
14.4 自底向上算法：动态程序设计 381
14.4.1 例1：广义Fibonacci数 381
14.4.2 例2：求解二项式系数 382
14.4.3 应用：排版问题 384
14.5 随机化算法 387
14.5.1 产生随机数 387
14.5.2 随机变量 390
14.5.3 蒙特卡罗法 392
14.5.4 模拟退火法 394
习题 395
设计项目 396
第15章 排序算法和排序器 398
15.1 基础知识 398
15.2 排序和排序器 398
15.3 插入排序 401
15.3.1 直接插入排序 402
15.3.2 平均运行时间 402
15.3.3 二分法插入排序 403
15.4 交换排序 405
15.4.1 冒泡排序 405
15.4.2 快速排序 406
15.4.3 运行时间分析 410
15.4.4 平均运行时间 411
15.4.5 轴值的选择 413
15.5 选择排序 414
15.5.1 直接选择排序 414
15.5.2 堆排序 416
15.5.3 堆的建立 418
15.6 归并排序 421
15.7 排序算法的下界 425
15.8.1 桶式排序 426
15.8 分配排序 426
15.8.2 基数排序 428
15.9 算法性能分析 431
习题 433
设计项目 435
第16章 图和图算法 436
16.1 基础知道 437
16.1.1 图的表示法 440
16.2 图的实现 443
16.2.1 顶点的实现 443
16.2.3 抽象图和有向图 444
16.2.4 无向图的实现 447
16.2.5 边带权图和顶点带权图 448
16.2.6 图表示法的比较 449
16.3 图的遍历 451
16.3.1 深度优先遍历 451
16.3.2 广度优先遍历 453
16.3.3 拓扑排序 455
16.3.4 图遍历的应用：检查图的回路及连通性 458
16.4 最短路径算法 462
16.4.1 单源最短路径 462
16.4.2 每对顶点间的最短路径 467
16.5 最小支撑树 470
16.5.1 Prim算法 472
16.5.2 Kruskal算法 474
16.6 应用：关键路径分析 477
习题 482
设计项目 484
附录A C＋＋与面向对象编程 485
附录B 类层次图 505
附录C 字符码 506
参考答案 507