用C++描述数据结构

第一章　基本概念
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.5　算法说述
1.5.1　引言
1.5.2　递归算法
1.6　　性能分析与测定
1.6.1性能分析
1.6.2　性能测定
1.6.3　　产生测试数据
第二章　数组
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.3.3　由数组表示多项式的缺点
2.4　稀疏矩阵
2.4.1　引言
2.4.2　稀疏矩阵的表示方式
2.4.3　矩阵的转置
2.4.4　矩阵相乘
2.4.5　由数组表示稀疏矩阵的缺点
2.5　数组的表示
2.6　字符串抽象数据类型
2.6.1　字符串模式匹配:一种简单算法
2.6.2　字符串模式匹配:K-M-P算法
2.7　附加练习
第三章　栈和队列
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　多栈和多队列
3.8　附加练习
第四章　链表
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.6.1　多项式表示
4.6.2　多项式相加
4.6.3　清除多项式
4.6.4　多项式的循环链表示
4.6.5　总结
4.7　等价类
4.8　稀疏矩阵
4.8.1　稀疏矩阵表示
4.8.2　稀疏矩阵的输入
4.8.3　清除稀疏矩阵
4.9　双向链表
4.10　广义表
4.10.1　文义表的表示
4.10.2　链表的递归算法
4.10.3　共享链表\递归链表和引用数
4.11　C++中的虚函数和动态联编
4.12　异质表
第五章　树
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.12　二叉树的计数
5.12.1　不相同的二叉树
5.12.2　栈排列
5.12.3　矩阵乘法
5.12.4　不同二叉树数
第六章　图
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　顶点表示活动的网络
6.5.2　边表示活动的网络
6.6　附加练习
第七章　排序
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　归并段的最佳归并
第八章　散列
8.1　符号表抽象数据类型
8.2　静态散列
8.2.1　哈希表
8.2.2　哈希函数
8.2.3　溢出处理
8.2.4　溢出处理技术的理论评估
8.3　动态散列
8.3.1　引言
8.3.2　使用目录的动态散列
8.3.3　基于目录的动态散列方法的分析
8.3.4　无目录的动态散列
第九章　堆结构
9.1　最小－最大堆
9.1.1　定义
9.1.2　向最小－最大堆中插入元素
9.1.3　删除最小元素
9.2　双端堆
9.2.1　定义
9.2.2　向双端堆中插入元素
9.2.3　删除最小元素
9.3　左树
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　从F-堆中删除结点
9.5.3　减-码
9.5.4　级联剪切
9.5.5　分析
9.5.6　在最短路径问题中的应用
9.6　附加练习
第十章　查找结构
10.1　最优二叉查找树
10.2　AVL树
10.3　　2-3树
10.3.1　定义和性质
10.3.2　查找一棵2-3树
10.3.3　向2-3树中插入元素
10.3.4　从2-3树中删除元素
10.4　2-3-4树
10.4.1　定义和性质
10.4.2　自顶向下插入
10.4.3　自顶向下删除
10.5　　红－黑树
10.5.1　定义和性质
10.5.2　查找红－黑树
10.5.3　自顶向下插入
10.5.4　自底向上插入
10.5.5　从红-黑树中删除元素
10.5.6　连接和分裂红-黑树
10.6　B-树
10.6.1　m-路查找树的定义
10.6.2　查找一棵m-路查找树
10.6.3　B-树的定义和性质
10.6.4　向B-树中插入
10.6.5　从B-树中删除
10.6.6　可变大小的关键码
10.7　扁树
10.8　数字查找树
10.8.1　定义
10.8.2　二叉trie树
10.8.3　Patricia
10.9　trie树
10.9.1　定义
10.9.2　查找一棵trie树
10.6.3　采样策略
10.9.4　向trie树中插入关键码
10.9.5　从trie树中删除关键码
10.9.6　结点结构
10.10　差异文件
10.10.1　概念
10.10.2　布卢姆过滤程序