數據結構與算法：Python語言描述

一本有關數據結構和算法的優秀譯本，使用Python語言進行描述，內容詳盡。

基本介紹

• 書名：《數據結構與算法：Python語言描述》
• 作者：裘宗燕
• ISBN：9787111521181
• 類別：數據結構，算法，Python，編程
• 定價：45
• 出版社：機械工業出版社
• 出版時間：2017-07-13
• 裝幀：平裝
• 開本：16開

基本信息

數據結構與算法：Python語言描述

書號：52118

ISBN：978-7-111-52118-1

作者：裘宗燕

印次：1-4

開本：16開

字數：563千字

定價：45.0

所屬叢書：面向CS2013計算機專業規劃教材

出版日期：2017-07-13

內容簡介

本書基於Python語言介紹了數據結構與算法的基本知識，主要內容包括抽象數據類型和Python面向對象程式設計、線性表、字元串、棧和佇列、二叉樹和樹、集合、排序以及算法的基本知識。本書延續問題求解的思路，從解決問題的目標來組織教學內容，注重理論與實踐的並用。

目錄信息

前言

第1章緒論1

1.1計算機問題求解1

1.1.1程式開發過程1

1.1.2　一個簡單例子3

1.2　問題求解：交叉路口的紅綠燈安排4

1.2.1問題分析和嚴格化5

1.2.2圖的頂點分組和算法6

1.2.3算法的精化和Python描述7

1.2.4討論8

1.3算法和算法分析10

1.3.1問題、問題實例和算法10

1.3.2算法的代價及其度量14

1.3.3算法分析19

1.3.4Python程式的計算代價（複雜度）21

1.4數據結構23

1.4.1數據結構及其分類24

1.4.2計算機記憶體對象表示26

1.4.3Python對象和數據結構30

練習32

第2章抽象數據類型和Python類34

2.1抽象數據類型34

2.1.1數據類型和數據構造34

2.1.2抽象數據類型的概念36

2.1.3抽象數據類型的描述37

2.2Python的類39

2.2.1有理數類39

2.2.2類定義進階40

2.2.3本書採用的ADT描述形式43

2.3類的定義和使用44

2.3.1類的基本定義和使用44

2.3.2實例對象：初始化和使用45

2.3.3幾點說明47

2.3.4繼承49

2.4Python異常53

2.4.1異常類和自定義異常53

2.4.2異常的傳播和捕捉54

2.4.3內置的標準異常類54

2.5類定義實例：學校人事管理系統中的類55

2.5.1問題分析和設計56

2.5.2人事記錄類的實現57

2.5.3討論62

本章總結63

練習64

第3章線性表66

3.1線性表的概念和表抽象數據類型66

3.1.1表的概念和性質66

3.1.2表抽象數據類型67

3.1.3線性表的實現：基本考慮69

3.2順序表的實現69

3.2.1基本實現方式69

3.2.2順序表基本操作的實現71

3.2.3順序表的結構74

3.2.4Python的list76

3.2.5順序表的簡單總結78

3.3連結表79

3.3.1線性表的基本需要和連結表79

3.3.2單鍊表79

3.3.3單鍊表類的實現84

3.4鍊表的變形和操作88

3.4.1單鍊表的簡單變形88

3.4.2循環單鍊表91

3.4.3雙鍊表92

3.4.4兩個鍊表操作95

3.4.5不同鍊表的簡單總結98

3.5表的套用99

3.5.1Josephus問題和基於“數組”概念的解法99

3.5.2基於順序表的解100

3.5.3基於循環單鍊表的解101

本章總結102

練習103

第4章　字元串107

4.1　字元集、字元串和字元串操作107

4.1.1　字元串的相關概念107

4.1.2　字元串抽象數據類型109

4.2　字元串的實現109

4.2.1　基本實現問題和技術109

4.2.2　實際語言裡的字元串110

4.2.3　Python的字元串111

4.3　字元串匹配（子串查找）112

4.3.1　字元串匹配112

4.3.2　串匹配和樸素匹配算法113

4.3.3　無回溯串匹配算法（KMP算法）115

4.4　字元串匹配問題119

4.4.1　串匹配/搜尋的不同需要120

4.4.2　一種簡化的正則表達式122

4.5　Python正則表達式123

4.5.1　概況124

4.5.2　基本情況124

4.5.3　主要操作125

4.5.4　正則表達式的構造126

4.5.5　正則表達式的使用132

本章總結132

練習133

第5章　棧和佇列135

5.1　概述135

5.1.1　棧、佇列和數據使用順序135

5.1.2　套用環境136

5.2　棧：概念和實現136

5.2.1　棧抽象數據類型137

5.2.2　棧的順序表實現137

5.2.3　棧的連結表實現139

5.3　棧的套用140

5.3.1　簡單套用：括弧匹配問題140

5.3.2　表達式的表示、計算和變換142

5.3.3　棧與遞歸149

5.4　佇列155

5.4.1　佇列抽象數據類型155

5.4.2　佇列的連結表實現155

5.4.3　佇列的順序表實現156

5.4.4　佇列的list實現158

5.4.5　佇列的套用160

5.5　迷宮求解和狀態空間搜尋162

5.5.1　迷宮求解：分析和設計162

5.5.2　求解迷宮的算法164

5.5.3　迷宮問題和搜尋167

5.6　幾點補充171

5.6.1　幾種與棧或佇列相關的結構171

5.6.2　幾個問題的討論172

本章總結173

練習173

第6章　二叉樹和樹176

6.1　二叉樹：概念和性質176

6.1.1　概念和性質177

6.1.2　抽象數據類型181

6.1.3　遍歷二叉樹181

6.2　二叉樹的list實現183

6.2.1　設計和實現183

6.2.2　二叉樹的簡單套用：表達式樹185

6.3　優先佇列188

6.3.1　概念188

6.3.2　基於線性表的實現189

6.3.3　樹形結構和堆191

6.3.4　優先佇列的堆實現192

6.3.5　堆的套用：堆排序195

6.4　套用：離散事件模擬196

6.4.1　通用的模擬框架197

6.4.2　海關檢查站模擬系統198

6.5　二叉樹的類實現202

6.5.1　二叉樹結點類203

6.5.2　遍歷算法204

6.5.3　二叉樹類208

6.6　哈夫曼樹209

6.6.1　哈夫曼樹和哈夫曼算法209

6.6.2　哈夫曼算法的實現210

6.6.3　哈夫曼編碼211

6.7　樹和樹林212

6.7.1　實例和表示213

6.7.2　定義和相關概念213

6.7.3　抽象數據類型和操作215

6.7.4　樹的實現216

6.7.5　樹的Python實現218

本章總結220

練習220

第7章圖224

7.1概念、性質和實現224

7.1.1　定義和圖示224

7.1.2　圖的一些概念和性質225

7.1.3　圖抽象數據類型227

7.1.4　圖的表示和實現228

7.2　圖結構的Python實現231

7.2.1　鄰接矩陣實現231

7.2.2　壓縮的鄰接矩陣（鄰接表）實現233

7.2.3　小結235

7.3　基本圖算法235

7.3.1　圖的遍歷236

7.3.2　生成樹238

7.4　最小生成樹240

7.4.1　最小生成樹問題240

7.4.2　Kruskal算法240

7.4.3　Prim算法243

*7.4.4　Prim算法的改進246

7.4.5　最小生成樹問題247

7.5　最短路徑248

7.5.1　最短路徑問題248

7.5.2　求解單源點最短路徑的Dijkstra算法248

7.5.3　求解任意頂點間最短路徑的Floyd算法252

7.6　AOV/AOE網及其算法255

7.6.1　AOV網、拓撲排序和拓撲序列255

7.6.2　拓撲排序算法257

7.6.3　AOE網和關鍵路徑258

7.6.4　關鍵路徑算法259

本章總結261

練習262

第8章　字典和集合265

8.1　數據存儲、檢索和字典265

8.1.1　數據存儲和檢索265

8.1.2　字典實現的問題267

8.2　字典線性表實現269

8.2.1　基本實現269

8.2.2　有序線性表和二分法檢索270

8.2.3　字典線性表總結272

8.3　散列和散列表273

8.3.1　散列的思想和套用273

8.3.2　散列函式275

8.3.3　衝突的內消解：開地址技術277

8.3.4　外消解技術280

8.3.5　散列表的性質280

8.4　集合282

8.4.1　集合的概念、運算和抽象數據類型282

8.4.2　集合的實現283

8.4.3　特殊實現技術：位向量實現285

8.5　Python的標準字典類dict和set286

8.6　二叉排序樹和字典287

8.6.1　二叉排序樹288

8.6.2　最佳二叉排序樹295

8.6.3　一般情況的最佳二叉排序樹297

8.7　平衡二叉樹302

8.7.1　定義和性質302

8.7.2　AVL樹類303

8.7.3　插入操作304

8.7.4　相關問題310

8.8　動態多分支排序樹311

8.8.1　多分支排序樹311

8.8.2　B樹312

8.8.3　B+ 樹314

本章總結315

練習316

第9章　排序319

9.1　問題和性質319

9.1.1　問題定義319

9.1.2　排序算法320

9.2　簡單排序算法323

9.2.1　插入排序323

9.2.2　選擇排序325

9.2.3　交換排序327

9.3　快速排序328

9.3.1　快速排序的表實現329

9.3.2　程式實現330

9.3.3　複雜度331

9.3.4　另一種簡單實現332

9.4　歸併排序332

9.4.1　順序表的歸併排序333

9.4.2　歸併算法的設計問題333

9.4.3　歸併排序函式定義333

9.4.4　算法分析335

9.5　其他排序方法335

9.5.1　分配排序和基數排序335

9.5.2　一些與排序有關的問題338

9.5.3　Python系統的list排序339

本章總結340

練習342

參考文獻344