《數據結構》是2017年科學出版社出版的圖書，作者是葉飛躍。
基本介紹
- 中文名：數據結構
- 作者：葉飛躍
- 出版社：科學出版社
- 出版時間：2017年6月
- ISBN：9787030533777
內容簡介,圖書目錄,
內容簡介
本書介紹數據結構的基本內容，包括線性表、棧和佇列、串、數組和廣義表、樹和二叉樹、圖，以及排序、查找等。書中詳細介紹了甩埋檔簽各種數據結構及其在相應結構下數據運算的實現方法和性能分析。
本書遵循理實一體化的編寫理念，通過問題導入法，引入教學的重點內容，以激發讀者的學習興趣。用通俗的語言講述基礎理論，通過舉例表述算法的設計思想，用C語言描述算法，並通過算法的設計與實現解決引入的問題，強化讀者使用數據結構與算法解決實際問題的能力。
圖書目錄
叢埋背墓書序
前言
第1章 緒論 1
1.1 引例 1
1.2 基本淚寒禁概念 3
1.2.1 數據、數據元素、數據項和數據對象 3
1.2.2 數據結構 4
1.2.3 數據類型和抽象數據類型 6
1.3 算法和算法分析殼蜜炒 9
1.3.1 算法的定義及算法描述 9
1.3.2 算法評價 10
1.3.3 算法的時間複雜度 12
1.3.4 算法的空間複雜度 16
小結 17
習題 18
上機實驗題 20
第2章 C/C++語言知識 21
2.1 指針 21
2.1.1 指針變數 21
2.1.2 指針運算 22
2.1.3 數組與指針 27
2.2 結構體 31
2.2.1 結構體的定義 31
2.2.2 結構體數組 33
2.2.3 結構體指針 34
2.3 共用體 37
2.4 C++運算符 39
2.4.1 動態申請與釋放記憶體運算符 39
2.4.2 引用 41
2.5 C程式分析 42
小結 44
習題 44
上機實驗題 47
第3章 線性表 48
3.1 引例 48
3.2 線性表的籃棄概念及運算 49
3.2.1 線性表的定義 49
3.2.2 線性表的抽象數據類型定義 49
3.3 線性表的順序表示和實現 50
3.3.1 線性表的順序存儲表示 50
3.3.2 順序表基本運算的實現 51
3.4 引例中讀書興趣小組活動管理的順序表解決 56
3.5 線性表的鏈式表示和實現 61
3.5.1 單鍊表的定義和表示 62
3.5.2 單鍊表基本運算的實現 62
3.5.3 順序表和鍊表的比較 70
3.6 引例中讀書興趣小組活動管理的鍊表解決 71
3.7 鍊表知紋欠朽歸識的擴展 76
3.7.1 單循環鍊表 76
3.7.2 雙向鍊表 77
3.8 線性表套用舉例 78
小結 85
習題 86
上機實驗題 89
第4章 棧和佇列 90
4.1 引例 90
4.2 棧 92
4.2.1 棧的概念及運算 92
4.2.2 棧的順序表示和實現 93
4.2.3 棧的鏈式表示和實現 95
4.3 引例中棧相關問題的解決 98
4.3.1 行編輯的解決 98
4.3.2 數制轉換的解決 99
4.3.3 表達式求值的解決 100
4.3.4 遞歸實現的解決 107
4.4 佇列 109
4.4.1 佇列的概念及運算 109
4.4.2 佇列的順序表示和實現 111
4.4.3 佇列的鏈式表示和實現 114
4.4.4 引例中銀行個人業務模擬問題的解決 117
小結 119
習題 120
上機實驗題 123
第5章 串 124
5.1 引例 124
5.2 串的概念及運算 124
5.2.1 串的定義 124
5.2.2 串的抽象數據類型定義 125
5.3 串的順序表示和實現 126
5.3.1 串的順序存儲表示 126
5.3.2 順序串基本運算的實現 127
5.4 串的鏈式表示和實現 129
5.4.1 串的鏈式存儲表示 129
5.4.2 鏈串基本運算的實現 130
5.5 串的模式匹配 132
5.5.1 Brute-Force算法 132
5.5.2 KMP算法 134
5.6 引例的解決 138
5.6.1 名和姓對換問題的解決櫃想潤 138
5.6.2 文本檔案中單詞計數和查找問題的解決 139
小結 140
習題 140
上機實驗題 142
第6章 數組和廣義表 143
6.1 引例 143
6.2 數組 144
6.2.1 數組的概念及運算 144
6.2.2 數組的順序存儲表示 145
6.2.3 引例中求矩陣馬鞍點問題的解決 146
6.3 特殊矩陣的壓縮存儲 147
6.3.1 對稱矩陣 147
6.3.2 引例中求對稱矩陣的和與乘積問題的解決 148
6.3.3 三角矩陣 150
6.3.4 引例中求三角矩陣的和與乘積問題的解決 151
6.3.5 對角矩陣 152
6.4 廣義表 153
6.4.1 廣義表的概念及運算 153
6.4.2 廣義表的存儲結構 155
6.4.3 引例中m元多項式表示問題的解決 157
小結 158
習題 158
上機實驗題 160
第7章 樹和二叉樹 161
7.1 引例 161
7.2 樹的概念及運算 162
7.2.1 樹的定義 162
7.2.2 樹的抽象數據類型定義 164
7.3 二叉樹 165
7.3.1 二叉樹的概念及運算 165
7.3.2 二叉樹的性質 167
7.3.3 二叉樹的存儲結構 169
7.4 遍歷二叉樹 172
7.4.1 遍歷二叉樹的概念和實現 172
7.4.2 根據遍歷序列確定二叉樹 178
7.4.3 遍歷算法套用 179
7.5 線索二叉樹 182
7.5.1 線索二叉樹的概念 182
7.5.2 線索二叉樹的構造和遍歷 184
7.6 樹和森林 186
7.6.1 樹的存儲結構 186
7.6.2 樹、森林與二叉樹的相互轉換 189
7.6.3 樹與森林的遍歷 191
7.7 引例的解決 193
7.7.1 哈夫曼樹用於編碼的原理和方法 193
7.7.2 引例中字元編碼和解碼問題的解決 196
7.7.3 引例中報文編碼和解碼問題的解決 202？
小結 202
習題 203
上機實驗題 206
第8章 圖 207
8.1 引例 207
8.2 圖的概念及運算 210
8.2.1 圖的定義 210
8.2.2 圖的術語 211
8.2.3 圖的抽象數據類型定義 215
8.3 圖的存儲結構 216
8.3.1 鄰接矩陣法 216
8.3.2 鄰接表法 219
8.4 圖的遍歷 222
8.4.1 圖的深度優先遍歷 222
8.4.2 圖的廣度優先遍歷 225
8.4.3 引例中按中轉次數查詢最優航線的解決 228
8.5 最小生成樹 231
8.5.1 最小生成樹和通信網路建立 231
8.5.2 普里姆算法 231
8.5.3 克魯斯卡爾算法 236
8.5.4 引例中通信網路建立問題的解決 240
8.6 最短路徑 241
8.6.1 兩類最短路徑問題及套用 241
8.6.2 迪傑斯特拉算法 242
8.6.3 引例中按距離、飛行時間、票價查詢最優航線的解決 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中醫院選址問題的解決 253
8.7 拓撲排序 254
8.7.1 拓撲排序和課程計畫制定 254
8.7.2 拓撲排序算法 255
8.7.3 引例中課程計畫制定問題的解決 258
8.8 關鍵路徑 260
8.8.1 AOE 網和關鍵路徑 260
8.8.2 關鍵路徑算法 261
8.8.3 引例中工程工期計算問題的解決 268
小結 270
習題 270
上機實驗題 273
第9章 查找 274
9.1 引例 274
9.2 查找的基本概念 277
9.3 線性表的查找 278
9.3.1 順序查找 278
9.3.2 折半查找 279
9.4 樹表的查找 282
9.4.1 二叉排序樹 283
9.4.2 平衡二叉樹 292
9.4.3 B-樹 296
9.4.4 B+樹 303
9.5 散列表 304
9.5.1 散列表的基本概念 304
9.5.2 散列函式的構造方法 305
9.5.3 處理衝突的方法 307
9.5.4 散列表的查找及其分析 308
9.6 引例的解決 312
9.6.1 手機選擇中查找相關問題的解決 312
9.6.2 火車票信息查詢中查找相關問題的解決 314
9.6.3 學生課程成績管理中查找相關問題的解決 316
9.6.4 手機通訊錄的解決 320
小結 321
習題 322
上機實驗題 325
第10章 內部排序 326
10.1 引例 326
10.2 排序的基本概念 327
10.3 插入排序 328
10.3.1 直接插入排序 328
10.3.2 折半插入排序 329
10.3.3 希爾排序 330
10.4 交換排序 332
10.4.1 冒泡排序 332
10.4.2 快速排序 334
10.5 選擇排序 337
10.5.1 簡單選擇排序 337
10.5.2 堆排序 338
10.6 歸併排序 343
10.7 基數排序 345
10.7.1 多關鍵字排序 345
10.7.2 基數排序 346
10.8 內部排序方法的比較討論 353
10.9 引例的解決 354
10.9.1 手機選擇中排序相關問題的解決 354
10.9.2 火車票信息查詢中排序相關問題的解決 355
10.9.3 學生課程成績管理中排序相關問題的解決 357
小結 360
習題 360
上機實驗題 363
參考文獻 364
- 索引
3.8 線性表套用舉例 78
小結 85
習題 86
上機實驗題 89
第4章 棧和佇列 90
4.1 引例 90
4.2 棧 92
4.2.1 棧的概念及運算 92
4.2.2 棧的順序表示和實現 93
4.2.3 棧的鏈式表示和實現 95
4.3 引例中棧相關問題的解決 98
4.3.1 行編輯的解決 98
4.3.2 數制轉換的解決 99
4.3.3 表達式求值的解決 100
4.3.4 遞歸實現的解決 107
4.4 佇列 109
4.4.1 佇列的概念及運算 109
4.4.2 佇列的順序表示和實現 111
4.4.3 佇列的鏈式表示和實現 114
4.4.4 引例中銀行個人業務模擬問題的解決 117
小結 119
習題 120
上機實驗題 123
第5章 串 124
5.1 引例 124
5.2 串的概念及運算 124
5.2.1 串的定義 124
5.2.2 串的抽象數據類型定義 125
5.3 串的順序表示和實現 126
5.3.1 串的順序存儲表示 126
5.3.2 順序串基本運算的實現 127
5.4 串的鏈式表示和實現 129
5.4.1 串的鏈式存儲表示 129
5.4.2 鏈串基本運算的實現 130
5.5 串的模式匹配 132
5.5.1 Brute-Force算法 132
5.5.2 KMP算法 134
5.6 引例的解決 138
5.6.1 名和姓對換問題的解決 138
5.6.2 文本檔案中單詞計數和查找問題的解決 139
小結 140
習題 140
上機實驗題 142
第6章 數組和廣義表 143
6.1 引例 143
6.2 數組 144
6.2.1 數組的概念及運算 144
6.2.2 數組的順序存儲表示 145
6.2.3 引例中求矩陣馬鞍點問題的解決 146
6.3 特殊矩陣的壓縮存儲 147
6.3.1 對稱矩陣 147
6.3.2 引例中求對稱矩陣的和與乘積問題的解決 148
6.3.3 三角矩陣 150
6.3.4 引例中求三角矩陣的和與乘積問題的解決 151
6.3.5 對角矩陣 152
6.4 廣義表 153
6.4.1 廣義表的概念及運算 153
6.4.2 廣義表的存儲結構 155
6.4.3 引例中m元多項式表示問題的解決 157
小結 158
習題 158
上機實驗題 160
第7章 樹和二叉樹 161
7.1 引例 161
7.2 樹的概念及運算 162
7.2.1 樹的定義 162
7.2.2 樹的抽象數據類型定義 164
7.3 二叉樹 165
7.3.1 二叉樹的概念及運算 165
7.3.2 二叉樹的性質 167
7.3.3 二叉樹的存儲結構 169
7.4 遍歷二叉樹 172
7.4.1 遍歷二叉樹的概念和實現 172
7.4.2 根據遍歷序列確定二叉樹 178
7.4.3 遍歷算法套用 179
7.5 線索二叉樹 182
7.5.1 線索二叉樹的概念 182
7.5.2 線索二叉樹的構造和遍歷 184
7.6 樹和森林 186
7.6.1 樹的存儲結構 186
7.6.2 樹、森林與二叉樹的相互轉換 189
7.6.3 樹與森林的遍歷 191
7.7 引例的解決 193
7.7.1 哈夫曼樹用於編碼的原理和方法 193
7.7.2 引例中字元編碼和解碼問題的解決 196
7.7.3 引例中報文編碼和解碼問題的解決 202？
小結 202
習題 203
上機實驗題 206
第8章 圖 207
8.1 引例 207
8.2 圖的概念及運算 210
8.2.1 圖的定義 210
8.2.2 圖的術語 211
8.2.3 圖的抽象數據類型定義 215
8.3 圖的存儲結構 216
8.3.1 鄰接矩陣法 216
8.3.2 鄰接表法 219
8.4 圖的遍歷 222
8.4.1 圖的深度優先遍歷 222
8.4.2 圖的廣度優先遍歷 225
8.4.3 引例中按中轉次數查詢最優航線的解決 228
8.5 最小生成樹 231
8.5.1 最小生成樹和通信網路建立 231
8.5.2 普里姆算法 231
8.5.3 克魯斯卡爾算法 236
8.5.4 引例中通信網路建立問題的解決 240
8.6 最短路徑 241
8.6.1 兩類最短路徑問題及套用 241
8.6.2 迪傑斯特拉算法 242
8.6.3 引例中按距離、飛行時間、票價查詢最優航線的解決 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中醫院選址問題的解決 253
8.7 拓撲排序 254
8.7.1 拓撲排序和課程計畫制定 254
8.7.2 拓撲排序算法 255
8.7.3 引例中課程計畫制定問題的解決 258
8.8 關鍵路徑 260
8.8.1 AOE 網和關鍵路徑 260
8.8.2 關鍵路徑算法 261
8.8.3 引例中工程工期計算問題的解決 268
小結 270
習題 270
上機實驗題 273
第9章 查找 274
9.1 引例 274
9.2 查找的基本概念 277
9.3 線性表的查找 278
9.3.1 順序查找 278
9.3.2 折半查找 279
9.4 樹表的查找 282
9.4.1 二叉排序樹 283
9.4.2 平衡二叉樹 292
9.4.3 B-樹 296
9.4.4 B+樹 303
9.5 散列表 304
9.5.1 散列表的基本概念 304
9.5.2 散列函式的構造方法 305
9.5.3 處理衝突的方法 307
9.5.4 散列表的查找及其分析 308
9.6 引例的解決 312
9.6.1 手機選擇中查找相關問題的解決 312
9.6.2 火車票信息查詢中查找相關問題的解決 314
9.6.3 學生課程成績管理中查找相關問題的解決 316
9.6.4 手機通訊錄的解決 320
小結 321
習題 322
上機實驗題 325
第10章 內部排序 326
10.1 引例 326
10.2 排序的基本概念 327
10.3 插入排序 328
10.3.1 直接插入排序 328
10.3.2 折半插入排序 329
10.3.3 希爾排序 330
10.4 交換排序 332
10.4.1 冒泡排序 332
10.4.2 快速排序 334
10.5 選擇排序 337
10.5.1 簡單選擇排序 337
10.5.2 堆排序 338
10.6 歸併排序 343
10.7 基數排序 345
10.7.1 多關鍵字排序 345
10.7.2 基數排序 346
10.8 內部排序方法的比較討論 353
10.9 引例的解決 354
10.9.1 手機選擇中排序相關問題的解決 354
10.9.2 火車票信息查詢中排序相關問題的解決 355
10.9.3 學生課程成績管理中排序相關問題的解決 357
小結 360
習題 360
上機實驗題 363
參考文獻 364
- 索引
