第1章 Java概览 1
1.1 你的第一个Java程序 1
1.2 Java的历史 2
1.2.1 编程语言 2
1.2.2 面向对象范型 3
1.2.3 Java编程语言 4
1.2.4 Java的演化 4
1.3 Java程序的结构 5
1.3.1 注释 6
1.3.2 包声明 6
1.3.3 导入语句 7
1.3.4 类定义 7
1.3.5 run方法 8
1.4 变量 11
1.4.1 变量声明 11
1.4.2 命名惯例 11
1.5 常量 12
1.6 数据类型 13
1.6.1 数据类型的概念 13
1.6.2 整数类型 14
1.6.3 浮点类型 14
1.6.4 布尔类型 15
1.6.5 字符 15
1.6.6 字符串 16
1.6.7 复合类型 16
1.7 表达式 16
1.7.1 优先级与结合性 17
1.7.2 表达式中的混用类型 18
1.7.3 整数除法和取余操作符 18
1.7.4 类型强制转换 19
1.7.5 赋值操作符 20
1.7.6 递增和递减操作符 21
1.7.7 布尔操作符 22
1.8 语句 24
1.8.1 简单语句 24
1.8.2 块 24
1.8.3 if语句 24
1.8.4 switch语句 25
1.8.5 while语句 26
1.8.6 for语句 29
1.9 类、对象和方法 31
1.10 总结 33
1.11 复习题 34
1.12 习题 35
第2章 方法 39
2.1 Java中的方法 39
2.1.1 Java方法的语法结构 40
2.1.2 静态方法 41
2.1.3 重载 42
2.2 方法和程序结构 43
2.3 方法调用的机制 44
2.3.1 调用方法的步骤 44
2.3.2 组合函数 45
2.3.3 跟踪组合函数 47
2.4 简单的递归函数 50
2.4.1 fact的递归方案 51
2.4.2 追踪递归过程 51
2.4.3 递归的信任飞跃 54
2.5 斐波那契函数 55
2.5.1 计算斐波那契数列中的项 55
2.5.2 在递归实现中收获自信 57
2.5.3 递归实现的效率 57
2.5.4 递归不应被指责 58
2.6 总结 60
2.7 复习题 60
2.8 习题 61
第3章 字符串 67
3.1 将字符串用作抽象值 67
3.2 字符串操作 68
3.2.1 在字符串中选择字符 70
3.2.2 抽取字符串的各个部分 70
3.2.3 字符串比较 71
3.2.4 在字符串内搜索 72
3.2.5 遍历字符串中的字符 72
3.2.6 通过连接来扩展字符串 73
3.2.7 使用递归操作字符串 74
3.2.8 对字符分类 74
3.3 编写字符串应用程序 75
3.3.1 识别回文 76
3.3.2 将英文翻译为隐语 77
3.4 总结 79
3.5 复习题 80
3.6 习题 81
第4章 文件 86
4.1 文本文件 86
4.2 读取文本文件 87
4.2.1 创建文件读取器 87
4.2.2 异常处理 88
4.2.3 逐个字符地读取文件 90
4.2.4 逐行地读取文件 92
4.3 编写文本文件 93
4.3.1 打开用于输出的文件 93
4.3.2 将输出写入文件中 93
4.4 格式化输出 95
4.5 格式化输入 100
4.6 使用文件对话框 102
4.7 总结 105
4.8 复习题 105
4.9 习题 106
第5章 数组 109
5.1 数组简介 109
5.1.1 数组声明 109
5.1.2 数组选择 110
5.2 数据表示和内存 112
5.2.1 位、字节和字 112
5.2.2 二进制和十六进制表示 113
5.2.3 表示其他数据类型 115
5.2.4 数组的表示 115
5.3 使用数组来制表 117
5.4 数组初始化 118
5.5 多维数组 119
5.6 可变长参数列表 120
5.7 总结 120
5.8 复习题 121
5.9 习题 122
第6章 集合 128
6.1 ArrayList类 128
6.1.1 指定ArrayList的元素类型 129
6.1.2 声明ArrayList对象 129
6.1.3 ArrayList的操作 129
6.1.4 ArrayList类的一个简单应用 130
6.2 包装器类 131
6.2.1 从基本类型创建对象 132
6.2.2 自动装箱 132
6.2.3 包装器类中的静态方法 133
6.3 栈抽象 134
6.3.1 Stack类的结构 135
6.3.2 栈和袖珍计算器 135
6.4 队列抽象 138
6.4.1 队列应用 140
6.4.2 仿真与模型 140
6.4.3 排队模型 140
6.4.4 离散时间 141
6.4.5 仿真时间中的事件 141
6.4.6 实现仿真 142
6.4.7 随机数 144
6.5 映射表抽象 145
6.5.1 Map接口的结构 145
6.5.2 在应用中使用映射表 147
6.6 集抽象 149
6.7 遍历集合 151
6.7.1 使用迭代器 151
6.7.2 迭代顺序 151
6.7.3 计算词频 152
6.8 总结 154
6.9 复习题 155
6.10 习题 156
第7章 类和对象 161
7.1 类和面向对象设计 161
7.2 定义一个简单的Point类 161
7.2.1 将点定义为一种记录类型 162
7.2.2 在Point类中包含方法 163
7.2.3 javadoc注释 165
7.2.4 让实例变量保持私有 166
7.3 有理数 168
7.3.1 定义新类的策略 169
7.3.2 站在客户的视角 169
7.3.3 指定Rational类的私有状态 170
7.3.4 定义Rational类的构造器 170
7.3.5 为Rational类定义方法 171
7.3.6 实现Rational类 172
7.4 设计一个符号扫描器类 175
7.4.1 客户希望从符号扫描器中得到什么 175
7.4.2 TokenScanner类 176
7.5 将对象链接起来 180
7.5.1 刚铎的烽火 180
7.5.2 在链表中迭代 183
7.6 枚举类型 183
7.7 单元测试 185
7.8 总结 189
7.9 复习题 190
7.10 习题 190
第8章 继承 197
8.1 继承的简单示例 197
8.1.1 指定参数化类中的类型 197
8.1.2 调用继承方法的规则 198
8.1.3 调用继承构造器的规则 200
8.1.4 控制对类内容的访问 200
8.1.5 继承之外的选择 201
8.2 定义Employee类 203
8.3 Java图形类概览 206
8.3.1 在屏幕上放置一个窗口 207
8.3.2 向窗口中添加图形 208
8.4 一种图形对象的层次结构 210
8.4.1 创建一个面向对象的图形包 211
8.4.2 实现GWindow和GCanvas类 216
8.4.3 演示GObject类 219
8.4.4 创建简单的动画 220
8.5 定义一个控制台界面 222
8.6 总结 227
8.7 复习题 228
8.8 习题 228
第9章 递归策略 233
9.1 递归地思考 233
9.1.1 一个分而治之算法的简单示例 233
9.1.2 保持大局观 235
9.1.3 避免常见的陷阱 235
9.2 汉诺塔 236
9.2.1 刻画汉诺塔问题 237
9.2.2 找到递归策略 238
9.2.3 验证递归策略 240
9.2.4 编码解决方案 240
9.2.5 跟踪递归过程 241
9.3 子集求和问题 245
9.3.1 探寻递归解决方案 245
9.3.2 包含／排除模式 246
9.4 生成排列 246
9.5 图形递归 249
9.5.1 一个计算机艺术实例 249
9.5.2 分形 252
9.6 总结 256
9.7 复习题 256
9.8 习题 256
第10章 回溯算法 267
10.1 迷宫中的递归回溯 267
10.1.1 右手规则 267
10.1.2 寻找递归方式 268
10.1.3 识别简单情况 269
10.1.4 编码迷宫解决算法 270
10.1.5 说服自己解决方案有效 271
10.2 回溯与游戏 273
10.2.1 Nim游戏 274
10.2.2 对弈游戏的通用程序 277
10.3 最小最大值算法 279
10.3.1 博弈树 279
10.3.2 对位置和奕法做评估 279
10.3.3 限制递归搜索的深度 281
10.3.4 实现最小最大值算法 282
10.4 总结 283
10.5 复习题 284
10.6 习题 285
第11章 算法分析 294
11.1 排序问题 294
11.1.1 选择排序算法 294
11.1.2 性能的经验度量 295
11.1.3 分析选择排序的性能 296
11.2 计算复杂度 297
11.2.1 大O标记法 298
11.2.2 大O的标准简化 298
11.2.3 选择排序的计算复杂度 298
11.2.4 从代码中降低计算复杂度 299
11.2.5 最坏情况复杂度与平均情况复杂度 300
11.2.6 大O的形式化定义 301
11.3 递归的救赎 302
11.3.1 分而治之策略的威力 302
11.3.2 合并两个数组 303
11.3.3 合并排序算法 304
11.3.4 合并排序的计算复杂度 304
11.3.5 比较N2与N log N的性能 306
11.4 标准的复杂度分类 307
11.5 快速排序算法 309
11.5.1 划分数组 310
11.5.2 分析快速排序的性能 311
11.6 数学归纳 313
11.7 总结 315
11.8 复习题 316
11.9 习题 317
第12章 效率与表示方式 323
12.1 用于文本编辑的软件模式 323
12.2 设计一个简单的文本编辑器 324
12.2.1 编辑器命令 324
12.2.2 考虑底层的表示方式 325
12.2.3 对编辑器应用编码 327
12.3 基于数组的实现 328
12.3.1 定义私有数据结构 329
12.3.2 实现缓冲的操作 329
12.3.3 基于数组的编辑器的计算复杂度 332
12.4 基于栈的实现 333
12.4.1 定义私有数据结构 333
12.4.2 实现缓冲的操作 333
12.4.3 比较计算复杂度 335
12.5 基于表的实现 336
12.5.1 链表缓冲中的插入操作 338
12.5.2 链表缓冲中的删除操作 340
12.5.3 链表表示方式中的光标移动 341
12.5.4 完成缓冲的实现 343
12.5.5 链表缓冲区的计算复杂度 345
12.5.6 双向链表 345
12.5.7 时空权衡 346
12.6 总结 346
12.7 复习题 347
12.8 习题 347
第13章 线性结构 351
13.1 泛型 351
13.1.1 Java中泛型的实现 351
13.1.2 泛型的限制 353
13.1.3 GenericArray类 354
13.2 实现栈 355
13.2.1 用数组结构实现栈 355
13.2.2 用链表实现栈 357
13.3 实现队列 361
13.3.1 用数组实现队列 362
13.3.2 用链表实现队列 366
13.4 实现列表 369
13.5 翻倍策略的分析 372
13.6 总结 373
13.7 复习题 374
13.8 习题 374
第14章 映射表 377
14.1 用数组实现映射表 378
14.2 在表中查找 379
14.3 散列 382
14.3.1 设计数据结构 382
14.3.2 理解字符串的散列函数 384
14.3.3 跟踪散列表的实现 385
14.3.4 调整桶元数量 386
14.3.5 实现你自己的散列函数 388
14.4 实现HashMap类 389
14.5 总结 392
14.6 复习题 393
14.7 习题 393
第15章 树 396
15.1 家族树 396
15.1.1 用于描述树的术语 397
15.1.2 树的递归属性 397
15.1.3 用Java表示家族树 397
15.2 二叉搜索树 398
15.2.1 二叉搜索树幕后的动机 399
15.2.2 在二叉搜索树中查找结点 400
15.2.3 在二叉搜索树中插入新结点 401
15.2.4 移除结点 404
15.2.5 树的遍历 405
15.3 平衡树 406
15.3.1 树的平衡策略 408
15.3.2 可视化AVL算法 408
15.3.3 单旋转 410
15.3.4 双旋转 411
15.3.5 实现AVL算法 412
15.4 用二叉搜索树实现映射表 414
15.5 偏序树 417
15.6 总结 419
15.7 复习题 420
15.8 习题 422
第16章 集 428
16.1 作为数学抽象的集 428
16.1.1 隶属关系 428
16.1.2 集的操作 429
16.1.3 集的恒等式 430
16.2 集的实现策略 431
16.3 扩展集的模型 432
16.4 优化由小整数构成的集 435
16.4.1 特征向量 435
16.4.2 由位构成的压缩数组 436
16.4.3 位操作 437
16.4.4 实现特征向量 438
16.4.5 定义CharSet类 439
16.5 总结 443
16.6 复习题 443
16.7 习题 444
第17章 图 447
17.1 图的结构 447
17.1.1 有向图和无向图 448
17.1.2 路径和环 449
17.1.3 连通性 449
17.2 表示策略 450
17.2.1 使用邻接表表示连接 450
17.2.2 使用邻接矩阵表示连接 451
17.2.3 使用弧集表示连接 452
17.3 基于集的图抽象 452
17.4 图的遍历 458
17.4.1 深度优先搜索 458
17.4.2 广度优先搜索 461
17.5 查找最小代价路径 463
17.6 泛化Graph类 467
17.6.1 在图抽象中使用参数化类型 468
17.6.2 添加额外的操作 469
17.7 搜索Web的算法 469
17.7.1 Google的PageRank算法 470
17.7.2 PageRank计算的一个微型实例 470
17.8 总结 472
17.9 复习题 473
17.10 习题 474
第18章 表达式树 481
18.1 解释器概览 481
18.2 表达式的结构 483
18.2.1 表达式的递归定义 483
18.2.2 二义性 484
18.2.3 表达式树 485
18.2.4 实现Expression的子类 488
18.2.5 对表达式绘图 491
18.2.6 跟踪计算过程 492
18.3 解析表达式 495
18.3.1 解析和语法 495
18.3.2 考虑优先级 496
18.3.3 递归下推解析器 496
18.4 总结 501
18.5 复习题 502
18.6 习题 502
第19章 将函数作为数据使用 507
19.1 交互式程序 507
19.1.1 Java事件模型 507
19.1.2 事件驱动的简单应用 508
19.1.3 匿名内部类 511
19.2 命令分派表 512
19.2.1 使用层叠if语句的命令分派 513
19.2.2 使用命令表的命令分派 514
19.2.3 用lambda表达式实现命令分派 516
19.3 lambda表达式 516
19.3.1 Java中lambda表达式的语法 516
19.3.2 函数式接口 517
19.3.3 一个lambda函数的简单应用 518
19.4 绘制函数 519
19.5 映射函数 520
19.6 总结 522
19.7 复习题 523
19.8 习题 523
索引 529