《數據結構（Java語言描述）》是2015年12月電子工業出版社出版的圖書，作者是丁海軍。
基本介紹
- 中文名：數據結構（Java語言描述）
- 作者：丁海軍
- ISBN：9787121275302
- 頁數：304頁
- 定價：39.8元
- 出版社：電子工業出版社
- 出版時間：2015年12月
- 開本：16開
內容簡介,圖書目錄,
內容簡介
本書以作者多年數據結構課程教學經驗為基礎編寫而成。全書共9章，第1章介紹了數據結構的基本概念及算法複雜度分析的詳細框架和步驟；第2~5章是對線性結構的詳細介紹，這一部分是整個數據結構的基礎，包括順序表、鍊表、棧、佇列、稀疏矩陣以及線性表的查找和排序等內容；第6~8章主要研究樹結構，第6章介紹了二叉樹及樹的性質、遍歷算法及其套用，第7章研究了查找二叉樹及相關算法，第8章介紹了堆結構及其套用；第9章介紹了圖結構及關於圖的幾個基礎算法。 本書以Java語言作為數據結構及算法的描述語言，以Java環境的集合框架為參照組織教學內容，便於讀者更好地將課程內容運用到實際的軟體開發過程中。本書配套有PPT、習題解答等。
圖書目錄
第1章 緒 論 1
1.1 數據結構的概念 1
1.1.1 為什麼要學習數據結構 2
1.1.2 有關概念和術語 4
1.1.3 數據結構的三要素 5
1.2 抽象數據類型 6
1.2.1 數據類型 6
1.2.2 抽象數據類型 7
1.3 算法概念及算法設計的問題 8
1.3.1 什麼是算法 8
1.3.2 算法特性 10
1.3.3 算法的結構和表示方法 10
1.3.4 算法設計原則 11
1.3.5 幾種基本的算法設計方法和策略 12
1.3.6 編程解決問題的一般步驟 12
1.4 算法分析 13
1.4.1 時間複雜度分析的兩類方法 13
1.4.2 時間複雜度分析的理論框架 14
1.4.3 非遞歸算法時間複雜度分析步驟 19
1.4.4 典型非遞歸算法的時間複雜度類型 20
1.4.5 遞歸算法時間複雜度分析步驟 22
1.4.6 空間複雜度 23
1.5 數據結構課程的內容 23
1.6 習題 24
第2章 線性表 27
2.1 線性表的邏輯結構 27
2.2 順序表概念及存儲特點 29
2.2.1 順序表的邏輯特點 29
2.2.2 順序表面向對象描述 29
2.3 順序表的重要算法及實現 31
2.3.1 初始化 31
2.3.2 順序表容量管理 31
2.3.3 數據存取 32
2.3.4 向順序表中插入元素 33
2.3.5 刪除順序表中的元素 34
2.3.6 查找元素 35
2.3.7 順序表中元素的有序插入與排序 36
2.3.8 順序錶轉換為數組 37
2.3.9 順序錶轉換為字元串 38
2.4 單鍊表概念及類定義 38
2.4.1 單鍊表基本概念 38
2.4.2 鍊表面向對象描述 41
2.5 單鍊表重要算法實現 44
2.5.1 數據存取 44
2.5.2 向鍊表中插入元素 44
2.5.3 刪除鍊表節點 47
2.5.4 查找節點 49
2.5.5 向鍊表中有序插入節點 50
2.5.6 鍊表排序 52
2.5.7 鍊表轉換為字元串和數組 53
2.6* 鍊表疊代器 54
2.6.1 疊代器的概念 54
2.6.2 與疊代器有關的Java語言特性 55
2.6.3 鍊表類LinkList疊代器的實現 56
2.7 循環鍊表與雙向鍊表 58
2.7.1 循環鍊表 58
2.7.2 雙向鍊表 59
2.8* 順序表和鍊表的比較 60
2.9 習題 61
第3章 特殊的線性結構 64
3.1 棧 64
3.1.1 基本概念 64
3.1.2 鏈棧——棧的鍊表實現 65
3.1.3 順序棧——棧的數組實現 66
3.1.4 表達式求值 68
3.2 佇列 72
3.2.1 佇列概念 72
3.2.2 鏈式佇列 73
3.2.3 順序佇列 74
3.2.4 循環佇列 75
3.2.5 佇列套用 76
3.3 特殊矩陣 78
3.3.1 矩陣存儲方式 78
3.3.2 對稱矩陣和三角矩陣 79
3.3.3 對角矩陣 80
3.4 稀疏矩陣 81
3.4.1 三元組 81
3.4.2 矩陣抽象數據類型 82
3.4.3 稀疏矩陣的三元組順序表表示 83
3.4.4 稀疏矩陣的行鍊表表示 88
3.4.5 稀疏矩陣的十字鍊表表示 91
3.5 廣義表 92
3.5.1 廣義表的定義和基本運算 93
3.5.2 廣義表的存儲結構 95
3.6 習題 96
第4章 線性查找算法 99
4.1 查找的基本概念 99
4.1.1 什麼是查找及查找結構 99
4.1.2 查找結構的分類 100
4.1.3 平均查找長度 100
4.2 線性查找表 100
4.2.1 順序查找 100
4.2.2 二分查找 100
4.2.3 分塊查找 102
4.2.4 順序表三種查找方法的比較 103
4.3 哈希查找 103
4.3.1 哈希表 103
4.3.2 哈希函式的構造方法 104
4.3.3 處理衝突的方法 106
4.3.4 哈希查找算法性能分析 109
4.4 哈希映射 109
4.4.1 映射（Map）概念 109
4.4.2 哈希表實現映射 110
4.5 串匹配 112
4.5.1 簡單的模式匹配算法 112
4.5.2 KMP模式匹配算法 114
4.6 習題 118
第5章 排序算法 122
5.1 基本概念 122
5.2 插入排序 122
5.2.1 算法設計 123
5.2.2 時間複雜度分析 124
5.3 選擇排序 124
5.3.1 算法設計 124
5.3.2 時間複雜度分析 125
5.4 冒泡排序 126
5.4.1 算法設計 126
5.4.2 時間複雜度分析 127
5.5 快速排序 127
5.5.1 快速排序的思想 127
5.5.2 快速排序算法實現 128
5.5.3 時間複雜度分析 129
5.6 歸併排序 130
5.6.1 有序表的合併算法 130
5.6.2 遞歸歸併排序 131
5.6.3 疊代歸併排序 132
5.6.4 時間複雜度分析 133
5.7 基數排序 134
5.7.1 桶排序 134
5.7.2 基數排序套用舉例 134
5.8* 希爾排序 135
5.8.1 排序過程與算法設計 135
5.8.2 時間複雜度分析 137
5.9 習題 138
第6章 二叉樹與樹 145
6.1 樹與二叉樹一般概念 145
6.1.1 樹 145
6.1.2 二叉樹 146
6.2 二叉樹的性質 148
6.3 二叉樹存儲結構 150
6.3.1 順序存儲 150
6.3.2 鏈式存儲 151
6.4 二叉樹遍歷 152
6.4.1 二叉樹遍歷概念 152
6.4.2 先序遍歷（DLR） 153
6.4.3 中序遍歷（LDR） 154
6.4.4 後序遍歷（LRD） 154
6.4.5 層次遍歷 155
6.4.6 遍歷的套用 156
6.4.7 根據已知的遍歷序列恢復二叉樹 157
6.5 哈夫曼（Huffman）樹及其套用 159
6.5.1 最優二叉樹（Huffman樹）概念 159
6.5.2 Huffman樹的構造方法 160
6.5.3 Huffman編碼 162
6.5.4 Huffman編碼、碼算法實現 164
6.6 遞歸 172
6.6.1 遞歸調用樹 172
6.6.2 遞歸棧 176
6.6.3 二叉樹遍歷的非遞歸算法 179
6.7 樹和森林 182
6.7.1 基本概念 182
6.7.2 樹的存儲結構 182
6.7.3 樹的遍歷 185
6.7.4 樹的深度優先搜尋與回溯法 186
6.7.5 樹與並查集 190
6.8 習題 192
第7章 查找樹 198
7.1 二叉查找樹概念 198
7.1.1 二叉查找樹定義 198
7.1.2 二叉查找樹的面向對象描述 199
7.2 二叉查找樹主要算法 202
7.2.1 求最大、最小值算法 202
7.2.2 查找算法 202
7.2.3 插入算法 204
7.2.4 刪除算法 206
7.2.5 時間複雜度分析 209
7.3 AVL平衡二叉樹 210
7.3.1 平衡二叉樹的概念 211
7.3.2 平衡調整 214
7.3.3 AVL樹的查找算法 218
7.3.4 AVL樹的插入算法 218
7.3.5 AVL樹刪除算法 219
7.3.6 AVL樹時間複雜度分析 220
7.4 B-樹 222
7.4.1 分塊索引查找 222
7.4.2 B-樹定義 222
7.4.3 B-樹查找 223
7.4.4 B-樹的插入 225
7.4.5 B-樹刪除 226
7.5 B+樹 228
7.6 習題 229
第8章 堆與優先佇列及堆排序 233
8.1堆 233
8.1.1 堆的基本算法 234
8.1.2 堆的實現 237
8.2 優先佇列 239
8.3 堆排序 240
8.4 習題 241
第9章 圖結構及相關算法 242
9.1 圖的概念 242
9.1.1 什麼是圖 242
9.1.2 圖論的基本概念 243
9.1.3 樹和森林 246
9.2 圖的基本操作與圖的存儲結構 246
9.2.1 圖的基本操作 247
9.2.2 圖的存儲結構概述 250
9.2.3 圖的鄰接矩陣存儲 250
9.2.4 圖的鄰接表存儲 255
9.2.5 圖的邊集數組存儲 260
9.3 圖的遍歷 261
9.3.1 深度優先遍歷 261
9.3.2 廣度優先遍歷 263
9.3.3 利用圖遍歷算法研究圖的連通性 264
9.4 最小生成樹問題 266
9.4.1 圖的生成樹和生成森林 266
9.4.2 圖的最小生成樹概念 267
9.4.3 構造最小生成樹的Prim算法 268
9.4.4 構造最小生成樹的Kruskal算法 271
9.5 最短路徑問題 273
9.5.1 從一個源點到其他各點的最短路徑 274
9.5.2 所有點對之間的最短路徑 278
9.6 拓撲排序問題 280
9.6.1 偏序關係 280
9.6.2 拓撲排序 280
9.6.3 拓撲排序套用 281
9.7* 關鍵路徑問題 283
9.7.1 AOE網（Activity On Edge network） 283
9.7.2 關鍵路徑 284
9.8 習題 287
