精讲数据结构(Java语言实现)/计算机技术开发与应用丛书

本书按照循序渐进的顺 序讲解了多种常见数据结构 的相关定义、实现方式及应 用场景，并通过提供配套代 码、研读Java源码的方式， 让读者能够通过体会代码实 现细节的方式加深对各种常 见数据结构从理论定义到实 践落地过程的理解。本书除 了阐述各种常见数据结构的 基本定义外，还引申的讲解 了常见数据结构内部隐含的 特点，使读者能够更加全面 地了解各种常见数据结构的 特征和优缺点。 本书共9章。第1章对数 据结构时间、空间效能的评 判标准进行讲解。第2章对 数组和链表及其引申结构进 行讲解。第3章对栈和队列 两种基于数组和链表的逻辑 结构讲解。第4章对常见的 搜索、排序算法进行讲解。 第5章对字符串结构及字符 串匹配算法进行讲解。第6 章对多种常见树形结构及相 关算法进行讲解。第7章对 堆结构进行讲解。第8章对 散列表结构进行讲解。第9 章对图结构及其常见算法进 行讲解。 本书既适合具有一定 Java语言基础的高校学生作 为学习数据结构、研究其实 现原理的参考书籍，也对具 有一定工作经验、需要对不 同数据结构之间差异性、内 在特征进行研究的人群均有 一定参考价值。

塔拉，国家认证的软件开发工程师、Oracle认证的Java开发工程师。毕业于黑龙江大学计算机科学技术专业，毕业后从事软件研发工作，并于2016年正式进入IT教育行业。从业期间曾在多家IT教育机构及高校从事讲师、课程研发工作，至今已授业数百名学员，积累了丰富的教育教学经验，对IT行业教学内容及教育体系有深入了解。从事IT教育行业过程中，作者坚持研究各种应用底层原理与编程思想，在数据结构、通用型算法及设计模式等方面有所心得。

第1章 绪论 1.1 时间复杂度 1.2 空间复杂度 第2章 数组与链表 2.1 数组结构 2.1.1 数组的创建与基本操作 2.1.2 数组内存特性分析 2.1.3 内存中的多维数组 2.2 链表结构 2.2.1 基本概念普及 2.2.2 链表内存特性分析 2.2.3 链表衍生结构 第3章 栈和队列 3.1 栈结构 3.1.1 栈结构概述 3.1.2 栈结构的实现 3.1.3 栈结构的应用场景 3.2 队列结构 3.2.1 队列结构概述 3.2.2 队列结构的实现 3.2.3 队列结构的应用场景 3.2.4 队列结构的衍生 第4章 递归、查找与排序 4.1 递归 4.1.1 简单的递归案例 4.1.2 递归结构基础 4.1.3 递归结构进阶 4.2 查找 4.2.1 二分查找 4.2.2 插值查找 4.2.3 斐波那契查找 4.3 排序 4.3.1 排序算法的稳定性 4.3.2 冒泡排序 4.3.3 选择排序 4.3.4 插入排序 4.3.5 希尔排序 4.3.6 归并排序 4.3.7 快速排序 4.3.8 堆排序 4.3.9 计数排序 4.3.10 桶排序 第5章 字符串 5.1 基本概念与实现 5.1.1 字符串的基本概念 5.1.2 Java中的String类 5.2 字符串匹配算法 5.2.1 通用定义 5.2.2 BF算法 5.2.3 RK算法 5.2.4 KMP算法 5.2.5 BM算法 5.2.6 Sunday算法 第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.3.1 哈夫曼树的构建 6.3.2 获取明文字符的哈夫曼编码 6.3.3 文本编码与译码 6.4 线索二叉树与Morris遍历 6.4.1 线索二叉树的节点定义方式 6.4.2 二叉树的线索化 6.4.3 线索二叉树的遍历 6.4.4 二叉树的Morris遍历 6.5 二叉排序树 6.5.1 二叉排序树的结构特点 6.5.2 二叉排序树的增删查找 6.5.3 二叉排序树退化为单链表的情况 6.6 平衡二叉树（AVL树） 6.6.1 AVL树节点的旋转方式 6.6.2 节点增删导致不平衡的情况 6.6.3 AVL树与平衡二叉树的对比 6.72 -3-4树 6.7.12 -3-4树的结构特点 6.7.22 -3-4树的增删查找 6.8 红黑树 6.8.1 红黑树的平衡策略与染色规则 6.8.22 -3-4树向红黑树的转换 6.8.3 红黑树的节点增删与结构调整 6.9 B树与B+树 6.9.1 B树结构 6.9.2 B+树结构 6.9.3 B树与B+树在实际应用方面的区别 6.10 字典树（Trie树） 6.10.1 字典树的结构特点 6.10.2 字典树的基本功能与实现方式 6.10.3 字典树的时间复杂度与空间复杂度 6.11 树状数组 6.11.1 前置知识：非负整数的lowBit操作 6.11.2 树状数组的构建方式 6.11.3 树状数组的基本操作 6.11.4 差分数组与基本操作 第7章 堆结构 7.1 堆结构基础 7.2 二叉堆 7.2.1 二叉堆的存储方式与特性 7.2.2 二叉堆的元素添加操作 7.2.3 二叉堆的堆顶元素删除操作 7.2.4 二叉堆与Top-K问题 7.3 左式堆与斜堆 7.3.1 左式堆 7.3.2 斜堆 7.4 二项堆 7.4.1 二项树结构 7.4.2 二项堆的结构特点 7.4.3 二项堆的合并操作 7.4.4 二项堆的元素添加操作 7.4.5 二项堆的堆顶元素删除操作 第8章 散列表 8.1 散列表的基本概念 8.2 散列函数的常见实现方式 8.2.1 前置知识：整数的模运算 8.2.2 直接定址法 8.2.3 除留余数法 8.2.4 数字分析法 8.2.5 平方取中法 8.2.6 折叠法 8.2.7 随机数法 8.2.8 全域散列法 8.3 散列表常见实现方式 8.3.1 开放地址法实现散列表 8.3.2 链地址法实现散列表 8.3.3 完全散列的实现 8.4 散列表的平均查找长度 8.5 Java中的散列表 8.5.1 Java中的hashCode()与equals()方法 8.5.2 HashMap类与HashSet类 第9章 图结构 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.3.1 迪杰斯特拉算法求解有向带权图的单源最短路径 9.3.2 弗洛伊德算法求解有向带权图的多源最短路径 9.4 AOV网和拓扑排序问题 9.5 AOE网和关键路径问题 参考文献