數(shù)據(jù)結構與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  構造函數(shù)    8
1.1.6  實例變量和靜態(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  繼承和構造函數(shù)    15
1.1.13  多態(tài)性(Polymorphism)    19
1.1.14  信息隱藏    21
1.1.15  異常處理    22
1.1.16  異常傳送    24
1.2  小結    26
1.3  練習    27
第2章  接口和集合類    31
2.1  抽象方法和抽象類    31
2.2  接口    33
2.3  數(shù)組    36
2.4  集合類    38
2.5  集合類的存儲結構    39
2.5.1  鏈接結構    39
2.5.2  LinkedCollection類    39
2.5.3  LinkedCollection類中的
字段和方法定義    42
2.5.4  迭代器    45
2.5.5  數(shù)據(jù)結構和Java
Collections Framework    47
2.6  小結    48
2.7  練習    48
第3章  軟件工程介紹    51
3.1  軟件開發(fā)生命期    51
3.2  問題分析    52
3.3  程序設計    53
3.3.1  方法描述和字段    54
3.3.2  依賴性圖表    55
3.4  程序實現(xiàn)    57
3.4.1  方法驗證    57
3.4.2  修正是否可行    58
3.4.3  評估方法的效率    58
3.4.4  大O符號    59
3.4.5  快速獲取大O估計時間    61
3.4.6  平衡    64
3.4.7  運行時分析    65
3.4.8  Random類    66
3.5  程序維護    67
3.6  小結    68
3.7  練習    68
第4章  遞歸    73
4.1  緒論    73
4.2  階乘    74
4.3  十進制轉換成二進制    77
4.4  漢諾塔    80
4.5  回溯    88
4.6  二叉樹搜索    96
4.7  間接遞歸    105
4.8  遞歸的開銷    105
4.9  小結    106
4.10  練習    107
第5章  數(shù)組列表    119
5.1  List接口    119
5.2  ArrayList類    120
5.2.1  ArrayList類的方法描述    122
5.2.2  ArrayList類標題    127
5.2.3  ArrayList類中的字段    128
5.2.4  ArrayList對象可串行化性    128
5.2.5  ArrayList對象的可克隆性    129
5.3  實現(xiàn)ArrayList類    130
5.3.1  定義add方法    131
5.3.2  分攤時間    133
5.3.3  clone方法和copy構造函數(shù)    134
5.3.4  Fail-Fast 迭代器    135
5.4  高精度算法    136
5.4.1  設計VeryLongInt類    137
5.4.2  實現(xiàn)VeryLongInt類    138
5.5  VECTOR類    141
5.6  小結    141
5.7  練習    141
第6章  鏈表    149
6.1  LinkedList類    149
6.1.1  比較LinkedList類
和ArrayList類    151
6.1.2  LinkList迭代器    153
6.1.3  LinkedList類的字段和
實現(xiàn)方法    158
6.1.4  ListItr類的字段和實現(xiàn)    164
6.1.5  LinkedList類的其他設計
和實現(xiàn)方法    167
6.1.6  循環(huán)鏈表    169
6.2  行編輯器    171
6.2.1  設計Editor類    174
6.2.2  實現(xiàn)Editor類    176
6.2.3  Editor類方法的大O分析    179
6.2.4  EditorDirver類    179
6.3  小結    181
6.4  練習    181
第7章  隊列和堆棧    187
7.1  隊列    187
7.1.1  Queue類的設計與實現(xiàn)    188
7.1.2  Queue類可選擇的設計和實現(xiàn)    190
7.2  計算機模擬    194
7.3  應用：模擬洗車    195
7.3.1  CarWash類的設計    196
7.3.2  CarWash類的實現(xiàn)    197
7.3.3  CarWash方法分析    200
7.3.4  隨機到達時間    200
7.4  堆棧    201
7.4.1  Stack類的設計和實現(xiàn)    202
7.4.2  Java集合框架中的Stack類    202
7.4.3  Stack類可選的設計和實現(xiàn)    203
7.5  應用：如何編譯實現(xiàn)遞歸    203
7.6  應用：中綴表達式到后綴
表達式的轉換    207
7.6.1  后綴表示    208
7.6.2  轉換矩陣    210
7.6.3  標記    211
7.6.4  前綴表達式    212
7.7  小結    214
7.8  練習    215
第8章  二叉樹和二叉搜索樹    225
8.1  二叉樹的定義和屬性    226
8.1.1  二叉樹定理    232
8.1.2  外部路徑長度    234
8.1.3  對二叉樹的遍歷    235
8.2  二叉搜索樹    240
8.2.1  BinSearchTree類    241
8.2.2  BinSearchTree類的字段
及內(nèi)置類    243
8.2.3  BinSearchTree類的實現(xiàn)    244
8.2.4  remove方法    249
8.2.5  TreeIterator類    256
8.3  小結    258
8.4  練習    259
第9章  平衡二叉搜索樹    265
9.1  二叉搜索樹的一個問題    265
9.2  旋轉    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  小結    290
9.6  練習    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類的實現(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對象：一個簡單
的辭典    318
10.2.1  Thesaurus類的設計和實現(xiàn)    319
10.2.2  ThesaurusDriver類的
設計和實現(xiàn)    320
10.3  TreeSet類    322
10.4  一個簡單的拼寫檢查器    326
10.4.1  SpellChecker類的設計
和實現(xiàn)    327
10.4.2  SpellCheckerDriver類
的設計與實現(xiàn)    328
10.5  小結    330
10.6  練習    331
第11章  優(yōu)先級隊列    337
11.1  簡介    337
11.2  PriorityQueue接口的定義    338
11.3  PriorityQueue接口的實現(xiàn)    339
11.3.1  Heap類    340
11.3.2  Heap類中的字段    344
11.3.3  Heap類的實現(xiàn)    344
11.3.4  percolateUp方法    345
11.3.5  percolateDown方法    349
11.4  應用：Huffman編碼    351
11.4.1  Huffman樹    353
11.4.2  貪婪算法    356
11.4.3  Huffman類    356
11.5  小結    361
11.6  練習    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  小結    391
12.6  練習    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  散列設計    406
13.3.4  hashCode方法    409
13.3.5  均勻散列假設    410
13.3.6  鏈    411
13.3.7  HashMap類的實現(xiàn)    412
13.3.8  鏈式散列分析    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  小結    432
13.7  練習    432
第14章  圖、樹和網(wǎng)絡    437
14.1  無向圖    437
14.2  有向圖    440
14.3  樹    441
14.4  網(wǎng)絡    442
14.5  圖的算法    443
14.5.1  迭代器    444
14.5.2  連通性    449
14.5.3  產(chǎn)生最小生成樹    450
14.5.4  在網(wǎng)絡中尋找最短路徑    454
14.6  開發(fā)Network類    457
14.6.1  Network類的方法描述    458
14.6.2  Network類的字段    460
14.6.3  實現(xiàn)Network類    462
14.6.4  Network類的另一種
設計和實現(xiàn)    469
14.7  突破網(wǎng)絡    471
14.8  小結    473
14.9  練習    474
附錄A  數(shù)學背景知識    481
A.1  簡介    481
A.2  函數(shù)和數(shù)列    481
A.3  求和與求積    482
A.4  對數(shù)    483
A.5  數(shù)學歸納法    485
A.6  練習    492
附錄B  GUI和GUIListener類    495
B.1  簡介    495
B.2  線程    496
B.3  實現(xiàn)Process接口    497
B.4  GUI類    499
B.4.1  GUI構造函數(shù)    500
B.4.2  GUI類中的其他方法    501
B.5  GUIListener類    502
B.6  綜合應用    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