本书介绍如何使用Java语言编写程序，旨在通过介绍编程过程中遇到的难点和问题来拓宽读者的视野。本书结合具体的示例代码，由浅入深介绍解决编程问题的策略和方法，有助于读者快速入门Java语言编程。同时，每章后面都有配套的复习题和习题，便于读者理论联系实践，通过编程实践查漏补缺，温故而知新。本书适合作为计算机专业的教材，也适合希望学习Java语言的各个层次的读者阅读。

前　言Programming Abstractions in Java致学生在过去的10年中，计算领域的发展激动人心。人们日常随身携带的各种网络设备变得速度更快、价格更便宜、能力更强。利用像Google和Wikipedia这些基于网络的服务，人们滑动指尖就可以获得世界上众多的信息。社交网络将全世界的人联系到了一起。流技术和更快的硬件使得人们可以随时随地下载音乐和视频。
但是，这些技术不会凭空出现，人们需要构建它们。幸运的是，至少对那些研究这个令人激动且变化万千的领域的人来说，具备必需的软件开发技能的人供不应求。这里是硅谷的高科技经济中心，能够将各大公司的技术愿景转化为现实的天资聪慧的工程师十分短缺。各大公司甚至不敢奢求找到更多懂开发和维护大型系统的软件开发人员—他们需要理解诸如数据表示、效率、安全性、正确性和模块化等问题。
尽管本书并不会教给你了解这些主题以及更广阔的计算机科学领域所需的所有知识，但是它会给你一个良好的开端。在斯坦福大学，每年有超过1200名学生选修教授本书内容的课程。其中许多学生的知识背景仅限于本书，但是他们都找到了暑期实习或在业界工作的岗位。更多的学生会继续选修更高级的课程，以便为把握这个快速发展的领域中的无限机会做好准备。
除了为从业提供机会，本书中的主题还充满了智力上的刺激。你在本书中学到的算法和策略，有些是在过去10年中发明的，而有些则已经有超过2000年的历史了。它们难以置信地灵巧，就像是一座座矗立着的人类创造力的丰碑。它们还非常实用，可以帮助你变成经验丰富的程序员。
在阅读本书时，请记住，编程永远都是实践出真知。读过有关某种算法技术的内容并不表示你就能够将其应用到实践中，真正的学习是在完成练习和调试为了解决这些问题而编写的程序时才开始的。尽管编程时不时会让你感到挫败，但是在发现最后一个bug并看到程序可以工作时的激动心情是无与伦比的，它让你可以将一路走来碰到的所有困难都抛之脑后。
致教师本书旨在作为一般大学或学院的第二门编程课程的教材。它涵盖了传统的CS2课程的内容，CS2是在美国计算机学会（ACM）制定的Curriculum?8中定义的课程。因此，它包含了ACM/IEEE-CS联合计算课程设置2001（Joint ACM/IEEE-CS Computing Curricula 2001）定义的CS102O和CS103O课程中规定的大部分主题，以及计算机科学课程设置2013（Computer Science Curricula 2013）中有关基础数据结构和算法部分的内容。
乍一看，本书中这些主题出现的顺序似乎很常规。典型情况下，传统的CS2课程大纲会对基础数据结构逐一按照顺序介绍。在这种模式中，学生会学习如何使用特定的数据结构，如何实现它，以及它的性能特性等，所有知识点会同时学习。这种方式的主要缺点是学生需要在掌握如何使用某种结构之前，就先理解它是如何实现的。例如，如果学生一开始不知道为什么某个应用要使用映射表，那么就很难让他们理解为什么可以优选某种实现模型而不是另一种实现模型。
在斯坦福大学，我们采用了一种不同的策略—客户优先方式。学生在被要求思考任何实现问题之前，会先学习如何使用集合类的全集。他们还有机会去完成有趣的作业，在这些作业中他们会作为客户来使用这些集合类。在这个过程中，学生会对底层的数据模型和每种结构的用法获得更深刻的理解。一旦学生了解了客户端的视角，那么他们就已经准备好了去探索各种可能的实现及其对应的计算特性了。
客户优先方式被证明非常成功。在我们将这种改变引入CS2课程中之后，在所有教师教授的班级中，期中考试成绩的中位值提升了大约15%，而期末考试的成绩则提升了超过5%。课程等级和学生满意度都随着学生对课程内容理解程度的提高而不断增长。现在，我们每年向超过1200名学生教授CS2，我们相信客户优先方式是产生这种变化的关键。
我撰写本书是为了让许多用Java来教授CS2课程的学校一起分享斯坦福大学的成功经验。我们自信地认为，你将会和我们一样，对于学生对知识的理解和运用程度的提升而感到惊讶。
补充材料为学生提供的材料本书的所有读者都可以在Pearson的网站（http://www.pearsonhighered.com/ericroberts）上获得下面各项材料：
书中每个示例程序的源代码。
样例运行的彩色PDF版本。
复习题的答案。
为教师提供的材料所有具有资质的教师都可以在Pearson的网站（http://www.pearsonhighered.com/ericroberts）上获得下面各项材料：
书中每个示例程序的源代码。
样例运行的彩色PDF版本。
复习题的答案。
编程习题的解决方案。
每一章的PowerPoint讲座幻灯片。
致谢感谢斯坦福大学的同事，首先是Julie Zelenski，感谢她开创性地开发了客户优先方式。我的同事Keith Schwarz、Marty Stepp、Stephen Cooper、Cynthia Lee、Jerry Cain、Chris Piech和Mehran Sahami都在教学策略和支撑材料这两方面做出了宝贵的贡献。还要向数任本科生部的领导和多年来的许多学生表达谢意，他们鼎力相助使教授这门课变得如此令人兴奋。
此外，向Pearson出版社的Marcia Horton、Tracy Johnson和其他成员表示感谢，感谢他们数年来对本书及各个前期版本的支持。
一如既往，最诚挚的谢意要献给我的妻子Lauren Rusk，她再次作为我的开发编辑完成了魔幻般的工作。Lauren运用她的专业知识对本书的文字进行了仔细的打磨，如果没有她，就压根不会有本书。
Eric S. Roberts斯坦福大学

埃里克·S·罗伯茨（Eric S. Roberts） 的计算机科学教育领导者，美国斯坦福大学计算机科学系教授。由于其对计算机科学教育改革的杰出贡献和成就，曾获得多项奖励，包括 2012年 ACM Karl V. Karlstrom 杰出教育家奖，2012年IEEE CS Taylor L. Booth 教育奖，并于2007年被选为ACM Fellow。他曾编写了几本的计算机程序设计教材，包括《C语言的科学与艺术》、《JAVA语言的科学与艺术》、《c程序设计的抽象思维》等。他是ACM Education Council共同主席， ACM Education Board前任共同主席，SIGCSE Board前委员。他于1980年获得哈佛大学应用数学博士学位。

目　录
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