数据结构：思想与实现（第2版） / 国家精品课程主讲教材
作者： 翁惠玉，俞勇
出版时间：2017-11-29
出版社：高等教育出版社
获奖信息：“十二五”普通高等教育本科国家级规划教材
- 高等教育出版社
- 9787040486995
- 2版
- 207134
- 45242533-3
- 平装
- 16开
- 2017-11-29
- 680
- 464
- 工学
- 计算机科学与技术
- 计算机科学与技术
- 本科 研究生（硕士、EMBA、MBA、MPA、博士）
数据结构是计算机类专业最基础，也是最重要的课程之一，它和程序设计一起为计算学科其他后继课程的学习奠定了基础。
上海交通大学的“数据结构”课程是国家精品课程和精品资源共享课程，本书是该课程的教学成果之一，被列入“十二五”普通高等教育本科国家级规划教材。
本书条理清晰，严格按照线性结构、树状结构、集合结构和图状结构的次序来组织。除常规的数据结构内容之外，还介绍了一些高级的数据结构，如红黑树、AA 树和跳表等，并提供了大量的数据结构应用实例，让读者在学习数据结构的同时，逐步了解为什么要学数据结构以及数据结构对计算机类专业的重要性。
本书内容详实，既注重数据结构和算法的原理，又十分强调和程序设计课程的衔接。在讲授数据结构的同时，不断加强学生对程序设计的理解。书中的算法都有完整的C++ 实现，这些程序结构清晰，构思精巧，且所有程序都在VC 6.0 环境下编译通过，并能正确运行。它们既是学习数据结构和算法的示例，也是学习C++ 程序设计很好的示例。
为便于读者学习与理解，本书为重点、难点内容提供了教学视频，读者可通过扫描二维码观看。完整的课程视频可见http://www.icourses.cn/coursestatic/course_2945.html。本书可作为高等学校计算机类专业“数据结构”课程的教材，也可供相关技术人员参考。
前辅文
第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.3.6 空间复杂度
1.4 面向对象方法
本书的结构和特点
总结
练习1
第1部分 线性结构
第2章 线性表
2.1 线性表的定义
2.2 线性表的顺序实现
2.2.1 顺序表的存储实现
2.2.2 顺序表的运算实现
2.2.3 顺序实现的性能分析
2.2.4 顺序表的简单示例
2.3 线性表的链接实现
2.3.1 单链表
2.3.2 双链表
2.3.3 循环链表
2.3.4 链表的性能分析
2.4 标准模板库（STL）中的线性表
2.4.1 容器和迭代器的概念
2.4.2 STL 中的线性表类
2.5 线性表的应用
2.5.1 大整数处理
2.5.2 多项式求和
2.5.3 约瑟夫环
2.5.4 动态内存管理
总结
练习2
第3章 栈
3.1 栈的定义
3.2 栈的顺序实现
3.2.1 顺序栈的存储实现
3.2.2 顺序栈的运算实现
3.2.3 顺序栈性能分析
3.2.4 顺序栈的简单示例
3.3 栈的链接实现
3.3.1 链接栈的存储实现
3.3.2 链接栈的运算实现
3.3.3 链接栈的简单示例
3.4 STL 中的栈
3.5 栈的应用
3.5.1 递归消除
3.5.2 括号配对
3.5.3 简单的计算器
总结
练习3
第4章 队列
4.1 队列的定义
4.2 队列的顺序实现
4.2.1 顺序队列的存储实现
4.2.2 循环队列的运算实现
4.2.3 循环队列简单示例
4.3 队列的链接实现
4.3.1 链接队列的存储实现
4.3.2 链接队列的运算实现
4.3.3 链接队列简单示例
4.4 STL 中的队列
4.5 队列的应用
4.5.1 火车车厢重排问题
4.5.2 排队系统的模拟
总结
练习4
第5章 字符串
5.1 字符串的定义
5.2 字符串的顺序实现
5.2.1 顺序串的存储实现
5.2.2 顺序串的运算实现
5.3 字符串的链接实现
5.3.1 链接串的存储实现
5.3.2 链接串类的运算实现
5.4 字符串的匹配
5.5 STL 的字符串类
总结
练习5
第2部分 树状结构
第6章 树
6.1 树的定义
6.1.1 树的基本术语
6.1.2 树的基本运算
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的常用性质
6.2.3 二叉树的基本运算
6.2.4 二叉树的顺序实现
6.2.5 二叉树的链接实现
6.2.6 二叉链表类
6.3 二叉树的应用：计算表达式
6.4 哈夫曼树和哈夫曼编码
6.4.1 前缀编码
6.4.2 哈夫曼算法
6.4.3 哈夫曼树类的实现
6.5 树和森林
6.5.1 树的存储实现
6.5.2 树的遍历
6.5.3 树、森林与二叉树的转换
总结
练习6
第7章 优先级队列
7.1 基于线性表的优先级队列
7.2 基于树的优先级队列
7.2.1 优先级队列的存储实现
7.2.2 优先级队列的运算实现
7.3 D 堆
7.4 归并优先级队列
7.4.1 左堆
7.4.2 斜堆
7.4.3 二项堆
7.5 STL 中的优先级队列
7.6 优先级队列的应用：排队系统的模拟
总结
练习7
第3部分 集合结构
第8章 集合与静态查找表
8.1 集合的定义
8.2 查找的基本概念
8.3 静态查找表
8.4 无序表的查找
8.4.1 顺序查找
8.4.2 顺序查找的时间复杂度分析
8.5 有序表的查找
8.5.1 顺序查找
8.5.2 二分查找
8.5.3 插值查找
8.5.4 分块查找
8.6 STL 中的静态查找表
总结
练习8
第9章 动态查找表
9.1 二叉查找树
9.1.1 二叉查找树的定义
9.1.2 二叉查找树的存储实现
9.1.3 二叉查找树的运算实现
9.1.4 二叉查找树性能
9.2 AVL 树
9.2.1 AVL 树的定义
9.2.2 AVL 树的存储实现
9.2.3 AVL 树的运算实现
9.3 红黑树
9.3.1 红黑树的定义
9.3.2 红黑树的存储实现
9.3.3 红黑树的运算实现
9.4 AA 树
9.4.1 AA 树的定义
9.4.2 AA 树的存储实现
9.4.3 AA 树的运算实现
9.5 伸展树
9.5.1 伸展树的定义
9.5.2 伸展操作的实现
9.6 散列表
9.6.1 散列表的定义
9.6.2 线性探测法
9.6.3 二次探测法
9.6.4 再散列法
9.6.5 开散列表
9.7 STL 中的动态查找表
9.7.1 set
9.7.2 map
总结
练习9
第10章 排序
10.1 排序的基本概念
10.2 插入排序
10.2.1 直接插入排序
10.2.2 二分插入排序
10.2.3 希尔排序
10.3 选择排序
10.3.1 直接选择排序
10.3.2 堆排序
10.4 交换排序
10.4.1 冒泡排序
10.4.2 快速排序
10.5 归并排序
10.6 基数排序
10.7 STL 中的排序
总结
练习10
第11章 外部查找与排序
11.1 主存储器与外存储器
11.2 B 树
11.2.1 B 树的定义
11.2.2 B 树的查找
11.2.3 B 树的插入
11.2.4 B 树的删除
11.3 B+ 树
11.3.1 B+ 树的定义
11.3.2 B+ 树的查找
11.3.3 B+ 树的插入
11.3.4 B+ 树的删除
11.4 外排序
11.4.1 置换选择
11.4.2 多阶段归并
总结
练习11
第12章 不相交集
12.1 等价关系与等价类
12.2 不相交集
12.3 不相交集的实现
12.3.1 不相交集的存储实现
12.3.2 不相交集的运算实现
12.4 不相交集的应用
12.4.1 生成迷宫
12.4.2 最近的共同祖先问题
总结
练习12
第4部分 图状结构
第13章 图
13.1 图的定义
13.1.1 图的基本术语
13.1.2 图的基本运算
13.2 图的存储
13.2.1 邻接矩阵表示法
13.2.2 邻接表表示法
13.3 图的遍历
13.3.1 深度优先搜索
13.3.2 广度优先搜索
13.4 图的遍历的应用
13.4.1 无向图的连通性
13.4.2 欧拉回路
13.4.3 有向图的连通性
13.4.4 拓扑排序
13.4.5 关键路径
总结
练习13
第14章 最小生成树
14.1 生成树和最小生成树
14.2 Kruskal 算法
14.3 Prim 算法
14.4 算法的正确性
总结
练习14
第15章 最短路径问题
15.1 单源最短路径
15.1.1 非加权图的最短路径
15.1.2 加权图的最短路径
15.1.3 带有负权值的图
15.1.4 无环图
15.2 所有顶点对的最短路径
总结
练习15
第5部分 算法设计基础
第16章 算法设计基础
16.1 枚举法
16.2 贪婪法
16.3 分治法
16.3.1 整型数的乘法问题
16.3.2 平面上的最近点问题
16.4 动态规划
16.4.1 硬币找零问题
16.4.2 最优二叉查找树
16.5 回溯法
16.5.1 八皇后问题
16.5.2 分书问题
16.6 随机算法
16.6.1 跳表
16.6.2 素数检测
总结
练习16
参考文献
