數據結構與算法

目錄

第1章緒論1

問題導入1

1.1數據結構的研究內容1

1.2數據結構的基本概念和術語1

1.2.1數據的邏輯結構2

1.2.2數據的存儲結構3

1.2.3數據的操作實現4

1.2.4抽象數據類型的定義4

1.3算法分析5

1.3.1算法的定義及特性5

1.3.2時間復雜度的度量6

1.3.3空間復雜度7

1.4應用案例: 人工智能大模型的參數量7

1.5本章小結8

1.6本章習題8

第2章線性表10

問題導入10

2.1線性表的定義10

2.2線性表的順序存儲結構11

2.2.1順序表的結構定義11

2.2.2順序表的基本操作12

2.3線性表的鏈式存儲實現16

2.3.1單鏈表16

2.3.2單鏈表的基本操作17

2.3.3循環鏈表20

2.3.4雙向鏈表21

2.3.5引入案例的實現22

2.3.6靜態鏈表23

2.4線性表實現方法的比較24

2.5應用案例: 深度學習模型中的張量存儲25

2.6本章小結25

2.7本章習題26

第3章棧與隊列28

問題導入28

3.1棧的定義與結構28

3.1.1棧的抽象數據類型定義28

3.1.2棧的順序存儲實現29

3.1.3棧的鏈式存儲實現30

3.2棧的應用舉例31

3.2.1數制轉換31

3.2.2括號匹配檢測32

3.2.3行編輯程序33

3.2.4棧的迷宮求解34

3.2.5表達式求值35

3.3棧與遞歸的實現36

3.4隊列38

3.4.1隊列的抽象數據類型定義38

3.4.2隊列的鏈式存儲實現39

3.4.3隊列的順序存儲實現41

3.4.4隊列的迷宮求解43

3.5應用案例: 區塊鏈技術45

3.6本章小結46

3.7本章習題46

第4章串49

問題導入49

4.1串類型的表示49

4.2串的表示和實現51

4.2.1定長順序存儲表示51

4.2.2堆分配存儲表示54

4.2.3串的塊鏈存儲表示58

4.3串的模式匹配算法59

4.3.1求子串位置的定位函數59

4.3.2模式匹配的改進算法59

4.4串操作應用舉例63

4.4.1文本編輯63

4.4.2建立詞索引表64

4.5本章小結65

4.6本章習題66第5章數組和廣義表68

問題導入68

5.1數組的定義68

5.1.1數組的基本概念68

5.1.2數組的實現69

5.2數組的順序表示和實現69

5.2.1存儲映像69

5.2.2數據元素存儲位置的映像關系70

5.2.3數組的順序存儲實現70

5.3矩陣的壓縮存儲72

5.3.1特殊矩陣72

5.3.2稀疏矩陣73

5.3.3三元組順序表存儲稀疏矩陣74

5.3.4行邏輯鏈接的順序表存儲稀疏矩陣77

5.3.5十字鏈表存儲稀疏矩陣79

5.4廣義表的定義和存儲結構82

5.4.1廣義表的定義82

5.4.2表頭表尾存儲結構84

5.4.3子表存儲結構85

5.5廣義表操作的遞歸算法86

5.5.1求廣義表的深度87

5.5.2復制廣義表88

5.5.3建立廣義表的存儲結構89

5.6應用案例: 深度學習模型中的張量91

5.7本章小結92

5.8本章習題92

第6章樹和二叉樹94

問題導入94

6.1樹的定義和基本術語94

6.1.1樹的定義和基本操作94

6.1.2樹的基本術語96

6.2二叉樹96

6.2.1二叉樹的定義96

6.2.2二叉樹的性質97

6.2.3二叉樹的存儲結構99

6.3遍歷二叉樹100

6.3.1問題提出100

6.3.2二叉樹遍歷算法101

6.3.3遍歷算法應用104

6.4線索二叉樹106

6.4.1問題提出106

6.4.2線索二叉樹算法107

6.4.3建立線索鏈表107

6.5樹和森林108

6.5.1樹的存儲結構108

6.5.2森林與二叉樹的轉換110

6.5.3樹和森林的遍歷112

6.5.4樹的計數112

6.6應用案例115

6.6.1哈夫曼樹及其應用115

6.6.2人工智能中的決策樹118

6.7本章小結120

6.8本章習題120

第7章圖122

問題導入122

7.1圖的定義和術語122

7.1.1圖相關基本概念122

7.1.2圖基本操作125

7.2圖的存儲126

7.2.1鄰接矩陣126

7.2.2鄰接表129

7.2.3十字鏈表130

7.2.4鄰接多重表133

7.3圖的遍歷134

7.3.1深度優先搜索134

7.3.2廣度優先搜索137

7.4圖的連通性問題139

7.4.1無向圖的連通分量和生成樹139

7.4.2有向圖的強連通分量141

7.4.3最小生成樹141

7.5有向無環圖及其應用146

7.5.1拓撲排序147

7.5.2關鍵路徑149

7.6最短路徑153

7.6.1從某個源點到其余各頂點的最短路徑153

7.6.2每一對頂點之間的最短路徑156

7.7應用案例158

7.7.1社交網絡分析158

7.7.2路徑規劃158

7.8本章小結159

7.9本章習題160

第8章查找164

問題導入164

8.1靜態查找表166

8.1.1順序表的查找166

8.1.2有序表的查找167

8.1.3靜態樹表的查找169

8.1.4索引順序表的查找170

8.2動態查找表171

8.2.1二叉排序樹和平衡二叉樹172

8.2.2B樹和B+樹180

8.2.3鍵樹185

8.3哈希表186

8.3.1哈希表定義186

8.3.2構造哈希函數的方法186

8.3.3處理沖突的方法189

8.3.4哈希表的查找及其分析192

8.4應用案例193

8.4.1電商平臺商品查找193

8.4.2數據庫中的數據查找193

8.5本章小結194

8.6本章習題194

第9章內部排序198

問題導入198

9.1概述198

9.1.1排序的定義與基本概念199

9.1.2排序算法的性能分析指標199

9.2插入排序199

9.2.1直接插入排序200

9.2.2折半插入排序200

9.2.3希爾排序201

9.3交換排序202

9.3.1冒泡排序202

9.3.2快速排序203

9.4選擇排序205

9.4.1簡單選擇排序205

9.4.2堆排序206

9.5歸並排序207

9.5.1二路歸並排序207

9.5.2多路歸並排序208

9.6基數排序210

9.6.1多關鍵字排序210

9.6.2鏈式基數排序211

9.7各種內部排序方法的比較213

9.7.1時間性能對比213

9.7.2空間性能對比214

9.7.3穩定性214

9.8排序算法在深度學習中的應用215

9.8.1註意力機制中的權重篩選215

9.8.2推薦系統和搜索中的得分排序216

9.8.3Beam Search中的候選序列排序216

9.8.4其他場景216

9.9排序算法總結216

9.10本章小結218

9.11本章習題218

第10章算法思想221

10.1枚舉法221

10.2回溯法222

10.3分治法224

10.4動態規劃225

10.5貪心法226

10.6本章小結228

10.7本章習題228

參考文獻230