第1章 Java简介 2
1.1 通用环境 2
第一部分 Java教程 2
1.2 第一个程序 3
1.3 基本数据类型 4
1.4 基本运算符 5
1.5 条件语句 7
1.6 方法 11
1.8 名词解释 13
1.7 小结 13
1.9 常见错误 14
1.10 网上资源 14
习题 15
参考文献 16
第2章 引用类型 17
2.1 什么是引用 17
2.2 对象和引用的基本概念 18
2.3 字符串 21
2.4 数组 23
2.5 异常处理 30
2.6 输入和输出 32
2.7 小结 35
2.8 名词解释 37
2.9 常见错误 38
2.10 网上资源 38
习题 38
参考文献 39
3.1 何为面向对象编程 40
第3章 对象与类 40
3.2 一个简单的例子 41
3.3 JavaDOC 42
3.4 基本方法 43
3.5 附加结构 46
3.6 包 49
3.7 设计模式：复合 52
3.8 小结 52
3.9 名词解释 53
3.10 常见错误 54
3.11 网上资源 55
习题 55
参考文献 57
第4章 继承 58
4.1 什么是继承 58
4.2 层次结构设计 68
4.3 多重继承 71
4.4 接口 72
4.5 Java中的基础继承体系 74
4.6 通用实现组件 77
4.7 函数（函数对象） 82
4.8 动态绑定细节 87
4.9 小结 89
4.10 名词解释 90
4.11 常见错误 91
4.12 网上资源 91
习题 92
参考文献 95
5.1 什么是算法分析 98
第二部分 算法与程序构建 98
第5章 算法分析 98
5.2 算法运行时间举例 100
5.3 最大连续子序列之和的问题 101
5.4 通用Big-Oh规则 106
5.5 对数 108
5.6 静态搜索问题 109
5.7 检验算法分析 112
5.10 名词解释 113
5.9 小结 113
5.8 Big-Oh分析法的限制 113
5.11 常见错误 114
5.12 网上资源 114
习题 114
参考文献 118
第6章 应用程序接口集 119
6.1 简介 119
6.2 迭代器模式 120
6.3 应用程序接口集：容器和迭代器 123
6.4 通用算法 127
6.5 表接口 131
6.6 栈和队列 134
6.7 集合 137
6.8 映射 142
6.9 优先级队列 145
6.10 小结 148
6.11 名词解释 148
6.13 网上资源 149
6.12 常见错误 149
习题 150
参考文献 151
第7章 递归 152
7.1 什么是递归 152
7.2 背景：通过数学归纳法证明 153
7.3 基本递归 154
7.4 数值应用 163
7.5 分而治之算法 168
7.6 动态规划 174
7.7 回溯 177
7.8 小结 180
7.9 名词解释 181
7.10 常见错误 181
7.11 网上资源 181
习题 182
参考文献 184
8.1 排序算法为什么重要 185
第8章 排序算法 185
8.2 基础知识 186
8.3 插入排序算法和其他简单排序算法的分析 186
8.4 希尔排序 188
8.5 归并排序 190
8.6 快速排序 192
8.7 快速选择 202
8.8 排序的下限 203
8.10 名词解释 204
8.11 常见错误 204
8.9 小结 204
8.12 网上资源 205
习题 205
参考文献 208
第9章 随机化处理 209
9.1 为什么需要随机数字 209
9.2 随机数字发生器 209
9.3 非均匀分布的随机数字 213
9.4 产生随机排序 214
9.5 随机化算法 215
9.6 随机化初试 217
9.7 小结 219
9.8 名词解释 219
9.9 常见错误 220
9.10 网上资源 220
习题 220
参考文献 221
10.1 迷宫索字游戏 224
第10章 趣味游戏 224
第三部分 应用 224
10.2 Tic-Tac-Toe游戏 230
10.3 小结 236
10.4 名词解释 236
10.5 常见错误 236
10.6 网上资源 236
习题 236
参考文献 238
11.1 平衡符校验器 239
第11章 栈和编译程序 239
11.2 一个简单的计算器 248
11.3 小结 258
11.4 名词解释 258
11.5 常见错误 259
11.6 网上资源 259
习题 259
参考文献 260
第12章 公用程序 261
12.1 文件压缩 261
12.2 交叉引用发生器 276
12.3 小结 279
12.4 名词解释 279
12.5 常见错误 280
12.6 网上资源 280
习题 280
参考文献 282
第13章 仿真 283
13.1 Josephus问题 283
13.2 事件驱动仿真 286
13.3 小结 292
13.4 名词解释 293
13.5 常见错误 293
13.6 网上资源 293
习题 293
第14章 图形和路径 295
14.1 定义 295
14.2 无权值最短路径问题 304
14.3 正权值最短路径问题 307
14.4 负权值最短路径问题 311
14.5 无环图中的路径问题 313
14.6 小结 318
14.7 名词解释 318
14.8 常见错误 319
14.9 网上资源 319
习题 319
参考文献 321
第15章 内部类和数组表的实现 324
15.1 迭代和嵌套类 324
第四部分 实现 324
15.2 迭代类和内部类 326
15.3 抽象集（AbstractCollection）类 328
15.4 有迭代类的ArrayList的实现 330
15.5 小结 334
15.6 名词解释 334
15.7 常见错误 335
15.8 网络资源 335
习题 335
16.1 动态数组的实现 337
第16章 堆栈和队列 337
16.2 链表的实现 345
16.3 两种方法的对比 350
16.4 java.util.Stack类 350
16.5 双端队列 351
16.6 小结 352
16.7 名词解释 352
16.8 常见错误 352
16.9 网上资源 352
习题 353
第17章 链表 354
17.1 基本概念 354
17.2 Java实现 357
17.3 双向链表和循环链表 361
17.4 排序链表 363
17.5 API类库集中的LinkedList类的实现 364
17.9 网上资源 373
17.8 常见错误 373
17.7 名词解释 373
17.6 小结 373
习题 374
第18章 树 376
18.1 通用树 376
18.2 二叉树 381
18.3 递归和树 385
18.4 树的遍历：iterator类 387
18.6 名词解释 396
18.5 小结 396
18.7 常见错误 397
18.8 网上资源 397
习题 397
第19章 二叉查找树 400
19.1 基本思想 400
19.2 静态顺序 407
19.3 二叉查找树的操作分析 410
19.4 AVL树 412
19.5 红-黑树 418
19.6 AA-树 427
19.7 API类库中的集TreeSet和TreeMap类的实现 434
19.8 B-树 446
19.9 小结 449
19.10 名词解释 450
19.11 常见错误 451
19.12 网上资源 451
习题 451
参考文献 453
第20章 哈希表 455
20.1 基本思想 455
20.2 哈希函数 456
20.3 线性探测 457
20.4 二次探测 460
20.5 单链哈希法 470
20.6 哈希表与二叉查找树 470
20.8 小结 471
20.9 名词解释 471
20.7 哈希法的应用 471
20.10 常见错误 472
20.11 网上资源 472
习题 472
参考文献 474
第21章 优先队列：二分堆 475
21.1 基本思想 475
21.2 基本操作的实现 479
21.3 buildHeap操作：线性时间堆结构 482
21.4 高级操作：decreaseKey和merge 484
21.5 内部排序：堆排序 485
21.6 外部排序 487
21.7 小结 491
21.8 名词解释 491
21.9 常见错误 492
21.10 网上资源 492
习题 492
参考文献 494
第22章 splay树 498
22.1 自动调整和分步偿付 498
第五部分 高级数据结构 498
22.2 基本的自下而上的splay树 500
22.3 基本的splay树操作 501
22.4 自底而上的splay树的分析 502
22.5 自顶而下的splay树的分析 505
22.6 自顶而下splay树的实现 508
22.9 名词解释 512
22.11 网上资源 512
22.10 常见错误 512
22.8 小结 512
22.7 splay树和其他查找树的比较 512
习题 513
参考文献 513
第23章 归并优先级队列 515
23.1 非对称堆 515
23.2 对称堆 518
23.3 小结 526
习题 527
23.6 网上资源 527
23.5 常见错误 527
23.4 名词解释 527
参考文献 528
第24章 不相交集合类 529
24.1 等价关系 529
24.2 动态等价及应用 529
24.3 快速查找算法 536
24.4 快速合并算法 536
24.5 Java实现 539
24.6 根据层合并和路径压缩的最差情况 541
24.7 小结 545
24.8 名词解释 546
24.9 常见错误 546
24.10 网上资源 546
习题 546
参考文献 548
附录A 运算符 550
附录B 图形用户界面 551
附录C 位运算符 569