数据结构(Java版第2版微课视频版题库版21世纪高等学校计算机基础实用系列教材)

本书在选材与编排上 ，贴近当前普通高等院校 “数据结构”课程的现状和 发展趋势，内容难度适度 ，突出实用性和应用性。 在内容选取与结构上，本 书并未对各种数据结构面 面俱到，而是通过分类和 讲解典型结构，使读者形 成对数据结构的宏观认识 。根据内容侧重，本书共 8章，分别为绪论、线性 表、栈和队列、串和数组 、树结构、图、排序和查 找。 本书是高等院校计算 机科学、软件工程及相关 专业“数据结构”课程的理 想教材，也可供程序员、 系统工程师等相关人员阅 读参考。

第1章 绪论 1.1 引言 1.1.1 学习目的 1.1.2 课程内容 1.2 基本概念 1.2.1 数据与数据结构 1.2.2 数据类型与抽象数据类型 1.3 算法 1.3.1 算法的概念 1.3.2 算法描述 1.3.3 算法分析 1.4 Java提供的泛型方法 1.4.1 使用Object类表示泛型 1.4.2 使用Comparable接口类型表示泛型 小结 习题1 第2章 线性表 2.1 线性表及其基本操作 2.1.1 线性表的基本概念 2.1.2 抽象数据类型描述 2.1.3 线性表的存储和实现 2.2 线性表的顺序存储 2.2.1 顺序表 2.2.2 顺序表的基本操作实现 2.3 线性表的链式存储和实现 2.3.1 单链表 2.3.2 单链表的基本操作实现 2.3.3 其他链表 2.4 顺序表与链表的比较 2.5 实验 2.5.1 数组奇偶分割 2.5.2 反转链表 2.5.3 链表环检测 小结 习题2 第3章 栈和队列 3.1 栈 3.1.1 栈的基本概念 3.1.2 栈的抽象数据类型描述 3.1.3 顺序栈 3.1.4 链栈 3.2 队列 3.2.1 队列的基本概念 3.2.2 队列的抽象数据类型描述 3.2.3 顺序队列 3.2.4 链队列 3.2.5 优先级队列 3.3 栈和队列的比较 3.4 实验 3.4.1 汉诺塔 3.4.2 吃巧克力 3.4.3 表达式求值 小结 习题3 第4章 串和数组 4.1 串 4.1.1 串的基本概念 4.1.2 串的抽象数据类型描述 4.1.3 顺序串 4.1.4 链串 4.2 串的模式匹配 4.2.1 Brute-Force算法 4.2.2 KMP算法 4.3 数组 4.3.1 数组的基本概念 4.3.2 数组的特性 4.3.3 数组的遍历 4.4 特殊矩阵的压缩存储 4.4.1 三角矩阵的压缩存储 4.4.2 对称矩阵的压缩存储 4.4.3 对角矩阵的压缩存储 4.4.4 稀疏矩阵的压缩存储 4.5 实验 4.5.1 最大连续子数组 4.5.2 最大上升子序列 4.5.3 走迷宫 小结 习题4 第5章 树结构 5.1 树 5.1.1 树的基本概念 5.1.2 树的术语 5.2 二叉树 5.2.1 二叉树的基本概念 5.2.2 二叉树的性质 5.2.3 二叉树的存储结构 5.2.4 二叉树的遍历 5.2.5 二叉树遍历算法的应用 5.2.6 二叉树的建立 5.3 哈夫曼树及哈夫曼编码 5.3.1 哈夫曼树的基本概念 5.3.2 哈夫曼树的构造 5.3.3 哈夫曼编码 5.3.4 构造哈夫曼树和哈夫曼编码的类的描述 5.4 树和森林 5.4.1 树的存储结构 5.4.2 树的遍历规则 5.5 实验 5.5.1 平衡二又树检验 5.5.2 查找最近公共祖先 5.5.3 由前序遍历和中序遍历构造二叉树 小结 习题5 第6章 图 6.1 图概述 6.1.1 图的基本概念 6.1.2 图的抽象数据类型描述 6.2 图的存储结构 6.2.1 邻接矩阵 6.2.2 邻接表 6.3 图的遍历 6.4 最小生成树 6.4.1 最小生成树的基本概念 6.4.2 Kruskal算法 6.4.3 Prim算法 6.5 最短路径 6.5.1 求某个顶点到其余顶点的最短路径 6.5.2 求任意两个顶点间的最短路径 6.6 拓扑排序和关键路径 6.6.1 拓扑排序 6.6.2 关键路径 6.7 实验 6.7.1 Prime算法 6.7.2 单源最短路 小结 习题6 第7章 排序 7.1 排序概述 7.1.1 排序的基本概念 7.1.2 排序算法的性能评价 7.1.3 待排序的记录和顺序表的类描述 7.2 插入排序 7.2.1 直接插入排序 7.2.2 希尔排序 7.3 交换排序 7.3.1 冒泡排序 7.3.2 快速排序 7.4 选择排序 7.4.1 直接选择排序 7.4.2 堆排序 7.5 归并排序 7.6 实验 7.6.1 插入排序 7.6.2 链表排序 7.6.3 链表排序(进阶) 小结 习题7 第8章 查找 8.1 查找的基本概念 8.1.1 什么是查找 8.1.2 查找表 8.1.3 平均查找长度 8.2 静态表查找 8.2.1 顺序查找 8.2.2 二分查找 8.2.3 分块查找 8.3 动态表查找 8.3.1 二叉排序树查找 8.3.2 平衡二叉树 8.3.3 B一树和B+树 8.4 哈希表查找 8.4.1 哈希表的概念 8.4.2 哈希函数 8.4.3 解决冲突的方法 8.4.4 哈希表查找性能分析 8.5 实验 8.5.1 寻找山形数组的顶点 8.5.2 查找重复数 8.5.3 有序矩阵查找 小结 习题8 附录A 综合实践题 参考文献