Java程序设计-基础.编程抽象与算法策略

Programming Abstractions in Java
出版者的话
译者序
前言
第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