數(shù)據(jù)結(jié)構(gòu)與算法（Java版）

第I部分  面向?qū)ο蟪绦蛟O(shè)計(jì)
第1章  封裝
1.1  軟件開(kāi)發(fā)    2
1.1.1  良好的程序    2
1.1.2  封裝    3
1.1.3  軟件開(kāi)發(fā)周期    5
習(xí)題    6
1.2  類(lèi)和對(duì)象    7
1.2.1  類(lèi)    7
1.2.2  對(duì)象、字段和方法    8
1.2.3  構(gòu)造函數(shù)    9
1.2.4  訪問(wèn)器、修改器和this    11
1.2.5  靜態(tài)與非靜態(tài)    12
1.2.6  完成Die類(lèi)    13
習(xí)題    14
1.3  使用對(duì)象    14
1.3.1  Beetle類(lèi)    14
1.3.2  toString()方法    15
1.3.3  BeetleGame類(lèi)    19
習(xí)題    24
1.4  小結(jié)    24
1.5  術(shù)語(yǔ)    25
1.6  復(fù)習(xí)題    26
1.7  項(xiàng)目    27
第2章  多態(tài)性
2.1  引用類(lèi)型    29
2.1.1  null    30
2.1.2  引用和相等性    30
2.1.3  多態(tài)類(lèi)型對(duì)象    31
2.1.4  基本類(lèi)型和包裝器    33
2.1.5  String    33
習(xí)題    34
2.2  數(shù)組    34
2.2.1  聲明、分配和初始化    34
2.2.2  多維數(shù)組    35
2.2.3  示例：Domineering    37
習(xí)題    42
2.3  接口    43
習(xí)題    47
2.4  重載    47
習(xí)題    48
2.5  小結(jié)    48
2.6  術(shù)語(yǔ)    49
2.7  復(fù)習(xí)題    50
2.8  項(xiàng)目    50
第3章  繼承
3.1  擴(kuò)展類(lèi)    53
3.1.1  多態(tài)性和繼承    55
3.1.2  繼承鏈    57
3.1.3  is-a和has-a    58
習(xí)題    60
3.2  Object類(lèi)    61
3.2.1  Object類(lèi)的方法    61
3.2.2  隱式構(gòu)造函數(shù)    62
習(xí)題    62
3.3  包和訪問(wèn)級(jí)別    63
訪問(wèn)級(jí)別    64
習(xí)題    65
3.4  小結(jié)    65
3.5  術(shù)語(yǔ)    66
3.6  復(fù)習(xí)題    66
3.7  項(xiàng)目    66
第Ⅱ部分  線 性 結(jié) 構(gòu)
第4章  棧和隊(duì)列
4.1  Stack接口    70
4.1.1  泛型    71
4.1.2  示例：Idiot's Delight    72
習(xí)題    77
4.2  調(diào)用棧    78
習(xí)題    80
4.3  異常    80
習(xí)題    86
4.4  Queue接口    86
習(xí)題    91
4.5  小結(jié)    91
4.6  術(shù)語(yǔ)    91
4.7  復(fù)習(xí)題    92
4.8  項(xiàng)目    93
第5章  基于數(shù)組的結(jié)構(gòu)
5.1  收縮和加長(zhǎng)數(shù)組    95
5.1.1  Card類(lèi)    96
5.1.2  收縮數(shù)組    97
5.1.3  加長(zhǎng)數(shù)組    100
習(xí)題    101
5.2  實(shí)現(xiàn)棧和隊(duì)列    101
5.2.1  ArrayStack類(lèi)    101
5.2.2  ArrayQueue類(lèi)    103
習(xí)題    105
5.3  List接口    106
5.3.1  接口    106
5.3.2  ArrayList類(lèi)    107
習(xí)題    110
5.4  迭代器    111
5.4.1  Iterator接口    111
5.4.2  Iterable接口    112
5.4.3  ArrayIterator類(lèi)    112
5.4.4  示例：Go Fish    114
習(xí)題    120
5.5  初識(shí)Java集合框架    121
抽象類(lèi)    121
習(xí)題    122
5.6  小結(jié)    123
5.7  術(shù)語(yǔ)    123
5.8  復(fù)習(xí)題    123
5.9  項(xiàng)目    124
第6章  鏈表結(jié)構(gòu)
6.1  表節(jié)點(diǎn)    125
習(xí)題    128
6.2  棧和隊(duì)列    128
6.2.1  LinkedStack類(lèi)    128
6.2.2  LinkedQueue類(lèi)    131
習(xí)題    133
6.3  LinkedList類(lèi)    134
6.3.1  Predecessor接口    136
6.3.2  兩指算法    138
6.3.3  ListIterator類(lèi)    139
習(xí)題    140
6.4  再論Java集合框架    141
習(xí)題    142
6.5  小結(jié)    142
6.6  術(shù)語(yǔ)    142
6.7  復(fù)習(xí)題    143
6.8  項(xiàng)目    143
第Ⅲ部分  算法
第7章  算法分析
7.1  計(jì)時(shí)    146
習(xí)題    148
7.2  漸近表示法    148
習(xí)題    152
7.3  統(tǒng)計(jì)步驟數(shù)    153
習(xí)題    157
7.4  最好、最壞和平均情況    157
習(xí)題    158
7.5  平攤分析    159
習(xí)題    160
7.6  小結(jié)    160
7.7  術(shù)語(yǔ)    161
7.8  復(fù)習(xí)題    161
7.9  項(xiàng)目    162
第8章  查找和排序
8.1  線性查找    163
習(xí)題    164
8.2  折半查找    164
8.2.1  折半查找分析    165
8.2.2  假定n是2的冪    166
習(xí)題    167
8.3  插入排序    167
習(xí)題    169
8.4  Comparable接口    170
習(xí)題    173
8.5  排序鏈表    173
習(xí)題    174
8.6  小結(jié)    174
8.7  術(shù)語(yǔ)    175
8.8  復(fù)習(xí)題    175
8.9  項(xiàng)目    176
第9章  遞歸
9.1  遞歸地思考    177
習(xí)題    183
9.2  分析遞歸算法    183
習(xí)題    186
9.3  歸并排序    186
歸并排序分析    189
習(xí)題    189
9.4  快速排序    190
快速排序分析    192
習(xí)題    193
9.5  避免遞歸    193
9.5.1  尾部遞歸    194
9.5.2  動(dòng)態(tài)規(guī)劃    195
習(xí)題    197
9.6  小結(jié)    197
9.7  術(shù)語(yǔ)    198
9.8  復(fù)習(xí)題    198
9.9  項(xiàng)目    200
第Ⅳ部分  樹(shù)和集合
第10章  樹(shù)
10.1  二叉樹(shù)    202
10.1.1  有關(guān)樹(shù)的術(shù)語(yǔ)    203
10.1.2  實(shí)現(xiàn)二叉樹(shù)    205
習(xí)題    208
10.2  樹(shù)的遍歷    210
習(xí)題    213
10.3  廣義樹(shù)    213
10.3.1  表示廣義樹(shù)    214
10.3.2  示例：智能的Tic Tac Toe玩家    215
習(xí)題    221
10.4  小結(jié)    221
10.5  術(shù)語(yǔ)    221
10.6  復(fù)習(xí)題    223
10.7  項(xiàng)目    223
第11章  集合
11.1  Set接口    224
習(xí)題    229
11.2  有序表    230
11.2.1  查找    232
11.2.2  插入    233
11.2.3  刪除    233
習(xí)題    234
11.3  二叉查找樹(shù)    234
11.3.1  查找    235
11.3.2  插入    236
11.3.3  刪除    238
習(xí)題    241
11.4  散列表    242
11.4.1  直接定址法    242
11.4.2  散列函數(shù)和散列碼    244
11.4.3  沖突解決方法    245
11.4.4  查找    248
11.4.5  插入    249
11.4.6  刪除    250
習(xí)題    250
11.5  再論Java集合框架    251
映射    252
習(xí)題    252
11.6  小結(jié)    253
11.7  術(shù)語(yǔ)    253
11.8  復(fù)習(xí)題    254
11.9  項(xiàng)目    255
第Ⅴ部分  高 級(jí) 主 題
第12章  高級(jí)線性結(jié)構(gòu)
12.1  位向量    258
BitSet    264
習(xí)題    264
12.2  稀疏數(shù)組    265
習(xí)題    267
12.3  多維數(shù)組的連續(xù)表示法    267
習(xí)題    271
12.4  高級(jí)查找和排序    271
12.4.1  插值查找    271
12.4.2  比較排序的下界    273
12.4.3  桶排序    273
習(xí)題    275
12.5  小結(jié)    275
12.6  術(shù)語(yǔ)    276
12.7  復(fù)習(xí)題    276
12.8  項(xiàng)目    276
第13章  字符串
13.1  String和StringBuilder    277
習(xí)題    280
13.2  字符串匹配    280
13.2.1  樸素的字符串匹配    282
13.2.2  RK指紋識(shí)別算法    283
13.2.3  KMP跳躍算法    285
習(xí)題    289
13.3  小結(jié)    289
13.4  術(shù)語(yǔ)    290
13.5  復(fù)習(xí)題    290
13.6  項(xiàng)目    291
第14章  高級(jí)主題
14.1  堆    292
14.1.1  優(yōu)先級(jí)隊(duì)列    294
14.1.2  堆排序    296
14.1.3  Java的PriorityQueue類(lèi)    297
習(xí)題    298
14.2  不相交集合簇    298
14.2.1  按高度合并    300
14.2.2  路徑壓縮    301
習(xí)題    302
14.3  數(shù)字查找樹(shù)    302
習(xí)題    308
14.4  紅黑樹(shù)    308
14.4.1  紅黑樹(shù)的性質(zhì)    308
14.4.2  查找    309
14.4.3  插入    309
14.4.4  刪除    311
14.4.5  實(shí)現(xiàn)    312
習(xí)題    320
14.5  小結(jié)    320
14.6  術(shù)語(yǔ)    321
14.7  復(fù)習(xí)題    321
14.8  項(xiàng)目    321
第15章  圖
15.1  術(shù)語(yǔ)    323
習(xí)題    327
15.2  表示法    327
習(xí)題    332
15.3  圖的遍歷    332
習(xí)題    334
15.4  拓?fù)渑判?nbsp;   335
習(xí)題    339
15.5  最短路徑    339
15.5.1  Dijkstra的單源點(diǎn)算法    340
15.5.2  Floyd-Warshall所有頂點(diǎn)對(duì)算法    341
習(xí)題    342
15.6  最小生成樹(shù)    342
習(xí)題    346
15.7  小結(jié)    346
15.8  術(shù)語(yǔ)    346
15.9  復(fù)習(xí)題    348
15.10  項(xiàng)目    348
第16章  內(nèi)存管理
16.1  顯式內(nèi)存管理    350
16.1.1  自由表    352
16.1.2  使用節(jié)點(diǎn)池    356
習(xí)題    358
16.2  自動(dòng)內(nèi)存管理    358
16.2.1  引用計(jì)數(shù)    358
16.2.2  標(biāo)記和清理無(wú)用單元收集    359
16.2.3  復(fù)制無(wú)用單元收集    359
習(xí)題    365
16.3  小結(jié)    366
16.4  術(shù)語(yǔ)    366
16.5  復(fù)習(xí)題    367
16.6  項(xiàng)目    367
第17章  輸出到磁盤(pán)
17.1  與文件交互    368
17.1.1  文本文件    368
17.1.2  數(shù)據(jù)文件    372
習(xí)題    376
17.2  壓縮    376
17.2.1  霍夫曼編碼方式    376
17.2.2  Lempel-Ziv編碼方式    381
習(xí)題    384
17.3  外部排序    384
習(xí)題    389
17.4  B樹(shù)    389
17.4.1  查找    390
17.4.2  插入    390
17.4.3  刪除    391
17.4.4  實(shí)現(xiàn)    392
習(xí)題    404
17.5  小結(jié)    405
17.6  術(shù)語(yǔ)    405
17.7  復(fù)習(xí)題    406
17.8  項(xiàng)目    406
第Ⅵ部分  附    錄
附錄A  Java知識(shí)回顧
A.1  第一個(gè)程序    408
A.2  變量和類(lèi)型    410
A.3  循環(huán)    412
A.4  與用戶交互    414
A.5  分支    414
A.6  方法和中斷    417
A.7  常量    418
A.8  運(yùn)算符    420
A.9  調(diào)試    423
A.10  編碼約定    424
附錄B  統(tǒng)一建模語(yǔ)言
B.1  類(lèi)圖    428
B.2  實(shí)例圖    431
附錄C  求和公式
C.1  求和符號(hào)    433
C.2  常量求和    434
C.3  前n個(gè)整數(shù)之和    434
C.4  二等分與加倍之和    435
C.5  函數(shù)之和的上限    435
C.6  常數(shù)因子    436
附錄D  進(jìn)一步的閱讀材料
D.1  數(shù)據(jù)結(jié)構(gòu)和算法    437
D.2  Java    437
D.3  游戲    437