第1章 软件开发

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

1.2 设计

1.2.1 自顶向下设计

1.2.2 面向对象设计

1.2.3 小规模设计

1.3 编码

1.4 测试、运行和调试

1.5 维护

1.6 本章小结

第2章 抽象数据类型入门

2.1 对ADT及其实现的第一瞥

2.2 C＋＋的简单数据类型

2.2.1 整型数据

2.2.2 实型数据

2.2.3 字符数据

2.4.4 布尔数据

2.3.1 Typedefs

2.3.2 枚举

2.3 程序员定义的数据类型

2.3.3 类

2.4 指针

2.4.1 声明和初始化指针

2.4.2 基本指针操作

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

2.4.4 关于引用形参的注释

2.5 本章小结

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

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

3.2 静态数组

3.2.1 一维静态数组

3.2.2 下标运算

3.2.3 数组作为形参

3.2.4 越界错误

3.2.5 数组的问题

3.3 多维数组

3.3.1 二维数组

3.3.2 高维数组

3.3.3 数组的数组声明

3.3.4 多维数组作函数参数

3.4 动态数组

3.4.1 new操作——动态数组

3.4.2 指针的其他用法

3.5 C风格结构（可选）

指向结构的指针

3.6 过程式编程

过程式编程的例子

3.7 本章小结

4.1 过程式编程vs．面向对象编程

第4章 OOP和ADT进阶——类

4.2 类

4.2.1 “传统的”（C）结构和OOP（C＋＋）结构以及类之间的区别

4.2.2 类声明

4.3 例子：用户定义的Time类的第一个版本

4.3.1 为什么不使所有成员都公有化

4.3.2 实现一个类

4.3.3 一些现象

4.4 类构造函数

4.5.1 复制操作——初始化和赋值

4.5 其他类操作

4.5.2 访问函数和更动函数

4.5.3 重载运算符

4.5.4 重载输入／输出运算符

4.5.5 其他操作：前进和关系操作

4.5.6 总结以及其他一些细节

4.5.7 指向类对象的指针

4.5.8 this指针

4.6 本章小结

第5章 标准C＋＋输入／输出和字符串类

5.1 C＋＋标准I/O类

5.1.1 istream类

5.1.2 ostream类

5.1.3 文件I/O:ifstream和ofstream类

5.1.4 I/O类层次

5.2 C++ String类型

5.2.1 C风格的字符串

5.2.2 一个字符串类

5.2.3 C++ String类

5.2.4 String流

5.3 案例学习：文本编辑

5.4 模式匹配介绍（可选）

5.5 数据加密介绍（可选）

5.5.1 数据加密标准（Data Encryption Standard）

5.5.2 公共密钥加密（Public-Key Encryption）

5.6 本章小结

第6章 列表

6.1 作为ADT的列表

设计和创建一个列表类

6.2.1 选择存储结构

6.2 基于数组的列表实现

6.2.2 实现操作

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

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

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

6.3.2 最后一点

6.4 对链表的介绍

6.4.1 它们是什么

6.4.2 实现基本列表操作

6.4.3 小结

6.5.1 节点结构

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

6.5.2 链表实现中的数据成员

6.5.3 链表实现中的函数成员

6.6 基于数组的链表实现

6.6.1 节点结构

6.6.2 存储池管理

6.7 本章小结

第7章 栈

7.1 栈的介绍

7.2.1 选择存储结构

7.2 设计和创建一个Stack类——基于数组

7.2.2 实现操作

7.2.3 实现pop操作的算法

7.2.4 完整的Stack类

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

7.2.6 前瞻

7.3 链式栈

7.3.1 选择存储结构

7.3.2 实现操作

7.3.3 完整的Stack类：链表版本

7.4 栈在函数调用中的使用

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

7.5.1 计算后缀表达式

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

7.6 本章小节

第8章 队列

8.1 队列入门

8.2 设计和创建一个Queue类——基于数组

8.2.1 使用静态数组存储队列元素

8.2.2 使用动态数组存储队列元素

8.3.1 一种自然的链表实现

8.3 链式队列

8.3.2 使用循环链表

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

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

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

8.5.2 创建一个Simulation类

8.5.3 Time类和Call类

8.6 本章小结

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

9.1.1 从算法到算法

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

9.1.2 从数据到容器

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

9.2.1 重载

9.2.2 函数模板

9.2.3 另一个例子：显示一个数组

9.3 类通用性——模板

9.3.1 Typedef有什么错

9.3.2 类模板

9.3.3 Stack类模板的另一个版本

9.3.4 对标准C＋＋容器类模板的快速一瞥

9.4 vector容器

9.4.1 定义vector对象

9.4.2 一些vector操作

9.4.3 内部实现一瞥——增加容量

9.4.4 对迭代器的第一次探讨

9.4.5 一些牵涉到迭代器的vector函数成员

9.4.6 综合比较：vector对数组

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

9.6.1 二维vector对象

9.6 多维vector（可选）

9.6.2 二维vector操作

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

9.7.1 STL的deque类模板

9.7.2 我们的stack类模板的一个新（但是非必须的）版本

9.7.3 STL的stack适配器

9.7.4 STL的queue适配器

9.8 Bitset和Valarray（可选）

9.8.1 Bitset

9.8.2 Valarray

9.8.3 Slics、Mask、以及间接数组

9.9 本章小结

第10章 ADT实现——递归、算法分析以及标准算法

10.1 递归

10.1.1 递归的例子

10.1.2 递归函数的编码

10.1.3 糟糕递归的例子：Fibonacci数字

10.1.4 例子：折半查找

10.1.5 例子：回文检查程序

10.2.1 Hanoi塔

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

10.2.2 分析

10.3 实现递归

10.4 算法效率

10.5 C＋＋中的标准算法

10.5.1 例：STL的sort算法

10.5.2 STL算法的例子

10.5.3 ＜numeric＞库中的算法

10.5.4 例：花样滑冰评判

10.6 算法正确性证明（可选）

10.6.1 例：计算平均值

10.6.2 例：递归求幂函数

10.6.3 总结

10.7 本章小节

第11章 其他链表结构

11.1 单向链表的某些变种

11.1.1 带头节点的链表

11.1.2 循环链表

11.2 稀疏多项式的链式实现

11.3.1 双向链表

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

11.3.2 标准list类模板

11.3.3 例：互联网地址

11.3.4 对C＋＋中list的内部一瞥

11.4 案例学习：长整数运算

11.4.1 问题

11.4.2 设计

11.4.3 实现

11.5.1 多序列表

11.5 其他链列表

11.5.2 稀疏矩阵

11.5.3 广义表

11.6 本章小结

第12章 二叉树和散列表

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

12.1.1 线性查找

12.1.2 折半查找

12.2 二叉树的介绍

12.2.1 树的定义

12.2.2 二叉树的一些例子

12.2.3 二叉树的数组表示

12.2.4 二叉树的链表表示

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

12.4 二叉查找树

12.4.1 BST的实现

12.4.2 遍历BST

12.4.3 BST的查找

12.4.4 BST中的插入操作

12.4.5 从BST中删除一个节点

12.4.6 不平衡（Lopsidedness）问题

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

12.5.1 问题

12.5.2 设计

12.5.3 编码

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

12.7 散列表

12.7.1 散列函数

12.7.2 冲突处理策略

12.7.3 改进

12.8 本章小结

第13章 排序

13.1 某些计算时间为O（n2）的排序方法

13.1.1 选择排序

13.1.2 交换排序

13.1.3 插入排序

13.1.4 排序算法的性能比较

13.1.5 间接排序

13.2 堆、堆排序和优先队列

13.2.1 堆

13.2.2 堆的基本操作

13.2.3 堆排序

13.2.4 STL中的堆算法

13.2.5 堆和优先队列

13.3 快速排序

13.3.1 拆分操作

13.3.2 快速排序

13.3.3 改进

13.4 归并排序

13.4.1 归并列表

13.4.2 折半归并排序

13.4.3 自然归并排序

13.5 基数排序（Radix Sort）

13.6 本章小结

第14章 OOP和ADT

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

14.1.1 封装性

14.1.2 继承性

14.1.3 多态性和动态联编

14.2 继承和面向对象设计

14.2.1 第1个例子：许可证

14.2.2 公有、私有和保护域

14.2.3 派生类的形式

14.2.4 类之间的Is-a、Has-a和Uses-a关系

14.3 创建派生类

14.3.1 派生类构造函数

14.3.2 访问继承的数据成员

14.3.3 复用操作

14.3.4 例子：栈和有限栈

14.4.1 问题

14.4.2 设计

14.4 案例学习：工资

14.5 多态性、虚函数和ADT

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

14.5.2 虚函数和动态联编

14.5.3 例1：使用句柄

14.5.4 例2：栈和有限栈

14.5.5 纯虚函数和抽象类

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

14.6.1 虚函数的必要性

14.7 本章小结

第15章 树

15.1 案例学习：哈夫曼编码

15.1.1 变长码

15.1.2 立刻可解码性

15.1.3 哈夫曼编码

15.2 平衡树：AVL树

15.2.1 例子：州简称的BST

15.2.2 基本的重新平衡旋转操作

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

15.3.1 2-3-4树

15.3.2 红-黑树

15.3.3 B-树

15.3.4 用二叉树来表示树和森林

15.4 STL中的关联容器——map（可选）

15.5 本章小结

第16章 图和有向图

16.1 有向图

16.1.1 邻接矩阵表示（Adjacency-Matrix Representation）

16.1.2 邻接表表示（Adjacency-List Representation）

16.2 搜索和遍历有向图

16.2.1 深度优先搜索

16.2.2 广度优先搜索

16.2.3 遍历和最短路经问题

16.2.4 NP完全性问题

16.3 图

16.3.1 邻接矩阵和邻接表表示

16.3.2 边列表表示

16.3.3 连通性

16.4 本章小结

附录A ASCll字符集

附录B 小测验答案