數據結構和算法：Python和C++語言描述

內容簡介

本書使用Python 和C++兩種程式語言來介紹數據結構。全書內容共15 章。書中首先介紹了抽象與分析、數據的抽象等數據結多元端構的基本原理和知識，然後結合Python 的特點介紹了容器類、鏈式結構和疊代器、堆疊和佇列、遞歸、樹；隨後，簡單介紹了C++語言的知識，並進一步講解了C++類、C++的動態記憶體、C++的鏈式結構、C++模板、堆、平衡樹和散列表、圖等內容；最後對算法技術進行了總結。每章最後給出了一些練習題和簽屑編程練習，幫助讀者複習鞏固所學的知識。

本書適合作為高等院校計算機相關專業數據結構課程的教材和參考書，也適合對數據結構知識感興趣的讀者學習參考。

圖書目錄

第　1 章抽象與分析　1

1.1　概要　1

1.1.1　大型編程.　1

1.1.2　前方的道路　2

1.2　功能的抽象　3

1.2.1　契約式設計　3

1.2.2　驗證先驗條件　6

1.2.3　自上而下的設計.　9

1.2.4　記錄副作用.　11

1.3　算法分析.　12

1.3.1　線性搜尋　12

1.3.2　二分搜尋　14

1.3.3　非正式的算法比較.　15

1.3.4　算法的正式分析　17

1.3.5　大O 符號與Θ 符號　21

1.4　小結　23

1.5　練習　23

第　2 章數據的抽象.　27

2.1　概要　27

2.2　抽象數據類型　27

2.2.1　從數據類型悼尋挨到抽象數據

類型.　28

2.2.2　定義抽象數據類型.　28

2.2.3　實現抽象數據類型.　30

2.3　抽象數據類型和對象　32

2.3.1　規範.　32

2.3.2　實現.　34

2.3.3　改變存儲方式　35

2.3.4　面向對象的設計和編程.　36

2.4　抽象數據類型的實例：

數據集（Dataset）　38

2.4.1　面向對象設計的過程　38

2.4.2　定義一個抽象數據

類型.　39

2.4.3　實現這個抽象數據類型.　41

2.5　抽象數據類型的實例：

有理數（Rational）　.42

2.5.1　運算符重載.42

2.5.2　有理數（Rational）類44

2.6　增淚禁凝量開發以及單元測試45

2.7　小結48

2.8　練習48

第3　章容器類52

3.1　概要52

3.2　Python 的列表52

3.3　順序集合：撲克牌牌組53

3.4　有序集合：手牌.56

3.4.1　創建橋牌的手牌56

3.4.2　比較撲克牌.58

3.4.3　撲克牌排序.59

3.5　Python 里列表的實現61

3.5.1　基於數組的列表61

3.5.2　效率分析62

3.6　Python 的字典（選讀） .63

3.6.1　字典抽象數據類型63

3.6.2　熟悉Python 字典.64

3.6.3　字典的實現.65

3.6.4　擴展示例：馬爾可夫鏈67

3.7　小結70

3.8　練習71

第4　章鏈式結構和疊代器.75

4.1　概要75

4.2　Python 的記憶體模型75

傳遞參數80

4.3　鍊表實現.81

4.4　鍊表抽象數據類型的實現.85

4.5　疊代器95

4.5.1　Python 的疊代器95

4.5.2　在鍊表（LList）里遷妹講

添加疊代器.96

4.5.3　通過Python 的生成器來

疊代　97

4.6　基於游標的列表API（選讀） .　99

4.6.1　游標（Cursor）的

API　99

4.6.2　Python 的游標列表

（CursorList）　100

4.6.3　鏈式結構的游標列表

（CursorList）　102

4.7　鍊表vs 數組　104

4.8　小結.　104

4.9　練習.　105

第5　章堆疊和佇列　109

5.1　概要.　109

5.2　堆疊.　109

5.2.1　堆疊抽象數據類型　109

5.2.2　堆疊的簡單套用　110

5.2.3　堆疊的實現　112

5.2.4　應用程式：處理算術

方程.　113

5.2.5　應用程式：語法的處理

（選讀）　.　116

5.3　佇列.　119

5.3.1　佇列抽象數據類型　119

5.3.2　佇列的簡單套用　120

5.4　佇列的實現.　121

5.5　應晚棗旬府用程式示例：佇列的模擬

（選讀）　.　123

5.6　小結.　128

5.7　練習.　128

第6　章遞歸　133

6.1　概要.　133

6.2　遞歸定義　134

6.3　簡單的遞歸示例催您艱灑　136

6.3.1　示例：字元串反轉　136

6.3.2　示例：字謎　137

6.3.3　示例：快速計算指數.　138

6.3.4　示例：二分搜尋　139

6.4　遞歸的分析.　140

6.5　排序.142

6.5.1　遞歸設計：歸併排序142

6.5.2　分析歸併排序.144

6.6　一個“難”題：漢諾塔146

6.7　小結.149

6.8　練習.150

第7　章樹156

7.1　概要.156

7.2　樹的術語156

7.3　示例應用程式：表達式樹158

7.4　樹的存儲方式159

7.5　套用：二叉搜尋樹.160

7.5.1　二分查找屬性.160

7.5.2　實現一個二叉搜尋樹161

7.5.3　遍歷整個二叉搜尋樹

（BST）　166

7.5.4　二叉搜尋樹（BST）的

運行時分析168

7.6　使用二叉搜尋樹（BST）來

實現映射（選讀）169

7.7　小結.171

7.8　練習.172

第8　章為Python 程式設計師準備的

C++簡介.177

8.1　概要.177

8.2　C++的歷史和背景178

8.3　注釋、代碼塊、變數名和

關鍵字.182

8.4　數據類型和變數聲明183

8.5　Include 語句、命名空間

以及輸入/輸出186

8.6　編譯.189

8.7　表達式和運算符優先權191

8.8　條件語句193

8.9　數據類型轉換196

8.10　循環語句197

8.11　數組199

8.11.1　一維數組199

8.11.2　多維數組201

8.11.3　字元數組.　201

8.12　函式的細節　202

8.12.1　聲明、定義以及原型.　202

8.12.2　值傳遞　205

8.12.3　引用傳遞.　205

8.12.4　將數組作為參數傳遞.　206

8.12.5　常量參數　208

8.12.6　默認參數.　208

8.13　頭檔案和內聯函式　209

8.14　斷言與測試　213

8.15　變數的作用域以及生命周期.　214

8.16　Python 程式設計師編寫C++程式

時的常見錯誤.　215

8.17　其他的C++相關話題

（選讀）　216

8.17.1　C++的Switch 語句.　216

8.17.2　創建C++的命名空間.　218

8.17.3　全局變數.　219

8.18　小結　220

8.19　練習　220

第9　章 C++類.　224

9.1　基本的語法和語義.　224

9.2　字元串　232

9.3　檔案輸入和輸出　234

9.4　運算符重載.　236

9.5　類變數和方法　242

9.6　小結.　246

9.7　練習.　246

第　10 章 C++的動態記憶體.　250

10.1　概要　250

10.2　C++的指針　254

10.3　動態數組　259

10.4　動態記憶體類　263

10.4.1　析構函式.　263

10.4.2　複製構造函式　265

10.4.3　賦值運算符　268

10.4.4　完整的動態數組類　270

10.4.5　引用返回類型　275

10.5　動態記憶體錯誤.　276

10.5.1　記憶體泄漏.276

10.5.2　訪問無效記憶體277

10.5.3　記憶體錯誤總結280

10.6　小結281

10.7　練習281

第　11 章 C++的鏈式結構285

11.1　概要285

11.2　C++鏈式結構的類286

11.3　C++鍊表.288

11.4　C++連結的動態記憶體錯誤.298

11.5　小結299

11.6　練習300

第　12 章 C++模板.302

12.1　概要302

12.2　模板方法303

12.3　模板類.305

12.3.1　標準模板庫的

vector　類305

12.3.2　用戶定義的模板類.308

12.4　小結　311

12.5　練習312

第　13 章堆、平衡樹和散列表314

13.1　概要314

13.2　優先佇列和堆.314

13.2.1　堆排序320

13.2.2　關於堆和優先佇列

實現的說明320

13.3　平衡樹.321

13.4　其他的樹結構.329

13.5　散列表.329

13.6　小結339

13.7　練習339

第　14 章圖.343

14.1　概要343

14.2　圖數據結構344

14.3　最短路徑算法.347

14.3.1　無權最短路徑347

14.3.2　加權最短路徑350

14.4　深度優先算法.353

14.5　最小生成樹　357

14.5.1　Kruskal 算法.　358

14.5.2　不交集數據結構.　358

14.5.3　Prim 算法　361

14.6　小結　361

14.7　練習　362

第　15 章算法技術　365

15.1　概要　365

15.2　分治算法　365

15.2.1　分析遞歸函式　366

15.2.2　快速排序.368

15.3　貪心算法372

15.4　動態規劃378

15.4.1　最長公共子序列379

15.4.2　記憶化382

15.4.3　矩陣鏈乘法382

15.5　NP 完全問題383

15.6　小結384

15.7　練習385

術語表387

數據結構和算法：Python和C++語言描述

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條