《数据结构与面向对象程序设计—— C++版(第3版)》

第1章  软件开发阶段	1
1.1  规范说明、设计和实现	2
1.1.1  概念设计：问题分解	3
1.1.2  前置条件和后置条件	4
1.1.3  使用其他程序员提供的函数	6
1.1.4  有关ANSI/ISO C++
标准的实现问题	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