数据结构：思想与实现
定价：￥39.00
作者： 翁惠玉，俞勇
出版社：高等教育出版社
“十二五”普通高等教育本科国家级规划教材
- 高等教育出版社
- 9787040277838
- 1
- 45151811-2
- 16开
- 570
内容简介
本书为国家精品课程“数据结构”的主讲教材。本书条理清晰，严格按照线性结构、树形结构、集合结构和图形结构的次序来组织编写。除了常规的数据结构内容之外，还介绍了一些高级的数据结构，如红黑树、粤粤树和跳表等，并提供了大量的数据结构应用实例。让读者在学习数据结构的同时，逐步了解为什么要学习数据结构，了解数据结构对计算机专业的重要性。
本书内容翔实，既注重数据结构和算法的原理，又十分强调和程序设计课程的衔接。在讲授数据结构的同时，不断加强学生对程序设计的理解。书中的算法都有完整的悦垣垣实现。这些程序结构清晰，构思精巧。所有的程序都在灾悦远援园环境下编译通过，并能正确运行。它们既是学习数据结构和算法的示例，也是学习悦垣垣程序设计很好的示例。
本书可作为高等学校计算机及相关专业数据结构课程教材，也可作为参加计算机专业硕士研究生入学考试的参考用书。
目录
目录
第1章 引言
1.1 算法与数据结构
1.1.1 数据的逻辑结构
1.1.2 数据结构的运算
1.2 存储实现
1.3 算法分析
1.3.1 时间复杂度的概念
1.3.2 算法运算量的计算
1.3.3 渐进表示法
1.3.4 时间复杂度的计算
1.3.5 算法的优化
1.4 面向对象的方法
1.4.1 面向对象的概念
1.4.2 用面向对象的思想讨论数据结构
1.4.3 面向对象方法中数据结构的描述和实现
1.5 本书的结构和特点
1.6 本书采用的算法描述工具
1.7 总结
1.8 习题
第一部分 线性表
第2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序实现
2.2.1 顺序表的存储实现
2.2.2 基本运算在顺序表上的实现
2.2.3 顺序实现的算法分析
2.3 线性表的链接实现
2.3.1 单链表
2.3.2 双链表
2.3.3 循环链表
2.4 线性表类的实现
2.4.1 线性表的抽象类
2.4.2 顺序表类的实现
2.4.3 双链表类的实现
2.5 STL中的线性表
2.5.1 容器和迭代器的概念
2.5.2 vector则类和list类
2.5.3 vector则类和list类的使用
2.5.4 双端队列-deque
2.6 线性表的应用：文本编辑系统
2.7 小结
2.8 习题
第3章 栈
3.1 栈的基本概念
3.2 栈的顺序实现
3.3 栈的链接实现
3.4 栈类的实现
3.4.1 栈的抽象类
3.4.2 顺序栈类的实现
3.4.3 链接栈类的实现
3.5 STL中的栈
3.6 栈的应用
3.6.1 递归消除
3.6.2 括号配对
3.6.3 简单的计算器
3.7 总结
3.8 习题
第4章 队列
4.1 队列的概念
4.2 队列的顺序实现
4.2.1 队头位置固定的顺序实现
4.2.2 队头位置不固定的顺序实现
4.2.3 循环队列
4.3 队列的链接实现
4.4 队列类的实现
4.4.1 队列的抽象类
4.4.2 循环队列类的实现
4.4.3 链接队列类的实现
4.5 STL中的队列
4.6 队列的应用：排队系统的模拟
4.7 总结
4.8 习题
第二部分 树形结构
第5章 树
5.1 树的概念
5.1.1 树的定义
5.1.2 树的基本术语
5.1.3 树的基本运算
5.2 二叉树
5.2.1 二叉树的基本概念
5.2.2 二叉树的主要性质
5.2.3 二叉树的基本运算和二叉树的遍历
5.2.4 二叉树的顺序实现
5.2.5 二叉树的链接实现
5.2.5 二叉树类的实现
5.2.6 二叉树遍历的非递归实现
5.3 二叉树的应用：计算表达式
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.7 习题
第6章 优先级队列
6.1 基本的优先级队列
6.2 二叉堆
6.2.1 二叉堆的结构性
6.2.2 二叉堆的有序性
6.2.3 基于二叉堆的优先级队列的实现
6.3 D堆
6.4 归并优先级队列
6.4.1 左堆
6.4.2 斜堆
6.4.3 贝努里队列
6.5 STL中的优先级队列
6.6 多服务台排队系统的模拟
6.7 总结
6.8 习题
第三部分 集合
第7章 集合与静态查找表
7.1 集合的基本概念
7.2 查找的基本概念
7.3 静态表查找
7.4 无序表的查找
7.4.1 顺序查找
7.4.2 顺序查找的时间复杂度分析
7.5 有序表的查找
7.5.1 顺序查找
7.5.2 二分查找
7.5.3 插值查找
7.5.4 分块查找
7.6 静态查找表的实现
7.7 STL中的静态表
7.8 总结
7.9 习题
第8章 查找树
8.1 二叉查找树
8.1.1 二叉查找树的定义
8.1.2 二叉查找树的操作
8.1.3 二叉查找树的性能
8.1.4 二叉查找树类的实现
8.2 AVL树
8.2.1 AVL树的定义
8.2.2 AVL树的插入操作
8.2.3 AVL树的删除操作
8.2.4 AVL树类的实现
8.3 红黑树
8.3.1 红黑树的定义
8.3.2 红黑树的插入操作
8.3.3 红黑树的删除操作
8.3.4 红黑树类的实现
8.4 AA树
8.4.1 AA树的定义
8.4.2 AA树的插入操作
8.4.3 AA树的删除操作
8.4.4 AA树类的实现
8.5 伸展树
8.5.1 伸展树的定义
8.5.2 伸展操作的实现
8.6 B树和B+垣树
8.6.1 B树
8.6.2 B+树
8.7 STL中的查找表
8.7.1 set
8.7.2 map
8.8 总结
8.9 习题
第9章 散列表
9.1 基本概念
9.2 散列函数
9.3 碰撞的解决
9.3.1 线性探测法
9.3.2 二次探测法
9.3.3 再散列法
9.3.4 开散列表
9.4 散列表类的实现
9.4.1 散列表类的抽象类
9.4.2 闭散列表的实现
9.4.3 开散列表的实现
9.5 散列表类的应用
9.6 总结
9.7 习题
第10章 排序
10.1 引言
10.2 插入排序
10.2.1 直接插入排序
10.2.2 二分插入排序
10.2.3 希尔排序
10.2.4 希尔排序的性能
10.3 选择排序
10.3.1 直接选择排序
10.3.2 堆排序
10.4 交换排序
10.4.1 冒泡排序
10.4.2 快速排序
10.5 归并排序
10.6 外排序
10.6.1 外排序的基本过程
10.6.2 预处理阶段
10.6.3 归并阶段
10.7 总结
10.8 习题
第11章 不相交集
11.1 等价关系与等价类
11.2 不相交集
11.3 不相交集的实现
11.3.1 不相交集的存储实现
11.3.2 不相交集的运算实现
11.3.3 改进的union灶算法
11.3.4 改进的find算法
11.4 不相交集类的实现
11.5 不相交集的应用
11.5.1 生成迷宫
11.5.2 最近的共同祖先问题
11.6 总结
11.7 习题
第四部分 图
第12章 图的基本概念
12.1 图的定义
12.2 图的基本术语
12.3 图的基本运算
12.4 图的存储
12.4.1 邻接矩阵表示法
12.4.2 邻接表表示法
12.5 图的遍历
12.5.1 深度优先搜索DFS
12.5.2 广度优先搜索BFS
12.6 图的遍历的应用
12.6.1 无向图的连通性
12.6.2 欧拉回路
12.6.3 有向图的连通性
12.6.4 拓扑排序
12.7 总结
12.8 习题
第13章 最小生成树
13.1 生成树和最小生成树
13.2 Kruskal算法
13.3 Prim算法
13.4 算法的正确性
13.5 总结
13.6 习题
第14章 最短路径问题
14.1 单源最短路径
14.1.1 非加权图的最短路径
14.1.2 加权图的最短路径
14.1.3 带有负权值的图
14.1.4 无环图
14.2 所有顶点对的最短路径
14.3 总结
14.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.5 回溯法
15.6 随机算法
15.6.1 跳表
15.6.2 素数检测
15.7 总结
15.8 习题
参考文献
第1章 引言
1.1 算法与数据结构
1.1.1 数据的逻辑结构
1.1.2 数据结构的运算
1.2 存储实现
1.3 算法分析
1.3.1 时间复杂度的概念
1.3.2 算法运算量的计算
1.3.3 渐进表示法
1.3.4 时间复杂度的计算
1.3.5 算法的优化
1.4 面向对象的方法
1.4.1 面向对象的概念
1.4.2 用面向对象的思想讨论数据结构
1.4.3 面向对象方法中数据结构的描述和实现
1.5 本书的结构和特点
1.6 本书采用的算法描述工具
1.7 总结
1.8 习题
第一部分 线性表
第2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序实现
2.2.1 顺序表的存储实现
2.2.2 基本运算在顺序表上的实现
2.2.3 顺序实现的算法分析
2.3 线性表的链接实现
2.3.1 单链表
2.3.2 双链表
2.3.3 循环链表
2.4 线性表类的实现
2.4.1 线性表的抽象类
2.4.2 顺序表类的实现
2.4.3 双链表类的实现
2.5 STL中的线性表
2.5.1 容器和迭代器的概念
2.5.2 vector则类和list类
2.5.3 vector则类和list类的使用
2.5.4 双端队列-deque
2.6 线性表的应用：文本编辑系统
2.7 小结
2.8 习题
第3章 栈
3.1 栈的基本概念
3.2 栈的顺序实现
3.3 栈的链接实现
3.4 栈类的实现
3.4.1 栈的抽象类
3.4.2 顺序栈类的实现
3.4.3 链接栈类的实现
3.5 STL中的栈
3.6 栈的应用
3.6.1 递归消除
3.6.2 括号配对
3.6.3 简单的计算器
3.7 总结
3.8 习题
第4章 队列
4.1 队列的概念
4.2 队列的顺序实现
4.2.1 队头位置固定的顺序实现
4.2.2 队头位置不固定的顺序实现
4.2.3 循环队列
4.3 队列的链接实现
4.4 队列类的实现
4.4.1 队列的抽象类
4.4.2 循环队列类的实现
4.4.3 链接队列类的实现
4.5 STL中的队列
4.6 队列的应用：排队系统的模拟
4.7 总结
4.8 习题
第二部分 树形结构
第5章 树
5.1 树的概念
5.1.1 树的定义
5.1.2 树的基本术语
5.1.3 树的基本运算
5.2 二叉树
5.2.1 二叉树的基本概念
5.2.2 二叉树的主要性质
5.2.3 二叉树的基本运算和二叉树的遍历
5.2.4 二叉树的顺序实现
5.2.5 二叉树的链接实现
5.2.5 二叉树类的实现
5.2.6 二叉树遍历的非递归实现
5.3 二叉树的应用：计算表达式
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.7 习题
第6章 优先级队列
6.1 基本的优先级队列
6.2 二叉堆
6.2.1 二叉堆的结构性
6.2.2 二叉堆的有序性
6.2.3 基于二叉堆的优先级队列的实现
6.3 D堆
6.4 归并优先级队列
6.4.1 左堆
6.4.2 斜堆
6.4.3 贝努里队列
6.5 STL中的优先级队列
6.6 多服务台排队系统的模拟
6.7 总结
6.8 习题
第三部分 集合
第7章 集合与静态查找表
7.1 集合的基本概念
7.2 查找的基本概念
7.3 静态表查找
7.4 无序表的查找
7.4.1 顺序查找
7.4.2 顺序查找的时间复杂度分析
7.5 有序表的查找
7.5.1 顺序查找
7.5.2 二分查找
7.5.3 插值查找
7.5.4 分块查找
7.6 静态查找表的实现
7.7 STL中的静态表
7.8 总结
7.9 习题
第8章 查找树
8.1 二叉查找树
8.1.1 二叉查找树的定义
8.1.2 二叉查找树的操作
8.1.3 二叉查找树的性能
8.1.4 二叉查找树类的实现
8.2 AVL树
8.2.1 AVL树的定义
8.2.2 AVL树的插入操作
8.2.3 AVL树的删除操作
8.2.4 AVL树类的实现
8.3 红黑树
8.3.1 红黑树的定义
8.3.2 红黑树的插入操作
8.3.3 红黑树的删除操作
8.3.4 红黑树类的实现
8.4 AA树
8.4.1 AA树的定义
8.4.2 AA树的插入操作
8.4.3 AA树的删除操作
8.4.4 AA树类的实现
8.5 伸展树
8.5.1 伸展树的定义
8.5.2 伸展操作的实现
8.6 B树和B+垣树
8.6.1 B树
8.6.2 B+树
8.7 STL中的查找表
8.7.1 set
8.7.2 map
8.8 总结
8.9 习题
第9章 散列表
9.1 基本概念
9.2 散列函数
9.3 碰撞的解决
9.3.1 线性探测法
9.3.2 二次探测法
9.3.3 再散列法
9.3.4 开散列表
9.4 散列表类的实现
9.4.1 散列表类的抽象类
9.4.2 闭散列表的实现
9.4.3 开散列表的实现
9.5 散列表类的应用
9.6 总结
9.7 习题
第10章 排序
10.1 引言
10.2 插入排序
10.2.1 直接插入排序
10.2.2 二分插入排序
10.2.3 希尔排序
10.2.4 希尔排序的性能
10.3 选择排序
10.3.1 直接选择排序
10.3.2 堆排序
10.4 交换排序
10.4.1 冒泡排序
10.4.2 快速排序
10.5 归并排序
10.6 外排序
10.6.1 外排序的基本过程
10.6.2 预处理阶段
10.6.3 归并阶段
10.7 总结
10.8 习题
第11章 不相交集
11.1 等价关系与等价类
11.2 不相交集
11.3 不相交集的实现
11.3.1 不相交集的存储实现
11.3.2 不相交集的运算实现
11.3.3 改进的union灶算法
11.3.4 改进的find算法
11.4 不相交集类的实现
11.5 不相交集的应用
11.5.1 生成迷宫
11.5.2 最近的共同祖先问题
11.6 总结
11.7 习题
第四部分 图
第12章 图的基本概念
12.1 图的定义
12.2 图的基本术语
12.3 图的基本运算
12.4 图的存储
12.4.1 邻接矩阵表示法
12.4.2 邻接表表示法
12.5 图的遍历
12.5.1 深度优先搜索DFS
12.5.2 广度优先搜索BFS
12.6 图的遍历的应用
12.6.1 无向图的连通性
12.6.2 欧拉回路
12.6.3 有向图的连通性
12.6.4 拓扑排序
12.7 总结
12.8 习题
第13章 最小生成树
13.1 生成树和最小生成树
13.2 Kruskal算法
13.3 Prim算法
13.4 算法的正确性
13.5 总结
13.6 习题
第14章 最短路径问题
14.1 单源最短路径
14.1.1 非加权图的最短路径
14.1.2 加权图的最短路径
14.1.3 带有负权值的图
14.1.4 无环图
14.2 所有顶点对的最短路径
14.3 总结
14.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.5 回溯法
15.6 随机算法
15.6.1 跳表
15.6.2 素数检测
15.7 总结
15.8 习题
参考文献
第1章 引言
1.1 算法与数据结构
1.1.1 数据的逻辑结构
1.1.2 数据结构的运算
1.2 存储实现
1.3 算法分析
1.3.1 时间复杂度的概念
1.3.2 算法运算量的计算
1.3.3 渐进表示法
1.3.4 时间复杂度的计算
1.3.5 算法的优化
1.4 面向对象的方法
1.4.1 面向对象的概念
1.4.2 用面向对象的思想讨论数据结构
1.4.3 面向对象方法中数据结构的描述和实现
1.5 本书的结构和特点
1.6 本书采用的算法描述工具
1.7 总结
1.8 习题
第一部分 线性表
第2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序实现
2.2.1 顺序表的存储实现
2.2.2 基本运算在顺序表上的实现
2.2.3 顺序实现的算法分析
2.3 线性表的链接实现
2.3.1 单链表
2.3.2 双链表
2.3.3 循环链表
2.4 线性表类的实现
2.4.1 线性表的抽象类
2.4.2 顺序表类的实现
2.4.3 双链表类的实现
2.5 STL中的线性表
2.5.1 容器和迭代器的概念
2.5.2 vector则类和list类
2.5.3 vector则类和list类的使用
2.5.4 双端队列-deque
2.6 线性表的应用：文本编辑系统
2.7 小结
2.8 习题
第3章 栈
3.1 栈的基本概念
3.2 栈的顺序实现
3.3 栈的链接实现
3.4 栈类的实现
3.4.1 栈的抽象类
3.4.2 顺序栈类的实现
3.4.3 链接栈类的实现
3.5 STL中的栈
3.6 栈的应用
3.6.1 递归消除
3.6.2 括号配对
3.6.3 简单的计算器
3.7 总结
3.8 习题
第4章 队列
4.1 队列的概念
4.2 队列的顺序实现
4.2.1 队头位置固定的顺序实现
4.2.2 队头位置不固定的顺序实现
4.2.3 循环队列
4.3 队列的链接实现
4.4 队列类的实现
4.4.1 队列的抽象类
4.4.2 循环队列类的实现
4.4.3 链接队列类的实现
4.5 STL中的队列
4.6 队列的应用：排队系统的模拟
4.7 总结
4.8 习题
第二部分 树形结构
第5章 树
5.1 树的概念
5.1.1 树的定义
5.1.2 树的基本术语
5.1.3 树的基本运算
5.2 二叉树
5.2.1 二叉树的基本概念
5.2.2 二叉树的主要性质
5.2.3 二叉树的基本运算和二叉树的遍历
5.2.4 二叉树的顺序实现
5.2.5 二叉树的链接实现
5.2.5 二叉树类的实现
5.2.6 二叉树遍历的非递归实现
5.3 二叉树的应用：计算表达式
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.7 习题
第6章 优先级队列
6.1 基本的优先级队列
6.2 二叉堆
6.2.1 二叉堆的结构性
6.2.2 二叉堆的有序性
6.2.3 基于二叉堆的优先级队列的实现
6.3 D堆
6.4 归并优先级队列
6.4.1 左堆
6.4.2 斜堆
6.4.3 贝努里队列
6.5 STL中的优先级队列
6.6 多服务台排队系统的模拟
6.7 总结
6.8 习题
第三部分 集合
第7章 集合与静态查找表
7.1 集合的基本概念
7.2 查找的基本概念
7.3 静态表查找
7.4 无序表的查找
7.4.1 顺序查找
7.4.2 顺序查找的时间复杂度分析
7.5 有序表的查找
7.5.1 顺序查找
7.5.2 二分查找
7.5.3 插值查找
7.5.4 分块查找
7.6 静态查找表的实现
7.7 STL中的静态表
7.8 总结
7.9 习题
第8章 查找树
8.1 二叉查找树
8.1.1 二叉查找树的定义
8.1.2 二叉查找树的操作
8.1.3 二叉查找树的性能
8.1.4 二叉查找树类的实现
8.2 AVL树
8.2.1 AVL树的定义
8.2.2 AVL树的插入操作
8.2.3 AVL树的删除操作
8.2.4 AVL树类的实现
8.3 红黑树
8.3.1 红黑树的定义
8.3.2 红黑树的插入操作
8.3.3 红黑树的删除操作
8.3.4 红黑树类的实现
8.4 AA树
8.4.1 AA树的定义
8.4.2 AA树的插入操作
8.4.3 AA树的删除操作
8.4.4 AA树类的实现
8.5 伸展树
8.5.1 伸展树的定义
8.5.2 伸展操作的实现
8.6 B树和B+垣树
8.6.1 B树
8.6.2 B+树
8.7 STL中的查找表
8.7.1 set
8.7.2 map
8.8 总结
8.9 习题
第9章 散列表
9.1 基本概念
9.2 散列函数
9.3 碰撞的解决
9.3.1 线性探测法
9.3.2 二次探测法
9.3.3 再散列法
9.3.4 开散列表
9.4 散列表类的实现
9.4.1 散列表类的抽象类
9.4.2 闭散列表的实现
9.4.3 开散列表的实现
9.5 散列表类的应用
9.6 总结
9.7 习题
第10章 排序
10.1 引言
10.2 插入排序
10.2.1 直接插入排序
10.2.2 二分插入排序
10.2.3 希尔排序
10.2.4 希尔排序的性能
10.3 选择排序
10.3.1 直接选择排序
10.3.2 堆排序
10.4 交换排序
10.4.1 冒泡排序
10.4.2 快速排序
10.5 归并排序
10.6 外排序
10.6.1 外排序的基本过程
10.6.2 预处理阶段
10.6.3 归并阶段
10.7 总结
10.8 习题
第11章 不相交集
11.1 等价关系与等价类
11.2 不相交集
11.3 不相交集的实现
11.3.1 不相交集的存储实现
11.3.2 不相交集的运算实现
11.3.3 改进的union灶算法
11.3.4 改进的find算法
11.4 不相交集类的实现
11.5 不相交集的应用
11.5.1 生成迷宫
11.5.2 最近的共同祖先问题
11.6 总结
11.7 习题
第四部分 图
第12章 图的基本概念
12.1 图的定义
12.2 图的基本术语
12.3 图的基本运算
12.4 图的存储
12.4.1 邻接矩阵表示法
12.4.2 邻接表表示法
12.5 图的遍历
12.5.1 深度优先搜索DFS
12.5.2 广度优先搜索BFS
12.6 图的遍历的应用
12.6.1 无向图的连通性
12.6.2 欧拉回路
12.6.3 有向图的连通性
12.6.4 拓扑排序
12.7 总结
12.8 习题
第13章 最小生成树
13.1 生成树和最小生成树
13.2 Kruskal算法
13.3 Prim算法
13.4 算法的正确性
13.5 总结
13.6 习题
第14章 最短路径问题
14.1 单源最短路径
14.1.1 非加权图的最短路径
14.1.2 加权图的最短路径
14.1.3 带有负权值的图
14.1.4 无环图
14.2 所有顶点对的最短路径
14.3 总结
14.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.5 回溯法
15.6 随机算法
15.6.1 跳表
15.6.2 素数检测
15.7 总结
15.8 习题
参考文献
第1章 引言
1.1 算法与数据结构
1.1.1 数据的逻辑结构
1.1.2 数据结构的运算
1.2 存储实现
1.3 算法分析
1.3.1 时间复杂度的概念
1.3.2 算法运算量的计算
1.3.3 渐进表示法
1.3.4 时间复杂度的计算
1.3.5 算法的优化
1.4 面向对象的方法
1.4.1 面向对象的概念
1.4.2 用面向对象的思想讨论数据结构
1.4.3 面向对象方法中数据结构的描述和实现
1.5 本书的结构和特点
1.6 本书采用的算法描述工具
1.7 总结
1.8 习题
第一部分 线性表
第2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序实现
2.2.1 顺序表的存储实现
2.2.2 基本运算在顺序表上的实现
2.2.3 顺序实现的算法分析
2.3 线性表的链接实现
2.3.1 单链表
2.3.2 双链表
2.3.3 循环链表
2.4 线性表类的实现
2.4.1 线性表的抽象类
2.4.2 顺序表类的实现
2.4.3 双链表类的实现
2.5 STL中的线性表
2.5.1 容器和迭代器的概念
2.5.2 vector则类和list类
2.5.3 vector则类和list类的使用
2.5.4 双端队列-deque
2.6 线性表的应用：文本编辑系统
2.7 小结
2.8 习题
第3章 栈
3.1 栈的基本概念
3.2 栈的顺序实现
3.3 栈的链接实现
3.4 栈类的实现
3.4.1 栈的抽象类
3.4.2 顺序栈类的实现
3.4.3 链接栈类的实现
3.5 STL中的栈
3.6 栈的应用
3.6.1 递归消除
3.6.2 括号配对
3.6.3 简单的计算器
3.7 总结
3.8 习题
第4章 队列
4.1 队列的概念
4.2 队列的顺序实现
4.2.1 队头位置固定的顺序实现
4.2.2 队头位置不固定的顺序实现
4.2.3 循环队列
4.3 队列的链接实现
4.4 队列类的实现
4.4.1 队列的抽象类
4.4.2 循环队列类的实现
4.4.3 链接队列类的实现
4.5 STL中的队列
4.6 队列的应用：排队系统的模拟
4.7 总结
4.8 习题
第二部分 树形结构
第5章 树
5.1 树的概念
5.1.1 树的定义
5.1.2 树的基本术语
5.1.3 树的基本运算
5.2 二叉树
5.2.1 二叉树的基本概念
5.2.2 二叉树的主要性质
5.2.3 二叉树的基本运算和二叉树的遍历
5.2.4 二叉树的顺序实现
5.2.5 二叉树的链接实现
5.2.5 二叉树类的实现
5.2.6 二叉树遍历的非递归实现
5.3 二叉树的应用：计算表达式
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.7 习题
第6章 优先级队列
6.1 基本的优先级队列
6.2 二叉堆
6.2.1 二叉堆的结构性
6.2.2 二叉堆的有序性
6.2.3 基于二叉堆的优先级队列的实现
6.3 D堆
6.4 归并优先级队列
6.4.1 左堆
6.4.2 斜堆
6.4.3 贝努里队列
6.5 STL中的优先级队列
6.6 多服务台排队系统的模拟
6.7 总结
6.8 习题
第三部分 集合
第7章 集合与静态查找表
7.1 集合的基本概念
7.2 查找的基本概念
7.3 静态表查找
7.4 无序表的查找
7.4.1 顺序查找
7.4.2 顺序查找的时间复杂度分析
7.5 有序表的查找
7.5.1 顺序查找
7.5.2 二分查找
7.5.3 插值查找
7.5.4 分块查找
7.6 静态查找表的实现
7.7 STL中的静态表
7.8 总结
7.9 习题
第8章 查找树
8.1 二叉查找树
8.1.1 二叉查找树的定义
8.1.2 二叉查找树的操作
8.1.3 二叉查找树的性能
8.1.4 二叉查找树类的实现
8.2 AVL树
8.2.1 AVL树的定义
8.2.2 AVL树的插入操作
8.2.3 AVL树的删除操作
8.2.4 AVL树类的实现
8.3 红黑树
8.3.1 红黑树的定义
8.3.2 红黑树的插入操作
8.3.3 红黑树的删除操作
8.3.4 红黑树类的实现
8.4 AA树
8.4.1 AA树的定义
8.4.2 AA树的插入操作
8.4.3 AA树的删除操作
8.4.4 AA树类的实现
8.5 伸展树
8.5.1 伸展树的定义
8.5.2 伸展操作的实现
8.6 B树和B+垣树
8.6.1 B树
8.6.2 B+树
8.7 STL中的查找表
8.7.1 set
8.7.2 map
8.8 总结
8.9 习题
第9章 散列表
9.1 基本概念
9.2 散列函数
9.3 碰撞的解决
9.3.1 线性探测法
9.3.2 二次探测法
9.3.3 再散列法
9.3.4 开散列表
9.4 散列表类的实现
9.4.1 散列表类的抽象类
9.4.2 闭散列表的实现
9.4.3 开散列表的实现
9.5 散列表类的应用
9.6 总结
9.7 习题
第10章 排序
10.1 引言
10.2 插入排序
10.2.1 直接插入排序
10.2.2 二分插入排序
10.2.3 希尔排序
10.2.4 希尔排序的性能
10.3 选择排序
10.3.1 直接选择排序
10.3.2 堆排序
10.4 交换排序
10.4.1 冒泡排序
10.4.2 快速排序
10.5 归并排序
10.6 外排序
10.6.1 外排序的基本过程
10.6.2 预处理阶段
10.6.3 归并阶段
10.7 总结
10.8 习题
第11章 不相交集
11.1 等价关系与等价类
11.2 不相交集
11.3 不相交集的实现
11.3.1 不相交集的存储实现
11.3.2 不相交集的运算实现
11.3.3 改进的union灶算法
11.3.4 改进的find算法
11.4 不相交集类的实现
11.5 不相交集的应用
11.5.1 生成迷宫
11.5.2 最近的共同祖先问题
11.6 总结
11.7 习题
第四部分 图
第12章 图的基本概念
12.1 图的定义
12.2 图的基本术语
12.3 图的基本运算
12.4 图的存储
12.4.1 邻接矩阵表示法
12.4.2 邻接表表示法
12.5 图的遍历
12.5.1 深度优先搜索DFS
12.5.2 广度优先搜索BFS
12.6 图的遍历的应用
12.6.1 无向图的连通性
12.6.2 欧拉回路
12.6.3 有向图的连通性
12.6.4 拓扑排序
12.7 总结
12.8 习题
第13章 最小生成树
13.1 生成树和最小生成树
13.2 Kruskal算法
13.3 Prim算法
13.4 算法的正确性
13.5 总结
13.6 习题
第14章 最短路径问题
14.1 单源最短路径
14.1.1 非加权图的最短路径
14.1.2 加权图的最短路径
14.1.3 带有负权值的图
14.1.4 无环图
14.2 所有顶点对的最短路径
14.3 总结
14.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.5 回溯法
15.6 随机算法
15.6.1 跳表
15.6.2 素数检测
15.7 总结
15.8 习题
参考文献
