第1章 软件开发的阶段 1
1.1 规范说明、设计与实现 2
1.1.1 概念设计：问题分解 3
1.1.2 前置条件与后置条件 4
1.1.3 使用由其他程序员提供的函数 6
1.1.4 有关ANSI/ISO C++标准的实现问题 8
1.1.5 本节自测练习 11
1.2 运行时间分析 12
1.2.1 台阶计数问题 12
1.2.2 大O表示法 16
1.2.3 C++函数的时间分析 17
1.2.4 最坏情况、平均情况以及最好情况下的时间分析 19
1.2.5 本节自测练习 19
1.3 测试与调试 20
1.3.1 选择测试数据 20
1.3.2 边界值 20
1.3.3 完全代码测试 21
1.3.4 调试 21
1.3.5 本节自测练习 22
1.4 本章小结 22
本章自测练习参考答案 23
第2章 抽象数据类型与C++类 25
2.1 类与成员 25
2.1.1 编程示例：节流阀类throttle 25
2.1.2 使用类 29
2.1.3 throttle类的演示小程序 30
2.1.4 实现成员函数 31
2.1.5 可以调用其他成员的成员函数 34
2.1.6 本节自测练习 34
2.2 构造函数 35
2.2.1 throttle类的构造函数 35
2.2.2 修订throttle类的成员函数 37
2.2.3 内联成员函数 38
2.2.4 本节自测练习 39
2.3 使用名称空间、头文件与实现文件 39
2.3.1 创建名称空间 40
2.3.2 头文件 40
2.3.3 实现文件 44
2.3.4 使用名称空间里的数据项 46
2.3.5 本节自测练习 48
2.4 类与参数 49
2.4.1 编程示例：point类 49
2.4.2 参数默认值 52
2.4.3 参数 53
2.4.4 当函数的返回值的数据类型为类时 58
2.4.5 本节自测练习 59
2.5 操作符重载 60
2.5.1 二元比较操作符重载 60
2.5.2 二元算术操作符重载 61
2.5.3 输入输出操作符重载 62
2.5.4 友元函数 64
2.5.5 point类汇总 66
2.5.6 操作符重载小结 68
2.5.7 本节自测练习 69
2.6 标准模板库与pair类 69
2.7 本章小结 70
本章自测练习参考答案 71
编程项目 73
第3章 容器类 81
3.1 bag类 81
3.1.1 bag类的规范说明 81
3.1.2 bag类的文档说明 88
3.1.3 bag类的演示程序 91
3.1.4 bag类的设计 93
3.1.5 类的不变式 94
3.1.6 bag类的实现 95
3.1.7 bag类的集成 101
3.1.8 bag类的测试 104
3.1.9 bag类的分析 105
3.1.10 本节自测练习 106
3.2 编程项目：sequence类 107
3.2.1 sequence类的规范说明 107
3.2.2 sequence类的文档说明 111
3.2.3 sequence类的设计 113
3.2.4 sequence类的伪代码实现 114
3.2.5 本节自测练习 116
3.3 交互式测试程序 116
本节自测练习 121
3.4 STL中的multiset类及其迭代器 122
3.4.1 multiset模板类 122
3.4.2 multiset类的一些成员 123
3.4.3 迭代器与［…）模式 123
3.4.4 测试迭代器的相等性 126
3.4.5 multiset类的其他操作符 126
3.4.6 不合法的迭代器 126
3.4.7 本节自测练习 128
3.5 本章小结 128
本章自测练习参考答案 128
编程项目 131
第4章 指针与动态数组 138
4.1 指针与动态内存 138
4.1.1 指针变量 139
4.1.2 指针与赋值操作符一起使用 140
4.1.3 动态变量new操作符 142
4.1.4 使用new操作符为动态数组分配内存 143
4.1.5 内存堆与bad_alloc异常 144
4.1.6 delete操作符 145
4.1.7 本节自测练习 147
4.2 把指针与数组作为参数 147
4.2.1 以指针作为值参数 147
4.2.2 数组参数 149
4.2.3 以指针或数组作为常量参数 150
4.2.4 以指针作为引用参数 152
4.2.5 本节自测练习 153
4.3 具有动态数组的bag类 156
4.3.1 指针成员变量 156
4.3.2 成员函数按需分配内存 157
4.3.3 值语义 161
4.3.4 析构函数 163
4.3.5 修订后的bag类定义 164
4.3.6 修订后的bag类实现 165
4.3.7 修订后的bag类集成 170
4.3.8 本节自测练习 172
4.4 有关动态类的说明 172
4.4.1 4条规则 173
4.4.2 复制构造函数的特殊重要性 173
4.4.3 本节自测练习 174
4.5 STL的string类与编程项目 174
4.5.1 以null结尾的字符串 174
4.5.2 初始化字符串变量 175
4.5.3 空字符串 175
4.5.4 读写字符串变量 175
4.5.5 strcpy函数 176
4.5.6 strcat函数 177
4.5.7 strlen函数 177
4.5.8 strcmp函数 178
4.5.9 string类的规范说明 178
4.5.10 string类的构造函数 180
4.5.11 重载operator[] 181
4.5.12 其他重载成员 181
4.5.13 string类的其他操作 182
4.5.14 string类的设计 182
4.5.15 string类的实现 183
4.5.16 string类的演示程序 185
4.5.17 串联输出操作符 186
4.5.18 明常量对象 187
4.5.19 由构造函数产生的类型转换 187
4.5.20 在表达式中使用已重载的操作符 187
4.5.21 本章设计的string类与C++库的string类 188
4.5.22 本节自测练习 188
4.6 编程项目：polynomial类 188
4.7 本章小结 191
本章自测练习参考答案 192
编程项目 194
第5章 链表 196
5.1 链表的基本节点类 196
5.1.1 为节点声明类 196
5.1.2 在链表节点中使用typedef语句 197
5.1.3 头指针和尾指针 197
5.1.4 空指针NULL 198
5.1.5 头指针或尾指针为NULL的含义 199
5.1.6 节点类构造函数 199
5.1.7 节点类成员函数 200
5.1.8 成员选择操作符 201
5.1.9 本节自测练习 204
5.2 链表工具包 205
5.2.1 链表工具包的头文件 205
5.2.2 计算链表的长度 206
5.2.3 链表的参数 209
5.2.4 在链表头插入新节点 210
5.2.5 在非链表头的其他位置插入新节点 212
5.2.6 在链表中查找节点 215
5.2.7 根据节点的位置在链表中寻找节点 217
5.2.8 链表复制 218
5.2.9 在链表头删除节点 221
5.2.10 在非链表头删除节点 222
5.2.11 清空链表 223
5.2.12 链表工具包的集成 224
5.2.13 使用链表工具包 228
5.2.14 本节自测练习 228
5.3 用链表实现bag类 229
5.3.1 第3个bag类的规范说明 229
5.3.2 第3个bag类的类定义 230
5.3.3 如何使bag类的value_type与节点类的value_type相匹配 233
5.3.4 在类中使用动态内存 应遵循的规则 234
5.3.5 第3个bag类的实现 234
5.3.6 第3个bag类的集成 241
5.3.7 本节自测练习 244
5.4 编程项目：用链表实现sequence类 244
5.4.1 关于修订后的sequence类的设计建议 245
5.4.2 关于修订后的sequence类的值语义 246
5.4.3 本节自测练习 246
5.5 动态数组、链表与双向链表 246
5.5.1 做出抉择 248
5.5.2 本节自测练习 249
5.6 标准模板库的vector、list和deque类 249
本节测试练习 252
5.7 本章小结 252
本章自测练习参考答案 252
编程项目 257
第6章 用模板、迭代器和STL进行软件开发 261
6.1 模板函数 261
6.1.1 模板函数的语法 263
6.1.2 使用模板函数 263
6.1.3 交换两个值的模板函数 265
6.1.4 模板函数的参数匹配 266
6.1.5 在数组中查找最大项的模板函数 267
6.1.6 在已排序数组中插入一个数据项的模板函数 268
6.1.7 本节自测练习 270
6.2 模板类 270
6.2.1 模板类的语法 270
6.2.2 进一步了解模板类实现文件 277
6.2.3 模板类成员函数的参数匹配 278
6.2.4 使用模板类 278
6.2.5 详细讨论上一个演示程序 281
6.2.6 本节自测练习 282
6.3 STL算法与迭代器的使用 282
6.3.1 STL算法 282
6.3.2 标准迭代器的类型 283
6.3.3 数组的迭代器 285
6.3.4 本节自测习题 285
6.4 节点模板类 286
6.4.1 返回引用类型的函数 287
6.4.2 将引用返回值复制到别处时会发生什么 288
6.4.3 这里成员函数data需要两个版本 288
6.4.4 新节点类的头文件和实现文件 289
6.4.5 本节自测练习 297
6.5 链表的迭代器 297
6.5.1 节点迭代器 297
6.5.2 从std::iterator派生而来的节点迭代器 299
6.5.3 节点迭代器的私有成员变量 300
6.5.4 节点迭代器的构造函数 300
6.5.5 节点迭代器的*操作符 300
6.5.6 节点迭代器两个版本的＋＋操作符 300
6.5.7 节点迭代器的相等和不相等比较 302
6.5.8 常量集合的迭代器 302
6.5.9 本节自测练习 304
6.6 含迭代器的链表版bag模板类 305
6.6.1 如何为容器类提供迭代器 305
6.6.2 bag类迭代器 306
6.6.3 将迭代器定义在bag类中的原因 307
6.6.4 本节自测练习 314
6.7 本章小结与5个bag类的小结 314
本章自测练习答案 315
编程项目 318
第7章 栈 320
7.1 STL的stack类 320
7.1.1 标准库的stack类 321
7.1.2 编程示例：翻转单词 322
7.1.3 本节自测练习 323
7.2 栈的应用 323
7.2.1 编程示例：括号的匹配 323
7.2.2 编程示例：算术表达式求值 325
7.2.3 算术表达式求值的规范说明 326
7.2.4 算术表达式求值的设计 326
7.2.5 算术表达式求值的实现 331
7.2.6 计算器程序使用的函数 332
7.2.7 算术表达式求值的测试与分析 332
7.2.8 算术表达式求值的改进 333
7.2.9 本节自测练习 333
7.3 stack类的实现 334
7.3.1 栈的数组实现 334
7.3.2 栈的链表实现 337
7.3.3 Koenig查找 341
7.3.4 本节自测练习 341
7.4 更复杂的栈应用 342
7.4.1 后缀表达式求值 342
7.4.2 将中缀表示法转换成后缀表示法 344
7.4.3 在中缀表达式中使用优先级规则 346
7.4.4 中缀转换为后缀的正确性 348
7.4.5 本节自测练习 349
7.5 本章小结 349
本章自测练习答案 350
编程项目 351
第8章 队列 356
8.1 STL队列 356
8.1.1 标准库的队列类 357
8.1.2 队列的使用 358
8.1.3 本节自测练习 359
8.2 队列的应用 359
8.2.1 编程示例：识别回文 359
8.2.2 本节自测练习 361
8.2.3 编程示例：洗车模拟程序 362
8.2.4 洗车模拟程序的规范说明 362
8.2.5 洗车模拟程序的设计 362
8.2.6 实现洗车类 365
8.2.7 实现模拟函数 371
8.2.8 本节自测练习 372
8.3 队列类的实现 373
8.3.1 队列的数组实现 373
8.3.2 有关队列中环形数组实现的讨论 377
8.3.3 队列的链表实现 379
8.3.4 实现细节 380
8.3.5 本节自测练习 384
8.4 实现STL的双端队列 384
8.4.1 为双端队列的value_type项调用析构函数和构造函数 387
8.4.2 栈和队列的其他变体 388
8.4.3 本节自测练习 388
8.5 栈、队列和优先队列类的引用返回值 388
8.6 本章小结 389
本章自测练习答案 389
编程项目 390
第9章 递归思想 394
9.1 递归函数 394
9.1.1 递归思想的第一个例子 394
9.1.2 跟踪递归调用 396
9.1.3 编程示例：write_vertical的一个扩展 397
9.1.4 深入分析递归 398
9.1.5 成功递归函数的一般形式 401
9.1.6 本节自测练习 402
9.2 递归的研究：分形和迷宫 402
9.2.1 编程示例：产生随机分形 403
9.2.2 产生随机分形的函数及其规范说明 404
9.2.3 分形函数的设计和实现 405
9.2.4 如何显示随机分形 407
9.2.5 编程示例：穿越迷宫 407
9.2.6 穿越迷宫函数的规范说明 408
9.2.7 穿越迷宫函数的设计 409
9.2.8 穿越迷宫函数的实现 410
9.2.9 运用回溯穷举搜索的递归模式 412
9.2.10 编程示例：玩具熊游戏 413
9.2.11 本节自测练习 414
9.3 推导递归 415
9.3.1 如何确保没有无限递归 417
9.3.2 归纳推导递归函数的正确性 419
9.3.3 本节自测练习 419
9.4 本章小结 420
本章自测练习答案 420
编程项目 422
第10章 树 427
10.1 树的简介 427
10.1.1 二叉树 427
10.1.2 二叉分类树 430
10.1.3 一般树 430
10.1.4 本节自测练习 431
10.2 树的表示法 431
10.2.1 完全二叉树的数组表示法 432
10.2.2 使用节点类表示二叉树 433
10.2.3 本节自测练习 434
10.3 二叉树节点类 435
10.3.1 编程示例：猜测动物程序 439
10.3.2 猜测动物程序的设计与实现 440
10.3.3 猜测动物程序的改进 448
10.3.4 本节自测练习 448
10.4 树的遍历 449
10.4.1 二叉树的遍历 449
10.4.2 从树的节点中输出数据 453
10.4.3 遍历中的问题 454
10.4.4 函数作为参数 454
10.4.5 apply函数的一个模板版本 456
10.4.6 使apply模板函数更具有通用性 457
10.4.7 树遍历的模板函数 458
10.4.8 本节自测练习 465
10.5 二叉查找树 466
10.5.1 二叉查找树存储机制 466
10.5.2 第6个bag类的定义 470
10.5.3 第6个bag类的某些简单函数的实现 470
10.5.4 计算某个元素在二叉查找树中出现的次数 471
10.5.5 添加一个新元素到二叉查找树中 472
10.5.6 从二叉查找树中删除某个元素 473
10.5.7 二叉查找树的组合操作符 475
10.5.8 时间分析和迭代器 477
10.5.9 本节自测练习 478
10.6 本章小结 478
本章自测练习答案 479
编程项目 482
第11章 平衡树 487
11.1 堆 487
11.1.1 堆的存储规则 487
11.1.2 使用堆结构实现的优先队列 488
11.1.3 插入新项 488
11.1.4 删除项 489
11.2 STL优先队列与堆算法 491
本节自测练习 492
11.3 B树 492
11.3.1 非平衡树的问题 493
11.3.2 B树的规则 493
11.3.3 B树的一个示例 495
11.3.4 用B树实现set类 495
11.3.5 在B树中查找项 499
11.3.6 在B树中插入项 501
11.3.7 B树的松散插入操作 501
11.3.8 修正子节点多余项的私有成员函数 503
11.3.9 回到成员函数Insert 504
11.3.10 采用自顶向下方法设计 505
11.3.11 从B树中删除项 505
11.3.12 B树的松散删除操作 506
11.3.13 解决子节点项短缺问题的私有成员函数 508
11.3.14 从B树中删除最大的项 510
11.3.15 外部B树 512
11.3.16 本节自测练习 512
11.4 树、日志和时间分析 513
11.4.1 二叉查找树的时间分析 513
11.4.2 堆的时间分析 514
11.4.3 对数运算 515
11.4.4 对数级算法 516
11.4.5 本节自测练习 516
11.5 STL的map类和multimap类 517
11.6 本章小结 518
本章自测练习答案 518
编程项目 521
第12章 查找 523
12.1 顺序查找和二叉查找 523
12.1.1 顺序查找 523
12.1.2 顺序查找的分析 523
12.1.3 二叉查找 525
12.1.4 二叉查找的设计 526
12.1.5 二叉查找的分析 528
12.1.6 标准库的查找函数 531
12.1.7 用于有序区间的函数 531
12.1.8 用于无序区间的函数 532
12.1.9 STL的search函数 533
12.1.10 本节自测练习 534
12.2 开地址散列 534
12.2.1 散列简介 534
12.2.2 表类的声明 536
12.2.3 表类的设计 538
12.2.4 表ADT的实现 541
12.2.5 选择散列函数来减少冲突 547
12.2.6 再散列减少聚类 547
12.2.7 本节自测练习 548
12.3 链式散列 549
本节自测练习 551
12.4 散列的时间分析 551
12.4.1 散列表的装填因子 551
12.4.2 本节自测练习 553
12.5 程序设计：使用STL向量的表类 553
12.5.1 新表类 553
12.5.2 在新表类中使用向量 554
12.5.3 常量模板参数 554
12.5.4 函数模板参数 554
12.5.5 实现新表类 555
12.5.6 本节自测练习 556
12.6 TR1库扩展中的散列表 556
12.7 本章小结 557
本章自测练习答案 557
编程项目 561
第13章 排序 563
13.1 二次排序算法 563
13.1.1 选择排序的规范说明 563
13.1.2 选择排序的设计 563
13.1.3 选择排序的实现 565
13.1.4 选择排序的效率分析 567
13.1.5 插入排序 569
13.1.6 插入排序的效率分析 571
13.1.7 本节自测练习 573
13.2 递归排序算法 574
13.2.1 使用递归的分治法 574
13.2.2 归并排序 576
13.2.3 归并函数 577
13.2.4 动态内存在归并排序中的应用 581
13.2.5 归并排序的效率分析 582
13.2.6 文件的归并排序 583
13.2.7 快速排序 584
13.2.8 partition函数 585
13.2.9 快速排序的效率分析 588
13.2.10 为快速排序选择一个好的基准元素 589
13.2.11 本节自测练习 589
13.3 使用堆的O（n log n）算法 590
13.3.1 堆排序 590
13.3.2 构建堆 595
13.3.3 向下重排 596
13.3.4 堆排序的效率分析 597
13.3.5 本节自测练习 598
13.4 STL的排序与二叉查找 598
13.4.1 原始C标准库函数qsort 598
13.4.2 STL的排序函数 599
13.4.3 STL的堆排序 600
13.4.4 STL的二叉查找函数 600
13.4.5 用于STL排序函数的比较参数 601
13.4.6 使用迭代器编写一个自己的排序函数 601
13.5 本章小结 602
本章自测练习答案 603
编程项目 605
第14章 派生类与继承 610
14.1 派生类 610
14.1.1 如何声明派生类 612
14.1.2 派生类的自动构造函数 613
14.1.3 使用派生类 614
14.1.4 派生类的自动赋值操作符 615
14.1.5 派生类的自动析构函数 616
14.1.6 覆盖继承的成员函数 616
14.1.7 本节自测练习 617
14.2 仿真生态系统 618
14.2.1 实现部分生物对象层次 618
14.2.2 organism类 618
14.2.3 animal类：具有新私有成员变量的派生类 621
14.2.4 如何为派生类提供新构造函数 622
14.2.5 animal类的其他成员函数 623
14.2.6 本节自测练习 627
14.2.7 herbivore类 628
14.2.8 池塘生态仿真程序 630
14.2.9 池塘生态系统的实现细节 634
14.2.10 使用池塘模型 634
14.2.11 动态内存的使用 635
14.2.12 本节自测练习 636
14.3 虚拟成员函数和game类 636
14.3.1 game类简介 636
14.3.2 受保护的成员 640
14.3.3 虚拟成员函数 640
14.3.4 虚拟析构函数 641
14.3.5 game类的受保护虚拟成员函数 641
14.3.6 实现Connect Four游戏的派生类 642
14.3.7 connect4类的私有成员变量 642
14.3.8 connect4类的构造函数和restart函数 644
14.3.9 处理游戏状态的三个函数 644
14.3.10 处理移动的三个函数 645
14.3.11 clone函数 646
14.3.12 编写派生自game类的游戏 646
14.3.13 game类的play算法 647
14.3.14 本节自测练习 650
14.4 本章小结 650
进阶阅读 650
本章自测练习答案 651
编程项目 655
第15章 图 657
15.1 图的定义 657
15.1.1 无向图 657
15.1.2 有向图 660
15.1.3 图的更多术语 661
15.1.4 航线的例子 661
15.1.5 本节自测练习 662
15.2 图的实现 663
15.2.1 使用邻接矩阵表示图 663
15.2.2 使用二维数组存储邻接矩阵 663
15.2.3 使用边列表表示图 664
15.2.4 使用边集表示图 665
15.2.5 哪种表示方法最好 665
15.2.6 编程示例：标签图类 665
15.2.7 用于增加顶点和边的成员函数 666
15.2.8 标签图类——重载下标操作符 667
15.2.9 下标操作符的常量版本 668
15.2.10 标签图类——函数neighbors 668
15.2.11 标签图类的实现 669
15.2.12 本节自测练习 674
15.3 图的遍历 674
15.3.1 深度优先搜索 675
15.3.2 宽度优先搜索 677
15.3.3 深度优先搜索的实现 679
15.3.4 宽度优先搜索的实现 680
15.3.5 本节自测练习 682
15.4 路径算法 683
15.4.1 判断某条路径是否存在 683
15.4.2 具有加权边的图 683
15.4.3 最短距离算法 684
15.4.4 最短路径算法 691
15.4.5 本节自测练习 691
15.5 本章小结 692
本章自测练习答案 692
编程项目 693
附录 697
附录A ASCII字符集 697
附录B 大O表达式 698
附录C 操作符的优先顺序 700
附录D 命令行编译和链接 701
附录E 使用老式编译器 701
附录F C++的输入和输出 701
附录G 选择库函数 708
附录H 标准模板类简介 711
附录I 一些有用函数的工具包 720
附录J 基本风格指南 723
附录K 下载GNU编译器和软件 723
附录L 异常处理 724