Java程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)（第2版國外計算機科學(xué)經(jīng)典教材）

第1章 概述
1.1 集合
1.1.1 集合的分類
1.1.2 關(guān)于集合的操作
1.2 抽象數(shù)據(jù)類型
1.3 算法分析
1.3.1 簡單性和清晰度
1.3.2 空間效率
1.3.3 時間效率
1.4 算法類型
1.4.1 貪婪算法
1.4.2 分治算法
1.4.3 回溯算法
1.5 軟件開發(fā)過程
1.5.1 復(fù)雜性
1.5.2 脆弱性
1.5.3 可擴展性
1.5.4 互連性
1.6 面向?qū)ο蟪绦蛟O(shè)計簡介
1.6.1 過程式程序設(shè)計
1.6.2 函數(shù)式程序設(shè)計
1.6.3 面向?qū)ο蟪绦蛟O(shè)計(00P)
1.6.4 面向?qū)ο蟪绦蛟O(shè)計的直觀概括
1.7 軟件開發(fā)生命周期
1.8 本書的軟件開發(fā)方法
1.8.1 需求
1.8.2 分析
1.8.3 設(shè)計
1.8.4 實現(xiàn)
1.9 分析和設(shè)計階段的測試
1.10 測試代碼
1.10.1 單元、集成和驗收測試
1.10.2 測試內(nèi)容
1.10.3 如何設(shè)計測試數(shù)據(jù)
1.11 正確性的證明
1.12 軟件開發(fā)過程的其他方面
1.12.1 編碼約定
1.12.2 前置條件和后置條件
1.13 層次系統(tǒng)的開發(fā)
第2章 面向?qū)ο蟪绦蛟O(shè)計和基本的輸入輸出功能
2.1 簡介
2.2 類和對象
2.2.1 示例：字符串對象
2.2.2 示例：終端輸出
2.2.3 對象、類和計算機內(nèi)存
2.2.4 對象的3個特征
2.2.5 客戶端和服務(wù)器
2.3 Employee類
2.3.1 用戶需求
2.3.2 類模板的結(jié)構(gòu)
2.3.3 Employee類的設(shè)計和實現(xiàn)
2.3.4 構(gòu)造函數(shù)和異常
2.3.5 this的使用
2.3.6 取值方法、賦值方法和toString方法
2.3.7 測試等同性
2.3.8 比較及接口Comparable.
2.3.9 復(fù)制對象及接口Cloneable
2.3.10 對象序列化
2.3.11 finalize和dispose方法
2.3.12 使用對象時一些有用的提示
2.4 繼承和多態(tài)
2.5 實現(xiàn)一個簡單的圖形層次結(jié)構(gòu)
2.5.1 實現(xiàn)Shape類
2.5.2 實現(xiàn)Circle類
2.5.3 構(gòu)造函數(shù)和super保留字
2.5.4 其他方法和super保留字
2.5.5 實現(xiàn)Rectangle類
2.5.6 保護(hù)型(protected)變量和方法
2.5.7 實現(xiàn)、擴展、重寫和終結(jié)
2.6 圖形類的使用
2.6.1 查找合適的方法
2.6.2 圖形數(shù)組
2.7 將圖形作為參數(shù)和返回值
2.7.1 示例：輸入Retangle，輸出Circle
2.7.2 示例：輸入任意圖形，輸出Circle
2.7.3 示例：輸入任意圖形，輸出任意圖形
2.8 面向?qū)ο笙到y(tǒng)的分解
2.8.1 確定類
2.8.2 分配職責(zé)
2.8.3 確定數(shù)據(jù)屬性
2.8.4 確定方法
2.8.5 類和對象模型之間的關(guān)系
2.9 基于字符的流輸入、輸出
2.9.1 介紹鍵盤讀取器
2.9.2 擴展鍵盤讀取器
2.9.3 文件讀取器
2.9.4 格式化輸出
2.9.5 使用支持類
第3章 基于GUI的Java應(yīng)用程序
3.1 模型、視圖、控制器模式
3.2 溫度轉(zhuǎn)換程序的代碼
3.2.1 模型
3.2.2 視圖
3.2.3 控制器
3.2.4 視圖和控制器的完整代碼
3.3 GridBagLayout類
3.4 EasyGridLayout類
3.5 IntegerField類和DoubleField類
3.6 彈出式消息
3.7 其他窗口組件
3.7.1 菜單和文本區(qū)
3.7.2 復(fù)選框和單選按鈕
3.7.3 列表框
3.8 模式對話框的使用
3.9 多窗口應(yīng)用程序
3.10 偵聽器共享
3.11 方法一覽表
第4章 復(fù)雜度
4.1 衡量算法的效率
4.1.1 測量算法的執(zhí)行時間
4.1.2 對指令計數(shù)
4.1.3 用代數(shù)方法推導(dǎo)增長率
4.1.4 測量算法使用的內(nèi)存
4.2 比較增長率
4.2.1 使用代數(shù)方法比較增長率
4.2.2 大O表示法
4.2.3 最佳、最差和平均性能
4.3 查找算法
4.3.1 數(shù)組的線性查找法
4.3.2 數(shù)組的二分查找法
4.4 排序算法
4.4.1 選擇排序
4.4.2 冒泡排序
4.4.3 插入排序
4.5 案例分析：記錄運行時間 以及對指令計數(shù)
4.5.1 要求
4.5.2 分析
4.5.3 Algorithms類的設(shè)計
4.5.4 Algorithms類的實現(xiàn)
4.5.5 AlgorithmProfiler類的 設(shè)計和實現(xiàn)
第5章 數(shù)組和鏈表
5.1 數(shù)組的特性
5.1.1 隨機訪問和連續(xù)地址內(nèi)存
5.1.2 靜態(tài)內(nèi)存和動態(tài)內(nèi)存
5.1.3 物理大小和邏輯大小
5.2 數(shù)組操作
5.2.1 增加數(shù)組的大小
5.2.2 減小數(shù)組大小
5.2.3 向數(shù)組中插入數(shù)據(jù)項
5.2.4 從數(shù)組中移除數(shù)據(jù)項
5.2.5 數(shù)組方法的測試程序
5.2.6 復(fù)雜度的權(quán)衡：查找和 修改數(shù)組
5.3 鏈表
5.3.1 單鏈表和雙向鏈表
5.3.2 不連續(xù)地址內(nèi)存和節(jié)點
5.3.3 定義單鏈節(jié)點類
5.3.4 使用單鏈節(jié)點類
5.4 單鏈表的操作
5.4.1 遍歷
5.4.2 查找(對象或第i項)
5.4.3 替換(對象或第i項)
5.4.4 在首端插入
5.4.5 在尾端插入
5.4.6 在首端移除
5.4.7 在尾端移除
5.4.8 插入(對象或第i項)
5.4.9 移除(對象或第i項)
5.4.10 復(fù)雜度的權(quán)衡：時間、 空間和單鏈表
5.5 鏈表的各種變體
5.5.1 帶有虛頭節(jié)點的循環(huán)鏈表
5.5.2 雙向鏈表
第6章 集合概述
6.1 簡介
6.1.1 本書中集合的概述
6.1.2 Tiny集合
6.2 多種實現(xiàn)
6.3 集合和強制類型轉(zhuǎn)換
6.4 集合和串行化
6.5 迭代器
6.5.1 迭代器的使用
6.5.2 實現(xiàn)Tiny和iterator方法
6.6 集合和集合視圖
6.6.1 兩個例子
6.6.2 Collection接口中的方法
6.6.3 ColleetionView方法的 實現(xiàn)(可選內(nèi)容)
6.6.4 AbstractCollection 實現(xiàn)(可選內(nèi)容)
6.7 集合的原型和專門版本
6.7.1 Tiny專門版本的概述 (可選內(nèi)容)
6.7.2 Tiny接口的擴展(可選內(nèi)容)
6.7.3 將Tiny方法分配給類 (可選內(nèi)容)
6.7.4 編寫代碼的細(xì)節(jié)(可選內(nèi)容)
6.8 本章向?qū)?br />第7章 棧
7.1 棧概述
7.2 棧原型
7.3 棧的使用
7.4 棧原型的實現(xiàn)
7.4.1 數(shù)組實現(xiàn)
7.4.2 鏈表實現(xiàn)
7.4.3 兩個實現(xiàn)的時間和空間分析
7.5 棧的3個應(yīng)用
7.5.1 算術(shù)表達(dá)式求值
7.5.2 回溯算法
7.5.3 內(nèi)存管理
7.6 專門版本的接口
7.7 專門版本的實現(xiàn)
7.8 案例分析：后綴表達(dá)式求值
7.8.1 要求
7.8.2 分析
7.8.3 設(shè)計
7.8.4 實現(xiàn)
第8章 隊列
8.1 隊列概述
8.2 隊列的原型
8.3 隊列原型的實現(xiàn)
8.3.1 鏈表實現(xiàn)
8.3.2 數(shù)組實現(xiàn)
8.3.3 兩種實現(xiàn)的時間和空間分析
8.4 隊列的兩個應(yīng)用
8.4.1 模擬
8.4.2 CPU循環(huán)調(diào)度
8.5 專門版本的接口
8.6 專門版本的實現(xiàn)
8.7 案例分析1：模擬超市結(jié)賬流程
8.7.1 要求
8.7.2 分析
8.7.3 總體設(shè)計
8.7.4 MarketModel類的設(shè)計
8.7.5 MarkotModel類的實現(xiàn)
8.7.6 Cashier類的設(shè)計
8.7.7 Cashier類的實現(xiàn)
8.7.8 Customer類的設(shè)計
8.7.9 Customer類的實現(xiàn)
8.8 優(yōu)先隊列
8.9 案例分析2：急診室調(diào)度
8.9.1 要求
8.9.2 分析
8.9.3 推薦界面
第9章 列表
9.1 列表概述
9.2 列表原型
9.3 列表的使用
9.4 列表原型的實現(xiàn)
9.4.1 靜態(tài)數(shù)組實現(xiàn)
9.4.2 雙向鏈表實現(xiàn)
9.4.3 兩種實現(xiàn)的時間和空間分析
9.5 列表的3個應(yīng)用
9.5.1 堆存儲管理
9.5.2 對磁盤文件的組織
9.5.3 其他ADT實現(xiàn)
9.6 專門版本的接口
9.7 專門版本的實現(xiàn)
9.8 案例分析：維護(hù)任務(wù)列表(to-do列表)
9.8.1 要求
9.8.2 分析
9.8.3 設(shè)計
9.8.4 實現(xiàn)
第10章 遞歸、查找、排序和回溯
10.1 遞歸概述
10.1 實現(xiàn)遞歸
10.1.2 跟蹤遞歸調(diào)用
10.1.3 編寫遞歸方法的準(zhǔn)則
10.1.4 遞歸方法的運行支持
10.1.5 兩種遞歸方法的分析
10.1.6 兩種遞歸方法的空間分析
10.2 遞歸和查找
10.2.1 數(shù)組的線性查找
10.2.2 數(shù)組的二分查找
10.3 遞歸和排序
10.3.1 快速捧序
10.3.2 歸并排序
10.4 遞歸和回溯
10.5 采用遞歸的理由
10.5.1 消除遞歸
10.5.2 尾遞歸
10.6 案例分析1：迷宮解決方案
10.6.1 要求
10.6.2 分析
10.6.3 類
10.6.4 MazeView的實現(xiàn)
10.6.5 MazcModel的實現(xiàn)
10.7 遞歸下降及其編程語言
10.7.1 語法介紹
10.7.2 識別、解析和解釋語言中的語句
10.7.3 詞匯分析和掃描器
10.7.4 解析策略
10.8 案例分析2：遞歸下降解析器
10.8.1 要求
10.8.2 分析
10.8.3 推薦的用戶界面
10.8.4 Parser的實現(xiàn)
第11章 樹
11.1 樹的概述
11.1.1 樹的討論
11.1.2 普通樹和二叉樹的正式定義
11.2 樹的表示
11.2.1 鏈表表示
11.2.2 完全二叉樹的數(shù)組表示：
11.3 二叉樹的操作
11.3.1 二叉樹的原型
11.3.2 BinaryTreePT的測試程序
11.3.3 BinaryTreePT類的實現(xiàn)
11.4 案例分析1：解析表達(dá)式樹
11.4.1 要求
11.4.2 用戶界面
11.4.3 ExpressionTree類的分析和設(shè)計
11.4.4 Parser類的分析、設(shè)計和實現(xiàn)
11.5 普通樹操作
11.5.1 樹的接口
11.5.2 Treelterator接口
11.6 普通樹類的實現(xiàn)(可選內(nèi)容)
11.6.1 實現(xiàn)中的類職責(zé)
11.6.2 AbstractTree類的設(shè)計和實現(xiàn)
11.6.3 LinkedTree類的設(shè)計和實現(xiàn)
11.6.4 樹迭代器的設(shè)計和實現(xiàn)
11.7 案例分析2：技能數(shù)據(jù)庫
11.7.1 要求
11.7.2 分析
11.7.3 模型類的設(shè)計和實現(xiàn)
11.7.4 視圖類的設(shè)計和實現(xiàn)
第12章 特殊樹
12.1 堆
12.1.1 二叉樹的形狀
12.1.2 可比對象
12.1.3 Heap接口
12.1.4 Heap實現(xiàn)
12.1.5 堆排序的實現(xiàn)
12.1.6 add方法和pop方法的實現(xiàn)
12.1.7 分析堆排序
12.1.8 迭代器的實現(xiàn)
12.1.9 使用堆實現(xiàn)優(yōu)先隊列
12.2 二叉搜索樹
12.2.1 排序集合抽象數(shù)據(jù)類型及其接口
12.2.2 排序集合抽象數(shù)據(jù)類型的實現(xiàn)
12.2.3 二分查找
12.2.4 二叉搜索樹的實現(xiàn)
12.2.5 分析二叉搜索樹
12.3 “更好的”二叉搜索樹(可選內(nèi)容)
12.3.1 2-3樹
12.3.2 AVL樹
第13章 無序集合：集、映射和包
13.1 集、映射和包概述
13.1.1 集
13.1.2 映射
13.1.3 包
13.1.4 無序集合的迭代器
13.1.5 一個簡短的例子
13.2 實現(xiàn)的考慮事項
13.2.1 散列
13.2.2 散列鏈表方法的分析
13.2.3 其他散列策略
13.3 映射原型類
13.3.1 HashMapPT類的接口
13.3.2 HashMapPT類的設(shè)計
13.4 集原型類
13.4.1 HashSetPT類的接口
13.4.2 設(shè)計和實現(xiàn)
13.5 包原型類
13.5.1 HashBagPT類的接口
13.5.2 設(shè)計和實現(xiàn)
13.6 Java集合框架中的Map類和Set類
13.6.1 映射
13.6.2 Set接口
13.7 將Bag ADT添加到集合框架
13.7.1 Bag接口
13.7.2 Bag實現(xiàn)
13.8 案例分析1：文件索引系統(tǒng)
13.8.1 要求
13.8.2 分析
13.8.3 設(shè)計和實現(xiàn)
13.9 案例分析2：信貸批準(zhǔn)系統(tǒng)
13.9.1 要求
13.9.2 分析
13.9.3 類
13.9.4 設(shè)計和實現(xiàn)
第14章 圖
14.1 概述
14.2 術(shù)語
14.3 圖的表示
14.3.1 鄰接矩陣
14.3.2 鄰接表
14.3.3 兩種表示的分析
14.3.4 運行時間的進(jìn)一步分析
14.4 圖的遍歷
14.4.1 連通圖的一般遍歷算法
14.4.2 深度優(yōu)先遍歷和廣度優(yōu)先遍歷
14.4.3 圖的分量
14.5 圖中的樹
14.5.1 生成樹和生成森林
14.5.2 最小生成樹
14.5.3 最小生成樹算法
14.6 拓?fù)渑判?br />14.7 最短路徑問題
14.7.1 Diikstra算法
14.7.2 初始化
14.7.3 計算
14.7.4 分析
14.8 圖原型
14.8.1 使用圖原型的例子
14.8.2 LinkedGraphPT類
14.8.3 LinkedVertexPT類
14.8.4 LinkedEdgePT類
14.9 一個專門的圖實現(xiàn)(可選內(nèi)容)
14.9.1 Graph接口
14.9.2 權(quán)值
14.9.3 實現(xiàn)
14：9.4 關(guān)于性能的提示
14.10 案例分析：測試圖的算法
14.10.1 要求
14.10.2 分析
14.10.3 GraphDemoViCW類
14.10.4 GraphDemoModel類
第15章 多線程、網(wǎng)絡(luò)和客戶端/服務(wù)器編程
15.1 線程和進(jìn)程
15.1.1 線程
15.1.2 休眠線程
15.1.3 生產(chǎn)者、消費者和同步
15.2 網(wǎng)絡(luò)、服務(wù)器和客戶端
15.2.1 IP地址
15.2.2 端口、服務(wù)器和客戶端
15.2.3 套接字和一個日期/時間客戶端程序
15.2.4 服務(wù)器套接字和一個日期/時間服務(wù)器端程序
15.2.5 客戶端和服務(wù)器端之間的雙向會話
15.2.6 使服務(wù)器處理多個客戶端”
15.2.7 使用服務(wù)器守護(hù)進(jìn)程
15.2.8 使用客戶端處理器
15.2.9 模型、視圖、控制器模式
15.3 案例分析：校園電話目錄
15.3.1 要求
15.3.2 分析
15.3.3 設(shè)計
15.3.4 實現(xiàn)
附錄A Java語言特性回顧
A.1 保留字
A.2 數(shù)據(jù)類型
A.3 變量、作用域和生命周期
A.4 表達(dá)式
A.5 控制語句
A.5.1 復(fù)合語句
A.5.2 if和if-else語句
A.5.3 while和do-while語句
A.5.4 for語句
A.5.5 switch語句
A.6 混合模式運算和強制類型轉(zhuǎn)換
A.7 字符串
A.8 數(shù)組
A.9 方法和參數(shù)
A.10 引用類型
A.11 包裝器類
A.12 類
A.13 接口
A.14 適配器
A.15 異常
A.16 程序包
A.17 文本文件
附錄B 層次結(jié)構(gòu)、接口及類
B.1 層次結(jié)構(gòu)
B.2 接口
B.3 類
附錄C 安裝指令
C.1 使用JDK
C.2 使用JGrasp
術(shù)語表