Fundamentals of data structures in C++

目录
第1章 基本概念
1.1 概述：系统生命周期
1.2 面向对象的程序设计
1.2.1 算法分解与面向对象分解
1.2.2 基本定义和面向对象编程的概念
1.2.3 程序设计语言的演化和C++语言历史
1.3 数据抽象和封装
1.4 C++语言基础
1.4.1 C++程序的组织结构
1.4.2 C++语言的作用域
1.4.3 C++的语句与操作符
1.4.4 C++语言中的数据声明
1.4.5 C++语言的注释
1.4.6 C++语言的输入输出
1.4.7 C++语言的函数
1.4.8 C++语言的参数传递
1.4.9 C++语言的函数名重载
1.4.10 内联函数
1.4.11 C++语言的动态内存分配
1.4.12 例外
1.5 算法规范
1.5.1 概述
1.5.2 递归算法
1.6 标准模板库
1.7 性能分析和度量
1.7.1 性能分析
1.7.2 性能度量
1.7.3 测试数据的生成
1.8 参考文献和推荐读物
第2章 数组
2.1 抽象数据类型和C++类
2.1.1 C++类介绍
2.1.2 C++语言中的数据抽象和封装
2.1.3 声明类对象和调用成员函数
2.1.4 特别类操作
2.1.5 其他主题
2.1.6 ADT和C++类
2.2 将数组作为一种抽象数据类型
2.3 多项式抽象数据类型
2.3.1 多项式的表示
2.3.2 多项式的加法
2.4 稀疏矩阵
2.4.1 绪论
2.4.2 稀疏矩阵的表示法
2.4.3 转置一个矩阵
2.4.4 矩阵的乘法
2.5 多维数组的表示
2.6 字符串抽象数据类型
2.6.1 一种简单的字符串模式匹配算法
2.6.2 字符串模式匹配：Knuth-Morris-Pratt算法
2.7 参考文献和推荐读物
2.8 附加习题
第3章 栈和队列
3.1 C++模板
3.1.1 模板函数
3.1.2 用模板表示容器类
3.2 栈的抽象数据类型
3.3 队列抽象数据类型
3.4 C++中的子类型和继承
3.5 一个迷宫问题
3.6 计算表达式
3.6.1 表达式
3.6.2 后缀表达式
3.6.3 中缀表达式转换成后缀表达式
3.7 附加习题
第4章 链表
4.1 单链表和链
4.2 用C++语言表示链表
4.2.1 在C++语言中定义结点
4.2.2 用C++语言设计一个链表类
4.2.3 C++语言中的指针操作
4.2.4 链表的控制操作
4.3 链的模板类
4.3.1 用模板实现链表
4.3.2 链表迭代器
4.3.3 链表操作
4.3.4 类的重用
4.4 循环链表
4.5 可用空间链表
4.6 链式栈和链式队列
4.7 多项式
4.7.1 多项式的表示
4.7.2 多项式相加
4.7.3 用循环链表表示多项式
4.8 等价类
4.9 稀疏矩阵
4.9.1 稀疏矩阵的表示
4.9.2 稀疏矩阵的输入
4.9.3 删除稀疏矩阵
4.10 双向链表
4.11 广义表
4.11.1 广义表的表示
4.11.2 表的递归算法
4.11.3 引用计数、共享和递归表
第5章 树
5.1 概述
5.1.1 术语表
5.1.2 树的表示
5.2 二叉树
5.2.1 抽象数据类型
5.2.2 二叉树的性质
5.2.3 二叉树的表示
5.3 二叉树的遍历和迭代程序
5.3.1 概述
5.3.2 中序遍历
5.3.3 先序遍历
5.3.4 后序遍历
5.3.5 迭代中序遍历
5.3.6 层次遍历
5.3.7 不使用栈的遍历
5.4 补充的二叉树操作
5.4.1 复制二叉树
5.4.2 检测相等
5.4.3 满足性问题
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 二叉查找树
5.7.1 定义
5.7.2 二叉查找树的查找
5.7.3 二叉查找树的插入
5.7.4 二叉查找树的删除
5.7.5 二叉树的连接和分裂
5.7.6 二叉查找树的高度
5.8 选择树
5.8.1 概述
5.8.2 胜者树
5.8.3 败者树
5.9 森林
5.9.1 将森林转换成二叉树
5.9.2 森林的遍历
5.10 离散集合表示
5.10.1 概述
5.10.2 并和查找操作
5.10.3 等价类的应用
5.11 二叉树计数
5.11.1 不同的二叉树
5.11.2 栈排列
5.11.3 矩阵相乘
5.11.4 不同二叉树的个数
5.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.2.4 生成树
6.2.5 重连通分量
6.3 最小代价生成树
6.3.1 克鲁斯卡尔算法
6.3.2 普里姆算法
6.3.3 索林算法
6.4 最短路径和传递闭包
6.4.1 单源/多目标：非负权值
6.4.2 单源/多目标：任意权值
6.4.3 多源最短路径
6.4.4 传递闭包
6.5 活动网络
6.5.1 顶点表示活动的网络(AOV网)
6.5.2 用边表示活动的网络(AOE网)
6.5.3 事件最早发生时间的计算
6.5.4 事件最迟发生时间的计算
6.6 参考文献和推荐读物
6.7 附加习题
第7章 排序
7.1 目的
7.2 插入排序
7.3 快速排序
7.4 排序算法能够多快
7.5 归并排序
7.5.1 归并
7.5.2 迭代归并
7.5.3 递归归并
7.6 堆排序
7.7 多关键字排序
7.8 链和列表排序
7.9 内部排序总结
7.10 外部排序
7.10.1 概述
7.10.2 k路归并
7.10.3 并行操作的缓存处理
7.10.4 顺串产生
7.10.5 顺串的最佳归并
7.11 参考文献和推荐读物
第8章 散列
8.1 绪论
8.2 静态散列
8.2.1 哈希表
8.2.2 哈希函数
8.2.3 安全哈希函数
8.2.4 溢出处理
8.2.5 溢出技术的理论分析
8.3 动态散列
8.3.1 动态散列的目的
8.3.2 使用目录的动态散列
8.3.3 不使用目录的动态散列
8.4 布隆过滤器
8.4.1 勘误文件的应用
8.4.2 设计布隆过滤器
8.5 参考文献和推荐读物
第9章 优先队列
9.1 单端和双端优先队列
9.2 左偏树
9.2.1 高度左偏树
9.2.2 重量左偏树
9.3 二项式堆
9.3.1 代价分摊
9.3.2 二项式堆的定义
9.3.3 二项式堆的插入操作
9.3.4 合并两个二项式堆
9.3.5 删除最小元素
9.3.6 分析
9.4 斐波那契堆
9.4.1 定义
9.4.2 从斐波那契堆中删除元素
9.4.3 减小键值
9.4.4 级联剪切
9.4.5 分析
9.4.6 在最短路径问题上的应用
9.5 配对堆
9.5.1 定义
9.5.2 合并和插入操作
9.5.3 减小键值
9.5.4 删除最小元素
9.5.5 删除任意元素
9.5.6 实现问题
9.5.7 复杂度
9.6 对称最小-最大堆
9.6.1 定义及性质
9.6.2 SMMH的表示
9.6.3 插入操作
9.6.4 删除操作
9.7 区间堆
9.7.1 定义及性质
9.7.2 区间堆的插入操作
9.7.3 删除最小元素
9.7.4 初始化区间堆
9.7.5 区间堆操作的复杂度
9.7.6 互补范围搜索问题
9.8 参考文献和推荐读物
第10章 高效二叉查找树
10.1 最优二叉查找树
10.2 AVL树
10.3 红黑树
10.3.1 定义
10.3.2 红黑树的表示
10.3.3 查找
10.3.4 插入
10.3.5 删除
10.3.6 红黑树的合并
10.3.7 红黑树的分裂
10.4 伸展树
10.4.1 自底向上的伸展树
10.4.2 自顶向下的伸展树
10.5 参考文献和推荐读物
第11章 多路查找树
11.1 m路查找树
11.1.1 定义和性质
11.1.2 对m路查找树进行查找
11.2 B-树
11.2.1 定义和性质
11.2.2 B-树的元素个数
11.2.3 插入
11.2.4 删除
11.3 B?树
11.3.1 定义
11.3.2 查找
11.3.3 插入
11.3.4 删除
11.4 参考文献和推荐读物
第12章 数字查找结构
12.1 数字查找树
12.1.1 定义
12.1.2 查找、插入和删除
12.2 二叉Trie树和Patricia树
12.2.1 二叉Trie树
12.2.2 压缩二叉Trie树
12.2.3 Patricia树
12.3 多路Trie树
12.3.1 定义
12.3.2 查找Trie树
12.3.3 抽样策略
12.3.4 插入Trie树
12.3.5 从Trie树中删除
12.3.6 不同长度的关键字
12.3.7 Trie树的高度
12.3.8 空间需求与其他结点结构
12.3.9 前缀查找和应用
12.3.10 压缩Trie树
12.3.11 带跳过字段的压缩Trie树
12.3.12 带标号边的压缩Trie树
12.3.13 压缩Trie树需要的空间
12.4 后缀树
12.4.1 你是否见过这个字符串
12.4.2 后缀树数据结构
12.4.3 查找子串(查找后缀树)
12.4.4 后缀树上的其他技巧
12.5 Trie树和Internet包转发
12.5.1 IP路由
12.5.2 1-比特Trie树
12.5.3 固定跨度Trie树
12.5.4 可变跨度Trie树
12.6 参考文献和推荐读物
术语表