本書是一本數(shù)據(jù)結(jié)構(gòu)的教材，Java語言與數(shù)據(jù)結(jié)構(gòu)兩條知識(shí)主線貫穿始終，這兩條主線既相互獨(dú)立又相互支撐。本書介紹了計(jì)算機(jī)編程中使用的數(shù)據(jù)結(jié)構(gòu)和算法，包括29章，每章涉及一個(gè)ADT或其不同實(shí)現(xiàn)的規(guī)格說明和用法；書中貫穿9個(gè)Java插曲，涉及Java的高級(jí)特性。本書主要講述了組織數(shù)據(jù)、設(shè)計(jì)類、包、棧、遞歸、排序、隊(duì)列、雙端隊(duì)列、優(yōu)先隊(duì)列、線性表、有序表、查找、字典、散列、樹、二叉查找樹、堆、平衡查找樹、圖等內(nèi)容，并對(duì)算法的效率進(jìn)行了分析。本書非常適合作為大學(xué)本科生數(shù)據(jù)結(jié)構(gòu)課程的教材，也可作為計(jì)算機(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　寫一個(gè)接口 8
P.3.2　實(shí)現(xiàn)一個(gè)接口 9
P.3.3　接口作為數(shù)據(jù)類型 11
P.3.4　派生一個(gè)接口 12
P.3.5　接口內(nèi)命名常量 13
P.4　選擇類 14
P.4.1　標(biāo)識(shí)類 15
P.4.2　CRC卡 15
P.4.3　統(tǒng)一建模語言 16
P.5　重用類 17
第1章　包 22
1.1　什么是包 22
1.2　說明一個(gè)包 23
1.3　使用ADT包 30
1.4　像使用自動(dòng)販賣機(jī)一樣使用ADT 33
1.5　ADT集合 34
1.6　Java類庫：接口Set 35
Java插曲1　泛型 39
第2章　使用數(shù)組實(shí)現(xiàn)包 43
2.1　使用固定大小的數(shù)組實(shí)現(xiàn)ADT包 43
2.1.1　類比 43
2.1.2　一組核心方法 44
2.1.3　實(shí)現(xiàn)核心方法 45
2.1.4　讓實(shí)現(xiàn)安全 51
2.1.5　測(cè)試核心方法 54
2.1.6　實(shí)現(xiàn)更多的方法 56
2.1.7　刪除項(xiàng)的方法 58
2.2　使用可變大小的數(shù)組實(shí)現(xiàn)ADT包 65
2.2.1　可變大小數(shù)組 65
2.2.2　包的新實(shí)現(xiàn) 68
2.3　使用數(shù)組實(shí)現(xiàn)ADT包的優(yōu)缺點(diǎn) 70
Java插曲2　異常 75
第3章　使用鏈?zhǔn)綌?shù)據(jù)實(shí)現(xiàn)包 82
3.1　鏈?zhǔn)綌?shù)據(jù) 82
3.2　ADT包的鏈?zhǔn)綄?shí)現(xiàn) 84
3.2.1　私有類Node 84
3.2.2　類LinkedBag的框架 85
3.2.3　定義一些核心方法 86
3.2.4　測(cè)試核心方法 89
3.2.5　方法getFrequencyOf 90
3.2.6　方法contains 91
3.3　從鏈中刪除一項(xiàng) 92
3.4　有設(shè)置和獲取方法的類Node 96
3.5　使用鏈實(shí)現(xiàn)ADT包的優(yōu)缺點(diǎn) 98
第4章　算法的效率 102
4.1　動(dòng)機(jī) 102
4.2　測(cè)量算法的效率 103
4.2.1　計(jì)數(shù)基本操作 105
4.2.2　最優(yōu)、最差和平均情形 106
4.3　大O表示 107
4.4　描述效率 110
4.5　實(shí)現(xiàn)ADT包的效率 113
4.5.1　基于數(shù)組的實(shí)現(xiàn) 113
4.5.2　鏈?zhǔn)綄?shí)現(xiàn) 114
4.5.3　兩種實(shí)現(xiàn)的比較 115
第5章　棧 121
5.1　ADT棧的規(guī)格說明 121
5.2　使用棧來處理代數(shù)表達(dá)式 125
5.2.1　問題求解：檢查中綴代數(shù)表達(dá)式中平衡的分隔符 125
5.2.2　問題求解：將中綴代數(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 129
5.2.3　問題求解：計(jì)算后綴表達(dá)式的值 133
5.2.4　問題求解：計(jì)算中綴表達(dá)式的值 134
5.3　程序棧 136
5.4　Java類庫：類Stack 137
第6章　棧的實(shí)現(xiàn) 142
6.1　鏈?zhǔn)綄?shí)現(xiàn) 142
6.2　基于數(shù)組的實(shí)現(xiàn) 144
6.3　基于向量的實(shí)現(xiàn) 148
6.3.1　Java類庫：類Vector 148
6.3.2　使用向量實(shí)現(xiàn)ADT棧 149
第7章　遞歸 154
7.1　什么是遞歸 154
7.2　跟蹤遞歸方法 158
7.3　返回一個(gè)值的遞歸方法 160
7.4　遞歸處理數(shù)組 162
7.5　遞歸處理鏈 165
7.6　遞歸方法的時(shí)間效率 166
7.6.1　countDown的時(shí)間效率 166
7.6.2　計(jì)算xn的時(shí)間效率 167
7.7　困難問題的簡單求解方案 168
7.8　簡單問題的低劣求解方案 172
7.9　尾遞歸 174
7.10　間接遞歸 176
7.11　使用棧來替代遞歸 177
Java插曲3　再談泛型 185
第8章　排序簡介 194
8.1　對(duì)數(shù)組進(jìn)行排序的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　鏈?zhǔn)浇Y(jié)點(diǎn)鏈的插入排序 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　實(shí)現(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章　隊(duì)列、雙端隊(duì)列和優(yōu)先隊(duì)列 238
10.1　ADT隊(duì)列 238
10.1.1　問題求解：模擬排隊(duì) 241
10.1.2　問題求解：計(jì)算出售股票的資本收益 246
10.1.3　Java類庫：接口Queue 248
10.2　ADT雙端隊(duì)列 249
10.2.1　問題求解：計(jì)算出售股票的資本收益 251
10.2.2　Java類庫：接口Deque 252
10.2.3　Java類庫：類ArrayDeque 253
10.3　ADT優(yōu)先隊(duì)列 254
10.3.1　問題求解：跟蹤任務(wù)分配 255
10.3.2　Java類庫：類PriorityQueue 257
第11章　隊(duì)列、雙端隊(duì)列和優(yōu)先隊(duì)列的實(shí)現(xiàn) 262
11.1　隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn) 262
11.2　基于數(shù)組實(shí)現(xiàn)隊(duì)列 265
11.2.1　循環(huán)數(shù)組 266
11.2.2　帶一個(gè)不用位置的循環(huán)數(shù)組 267
11.3　隊(duì)列的循環(huán)鏈?zhǔn)綄?shí)現(xiàn) 272
11.4　Java類庫：類AbstractQueue 277
11.5　雙端隊(duì)列的雙向鏈?zhǔn)綄?shí)現(xiàn) 2