数据抽象和问题求解：C++语言描述（第四版）

第1部分 问题解决技术
第1章 编程原理与软件工程 3
1.1 问题求解与软件工程 3
1.1.1 问题求解的含义 3
1.1.2 软件的生命周期 4
1.1.3 优秀解决方案的含义 10
1.2 模块化设计 11
1.2.1 抽象与信息隐藏 11
1.2.2 面向对象的设计 13
1.2.3 自上而下的设计 14
1.2.4 一般设计原则 15
1.2.5 使用UML为面向对象的设计
建模 15
1.2.6 面向对象方式的优点 17
1.3 关键编程问题 18
1.3.1 模块化 18
1.3.2 可修改 19
1.3.3 易用 21
1.3.4 防故障编程 21
1.3.5 风格 25
1.3.6 调试 30
1.4 小结 31
1.5 提示 32
1.6 自我测试题 32
1.7 练习题 33
1.8 编程问题 35
第2章 递归：镜子 37
2.1 递归解决方案 37
2.1.1 递归值函数：n的阶乘 39
2.1.2 递归void函数：逆置字符串 43
2.2 计数 52
2.2.1 兔子繁殖(Fibonacci序列) 52
2.2.2 组织游行队伍 53
2.2.3 Spock的困惑 56
2.3 数组查找 57
2.3.1 查找数组的最大项 58
2.3.2 折半查找 59
2.3.3 查找数组中的第k个最小项 62
2.4 组织数据 64
2.5 递归与效率 69
2.6 小结 72
2.7 提示 72
2.8 自我测试题 73
2.9 练习题 73
2.10 编程问题 79
第3章 数据抽象：墙 80
3.1 抽象数据类型 80
3.2 指定ADT 83
3.2.1 ADT列表 84
3.2.2 ADT有序表 88
3.2.3 设计ADT 89
3.2.4 公理 92
3.3 实现ADT 94
3.3.1 C++类 95
3.3.2 C++命名空间 102
3.3.3 基于数组的ADT列表实现 104
3.3.4 C++异常 109
3.3.5 使用异常的ADT列表实现 110
3.4 小结 112
3.5 提示 113
3.6 自我测试题 113
3.7 练习题 114
3.8 编程问题 116第4章 链表 117
4.1 预备知识 117
4.1.1 指针 118
4.1.2 数组的动态分配 123
4.1.3 基于指针的链表 124
4.2 链表编程 125
4.2.1 显示链表的内容 126
4.2.2 从链表中删除指定的节点 127
4.2.3 在链表的指定位置插入节点 129
4.2.4 ADT列表的基于指针的实现 133
4.2.5 比较基于数组的实现和基于
引用的实现 139
4.2.6 使用文件存储和恢复链表 140
4.2.7 将链表传给函数 143
4.2.8 递归地处理链表 144
4.2.9 把对象作为链表的数据 148
4.3 链表的各种变化 148
4.3.1 循环链表 148
4.3.2 虚拟头节点 150
4.3.3 双向链表 150
4.4 清单应用程序 152
4.5 C++标准模板库 156
4.5.1 容器 157
4.5.2 迭代器 157
4.5.3 标准模板库类list 158
4.6 小结 162
4.7 提示 164
4.8 自我测试题 165
4.9 练习题 167
4.10 编程问题 169
第5章 递归问题解决技术 172
5.1 回溯 172
5.1.1 八皇后问题 172
5.1.2 使用STL类vector解决八皇后
问题 174
5.2 定义语言 178
5.2.1 语法知识基础 179
5.2.2 两种简单语言 180
5.2.3 代数表达式 182
5.3 递归和数学归纳法的关系 189
5.3.1 factorial递归算法的正确性 189
5.3.2 Hanoi塔的成本 190
5.4 小结 191
5.5 提示 192
5.6 自我测试题 192
5.7 练习题 192
5.8 编程问题 195第2部分 使用抽象数据类型
解决问题
第6章 栈 201
6.1 抽象数据类型 201
6.2 ADT栈的简单应用 206
6.2.1 检查括号匹配 206
6.2.2 识别语言中的字符串 208
6.3 ADT栈的实现 209
6.3.1 ADT栈的基本数组的实现 209
6.3.2 ADT栈的基于指针的实现 213
6.3.3 使用ADT列表的实现 217
6.3.4 各种实现方式的比较 221
6.3.5 标准模板库类stack 221
6.4 应用：代数表达式 223
6.4.1 计算后缀表达式 223
6.4.2 中缀表达式与后缀表达式的
等价转换 224
6.5 应用：查找问题 227
6.5.1 使用栈的非递归解决方案 228
6.5.2 递归解决方案 234
6.6 栈和递归的关系 236
6.7 小结 238
6.8 提示 238
6.9 自我测试题 238
6.10 练习题 239
6.11 编程问题 242
第7章 队列 247
7.1 ADT队列 247
7.2 ADT队列的简单应用 249
7.2.1 读取字符串 249
7.2.2 识别回文 250
7.3 实现ADT队列 251
7.3.1 基于指针的实现 251
7.3.2 基于数组的实现 256
7.3.3 使用ADT列表的实现 261
7.3.4 标准模板库类queue 263
7.3.5 实现的比较 266
7.4 基于位置的ADT总览 266
7.5 模拟应用 267
7.6 小结 275
7.7 提示 275
7.8 自我测试题 275
7.9 练习题 276
7.10 编程问题 278
第8章 类关系 282
8.1 继承 282
8.1.1 公有、私有和受保护的继承 287
8.1.2 is-a、has-a和As-a关系 288
8.2 虚函数和后期绑定 290
8.3 友元 297
8.4 ADT列表和有序表 299
8.5 类模板 304
8.6 重载运算符 310
8.7 迭代器 313
8.8 小结 318
8.9 提示 319
8.10 自我测试题 319
8.11 练习题 319
8.12 编程问题 323
第9章 算法效率和排序 325
9.1 确定算法效率 325
9.1.1 算法的执行时间 326
9.1.2 算法增率 327
9.1.3 数量阶分析和大O表示法 328
9.1.4 正确分析问题 331
9.1.5 查找算法的效率 332
9.2 排序算法及其效率 333
9.2.1 选择排序 333
9.2.2 起泡排序 336
9.2.3 插入排序 337
9.2.4 归并排序 339
9.2.5 快速排序 344
9.2.6 基数排序 352
9.2.7 各种排序算法的比较 354
9.2.8 标准模板库排序算法 355
9.3 小结 359
9.4 提示 360
9.5 自我测试题 360
9.6 练习题 361
9.7 编程问题 363
第10章 树 366
10.1 术语 366
10.2 ADT二叉树 372
10.2.1 二叉树的遍历 375
10.2.2 二叉树的表示 378
10.2.3 ADT二叉树的基于指针的
实现 381
10.3 ADT二叉查找树 393
10.3.1 ADT二叉查找树操作的
算法 397
10.3.2 ADT二叉查找树的基于指针
的实现 408
10.3.3 二叉查找树操作的效率 416
10.3.4 树排序 419
10.3.5 将二叉查找树保存到文件 419
10.3.6 STL查找算法 422
10.4 一般树 424
10.5 小结 426
10.6 提示 426
10.7 自我测试题 427
10.8 练习题 428
10.9 编程问题 433
第11章 表和优先队列 435
11.1 ADT表 435
11.1.1 选择实现 439
11.1.2 ADT表的基于数组的有序
实现 444
11.1.3 ADT表的二叉查找树实现 448
11.2 ADT优先队列：ADT表的
变体 451
11.2.1 堆 454
11.2.2 ADT优先队列的堆实现 462
11.2.3 堆排序 464
11.3 STL中的表和优先队列 466
11.3.1 STL关联容器 466
11.3.2 STL的priority_queue类和
堆算法 474
11.3 小结 477
11.4 提示 478
11.5 自我测试题 478
11.6 练习题 479
11.7 编程问题 481
第12章 表的高级实现 483
12.1 平衡查找树 483
12.1.1 2-3树 484
12.1.2 2-3-4树 499
12.1.3 红-黑树 504
12.1.4 AVL树 506
12.2 散列 510
12.2.1 散列函数 513
12.2.2 解决冲突 515
12.2.3 散列的效率 521
12.2.4 如何确立散列函数 523
12.2.5 表遍历：散列的低效操作 525
12.2.6 使用STL实现
HashMap类 525
12.3 按多种形式组织数据 528
12.4 小结 531
12.5 提示 532
12.6 自我测试题 532
12.7 练习题 533
12.8 编程问题 535
第13章 图 536
13.1 术语 536
13.2 将图作为ADT 538
13.2.1 实现图 539
13.2.2 使用STL实现Graph类 541
13.3 图的遍历 544
13.3.1 深度优先查找 545
13.3.2 广度优先查找 546
13.3.3 使用STL实现BFS类 548
13.4 图的应用 550
13.4.1 拓扑排序 550
13.4.2 生成树 552
13.4.3 最小生成树 555
13.4.4 最短路径 556
13.4.5 回路 560
13.4.6 一些复杂问题 563
13.5 小结 563
13.6 提示 564
13.7 自我测试题 564
13.8 练习题 565
13.9 编程问题 567
第14章 外部方法 569
14.1 了解外部存储 569
14.2 排序外部文件的数据 571
14.3 外部表 577
14.3.1 确定外部文件的索引 579
14.3.2 外部散列 582
14.3.3 B-树 584
14.3.4 遍历 590
14.3.5 多索引 593
14.4 小结 594
14.5 提示 594
14.6 自我测试题 595
14.7 练习题 595
14.8 编程问题 597
附录A C++基础 599
附录B ASCII字符代码 653
附录C C++头文件和标准函数 655
附录D 数学归纳法 659
附录E 标准模板库 663
术语表 673
自我测试题答案 690