第19章 泛型 1
19.1 引言 1
19.2 动机和优点 1
19.3 定义泛型类和接口 4
19.4 泛型方法 5
19.5 示例学习：对一个对象数组进行排序 7
19.6 原生类型和向后兼容 8
19.7 通配泛型 10
19.8 泛型的擦除和限制 12
19.9 示例学习：泛型矩阵类 15
关键术语 19
本章小结 19
测试题 20
编程练习题 20
第20章 线性表、栈、队列和优先队列 22
20.1 引言 22
20.2 集合 23
20.3 迭代器 26
20.4 使用forEach方法 27
20.5 线性表 28
20.5.1 List接口中的通用方法 28
20.5.2 数组线性表类ArrayL.i st和链表类LinkedList 29
20.6 Comparator接口 32
20.7 线性表和集合的静态方法 36
20.8 示例学习：弹球 39
20.9 向量类和栈类 42
20.10 队列和优先队列 44
20.10.1 Queue接口 44
20.10.2 双端队列Deque和链表LinkedList 45
20.11 示例学习：表达式求值 47
关键术语 51
本章小结 51
测试题 51
编程练习题 51
第21章 规则集和映射 57
21.1 引言 57
21.2 规则集 57
21.2.1 HashSet 58
21.2.2 LinkedHashSet 61
21.2.3 TreeSet 62
21.3 比较规则集和线性表的性能 65
21.4 示例学习：关键字计数 67
21.5 映射 69
21.6 示例学习：单词的出现次数 73
21.7 单元素与不可变的集合和映射 75
关键术语 76
本章小结 76
测试题 77
编程练习题 77
第22章 开发高效算法 79
22.1 引言 79
22.2 使用大O标记来衡量算法效率 79
22.3 示例：确定大O 81
22.4 分析算法的时间复杂度 85
22.4.1 分析二分查找算法 85
22.4.2 分析选择排序算法 85
22.4.3 分析汉诺塔问题 85
22.4.4 常用的递推关系 86
22.4.5 比较常用的增长函数 86
22.5 使用动态编程寻找斐波那契数 87
22.6 使用欧几里得算法求最大公约数 89
22.7 寻找素数的高效算法 93
22.8 使用分而治之法寻找最近点对 99
22.9 使用回溯法解决八皇后问题 101
22.10 计算几何：寻找凸包 103
22.10.1 卷包裹算法 104
22.10.2 格雷厄姆算法 105
关键术语 106
本章小结 106
测试题 107
编程练习题 107
第23章 排序 114
23.1 引言 114
23.2 插入排序 115
23.3 冒泡排序 117
23.4 归并排序 119
23.5 快速排序 122
23.6 堆排序 126
23.6.1 堆的存储 127
23.6.2 添加一个新的结点 127
23.6.3 删除根结点 128
23.6.4 Heap类 129
23.6.5 使用Heap类进行排序 131
23.6.6 堆排序的时间复杂度 132
23.7 桶排序和基数排序 133
23.8 外部排序 135
23.8.1 实现阶段I 136
23.8.2 实现阶段Ⅱ 137
23.8.3 结合两个阶段 139
23.8.4 外部排序复杂度 141
关键术语 142
本章小结 142
测试题 142
编程练习题 142
第24章 实现线性表、栈、队列和优先队列 146
24.1 引言 146
24.2 线性表的通用操作 146
24.3 数组线性表 149
24.4 链表 156
24.4.1 结点 156
24.4.2 MyLinkedList类 158
24.4.3 实现MyLinkedList 159
24.4.4 MyArrayList和MyLinkedList 167
24.4.5 链表的变体 167
24.5 栈和队列 169
24.6 优先队列 172
本章小结 173
测试题 174
编程练习题 174
第25章 二叉搜索树 176
25.1 引言 176
25.2 二叉搜索树 176
25.2.1 表示二叉搜索树 177
25.2.2 查找一个元素 178
25.2.3 在BST中插入一个元素 178
25.2.4 树的遍历 179
25.2.5 BST类 180
25.3 删除BST中的一个元素 189
25.4 树的可视化和MVC 194
25.5 迭代器 197
25.6 示例学习：数据压缩 199
关键术语 204
本章小结 204
测试题 204
编程练习题 204
第26章 AVL树 208
26.1 引言 208
26.2 重新平衡树 209
26.3 为AVL树设计类 211
26.4 重写insert方法 212
26.5 实现旋转 213
26.6 实现delete方法 213
26.7 AVLTree类 214
26.8 测试AVLTree类 219
26.9 AVL树的时间复杂度分析 222
关键术语 222
本章小结 223
测试题 223
编程练习题 223
第27章 散列 225
27.1 引言 225
27.2 什么是散列 225
27.3 散列函数和散列码 226
27.3.1 基本数据类型的散列码 226
27.3.2 字符串的散列码 227
27.3.3 压缩散列码 227
27.4 使用开放地址法处理冲突 228
27.4.1 线性探测法 228
27.4.2 二次探测法 230
27.4.3 双重散列法 230
27.5 使用分离链接法处理冲突 232
27.6 装填因子和再散列 232
27.7 使用散列实现映射 233
27.8 使用散列实现规则集 242
关键术语 248
本章小结 249
测试题 249
编程练习题 249
第28章 图及其应用 251
28.1 引言 251
28.2 基本的图术语 252
28.3 表示图 254
28.3.1 表示顶点 254
28.3.2 表示边：边数组 255
28.3.3 表示边：Edge对象 256
28.3.4 表示边：邻接矩阵 256
28.3.5 表示边：邻接线性表 257
28.4 图的建模 259
28.5 图的可视化 268
28.6 图的遍历 271
28.7 深度优先搜索 272
28.7.1 DFS的算法 272
28.7.2 DFS的实现 273
28.7.3 DFS的应用 274
28.8 示例学习：连通圆问题 275
28.9 广度优先搜索 278
28.9.1 BFS的算法 278
28.9.2 BFS的实现 278
28.9.3 BFS的应用 280
28.10 示例学习：9枚硬币反面问题 281
关键术语 286
本章小结 286
测试题 286
编程练习题 286
第29章 加权图及其应用 291
29.1 引言 291
29.2 加权图的表示 292
29.2.1 加权边的表示：边数组 292
29.2.2 加权邻接矩阵 293
29.2.3 邻接线性表 293
29.3 WeightedGraph类 294
29.4 最小生成树 301
29.4.1 最小生成树算法 302
29.4.2 完善Prim的MST算法 303
29.4.3 MST算法的实现 304
29.5 寻找最短路径 307
29.6 示例学习：加权的9枚硬币反面问题 315
关键术语 318
本章小结 318
测试题 319
编程练习题 319
第30章 集合流的聚合操作 325
30.1 引言 325
30.2 流管道 326
30.2.1 Stream.of、limit、forEach方法 328
30.2.2 sorted方法 329
30.2.3 filter方法 329
30.2.4 max和min方法 329
30.2.5 anyMatch、allMatch和noneMatch方法 329
30.2.6 map、di stinct和count方法 329
30.2.7 findFirst、findAny和toArray方法 330
30.3 IntStream、LongStream和DoubleStream 331
30.4 并行流 333
30.5 使用reduce方法进行流的归约 336
30.6 使用collect方法进行流的归约 338
30.7 使用groupingBy收集器进行元素分组 341
30.8 示例学习 344
30.8.1 示例学习：数字分析 344
30.8.2 示例学习：计算字母的出现次数 345
30.8.3 示例学习：计算字符串中每个字母的出现次数 346
30.8.4 示例学习：处理二维数组中的所有元素 347
30.8.5 示例学习：得到目录大小 348
30.8.6 示例学习：关键字计数 349
30.8.7 示例学习：单词出现次数 350
本章小结 351
测试题 351
编程练习题 351
附录A Java关键字 353
附录B ASCII字符集 354
附录C 操作符优先级表 355
附录D Java修饰符 356
附录E 特殊浮点值 357
附录F 数系 358
附录G 位操作符 362
附录H 正则表达式 363
附录I 枚举类型 367