Java軟件結(jié)構(gòu)：設(shè)計(jì)和使用數(shù)據(jù)結(jié)構(gòu)

第1章 軟件開(kāi)發(fā) 1
1.1 軟件工程 1
專業(yè)水準(zhǔn)與道德規(guī)范 2
1.2 軟件質(zhì)量 3
正確性 3
可靠性 3
健壯性 4
可用性 4
可維護(hù)性 4
可重用性 5
可移植性 5
效率 6
質(zhì)量問(wèn)題 6
1.3 開(kāi)發(fā)生命周期模型 6
瀑布模型（Waterfall Model） 8
螺旋模型（Spiral Model） 9
演化開(kāi)發(fā)模型 10
1.4 統(tǒng)一建模語(yǔ)言（Unified Modeling
Language，UML） 10
UML關(guān)系 11
1.5 錯(cuò)誤處理 14
1.6 算法分析 15
增長(zhǎng)函數(shù)（Growth Function）及
Big O( )記法 15
增長(zhǎng)函數(shù)的比較 16
循環(huán)執(zhí)行分析 17
嵌套循環(huán) 18
1.7 軟件工程與數(shù)據(jù)結(jié)構(gòu) 19
第2章 面向?qū)ο笤O(shè)計(jì) 23
2.1 面向?qū)ο髢?nèi)容綜述 23
2.2 對(duì)象的使用 24
抽象 24
對(duì)象的創(chuàng)建 25
2.3 類的庫(kù)與包 26
import（導(dǎo)入）聲明 27
2.4 狀態(tài)與行為 28
2.5 類 29
實(shí)例數(shù)據(jù) 31
2.6 封裝 31
可見(jiàn)性修飾符 32
局部數(shù)據(jù) 33
2.7 構(gòu)造函數(shù) 34
2.8 方法重載 34
2.9 再論引用 35
空（null）引用 36
this引用 36
別名 38
垃圾回收 39
將對(duì)象作為參數(shù)傳遞 40
2.10 static（靜態(tài)）修飾符 40
靜態(tài)變量 40
靜態(tài)方法 41
2.11 包裝類 41
2.12 接口 42
Comparable接口 44
Iterator接口 44
2.13 繼承 44
派生類 45
protected（保護(hù)）修飾符 47
super（超級(jí)）引用 47
方法的重寫 48
2.14 類的層次結(jié)構(gòu) 48
Object類 49
抽象類 50
接口的層次結(jié)構(gòu) 51
2.15 多態(tài) 52
引用和類的層次結(jié)構(gòu) 53
基于繼承的多態(tài) 53
基于接口的多態(tài) 55
2.16 泛型 56
2.17 異常 57
異常消息 58
try語(yǔ)句 58
異常傳播 59
異常類的層次結(jié)構(gòu) 60
第3章 集合 66
3.1 集合介紹 66
抽象數(shù)據(jù)類型 67
Java集合API 69
3.2 set集合 69
接口 70
迭代器 72
異常 72
3.3 使用set：bingo 73
3.4 實(shí)現(xiàn)set：利用數(shù)組 76
容量的管理 77
3.5 ArraySet類 77
size運(yùn)算和isEmpty運(yùn)算 79
add運(yùn)算 80
addAll運(yùn)算 82
removeRandom運(yùn)算 82
remove運(yùn)算 83
union運(yùn)算 84
contains運(yùn)算 85
equals運(yùn)算 85
iterator運(yùn)算 86
toString運(yùn)算 88
UML描述 88
3.6 ArraySet的分析 88
add的分析 89
remove的分析 90
removeRandom的分析 90
addAll的分析 90
find、contains的分析 90
union的分析 90
equals的分析 91
第4章 鏈?zhǔn)浇Y(jié)構(gòu) 94
4.1 用做鏈接的引用 94
4.2 管理鏈表 96
插入節(jié)點(diǎn) 96
刪除節(jié)點(diǎn) 97
啞節(jié)點(diǎn) 98
4.3 沒(méi)有鏈接的元素 98
雙向鏈表 99
4.4 實(shí)現(xiàn)set：利用鏈接 99
LinkedSet類 100
add運(yùn)算 102
removeRandom運(yùn)算 103
remove運(yùn)算 104
iterator運(yùn)算 105
4.5 LinkedSet的分析 107
add的分析 107
remove的分析 108
removeRandom的分析 108
第5章 Black Jack 111
5.1 Black Jack游戲 111
5.2 初始設(shè)計(jì) 111
5.3 實(shí)現(xiàn)Black Jack游戲 115
Card類 115
Deck類 117
Hand類 122
BlackJack類 125
BlackJackGUI類 128
BlackJackDemo類 135
第6章 堆棧 137
6.1 堆棧ADT 137
6.2 堆棧的使用：計(jì)算后綴表達(dá)式
的值 140
6.3 堆棧的使用：穿越迷宮 146
6.4 堆棧的實(shí)現(xiàn)：鏈接實(shí)現(xiàn) 151
push操作 151
pop操作 152
其他操作 153
6.5 堆棧的實(shí)現(xiàn)：數(shù)組實(shí)現(xiàn) 153
push操作 154
pop操作 154
其他操作 155
6.6 堆棧的實(shí)現(xiàn)：java.util.Stack類 156
惟一操作 156
繼承和實(shí)現(xiàn) 156
6.7 堆棧實(shí)現(xiàn)的分析 157
push操作的分析 157
pop操作的分析 158
第7章 隊(duì)列 162
7.1 隊(duì)列ADT 162
7.2 使用隊(duì)列：代碼密鑰 164
7.3 使用隊(duì)列：售票口模擬 167
7.4 使用隊(duì)列：基數(shù)排序 171
7.5 實(shí)現(xiàn)隊(duì)列：利用鏈接 175
enqueue運(yùn)算 175
dequeue運(yùn)算 176
其他運(yùn)算 178
7.6 實(shí)現(xiàn)隊(duì)列：利用數(shù)組 178
enqueue運(yùn)算 178
dequeue運(yùn)算 179
其他運(yùn)算 180
7.7 實(shí)現(xiàn)隊(duì)列：利用環(huán)形數(shù)組 181
7.8 分析各種隊(duì)列實(shí)現(xiàn) 184
enqueue 184
遞增count 184
dequeue 185
第8章 列表 190
8.1 列表ADT（Abstract Data Type，
抽象數(shù)據(jù)類型） 190
8.2 運(yùn)用有序列表：錦標(biāo)賽主辦者 196
8.3 運(yùn)用索引表：Josephus問(wèn)題 201
8.4 實(shí)現(xiàn)列表：利用數(shù)組 203
remove操作 204
Contains操作 206
有序列表的添加（add）操作 206
無(wú)序列表的特有操作 207
索引列表的特有操作 207
8.5 實(shí)現(xiàn)列表：利用鏈接 208
remove操作 208
雙向鏈表 209
8.6 列表的實(shí)現(xiàn)分析 212
有序列表的實(shí)現(xiàn)分析 214
無(wú)序列表的實(shí)現(xiàn)分析 214
索引列表的實(shí)現(xiàn)分析 216
第9章 計(jì)算器 220
9.1 計(jì)算器 220
9.2 初始設(shè)計(jì) 220
9.3 實(shí)現(xiàn)計(jì)算器 224
infixToPostfix類 224
listPostfixEvaluator類 228
CalculatorGUI類 230
CalculatorDemo類 235
第10章 遞歸 238
10.1 遞歸地思考 238
無(wú)窮遞歸 239
數(shù)學(xué)中的遞歸 240
10.2 遞歸地編程 240
遞歸與迭代 242
直接遞歸與間接遞歸 243
10.3 使用遞歸 243
游歷迷宮 243
河內(nèi)塔 247
10.4 分析遞歸算法 251
第11章 排序和查找 256
11.1 查找 256
線性查找法 257
二分查找法 258
查找算法的比較 260
11.2 排序 261
選擇排序法 263
插入排序法 265
冒泡排序法 266
快速排序法 268
歸并排序法 270
第12章 樹(shù) 275
12.1 樹(shù) 275
樹(shù)的分類 276
12.2 樹(shù)的實(shí)現(xiàn)策略 278
樹(shù)的數(shù)組實(shí)現(xiàn)之計(jì)算策略 278
樹(shù)的數(shù)組實(shí)現(xiàn)之模擬鏈接策略 279
樹(shù)的分析 279
12.3 樹(shù)的遍歷 280
前序遍歷 280
中序遍歷 281
后序遍歷 282
層序遍歷 282
12.4 二叉樹(shù)的實(shí)現(xiàn) 283
removeLeftSubtree方法 288
find方法 289
iteratorInOrder方法 290
12.5 二叉樹(shù)的使用：表達(dá)式樹(shù) 291
第13章 二叉查找樹(shù) 302
13.1 二叉查找樹(shù) 302
13.2 實(shí)現(xiàn)二叉查找樹(shù)：利用鏈接 304
addElement運(yùn)算 304
removeElement運(yùn)算 306
removeAllOccurrences運(yùn)算 309
removeMin運(yùn)算 310
13.3 使用二叉查找樹(shù)：實(shí)現(xiàn)有序
列表 310
BinarySearchTreeList實(shí)現(xiàn)的
分析 313
13.4 平衡二叉查找樹(shù) 314
右旋 314
左旋 315
右左旋 315
左右旋 316
13.5 實(shí)現(xiàn)二叉查找樹(shù)：AVL樹(shù) 317
AVL樹(shù)中的右旋 317
AVL樹(shù)中的左旋 317
AVL樹(shù)中的右左旋 318
AVL樹(shù)中的左右旋 318
13.6 實(shí)現(xiàn)二叉查找樹(shù)：紅黑樹(shù) 319
紅黑樹(shù)中的插入 320
紅黑樹(shù)中的元素刪除 322
13.7 實(shí)現(xiàn)二叉查找樹(shù)：Java集合
API 324
第14章 祖先樹(shù) 331
14.1 祖先樹(shù) 331
14.2 初始設(shè)計(jì) 331
14.3 祖先樹(shù)的實(shí)現(xiàn) 335
Person類 335
AncestorTreeNode類 335
AncestorTree類 336
AncestorGUI類 345
AncestorDemo類 358
第15章 堆 361
15.1 堆 361
addElement操作 362
removeMin操作 363
findMin操作 364
15.2 堆的使用：堆排序 365
15.3 堆的使用：優(yōu)先級(jí)隊(duì)列 365
15.4 堆的實(shí)現(xiàn)：利用鏈接 368
addElement操作 368
removeMin操作 371
findMin操作 373
15.5 堆的實(shí)現(xiàn)：利用數(shù)組 373
addElement操作 373
removeMin操作 374
findMin 操作 376
15.6 堆實(shí)現(xiàn)的分析 376
addElement操作 376
removeMin操作 376
findMin 操作 377
堆排序 377
第16章 多路查找樹(shù) 381
16.1 整合樹(shù)的概念 381
16.2 2-3樹(shù) 381
向2-3樹(shù)中插入元素 382
從2-3樹(shù)中刪除元素 384
16.3 2-4樹(shù) 387
16.4 B樹(shù) 388
16.5 創(chuàng)建和使用B樹(shù)的動(dòng)因 388
B*樹(shù) 389
B+樹(shù) 389
B樹(shù)的分析 390
16.6 B樹(shù)的實(shí)現(xiàn)策略 390
第17章 散列（Hashing） 394
17.1 散列 394
17.2 散列函數(shù) 396
除法方法 396
折疊法 397
平方取中間值法 397
基數(shù)轉(zhuǎn)換法 397
數(shù)字分析法 398
長(zhǎng)度依賴法 398
Java語(yǔ)言中的散列函數(shù) 398
17.3 解決沖突 398
鏈鎖法 399
開(kāi)地址 400
17.4 從散列表刪除元素 402
從鏈鎖式實(shí)現(xiàn)中刪除 402
從開(kāi)地址實(shí)現(xiàn)中刪除 403
17.5 Java集合API中的散列表 403
Hashtable類 404
HashSet類 405
HashMap類 406
IdentityHashMap類 406
WeakHashMap類 407
LinkedHashSet與
LinkedHashMap 408
第18章 圖 413
18.1 無(wú)向圖 413
18.2 有向圖 415
18.3 網(wǎng)絡(luò) 416
18.4 常見(jiàn)的圖算法 417
遍歷 417
測(cè)試連通性 421
最小生成樹(shù) 422
判定最短路徑 424
18.5 圖的實(shí)現(xiàn)策略 425
鄰接表 425
鄰接矩陣 426
第19章 Web爬蟲(chóng)工具 430
19.1 Web爬蟲(chóng)工具 430
19.2 初始設(shè)計(jì) 430
19.3 實(shí)現(xiàn)Web爬蟲(chóng)工具 432
WebCrawler類 433
WebcrawlerGUI類 439
WebCrawlerDemo類 441