數據結構與Java集合框架

第1章  Java語言的重要特性    1
1.1  類        1
1.1.1  方法描述    2
1.1.2  數據抽象    4
1.1.3  Employee類    6
1.1.4  局部變量和字段    8
1.1.5  構造函數    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  繼承和構造函數    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  數組    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  數據結構和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  程序實現    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章  數組列表    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  實現ArrayList類    130
5.3.1  定義add方法    131
5.3.2  分攤時間    133
5.3.3  clone方法和copy構造函數    134
5.3.4  Fail-Fast 迭代器    135
5.4  高精度算法    136
5.4.1  設計VeryLongInt類    137
5.4.2  實現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類的字段和
實現方法    158
6.1.4  ListItr類的字段和實現    164
6.1.5  LinkedList類的其他設計
和實現方法    167
6.1.6  循環(huán)鏈表    169
6.2  行編輯器    171
6.2.1  設計Editor類    174
6.2.2  實現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類的設計與實現    188
7.1.2  Queue類可選擇的設計和實現    190
7.2  計算機模擬    194
7.3  應用：模擬洗車    195
7.3.1  CarWash類的設計    196
7.3.2  CarWash類的實現    197
7.3.3  CarWash方法分析    200
7.3.4  隨機到達時間    200
7.4  堆棧    201
7.4.1  Stack類的設計和實現    202
7.4.2  Java集合框架中的Stack類    202
7.4.3  Stack類可選的設計和實現    203
7.5  應用：如何編譯實現遞歸    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類的字段
及內置類    243
8.2.3  BinSearchTree類的實現    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類的實現    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類的設計和實現    319
10.2.2  ThesaurusDriver類的
設計和實現    320
10.3  TreeSet類    322
10.4  一個簡單的拼寫檢查器    326
10.4.1  SpellChecker類的設計
和實現    327
10.4.2  SpellCheckerDriver類
的設計與實現    328
10.5  小結    330
10.6  練習    331
第11章  優(yōu)先級隊列    337
11.1  簡介    337
11.2  PriorityQueue接口的定義    338
11.3  PriorityQueue接口的實現    339
11.3.1  Heap類    340
11.3.2  Heap類中的字段    344
11.3.3  Heap類的實現    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類的實現    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章  圖、樹和網絡    437
14.1  無向圖    437
14.2  有向圖    440
14.3  樹    441
14.4  網絡    442
14.5  圖的算法    443
14.5.1  迭代器    444
14.5.2  連通性    449
14.5.3  產生最小生成樹    450
14.5.4  在網絡中尋找最短路徑    454
14.6  開發(fā)Network類    457
14.6.1  Network類的方法描述    458
14.6.2  Network類的字段    460
14.6.3  實現Network類    462
14.6.4  Network類的另一種
設計和實現    469
14.7  突破網絡    471
14.8  小結    473
14.9  練習    474
附錄A  數學背景知識    481
A.1  簡介    481
A.2  函數和數列    481
A.3  求和與求積    482
A.4  對數    483
A.5  數學歸納法    485
A.6  練習    492
附錄B  GUI和GUIListener類    495
B.1  簡介    495
B.2  線程    496
B.3  實現Process接口    497
B.4  GUI類    499
B.4.1  GUI構造函數    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