數據結構（計算機科學與技術 Java版）

第1章  類與對象    1
1.1  本書內容    1
1.1.1  動態(tài)數組    1
1.1.2  鏈表    2
1.1.3  關聯數組    3
1.1.4  圖    4
1.1.5  適配器結構    4
1.1.6  數據結構與面向對象編程    5
1.1.7  數據結構與算法    5
1.2  面向對象編程    5
1.3  理解類的概念    7
1.4  Time24類    8
1.4.1  設計Time24類    8
1.4.2  構造函數    9
1.4.3  toString方法    10
1.4.4  Accessor和mutator方法    11
1.4.5  靜態(tài)方法    12
1.5  對象的聲明和使用    12
1.5.1  對象方法的使用    13
1.5.2  引用與別名    14
1.6  一個使用Time24對象的
應用程序    15
1.7  類的表示    16
1.8  類的實現    18
1.8.1  Time24類聲明    19
1.8.2  私有的工具方法    20
1.8.3  accessor與mutator方法    21
1.8.4  構造函數    22
1.8.5  格式化的對象描述    23
1.8.6  增加時間    23
1.8.7  時間間隔    23
1.9  類的構造    24
1.10  String類    26
1.10.1  串索引    27
1.10.2  串合并    27
1.10.3  串比較    28
1.11  枚舉類    29
1.12  總結    32
書面練習    33
編程練習    34
編程項目    36
第2章  類之間的關系    39
2.1  wrapper類    40
2.1.1  Integer對象的比較    40
2.1.2  靜態(tài)wrapper類成員    41
2.1.3  字符處理    42
2.2  自動裝箱與自動拆箱    43
2.3  對象組合    44
2.3.1  TimeCard類    45
2.3.2  TimeCard類的實現    46
2.3.3  TimeCard類的UML圖    47
2.4  Java中的繼承    47
2.4.1  一個雇員層次結構    48
2.4.2  繼承層次結構中成員的
可見性    49
2.4.3  Employee類的聲明    50
2.4.4  SalaryEmployee子類    51
2.4.5  繼承層次結構中的關鍵
字super    52
2.4.6  HourlyEmployee子類    53
2.5  多態(tài)性    55
2.6  抽象類    59
2.7  運行時錯誤的處理    60
2.7.1  throw語句    60
2.7.2  處理異常的try/catch
代碼塊    61
2.7.3  finally子句    62
2.7.4  異常傳播    63
2.7.5  Java異常的層次結構    63
2.7.6  標準的異常    65
2.8  輸入與輸出    65
2.8.1  控制臺I/O    66
2.8.2  文件I/O    67
2.8.3  使用Reader流的文本輸入    67
2.8.4  輸入串的分析    69
2.8.5  使用Writer流的文本輸出    71
2.8.6  輸出流的控制    72
2.9  Scanner類    73
2.9.1  聲明Scanner對象    73
2.9.2  輸入流的讀取    73
2.9.3  文件輸入    75
2.9.4  Scanner類API    75
2.9.5  應用程序：Scanner類
的使用    76
2.10  總結    79
書面練習    80
編程練習    83
編程項目    87
第3章  類的設計    89
3.1  Java接口    89
3.2  作為模板的接口    91
3.2.1  使用接口類型    92
3.2.2  接口與繼承    94
3.3  使用javadoc創(chuàng)建API    96
3.4  設計模式    99
3.5  GUI應用程序設計    100
3.5.1  圖形組件    101
3.5.2  GUI應用程序設計模式    102
3.5.3  事件偵聽器與事件處理
程序    105
3.5.4  骰子投擲動作事件    106
3.6  總結    107
書面練習    108
編程練習    108
編程項目    112
第4章  算法介紹    115
4.1  選擇排序    115
4.2  簡單的搜索算法    119
4.2.1  順序搜索    119
4.2.2  二叉搜索    121
4.3  算法的分析    126
4.3.1  系統(tǒng)/內存性能標準    126
4.3.2  算法性能：運行時間分析    126
4.3.3  Big-O符號    129
4.3.4  通用數量級    131
4.4  搜索算法的比較    133
4.5  總結    136
書面練習    136
編程練習    138
編程項目    141
第5章  泛型類與方法    143
5.1  Object超類    144
5.1.1  對象數組方法    145
5.1.2  通用的順序搜索    146
5.2  Java泛型介紹    147
5.2.1  基于Object的Store類    148
5.2.2  泛型集合    149
5.2.3  泛型Store類    150
5.3  泛型接口    151
5.4  泛型方法    155
5.4.1  基本的泛型方法    155
5.4.2  為泛型類型使用綁定    156
5.5  泛型與繼承    157
5.5.1  被綁定的泛型類型    158
5.5.2  泛型與通配符    160
5.6  泛型搜索/排序算法    161
5.7  總結    164
書面練習    165
編程練習    166
編程項目    168
第6章  遞歸    171
6.1  遞歸的概念    171
6.1.1  描述一個遞歸算法    173
6.1.2  遞歸方法的實現    173
6.1.3  遞歸的工作方式    175
6.1.4  多種基數表示法    176
6.2  遞歸的應用    179
6.2.1  構建一個刻度尺    179
6.2.2  Hanoi塔    181
6.3  遞歸的評價    185
6.3.1  Fibonacci方法    186
6.3.2  使用遞歸的標準    189
6.4  總結    189
書面練習    190
編程練習    192
編程項目    194
第7章  排序算法    195
7.1  插入排序    195
7.2  分治排序算法    198
7.2.1  歸并排序    198
7.2.2  通用的排序方法    201
7.2.3  msort()方法    202
7.2.4  歸并排序的效率    205
7.3  快速排序    206
7.3.1  使用基準值分割列表    206
7.3.2  快速排序遞歸下降    209
7.3.3  pivotIndex()方法    211
7.3.4  quicksort()方法    213
7.3.5  快速排序的運行時間    215
7.3.6  排序算法的比較    216
7.4  第k大元素的查找    219
7.5  總結    221
書面練習    222
編程練習    223
編程項目    225
第8章  集合類型    227
8.1  集合介紹    227
8.2  集合的概述    229
8.2.1  List集合    230
8.2.2  Set集合    232
8.2.3  Map集合    233
8.2.4  適配器集合    234
8.2.5  Graph集合    235
8.2.6  Java Collections Framework    236
8.3  Bag集合    237
8.3.1  創(chuàng)建和使用一個Bag集合    238
8.3.2  應用：Eratosthenes篩選法    240
8.4  Bag類的實現    243
8.4.1  私有的remove()方法    244
8.4.2  插入和訪問方法    245
8.4.3  集合的toString()方法    246
8.5  總結    246
書面練習    247
編程練習    248
編程項目    249
第9章  基于數組的列表集合    251
9.1  列表集合    251
9.2  ArrayList類    255
9.2.1  調整ArrayList的大小    257
9.2.2  ArrayList API    259
9.3  ArrayList應用程序    259
9.3.1  ArrayList的連接    259
9.3.2  closest-pair問題    262
9.4  實現ArrayList類    266
9.4.1  ArrayList類的設計    266
9.4.2  準備更大的容量    267
9.4.3  添加和刪除元素    268
9.4.4  實現索引訪問    272
9.5  Cloneable對象    273
9.5.1  克隆Time24對象    274
9.5.2  克隆引用變量    275
9.5.3  克隆ArrayList對象    277
9.5.4  克隆數組    279
9.6  ArrayList集合的評價    279
9.7  總結    280
書面練習    280
編程練習    282
編程項目    285
第10章  鏈表    287
10.1  單鏈表    289
10.1.1  創(chuàng)建鏈表    289
10.1.2  掃描鏈表    291
10.1.3  定位列表位置    291
10.1.4  更新列表頭    292
10.1.5  通用的插入和刪除操作    292
10.1.6  刪除目標節(jié)點    294
10.2  雙鏈表    298
10.3  LinkedList集合    299
10.3.1  LinkedList類    300
10.3.2  基于索引的LinkedList
方法    301
10.3.3  訪問列表尾    302
10.4  使用LinkedList集合的
應用程序    304
10.4.1  應用程序：選拔列表    304
10.4.2  應用程序：回文列表    307
10.5  總結    309
書面練習    310
編程練習    313
編程項目    318
第11章  實現LinkedList類    321
11.1  雙鏈表    321
11.1.1  DNode對象    322
11.1.2  使用DNode對象    323
11.2  循環(huán)雙鏈表    325
11.2.1  聲明雙鏈表    326
11.2.2  更新雙鏈表    327
11.2.3  應用程序：詞匯雜亂    330
11.3  實現LinkedList類    333
11.3.1  LinkedList類的私有
成員    333
11.3.2  LinkedList類的構造
函數    335
11.3.3  列表中基于索引的訪問    335
11.3.4  搜索列表    336
11.3.5  修改列表    337
11.4  總結    339
書面練習    339
編程練習    340
編程項目    342
第12章  迭代器    345
12.1  迭代器的概念    345
12.2  集合迭代器    346
12.2.1  迭代器掃描方法    347
12.2.2  通用的迭代器方法    350
12.2.3  使用增強的for語句
進行迭代    351
12.3  列表迭代器    352
12.3.1  ListIterator方法set()    353
12.3.2  列表的后向掃描    354
12.3.3  ListIterator方法add()    356
12.3.4  迭代器設計模式    357
12.4  迭代器的應用    358
12.4.1  有序列表    358
12.4.2  刪除有序列表中的
重復值    360
12.5  OrderedList集合    361
12.5.1  OrderedList類方法    362
12.5.2  應用程序：確定字頻    363
12.5.3  適配器設計模式    367
12.6  順序集合的選擇    367
12.7  總結    368
書面練習    369
編程練習    371
編程項目    373
第13章  迭代器的實現    375
13.1  迭代器實現設計    375
13.1.1  迭代器變量    376
13.1.2  迭代器接口方法    377
13.2  LinkedList迭代器    378
13.3  列表迭代器的實現    381
13.3.1  列表迭代器構造函數    381
13.3.2  列表迭代器的公共方法    382
13.4  快速失效迭代器    385
13.5  總結    386
書面練習    387
編程練習    388
編程項目    390
第14章  堆棧    391
14.1  堆棧集合    392
14.2  堆棧的應用    396
14.2.1  多種基數    397
14.2.2  符號對的平衡    400
14.3  遞歸與運行時堆棧    403
14.4  后綴表達式    405
14.4.1  后綴表達式的求解    406
14.4.2  PostfixEval類    408
14.4.3  evaluate()方法    410
14.5  中綴表達式的求解    412
14.5.1  中綴表達式屬性    412
14.5.2  中綴-后綴轉換    413
14.6  總結    416
書面練習    417
編程練習    419
編程項目    422
第15章  隊列與優(yōu)先隊列    425
15.1  Queue接口    426
15.1.1  創(chuàng)建一個隊列集合類    427
15.1.2  應用：隊列的調度    428
15.2  基數排序    430
15.3  有界隊列    436
15.3.1  BQueue類的設計實現    438
15.3.2  BQueue類的聲明    440
15.4  優(yōu)先隊列    441
15.4.1  優(yōu)先隊列接口    442
15.4.2  應用程序：支持服務庫    444
15.5  事件驅動的仿真    447
15.5.1  對銀行的仿真    447
15.5.2  仿真設計模式    449
15.5.3  BankSimulation類    451
15.6  總結    457
書面練習    457
編程練習    460
編程項目    463
第16章  二叉樹    465
16.1  樹結構    465
16.1.1  樹的相關術語    466
16.1.2  二叉樹    468
16.2  二叉樹節(jié)點    473
16.3  二叉樹掃描算法    477
16.3.1  遞歸樹遍歷    477
16.3.2  中序掃描算法    478
16.3.3  掃描方法的設計    480
16.3.4  迭代的層序掃描    482
16.3.5  Visitor設計模式    484
16.3.6  Visitor設計模式的使用    486
16.4  樹掃描算法的使用    489
16.4.1  樹高度的計算    489
16.4.2  復制二叉樹    491
16.4.3  清除樹    494
16.4.4  顯示二叉樹    495
16.5  排序的下界(選讀)    497
16.6  總結    499
書面練習    500
編程練習    503
編程項目    505
第17章  二叉樹的應用    507
17.1  表達式樹    507
17.2  迭代的樹遍歷    512
17.2.1  中序迭代遍歷    513
17.2.2  InorderIterator類的實現    515
17.3  Euler回路遍歷    518
17.4  繪制二叉樹    521
17.4.1  影像樹的構建    521
17.4.2  影像樹的顯示    523
17.5  總結    525
書面練習    526
編程練習    526
編程項目    529
第18章  二叉搜索樹    531
18.1  二叉搜索樹    531
18.1.1  構建二叉搜索樹    532
18.1.2  在二叉搜索樹中定位
對象    533
18.1.3  刪除二叉搜索樹節(jié)點    535
18.2  STree：一種二叉搜索樹類    536
18.3  STree類的實現    540
18.3.1  STree類的私有成員與
構造函數    541
18.3.2  插入和定位節(jié)點    542
18.3.3  刪除節(jié)點    544
18.3.4  其他操作    550
18.3.5  二叉搜索樹操作的
復雜度    551
18.4  STree迭代器    551
18.5  總結    556
書面練習    556
編程練習    558
編程項目    559
第19章  集與映射    561
19.1  集    563
19.1.1  TreeSet集合    563
19.1.2  簡單的拼寫檢查器    565
19.2  集運算符    568
19.2.1  集運算符的實現    569
19.2.2  應用程序：計算機賬號的
更新    572
19.2.3  使用有序集的操作    574
19.3  映射    577
19.3.1  Map接口    577
19.3.2  有序映射TreeMap    579
19.3.3  應用程序：一個學生時間
記錄映射    581
19.3.4  應用程序：計算機軟件
產品    583
19.4  映射集合視圖    586
19.4.1  鍵集集合視圖    586
19.4.2  條目集集合視圖    588
19.4.3  應用程序：構建詞匯
索引    591
19.5  總結    596
書面練習    596
編程練習    598
編程項目    602
第20章  有序集與映射的實現    603
20.1  TreeSet類的實現    603
20.2  TreeMap類的實現    604
20.2.1  TreeMap類的設計    607
20.2.2  使用鍵對條目進行訪問    608
20.2.3  更新條目    609
20.2.4  刪除條目    611
20.2.5  TreeSet和TreeMap類中
插入和刪除操作的
復雜度    611
20.3  集合視圖的實現    611
20.3.1  查看視圖    612
20.3.2  實現視圖    614
20.3.3  keySet集合視圖    615
20.4  總結    617
書面練習    617
編程練習    618
編程項目    621
第21章  實現映射的散列法    625
21.1  散列法    625
21.2  散列函數的設計    627
21.2.1  Java方法hashCode()    627
21.2.2  自定義的散列函數    629
21.3  散列表的設計    631
21.3.1  線性探查法    631
21.3.2  具有不同列表的拉鏈法    633
21.3.3  再散列    635
21.4  作為集合的散列表    636
21.5  Hash類的實現    637
21.5.1  Hash類的add()和
rehash()方法    639
21.5.2  Hash類的remove()方法    641
21.5.3  Hash類迭代器的實現    642
21.6  無序映射集合    645
21.6.1  訪問HashMap類中的
條目    646
21.6.2  更新HashMap類中的
條目    647
21.7  無序集集合    649
21.8  散列表的性能    650
21.9  總結    652
書面練習    653
編程練習    655
編程項目    657
第22章  堆    661
22.1  基于數組的二叉樹    661
22.2  Comparator接口    663
22.2.1  通用比較對象    664
22.2.2  通用的數組排序    665
22.3  堆    667
22.3.1  堆的插入操作    668
22.3.2  堆的刪除操作    670
22.3.3  堆的顯示    674
22.4  使用堆進行排序    676
22.4.1  堆的產生    676
22.4.2  堆排序    679
22.4.3  靜態(tài)堆方法概述    680
22.5  優(yōu)先隊列的實現    681
22.6  總結    684
書面練習    684
編程練習    687
編程項目    689
第23章  位數組與文件壓縮    691
23.1  位數組    691
23.1.1  BitArray類    694
23.1.2  BitArray類的實現    696
23.2  二進制文件    699
23.3  Huffman壓縮    703
23.3.1  Huffman樹的構建    707
23.3.2  Huffman壓縮的實現    708
23.3.3  Huffman解壓的實現    714
23.4  序列化    716
23.4.1  對象的序列化    717
23.4.2  使類可序列化    718
23.4.3  反序列化對象    718
23.4.4  應用程序：對象的
序列化    718
23.4.5  定制序列化    721
23.5  總結    723
書面練習    724
編程練習    728
編程項目    729
第24章  圖與路徑    731
24.1  圖的相關術語    731
24.1.1  有向圖    733
24.1.2  帶權圖    734
24.2  圖的創(chuàng)建和使用    735
24.2.1  Graph接口    735
24.2.2  DiGraph類    737
24.3  圖遍歷算法    741
24.3.1  廣度優(yōu)先搜索算法    741
24.3.2  深度優(yōu)先訪問算法    746
24.3.3  深度優(yōu)先搜索算法    751
24.3.4  無環(huán)圖    753
24.4  總結    755
書面練習    755
編程練習    758
編程項目    761
第25章  圖算法    763
25.1  拓撲排序    763
25.1.1  拓撲排序的目的    764
25.1.2  topologicalSort()方法
的實現    765
25.2  強連通組件    766
25.2.1 強連通組件算法的工作
原理    768
25.2.2  strongComponents()方法
的實現    769
25.3  圖最優(yōu)化算法    771
25.4  最短路徑算法    772
shortestPath()方法的實現    774
25.5  Dijkstra最小路徑算法    777
25.5.1  Dijkstra算法的設計    778
25.5.2  Dijkstra算法的工作
原理    781
25.5.3  minimumPath()方法的
實現    781
25.5.4  無環(huán)圖中的最小路徑    784
25.6  最小生成樹    787
25.6.1  Prim算法    788
25.6.2  minSpanTree()方法的
實現    790
25.7  總結    794
書面練習    794
編程練習    796
編程項目    798
第26章  圖的實現    799
26.1  圖的表示    799
26.2  DiGraph類的組件    800
26.2.1  頂點信息的表示    801
26.2.2  頂點映射與VertexInfo
數組列表    803
26.3  DiGraph類設計    806
26.4  DiGraph類方法    807
26.4.1  ArrayList的訪問    808
26.4.2  鄰接頂點的標識    808
26.4.3  入度和出度的求解    809
26.4.4  添加邊    809
26.4.5  刪除頂點    810
26.4.6  圖算法支持方法    813
26.4.7  圖集合視圖    814
26.5  總結    815
書面練習    816
編程練習    817
編程項目    819
第27章  平衡的搜索樹    821
27.1  AVL樹    822
27.2  AVLTree類的實現    824
27.2.1  AVLTree類的add()
方法    825
27.2.2  私有的addNode()方法    831
27.2.3  add()方法    832
27.3  2-3-4樹    835
27.3.1  2-3-4樹的搜索    836
27.3.2  2-3-4樹中的插入操作    836
27.4  紅-黑樹    839
27.4.1  2-3-4樹節(jié)點的表示    840
27.4.2  2-3-4樹的紅-黑樹表示    841
27.4.3  在紅-黑樹中插入節(jié)點    844
27.4.4  4-節(jié)點的分割    844
27.4.5  紅-黑樹底部的插入
操作    848
27.4.6  紅-黑樹的構建    849
27.4.7  紅-黑樹的搜索運行
時間    850
27.4.8  在紅-黑樹中刪除節(jié)點    851
27.5  RBTree類    852
27.6  總結    855
書面練習    855
編程練習    858
編程項目    859
第28章  數論與加密    861
28.1  基本的數論概念    861
28.1.1  Euclid GCD算法    862
28.1.2  模運算    863
28.1.3  Euler Φ函數    865
28.2  安全的消息傳輸    866
28.2.1  創(chuàng)建用于RSA加密的
密鑰    867
28.2.2  使用用于RSA加密的
密鑰    867
28.2.3  如何保護RSA通信    868
28.3  大整數的使用    868
28.4  RSA的客戶-服務器模式    872
28.5  RSA算法(選讀)    873
28.5.1  Euclid GCD算法的實現    873
28.5.2  RSA定理    876
28.6  總結    877
書面練習    878
編程練習    879
編程項目    880
第29章  雜類算法    881
29.1  組合學    881
29.1.1  組合的構建    882
29.1.2  查找所有子集    883
29.1.3  列出置換    885
29.1.4  旅行推銷員問題    888
29.1.5  置換與TSP    889
29.2  動態(tài)編程    889
29.2.1  由頂向下動態(tài)編程    890
29.2.2  使用動態(tài)編程的組合    893
29.2.3  由底向上動態(tài)編程    894
29.2.4  背包問題    896
29.2.5  Knapsack類    899
29.3  回溯：八皇后問題    903
29.3.1  問題分析    905
29.3.2  程序設計    907
29.3.3  顯示棋盤    911
29.4  總結    913
書面練習    914
編程練習    915
編程項目    920
附錄A  Java入門    923
A.1  Java程序的結構    923
A.1.1  注釋    924
A.1.2  關鍵字與標識符    925
A.1.3  變量的聲明和使用    925
A.1.4  控制臺輸出    925
A.2  Java編程環(huán)境    926
A.3  原始數據類型    927
A.3.1  數值類型    927
A.3.2  Java的char類型    929
A.3.3  命名常量的聲明    930
A.4  運算符    930
A.4.1  算術運算符    930
A.4.2  賦值運算符    931
A.4.3 復合賦值運算符    931
A.4.4  增量運算符    932
A.4.5  運算符的優(yōu)先順序    932
A.5  類型之間的轉換    933
A.6  選擇語句    935
A.6.1  if語句    937
A.6.2  嵌套的if語句    938
A.6.3  多路if/else語句    939
A.6.4  條件表達式運算符    939
A.6.5  switch語句    940
A.6.6  boolean類型    941
A.7  循環(huán)語句    942
A.7.1  while語句    942
A.7.2  do/while語句    943
A.7.3  for語句    944
A.7.4  break語句    945
A.8  數組    946
A.8.1  數組的初始化    947
A.8.2  使用增強的for語句
掃描數組    947
A.8.3  二維數組    948
A.9  Java的方法    949
A.9.1  預定義的方法    949
A.9.2  自定義的方法    951
A.9.3  作為方法參數的數組    953
附錄B  Java關鍵字    957
附錄C  ASCII字符編碼    959
附錄D  Java操作符的優(yōu)先順序    961
附錄E  EZJava集成開發(fā)環(huán)境    963
E.1  安裝EZJava    963
E.2  啟動EZJava    964
E.2.1  創(chuàng)建新文檔    965
E.2.2  菜單選項    966
E.3  程序的編譯和運行    966
E.4  項目的使用    968