本書介紹如何使用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%。課程等級和學生滿意度都隨著學生對課程內容理解程度的提高而不斷增長�，F在，我們每年向超過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
新書資訊