數(shù)據(jù)結(jié)構(gòu)與Java集合框架

第1章  Java語言的重要特性    1
1.1  類        1
1.1.1  方法描述    2
1.1.2  數(shù)據(jù)抽象    4
1.1.3  Employee類    6
1.1.4  局部變量和字段    8
1.1.5  構(gòu)造函數(shù)    8
1.1.6  實(shí)例變量和靜態(tài)變量    9
1.1.7  可見性修飾符    10
1.1.8  圖形用戶接口    10
1.1.9  Company類    11
1.1.10  繼承    12
1.1.11  可見性修飾符protected    13
1.1.12  繼承和構(gòu)造函數(shù)    15
1.1.13  多態(tài)性(Polymorphism)    19
1.1.14  信息隱藏    21
1.1.15  異常處理    22
1.1.16  異常傳送    24
1.2  小結(jié)    26
1.3  練習(xí)    27
第2章  接口和集合類    31
2.1  抽象方法和抽象類    31
2.2  接口    33
2.3  數(shù)組    36
2.4  集合類    38
2.5  集合類的存儲(chǔ)結(jié)構(gòu)    39
2.5.1  鏈接結(jié)構(gòu)    39
2.5.2  LinkedCollection類    39
2.5.3  LinkedCollection類中的
字段和方法定義    42
2.5.4  迭代器    45
2.5.5  數(shù)據(jù)結(jié)構(gòu)和Java
Collections Framework    47
2.6  小結(jié)    48
2.7  練習(xí)    48
第3章  軟件工程介紹    51
3.1  軟件開發(fā)生命期    51
3.2  問題分析    52
3.3  程序設(shè)計(jì)    53
3.3.1  方法描述和字段    54
3.3.2  依賴性圖表    55
3.4  程序?qū)崿F(xiàn)    57
3.4.1  方法驗(yàn)證    57
3.4.2  修正是否可行    58
3.4.3  評(píng)估方法的效率    58
3.4.4  大O符號(hào)    59
3.4.5  快速獲取大O估計(jì)時(shí)間    61
3.4.6  平衡    64
3.4.7  運(yùn)行時(shí)分析    65
3.4.8  Random類    66
3.5  程序維護(hù)    67
3.6  小結(jié)    68
3.7  練習(xí)    68
第4章  遞歸    73
4.1  緒論    73
4.2  階乘    74
4.3  十進(jìn)制轉(zhuǎn)換成二進(jìn)制    77
4.4  漢諾塔    80
4.5  回溯    88
4.6  二叉樹搜索    96
4.7  間接遞歸    105
4.8  遞歸的開銷    105
4.9  小結(jié)    106
4.10  練習(xí)    107
第5章  數(shù)組列表    119
5.1  List接口    119
5.2  ArrayList類    120
5.2.1  ArrayList類的方法描述    122
5.2.2  ArrayList類標(biāo)題    127
5.2.3  ArrayList類中的字段    128
5.2.4  ArrayList對(duì)象可串行化性    128
5.2.5  ArrayList對(duì)象的可克隆性    129
5.3  實(shí)現(xiàn)ArrayList類    130
5.3.1  定義add方法    131
5.3.2  分?jǐn)倳r(shí)間    133
5.3.3  clone方法和copy構(gòu)造函數(shù)    134
5.3.4  Fail-Fast 迭代器    135
5.4  高精度算法    136
5.4.1  設(shè)計(jì)VeryLongInt類    137
5.4.2  實(shí)現(xiàn)VeryLongInt類    138
5.5  VECTOR類    141
5.6  小結(jié)    141
5.7  練習(xí)    141
第6章  鏈表    149
6.1  LinkedList類    149
6.1.1  比較LinkedList類
和ArrayList類    151
6.1.2  LinkList迭代器    153
6.1.3  LinkedList類的字段和
實(shí)現(xiàn)方法    158
6.1.4  ListItr類的字段和實(shí)現(xiàn)    164
6.1.5  LinkedList類的其他設(shè)計(jì)
和實(shí)現(xiàn)方法    167
6.1.6  循環(huán)鏈表    169
6.2  行編輯器    171
6.2.1  設(shè)計(jì)Editor類    174
6.2.2  實(shí)現(xiàn)Editor類    176
6.2.3  Editor類方法的大O分析    179
6.2.4  EditorDirver類    179
6.3  小結(jié)    181
6.4  練習(xí)    181
第7章  隊(duì)列和堆棧    187
7.1  隊(duì)列    187
7.1.1  Queue類的設(shè)計(jì)與實(shí)現(xiàn)    188
7.1.2  Queue類可選擇的設(shè)計(jì)和實(shí)現(xiàn)    190
7.2  計(jì)算機(jī)模擬    194
7.3  應(yīng)用：模擬洗車    195
7.3.1  CarWash類的設(shè)計(jì)    196
7.3.2  CarWash類的實(shí)現(xiàn)    197
7.3.3  CarWash方法分析    200
7.3.4  隨機(jī)到達(dá)時(shí)間    200
7.4  堆棧    201
7.4.1  Stack類的設(shè)計(jì)和實(shí)現(xiàn)    202
7.4.2  Java集合框架中的Stack類    202
7.4.3  Stack類可選的設(shè)計(jì)和實(shí)現(xiàn)    203
7.5  應(yīng)用：如何編譯實(shí)現(xiàn)遞歸    203
7.6  應(yīng)用：中綴表達(dá)式到后綴
表達(dá)式的轉(zhuǎn)換    207
7.6.1  后綴表示    208
7.6.2  轉(zhuǎn)換矩陣    210
7.6.3  標(biāo)記    211
7.6.4  前綴表達(dá)式    212
7.7  小結(jié)    214
7.8  練習(xí)    215
第8章  二叉樹和二叉搜索樹    225
8.1  二叉樹的定義和屬性    226
8.1.1  二叉樹定理    232
8.1.2  外部路徑長度    234
8.1.3  對(duì)二叉樹的遍歷    235
8.2  二叉搜索樹    240
8.2.1  BinSearchTree類    241
8.2.2  BinSearchTree類的字段
及內(nèi)置類    243
8.2.3  BinSearchTree類的實(shí)現(xiàn)    244
8.2.4  remove方法    249
8.2.5  TreeIterator類    256
8.3  小結(jié)    258
8.4  練習(xí)    259
第9章  平衡二叉搜索樹    265
9.1  二叉搜索樹的一個(gè)問題    265
9.2  旋轉(zhuǎn)    266
9.3  AVL樹    270
9.3.1  AVL樹的高度    271
9.3.2  AVLTree類    272
9.3.3  fixAfterInsertion方法    274
9.3.4  add方法的正確性    282
9.4  RED-BLACK樹    284
9.5  小結(jié)    290
9.6  練習(xí)    290
第10章  TreeMap和TreeSet    295
10.1  TreeMap類    295
10.1.1  TreeMap類的方法介紹    296
10.1.2  TreeMap類的字段    298
10.1.3  Comparator接口和
Comparable接口    299
10.1.4  Entry類    300
10.1.5  TreeMap類的實(shí)現(xiàn)    300
10.1.6  fixAfterInsertion方法    302
10.1.7  Insertion的三種情況    303
10.1.8  TreeMap類的其他方法    307
10.1.9  fixAfterDeletion方法    311
10.1.10  entrySet方法    318
10.2  TREEMAP對(duì)象：一個(gè)簡單
的辭典    318
10.2.1  Thesaurus類的設(shè)計(jì)和實(shí)現(xiàn)    319
10.2.2  ThesaurusDriver類的
設(shè)計(jì)和實(shí)現(xiàn)    320
10.3  TreeSet類    322
10.4  一個(gè)簡單的拼寫檢查器    326
10.4.1  SpellChecker類的設(shè)計(jì)
和實(shí)現(xiàn)    327
10.4.2  SpellCheckerDriver類
的設(shè)計(jì)與實(shí)現(xiàn)    328
10.5  小結(jié)    330
10.6  練習(xí)    331
第11章  優(yōu)先級(jí)隊(duì)列    337
11.1  簡介    337
11.2  PriorityQueue接口的定義    338
11.3  PriorityQueue接口的實(shí)現(xiàn)    339
11.3.1  Heap類    340
11.3.2  Heap類中的字段    344
11.3.3  Heap類的實(shí)現(xiàn)    344
11.3.4  percolateUp方法    345
11.3.5  percolateDown方法    349
11.4  應(yīng)用：Huffman編碼    351
11.4.1  Huffman樹    353
11.4.2  貪婪算法    356
11.4.3  Huffman類    356
11.5  小結(jié)    361
11.6  練習(xí)    362
第12章  排序    367
12.1  簡介    367
12.2  插入排序    368
12.3  排序能有多快    370
12.4  快速排序法    371
12.4.1  歸并排序    372
12.4.2  樹排序    377
12.4.3  堆排序    379
12.4.4  快速排序    383
12.5  小結(jié)    391
12.6  練習(xí)    391
第13章  檢索和散列類    401
13.1  檢索的分析框架    401
13.2  檢索概述    402
13.2.1  順序檢索    402
13.2.2  二分法檢索    403
13.2.3  red-black樹檢索    403
13.3  HashMap類    404
13.3.1  HashMap類的方法描述    404
13.3.2  HashMap類的字段    406
13.3.3  散列設(shè)計(jì)    406
13.3.4  hashCode方法    409
13.3.5  均勻散列假設(shè)    410
13.3.6  鏈    411
13.3.7  HashMap類的實(shí)現(xiàn)    412
13.3.8  鏈?zhǔn)缴⒘蟹治?nbsp;   416
13.3.9  HashIterator類    418
13.4  HashSet類    419
13.5  開放地址散列    419
13.5.1  remove方法    421
13.5.2  主簇    425
13.5.3  雙散列    426
13.5.4  開放地址散列分析    429
13.6  小結(jié)    432
13.7  練習(xí)    432
第14章  圖、樹和網(wǎng)絡(luò)    437
14.1  無向圖    437
14.2  有向圖    440
14.3  樹    441
14.4  網(wǎng)絡(luò)    442
14.5  圖的算法    443
14.5.1  迭代器    444
14.5.2  連通性    449
14.5.3  產(chǎn)生最小生成樹    450
14.5.4  在網(wǎng)絡(luò)中尋找最短路徑    454
14.6  開發(fā)Network類    457
14.6.1  Network類的方法描述    458
14.6.2  Network類的字段    460
14.6.3  實(shí)現(xiàn)Network類    462
14.6.4  Network類的另一種
設(shè)計(jì)和實(shí)現(xiàn)    469
14.7  突破網(wǎng)絡(luò)    471
14.8  小結(jié)    473
14.9  練習(xí)    474
附錄A  數(shù)學(xué)背景知識(shí)    481
A.1  簡介    481
A.2  函數(shù)和數(shù)列    481
A.3  求和與求積    482
A.4  對(duì)數(shù)    483
A.5  數(shù)學(xué)歸納法    485
A.6  練習(xí)    492
附錄B  GUI和GUIListener類    495
B.1  簡介    495
B.2  線程    496
B.3  實(shí)現(xiàn)Process接口    497
B.4  GUI類    499
B.4.1  GUI構(gòu)造函數(shù)    500
B.4.2  GUI類中的其他方法    501
B.5  GUIListener類    502
B.6  綜合應(yīng)用    503
附錄C  Java集合框架    505
C.1  簡介    505
C.2  Collection接口    505
C.3  List接口    507
C.4  ListIterator接口    509
C.5  Set接口    511
C.6  Map接口    513
C.7  ArrayList類    516
C.8  LinkedList類    527
C.9  TreeSet類    543
C.10  TreeMap類    555
C.11  HashSet類    567
C.12  HashMap類    575