第1章 绪论 1 1.1 引言 2 1.1.1 数据结构概述 2 1.1.2 什么是算法 5 1.1.3 算法的描述 5 1.2 程序的性能 9 1.2.1 程序的性能 9 1.2.2 程序的性能 10 1.3 渐近记法 12 1.3.1 大O标记法 12 1.3.2 大Ω标记法 12 1.3.3 大Θ标记法 13 1.3.4 渐近记法总结 13 1.4 算法复杂度等级及其分析 13 1.4.1 常数的时间复杂度O(1) 14 1.4.2 对数的时间复杂度O(logn) 14 1.4.3 线性的时间复杂度O(n) 15 1.4.4 平方的时间复杂度O(n2) 16 1.4.5 指数的时间复杂度O(2n) 16 1.4.6 算法复杂度总结 17 1.5 总结 17 1.6 习题 18 第2章 开发环境搭建及测试 19 2.1 安装JDK 20 2.1.1 解压.zip文件到指定位置 20 2.1.2 设置环境变量 20 2.1.3 验证安装 21 2.2 安装Maven 22 2.2.1 安装 22 2.2.2 设置本地仓库 22 2.2.3 设置镜像 23 2.3 安装IDE 23 2.3.1 解压.zip文件到指定位置 23 2.3.2 配置工作区间 24 2.3.3 配置JDK 24 2.3.4 配置Maven 24 2.3.5 设置字符编码 26 2.4 实战：编写单元测试用例 26 2.4.1 创建HelloWorld类 26 2.4.2 使用JUnit5 27 2.4.3 编写JUnit5测试用例 27 2.5 总结 29 2.6 习题 29 第3章 顺序表 30 3.1 Java数组初探 31 3.2 线性表数据结构 32 3.3 实战：使用数组实现顺序表 SequentialList 37 3.4 顺序表的动态扩容 47 3.4.1 顺序表的动态扩容原理 47 3.4.2 动态扩容机制的选择 48 3.4.3 ArrayList动态扩容分析 49 3.4.4 Vector动态扩容分析 50 3.4.5 选择ArrayList还是Vector 52 3.5 总结 52 3.6 习题 52 第4章 链表 53 第5章 数组和矩阵 93 第6章 栈 114 6.1 基本概念及应用场景 115 6.1.1 栈的基本概念 115 6.1.2 栈的应用场景 115 6.2 抽象数据类型 117 6.3 数组描述 117 6.4 实战：使用数组实现栈 SequentialListStack 117 6.4.1 成员变量及构造函数 117 6.4.2 统计栈的规模 118 6.4.3 判断栈中的数据元素是否为空 118 6.4.4 入栈 118 6.4.5 出栈 119 6.4.6 引用栈顶对象 119 6.4.7 时间复杂度分析总结 119 6.4.8 单元测试 119 6.5 链表描述 121 6.6 实战：使用链表实现栈 SinglyLinkedListStack 122 6.6.1 成员变量及构造函数 122 6.6.2 统计栈的规模 122 6.6.3 判断栈中的数据元素是否为空 122 6.6.4 入栈 123 6.6.5 出栈 123 6.6.6 引用栈顶对象 123 6.6.7 时间复杂度分析总结 123 6.6.8 单元测试 123 6.7 总结 125 6.8 习题 125 第7章 队列 126 第8章 跳表和散列 183 8.1 字典 184 8.1.1 跳表 184 8.1.2 散列 185 8.2 抽象数据类型 186 8.2.1 Dictionary抽象类 186 8.2.2 Map接口 187 8.2.3 Dictionary抽象类和Map接口 的抉择 194 8.3 散列HashMap 194 8.3.1 HashMap的声明 195 8.3.2 HashMap的成员变量和构造 函数 201 8.3.3 HashMap的核心方法 203 8.3.4 实战：HashMap的单元测试 210 8.3.5 实战：HashMap的应用案例 ——词频统计 214
8.4 基于跳表实现的 ConcurrentSkipListMap 216 8.4.1 ConcurrentSkipListMap的声明 216 8.4.2 ConcurrentSkipListMap的成员 变量和构造函数 217 8.4.3 ConcurrentSkipListMap的核心 方法 219 8.4.4 实战：ConcurrentSkipListMap 的单元测试 232 8.4.5 实战：ConcurrentSkipListMap 的应用案例——词频统计 235 8.5 实战：文本压缩 237 8.5.1 文本的压缩和解压 238 8.5.2 文本的压缩和解压的实现 238 8.5.3 测试文本的压缩和解压 240 8.6 总结 242 8.7 习题 243 第9章 树及二叉树 244 9.10 习题 272 第10章 优先级队列及堆 273 10.1 基本概念及应用场景 274 10.2 抽象数据类型 274 10.3 数组描述 274 10.4 实战：使用数组实现优先级队列 275 10.4.1 定义实现类 275 10.4.2 实现插入 276 10.4.3 实现删除 278 10.4.4 单元测试 279 10.5 堆描述 282 10.5.1 堆的定义 283 10.5.2 堆和普通树的区别 283 10.5.3 堆的存储 284 10.5.4 堆的常用操作 284 10.6 实战：使用堆实现优先级队列 285 10.6.1 定义实现类 286 10.6.2 实现插入 287 10.6.3 实现删除 289 10.6.4 单元测试 291 10.7 总结 293 10.8 习题 294 第11章 二叉查找树 295 第12章 平衡查找树 311 第13章 图 361 第14章 分而治之 438 第15章 贪心算法 461 第16章 动态规划 473 第17章 回溯 490 第18章 遗传算法 502 第19章 蚂蚁算法 528 第20章 汉诺塔游戏 555 20.1 实战：汉诺塔问题 556 参考文献 582