《數據結構與抽象：Java語言描述（原書第4版）》是2017年機械工業出版社出版的圖書。
基本介紹
- 中文名：數據結構與抽象：Java語言描述（原書第4版）
- 出版時間：2017年6月
- 出版社：機械工業出版社
- ISBN：9787111567288
內容簡介,圖書目錄,
內容簡介
本書是一本數據結構的教材，Java語言與數據結構兩條知識主線貫穿始終，這兩條主線既相互獨立又相互支撐。本書介紹了計算機編程中使用的數據結構和算法，包括29章，每章涉及一個ADT或其不同實現的規格說明和用法；書中貫穿9個Java插曲，涉及Java的高級特性。本書主要講述了組織數據、設計類、包、棧、遞歸、排序、佇列、雙端佇列、優先佇列、線性表、有序表、查找、字典、散列、樹、二叉查找樹、堆、平衡查找樹、圖等內容，並對算法的效率進行了分析。本書非常適合作為大學本科生數據結構課程的教材，也可作為計算機研究與開發人員的參考書。
圖書目錄
Data Structures and Abstractions with Java, Fourth Edition
出版者的話
譯者序
前言
引言 組織數據 1
序言 設計類 3
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 統一建模語言 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包的優缺點 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包的優缺點 98
第4章 算法的效率 102
4.1 動機 102
4.2 測量算法的效率 103
4.2.1 計數基本操作 105
4.2.2 、差和平均情形 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棧的規格說明 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 創建劃分 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章 佇列、雙端佇列和優先佇列 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優先佇列 254
10.3.1 問題求解：跟蹤任務分配 255
10.3.2 Java類庫：類PriorityQueue 257
第11章 佇列、雙端佇列和優先佇列的實現 262
11.1 佇列的鏈式實現 262
11.2 基於數組實現佇列 265
11.2.1 循環數組 266
11.2.2 帶一個不用位置的循環數組 267
11.3 佇列的循環鏈式實現 272
11.4 Java類庫：類AbstractQueue 277
11.5 雙端佇列的雙向鏈式實現 2
