第1章 软件开发阶段 1
1.1 规范说明、设计和实现 2
1.1.1 概念设计：问题分解 3
1.1.2 前置条件和后置条件 4
1.1.3 使用其他程序员提供的函数 6
1.1.4 有关ANSI/ISOC＋＋标准的实现问题 7
1.1.5 自测习题 12
1.2 运行时间分析 13
1.2.1 台阶计数问题 13
1.2.2 大O表示法 17
1.2.3 C＋＋函数的时间分析 18
1.2.4 最坏情况、平均情况和最好情况下的时间分析 20
1.2.5 自测习题 20
1.3 测试和调试 21
1.3.1 选择测试数据 21
1.3.2 边界值 22
1.3.3 完全代码测试 22
1.3.4 调试 23
1.3.5 自测习题 23
1.4 本章小结 24
1.5 自测习题答案 24
第2章 抽象数据类型和C＋＋类 27
2.1 类和成员 28
2.1.1 编程示例：节流阀类 28
2.1.2 使用类 31
2.1.3 节流阀类的示范程序 33
2.1.4 实现成员函数 34
2.1.5 自测习题 37
2.2 构造函数 37
2.2.1 节流阀类的构造函数 38
2.2.2 修改节流阀类的成员函数 40
2.2.3 内联成员函数 41
2.2.4 自测习题 42
2.3 使用命名空间、头文件和实现文件 42
2.3.1 创建命名空间 42
2.3.2 头文件 43
2.3.3 实现文件 47
2.3.4 使用命名空间中的数据项 49
2.3.5 自测习题 51
2.4 类和参数 52
2.4.1 编程示例：point类 52
2.4.2 默认参数 55
2.4.3 参数 57
2.4.4 当函数返回值的类型是类时 62
2.4.5 自测习题 63
2.5 操作符重载 64
2.5.1 重载二元比较操作符 64
2.5.2 重载二元算术操作符 65
2.5.3 重载输出和输入操作符 66
2.5.4 友元函数 69
2.5.5 Point类——内容汇总 70
2.5.6 操作符重载的总结 72
2.5.7 自测习题 73
2.6 本章小结 73
2.7 自测习题答案 74
2.8 编程项目 77
第3章 容器类 85
3.1 包类 85
3.1.1 包类——规范说明 86
3.1.2 包类——文档说明 92
3.1.3 包类——示范程序 93
3.1.4 包类——设计 95
3.1.5 类的不变式 96
3.1.6 包类——实现 97
3.1.7 包类——内容汇总 103
3.1.8 包类——测试 106
3.1.9 包类——分析 107
3.1.10 自测习题 108
3.2 编程项目：序列类 109
3.2.1 序列类——规范说明 109
3.2.2 序列类——文档说明 112
3.2.3 序列类——设计 114
3.2.4 序列类——实现的伪代码 115
3.2.5 自测习题 117
3.3 交互式测试程序 117
3.4 本章小结 122
3.5 自测习题答案 123
3.6 编程项目 125
第4章 指针和动态数组 131
4.1 指针和动态内存 131
4.1.1 指针变量 132
4.1.2 使用指针的赋值操作符 134
4.1.3 动态变量和new操作符 135
4.1.4 使用new分配动态数组 136
4.1.5 堆和bad_alloc异常 138
4.1.6 操作符delete 139
4.1.7 自测习题 140
4.2 指针和数组作为参数 141
4.2.1 指针作为值参数 141
4.2.2 数组参数 143
4.2.3 指针或数组作为常量参数 144
4.2.4 指针作为引用参数 145
4.2.5 自测习题 147
4.3 用动态数组实现的包类 149
4.3.1 指针成员变量 150
4.3.2 成员函数按需分配动态内存 151
4.3.3 值语义 154
4.3.4 析构函数 156
4.3.5 修改后的包类——类定义 157
4.3.6 修改后的包类——实现 159
4.3.7 修改后的包类——内容汇总 163
4.3.8 自测习题 165
4.4 有关动态类的规定 166
4.4.1 4条规则 166
4.4.2 复制构造函数的特殊重要性 166
4.4.3 自测习题 167
4.5 编程项目：字符串类 167
4.5.1 以null终结的字符串 167
4.5.2 初始化字符串变量 168
4.5.3 空字符串 168
4.5.4 读写字符串变量 169
4.5.5 函数strcpy 169
4.5.6 函数strcat 170
4.5.7 函数strlen 170
4.5.8 函数strcmp 171
4.5.9 字符串类——规范说明 171
4.5.10 字符串类——设计 175
4.5.11 字符串类——实现 175
4.5.12 字符串类的示范程序 177
4.5.13 串接输出操作符 178
4.5.14 声明常量对象 179
4.5.15 产生构造函数的转换 179
4.5.16 在表达式中使用重载的操作符 180
4.5.17 本文的字符串类与C＋＋库中的字符串类 180
4.5.18 自测习题 180
4.6 编程项目：多项式 180
4.7 本章小结 184
4.8 自测习题答案 184
4.9 编程项目 186
第5章 链表 189
5.1 链表的基本节点类 189
5.1.1 为节点声明类 190
5.1.2 在链表节点中使用typedef语句 191
5.1.3 头指针和尾指针 191
5.1.4 空指针 192
5.1.5 头指针或尾指针为NULL时的含义 193
5.1.6 节点构造函数 193
5.1.7 节点成员函数 194
5.1.8 成员选择操作符 195
5.1.9 自测习题 198
5.2 链表工具包 199
5.2.1 链表工具包——头文件 199
5.2.2 计算链表的长度 200
5.2.3 链表的参数 203
5.2.4 在链表头插入一个新节点 204
5.2.5 在非头节点处插入一个新节点 206
5.2.6 在链表中查找数据项 210
5.2.7 在链表中根据节点的位置寻找节点 211
5.2.8 复制链表 212
5.2.9 从链表头删除节点 215
5.2.10 删除链表中不在头部的节点 216
5.2.11 清除链表 217
5.2.12 链表工具包——内容汇总 218
5.2.13 使用链表工具包 222
5.2.14 自测习题 222
5.3 用链表实现的包类 223
5.3.1 第三个包——规范说明 223
5.3.2 第三个包——类定义 223
5.3.3 如何匹配包的value_type和节点的value_type 226
5.3.4 在类中使用动态内存应当遵循的规则 227
5.3.5 第三个包类——实现 227
5.3.6 第三个包类——内容汇总 234
5.3.7 自测习题 236
5.4 编程项目：用链表实现的序列类 237
5.4.1 修改的序列类——设计建议 237
5.4.2 修改后的序列类——值语义 238
5.4.3 自测习题 239
5.5 动态数组、链表和双向链表 239
5.5.1 做出抉择 241
5.5.2 自测习题 241
5.6 本章小结 241
5.7 自测习题答案 242
5.8 编程项目 246
第6章 利用模板、迭代器和STL进行软件开发 251
6.1 模板函数 251
6.1.1 模板函数的语法 253
6.1.2 使用模板函数 253
6.1.3 模板函数——交换两个值 255
6.1.4 模板函数的参数匹配 256
6.1.5 模板函数——在数组中寻找最大项 257
6.1.6 模板函数——在排序数组中插入一个数据项 258
6.1.7 自测习题 260
6.2 模板类 260
6.2.1 模板类的语法 260
6.2.2 关于模板实现文件的其他内容 262
6.2.3 模板类成员函数的参数匹配 267
6.2.4 使用模板类 267
6.2.5 编故事程序的细节 270
6.2.6 自测习题 270
6.3 标准模板类及其迭代器 271
6.3.1 多集模板类 271
6.3.2 多集成员 272
6.3.3 迭代器和［...）模式 272
6.3.4 测试迭代器的等同性 274
6.3.5 其他多集操作 274
6.3.6 集合算法 275
6.3.7 无效的迭代器 276
6.3.8 迭代器的标准类别 277
6.3.9 数组的迭代器 278
6.3.10 标准模板库列表类 279
6.3.11 自测习题 280
6.4 节点模板类 280
6.4.1 返回引用类型的函数 281
6.4.2 将引用返回值复制到别处时发生的情况 283
6.4.3 成员函数data目前需要两个版本 283
6.4.4 新节点的头文件和实现文件 283
6.4.5 自测习题 290
6.5 链表的迭代器 291
6.5.1 节点迭代器 291
6.5.2 节点迭代器源自std∷iterator 293
6.5.3 节点迭代器的私有成员变量 293
6.5.4 节点迭代器——构造函数 293
6.5.5 节点迭代器——＊操作符 293
6.5.6 节点迭代器——操作符＋＋的两个版本 294
6.5.7 节点迭代器——相等和不相等的比较 295
6.5.8 常量集合的迭代器 296
6.5.9 自测习题 297
6.6 含有迭代器的包模板类的链表版本 298
6.6.1 如何为容器类提供迭代器 298
6.6.2 包迭代器 299
6.6.3 将迭代器定义在包中的原因 299
6.6.4 自测习题 306
6.7 本章小结和5个包的总结 306
6.8 自测习题答案 307
6.9 编程项目 311
第7章 堆栈 313
7.1 堆栈和STL堆栈的简介 313
7.1.1 标准库的堆栈类 315
7.1.2 编程示例：翻转单词 316
7.1.3 自测习题 316
7.2 堆栈的应用 317
7.2.1 编程示例：括号的平衡 317
7.2.2 编程示例：算术表达式求值 319
7.2.3 算术表达式求值——规范说明 319
7.2.4 算术表达式求值——设计 319
7.2.5 算术表达式求值——实现 325
7.2.6 计算器程序使用的函数 325
7.2.7 算术表达式求值——测试与分析 325
7.2.8 算术表达式求值——改进 326
7.2.9 自测习题 326
7.3 堆栈类的实现 327
7.3.1 堆栈的数组实现 327
7.3.2 堆栈的链表实现 330
7.3.3 Koenig查找 333
7.3.4 自测习题 333
7.4 更复杂的堆栈应用 334
7.4.1 后缀表达式求值 334
7.4.2 将中缀表示法转换成后缀表示法 336
7.4.3 在中缀表达式中使用优先级规则 338
7.4.4 中缀转换为后缀的正确性 340
7.4.5 自测习题 341
7.5 本章小结 342
7.6 自测习题答案 342
7.7 编程项目 344
第8章 队列 349
8.1 队列和STL队列的简介 349
8.1.1 标准库的队列类 350
8.1.2 队列的使用 350
8.1.3 自测习题 352
8.2 队列的应用 352
8.2.1 编程示例：识别回文 352
8.2.2 自测习题 355
8.2.3 编程示例：洗车模拟 355
8.2.4 洗车模拟——规范说明 355
8.2.5 洗车模拟——设计 355
8.2.6 洗车模拟——实现洗车类 358
8.2.7 洗车模拟——实现模拟函数 363
8.2.8 自测习题 365
8.3 队列类的实现 365
8.3.1 队列的数组实现 365
8.3.2 有关队列中循环数组实现的讨论 369
8.3.3 队列的链表实现 371
8.3.4 实现细节 372
8.3.5 自测习题 377
8.4 优先队列 377
8.4.1 如何指定优先级 378
8.4.2 标准库的优先队列类 378
8.4.3 优先队列类——实现思想 379
8.4.4 自测习题 379
8.5 堆栈、队列和优先队列类的引用返回值 379
8.6 本章小结 380
8.7 自测习题答案 380
8.8 编程项目 381
第9章 递归思想 385
9.1 递归函数 385
9.1.1 递归思想的第一个例子 385
9.1.2 跟踪递归调用 387
9.1.3 编程示例：write_vertical的一个扩展 388
9.1.4 深入分析递归 389
9.1.5 成功递归函数的一般形式 392
9.1.6 自测习题 392
9.2 递归的研究：分形和迷宫 393
9.2.1 编程示例：产生随机分形 393
9.2.2 用于产生随机分形的函数——规范说明 395
9.2.3 分形函数的设计和实现 396
9.2.4 如何显示随机分形 398
9.2.5 编程示例：穿越迷宫 399
9.2.6 穿越迷宫——规范说明 399
9.2.7 穿越迷宫——设计 401
9.2.8 穿越迷宫——实现 401
9.2.9 运用回溯穷举搜索的递归模式 403
9.2.10 编程示例：玩具熊游戏 404
9.2.11 自测习题 406
9.3 推导递归 406
9.3.1 如何确保没有无限递归 408
9.3.2 归纳推导递归函数的正确性 410
9.3.3 自测习题 411
9.4 本章小结 411
9.5 自测习题答案 412
9.6 编程项目 414
第10章 树 419
10.1 树的简介 419
10.1.1 二叉树 419
10.1.2 二叉分类树 422
10.1.3 一般树 422
10.1.4 自测习题 423
10.2 树的表示法 424
10.2.1 完全二叉树的数组表示法 424
10.2.2 使用节点类表示二叉树 427
10.2.3 自测习题 428
10.3 二叉树节点类 429
10.3.1 编程示例：猜动物 432
10.3.2 动物猜测程序——设计和实现 434
10.3.3 动物猜测程序——改进 438
10.3.4 自测习题 441
10.4 树的遍历 441
10.4.1 二叉树的遍历 441
10.4.2 从树的节点中输出数据 445
10.4.3 遍历中的问题 446
10.4.4 函数作为参数 447
10.4.5 apply函数的一个模板版本 448
10.4.6 使apply模板函数更具有通用性 449
10.4.7 树遍历的模板函数 450
10.4.8 自测习题 451
10.5 二叉搜索树 458
10.5.1 二叉搜索树存储机制 458
10.5.2 第6个包——类定义 462
10.5.3 第6个包——某些简单函数的实现 462
10.5.4 计算某个元素在二叉搜索树中出现的次数 462
10.5.5 添加一个新元素到二叉搜索树中 463
10.5.6 从二叉搜索树中移除某个元素 464
10.5.7 二叉搜索树的组合操作符 467
10.5.8 时间分析和迭代器 469
10.5.9 自测习题 469
10.6 本章小结 469
10.7 自测习题答案 470
10.8 编程项目 473
第11章 树项目 479
11.1 堆 479
11.1.1 堆的存储规则 479
11.1.2 使用堆结构实现的优先队列ADT 480
11.1.3 插入新项 480
11.1.4 删除项 482
11.1.5 自测习题 484
11.2 B树 484
11.2.1 非平衡树的问题 484
11.2.2 B树的规则 485
11.2.3 B树的一个示例 486
11.2.4 B树实现的集合ADT 487
11.2.5 在B树中查找项 491
11.2.6 在B树中插入项 493
11.2.7 B树的松散插入操作 493
11.2.8 修正子节点多余项的私有成员函数 495
11.2.9 回到成员函数Insert 496
11.2.10 采用自顶向下方法设计 497
11.2.11 从B树中删除项 498
11.2.12 B树的松散删除操作 499
11.2.13 解决子节点项短缺问题的私有成员函数 501
11.2.14 从B树中删除最大的项 503
11.2.15 外部B树 505
11.2.16 自测习题 505
11.3 树、日志和时间分析 506
11.3.1 二叉搜索树的时间分析 506
11.3.2 堆的时间分析 507
11.3.3 对数运算 508
11.3.4 对数级算法 509
11.3.5 自测习题 510
11.4 本章小结 510
11.5 自测习题答案 510
11.6 编程项目 513
第12章 查找 515
12.1 顺序查找和二分查找 515
12.1.1 顺序查找 515
12.1.2 顺序查找——分析 516
12.1.3 二分查找 517
12.1.4 二分查找——设计 518
12.1.5 二分查找——分析 520
12.1.6 标准库查找函数 523
12.1.7 用于有序域的函数 523
12.1.8 用于无序域的函数 525
12.1.9 STL查找函数 526
12.1.10 自测习题 526
12.2 开地址散列 526
12.2.1 散列简介 526
12.2.2 表类——声明 529
12.2.3 表类——设计 530
12.2.4 表ADT——实现 533
12.2.5 选择散列函数来减少冲突 538
12.2.6 再散列减少聚类 538
12.2.7 自测习题 540
12.3 链式散列 540
12.3.1 链式散列 540
12.3.2 自测习题 542
12.4 散列的时间分析 542
12.4.1 散列表的装填因子 542
12.4.2 自测习题 545
12.5 程序设计：使用STL向量的表类 545
12.5.1 新表类 545
12.5.2 在新表类中使用向量 545
12.5.3 常量模板参数 545
12.5.4 函数模板参数 546
12.5.5 实现新表类 546
12.5.6 自测习题 547
12.6 STL中的匹配和多重匹配 547
12.7 本章小结 548
12.8 自测习题答案 549
12.9 编程项目 552
第13章 排序 555
13.1 二次排序算法 555
13.1.1 选择排序——规范说明 555
13.1.2 选择排序——设计 556
13.1.3 选择排序——实现 558
13.1.4 选择排序——分析 560
13.1.5 插入排序 561
13.1.6 插入排序——分析 564
13.1.7 自测习题 566
13.2 递归排序算法 567
13.2.1 使用递归的分治法 567
13.2.2 合并排序 569
13.2.3 合并函数 571
13.2.4 动态内存在合并排序中的应用 575
13.2.5 合并排序——分析 575
13.2.6 文件的合并排序 577
13.2.7 快速排序 577
13.2.8 partition函数 579
13.2.9 快速排序——分析 581
13.2.10 快速排序——选择一个好的基准元素 583
13.2.11 自测习题 583
13.3 使用堆的O（n log n）算法 584
13.3.1 堆排序 584
13.3.2 构建堆 589
13.3.3 向下重排 590
13.3.4 堆排序——分析 591
13.3.5 自测习题 592
13.4 使用库函数排序和随机访问迭代器 592
13.4.1 原始C qusort函数 592
13.4.2 STL排序函数 593
13.4.3 使用迭代器编写一个排序函数 593
13.5 本章小结 594
13.6 自测习题答案 595
13.7 编程项目 597
第14章 派生类和继承 601
14.1 派生类 601
14.1.1 如何声明派生类 603
14.1.2 派生类的自动构造函数 604
14.1.3 使用派生类 605
14.1.4 派生类的自动赋值操作符 606
14.1.5 派生类的自动析构函数 607
14.1.6 覆盖继承的成员函数 607
14.1.7 自测习题 608
14.2 仿真生态系统 608
14.2.1 实现部分生物对象层次 609
14.2.2 organism类 609
14.2.3 animal类：具有新私有成员变量的派生类 612
14.2.4 如何为派生类提供新的构造函数 612
14.2.5 animal类的其他成员函数 614
14.2.6 自测习题 617
14.2.7 Herbivore类 618
14.2.8 池塘生活仿真程序 620
14.2.9 池塘生活——实现细节 623
14.2.10 使用池塘模型 624
14.2.11 动态内存的使用 625
14.2.12 自测习题 625
14.3 虚拟成员函数和game类 625
14.3.1 game类简介 626
14.3.2 受保护的成员 629
14.3.3 虚拟成员函数 629
14.3.4 虚拟析构函数 630
14.3.5 游戏类的受保护虚拟成员函数 630
14.3.6 玩Connect Four游戏的派生类 631
14.3.7 Connect Four游戏类的私有成员变量 631
14.3.8 Connect Four的构造函数和重启函数 633
14.3.9 三个处理游戏状态的Connect Four函数 633
14.3.10 三个处理移动的Connect Four函数 634
14.3.11 Clone函数 634
14.3.12 编写派生自game类的游戏 635
14.3.13 使用minimax的游戏类的play算法 635
14.3.14 自测习题 638
14.4 本章小结 638
14.5 进阶阅读 639
14.6 自测习题答案 639
14.7 编程项目 643
第15章 图 645
15.1 图的定义 645
15.1.1 无向图 645
15.1.2 有向图 648
15.1.3 图的更多术语 649
15.1.4 航线的例子 650
15.1.5 自测习题 650
15.2 图的实现 651
15.2.1 使用邻接矩阵表示图 651
15.2.2 使用二维数组存储邻接矩阵 652
15.2.3 使用边列表表示图 652
15.2.4 使用边集表示图 653
15.2.5 哪种表示方法最好 653
15.2.6 编程示例：标签图类 654
15.2.7 用于增加顶点和边的成员函数 655
15.2.8 标签图类——重载下标操作符 655
15.2.9 下标操作符的常量版本 656
15.2.10 标签图类——函数neighbors 657
15.2.11 标签图类——实现 657
15.2.12 自测习题 657
15.3 图的遍历 662
15.3.1 深度优先搜索 663
15.3.2 宽度优先搜索 666
15.3.3 深度优先搜索——实现 668
15.3.4 宽度优先搜索——实现 669
15.3.5 自测习题 669
15.4 路径算法 671
15.4.1 判断某条路径是否存在 671
15.4.2 具有加权边的图 672
15.4.3 最短距离算法 672
15.4.4 最短路径算法 680
15.4.5 自测习题 681
15.5 本章小结 681
15.6 自测习题答案 681
15.7 编程项目 683
附录A ASCII字符集类 687
附录B 大O表达式 689
附录C 操作符的优先顺序 693
附录D 命令行编译和链接 695
附录E 使用旧式编译器 699
附录F C＋＋的输入和输出 703
附录G 选择库函数 711
附录H 标准模板类简介 715
附录I useful函数的工具箱 725
附录J 基本格式指南 729
附录K 下载GNU编译器和软件 731
附录L 异常处理 733