《數據結構與算法設計》是2023年電子工業出版社出版的圖書，作者是王新宇、毛啟容。
基本介紹
- 書名：數據結構與算法設計
- 作者：王新宇、毛啟容
- 出版社：電子工業出版社
- 出版時間：2023年1月
- 頁數：400 頁
- 定價：79.80 元
- 開本：16 開
- ISBN：9787121449789
內容簡介,圖書目錄,
內容簡介
數據結構與算法設計相關課程是計算機專業教學中的核心課程，也是各類程式設計競賽及網際網路公司與軟體企業招聘考查的重要方面。本書按照"數據結構—算法設計”的路線系統地介紹數據結構與算法設計的主要內容。其中，數據結構部分包括線性表、棧、佇列、字元串、數組、廣義表、樹和圖，以及兩種常用的數據操作——查找和排序；算法設計部分包括遞歸與分治法、動態規劃、貪心法、回溯法和分支限界法；最後以"快遞超市信息管理系統”作為案例介紹面向實際套用開展分析、設計、編碼與測試的完整過程。 本書融入了思政元素，注重培養學習者解決問題的思維能力，擁有豐富且形式多樣的習題，能夠同時滿足數據結構與算法設計的教學和學習需求。 本書可以作為高等院校計算機科學與技術、軟體工程、信息安全、智慧型科學與技術、物聯網工程等計算機相關專業的本科生教材，也可以作為從事計算機套用開發的工程技術人員的參考用書。
圖書目錄
第1章 緒論 1
1.1 數據結構的研究內容 1
1.2 數據結構的概念 4
1.2.1 基本術語 4
1.2.2 數據結構的三個要素 5
1.3 算法的定義和評價 7
1.3.1 算法的定義 7
1.3.2 算法的評價 7
1.4 算法性能分析 8
1.4.1 算法的時間複雜度分析 8
1.4.2 算法的空間複雜度分析 11
1.5 算法的設計與描述 11
1.5.1 算法設計的一般步驟 11
1.5.2 算法設計的基本策略 12
1.5.3 算法的描述 13
1.6 本章小結 14
習題一 15
第2章 線性表 18
2.1 線性表的定義及基本操作 18
2.2 線性表的順序表示和實現 19
2.2.1 順序表的定義 19
2.2.2 順序表的類模板定義 20
2.2.3 順序表基本操作的實現 20
2.3 線性表的鏈式表示和實現 25
2.3.1 單鍊表 25
2.3.2 單循環鍊表 32
2.3.3 雙向循環鍊表 33
2.3.4 靜態鍊表 37
2.4 線性表的套用 41
2.5 本章小結 45
習題二 46
第3章 棧和佇列 49
3.1 棧 50
3.1.1 棧的定義 50
3.1.2 順序棧 51
3.1.3 鏈棧 54
3.2 棧的套用 58
3.3 佇列 65
3.3.1 佇列的定義 66
3.3.2 循環佇列 66
3.3.3 鏈佇列 72
3.4 佇列的套用 76
3.5 本章小結 82
習題三 82
第4章 字元串、數組和廣義表 86
4.1 字元串 87
4.1.1 字元串的定義 87
4.1.2 C++字元串操作 88
4.1.3 模式匹配 88
4.2 數組 93
4.2.1 數組的定義 93
4.2.2 數組的順序存儲結構 93
4.3 特殊矩陣的壓縮存儲 95
4.3.1 對稱矩陣和三角矩陣 95
4.3.2 帶狀矩陣 96
4.3.3 稀疏矩陣 97
4.4 廣義表 101
4.5 本章小結 101
習題四 102
第5章 樹 105
5.1 樹的定義與術語 106
5.1.1 樹的定義 106
5.1.2 樹的術語 107
5.1.3 樹的表示方法 107
5.1.4 樹的基本操作 108
5.2 二叉樹 108
5.2.1 二叉樹的定義 108
5.2.2 二叉樹的性質 109
5.2.3 二叉樹的基本操作 110
5.3 二叉樹的存儲結構 111
5.3.1 二叉樹的順序存儲結構 111
5.3.2 二叉樹的鏈式存儲結構 112
5.3.3 二叉樹的二叉鍊表類模板
定義 112
5.4 二叉樹的遍歷 115
5.4.1 先序遍歷 116
5.4.2 中序遍歷 116
5.4.3 後序遍歷 117
5.4.4 層次遍歷 117
5.4.5 基於遍歷的操作 118
5.5 線索二叉樹 121
5.5.1 線索二叉樹的定義 121
5.5.2 中序線索二叉樹類模板定義 122
5.6 二叉樹的套用 126
5.6.1 堆 127
5.6.2 哈夫曼樹 133
5.7 樹和森林 136
5.7.1 樹的存儲結構 136
5.7.2 樹、森林和二叉樹的轉換 138
5.7.3 樹的遍歷 141
5.7.4 森林的遍歷 141
5.8 本章小結 142
習題五 142
第6章 圖 146
6.1 圖的定義與術語 146
6.1.1 圖的定義 146
6.1.2 圖的術語 147
6.1.3 圖的基本操作 149
6.2 圖的存儲結構 149
6.2.1 鄰接矩陣 150
6.2.2 鄰接表 156
6.2.3 鄰接多重表 164
6.2.4 十字鍊表 165
6.3 圖的遍歷 166
6.3.1 深度優先遍歷 166
6.3.2 廣度優先遍歷 168
6.4 圖的套用 170
6.4.1 最小生成樹 170
6.4.2 最短路徑 173
6.4.3 活動網路 177
6.5 本章小結 184
習題六 185
第7章 查找 189
7.1 查找的基本概念 189
7.2 線性表的查找 191
7.2.1 順序查找 191
7.2.2 折半查找 193
7.2.3 索引查找 195
7.3 樹表查找 198
7.3.1 二叉排序樹 198
7.3.2 平衡二叉樹 206
7.3.3 B-樹與B+樹 213
7.4 散列查找 218
7.4.1 散列表的概念 218
7.4.2 散列函式的構造方法 219
7.4.3 解決衝突的方法 222
7.4.4 散列查找及其性能分析 224
7.5 本章小結 227
習題七 228
第8章 排序 231
8.1 排序的基礎知識 232
8.2 交換排序 233
8.2.1 冒泡排序 233
8.2.2 快速排序 235
8.3 插入排序 237
8.3.1 直接插入排序 237
8.3.2 折半插入排序 239
8.3.3 希爾排序 240
8.4 選擇排序 241
8.4.1 簡單選擇排序 242
8.4.2 堆排序 243
8.5 歸併排序 245
8.5.1 兩路歸併算法 245
8.5.2 兩路歸併排序 247
8.6 基數排序 248
8.6.1 多關鍵字排序 248
8.6.2 鏈式基數排序 249
8.7 排序方法的比較 252
8.8 本章小結 253
習題八 253
第9章 遞歸與分治法 256
9.1 遞歸程式設計 256
9.1.1 遞歸的定義 256
9.1.2 遞歸的適用條件 257
9.1.3 遞歸的程式設計 259
9.1.4 遞歸的優缺點 264
9.2 分治法 265
9.2.1 分治法的基本思想 265
9.2.2 分治法的適用條件 266
9.2.3 分治法的設計步驟 266
9.3 分治法的套用實例 267
9.3.1 選擇問題 267
9.3.2 排序問題 272
9.3.3 大整數的乘法 273
9.3.4 Strassen矩陣乘法 276
9.3.5 棋盤覆蓋問題 278
9.3.6 循環賽日程安排 281
9.4 本章小結 284
習題九 284
第10章 動態規劃 286
10.1 動態規劃概述 286
10.1.1 動態規劃的基本思想 286
10.1.2 動態規劃的適用條件 287
10.1.3 動態規劃的設計步驟 289
10.2 動態規劃的套用實例 291
10.2.1 矩陣連乘問題 291
10.2.2 投資問題 295
10.2.3 0-1背包問題 299
10.2.4 最長公共子序列問題 303
10.3 本章小結 308
習題十 308
第11章 貪心法 310
11.1 貪心法概述 310
11.1.1 貪心法的基本思想 310
11.1.2 貪心法的適用條件 311
11.1.3 貪心法和動態規劃的區別 312
11.1.4 貪心法的設計算法的步驟 312
11.1.5 貪心算法的正確性證明 313
11.2 貪心法的套用實例 313
11.2.1 活動安排問題 313
11.2.2 最優裝載問題 316
11.2.3 背包問題 318
11.3 本章小結 321
習題十一 321
第12章 回溯法 323
12.1 回溯法概述 323
12.1.1 問題的解空間 323
12.1.2 回溯法的基本思想 325
12.1.3 回溯法的設計步驟與算法框架 327
12.1.4 子集樹與排列樹 328
12.1.5 回溯法的適用條件 330
12.2 回溯法的套用實例 331
12.2.1 0-1背包問題 331
12.2.2 裝載問題 335
12.2.3 n皇后問題 339
12.2.4 旅行商問題 342
12.3 本章小結 346
習題十二 346
第13章 分支限界法 348
13.1 分支限界法概述 348
13.1.1 分支限界法的基本思想 348
13.1.2 分支限界法的三個關鍵問題 349
13.1.3 分支限界法的設計步驟 350
13.1.4 分支限界法的時間性能 350
13.1.5 分支限界法的適用條件 350
13.2 分支限界法的套用實例 351
13.2.1 0-1背包問題 351
13.2.2 旅行商問題 358
13.2.3 流水作業調度 360
13.2.4 單源點最短路徑問題 365
13.3 本章小結 367
習題十三 367
第14章 快遞超市信息管理系統 369
14.1 問題描述 369
14.2 需求分析 370
14.3 概要設計 370
14.3.1 模組設計 370
14.3.2 界面設計 371
14.3.3 類和數據結構設計 371
14.4 詳細設計 373
14.4.1 類的詳細設計 373
14.4.2 系統功能的詳細設計 376
14.5 編碼 377
14.6 測試 386
14.7 本章小結 391
習題十四 391
參考文獻 392
