数据结构与STL

出版者的话
专家指导委员会
译者序
前言
第1章 C＋＋中的类
1.1 类
1.1.1 方法接口
1.1.2 对象
1.1.3 数据抽象
1.1.4 构造器
1.1.5 一个Employee类
1.1.6 Employee类的定义
实验1：Company项目
1.1.7 继承
1.1.8 受保护的访问
1.1.9 HourlyEmployee类
实验2：关于继承的更多的细节
1.1.10 运算符的重载
1.1.11 友元
实验3：重载运算符“＝”和运算符“＞＞”
1.1.12 信息隐藏
总结
习题
编程项目1.1：一个Sequence类
第2章 容器类的存储结构
2.1 指针
2.1.1 堆和堆栈的对比
2.1.2 引用参数
2.1.3 指针字段
2.1.4 数组和指针
实验4：指针变量赋值与动态变量赋值的对比
2.1.5 动态变量的存储空间释放
2.2 数组
2.3 容器类
2.3.1 容器类的存储结构
2.3.2 链式结构
2.3.3 迭代器
2.3.4 Iteratror类的设计和实现
实验5：定义其他的选代器运算符
2.3.5 pop_front方法
2.3.6 析构器
实验6：重载运算符operator=
2.3.7 通用型算法
实验7：更多关于通用型算法的知识
2.3.8 数据结构和标准模板库
总结
习题
编程项目2.1：扩展Linked类
第3章 软件工程简介
3.1 软件开发生命周期
3.2 问题分析
3.3 程序设计
3.3.1 方法接口和字段
3.3.2 依赖关系图
3.4 程序实现
3.4.1 方法验证
实验8：驱动器
3.4.2 正确性实现的可行性
3.4.3 方法效率评估
3.4.4 大O表示法
3.4.5 快速获取大O估算
3.4.6 平衡折中
3.4.7 运行时间分析
3.4.8 随机性
实验9：计时和随机性
3.4.9 类型转换
3.5 程序维护
总结
习题
编程项目3.1：Linked类的进一步扩充
第4章 递归
4.1 简介
4.2 阶乘
4.3 十进制到二进制的转换
实验10：斐波纳契数
4.4 汉诺塔
4.5 回溯
4.6 折半查找
实验11：迭代折半查找
4.7 生成置换
4.8 间接递归
4.9 递归的代价
总结
习题
编程项目4.1：汉诺塔的选代版本
编程项目4.2：八皇后问题
编程项目4.3：马的遍历问题
第5章 向量和双端队列
5.1 标准模板库
5.2 向量
5.2.1 vector类的方法接口
5.2.2 向量迭代器
5.2.3 向量和其他容器的对比
5.2.4 vector类可能的字段
5.2.5 vector类的一个实现
实验12：vector类的更多的实现细节
5.3 向量的一个应用：高精度算法
5.3.1 very＿long＿int类的设计
5.3.2 very＿long＿int类的一个实现
实验13：扩展very＿long＿int类
5.4 双端队列
实验14：惠普的deque类实现的更多细节
5.5 双端队列的一个应用：非常长的整数
总结
习题
编程项目5.1：扩展very＿long＿int类
编程项目5.2：deque类的另一种实现
第6章 表
6.1 表
6.1.1 list类的方法接口
6.1.2 迭代器接口
6.1.3 链表方法和向量或双端队列方法的差别
6.1.4 list类的字段和实现
6.1.5 list节点的存储
实验15：更多list类的实现细节
实验16：计时顺序容器
实验17：迭代器，第二部分
6.1.6 list类的其他实现
6.2 链表应用：一个行编辑器
6.2.1 Editor类的设计
6.2.2 Editor类的实现
总结
习题
编程项目6.1：扩展Editor类
编程项目6.2：list类的另一种设计和实现
第7章 队列和堆栈
7.1 队列
7.1.1 queue类的方法接口
7.1.2 使用queue类
7.1.3 容器配接器
7.1.4 一个接近的设计
7.2 计算机仿真
7.3 队列应用：洗车仿真
7.3.1 程序设计
7.3.2 CarWash类的实现
7.3.3 CarWash方法的分析
7.3.4 随机化到达时间
实验18：随机化到达时间
7.4 堆栈
7.4.1 Stack类的方法接口
7.4.2 使用stack类
7.4.3 stack类是一个容器配接器
7.5 堆栈应用1：递归是如何实现的
7.6 堆栈应用2：将中缀转换成后缀
7.6.1 后缀表示法
7.6.2 转换矩阵
7.6.3 记号
实验19：将中缀转化成后缀
7.6.4 前缀表示法
总结
习题
编程项目7.1：扩展洗车仿真
编程项目7.2：求一个条件的值
编程项目7.3：一个迭代的迷宫搜索
编程项目7.4：queue类的另一个设计
第8章 二叉树和折半查找树
8.1 定义和属性
8.1.1 二叉树定理
8.1.2 外部路径长度
8.1.3 二叉树的遍历
8.2 折半查找树
8.2.1 BinSearchTree类
8.2.2 BinSearchTree类的Iterator类
8.2.3 BinSearchTree类的字段和实现
8.2.4 递归方法
8.2.5 BinSearchTree迭代器
实验20：BinSearchTree的平均高度
总结
习题
编程项目8.1：BinSearchTree类的另一种实现
第9章 AVL树
9.1 平衡的折半查找树
9.2 旋转
9.3 AVL树
9.3.1 AVL树的高度
9.3.2 函数对象
实验21：更多的函数对象的细节
9.3.3 AVLTree类
9.3.4 fixAfterInsertion方法
9.3.5 insert方法的正确性
9.4 AVL树的应用：一个简单的拼写检查器
总结
习题
编程项目9.1：AVLTree类的erase方法
编程项目9.2：改进的SpellChecker项目
第10章 红黑树
10.1 红黑树
10.1.1 红黑树的高度
10.1.2 惠普的rb_tree类
10.1.3 rb_tree类中的insert方法
实验22：使用全部三种情况的红黑树插入
10.1.4 erase方法
实验23：erase的调用，其中应用了全部四种情况
10.2 标准模板库的关联容器
10.3 集合应用：再次讨论拼写检查器
10.3.1 multiset类
实验24：更多与set和multiset类相关的知识
10.3.2 map类
10.3.3 multimap类
实验25：更多与map和multimap类相关的知识
总结
习题
编程项目10.1：一个简单的辞典
编程项目10.2：创建一个词汇索引
第11章 优先队列和堆
11.1 介绍
11.1.1 priority_queue类
11.1.2 priority_queue类的字段和实现
11.1.3 堆
实验26：优先队列中的公平性
11.1.4 priority_queue类的另一种设计及实现
11.2 优先队列的应用：霍夫曼编码
11.2.1 huffman类的设计
11.2.2 huffman类的实现
总结
习题
编程项目11.1：解码一个消息
第12章 排序
12.1 介绍
12.2 排序能有多快
12.3 快速排序
12.3.1 树排序
12.3.2 堆排序
12.3.3 归并排序
12.3.4 快速排序
12.3.5 分治法算法
实验27：排序算法的运行时间
总结
习题
编程项目12.1：排序一个文件
第13章 查找和散列类
13.1 分析查找的框架
13.2 查找方式复习
13.2.1 顺序查找
13.2.2 折半查找
13.2.3 红黑树查找
13.3 hash_map类
13.3.1 hash_map类中的字段
13.3.2 散列
13.3.3 链式
13.3.4 iterator类的字段和实现
13.3.5 hash_map类的实现
13.3.6 链式散列分析
13.3.7 value_type类
13.3.8 应用
实验28：hash_map计时
13.4 hash_set类
13.5 开放地址散列
13.5.1 erase方法
13.5.2 主聚类
13.5.3 双散列
13.5.4 开放地址散列分析
总结
习题
编程项目13.1：使用链式和双散到构造一个符号表的运行时间比较
第14章 图、树和网络
14.1 无向图
14.2 有向图
14.3 树
14.4 网络
14.5 图算法
14.5.1 迭代器
14.5.2 连通性
14.5.3 产生最小生成树
14.5.4 寻找网络中的最短路径
14.6 开发一个网络类
14.7 network类
14.7.1 network类中的字段
14.7.2 network类的实现
14.7.3 与边相关的方法的实现
14.7.4 全局方法的实现
14.7.5 get_minimum_spanning_tree方法
14.7.6 get_shortest_path方法
14.7.7 网络方法的时间花费估算
实验29：货郎担问题
14.7.8 network类的另一种设计和实现
14.8 回溯通过网络
总结
习题
编程项目14.1：完成邻接矩阵的实现
编程项目14.2：回溯通过一个网络
附录1 数学背景
附录2 string类
附录3 多态性
参考文献
索引