顶部
收藏

数据结构:思想与实现(第2版)

“十二五”普通高等教育本科国家级规划教材

作者:
翁惠玉 俞勇
定价:
52.00 元
版面字数:
680.00千字
开本:
16开
装帧形式:
平装
页数:
480
最新
印次时间:
2026年05月
ISBN:
978-7-04-048699-5
物料号:
48699-00
出版时间:
2017-11-29
读者对象:
高等教育
一级分类:
计算机/教育技术类
二级分类:
计算机类专业核心课程
三级分类:
数据结构

数据结构是计算机类专业最基础,也是最重要的课程之一,它和程序设计一起为计算学科其他后继课程的学习奠定了基础。 上海交通大学的“数据结构”课程是国家精品课程和精品资源共享课程,本书是该课程的教学成果之一,被列入“十二五”普通高等教育本科国家级规划教材。 本书条理清晰,严格按照线性结构、树状结构、集合结构和图状结构的次序来组织。除常规的数据结构内容之外,还介绍了一些高级的数据结构,如红黑树、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 AL树
                                                                                                                                                                                                                                      • 9.2.1 AL树的定义
                                                                                                                                                                                                                                        • 9.2.2 AL树的存储实现
                                                                                                                                                                                                                                          • 9.2.3 AL树的运算实现
                                                                                                                                                                                                                                          • 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
                                                                                                                                                                                                                                                                                                                                                                                                                        • 参考文献

                                                                                                                                                                                                                                                                                                                                                                                                                        相关图书