数据结构（Java语言描述）

第1章 绪 论 1 1.1 数据结构的概念 1 1.1.1 为什么要学习数据结构 2 1.1.2 有关概念和术语 4 1.1.3 数据结构的三要素 5 1.2 抽象数据类型 6 1.2.1 数据类型 6 1.2.2 抽象数据类型 7 1.3 算法概念及算法设计的问题 8 1.3.1 什么是算法 8 1.3.2 算法特性 10 1.3.3 算法的结构和表示方法 10 1.3.4 算法设计原则 11 1.3.5 几种基本的算法设计方法和策略 12 1.3.6 编程解决问题的一般步骤 12 1.4 算法分析 13 1.4.1 时间复杂度分析的两类方法 13 1.4.2 时间复杂度分析的理论框架 14 1.4.3 非递归算法时间复杂度分析步骤 19 1.4.4 典型非递归算法的时间复杂度类型 20 1.4.5 递归算法时间复杂度分析步骤 22 1.4.6 空间复杂度 23 1.5 数据结构课程的内容 23 1.6 习题 24 第2章 线性表 27 2.1 线性表的逻辑结构 27 2.2 顺序表概念及存储特点 29 2.2.1 顺序表的逻辑特点 29 2.2.2 顺序表面向对象描述 29 2.3 顺序表的重要算法及实现 31 2.3.1 初始化 31 2.3.2 顺序表容量管理 31 2.3.3 数据存取 32 2.3.4 向顺序表中插入元素 33 2.3.5 删除顺序表中的元素 34 2.3.6 查找元素 35 2.3.7 顺序表中元素的有序插入与排序 36 2.3.8 顺序表转换为数组 37 2.3.9 顺序表转换为字符串 38 2.4 单链表概念及类定义 38 2.4.1 单链表基本概念 38 2.4.2 链表面向对象描述 41 2.5 单链表重要算法实现 44 2.5.1 数据存取 44 2.5.2 向链表中插入元素 44 2.5.3 删除链表节点 47 2.5.4 查找节点 49 2.5.5 向链表中有序插入节点 50 2.5.6 链表排序 52 2.5.7 链表转换为字符串和数组 53 2.6* 链表迭代器 54 2.6.1 迭代器的概念 54 2.6.2 与迭代器有关的Java语言特性 55 2.6.3 链表类LinkList迭代器的实现 56 2.7 循环链表与双向链表 58 2.7.1 循环链表 58 2.7.2 双向链表 59 2.8* 顺序表和链表的比较 60 2.9 习题 61 第3章 特殊的线性结构 64 3.1 栈 64 3.1.1 基本概念 64 3.1.2 链栈——栈的链表实现 65 3.1.3 顺序栈——栈的数组实现 66 3.1.4 表达式求值 68 3.2 队列 72 3.2.1 队列概念 72 3.2.2 链式队列 73 3.2.3 顺序队列 74 3.2.4 循环队列 75 3.2.5 队列应用 76 3.3 特殊矩阵 78 3.3.1 矩阵存储方式 78 3.3.2 对称矩阵和三角矩阵 79 3.3.3 对角矩阵 80 3.4 稀疏矩阵 81 3.4.1 三元组 81 3.4.2 矩阵抽象数据类型 82 3.4.3 稀疏矩阵的三元组顺序表表示 83 3.4.4 稀疏矩阵的行链表表示 88 3.4.5 稀疏矩阵的十字链表表示 91 3.5 广义表 92 3.5.1 广义表的定义和基本运算 93 3.5.2 广义表的存储结构 95 3.6 习题 96 第4章 线性查找算法 99 4.1 查找的基本概念 99 4.1.1 什么是查找及查找结构 99 4.1.2 查找结构的分类 100 4.1.3 平均查找长度 100 4.2 线性查找表 100 4.2.1 顺序查找 100 4.2.2 二分查找 100 4.2.3 分块查找 102 4.2.4 顺序表三种查找方法的比较 103 4.3 哈希查找 103 4.3.1 哈希表 103 4.3.2 哈希函数的构造方法 104 4.3.3 处理冲突的方法 106 4.3.4 哈希查找算法性能分析 109 4.4 哈希映射 109 4.4.1 映射（Map）概念 109 4.4.2 哈希表实现映射 110 4.5 串匹配 112 4.5.1 简单的模式匹配算法 112 4.5.2 KMP模式匹配算法 114 4.6 习题 118 第5章 排序算法 122 5.1 基本概念 122 5.2 插入排序 122 5.2.1 算法设计 123 5.2.2 时间复杂度分析 124 5.3 选择排序 124 5.3.1 算法设计 124 5.3.2 时间复杂度分析 125 5.4 冒泡排序 126 5.4.1 算法设计 126 5.4.2 时间复杂度分析 127 5.5 快速排序 127 5.5.1 快速排序的思想 127 5.5.2 快速排序算法实现 128 5.5.3 时间复杂度分析 129 5.6 归并排序 130 5.6.1 有序表的合并算法 130 5.6.2 递归归并排序 131 5.6.3 迭代归并排序 132 5.6.4 时间复杂度分析 133 5.7 基数排序 134 5.7.1 桶排序 134 5.7.2 基数排序应用举例 134 5.8* 希尔排序 135 5.8.1 排序过程与算法设计 135 5.8.2 时间复杂度分析 137 5.9 习题 138 第6章 二叉树与树 145 6.1 树与二叉树一般概念 145 6.1.1 树 145 6.1.2 二叉树 146 6.2 二叉树的性质 148 6.3 二叉树存储结构 150 6.3.1 顺序存储 150 6.3.2 链式存储 151 6.4 二叉树遍历 152 6.4.1 二叉树遍历概念 152 6.4.2 先序遍历（DLR） 153 6.4.3 中序遍历（LDR） 154 6.4.4 后序遍历（LRD） 154 6.4.5 层次遍历 155 6.4.6 遍历的应用 156 6.4.7 根据已知的遍历序列恢复二叉树 157 6.5 哈夫曼（Huffman）树及其应用 159 6.5.1 最优二叉树（Huffman树）概念 159 6.5.2 Huffman树的构造方法 160 6.5.3 Huffman编码 162 6.5.4 Huffman编码、码算法实现 164 6.6 递归 172 6.6.1 递归调用树 172 6.6.2 递归栈 176 6.6.3 二叉树遍历的非递归算法 179 6.7 树和森林 182 6.7.1 基本概念 182 6.7.2 树的存储结构 182 6.7.3 树的遍历 185 6.7.4 树的深度优先搜索与回溯法 186 6.7.5 树与并查集 190 6.8 习题 192 第7章 查找树 198 7.1 二叉查找树概念 198 7.1.1 二叉查找树定义 198 7.1.2 二叉查找树的面向对象描述 199 7.2 二叉查找树主要算法 202 7.2.1 求最大、最小值算法 202 7.2.2 查找算法 202 7.2.3 插入算法 204 7.2.4 删除算法 206 7.2.5 时间复杂度分析 209 7.3 AVL平衡二叉树 210 7.3.1 平衡二叉树的概念 211 7.3.2 平衡调整 214 7.3.3 AVL树的查找算法 218 7.3.4 AVL树的插入算法 218 7.3.5 AVL树删除算法 219 7.3.6 AVL树时间复杂度分析 220 7.4 B-树 222 7.4.1 分块索引查找 222 7.4.2 B-树定义 222 7.4.3 B-树查找 223 7.4.4 B-树的插入 225 7.4.5 B-树删除 226 7.5 B+树 228 7.6 习题 229 第8章 堆与优先队列及堆排序 233 8.1堆 233 8.1.1 堆的基本算法 234 8.1.2 堆的实现 237 8.2 优先队列 239 8.3 堆排序 240 8.4 习题 241 第9章 图结构及相关算法 242 9.1 图的概念 242 9.1.1 什么是图 242 9.1.2 图论的基本概念 243 9.1.3 树和森林 246 9.2 图的基本操作与图的存储结构 246 9.2.1 图的基本操作 247 9.2.2 图的存储结构概述 250 9.2.3 图的邻接矩阵存储 250 9.2.4 图的邻接表存储 255 9.2.5 图的边集数组存储 260 9.3 图的遍历 261 9.3.1 深度优先遍历 261 9.3.2 广度优先遍历 263 9.3.3 利用图遍历算法研究图的连通性 264 9.4 最小生成树问题 266 9.4.1 图的生成树和生成森林 266 9.4.2 图的最小生成树概念 267 9.4.3 构造最小生成树的Prim算法 268 9.4.4 构造最小生成树的Kruskal算法 271 9.5 最短路径问题 273 9.5.1 从一个源点到其他各点的最短路径 274 9.5.2 所有点对之间的最短路径 278 9.6 拓扑排序问题 280 9.6.1 偏序关系 280 9.6.2 拓扑排序 280 9.6.3 拓扑排序应用 281 9.7* 关键路径问题 283 9.7.1 AOE网（Activity On Edge network） 283 9.7.2 关键路径 284 9.8 习题 287