数据结构与算法分析-C++语言描述（第2版）

第1章 软件开发 1

1.1 问题分析和需求规格说明 3

1.2 设计 5

1.2.1 自顶向下设计 5

1.2.2 面向对象设计 7

1.2.3 小规模设计 9

1.3 编码 15

1.4 测试、运行和调试 27

1.5 维护 34

1.6 本章小结 36

第2章 抽象数据类型入门 40

2.1 对ADT及其实现的第一瞥 40

2.2 C++的简单数据类型 41

2.2.1 整型数据 42

2.2.2 实型数据 46

2.2.3 字符数据 49

2.4.4 布尔数据 50

2.3 程序员定义的数据类型 53

2.3.1 Typedefs 53

2.3.2 枚举 53

2.3.3 类 55

2.4 指针 56

2.4.1 声明和初始化指针 57

2.4.2 基本指针操作 60

2.4.3 动态内存分配——new操作 64

2.4.4 关于引用形参的注释 65

2.5 本章小结 68

第3章 数据结构和抽象数据类型 73

3.1 数据结构，抽象数据类型和实现 73

3.2 静态数组 77

3.2.1 一维静态数组 78

3.2.2 下标运算 81

3.2.3 数组作为形参 82

3.2.4 越界错误 83

3.2.5 数组的问题 86

3.3 多维数组 88

3.3.1 二维数组 88

3.3.2 高维数组 89

3.3.3 数组的数组声明 91

3.3.4 多维数组作函数参数 95

3.4 动态数组 97

3.4.1 new操作——动态数组 98

3.4.2 指针的其他用法 110

3.5 C风格结构（可选） 112

指向结构的指针 116

3.6 过程式编程 117

过程式编程的例子 118

3.7 本章小结 123

第4章 OOP和ADT进阶——类 129

4.1 过程式编程vs.面向对象编程 129

4.2 类 130

4.2.1 “传统的”（C）结构和OOP

（C++）结构以及类之间的

区别 131

4.2.2 类声明 131

4.3 例子：用户定义的Time类的

第一个版本 135

4.3.1 为什么不使所有成员都

公有化 137

4.3.2 实现一个类 138

4.3.3 一些现象 141

4.4 类构造函数 142

4.5 其他类操作 150

4.5.1 复制操作——初始化和

赋值 150

4.5.2 访问函数和更动函数 151

4.5.3 重载运算符 153

4.5.4 重载输入/输出运算符 154

4.5.5 其他操作：前进和关系

操作 161

4.5.6 总结以及其他一些细节 163

4.5.7 指向类对象的指针 167

4.5.8 this指针 168

4.6 本章小结 171

第5章 标准C++输入/输出和字

符串类 176

5.1 C++标准I/O类 177

5.1.1 istream类 178

5.1.2 ostream类 182

5.1.3 文件I/O：ifstream和

ofstream类 186

5.1.4 I/O类层次 188

5.2 C++ String类型 192

5.2.1 C风格的字符串 193

5.2.2 一个字符串类 195

5.2.3 C++ String类 196

5.2.4 String流 204

5.3 案例学习：文本编辑 208

5.4 模式匹配介绍（可选） 216

5.5 数据加密介绍（可选） 219

5.5.1 数据加密标准（Data Encryption

Standard） 222

5.5.2 公共密钥加密（Public-Key

Encryption） 222

5.6 本章小结 224

第6章 列表 228

6.1 作为ADT的列表 229

设计和创建一个列表类 230

6.2 基于数组的列表实现 231

6.2.1 选择存储结构 231

6.2.2 实现操作 232

6.2.3 一个使用静态数组存储的

列表类 234

6.3 使用动态分配的基于数组实现的

列表 242

6.3.1 类中的动态分配——析构函数、复制构造函数和赋值运算符 246

6.3.2 最后一点 253

6.4 对链表的介绍 257

6.4.1 它们是什么 257

6.4.2 实现基本列表操作 258

6.4.3 小结 262

6.5 在C++中基于指针来实现链表 264

6.5.1 节点结构 264

6.5.2 链表实现中的数据成员 266

6.5.3 链表实现中的函数成员 267

6.6 基于数组的链表实现 271

6.6.1 节点结构 272

6.6.2 存储池管理 274

6.7 本章小结 276

第7章 栈 280

7.1 栈的介绍 281

7.2 设计和创建一个Stack类——

基于数组 285

7.2.1 选择存储结构 285

7.2.2 实现操作 288

7.2.3 实现pop操作的算法 290

7.2.4 完整的Stack类 290

7.2.5 使用动态数组存储栈元素296

7.2.6 前瞻 309

7.3 链式栈 312

7.3.1 选择存储结构 313

7.3.2 实现操作 314

7.3.3 完整的Stack类：链表

版本 317

7.4 栈在函数调用中的使用 324

7.5 案例学习：后缀（RPN）表示329

7.5.1 计算后缀表达式 330

7.5.2 将中缀表达式转换成后缀

表达式 331

7.6 本章小节 341

第8章 队列 345

8.1 队列入门 345

8.2 设计和创建一个Queue类——

基于数组 353

8.2.1 使用静态数组存储队列

元素 356

8.2.2 使用动态数组存储队列

元素 361

8.3 链式队列 365

8.3.1 一种自然的链表实现 365

8.3.2 使用循环链表 374

8.4 队列的应用：缓冲区和调度376

8.5 案例学习：信息中心仿真 379

8.5.1 问题分析和需求规格说明380

8.5.2 创建一个Simulation类 380

8.5.3 Time类和Call类 389

8.6 本章小结 390

第9章 ADT实现：模板和标准容器393

9.1 介绍：可重用性和通用性的发展394

9.1.1 从算法到算法 394

9.1.2 从数据到容器 396

9.2 函数通用性——重载和模板396

9.2.1 重载 397

9.2.2 函数模板 399

9.2.3 另一个例子：显示一个

数组 403

9.3 类通用性——模板 404

9.3.1 Typedef有什么错 404

9.3.2 类模板 405

9.3.3 Stack类模板的另一个版本417

9.3.4 对标准C++容器类模板的

快速一瞥 418

9.4 vector容器 420

9.4.1 定义vector对象 421

9.4.2 一些vector操作 423

9.4.3 内部实现一瞥——增加

容量 427

9.4.4 对迭代器的第一次探讨 430

9.4.5 一些牵涉到迭代器的vector

函数成员 433

9.4.6 综合比较：vector对数组434

9.5 案例学习：计算机系统登录统计438

9.6 多维vector（可选） 443

9.6.1 二维vector对象 443

9.6.2 二维vector操作 444

9.7 其他标准容器——deque、stack以及queue 447

9.7.1 STL的deque类模板 447

9.7.2 我们的stack类模板的一个

新（但是非必须的）版本 450

9.7.3 STL的stack适配器 452

9.7.4 STL的queue适配器 453

9.8 Bitset和Valarray（可选）454

9.8.1 Bitset 454

9.8.2 Valarray 456

9.8.3 Slics、Mask、以及间接

数组 458

9.9 本章小结 459

第10章 ADT实现--递归、算法分析

以及标准算法 464

10.1 递归 464

10.1.1 递归的例子 465

10.1.2 递归函数的编码 466

10.1.3 糟糕递归的例子：Fibonacci

数字 468

10.1.4 例子：折半查找 470

10.1.5 例子：回文检查程序 473

10.2 递归的例子：Hanoi塔；分析478

10.2.1 Hanoi塔 478

10.2.2 分析 481

10.3 实现递归 485

10.4 算法效率 489

10.5 C++中的标准算法 500

10.5.1 例：STL的sort算法 500

10.5.2 STL算法的例子 505

10.5.3 <numeric>库中的算法 506

10.5.4 例：花样滑冰评判 507

10.6 算法正确性证明(可选) 508

10.6.1 例：计算平均值 509

10.6.2 例：递归求幂函数 510

10.6.3 总结 511

10.7 本章小节 513

第11章 其他链表结构 519

11.1 单向链表的某些变种 519

11.1.1 带头节点的链表 519

11.1.2 循环链表 522

11.2 稀疏多项式的链式实现 526

11.3 双向链表和标准C++list 534

11.3.1 双向链表 534

11.3.2 标准list类模板 536

11.3.3 例：互联网地址 542

11.3.4 对C++中list的内部一瞥546

11.4 案例学习：长整数运算 551

11.4.1 问题 551

11.4.2 设计 551

11.4.3 实现 553

11.5 其他链列表 560

11.5.1 多序列表 560

11.5.2 稀疏矩阵 561

11.5.3 广义表 563

11.6 本章小结 566

第12章 二叉树和散列表 571

12.1 线性查找和折半查找的复习571

12.1.1 线性查找 572

12.1.2 折半查找 573

12.2 二叉树的介绍 576

12.2.1 树的定义 577

12.2.2 二叉树的一些例子 578

12.2.3 二叉树的数组表示 579

12.2.4 二叉树的链表表示 581

12.3 作为递归数据结构的二叉树583

12.4 二叉查找树 589

12.4.1 BST的实现 590

12.4.2 遍历BST 592

12.4.3 BST的查找 596

12.4.4 BST中的插入操作 599

12.4.5 从BST中删除一个节点 602

12.4.6 不平衡（Lopsidedness）

问题 612

12.5 案例学习：计算机登录验证616

12.5.1 问题 616

12.5.2 设计 616

12.5.3 编码 617

12.6 线索化二叉查找树（可选）620

12.7 散列表 624

12.7.1 散列函数 625

12.7.2 冲突处理策略 626

12.7.3 改进 627

12.8 本章小结 631

第13章 排序 636

13.1 某些计算时间为O(n2)的排序

方法 637

13.1.1 选择排序 637

13.1.2 交换排序 639

13.1.3 插入排序 641

13.1.4 排序算法的性能比较 643

13.1.5 间接排序 644

13.2 堆、堆排序和优先队列 647

13.2.1 堆 648

13.2.2 堆的基本操作 649

13.2.3 堆排序 652

13.2.4 STL中的堆算法 655

13.2.5 堆和优先队列 658

13.3 快速排序 662

13.3.1 拆分操作 663

13.3.2 快速排序 665

13.3.3 改进 668

13.4 归并排序 670

13.4.1 归并列表 670

13.4.2 折半归并排序 672

13.4.3 自然归并排序 674

13.5 基数排序（Radix Sort）677

13.6 本章小结 680

第14章 OOP和ADT 684

14.1 OOP和ADT的简要历史和概览684

14.1.1 封装性 685

14.1.2 继承性 686

14.1.3 多态性和动态联编 687

14.2 继承和面向对象设计 688

14.2.1 第1个例子：许可证 689

14.2.2 公有、私有和保护域 693

14.2.3 派生类的形式 693

14.2.4 类之间的Is-a、Has-a和

Uses-a关系 694

14.3 创建派生类 696

14.3.1 派生类构造函数 697

14.3.2 访问继承的数据成员 697

14.3.3 复用操作 698

14.3.4 例子：栈和有限栈 700

14.4 案例学习：工资 703

14.4.1 问题 703

14.4.2 设计 703

14.5 多态性、虚函数和ADT 711

14.5.1 为什么需要多态性：联编

问题 711

14.5.2 虚函数和动态联编 713

14.5.3 例1：使用句柄 716

14.5.4 例2：栈和有限栈 717

14.5.5 纯虚函数和抽象类 720

14.6 案例学习：异构数据结构722

14.6.1 虚函数的必要性 723

14.7 本章小结 726

第15章 树 729

15.1 案例学习：哈夫曼编码 729

15.1.1 变长码 730

15.1.2 立刻可解码性 730

15.1.3 哈夫曼编码 731

15.2 平衡树：AVL树 735

15.2.1 例子：州简称的BST 735

15.2.2 基本的重新平衡旋转

操作 743

15.3 2-3-4树、红-黑树、B-树和

其他树 748

15.3.1 2-3-4树 750

15.3.2 红-黑树 756

15.3.3 B-树 760

15.3.4 用二叉树来表示树和

森林 761

15.4 STL中的关联容器——

map（可选） 765

15.5 本章小结 771

第16章 图和有向图 773

16.1 有向图 773

16.1.1 邻接矩阵表示（Adjacency-

Matrix Representation） 775

16.1.2 邻接表表示（Adjacency-

List Representation） 776

16.2 搜索和遍历有向图 781

16.2.1 深度优先搜索 782

16.2.2 广度优先搜索 783

16.2.3 遍历和最短路经问题 785

16.2.4 NP完全性问题 794

16.3 图 796

16.3.1 邻接矩阵和邻接表表示797

16.3.2 边列表表示 798

16.3.3 连通性 799

16.4 本章小结 810

附录A ASCII字符集 812

附录B 小测验答案 814