数据结构：C++与面向对象的途径（修订版）

第一章 绪论
1.1 问题求解
1.1.1 问题
1.1.2 问题的分析
1.].3 算法的选择
1.1.4 解的精化
1.2 数据结构
1.3 算法
1.3.1 算法的设计
1.3.2 算法的分析
1.4 抽象数据类型
1.5 程序设计方法和语言
小结
习题
第二章 C++与面向对象初步
2.1 C++语言对C的基本扩充
2.1.1 注释
2.1.2 函数原型说明
2.1.3 引用和引用参数
2.1.4 重载
2.1.5 缺省参数
2.1.6 变量说明
2.1.7 输入和输出
2.1.8 动态存储分配
2.1.9 类型定义
2.1.10 强制类型转换
2.2 对象和类
2.3 类的界面描述和实现
2.3.1 类的数据域
2.3.2 对象的行为——成员函数
2.3.3 运算符作为成员函数
2.3.4 用构造函数进行实例的初始化
2.4 普通运算符和普通函数
2.4.1 普通运算符
2.4.2 普通函数
2.4.3 输入和输出
2.5 类的合成、继承和多态性
2.5.1 合成
2.5.2 继承
2.5.3 多态性
小结
习题
第三章 字符串——数据封装技术
3.1 C语言的字符和字符串
3.2 字符串数据抽象的描述和实现
3.2.1 字符串类的定义
3.2.2 构造函数的定义
3.2.3 析构函数
3.2.4 基本成员函数的实现
3.2.5 比较运算符
3.2.6 串连接
3.2.7 输入和输出
3.3 子串
3.4 模式匹配
3.4.1 简单字符串匹配
3.4.2 Knuth-Morris.Pratt模式匹配算法
3.4.3 Boycr－Moom字符串匹配算法
小结
习题
第四章 向量——类的重用技术
4.1 模板类
4.2 向量的实现
4.3 定界向量和枚举向量、——继承方式的重用
4.3.1 定界向量
4.3.2 枚举向量
4.4 排序向量和矩阵——合成方式的重用
4.4.1 排序向量和二分法检索
4.4.2 矩阵
4.5 向量遍历器
4.5.1 遍历器的抽象
4.5.2 向量遍历器
4.6 向量的排序——模板函数
4.6.1 插入排序
4.6.2 起泡排序
4.6.3 选择排序
4.6.4 快速排序算法
4.7 继承和多态的若干讨论
4.7.1 父类与子类
4.7.2 静态类型和动态类型
4.7.3 框架和框架类
4.7.4 蔽和虚函数
4.7.5 虚遮蔽和非虚遮蔽
4.7.6 两类继承
4.7.7 多态的主要形式
4.7.8 参数多态性——归约
4.7.9 切割问题
小结
习题
第五章 动态数据结构——链表
5.1 单链表的定义
5.1.1 表类
5.1.2 链类
5.2 单链表的实现
5.2.1 链类的实现
5.2.2 表类的实现
5.3 表遍历器
5.3.1 表遍历器类
5.3.2 表遍历器类的实现表的应用：多项式处理
5.4.1 项类
5.4.2 多项式类
5.5 排序表
5.5.1 排序表类
5.5.2 排序表类的实现
5.5.3 排序表的应用——表插入排序
5.6 其他链表
5.6.1 自组织表
5.6.2 双端表
5.6.3 循环表
5.6.4 双链表
5.7 可利用空间表
小结
习题
第六章 栈和队列
6.1 抽象类栈和队列
6.2 栈的实现
6.2.1 栈的向量实现
6.2.2 栈的链表实现
6.3 栈的应用——表达式计算
6.3.1 后缀表达式的求值
6.3.2 中缀表达式到后缀表达式的转换
6.4 队列的实现
6.4.1 队列的向量实现
6.4.2 队列的链表实现
6.5 队列的应用——农夫过河问题
小结
习题
第七章 树和二叉树
7.1 基本概念
7.1.1 树
7.1.2 二叉树山
7.1.3 树与二叉树的关系
7.2 二叉树的实现
7.2.1 二叉树结点类
7.2.2 基本二叉树类
7.2.3 可构造二叉树类
7.3 二叉树的周游
7.3.1 周游的递归实现
7.3.2 通过遍历器实现周游
7.3.3 前序周游器类
7.3.4 中序周游器类
7.3.5 后序周游器类
7.3.6 层次周游算法(按宽度方向周游)
7.4 二叉树的向量表示
7.4.1 二叉树向量表示的一种基本方法
7.4.2 记录结构信息的二叉树向量表示
7.5 二叉排序树
7.6 平衡的二叉排序树
7.6.1 AVL树上的操作
7.6.2 AVL树的设计与实现
7.7 二叉树的应用——哈夫曼树
小结
习题
第八章 优先队列
8.1 优先队列的抽象
8.2 堆
8.3 堆排序
8.4 斜堆
8.5 离散事件模拟
8.5.1 模拟类的结构
8.5.2 冰淇淋店的模拟
8.5.3 随机数
小结
习题
第九章 集合与字典
9.1 集合及其运算
9.1.1 集合运算
9.1.2 集合类
9.2 位向量集合
9.2.1 位向量
9.2.2 位向量集合
9.2.3 字符集合
9.2.4 字符集类的应用——将字符串分解为单词
9.3 集合的表实现
9.4 关联与字典
9.5 字典的关联表实现
9.6 字典的应用
9.6.1 稀疏矩阵
9.6.2 排序字典
9.6.3 索引的实现
小结
习题
第十章 散列结构
10.1 散列结构
10.2 散列函数
10.3 开地址散列向量
10.4 桶散列——用桶解决碰撞
10.4.1 桶散列的抽象模板类
10.4.2 用树作为桶的实现
10.4.3 桶散列结构操作时间的分析
10.5 桶散列结构的遍历器
10.6 用散列表实现集合
10.6.1 应用——拼写检查器
10.7 用桶散列表实现字典
小结
习题
第十一章 图
11.1 基本概念
11.2 图的邻接矩阵表示和Warshall算法
11.2.1 图的邻接矩阵表示
11.2.2 图结点的可达性问题
11.3 邻接表方式的图表示和深度优先搜索
11.3.1 邻接表表示中的结点类
11.3.2 用深度优先方式求解可达性问题
11.4 带权图的矩阵表示和Floyd算法
11.4.1 带权图的邻接矩阵
11.4.2 带权图最短路径问题Floyd算法
11.5 带权图的邻接表表示与Dijkstra算法
11.5.1 带权图的邻接表表示
11.5 ，2从一个结点出发的最短路径和Dijkstra算法
11.6 连通性、带权连通无向图与最小生成树
11.7 有限自动机
11.8 拓扑排序
小结
习题
第十二章 文件
12.1 外存、文件及其问题
12.1.1 外存储器的特点与信息组织
12.1.2 文件基本结构和操作
12.1.3 文件与字典
12.1.4 文件组织
12.2 C++的字符流文件及其操作
12.3 归并排序
12.4 文件的随机访问
12.5 文件索引结构
12.5.1 索引向量
12.5.2 树形索引结构
12.5.3 B树
12.5.4 B+树
12.6 树索引文件的实现
小结
习题
附录
附录A 主要抽象数据类及其相互关系
附录B BorlandC++集成开发环境使用入门
附录C “多叉路口的交通管理系统
上机报告