目　　录
Data Structures and Problem Solving Using Java, Fourth Edition
译者序
前言
第一部分　Java之旅
第1章　Java的基本特性　　2
1.1　总体运行环境　　2
1.2　第一个程序　　3
1.2.1　注释　　3
1.2.2　main　　3
1.2.3　终端输出　　4
1.3　Java的基本类型　　4
1.3.1　基本类型　　4
1.3.2　常量　　4
1.3.3　基本类型的声明和初始化　　5
1.3.4　终端输入和输出　　5
1.4　基本运算符　　5
1.4.1　赋值运算符　　5
1.4.2　二元算术运算符　　6
1.4.3　一元运算符　　6
1.4.4　类型转换　　7
1.5　条件语句　　7
1.5.1　关系运算符和相等运算符　　7
1.5.2　逻辑运算符　　8
1.5.3　if语句　　8
1.5.4　while语句　　9
1.5.5　for语句　　9
1.5.6　do语句　　10
1.5.7　break和continue语句　　11
1.5.8　switch语句　　11
1.5.9　条件运算符　　12
1.6　方法　　12
1.6.1　方法名的重载　　13
1.6.2　存储类　　13
1.7　总结　　13
1.8　核心概念　　14
1.9　常见错误　　15
1.10　网络资源　　15
1.11　练习　　15
1.12　参考文献　　16
第2章　引用类型　　18
2.1　什么是引用　　18
2.2　对象和引用的基础知识　　19
2.2.1　点运算符　　19
2.2.2　对象的声明　　20
2.2.3　垃圾收集　　20
2.2.4　=的含义　　21
2.2.5　参数传递　　22
2.2.6　==的含义　　22
2.2.7　没有对象的运算符重载　　23
2.3　字符串　　23
2.3.1　字符串操作的基础　　23
2.3.2　字符串连接　　23
2.3.3　字符串比较　　24
2.3.4　其他String方法　　24
2.3.5　将其他类型转换为字符串　　24
2.4　数组　　25
2.4.1　声明、赋值和方法　　25
2.4.2　动态数组扩展　　27
2.4.3　ArrayList　　29
2.4.4　多维数组　　30
2.4.5　命令行参数　　31
2.4.6　增强的for循环　　31
2.5　异常处理　　32
2.5.1　处理异常　　32
2.5.2　finally子句　　33
2.5.3　常见的异常　　33
2.5.4　throw和throws子句　　34
2.6　输入和输出　　35
2.6.1　基本的流操作　　35
2.6.2　Scanner类型　　36
2.6.3　顺序文件　　38
2.7　总结　　40
2.8　核心概念　　40
2.9　常见错误　　41
2.10　网络资源　　42
2.11　练习　　42
2.12　参考文献　　45
第3章　对象和类　　46
3.1　什么是面向对象程序设计　　46
3.2　简单示例　　47
3.3　javadoc　　48
3.4　基本方法　　50
3.4.1　构造方法　　50
3.4.2　设置方法和访问方法　　51
3.4.3　输出和toString　　52
3.4.4　equals　　52
3.4.5　main　　52
3.5　示例：使用java.math.
BigInteger　　52
3.6　其他结构成分　　54
3.6.1　this引用　　54
3.6.2　用于构造方法的this简写　　55
3.6.3　instanceof运算符　　55
3.6.4　实例成员和静态成员　　55
3.6.5　静态域和方法　　55
3.6.6　静态初始化程序　　57
3.7　示例：实现BigRational类　　58
3.8　包　　61
3.8.1　import指令　　61
3.8.2　package语句　　62
3.8.3　CLASSPATH环境变量　　63
3.8.4　包可见性规则　　64
3.9　设计模式：复合　　64
3.10　总结　　65
3.11　核心概念　　66
3.12　常见错误　　67
3.13　网络资源　　67
3.14　练习　　67
3.15　参考文献　　71
第4章　继承　　72
4.1　什么是继承　　72
4.1.1　创建新的类　　72
4.1.2　类型兼容性　　76
4.1.3　动态调度和多态　　76
4.1.4　继承层次结构　　77
4.1.5　可见性规则　　77
4.1.6　构造方法和super　　78
4.1.7　final方法和类　　79
4.1.8　覆盖一个方法　　80
4.1.9　再次讨论类型兼容性　　81
4.1.10　数组类型的兼容性　　82
4.1.11　协变返回类型　　82
4.2　设计层次结构　　83
4.2.1　抽象方法和类　　85
4.2.2　为未来而设计　　86
4.3　多继承　　87
4.4　接口　　88
4.4.1　规范接口　　89
4.4.2　实现一个接口　　89
4.4.3　多接口　　90
4.4.4　接口是抽象类　　90
4.5　Java中的基本继承　　90
4.5.1　Object类　　90
4.5.2　异常的层次结构　　90
4.5.3　I/O：装饰器模式　　92
4.6　使用继承实现泛型组件　　94
4.6.1　Object用于泛型　　94
4.6.2　基本类型的包装类　　96
4.6.3　装箱/拆箱　　97
4.6.4　适配器：改变接口　　97
4.6.5　为泛型使用接口类型　　98
4.7　使用Java 5泛型实现泛型组件　　99
4.7.1　简单的泛型类和接口　　99
4.7.2　有界通配符　　100
4.7.3　泛型静态方法　　101
4.7.4　类型限定　　101
4.7.5　类型擦除　　102
4.7.6　对泛型的限制　　103
4.8　函子　　105
4.8.1　嵌套类　　107
4.8.2　局部类　　108
4.8.3　匿名类　　109
4.8.4　嵌套类和泛型　　110
4.9　动态调度细节　　110
4.10　总结　　112
4.11　核心概念　　113
4.12　常见错误　　114
4.13　网络资源　　114
4.14　练习　　115
4.15　参考文献　　121
第二部分　算法和构成要素
第5章　算法分析　　124
5.1　什么是算法分析　　124
5.2　算法运行时间示例　　126
5.3　最大连续子序列和问题　　127
5.3.1　容易理解的O(N3)算法　　128
5.3.2　改进的O(N2)算法　　129
5.3.3　线性算法　　130
5.4　一般的大O规则　　132
5.5　对数　　134
5.6　静态搜索问题　　136
5.6.1　顺序搜索　　136
5.6.2　二分搜索　　136
5.6.3　插值搜索　　138
5.7　检查算法分析　　139
5.8　大O分析的局限性　　140
5.9　总结　　140
5.10　核心概念　　140
5.11　常见错误　　141
5.12　网络资源　　141
5.13　练习　　141
5.14　参考文献　　148
第6章　Collections API　　149
6.1　介绍　　149
6.2　迭代器模式　　150
6.2.1　迭代器的基本设计　　151
6.2.2　基于继承的迭代器和工厂
方法　　152
6.3　Collections API：容器和迭代器　　154
6.3.1　Collection接口　　154
6.3.2　Iterator接口　　156
6.4　泛型算法　　158
6.4.1　Comparator函数对象　　158
6.4.2　Collections类　　159
6.4.3　二分搜索　　160
6.4.4　排序　　162
6.5　List接口　　162
6.5.1　ListIterator接口　　163
6.5.2　LinkedList类　　164
6.5.3　List的运行时间　　166
6.5.4　在List的中间进行删除和
插入　　168
6.6　栈和队列　　169
6.6.1　栈　　169
6.6.2　栈和计算机语言　　170
6.6.3　队列　　171
6.6.4　Collections API中的栈和
队列　　171
6.7　集合　　172
6.7.1　TreeSet类　　173
6.7.2　HashSet类　　174
6.8　映射　　177
6.9　优先队列　　181
6.10　Collections API中的视图　　183
6.10.1　List中的subList方法　　183
6.10.2　SortedSet中的headSet、subSet和tailSet方法　　183
6.11　总结　　184
6.12　核心概念　　184
6.13　常见错误　　185
6.14　网络资源　　185
6.15　练习　　186
6.16　参考文献　　192
第7章　递归　　193
7.1　什么是递归　　193
7.2　背景：数学归纳法证明　　194
7.3　基本递归　　195
7.3.1　输出任意基数的数　　196
7.3.2　递归为什么有效　　198
7.3.3　递归的工作原理　　199
7.3.4　出现过多的递归可能是
危险的　　200
7.3.5　树的预览　　201
7.3.6　其他示例　　202
7.4　数值应用　　204
7.4.1　模运算　　205
7.4.2　模幂运算　　205
7.4.3　最大公约数和乘法逆元　　206
7.4.4　RSA加密系统　　208
7.5　分治算法　　210
7.5.1　最大连续子序列和问题　　210
7.5.2　基本分治重现的分析　　212
7.5.3　分治法运行时间的一般上界　　214
7.6　动态规划　　216
7.7　回溯　　218
7.8　总结　　221
7.9　核心概念　　222
7.10　常见错误　　222
7.11　网络资源　　223
7.12　练习　　223
7.13　参考文献　　228
第8章　排序算法　　229
8.1　排序的重要性　　229
8.2　预备知识　　230
8.3　插入排序和其他简单排序的分析　　230
8.4　希尔排序　　232
8.5　归并排序　　235
8.5.1　线性时间内有序数组的合并　　235
8.5.2　归并排序算法　　236
8.6　快速排序　　238
8.6.1　快速排序算法　　239
8.6.2　快速排序的分析　　240
8.6.3　选择枢轴　　243
8.6.4　划分策略　　244
8.6.5　关键字等于枢轴　　245
8.6.6　三元中值划分　　246
8.6.7　小数组　　246
8.6.8　Java快速排序例程　　247
8.7　快速选择　　248
8.8　排序的下界　　250
8.9　总结　　250
8.10　核心概念　　251
8.11　常见错误　　251
8.12　网络资源　　251
8.13　练习　　251
8.14　参考文献　　255
第9章　随机化　　256
9.1　为什么需要随机数　　256
9.2　随机数生成器　　256
9.3　不均匀随机数　　262
9.4　生成一个随机排列　　263
9.5　随机算法　　264
9.6　随机素数测试　　266
9.7　总结　　268
9.8　核心概念　　268
9.9　常见错误　　269
9.10　网络资源　　269
9.11　练习　　269
9.12　参考文献　　270
第三部分　应用程序
第10章　娱乐和游戏　　274
10.1　字谜游戏　　274
10.1.1　理论　　274
10.1.2　Java实现　　275
10.2　井字棋游戏　　280
10.2.1　α-β剪枝　　280
10.2.2　置换表　　282
10.2.3　计算机下棋　　285
10.3　总结　　286
10.4　核心概念　　286
10.5　常见错误　　286
10.6　网络资源　　286
10.7　练习　　286
10.8　参考文献　　288
第11章　栈和编译器　　289
11.1　平衡符号检查　　289
11.1.1　基本算法　　289
11.1.2　实现　　290
11.2　一个简单的计算器　　297
11.2.1　后缀机器　　298
11.2.2　中缀到后缀的转换　　299
11.2.3　实现　　300
11.2.4　表达式树　　306
11.3　总结　　307
11.4　核心概念　　307
11.5　常见错误　　308
11.6　网络资源　　308
11.7　练习　　308
11.8　参考文献　　309
第12章　实用工具　　310
12.1　文件压缩　　310
12.1.1　前缀编码　　311
12.1.2　霍夫曼算法　　312
12.1.3　实现　　314
12.2　交叉引用生成器　　325
12.2.1　基本思想　　325
12.2.2　Java实现　　325
12.3　总结　　328
12.4　核心概念　　328
12.5　常见错误　　328
12.6　网络资源　　328
12.7　练习　　329
12.8　参考文献　　331
第13章　模拟　　332
13.1　约瑟夫问题　　332
13.1.1　简单的解决方案　　333
13.1.2　更有效率的算法　　334
13.2　事件驱动模拟　　335
13.2.1　基本思路　　336
13.2.2　示例：电话银行模拟　　336
13.3　总结　　342
13.4　核心概念　　342
13.5　常见错误　　342
13.6　网络资源　　342
13.7　练习　　343
第14章　图和路径　　344
14.1　定义　　344
14.2　无权最短路径问题　　353
14.2.1　理论　　353
14.2.2　Java实现　　355
14.3　正权值最短路径问题　　356
14.3.1　理论：Dijkstra算法　　356
14.3.2　Java实现　　359
14.4　负权值最短路径问题　　360
14.4.1　理论　　360
14.4.2　Java实现　　361
14.5　无环图中的路径问题　　362
14.5.1　拓扑排序　　362
14.5.2　无环最短路径算法的
理论　　364
14.5.3　Java实现　　364
14.5.4　应用：关键路径分析　　366
14.6　总结　　367
14.7　核心概念　　368
14.8　常见错误　　369
14.9　网络资源　　369
14.10　练习　　369
14.11　参考文献　　371
第四部分　实现
第15章　内部类和ArrayList的
实现　　374
15.1　迭代器和嵌套类　　374
15.2　迭代器和内部类　　376
15.3　AbstractCollection类　　378
15.4　StringBuilder　　381
15.5　实现带迭代器的ArrayList　　382
15.6　总结　　386
15.7　核心概念　　386
15.8　常见错误　　386
15.9　网络资源　　386
15.10　练习　　386
第16章　栈和队列　　389
16.1　动态数组实现　　389
16.1.1　栈　　389
16.1.2　队列　　392
16.2　链式实现　　396
16.2.1　栈　　397
16.2.2　队列　　399
16.3　两种方法的比较　　402
16.4　java.util.Stack类　　402
16.5　双端队列　　403
16.6　总结　　403
16.7　核心概念　　404
16.8　常见错误　　404
16.9　网络资源　　404
16.10　练习　　404
第17章　链表　　405
17.1　基本思想　　405
17.1.1　头结点　　406
17.1.2　迭代器类　　407
17.2　Java实现　　408
17.3　双向链表和循环链表　　413
17.4　有序链表　　414
17.5　Collections API LinkedList类的
实现　　415
17.6　总结　　424
17.7　核心概念　　424
17.8　常见错误　　424
17.9　网络资源　　425
17.10　练习　　425
第18章　树　　427
18.1　一般树　　427
18.1.1　定义　　427
18.1.2　实现　　428
18.1.3　应用：文件系统　　429
18.1.4　Java实现　　431
18.2　二叉树　　432
18.3　递归与树　　436
18.4　树的遍历：迭代器类　　438
18.4.1　后序遍历　　441
18.4.2　中序遍历　　444
18.4.3　前序遍历　　445
18.4.4　层序遍历　　446
18.5　总结　　448
18.6　核心概念　　448
18.7　常见错误　　448
18.8　网络资源　　449
18.9　练习　　449
第19章　二叉搜索树　　452
19.1　基本思想　　452
19.1.1　操作　　452
19.1.2　Java实现　　454
19.2　次序统计　　459
19.3　二叉搜索树操作的分析　　462
19.4　AVL树　　465
19.4.1　特性　　465
19.4.2　单旋转　　466
19.4.3　双旋转　　468
19.4.4　AVL插入的总结　　470
19.5　红黑树　　471
19.5.1　自底向上的插入　　471
19.5.2　自顶向下的红黑树　　473
19.5.3　Java实现　　474
19.5.4　自顶向下的删除　　479
19.6　AA树　　481
19.6.1　插入　　482
19.6.2　删除　　484
19.6.3　Java实现　　484
19.7　Collections API TreeSet和
TreeMap类的实现　　487
19.8　B树　　501
19.9　总结　　505
19.10　核心概念　　505
19.11　常见错误　　506
19.12　网络资源　　506
19.13　练习　　506
19.14　参考文献　　509
第20章　散列表　　511
20.1　基本思想　　511
20.2　散列函数　　512
20.3　线性探查　　514
20.3.1　线性探查的简单分析　　515
20.3.2　真正发生了什么：基本
聚集　　516
20.3.3　find操作的分析　　517
20.4　二次探查　　518
20.4.1　Java实现　　521
20.4.2　二次探查的分析　　528
20.5　独立链散列　　528
20.6　散列表对比二叉搜索树　　530
20.7　散列应用　　530
20.8　总结　　531
20.9　核心概念　　531
20.10　常见错误　　531
20.11　网络资源　　531
20.12　练习　　532
20.13　参考文献　　533
第21章　优先队列：二叉堆　　535
21.1　基本思想　　535
21.1.1　结构属性　　536
21.1.2　堆的次序属性　　536
21.1.3　允许的操作　　537
21.2　基本操作的实现　　539
21.2.1　插入　　539
21.2.2　deleteMin操作　　540
21.3　buildHeap操作：线性时间
构造堆　　542
21.4　高级操作：decreaseKey和
merge　　544
21.5　内部排序：堆排序　　545
21.6　外排序　　546
21.6.1　为什么我们需要新的算法　　547
21.6.2　外排序模型　　547
21.6.3　简单算法　　547
21.6.4　多路归并　　548
21.6.5　多相合并　　549
21.6.6　置换选择　　550
21.7　总结　　551
21.8　核心概念　　552
21.9　常见错误　　552
21.10　网络资源　　552
21.11　练习　　552
21.12　参考文献　　555
第五部分　高级数据结构
第22章　伸展树　　558
22.1　自调整和摊销分析　　558
22.1.1　摊销时间界　　559
22.1.2　简单自调整策略—无效　　559
22.2　最简单的自底向上伸展树　　560
22.3　基本的伸展树操作　　562
22.4　自底向上伸展的分析　　562
22.5　自顶向下伸展树　　565
22.6　自顶向下伸展树的实现　　568
22.7　伸展树与其他搜索树的比较　　572
22.8　总结　　572
22.9　核心概念　　572
22.10　常见错误　　572
22.11　网络资源　　573
22.12　练习　　573
22.13　参考文献　　573
第23章　合并优先队列　　575
23.1　斜堆　　575
23.1.1　合并是基础　　575
23.1.2　堆次序树的简单合并　　576
23.1.3　斜堆—简单的修改　　576
23.1.4　斜堆的分析　　577
23.2　配对堆　　578
23.2.1　配对堆操作　　579
23.2.2　配对堆的实现　　580
23.2.3　应用：Dijkstra最短带权路径
算法　　585
23.3　总结　　587
23.4　核心概念　　587
23.5　常见错误　　587
23.6　网络资源　　587
23.7　练习　　587
23.8　参考文献　　588
第24章　不相交集合类　　589
24.1　等价关系　　589
24.2　动态等价及应用　　589
24.2.1　应用：生成迷宫　　590
24.2.2　应用：最小生成树　　592
24.2.3　应用：最近共同祖先问题　　594
24.3　快查算法　　596
24.4　快并算法　　597
24.4.1　聪明的union算法　　598
24.4.2　路径压缩　　600
24.5　Java实现　　600
24.6　按秩合并和路径压缩的最差
情形　　602
24.7　总结　　607
24.8　核心概念　　607
24.9　常见错误　　607
24.10　网络资源　　608
24.11　练习　　608
24.12　参考文献　　609
附录
附录A　运算符　　612
附录B　图形用户界面　　613
附录C　按位运算符　　632