數(shù)據(jù)結(jié)構(gòu)——Java版

第1章 軟件工程基本原理和Java類
1.1 軟件的生命周期
1.2 軟件開發(fā)階段
1.2.1 分析階段
1.2.2 設(shè)計階段
1.2.3 實現(xiàn)階段
1.2.4 測試和調(diào)試
1.3 算法分析：大O表示法
1.4 用戶定義的類
1.4.1 構(gòu)造函數(shù)
1.4.2 統(tǒng)一建模語言圖
1.4.3 變量聲明和對象實例化
1.4.4 訪問類的成員
1.4.5 類的內(nèi)置運算
1.4.6 賦值運算符和類
1.4.7 類的作用域
1.4.8 定義類Clock的構(gòu)造函數(shù)和方法
1.4.9 拷貝構(gòu)造函數(shù)
1.4.10 類和方法toString
1.4.11 類的靜態(tài)成員
1.4.12 類的靜態(tài)變量(數(shù)據(jù)成員)
1.4.13 析構(gòu)函數(shù)
1.4.14 創(chuàng)建自己的包
1.4.15 多文件程序
1.4.16 引用this
1.4.17 內(nèi)部類
1.5 抽象數(shù)據(jù)類型
1.6 編程示例：糖果機
1.6.1 問題分析和算法設(shè)計
1.6.2 收銀機
1.6.3 自動售貨機
1.6.4 主程序
1.7 標(biāo)識類、對象和操作
1.8 快速總結(jié)
1.9 練習(xí)題
1.10 編程練習(xí)
第2章 繼承和異常處理
2.1 繼承
2.1.1 在子類中使用超類的方法
2.1.2 子類與超類的構(gòu)造函數(shù)
2.1.3 類的受保護(hù)成員
2.1.4 類Object
2.1.5 超類和子類的對象
2.1.6 運算符instanceof
2.2 抽象方法和抽象類
2.3 聚合
2.4 異常處理
2.4.1 Java異常層次結(jié)構(gòu)
2.4.2 異常層次結(jié)構(gòu)
2.4.3 已解析的異常和未解析的異常
2.4.4 處理程序中的異常
2.4.5 拋出和重新拋出異常
2.4.6 異常處理技術(shù)
2.4.7 創(chuàng)建自己的異常類
2.5 編程示例：成績報告單
2.5.1 問題分析與算法設(shè)計
2.5.2 主程序
2.5.3 程序清單
2.6 快速總結(jié)
2.7 練習(xí)題
2.8 編程練習(xí)
第3章 基于數(shù)組的表
3.1 表元素的類型
3.1.1 類IntElement
3.1.2 類StringElement
3.2 類ArrayListClass
3.2.1 拷貝構(gòu)造函數(shù)
3.2.2 方法copyList
3.3 無序表
3.3.1 搜索
3.3.2 插入
3.3.3 刪除
3.3.4 各種表操作的時間復(fù)雜度
3.4 類Vector
3.5 編程示例：多項式的運算
3.6 快速回顧
3.7 練習(xí)題
3.8 編程練習(xí)
第4章 鏈表
4.1 鏈表
4.1.1 鏈表的一些屬性
4.1.2 遍歷鏈表
4.2 鏈表元素的插入和刪除
4.2.1 插入
4.2.2 刪除
4.3 構(gòu)建鏈表
4.3.1 正向構(gòu)建鏈表
4.3.2 反向構(gòu)建鏈表
4.4 ADT鏈表
4.4.1 鏈表的長度
4.4.2 檢索第一個節(jié)點和最后一個節(jié)點的數(shù)據(jù)
4.4.3 在鏈表頭插入節(jié)點
4.4.4 在鏈表尾插入節(jié)點
4.4.5 復(fù)制鏈表
4.4.6 拷貝構(gòu)造函數(shù)
4.4.7 copyList方法
4.4.8 類LinkedListClass的定義
4.5 無序鏈表
4.5.1 搜索鏈表
4.5.2 刪除節(jié)點
4.6 有序鏈表
4.6.1 搜索鏈表
4.6.2 插入節(jié)點
4.6.3 刪除節(jié)點
4.7 雙向鏈表
4.7.1 默認(rèn)構(gòu)造函數(shù)
4.7.2 isEmptyList
4.7.3 初始化鏈表
4.7.4 鏈表的長度
4.7.5 輸出鏈表
4.7.6 反向輸出鏈表
4.7.7 搜索鏈表
4.7.8 第一個和最后一個元素
4.7.9 插入節(jié)點
4.7.10 刪除節(jié)點
4.8 帶有頭節(jié)點和尾節(jié)點的鏈表
4.9 循環(huán)鏈表
4.10 編程示例：音像店
4.11 快速回顧
4.12 練習(xí)題
4.13 編程練習(xí)
第5章 遞歸
5.1 遞歸的定義
5.1.1 直接遞歸和間接遞歸
5.1.2 無窮遞歸
5.2 使用遞歸法解決問題
5.3 編程示例：將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)
5.4 編程示例：Sierpinski gasket
5.4.1 問題分析和算法設(shè)計
5.4.2 完整的程序清單
5.5 使用遞歸還是迭代
5.6 遞歸和回溯：8-皇后問題
5.6.1 回溯
5.6.2 n-皇后問題
5.6.3 回溯和4-皇后問題
5.6.4 8-皇后問題
5.7 快速回顧
5.8 練習(xí)題
5.9 編程練習(xí)
第6章 堆棧
6.1 堆棧
6.2 StackException類
6.3 使用數(shù)組實現(xiàn)堆棧
6.3.1 初始化堆棧
6.3.2 空堆棧
6.3.3 滿堆棧
6.3.4 入棧
6.3.5 返回棧頂元素
6.3.6 出棧
6.3.7 復(fù)制
6.3.8 構(gòu)造函數(shù)
6.3.9 拷貝構(gòu)造函數(shù)
6.3.10 CopyStack方法
6.4 編程示例：求最高GPA
6.5 把堆棧實現(xiàn)為鏈表
6.5.1 默認(rèn)構(gòu)造函數(shù)
6.5.2 初始化堆棧
6.5.3 入棧
6.5.4 返回棧頂元素
6.5.5 出棧
6.6 由類LinkedListClass派生而來的堆棧
6.7 堆棧的應(yīng)用：后綴表達(dá)式計算器
6.7.1 主算法
6.7.2 方法evaluateExpression
6.7.3 方法evaluateOpr
6.7.4 方法printResult
6.7.5 完整的程序清單
6.8 后綴表達(dá)式計算器：圖形用戶界面(GUI)
6.9 消除遞歸：反向打印鏈表的非遞歸算法
6.10 類Stack
6.11 快速回顧
6.12 練習(xí)題
6.13 編程練習(xí)
第7章 隊列
7.1 隊列
7.2 隊列的異常類
7.3 隊列的數(shù)組實現(xiàn)
7.4 隊列的鏈表實現(xiàn)
7.5 從類LinkedListClass派生而來的隊列
7.6 優(yōu)先隊列
7.7 隊列的應(yīng)用：模擬
7.7.1 設(shè)計隊列系統(tǒng)
7.7.2 客戶
7.7.3 服務(wù)器
7.7.4 服務(wù)器表
7.7.5 等待客戶的隊列
7.7.6 主程序
7.8 快速回顧
7.9 練習(xí)題
7. 10 編程練習(xí)
第8章 搜索算法
8.1 搜索算法
8.1.1 順序搜索
8.1.2 順序搜索算法分析
8.1.3 有序表
8.1.4 二叉樹搜索
8.1.5 二叉樹搜索算法的性能
8.1.6 將數(shù)據(jù)項插入有序表
8.2 基于比較的搜索算法的下限
8.3 散列算法
8.3.1 散列函數(shù)：示例
8.3.2 沖突的解決
8.3.3 沖突的解決：開型尋址法
8.3.4 二次探測
8.3.5 刪除：開型尋址法
8.3.6 散列算法：使用二次探測來實現(xiàn)
8.3.7 沖突的解決：鏈地址法(開散列方法)
8.3.8 散列法性能分析
8.4 快速回顧
8.5 練習(xí)題
8.6 編程練習(xí)
第9章 排序算法
9.1 排序算法
9.2 選擇排序: 基于數(shù)組的表
9.3 插入排序: 基于數(shù)組的表
9.4 插入排序: 基于鏈表的表
9.5 基于比較的排序算法的下限
9.6 快速排序：基于數(shù)組的表
9.7 歸并排序: 基于鏈表的表
9.7.1 劃分
9.7.2 歸并
9.7.3 分析：歸并排序
9.8 堆排序: 基于數(shù)組的表
9.8.1 構(gòu)建堆
9.8.2 分析：堆排序
9.9 再論優(yōu)先級隊列
9.9.1 在優(yōu)先級隊列中插入一個元素
9.9.2 從優(yōu)先級隊列刪除一個元素
9.10 編程示例：選舉結(jié)果
9.10.1 問題分析和算法設(shè)計
9.10.2 主程序
9.10.3 對姓名排序
9.10.4 處理投票數(shù)據(jù)
9.10.5 計算選票數(shù)的總和
9.10.6 打印標(biāo)題和結(jié)果
9.11 快速回顧
9.12 練習(xí)題
9.13 編程練習(xí)
第10章 二叉樹
10.1 二叉樹
10.2 二叉樹的遍歷
10.2.1 中序遍歷
10.2.2 前序遍歷
10.2.3 后序遍歷
10.2.4 二叉樹的實現(xiàn)
10.3 二叉搜索樹
10.3.1 search方法
10.3.2 Insert方法
10.3.3 Delete方法
10.4 二叉搜索樹分析
10.5 二叉樹的非遞歸遍歷算法
10.5.1 非遞歸的中序遍歷算法
10.5.2 非遞歸的前序遍歷算法
10.5.3 非遞歸的后序遍歷算法
10.6 AVL(平衡)樹
10.6.1 AVL樹的插入操作
10.6.2 AVL樹的旋轉(zhuǎn)
10.6.3 AVL樹的刪除操作
10.6.4 AVL樹的性能分析
10.7 編程示例：音像店
10.8 快速回顧
10.9 練習(xí)題
10.10 編程練習(xí)
第11章 圖
11.1 圖的簡史
11.2 圖的定義和符號
11.3 圖的表示方法
11.3.1 鄰接矩陣
11.3.2 鄰接表
11.4 圖的操作
11.5 圖的ADT定義
11.6 圖的遍歷
11.6.1 深度優(yōu)先遍歷
11.6.2 廣度優(yōu)先遍歷
11.7 最短路徑算法
11.8 最小生成樹
11.9 拓?fù)渑判?br />11.10 快速回顧
11.11 練習(xí)題
11.12 編程練習(xí)
附錄A 保留字
附錄B 運算符優(yōu)先級
附錄C 字符集
附錄D 包和用戶定義的類
附錄E Java類
附錄F 針對C++程序員的JAVA介紹
附錄G 參考文獻(xiàn)
附錄H 部分習(xí)題答案