數據結構與算法分析新視角（第2版）

《數據結構與算法分析新視角(第2版)》是2021年電子工業出版社出版的圖書，本書按照“像外行一樣思考,像專家一樣實踐”的解決問題的思維方法，基於學習者的認知規律，列舉大量實際或工程案例，從具體問題中引出抽象概念，運用類比、圖形化描述等方式，對經典數據結構內容做深入淺出的介紹。

基本介紹

• 中文名：數據結構與算法分析新視角(第2版)
• 作者：周幸妮 等
• 出版社：電子工業出版社
• ISBN：9787121403675

內容簡介

數據結構是高等學校計算機及其相關專業的核心課程，是電腦程式設計的基礎。本書在介紹數據結構和算法的基本概念和算法分析方法的基礎上，從軟體開發的角度，通過套用背景或知識背景介紹、數據分析、函式設計、算法設計、測試調試等環節，分別對順序表、鍊表、棧、佇列、串、數組、樹、圖等基本類型的數據結構進行了分析和討論；介紹數據的典型操作方法，如數據排序方法和查找方法；介紹常見的如遞歸、分治法、動態規劃、貪心法等經典算法。

圖書目錄

第1章 緒論 1

1.1 從編程說起 1

1.1.1 計算機解題的一般步驟 1

1.1.2 從程式設計角度看數據與數據的處理 2

1.1.3 程式設計方法 3

1.1.4 程式開發過程 3

1.2 程式要處理的數據 4

1.2.1 數值計算與非數值計算的概念 5

1.2.2 數值計算實例 5

1.2.3 非數值計算實例—表 6

1.2.4 非數值計算實例—圖 9

1.2.5 非數值計算實例—樹 10

1.3 數據結構的引入 11

1.4 數據結構的基本概念 12

1.4.1 數據結構的基本術語 12

1.4.2 數據結構的三個要素 12

1.5 如何設計算法 15

1.5.1 算法的定義與表示方法 15

1.5.2 算法設計與函式設計的關係 16

1.5.3 軟體設計方法 17

1.5.4 算法設計的一般步驟 18

1.6 如何評價算法的優劣 21

1.6.1 算法的設計要求 21

1.6.2 算法效率的度量方法 22

1.7 算法性能的事前分析方法 23

1.7.1 問題的規模與算法的策略 24

1.7.2 算法效率的上限與下限 25

1.7.3 上下限問題的數學描述 26

1.7.4 漸近的上限—算法的時間複雜度 29

1.7.5 算法時間複雜度的綜合討論 30

1.7.6 算法的空間效率分析方法 34

1.7.7 算法效率分析的綜合例子 37

1.8 算法性能綜合考量 39

1.9 本章小結 40

習題 40

第2章 結點邏輯關係為線性的結構—線性表 43

2.1 從邏輯結構角度看線性表 43

2.1.1 實際問題中的線性關係 43

2.1.2 線性表的邏輯結構 44

2.2 線性表的存儲結構方法之一—順序表 45

2.2.1 順序表的存儲結構設計 45

2.2.2 關於結構類型套用的思考與討論 47

2.2.3 順序表的運算 49

2.2.4 順序存儲結構的討論 56

2.3 線性表的存儲結構方法之二—鍊表 56

2.3.1 問題的引入 56

2.3.2 單鍊表的存儲 59

2.3.3 單鍊表的運算 65

2.3.4 單鍊表的討論 78

2.3.5 循環鍊表 79

2.3.6 雙向鍊表 82

2.3.7 靜態鍊表 83

2.3.8 鍊表小結 83

2.4 線性表套用舉例 84

2.4.1 逆序輸出單鍊表結點值 84

2.4.2 一元多項式的相加 85

2.5 順序表和鍊表的比較 92

2.6 本章小結 93

習題 93

第3章 運算受限的線性表—棧和佇列 97

3.1 棧—按先進後出方式管理的線性表 97

3.1.1 棧處理模式的引入 97

3.1.2 棧的邏輯結構 100

3.1.3 棧的存儲結構設計 102

3.1.4 順序棧的操作 103

3.1.5 鏈棧的基本操作 114

3.1.6 各種棧結構的比較 119

3.1.7 棧的套用舉例 119

3.2 佇列—按先進先出方式管理的線性表 127

3.2.1 佇列處理模式的引入 127

3.2.2 佇列的邏輯結構 130

3.2.3 佇列的順序存儲結構 131

3.2.4 順序佇列的基本操作 143

3.2.5 佇列的鏈式存儲結構 147

3.2.6 鏈佇列的基本操作 148

3.2.7 各種佇列結構的比較 156

3.2.8 優先佇列 156

3.2.9 佇列的套用舉例 156

3.3 本章小結 168

習題 169

第4章 內容特殊的線性表—多維數組與字元串 171

4.1 多維數組 171

4.1.1 數組的概念 171

4.1.2 數組的存儲結構 172

4.2 矩陣的壓縮存儲 175

4.2.1 對稱矩陣的壓縮存儲 176

4.2.2 三角矩陣的壓縮存儲 177

4.2.3 對角矩陣的壓縮存儲 178

4.2.4 稀疏矩陣的壓縮存儲 179

4.3 字元串 183

4.3.1 字元串的概念 184

4.3.2 字元串的存儲結構 185

4.3.3 字元串的查找—模式匹配 189

4.3.4 BF算法 190

4.3.5 KMP算法 196

4.4 本章小結 204

習題 205

第5章 結點邏輯關係分層次的非線性結構—樹 208

5.1 實際問題中的樹形結構 208

5.1.1　日常生活中的樹形結構 208

5.1.2　計算機中的目錄結構 209

5.1.3　網站的樹形結構 209

5.1.4 表達式樹 210

5.2 樹的邏輯結構 210

5.2.1 樹的定義和基本術語 210

5.2.2 樹的操作定義 213

5.3 樹的存儲結構 213

5.3.1 樹的連續存儲方式 214

5.3.2 樹的鏈式存儲方式 215

5.4 二叉樹的邏輯結構 218

5.4.1　二叉樹與普通樹的轉換 218

5.4.2 二叉樹的概念 220

5.4.3 二叉樹的基本性質 222

5.4.4 二叉樹的操作定義 222

5.5 二叉樹的存儲結構及實現 223

5.5.1 二叉樹的順序結構 223

5.5.2 二叉樹的鏈式存儲結構 224

5.5.3 建立動態二叉鍊表 226

5.6 二叉樹結點的查找問題—樹的遍歷 230

5.6.1　問題引例 230

5.6.2 樹的廣度優先遍歷 233

5.6.3 樹的深度優先遍歷 235

5.6.4 樹的遍歷的套用 243

5.7 樹的套用 248

5.7.1 表達式樹 248

5.7.2 線索二叉樹 249

5.7.3 哈夫曼樹及哈夫曼編碼 254

5.8 線性與非線性結構的集合—廣義表 268

5.8.1 廣義表的定義 269

5.8.2 廣義表的存儲 271

5.8.3 廣義表的基本運算 277

5.9 本章小結 280

習題 281

第6章 結點邏輯關係任意的非線性結構—圖 285

6.1 實際問題中的圖及抽象 285

6.2 圖的邏輯結構 289

6.2.1 圖的定義和基本術語 289

6.2.2　圖的基本術語 290

6.2.3 圖的操作定義 292

6.3 圖的存儲結構及實現 292

6.3.1 圖的數組表示法1—鄰接矩陣 293

6.3.2 圖的數組表示法2—邊集數組 295

6.3.3 圖的鍊表表示法1—鄰接表 296

6.3.4 圖的鍊表表示法2—十字鍊表 301

6.3.5 圖的鍊表表示法3—鄰接多重表 302

6.3.6 圖各種存儲結構的歸結比較 304

6.4 圖的基本操作 305

6.4.1 鄰接矩陣的操作 305

6.4.2 鄰接表的操作 307

6.4.3　圖的運算實例 309

6.5 圖的頂點查找問題—圖的遍歷 313

6.5.1　問題的引入 313

6.5.2 圖的廣度優先遍歷—BFS 314

6.5.3 圖的深度優先遍歷—DFS 318

6.6 圖的經典套用—圖中的樹問題 324

6.6.1　引例 324

6.6.2 生成樹 326

6.6.3 小生成樹 327

6.6.4 求小生成樹算法1—Prim算法 328

6.6.5 求小生成樹算法2—Kruskal算法 334

6.6.6 生成樹算法小結 341

6.7 圖的經典套用—短路徑問題 341

6.7.1 短路徑問題的引入 341

6.7.2 單源短路徑算法—Dijkstra算法 343

6.7.3 各頂點對間短路徑算法—Floyd算法 348

6.7.4 短路徑問題小結 353

6.8 圖的經典套用—活動頂點與活動邊的問題 354

6.8.1 圖的活動頂點排序問題的引入 354

6.8.2 AOV網與拓撲排序—活動頂點排序問題 356

6.8.3 AOE網與關鍵路徑—活動邊長問題 362

6.8.4 活動頂點與活動邊問題小結 373

6.9 本章小結 373

習題 374

第7章 數據的處理方法—排序技術 380

7.1 概述 380

7.1.1 排序的基本概念 380

7.1.2 排序算法的分類 382

7.2 插入排序 382

7.2.1 直接插入排序 382

7.2.2 希爾排序 385

7.3 交換排序 387

7.3.1 冒泡排序 387

7.3.2 快速排序 389

7.4 選擇排序 393

7.4.1 簡單選擇排序 393

7.4.2 堆排序 394

7.5 歸併排序 398

7.6 分配排序 402

7.6.1 桶排序 402

7.6.2 基數排序 405

7.7 各種排序算法的比較 408

7.8 本章小結 411

習題 411

第8章 數據的處理方法—索引與查找技術 414

8.1 索引的基本概念 415

8.1.1 索引的定義 416

8.1.2 表示索引的邏輯結構 416

8.1.3 索引的主要操作 417

8.2 線性索引技術 417

8.2.1 稠密索引 417

8.2.2 分塊索引 418

8.2.3 分級索引 419

8.2.4 多重表 420

8.2.5 倒排表 422

8.3 樹形索引 424

8.3.1 二叉排序樹 424

8.3.2 B樹 428

8.4 查找概述 430

8.4.1 查找的基本概念 431

8.4.2 查找算法的性能 431

8.5 線性表的查找技術 432

8.5.1 順序查找 432

8.5.2 有序表查找 433

8.5.3 索引查找 437

8.6 樹表的查找技術 439

8.6.1 二叉排序樹的查找 439

8.6.2 B樹的查找 439

8.6.3 在非數值有序表上的查找—字典樹 440

8.7 散列表存儲及其查找技術 442

8.7.1 問題引入 442

8.7.2 散列概述 443

8.7.3 散列函式的設計 446

8.7.4 處理衝突的方法 447

8.7.5 散列查找的性能分析 452

8.8 本章小結 454

習題 455

第9章 經典算法 457

9.1 遞歸—有去有回的過程 457

9.1.1 “先進後出”的遞歸 457

9.1.2 遞歸的計算機實現 458

9.1.3 遞歸方法特點分析 460

9.1.4 遞歸算法實例 462

9.1.5 遞歸小結 464

9.2 分治法—分而治之策略 464

9.2.1 分治法 464

9.2.2 分治法的適用條件 465

9.2.3 分治問題的類型 465

9.2.4 分治法小結 468

9.3 動態規劃—多段決策法 468

9.3.1 動態規劃 468

9.3.2 動態規劃的解題方法 470

9.3.3 動態規劃解題實例 473

9.3.4 動態規劃小結 478

9.4 貪心算法—局部解法 478

9.4.1 貪心算法 478

9.4.2 貪心算法經典問題 480

9.4.3 貪心算法小結 482

9.5 回溯法—深度優先搜尋解空間 483

9.5.1 回溯法 483

9.5.2 回溯法實例 484

9.5.3 回溯法小結 488

9.6 分支限界法—廣度優先搜尋解空間 488

9.6.1 分支限界法簡介 488

9.6.2 分支限界法的求解思想 490

9.6.3 分支限界法經典問題 491

9.6.4 分支限界法小結 493

9.7 本章小結 494

習題 494

附錄A 數據的聯繫 496

作者簡介

周幸妮，西安電子科技大學通信工程學院副教授，長期從事“數據結構”、“C程式設計語言”等課程的教學工作，著有《C程式設計》、等教材。