數據結構與算法設計

數據結構與算法設計相關課程是計算機專業教學中的核心課程，也是各類程序設計競賽及互聯網公司與軟件企業招聘考查的重要方面。本書按照"數據結構—算法設計”的路線系統地介紹數據結構與算法設計的主要內容。其中，數據結構部分包括線性表、棧、隊列、字符串、數組、廣義表、樹和圖，以及兩種常用的數據操作——查找和排序；算法設計部分包括遞歸與分治法、動態規劃、貪心法、回溯法和分支限界法；最後以"快遞超市信息管理系統”作為案例介紹面向實際應用開展分析、設計、編碼與測試的完整過程。 本書融入了思政元素，注重培養學習者解決問題的思維能力，擁有豐富且形式多樣的習題，能夠同時滿足數據結構與算法設計的教學和學習需求。 本書可以作為高等院校計算機科學與技術、軟件工程、信息安全、智能科學與技術、物聯網工程等計算機相關專業的本科生教材，也可以作為從事計算機應用開發的工程技術人員的參考用書。 ^[1] 

第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 ^[1]