数据抽象和问题求解：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