數據結構與智能算法

目錄

 

 

第1章緒論1

1.1數據結構及其相關概念1

1.1.1數據結構討論範圍1

1.1.2定義和術語5

1.1.3抽象數據類型12

1.2算法及其分析15

1.2.1算法和數據結構關系15

1.2.2算法定義16

1.2.3算法描述18

1.2.4算法分析21

1.3程序設計基礎27

1.3.1程序和數據結構關系27

1.3.2靜態存儲和動態存儲28

1.3.3結構體類型28

1.3.4輸入/輸出29

1.3.5引用類型參數29

1.3.6流程控制（分支、循環等）30

1.3.7遞歸31

1.3.8軟件構造31

1.4數據結構的歷史與發展32

1.5人工智能的歷史與發展34

1.6智能算法應用36

本章小結38

習題38

與前沿技術鏈接39

科學家精神39

第2章線性表43

2.1線性表的邏輯結構43

2.1.1線性表的定義43

2.1.2線性表的邏輯特徵44

2.2線性表的抽象數據類型44

2.3線性表的順序存儲實現45

2.3.1順序表46

2.3.2順序表基本運算的實現46

2.3.3順序表的基礎應用49

2.3.4順序表的智能應用50

2.4線性表的鏈式存儲實現52

2.4.1線性鏈表53

2.4.2靜態鏈表58

2.4.3循環鏈表59

2.4.4雙向鏈表60

2.4.5鏈表的智能應用61

2.5實際中存儲結構的選擇63

本章小結63

習題63

與前沿技術鏈接65

科學家精神65

第3章棧與隊列67

3.1棧的定義67

3.1.1棧的定義和術語67

3.1.2棧的抽象數據類型68

3.2棧的存儲與實現69

3.2.1棧的順序存儲與實現69

3.2.2棧的鏈式存儲與實現70

3.2.3多棧共享的存儲與實現70

3.3棧的應用71

3.3.1棧與遞歸過程71

3.3.2迷宮問題74

3.3.3表達式求值76

3.3.4棧在智能算法中的應用78

3.4隊列的定義79

3.4.1隊列的定義和術語79

3.4.2隊列的抽象數據類型79

3.5隊列的存儲與實現79

3.5.1隊列的鏈式存儲與實現79

3.5.2隊列的順序存儲與實現81

3.6隊列的應用82

3.6.1約瑟夫出圈問題83

3.6.2舞伴問題83

3.6.3隊列在智能算法中的應用84

本章小結85

習題85

與前沿技術鏈接87

科學家精神87

第4章串90

4.1串的定義90

4.1.1串的定義和術語90

4.1.2串的抽象數據類型91

4.2串的存儲與實現92

4.2.1串的順序存儲與實現92

4.2.2串的堆分配存儲與實現93

4.2.3串的鏈式存儲與實現94

4.3模式匹配95

4.3.1樸素模式匹配算法95

4.3.2KMP算法——改進的模式匹配算法97

4.4串的智能算法應用102

本章小結103

習題103

與前沿技術鏈接104

科學家精神106

第5章數組與廣義表108

5.1數組的定義108

5.1.1數組的定義和術語108

5.1.2數組的抽象數據類型109

5.2數組的存儲與實現109

5.2.1數組的順序存儲109

5.2.2數組的壓縮存儲111

5.2.3數組的鏈式存儲115

5.3數組的智能算法應用117

5.4廣義表的定義118

5.4.1廣義表的定義和術語118

5.4.2廣義表的抽象數據類型119

5.5廣義表的存儲與實現120

5.5.1表頭表尾分析法120

5.5.2子表分析法120

5.5.3廣義表的操作121

5.6廣義表的智能算法應用122

本章小結123

習題123

與前沿技術鏈接124

科學家精神124

第6章樹126

6.1樹的相關概念126

6.1.1樹的定義和術語126

6.1.2樹的抽象數據類型127

6.1.3樹的應用和表示方法128

6.2二叉樹130

6.2.1二叉樹的有關概念130

6.2.2二叉樹的存儲與實現133

6.2.3二叉樹的遍歷134

6.3線索二叉樹141

6.3.1線索二叉樹的表示141

6.3.2二叉樹的線索化142

6.3.3線索二叉樹的遍歷144

6.4樹和森林145

6.4.1樹的存儲結構145

6.4.2樹、森林與二叉樹的轉換148

6.4.3樹和森林的遍歷150

6.5樹的應用152

6.5.1哈夫曼樹152

6.5.2判定樹160

6.5.3集合的樹形結構表示162

6.6樹的知識點結構164

6.7樹的智能算法應用165

6.7.1決策樹165

6.7.2梯度提升樹(GBDT)特徵工程166

6.7.3樹形遞歸神經網絡(Tree Recursive Neural Network)167

6.7.4深度神經網絡壓縮169

本章小結170

習題170

與前沿技術鏈接175

科學家精神175

第7章圖177

7.1圖的相關概念177

7.1.1圖的定義和術語177

7.1.2圖的抽象數據類型178

7.2圖的存儲結構179

7.2.1圖的順序存儲179

7.2.2圖的鏈式存儲181

7.2.3有向圖的十字鏈表存儲183

7.2.4無向圖的鄰接多重表存儲184

7.3圖的遍歷185

7.3.1深度優先遍歷185

7.3.2廣度優先遍歷187

7.4圖與樹的聯系190

7.4.1生成樹190

7.4.2無向圖與開放樹191

7.4.3最小生成樹191

7.5無向圖的雙連通性196

7.5.1無向圖的雙連通分量196

7.5.2求關節點算法196

7.6有向圖的遍歷和強連通性198

7.6.1有向圖的遍歷198

7.6.2強連通性199

7.7有向無環圖的應用200

7.7.1拓撲排序200

7.7.2關鍵路徑202

7.8最短路徑205

7.8.1單源最短路徑205

7.8.2每對頂點間的最短路徑207

7.9圖的智能算法應用209

7.9.1圖與復雜網絡209

7.9.2圖與社區發現（GirvanNewman算法）210

7.9.3圖與推薦系統（協同過濾算法）211

7.9.4蓋板瑕疵檢測212

7.10圖的知識點結構214

本章小結215

習題215

與前沿技術鏈接221

科學家精神222

第8章查找225

8.1查找的相關概念225

8.1.1查找表的定義和術語225

8.1.2查找表的抽象數據類型225

8.1.3查找的分類226

8.2靜態查找226

8.2.1順序表的查找線性查找226

8.2.2有序表的查找折半查找228

8.2.3索引順序表的查找分塊查找229

8.3動態查找表230

8.3.1二叉排序樹230

8.3.2平衡二叉樹234

8.3.3B-樹和B+樹238

8.4哈希表243

8.4.1哈希表的有關概念243

8.4.2哈希函數的構造方法244

8.4.3處理沖突的方法247

8.4.4哈希表的查找和分析248

8.5查找的知識點結構及擴展252

8.5.1跳錶252

8.5.2紅黑樹253

8.6查找的智能算法應用254

8.6.1最近鄰查找算法254

8.6.2哈希查找算法255

8.6.3LSH算法256

本章小結257

習題257

與前沿技術鏈接258

科學家精神259

第9章內部排序262

9.1排序的相關概念262

9.1.1排序的定義和術語262

9.1.2內部排序263

9.2插入排序264

9.2.1直接插入排序264

9.2.2折半插入排序265

9.2.3表插入排序267

9.2.4希爾排序270

9.3冒泡排序和快速排序272

9.3.1冒泡排序272

9.3.2快速排序273

9.4選擇排序276

9.4.1簡單選擇排序276

9.4.2樹形選擇排序277

9.4.3堆排序278

9.4.4歸並排序280

9.4.5基數排序282

9.5排序算法的比較284

9.6排序的智能算法應用285

9.6.1檢索模型285

9.6.2推薦系統287

本章小結288

習題289

與前沿技術鏈接290

科學家精神291

第10章文件與外部排序293

10.1文件及文件操作293

10.1.1文件的相關概念293

10.1.2文件操作294

10.1.3查詢方式295

10.1.4文件分類295

10.2文件組織296

10.2.1順序方式296

10.2.2索引方式298

10.2.3散列方式299

10.2.4鏈接方式文件和多重鏈表文件301

10.2.5ISAM文件302

10.2.6VSAM文件304

10.2.7UNIX文件306

10.3磁盤文件的歸並分類307

10.4磁帶文件的歸並分類311

10.5外部排序的智能算法應用312

10.5.1分佈式隨機梯度下降313

10.5.2聯邦學習314

本章小結315

習題315

與前沿技術鏈接316

科學家精神317