數據結構與算法：Python語言描述(2021年機械工業出版社出版的圖書)

《數據結構與算法：Python語言描述》是2021年機械工業出版社出版的圖書，作者是裘宗燕。

基本介紹

• 中文名：數據結構與算法：Python語言描述
• 作者：裘宗燕
• 出版社：機械工業出版社
• 出版時間：2021年12月1日
• 開本：16 開
• 裝幀：平裝
• ISBN：9787111694250

內容簡介

Python是國際流行的用於教授入門級程式設計課程的語言，國內高校也開始使用。本書是結合國內數據結構課程現狀，以Python作為工作語言，編撰的一本數據結構教程。書中結合抽象數據類型結構的思想，基於Python的面向對象機制，討論了各種基本數據結構的思想、性質、問題和實現，相關算法的設計、實現和特性等。書中還研究了一些數據結構的套用案例。本書要求學習者已有基本Python程式設計的知識和經驗，可以作為基於Python的計算機基礎課程中的數據結構課程教材，也可以作為學習Python語言基本內容之後的面向對象等高級編程技術的進階讀物。

作者簡介

裘宗燕: 北京大學數學學院信息科學系教授。長期從事計算機軟體與理論、程式設計語言和符號計算方面的研究和教學工作。已出版多部著作和譯著，包括《程式設計語言基礎》（譯著，北京大學出版社，1990），《Mathematica數學軟體系統的套用與程式設計》（編著，北京大學出版社，1994），《計算概論（上）》（合著，高等教育出版社，1997），《從問題到程式—程式設計與C語言引論》（編著，北京大學出版社，1999）等；自2000年以來，他先後為機械工業出版社華章分社翻譯了《程式設計實踐》（2000），《C++程式設計語言（特別版）》（2001），《C++語言的設計和演化》（2002），《程式設計語言——概念和結構》（2002），《從規範出發的程式設計》（2003），《電腦程式的構造和解釋》（2004）等一系列經典著作，他認真的工作作風、嚴謹的治學態度，以及所做出的巨大貢獻，贏得廣大讀者的好評。 在北京大學教授的主要課程：計算概論（一年級本科生，主要內容為C語言程式設計），程式設計技術與方法（本科生），程式設計語言原理（研究生），算法和數據結構（本科生），算法設計與分析（本科生和研究生），數理邏輯（本科生）等。 點擊進入[URL=http://www.math.pku.edu.cn/teachers/qiuzy/]作者主頁[/URL]。

圖書目錄

前言

第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　算法的代價及其度量13

　　1.3.3　算法分析19

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

　1.4　數據結構24

　　1.4.1　數據結構及其分類24

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

　　1.4.3　Python對象和數據結構30

　練習32

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

　2.1　抽象數據類型34

　　2.1.1　數據類型和數據構造34

　　2.1.2　抽象數據類型的概念36

　　2.1.3　抽象數據類型的描述37

　2.2　Python的類和面向對象編程39

　　2.2.1　類的定義和使用39

　　2.2.2　繼承44

　　2.2.3　異常類和自定義異常48

　　2.2.4　本書採用的ADT描述形式50

　總結50

　練習51

第3章　線性表53

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

　　3.1.1　表的概念和性質53

　　3.1.2　表抽象數據類型53

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

　3.2　順序表56

　　3.2.1　基本實現方式56

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

　　3.2.3　順序表的實現結構61

　　3.2.4　Python的list64

　　3.2.5　順序表的簡單總結65

　3.3　連結表66

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

　　3.3.2　單鍊表67

　　3.3.3　單鍊表類的實現72

　3.4　鍊表的變形和操作75

　　3.4.1　單鍊表的簡單變形75

　　3.4.2　循環單鍊表78

　　3.4.3　雙鍊表79

　　3.4.4　兩個鍊表操作81

　　3.4.5　在順序表里實現“鍊表”85

　　3.4.6　不同鍊表的簡單總結86

　3.5　表的套用87

　　3.5.1　Josephus問題和基於數組概念的解法87

　　3.5.2　基於順序表的解88

　　3.5.3　基於循環單鍊表的解88

*3.6　廣義表和數組　本書中標星號的小節為選學/選講內容。89

　　3.6.1　廣義表89

　　3.6.2　數組92

　　3.6.3　矩陣94

　總結97

　練習98

第4章　字元串102

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

　　4.1.1　字元串的相關概念102

　　4.1.2　字元串抽象數據類型104

　4.2　字元串的實現104

　　4.2.1　基本實現問題和技術104

　　4.2.2　實際語言裡的字元串105

　　4.2.3　Python的字元串106

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

　　4.3.1　字元串匹配問題107

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

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

　4.4　字元串匹配問題115

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

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

*4.5　Python正則表達式119

　　4.5.1　正則表達式標準庫包re119

　　4.5.2　基本情況119

　　4.5.3　主要操作120

　　4.5.4　正則表達式的構造121

　　4.5.5　正則表達式的使用127

　總結127

　練習128

第5章　棧和佇列130

　5.1　概述130

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

　　5.1.2　套用環境131

　5.2　棧：概念和實現131

　　5.2.1　棧抽象數據類型131

　　5.2.2　棧的順序表實現132

　　5.2.3　棧的連結表實現134

　5.3　棧的套用134

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

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

　　5.3.3　棧與遞歸144

　5.4　佇列149

　　5.4.1　佇列抽象數據類型149

　　5.4.2　佇列的連結表實現150

　　5.4.3　佇列的順序表實現150

　　5.4.4　佇列的list實現152

　　5.4.5　佇列的套用155

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

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

　　5.5.2　求解迷宮的算法159

　　5.5.3　迷宮問題和搜尋161

　5.6　幾點補充166

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

　　5.6.2　順序實現和連結實現166

　總結167

　練習168

第6章　二叉樹和樹170

　6.1　二叉樹170

　　6.1.1　概念和性質170

　　6.1.2　抽象數據類型175

　　6.1.3　遍歷二叉樹176

　6.2　二叉樹的list實現177

　　6.2.1　設計和實現178

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

　6.3　優先佇列182

　　6.3.1　概念182

　　6.3.2　基於線性表的實現183

　　6.3.3　樹形結構和堆185

　　6.3.4　優先佇列的堆實現186

　　6.3.5　堆的套用：堆排序189

　6.4　套用：離散事件模擬190

　　6.4.1　通用的模擬框架191

　　6.4.2　海關檢查站模擬系統192

　6.5　二叉樹的類實現196

　　6.5.1　二叉樹結點類197

　　6.5.2　遍歷算法198

　　6.5.3　二叉樹類202

　6.6　哈夫曼樹203

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

　　6.6.2　哈夫曼算法的實現204

　　6.6.3　哈夫曼編碼205

　6.7　樹和樹林207

　　6.7.1　實例和表示207

　　6.7.2　定義和相關概念208

　　6.7.3　抽象數據類型和操作210

　　6.7.4　樹的實現211

　　6.7.5　樹的Python實現212

*6.8　等價類和查並集214

　　6.8.1　概念和問