本書是一本數據結構的教材，Java語言與數據結構兩條知識主線貫穿始終，這兩條主線既相互獨立又相互支撐。本書介紹了計算機編程中使用的數據結構和算法，包括29章，每章涉及一個ADT或其不同實現的規(guī)格說明和用法；書中貫穿9個Java插曲，涉及Java的高級特性。本書主要講述了組織數據、設計類、包、棧、遞歸、排序、隊列、雙端隊列、優(yōu)先隊列、線性表、有序表、查找、字典、散列、樹、二叉查找樹、堆、平衡查找樹、圖等內容，并對算法的效率進行了分析。本書非常適合作為大學本科生數據結構課程的教材，也可作為計算機研究與開發(fā)人員的參考書。

目錄：
 

P.1　封裝 3
P.2　說明方法 5
P.2.1　注釋 5
P.2.2　前置條件和后置條件 5
P.2.3　斷言 6
P.3　Java接口 7
P.3.1　寫一個接口 8
P.3.2　實現一個接口 9
P.3.3　接口作為數據類型 11
P.3.4　派生一個接口 12
P.3.5　接口內命名常量 13
P.4　選擇類 14
P.4.1　標識類 15
P.4.2　CRC卡 15
P.4.3　統(tǒng)一建模語言 16
P.5　重用類 17
第1章　包 22
1.1　什么是包 22
1.2　說明一個包 23
1.3　使用ADT包 30
1.4　像使用自動販賣機一樣使用ADT 33
1.5　ADT集合 34
1.6　Java類庫：接口Set 35
Java插曲1　泛型 39
第2章　使用數組實現包 43
2.1　使用固定大小的數組實現ADT包 43
2.1.1　類比 43
2.1.2　一組核心方法 44
2.1.3　實現核心方法 45
2.1.4　讓實現安全 51
2.1.5　測試核心方法 54
2.1.6　實現更多的方法 56
2.1.7　刪除項的方法 58
2.2　使用可變大小的數組實現ADT包 65
2.2.1　可變大小數組 65
2.2.2　包的新實現 68
2.3　使用數組實現ADT包的優(yōu)缺點 70
Java插曲2　異常 75
第3章　使用鏈式數據實現包 82
3.1　鏈式數據 82
3.2　ADT包的鏈式實現 84
3.2.1　私有類Node 84
3.2.2　類LinkedBag的框架 85
3.2.3　定義一些核心方法 86
3.2.4　測試核心方法 89
3.2.5　方法getFrequencyOf 90
3.2.6　方法contains 91
3.3　從鏈中刪除一項 92
3.4　有設置和獲取方法的類Node 96
3.5　使用鏈實現ADT包的優(yōu)缺點 98
第4章　算法的效率 102
4.1　動機 102
4.2　測量算法的效率 103
4.2.1　計數基本操作 105
4.2.2　最優(yōu)、最差和平均情形 106
4.3　大O表示 107
4.4　描述效率 110
4.5　實現ADT包的效率 113
4.5.1　基于數組的實現 113
4.5.2　鏈式實現 114
4.5.3　兩種實現的比較 115
第5章　棧 121
5.1　ADT棧的規(guī)格說明 121
5.2　使用棧來處理代數表達式 125
5.2.1　問題求解：檢查中綴代數表達式中平衡的分隔符 125
5.2.2　問題求解：將中綴代數表達式轉換為后綴表達式 129
5.2.3　問題求解：計算后綴表達式的值 133
5.2.4　問題求解：計算中綴表達式的值 134
5.3　程序棧 136
5.4　Java類庫：類Stack 137
第6章　棧的實現 142
6.1　鏈式實現 142
6.2　基于數組的實現 144
6.3　基于向量的實現 148
6.3.1　Java類庫：類Vector 148
6.3.2　使用向量實現ADT棧 149
第7章　遞歸 154
7.1　什么是遞歸 154
7.2　跟蹤遞歸方法 158
7.3　返回一個值的遞歸方法 160
7.4　遞歸處理數組 162
7.5　遞歸處理鏈 165
7.6　遞歸方法的時間效率 166
7.6.1　countDown的時間效率 166
7.6.2　計算xn的時間效率 167
7.7　困難問題的簡單求解方案 168
7.8　簡單問題的低劣求解方案 172
7.9　尾遞歸 174
7.10　間接遞歸 176
7.11　使用棧來替代遞歸 177
Java插曲3　再談泛型 185
第8章　排序簡介 194
8.1　對數組進行排序的Java方法的組織 194
8.2　選擇排序 195
8.2.1　迭代選擇排序 196
8.2.2　遞歸選擇排序 198
8.2.3　選擇排序的效率 198
8.3　插入排序 199
8.3.1　迭代插入排序 199
8.3.2　遞歸插入排序 201
8.3.3　插入排序的效率 202
8.3.4　鏈式結點鏈的插入排序 203
8.4　希爾排序 205
8.4.1　算法 206
8.4.2　希爾排序的效率 207
8.5　算法比較 208
第9章　更快的排序方法 213
9.1　歸并排序 213
9.1.1　歸并數組 213
9.1.2　遞歸歸并排序 214
9.1.3　歸并排序的效率 216
9.1.4　迭代歸并排序 217
9.1.5　Java類庫中的歸并排序 218
9.2　快速排序 218
9.2.1　快速排序的效率 219
9.2.2　創(chuàng)建劃分 219
9.2.3　實現快速排序 221
9.2.4　Java類庫中的快速排序 223
9.3　基數排序 223
9.3.1　基數排序的偽代碼 225
9.3.2　基數排序的效率 225
9.4　算法比較 226
Java插曲4　再談異常 231
第10章　隊列、雙端隊列和優(yōu)先隊列 238
10.1　ADT隊列 238
10.1.1　問題求解：模擬排隊 241
10.1.2　問題求解：計算出售股票的資本收益 246
10.1.3　Java類庫：接口Queue 248
10.2　ADT雙端隊列 249
10.2.1　問題求解：計算出售股票的資本收益 251
10.2.2　Java類庫：接口Deque 252
10.2.3　Java類庫：類ArrayDeque 253
10.3　ADT優(yōu)先隊列 254
10.3.1　問題求解：跟蹤任務分配 255
10.3.2　Java類庫：類PriorityQueue 257
第11章　隊列、雙端隊列和優(yōu)先隊列的實現 262
11.1　隊列的鏈式實現 262
11.2　基于數組實現隊列 265
11.2.1　循環(huán)數組 266
11.2.2　帶一個不用位置的循環(huán)數組 267
11.3　隊列的循環(huán)鏈式實現 272
11.4　Java類庫：類AbstractQueue 277
11.5　雙端隊列的雙向鏈式實現 2