数据结构与算法：面向对象的C++设计模式

第1章 概要

1. 1 本书的主要内容

1. 2 面向对象的设计

1. 3 对象分级与设计方法

1. 4 需要了解的C++特性

1. 5 本书是如何组织的？

第2章 算法分析

2. 1 一个细化的计算机模型

2. 1. 1 基本公理

2. 1. 2 例豆：算术级数求和

2. 1. 3 数组下标操作

2. 1. 4 例2：霍纳（Horner）法则

2. 1. 5 分析递归函数

2. 1. 6 例3：找出数组中最大元素

2. 1. 7 平均运行时间

2. 1. 8 关于调和数

2. 1. 9 最佳情况与最差情况的运行时间

2. 1. 10 最后的公理

2. 2 一个简化的计算机模型

2. 2. 1 例l, 求几何级数之和

2. 2. 2 关于算术级数求和

2. 2. 3 例2：再次求几何级数之和

2. 2. 4 关于几何级数求和

2. 2. 5 例3：幂计算

2. 2. 6 例4：再三求几何级数之和

习题

设计项目

第3章 渐近表示法

3. 1 渐近上界--大O表示法

3. 1. 1 一个简单的例子

3. 1. 2 大O表示法中的错误与陷阱

3. 1. 3 大O的特性

3. 1. 4 多项式

3. 1. 5 对数

3. 1. 6 紧凑大O界

3. 1. 7 大O表示法中更多的错误与陷阱

3. 1. 8 常用的大O表达式

3. 2 渐近下界--Ω表示法

3. 2. 1 一个简单的例子

3. 2. 2 再次关于多项式

3. 3 更多的表示法--θ及小o表示法

3. 4 算法渐近分析

3. 4. 1 运行时间分析的大O规则

3. 4. 2 例1：求级数的前项和

3. 4. 3 例2：Fibonacci数

3. 4. 4 例3：桶式排序

3. 4. 5 现实检查

3. 4. 6 检查你的分析

习题

设计项目

第4章 基本数据结构

4. 1 动态数组

4. 1. 1 缺省构造函数

4. 1. 2 数组构造函数

4. 1. 3 备份构造函数

4. 1. 4 析构函数

4. 1. 5 数组成员函数

4. 1. 6 数组下标操作符

4. l. 7 数组大小的重调

4. 2 单链表

4. 2. 1 链表的实现

4. 2. 2 链表元素

4. 2. 3 缺省构造函数

4. 2. 4 析构函数与Purge成员函数

4. 2. 5 存取器

4. 2. 6 First与Last函数

4. 2. 7 前插

4. 2. 8 添加

4. 2. 9 备份构造函数与赋值操作符

4. 2. 10 析取函数

4. 2. 11 InsertAfter与InsertBefore函数

4. 3 多维数组

4. 3. 1 数组下标计算

4. 3. 2 二维数组的实现

4. 3. 3 C＋十中多维数组的下标

4. 3. 4 例：规范矩阵相乘

习题

设计项目

第5章 数据类型与抽象

5. 1 抽象数据类型

5. 2 设计模式

5. 2. 1 类层次

5. 2. 2 对象

5. 2. 3 NullObject单元集类

5. 2. 4 内嵌类型的对象包装

5. 2. 5 容器

5. 2. 6 访问者

5. 2. 7 迭代器

5. 2. 8 NullIterator类

5. 2. 9 直接存储与间接存储

5. 2. 10 被包含对象的所有权

5. 2. 11 关联

5. 2. 12 可搜索容器

习题

设计项目

第6章 栈. 队列及双端队列

6. 1 栈

6. 1. 1 栈的数组表示法

6. 1. 2 栈的链表表示法

6. 1. 3 应用

6. 2 队列

6. 2. 1 队列的数组表示法

6. 2. 2 队列的链表表示法

6. 2. 3 应用

6. 3 双端队列

6. 3. l 双端队列的数组表示法

6. 3. 2 双端队列的链表表示法

6. 3. 3 双向链表及循环链表

习题

设计项目

第7章 有序线性表与排序表

7. 1 有序线性表

7. 1. 1 有序线性表的数组表示法

7. 1. 2 有序线性表的链表表示法

7. 1. 3 比较ListAsArray和ListAsLinkedList

7. 1. 4 应用

7. 2 排序表

7. 2. 1 排序表的数组表示法

7. 2. 2 排序表的链表表示法

7. 2. 3 比较SortedListAsArrny和SortedListAsLinkedList

7. 2. 4 应用

习题

设计项目

第8章 散列. 哈希表及分散表

8. 1 散列的基本知识

8. 1. 1 关键字和散列函数

8. 2 散列法

8. 2. 1 相除散列法

8. 2. 2 平方取中散列法

8. 2. 3 相乘散列法

8. 2. 4 Fibonacci散列法

8. 3 散列函数的实现

8. 3. 1 整型关键字

8. 3. 2 浮点型关键字

8. 3. 3 字符串关键字

8. 3. 4 散列对象

8. 3. 5 散列容器

8. 3. 6 使用关联

8. 4 哈希表

8. 4. 1 拉链法

8. 4. 2 平均情况分析

8. 5 分散表

8. 5. 1 链式分散表

8. 5. 2 平均情况分析

8. 6 使用开地址法的分散表

8. 6. 1 线性探查

8. 6. 2 二次探查

8. 6. 3 双散列法

8. 6. 4 开地址法的实现

8. 6. 5 平均情况分析

8. 7 应用

习题

设计项目

第9章 树

9. 1 基础

9. 2 N叉树

9. 3 二叉树

9. 4 树的遍历

9. 5 表达式树

9. 6 树的实现

9. 6. 1 树的遍历

9. 6. 2 树迭代器

9. 6. 3 广义树

9. 6. 4 N叉树

9. 6. 5 二叉树

9. 6. 6 二叉树的遍历

9. 6. 7 树的比较

9. 6. 8 应用

习题

设计项目

第10章 查找树

10. 1 基础知识

10. 1. 1 M路查找树

10. 1. 2 二叉查找树

10. 2 搜索查找树

10. 2. 1 搜索M路查找树

1O. 2. 2 搜索二叉树

10. 3 平均情况分析

10. 3. 1 搜索成功

10. 3. 2 递归关系的求解--拓展速归法

10. 3. 3 搜索失败

10. 3. 4 查找树的遍历

10. 4 查找树的实现

10. 4. 1 二叉查找树

10. 4. 2 在二叉查找树中插入数据项

10. 4. 3 从二叉查找树中删除数据项

10. 5 AVL查找树

10. 5. 1 AVL树的实现

10. 5. 2 在AVL树中插人数据项

10. 5. 3 从AVL树中删除数据项

10. 6 M路查找树

10. 6. 1 M路查找树的实现

10. 6. 2 在M路查找树中查找数据项

10. 6. 3 在M路查找树中插人数据项

10. 6. 4 从M路查找树中删除数据项

10. 7 B树

10. 7. 1 B树的实现

10. 7. 2 在B树中插人数据项

10. 7. 3 从B树中删除数据项

10. 8 应用

习题

设计项目

第11章 堆和优先队列

11. 1 基础知识

11. 2 二叉堆

11. 2. 1 完全树

11. 2. 2 二叉堆的实现

11. 2. 3 在二叉堆中插入数据项

11. 2. 4 从二叉堆中删除数据项

11. 3 左翼堆

11. 3. 1 左翼树

11. 3. 2 左翼堆的实现

11. 3. 3 左翼堆的合并

11. 3. 4 在左翼堆中插入数据项

11. 3. 5 从左翼堆中删除数据项

11. 4 二项队列

11. 4. 1 二项树

11. 4. 2 二项队列

11. 4. 3 实现

11. 4. 4 二项队列的合并

11. 4. 5 在二项队列中插入数据项

11. 4. 6 从二项队列中删除数据项

11. 5 应用

11. 5. 1 离散事件模拟

11. 5. 2 实现

习题

设计项目

第12章 集合. 多重集和分区

12. 1 基础知识

12. 1. 1 集合的实现

12. 2 数组和位矢量集合

12. 2. 1 位矢量集合

12. 3 多重集

12. 3. 1 多重集的数组表示法

12. 3. 2 多重集的链表表示法

12. 4 分区

12. 4. 1 用森林表示分区

12. 4. 2 折叠查找

12. 4. 3 按大小合并

12. 4. 4 按高度或层号合并

12. 5 应用

习题

设计项目

第13章 动态存储分配：另一种堆

13. 1 基础

13. 1. 1 C++ Magic

13. 1. 2 堆

13. 2 单链自由存储器

13. 2. 1 实现

13. 3 双链自由存储器

13. 3. 1 实现

13. 4 伙伴存储管理系统

13. 4. 1 实现

13. 5 应用

13. 5. 1 实现

习题

设计项目

第14章 算法模式和问题求解

14. 1 蛮干算法和贪心算法

14. 1. 1 例1：数钱

14. 1. 2 例2：0／l背包问题

14. 2 回溯算法

14. 2. 1 例1：平衡称

14. 2. 2 解空间的表示

14. 2. 3 抽象回溯求解程序

14. 2. 4 分支界限求解程序

14. 2. 5 例2：再次分析0/1背包问题

14. 3 自顶向下算法：分治算法

14. 3. 1 例1：二分法查找

14. 3. 2 例2：求解Fibonacci数

14. 3. 3 例3：归并排序

14. 3. 4 分治算法的运行时间

14. 3. 5 例个矩阵相乘

14. 4 自底向上算法：动态程序设计

14. 4. 1 例1：广义Fibonacci数

14. 4. 2 例2：求解二项式系数

14. 4. 3 应用：排版问题

14. 5 随机化算法

14. 5. 1 产生随机数

14. 5. 2 随机变量

14. 5. 3 蒙特卡罗法

14. 5. 4 模拟退火法

习题

设计项目

第15章 排序算法和排序器

15. 1 基础知识

15. 2 排序和排序器

15. 3 插入排序

15. 3. 1 直接插入排序

15. 3. 2 平均运行时间

15. 3. 3 二分法插入排序

15. 4 交换排序

15. 4. 1 冒泡排序

15. 4. 2 快速排序

15. 4. 3 运行时间分析

15. 4. 4 平均运行时间

15. 4. 5 轴值的选择

15. 5 选择排序

15. 5. 1 直接选择排序

15. 5. 2 堆排序

15. 5. 3 堆的建立

15. 6 归并排序

15. 7 排序算法的下界

15. 8 分配排序

15. 8. 1 桶式排序

15. 8. 2 基数排序

15. 9 算法性能分析

习题

设计项目

第16章 图和图算法

16. 1 基础知道

16. 1. 1 图的表示法

16. 2 图的实现

16. 2. 1 顶点的实现

16. 2. 3 抽象图和有向图

16. 2. 4 无向图的实现

16. 2. 5 边带权图和顶点带权图

16. 2. 6 图表示法的比较

16. 3 图的遍历

16. 3. 1 深度优先遍历

16. 3. 2 广度优先遍历

16. 3. 3 拓扑排序

16. 3. 4 图遍历的应用：检查图的回路及连通性

16. 4 最短路径算法

16. 4. 1 单源最短路径

16. 4. 2 每对顶点间的最短路径

16. 5 最小支撑树

16. 5. 1 Prim算法

16. 5. 2 Kruskal算法

16. 6 应用：关键路径分析

习题

设计项目

附录A C++与面向对象编程

附录B 类层次图

附录C 字符码

参考答案