數據結構與算法（第2版）（大數據與AI版）

數據結構與算法（第2版）（大數據與AI版）是北京郵電大學出版社出版的圖書，作者是徐雅靜。

基本介紹

• 中文名：數據結構與算法（第2版）（大數據與AI版）
• 作者：徐雅靜
• 出版時間：2024年2月14日
• 出版社：北京郵電大學出版社
• ISBN：9787563571635
• 定價：58 元

內容簡介

“數據結構與算法”是計算機及其相關專業的重要課程，該課程的內容是計算機軟體開發及套用人員必備的專業基礎。隨著大數據、人工智慧、通信技術的發展，計算機軟體也越來越朝著智慧型化、自動化方向發展，結合人工智慧技術、大數據技術來開發計算機軟體是未來的發展趨勢。本書主要介紹了經典的數據結構與算法的知識，包括基礎的線性表、棧、佇列、串、數組、樹、圖等數據結構，以及常用的查找和排序技術。在此基礎上，本書加入了大數據和AI領域的KNN機器學習、隨機梯度下降、神經網路、搜尋引擎、大規模矩陣計算、大數據排序等工程實踐案例，使讀者可以將數據結構和算法的知識與大數據和AI套用緊密結合在一起，融會貫通。

本書內容豐富、層次清晰、深入淺出，在AI、大數據領域的工程實踐案例中將理論講解和代碼實現一一對應，尤其適合作為人工智慧專業、大數據專業、電子信息類專業的數據結構與算法課程的教材，可以為學生後續學習AI和大數據等專業課程奠定基礎。

圖書目錄

第1章緒論1

1.1數據結構與算法的重要性1

1.2數據結構的基本概念4

1.3算法和算法分析7

1.3.1算法描述7

1.3.2算法分析9

1.3.3NP問題12

1.4STL與數據結構13

1.4.1STL簡介13

1.4.2STL與數據結構的關係14

1.5工程實踐和思考15

習題119

第2章線性表21

2.1線性表概述21

2.1.1線性表的定義21

2.1.2線性表的運算22

2.1.3各種常用存儲結構22

2.2順序表的實現25

2.2.1順序表的存儲結構25

2.2.2順序表的基本運算25

2.2.3順序表的套用——通訊錄30

2.2.4STL中的順序表——vector32

2.3單鍊表的實現34

2.3.1單鍊表的存儲結構34

2.3.2單鍊表的基本運算36

2.3.3單鍊表的套用——通訊錄43

2.4循環鍊表的實現43

2.5雙鍊表的實現45

2.5.1雙鍊表的基本結構45

2.5.2雙鍊表的基本運算46

2.5.3STL中的雙鍊表——list47

2.6順序表與鍊表的比較48

2.6.1時間性能比較48

2.6.2空間性能比較48

2.7工程實踐和思考49

問題1：不支持指針的高級語言如何實現鍊表?49

問題2：隨機梯度下降算法52

問題3：作業系統的記憶體如何管理？58

問題4：荷蘭國旗問題62

習題264

第3章線性表的擴展69

3.1各種擴展線性表69

3.1.1棧69

3.1.2佇列70

3.1.3串70

3.1.4多維數組72

3.2棧的實現73

3.2.1順序棧73

3.2.2鏈棧75

3.2.3棧與遞歸76

3.2.4STL中的棧——stack78

3.3佇列的實現79

3.3.1循環佇列79

3.3.2鏈佇列82

3.3.3STL中的佇列84

3.4串的實現87

3.4.1串的存儲結構87

3.4.2串的模式匹配88

3.4.3KMP算法90

3.4.4STL中的串——string94

3.5多維數組95

3.5.1多維數組的存儲95

3.5.2稀疏矩陣的表示和計算97

3.6經典算法分析105

3.6.1窮舉法——背包問題105

3.6.2貪心算法——背包問題106

3.6.3分治法——漢諾塔遊戲107

3.6.4回溯法——迷宮問題109

3.6.5動態規劃——背包問題113

3.7工程實踐和思考115

問題1：優先權佇列的調度115

問題2：大規模矩陣計算118

問題3：BMP圖像處理121

問題4：基於KNN算法的手寫數字識別130

習題3137

第4章樹140

4.1基本概念140

4.1.1樹140

4.1.2二叉樹141

4.1.3森林144

4.2基本操作145

4.2.1樹的遍歷145

4.2.2二叉樹的遍歷145

4.2.3森林的遍歷147

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

4.3存儲結構149

4.3.1樹的存儲結構149

4.3.2二叉樹的存儲結構152

4.4二叉樹的實現155

4.4.1二叉樹的聲明155

4.4.2二叉樹的關鍵算法155

4.4.3遞歸算法的規律159

4.5哈夫曼樹的套用164

4.5.1哈夫曼樹的定義與存儲結構164

4.5.2哈夫曼樹的構造167

4.5.3哈夫曼編碼表的構建168

4.5.4哈夫曼編、解碼的實現169

4.6工程實踐和思考170

問題1:構建算術表達式二叉樹170

問題2:在通信系統中如何使用哈夫曼樹壓縮信息？173

問題3：莫爾斯碼174

習題4179

第5章圖183

5.1基本概念183

5.1.1圖的定義183

5.1.2圖的基本術語183

5.2圖的存儲結構186

5.2.1鄰接矩陣187

5.2.2鄰接表188

5.2.3十字鍊表190

5.2.4鄰接多重表191

5.2.5邊集數組191

5.2.6圖的存儲結構比較192

5.3圖的實現192

5.3.1圖的構建192

5.3.2圖的遍歷194

5.3.3圖的析構198

5.4最小生成樹198

5.4.1普里姆算法199

5.4.2克魯斯卡爾算法203

5.5最短路徑207

5.5.1Dijkstra算法208

5.5.2Floyd算法211

5.6工程實踐與思考213

問題1:圖著色問題213

問題2:捷運換乘線路查找問題217

問題3:教學計畫安排問題218

問題4：多層神經網路模型220

習題5229

第6章查找232

6.1基本概念232

6.1.1靜態查找和動態查找232

6.1.2查找的性能評估232

6.1.3查找結構分類233

6.2線性表查找233

6.2.1順序查找233

6.2.2折半查找234

6.2.3索引查找237

6.3樹表查找238

6.3.1二叉排序樹238

6.3.2平衡二叉樹244

6.3.3B-樹247

6.3.4STL中的樹表——set和map253

6.4散列查找256

6.4.1散列技術256

6.4.2散列函式設計257

6.4.3衝突處理258

6.4.4常用的散列函式261

6.5工程實踐和思考263

問題1：自然語言處理的基本問題——中文分詞263

問題2：資料庫索引結構266

問題3：搜尋引擎中的索引結構271

習題6275

第7章排序277

7.1基本概念277

7.1.1相關概念277

7.1.2排序性能評估278

7.1.3排序方法分析278

7.2簡單排序279

7.2.1起泡排序279

7.2.2直接插入排序281

7.2.3簡單選擇排序283

7.3複雜排序285

7.3.1希爾排序285

7.3.2快速排序287

7.3.3堆排序289

7.3.4歸併排序293

7.3.5排序方法比較297

7.3.6STL中常用的排序算法298

7.4非比較的排序算法299

7.4.1計數排序299

7.4.2桶排序301

7.4.3基數排序303

7.5工程實踐和思考304

問題1：電話號碼排序304

問題2：大數據下的排序問題307

習題7311

參考文獻313

附錄314

附錄1異常處理314

附錄2模板315