第1章 C＋＋面向对象程序设计 1
1.1 抽象数据类型 1
1.2 封装 1
目录 1
1.3 继承 5
1.4 指针 7
1.4.1 指针和数组 9
1.4.2 指针和复制构造函数 11
1.4.3 指针和析构函数 13
1.4.4 指针和引用变量 14
1.4.5 函数指针 16
1.5 多态性 17
1.6 C＋＋和面向对象程序设计 19
1.7.2 迭代器 20
1.7 标准模板库 20
1.7.1 容器 20
1.7.3 算法 21
1.7.4 函数对象 21
1.8 标准模板库中的向量 23
1.9 数据结构与面向对象编程 30
1.10 案例分析：随机访问文件 30
1.11 习题 39
1.12 程序设计作业 41
第2章 复杂度分析 44
2.1 计算复杂度和渐近复杂度 44
2.2 大O符号 45
2.3 大O符号的性质 47
2.4 Ω符号与？符号 48
2.5 可能的问题 49
2.6 复杂度举例 49
2.7 确定渐近复杂度举例 51
2.8 最好、平均和最坏情况 52
2.9 阻尼复杂度 55
2.10 NP完整性 58
2.11 习题 60
第3章 链表 64
3.1 单链表 64
3.1.1 插入 69
3.1.2 删除 71
3.1.3 查找 75
3.2 双链表 75
3.3 循环链表 79
3.4 跳跃链表 80
3.5 自组织链表 85
3.6 稀疏表 89
3.7 标准模板库中的链表 91
3.8 标准模板库中的双端队列 95
3.9 小结 99
3.10 案例分析：图书馆 100
3.11 习题 107
3.12 程序设计作业 109
第4章 栈与队列 113
4.1 栈 113
4.2 队列 119
4.3 优先队列 125
4.4 标准模板库中的栈 126
4.5 标准模板库中的队列 127
4.6 标准模板库中的优先队列 128
4.7 案例分析：迷宫问题 130
4.8 习题 135
4.9 程序设计作业 136
第5章 递归 139
5.1 递归定义 139
5.2 函数调用与递归实现 141
5.3 递归调用的剖析 143
5.4 尾部递归 145
5.5 非尾部递归 146
5.6 间接递归 151
5.8 不合理递归 153
5.7 嵌套递归 153
5.9 回溯 156
5.10 小结 162
5.11 案例分析：递归下降解释器 163
5.12 习题 169
5.13 程序设计作业 172
第6章 二叉树 175
6.1 树、二叉树和二叉搜索树 175
6.2 二叉树的实现 178
6.3 二叉搜索树的查找 181
6.4 树的遍历 183
6.4.1 广度优先遍历 183
6.4.2 深度优先遍历 184
6.4.3 不用栈实现的深度优先遍历 190
6.5 插入 195
6.6 删除 198
6.6.1 合并删除 198
6.6.2 通过复制进行删除 201
6.7 树的平衡 203
6.7.1 DSW算法 205
6.7.2 AVL树 207
6.8 自调整树 212
6.8.1 自重新构造树 212
6.8.2 “张开”策略 213
6.9 堆 217
6.9.1 将堆作为优先队列 219
6.9.2 将数组组织为堆 221
6.10 波兰记号和表达式树 224
6.11 案例分析：计算单词出现的频率 228
6.12 习题 234
6.13 程序设计作业 237
第7章 多叉树 243
7.1 B树家族 243
7.1.1 B树 244
7.1.2 B＊树 252
7.1.3 B＋树 253
7.1.4 前缀B＋树 255
7.1.5 位树 257
7.1.6 R树 258
7.1.7 2-4树 260
7.1.8 标准模板库中的集和多集 270
7.1.9 标准模板库中的映射和多映射 274
7.2 trie 278
7.4 案例分析：拼写检查器 285
7.3 小结 285
7.5 习题 293
7.6 程序设计作业 294
第8章 图 299
8.1 图的表示法 300
8.2 图的遍历 301
8.3 最短路径 304
8.4 环的检测 311
8.5 生成树 314
8.6 连通性 316
8.6.1 无向图中的连通性 316
8.6.2 有向图中的连通性 318
8.7 拓扑排序 320
8.8.1 最大流 321
8.8 网络 321
8.8.2 成本最低的最大流 329
8.9 匹配 332
8.9.1 稳定匹配问题 337
8.9.2 分配问题 339
8.9.3 非二分图中的匹配集合 341
8.10 欧拉（Eulerian）图与汉密尔顿（Hamiltonian）图 343
8.10.1 欧拉图 343
8.10.2 汉密尔顿图 345
8.11 给图加上颜色 350
8.12 图理论中的NP完整性问题 352
8.12.1 派系问题 352
8.12.2 三色问题 353
8.12.3 顶点覆盖问题 354
8.12.4 汉密尔顿环问题 355
8.13 案例分析：惟一代表 356
8.14 习题 365
8.15 程序设计作业 369
第9章 排序 374
9.1 基本的排序算法 375
9.1.1 插入排序 375
9.1.2 选择排序 377
9.1.3 冒泡排序 379
9.2 决策树 380
9.3 高效排序算法 383
9.3.1 希尔排序 383
9.3.2 堆排序 386
9.3.3 快速排序 389
9.3.4 归并排序 393
9.3.5 基数排序 396
9.4 标准模板库中的排序 400
9.5 小结 403
9.6 案例分析：多项式相加 403
9.7 习题 409
9.8 程序设计作业 411
第10章 散列 415
10.1 散列函数 415
10.1.1 除余法 416
10.1.2 折叠法 416
10.1.3 平方取中法 416
10.1.5 基数转换法 417
10.2 冲突解决方法 417
10.1.4 提取法 417
10.2.1 开放定址法 418
10.2.2 链接法 422
10.2.3 桶定址 424
10.3 删除 425
10.4 理想散列函数 426
10.4.1 Cichelli方法 426
10.4.2 FHCD算法 429
10.5 可扩展文件的散列函数 430
10.5.1 可扩展散列 431
10.5.2 线性散列 433
10.6 案例分析：使用桶的散列 435
10.7 习题 442
10.8 程序设计作业 443
第11章 数据压缩 446
11.1 数据压缩的条件 446
11.2 Huffman编码 447
11.3 Run-Length编码方式 458
11.4 Ziv-Lempel编码方式 459
11.5 案例分析：Huffman方法和Run-Length编码方式 462
11.6 习题 471
11.7 程序设计作业 471
第12章 内存管理 474
12.1 sequential-fit方法 475
12.2 Nonsequential-fit方法 475
12.3 无用单元回收 483
12.3.1 标记和清除 483
12.3.2 复制方法 489
12.3.3 递增的无用单元回收 490
12.4 小结 496
12.5 案例分析 496
12.6 习题 503
12.7 程序设计作业 504
第13章 字符串匹配 509
13.1 字符串的精确匹配 509
13.1.1 简单的算法 509
13.1.2 Knuth-Morris-Pratt算法 512
13.1.3 Boyer-Moore算法 518
13.1.4 多次搜索 527
13.1.5 面向位的方法 528
13.1.6 单词集合的匹配 532
13.1.7 正则表达式的匹配 537
13.1.8 后缀trie和树 540
13.1.9 后缀数组 545
13.2 字符串的模糊匹配 546
13.2.1 字符串的近似性 547
13.2.2 有k个错误的字符串匹配 552
13.3 案例分析：最长的共有子字符串 555
13.4 习题 561
13.5 程序设计作业 563
附录A 计算大O 566
A.1 调和数序列n 566
A.2 函数lg（N！）的近似值 566
A.3 快速排序中平均情况的大O 568
A.4 随机二叉树中的平均路径长度 569
A.5 AVL树中的节点数 570
附录B 标准模板库中的算法 572
附录C NP完整性 581