滿額折
商品簡介
目次
商品簡介
本書是為“數據結構”課程編寫的教材，前面兩章介紹數學基礎和算法相關預備知識，第3章至第10章介紹常見數據結構的抽象數據類型、算法實現、性能分析及其應用。本書注重全面運用數據結構知識解決實際問題的案例介紹，同時穿插程序設計的技巧。全書採用Java語言作為數據結構和算法的描述語言，介紹JDK中常見的數據結構的實現原理，如ArrayList、LinkedList、HashMap等，對於高效使用這些對象，提高程序性能有指導意義，特別適合Java語言的進階學習者。本書提供了大量設計精良的代碼，且不乏對算法背後所蘊含數學原理的精彩介紹，使讀者不僅能夠編寫出高效、精緻的程序，而且達到“知其然，也知其所以然”的效果。
目次
目錄
前言 i
第1章 緒論 1
1.1 幾個實際問題 1
1.1.1 學生成績表管理 1
1.1.2 人機對弈 2
1.1.3 路徑導航 3
1.2 本書主要討論內容 3
1.2.1 數據結構的主要內容 3
1.2.2 學習數據結構的意義 4
1.3 數學知識複習 5
1.3.1 指數 5
1.3.2 對數 5
1.3.3 級數 6
1.3.4 模運算 8
1.3.5 證明方法 8
1.4 總結 10
第2章 算法分析 11
2.1 數學基礎 11
2.2 模型 13
2.3 要分析的問題 14
2.4 算法的運行時間計算 17
2.4.1 一個簡單的例子 17
2.4.2 一般法則 18
2.4.3 大子序列和問題的解 21
2.4.4 運行時間中的對數 27
2.4.5 檢驗結果 30
2.4.6 分析結果的準確性 31
2.4.7 算法的存儲空間計算 32
2.5 總結 32
第3章 線性表 34
3.1 抽象數據類型 34
3.2 線性表的邏輯特性 35
3.2.1 定義 35
3.2.2 特徵 35
3.2.3 運算 35
3.3 順序表及其實現 36
3.3.1 順序表 36
3.3.2 表的簡單數組實現 36
3.3.3 ArrayList 的實現 37
3.4 鏈表及其實現 47
3.4.1 鏈表的思想 47
3.4.2 單向鏈表 47
3.4.3 單向鏈表ADT 49
3.4.4 常見的錯誤 56
3.4.5 模塊化設計 56
3.4.6 雙向鏈表 57
3.4.7 循環鏈表 61
3.5 鏈表應用實例 62
3.5.1 一元多項式 62
3.5.2 音樂播放列表排序 67
3.5.3 多重表 70
3.6 總結 71
第4章 棧和隊列 72
4.1 棧 72
4.1.1 棧的定義 72
4.1.2 棧ADT 73
4.1.3 棧的順序表示 73
4.1.4 棧的鏈接表示 76
4.2 表達式計算 78
4.2.1 表達式 78
4.2.2 計算後綴表達式的值 78
4.2.3 中綴表達式轉換為後綴表達式 80
4.2.4 利用兩個棧計算表達式 81
4.3 遞歸 86
4.3.1 遞歸的概念 86
4.3.2 遞歸的實現 91
4.4 隊列 92
4.4.1 隊列ADT 92
4.4.2 隊列的數組實現 93
4.4.3 隊列數組實現的改進 96
4.4.4 循環隊列 96
4.4.5 循環隊列的應用 99
4.4.6 隊列的鏈接表示 99
4.4.7 舞伴問題 101
4.5 總結 103
第5章 矩陣 104
5.1 矩陣的二維數組存儲 104
5.2 特殊矩陣的壓縮存儲 107
5.2.1 稠密矩陣和稀疏矩陣 107
5.2.2 對稱矩陣 107
5.2.3 三角矩陣 108
5.2.4 帶狀矩陣 110
5.3 稀疏矩陣的壓縮存儲 111
5.3.1 三元組順序表存儲 112
5.3.2 行邏輯鏈接的順序存儲 116
5.3.3 十字鏈表 121
5.3.4 稀疏矩陣的並行運算 129
5.4 總結 130
第6章 查找和散列表 131
6.1 查找方法 131
6.1.1 順序表的查找 131
6.1.2 有序表的查找 133
6.1.3 索引順序表的查找 138
6.1.4 散列表的查找 139
6.2 散列表 140
6.2.1 基本思想 140
6.2.2 構造散列函數的原則 141
6.3 常見散列函數 141
6.3.1 直接定址法 141
6.3.2 數字分析法 142
6.3.3 平方取中法 142
6.3.4 折疊法 143
6.3.5 除留餘數法 143
6.4 解決散列函數衝突的方法 144
6.4.1 拉鍊法 144
6.4.2 開放定址法 145
6.4.3 裝填因子 148
6.4.4 再散列 148
6.5 散列表的查找 150
6.5.1 散列表的實現 150
6.5.2 性能分析 162
6.5.3 散列表的改進 162
6.6 總結 163
第7章 排序 164
7.1 基本概念 164
7.2 插入排序 165
7.2.1 直接插入排序 165
7.2.2 對直接插入排序的分析 167
7.2.3 希爾排序 168
7.2.4 對希爾排序的分析 170
7.3 交換排序 170
7.3.1 冒泡排序 171
7.3.2 對冒泡排序的分析 172
7.3.3 快速排序 173
7.3.4 實際的快速排序程序 175
7.3.5 對快速排序的分析 176
7.4 選擇排序 177
7.4.1 算法實現 177
7.4.2 效率分析 178
7.5 歸併排序 178
7.5.1 二路歸併排序 178
7.5.2 對歸併排序的分析 181
7.6 基數排序 182
7.6.1 多關鍵字的排序 182
7.6.2 鏈式基數排序 183
7.6.3 對基數排序的分析 185
7.7 外部排序 188
7.7.1 外部排序的概念 188
7.7.2 簡單算法 189
7.7.3 多路合併 190
7.7.4 多相合併 192
7.7.5 替換選擇 193
7.8 ArrayList與LinkedList中的排序方法 194
7.8.1 ArrayList中的排序方法 195
7.8.2 LinkedList中的排序方法 201
7.9 總結 203
第8章 樹 205
8.1 樹的基礎知識 205
8.1.1 基本術語 205
8.1.2 樹的ADT 207
8.1.3 樹的表示 209
8.1.4 樹的實現 210
8.2 樹的遍歷 211
8.2.1 前序遍歷 211
8.2.2 後序遍歷 213
8.3 二叉樹 215
8.3.1 二叉樹基本概念 215
8.3.2 二叉樹的性質 219
8.3.3 二叉樹的實現 220
8.3.4 二叉樹的遍歷方法以及非遞歸實現 223
8.3.5 表達式樹 230
8.3.6 哈夫曼樹 240
8.3.7 決策樹 247
8.4 二叉查找樹 251
8.4.1 二叉查找樹的概念 251
8.4.2 查找操作 252
8.4.3 插入操作 254
8.4.4 刪除操作 255
8.4.5 性能分析 258
8.5 二叉平衡樹 260
8.5.1 二叉平衡樹的概念 260
8.5.2 平衡化策略 262
8.5.3 平衡樹的實現 268
8.6 其他一些樹 276
8.6.1 伸展樹 276
8.6.2 B-樹 277
8.6.3 紅黑樹的概念 283
8.6.4 紅黑樹的實現 284
8.7 總結 293
第9章 優先隊列(堆) 295
9.1 基本概念和簡單實現 295
9.2 二叉堆 296
9.2.1 堆ADT 298
9.2.2 基本的堆操作 298
9.3 d-堆 311
9.4 左式堆 312
9.4.1 左式堆的性質 312
9.4.2 左式堆的操作 313
9.5 斜堆 320
9.6 二項隊列 321
9.6.1 二項隊列的結構 322
9.6.2 二項隊列的操作 323
9.6.3 二項隊列的實現 325
9.7 優先隊列的應用 331
9.7.1 堆排序 331
9.7.2 選擇問題 334
9.7.3 事件模擬 335
9.8 總結 336
第10章 圖論算法 337
10.1 圖的基本概念 337
10.1.1 定義與術語 338
10.1.2 圖ADT 341
10.2 圖的存儲 341
10.2.1 矩陣表示法 341
10.2.2 鄰接矩陣表示法的實現 343
10.2.3 鄰接表表示法 346
10.2.4 鄰接表表示法的實現 346
10.2.5 Java開源庫JGraphT中對圖的存儲方法 349
10.3 圖的遍歷 350
10.3.1 廣度優先遍歷 350
10.3.2 深度優先遍歷 353
10.3.3 圖的連通性 356
10.4 拓撲排序 359
10.4.1 AOV網絡 359
10.4.2 拓撲排序的概念 360
10.4.3 拓撲排序算法及其實現 361
10.5 關鍵路徑 365
10.5.1 AOE網絡 365
10.5.2 關鍵路徑的概念 366
10.5.3 關鍵路徑算法及其實現 368
10.6 小生成樹 371
10.6.1 小生成樹的概念 371
10.6.2 Prim算法 373
10.6.3 Kruskal算法 378
10.7 短路徑問題 381
10.7.1 問題描述 382
10.7.2 Dijkstra算法 383
10.7.3 Floyd算法 392
10.8 總結 396
參考文獻 398
附錄 399
前言 i
第1章 緒論 1
1.1 幾個實際問題 1
1.1.1 學生成績表管理 1
1.1.2 人機對弈 2
1.1.3 路徑導航 3
1.2 本書主要討論內容 3
1.2.1 數據結構的主要內容 3
1.2.2 學習數據結構的意義 4
1.3 數學知識複習 5
1.3.1 指數 5
1.3.2 對數 5
1.3.3 級數 6
1.3.4 模運算 8
1.3.5 證明方法 8
1.4 總結 10
第2章 算法分析 11
2.1 數學基礎 11
2.2 模型 13
2.3 要分析的問題 14
2.4 算法的運行時間計算 17
2.4.1 一個簡單的例子 17
2.4.2 一般法則 18
2.4.3 大子序列和問題的解 21
2.4.4 運行時間中的對數 27
2.4.5 檢驗結果 30
2.4.6 分析結果的準確性 31
2.4.7 算法的存儲空間計算 32
2.5 總結 32
第3章 線性表 34
3.1 抽象數據類型 34
3.2 線性表的邏輯特性 35
3.2.1 定義 35
3.2.2 特徵 35
3.2.3 運算 35
3.3 順序表及其實現 36
3.3.1 順序表 36
3.3.2 表的簡單數組實現 36
3.3.3 ArrayList 的實現 37
3.4 鏈表及其實現 47
3.4.1 鏈表的思想 47
3.4.2 單向鏈表 47
3.4.3 單向鏈表ADT 49
3.4.4 常見的錯誤 56
3.4.5 模塊化設計 56
3.4.6 雙向鏈表 57
3.4.7 循環鏈表 61
3.5 鏈表應用實例 62
3.5.1 一元多項式 62
3.5.2 音樂播放列表排序 67
3.5.3 多重表 70
3.6 總結 71
第4章 棧和隊列 72
4.1 棧 72
4.1.1 棧的定義 72
4.1.2 棧ADT 73
4.1.3 棧的順序表示 73
4.1.4 棧的鏈接表示 76
4.2 表達式計算 78
4.2.1 表達式 78
4.2.2 計算後綴表達式的值 78
4.2.3 中綴表達式轉換為後綴表達式 80
4.2.4 利用兩個棧計算表達式 81
4.3 遞歸 86
4.3.1 遞歸的概念 86
4.3.2 遞歸的實現 91
4.4 隊列 92
4.4.1 隊列ADT 92
4.4.2 隊列的數組實現 93
4.4.3 隊列數組實現的改進 96
4.4.4 循環隊列 96
4.4.5 循環隊列的應用 99
4.4.6 隊列的鏈接表示 99
4.4.7 舞伴問題 101
4.5 總結 103
第5章 矩陣 104
5.1 矩陣的二維數組存儲 104
5.2 特殊矩陣的壓縮存儲 107
5.2.1 稠密矩陣和稀疏矩陣 107
5.2.2 對稱矩陣 107
5.2.3 三角矩陣 108
5.2.4 帶狀矩陣 110
5.3 稀疏矩陣的壓縮存儲 111
5.3.1 三元組順序表存儲 112
5.3.2 行邏輯鏈接的順序存儲 116
5.3.3 十字鏈表 121
5.3.4 稀疏矩陣的並行運算 129
5.4 總結 130
第6章 查找和散列表 131
6.1 查找方法 131
6.1.1 順序表的查找 131
6.1.2 有序表的查找 133
6.1.3 索引順序表的查找 138
6.1.4 散列表的查找 139
6.2 散列表 140
6.2.1 基本思想 140
6.2.2 構造散列函數的原則 141
6.3 常見散列函數 141
6.3.1 直接定址法 141
6.3.2 數字分析法 142
6.3.3 平方取中法 142
6.3.4 折疊法 143
6.3.5 除留餘數法 143
6.4 解決散列函數衝突的方法 144
6.4.1 拉鍊法 144
6.4.2 開放定址法 145
6.4.3 裝填因子 148
6.4.4 再散列 148
6.5 散列表的查找 150
6.5.1 散列表的實現 150
6.5.2 性能分析 162
6.5.3 散列表的改進 162
6.6 總結 163
第7章 排序 164
7.1 基本概念 164
7.2 插入排序 165
7.2.1 直接插入排序 165
7.2.2 對直接插入排序的分析 167
7.2.3 希爾排序 168
7.2.4 對希爾排序的分析 170
7.3 交換排序 170
7.3.1 冒泡排序 171
7.3.2 對冒泡排序的分析 172
7.3.3 快速排序 173
7.3.4 實際的快速排序程序 175
7.3.5 對快速排序的分析 176
7.4 選擇排序 177
7.4.1 算法實現 177
7.4.2 效率分析 178
7.5 歸併排序 178
7.5.1 二路歸併排序 178
7.5.2 對歸併排序的分析 181
7.6 基數排序 182
7.6.1 多關鍵字的排序 182
7.6.2 鏈式基數排序 183
7.6.3 對基數排序的分析 185
7.7 外部排序 188
7.7.1 外部排序的概念 188
7.7.2 簡單算法 189
7.7.3 多路合併 190
7.7.4 多相合併 192
7.7.5 替換選擇 193
7.8 ArrayList與LinkedList中的排序方法 194
7.8.1 ArrayList中的排序方法 195
7.8.2 LinkedList中的排序方法 201
7.9 總結 203
第8章 樹 205
8.1 樹的基礎知識 205
8.1.1 基本術語 205
8.1.2 樹的ADT 207
8.1.3 樹的表示 209
8.1.4 樹的實現 210
8.2 樹的遍歷 211
8.2.1 前序遍歷 211
8.2.2 後序遍歷 213
8.3 二叉樹 215
8.3.1 二叉樹基本概念 215
8.3.2 二叉樹的性質 219
8.3.3 二叉樹的實現 220
8.3.4 二叉樹的遍歷方法以及非遞歸實現 223
8.3.5 表達式樹 230
8.3.6 哈夫曼樹 240
8.3.7 決策樹 247
8.4 二叉查找樹 251
8.4.1 二叉查找樹的概念 251
8.4.2 查找操作 252
8.4.3 插入操作 254
8.4.4 刪除操作 255
8.4.5 性能分析 258
8.5 二叉平衡樹 260
8.5.1 二叉平衡樹的概念 260
8.5.2 平衡化策略 262
8.5.3 平衡樹的實現 268
8.6 其他一些樹 276
8.6.1 伸展樹 276
8.6.2 B-樹 277
8.6.3 紅黑樹的概念 283
8.6.4 紅黑樹的實現 284
8.7 總結 293
第9章 優先隊列(堆) 295
9.1 基本概念和簡單實現 295
9.2 二叉堆 296
9.2.1 堆ADT 298
9.2.2 基本的堆操作 298
9.3 d-堆 311
9.4 左式堆 312
9.4.1 左式堆的性質 312
9.4.2 左式堆的操作 313
9.5 斜堆 320
9.6 二項隊列 321
9.6.1 二項隊列的結構 322
9.6.2 二項隊列的操作 323
9.6.3 二項隊列的實現 325
9.7 優先隊列的應用 331
9.7.1 堆排序 331
9.7.2 選擇問題 334
9.7.3 事件模擬 335
9.8 總結 336
第10章 圖論算法 337
10.1 圖的基本概念 337
10.1.1 定義與術語 338
10.1.2 圖ADT 341
10.2 圖的存儲 341
10.2.1 矩陣表示法 341
10.2.2 鄰接矩陣表示法的實現 343
10.2.3 鄰接表表示法 346
10.2.4 鄰接表表示法的實現 346
10.2.5 Java開源庫JGraphT中對圖的存儲方法 349
10.3 圖的遍歷 350
10.3.1 廣度優先遍歷 350
10.3.2 深度優先遍歷 353
10.3.3 圖的連通性 356
10.4 拓撲排序 359
10.4.1 AOV網絡 359
10.4.2 拓撲排序的概念 360
10.4.3 拓撲排序算法及其實現 361
10.5 關鍵路徑 365
10.5.1 AOE網絡 365
10.5.2 關鍵路徑的概念 366
10.5.3 關鍵路徑算法及其實現 368
10.6 小生成樹 371
10.6.1 小生成樹的概念 371
10.6.2 Prim算法 373
10.6.3 Kruskal算法 378
10.7 短路徑問題 381
10.7.1 問題描述 382
10.7.2 Dijkstra算法 383
10.7.3 Floyd算法 392
10.8 總結 396
參考文獻 398
附錄 399
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。