本書是一本數(shù)據(jù)結構的教材，Java語言與數(shù)據(jù)結構兩條知識主線貫穿始終，這兩條主線既相互獨立又相互支撐。本書介紹了計算機編程中使用的數(shù)據(jù)結構和算法，包括29章，每章涉及一個ADT或其不同實現(xiàn)的規(guī)格說明和用法；書中貫穿9個Java插曲，涉及Java的高級特性。本書主要講述了組織數(shù)據(jù)、設計類、包、棧、遞歸、排序、隊列、雙端隊列、優(yōu)先隊列、線性表、有序表、查找、字典、散列、樹、二叉查找樹、堆、平衡查找樹、圖等內容，并對算法的效率進行了分析。本書非常適合作為大學本科生數(shù)據(jù)結構課程的教材，也可作為計算機研究與開發(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　實現(xiàn)一個接口 9
P.3.3　接口作為數(shù)據(jù)類型 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章　使用數(shù)組實現(xiàn)包 43
2.1　使用固定大小的數(shù)組實現(xiàn)ADT包 43
2.1.1　類比 43
2.1.2　一組核心方法 44
2.1.3　實現(xiàn)核心方法 45
2.1.4　讓實現(xiàn)安全 51
2.1.5　測試核心方法 54
2.1.6　實現(xiàn)更多的方法 56
2.1.7　刪除項的方法 58
2.2　使用可變大小的數(shù)組實現(xiàn)ADT包 65
2.2.1　可變大小數(shù)組 65
2.2.2　包的新實現(xiàn) 68
2.3　使用數(shù)組實現(xiàn)ADT包的優(yōu)缺點 70
Java插曲2　異常 75
第3章　使用鏈式數(shù)據(jù)實現(xiàn)包 82
3.1　鏈式數(shù)據(jù) 82
3.2　ADT包的鏈式實現(xiàn) 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　使用鏈實現(xiàn)ADT包的優(yōu)缺點 98
第4章　算法的效率 102
4.1　動機 102
4.2　測量算法的效率 103
4.2.1　計數(shù)基本操作 105
4.2.2　最優(yōu)、最差和平均情形 106
4.3　大O表示 107
4.4　描述效率 110
4.5　實現(xiàn)ADT包的效率 113
4.5.1　基于數(shù)組的實現(xiàn) 113
4.5.2　鏈式實現(xiàn) 114
4.5.3　兩種實現(xiàn)的比較 115
第5章　棧 121
5.1　ADT棧的規(guī)格說明 121
5.2　使用棧來處理代數(shù)表達式 125
5.2.1　問題求解：檢查中綴代數(shù)表達式中平衡的分隔符 125
5.2.2　問題求解：將中綴代數(shù)表達式轉換為后綴表達式 129
5.2.3　問題求解：計算后綴表達式的值 133
5.2.4　問題求解：計算中綴表達式的值 134
5.3　程序棧 136
5.4　Java類庫：類Stack 137
第6章　棧的實現(xiàn) 142
6.1　鏈式實現(xiàn) 142
6.2　基于數(shù)組的實現(xiàn) 144
6.3　基于向量的實現(xiàn) 148
6.3.1　Java類庫：類Vector 148
6.3.2　使用向量實現(xiàn)ADT棧 149
第7章　遞歸 154
7.1　什么是遞歸 154
7.2　跟蹤遞歸方法 158
7.3　返回一個值的遞歸方法 160
7.4　遞歸處理數(shù)組 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　對數(shù)組進行排序的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　歸并數(shù)組 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　實現(xiàn)快速排序 221
9.2.4　Java類庫中的快速排序 223
9.3　基數(shù)排序 223
9.3.1　基數(shù)排序的偽代碼 225
9.3.2　基數(shù)排序的效率 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)先隊列的實現(xiàn) 262
11.1　隊列的鏈式實現(xiàn) 262
11.2　基于數(shù)組實現(xiàn)隊列 265
11.2.1　循環(huán)數(shù)組 266
11.2.2　帶一個不用位置的循環(huán)數(shù)組 267
11.3　隊列的循環(huán)鏈式實現(xiàn) 272
11.4　Java類庫：類AbstractQueue 277
11.5　雙端隊列的雙向鏈式實現(xiàn) 2