數據結構：Python語言描述（簡體書）

《數據結構：Python語言描述》選擇Python作為描述語言，在選材與編排上，貼近當前普通高等院校“數據結構”課程的現狀和發展趨勢，內容難度適中，突出實用性和應用性。在內容選取與結構上，《數據結構：Python語言描述》並未對各種數據結構面面俱到，而是通過分類和講解典型結構，使讀者形成對數據結構的宏觀認識。《數據結構：Python語言描述》共8章，分別為緒論、線性表、棧和隊列、串和數組、樹形結構、圖、排序和查找。
《數據結構：Python語言描述》可作為高等院校計算機科學、軟件工程等相關專業的數據結構課程的教材，也可供程序員、系統工程師等相關人員閱讀參考。

通過圖表對數據結構及相應操作進行簡單、直接的描述

前言

第1章 緒論1

1.1 引言1

1.1.1 學習目的1

1.1.2 課程內容2

1.2 基本概念2

1.2.1 數據與數據結構2

1.2.2 數據類型與抽象數據類型6

1.3 算法9

1.3.1 算法的概念9

1.3.2 算法描述9

1.3.3 算法分析11

小結13

習題114

第2章 線性表17

2.1 線性表及其基本操作17

2.1.1 線性表的基本概念17

2.1.2 抽象數據類型描述18

2.1.3 線性表的存儲和實現19

2.2 線性表的順序存儲19

2.2.1 順序表19

2.2.2 順序表的基本操作實現21

2.3 線性表的鏈式存儲和實現25

2.3.1 單鏈表25

2.3.2 單鏈表的基本操作實現27

2.3.3 其他鏈表30

2.4 順序表與鏈表的比較31

2.5 實驗32

2.5.1 數組奇偶分割32

2.5.2 反轉單向鏈表33

2.5.3 鏈表實現34

小結38

習題238

第3章 棧和隊列41

3.1 棧41

3.1.1 棧的基本概念41

3.1.2 棧的抽象數據類型描述41

3.1.3 順序棧43

3.1.4 鏈棧46

3.2 隊列50

3.2.1 隊列的基本概念50

3.2.2 隊列的抽象數據類型描述50

3.2.3 順序隊列51

3.2.4 鏈隊列55

3.2.5 優先級隊列57

3.3 棧和隊列的比較60

3.4 實驗60

3.4.1 漢諾塔60

3.4.2 吃巧克力62

3.4.3 數頭頂63

3.4.4 整數變換64

3.4.5 表達式求值66

3.4.6 用隊列表示棧67

3.4.7 用棧表示隊列69

3.4.8 層次遍歷71

小結72

習題373

第4章 串和數組72

4.1 串76

4.1.1 串的基本概念76

4.1.2 串的抽象數據類型描述76

4.1.3 順序串78

4.1.4 鏈串82

4.2 串的模式匹配82

4.2.1 Brute Force算法83

4.2.2 KMP算法83

4.3 數組87

4.3.1 數組的基本概念87

4.3.2 數組的特性88

4.3.3 數組的遍歷88

4.4 特殊矩陣的壓縮存儲89

4.4.1 三角矩陣的壓縮存儲89

4.4.2 對稱矩陣的壓縮存儲90

4.4.3 對角矩陣的壓縮存儲90

4.4.4 稀疏矩陣的壓縮存儲91

4.5 實驗93

4.5.1 AZY的冒險島93

4.5.2 最大連續子數組94

4.5.3 合併有序數組95

4.5.4 最長上升子序列96

小結97

習題497

第5章 樹形結構101

5.1 樹101

5.1.1 樹的基本概念101

5.1.2 樹的術語102

5.2 二叉樹103

5.2.1 二叉樹的基本概念103

5.2.2 二叉樹的性質104

5.2.3 二叉樹的存儲結構105

5.2.4 二叉樹的遍歷106

5.2.5 二叉樹遍歷算法的應用110

5.2.6 二叉樹的建立112

5.3 哈夫曼樹及哈夫曼編碼114

5.3.1 哈夫曼樹的基本概念114

5.3.2 哈夫曼樹的構造115

5.3.3 哈夫曼編碼116

5.3.4 構造哈夫曼樹和哈夫曼編碼的類的描述116

5.4 樹和森林118

5.4.1 樹的存儲結構118

5.4.2 樹的遍歷規則119

5.5 實驗119

小結121

習題5121

第6章 圖125

6.1 圖概述125

6.1.1 圖的基本概念125

6.1.2 圖的抽象數據類型描述127

6.2 圖的存儲結構128

6.2.1 鄰接矩陣128

6.2.2 鄰接表132

6.3 圖的遍歷137

6.4 最小生成樹141

6.4.1 最小生成樹的基本概念141

6.4.2 Kruskal算法142

6.4.3 Prim算法142

6.5 最短路徑144

6.5.1 單源最短路徑144

6.5.2 求任意兩個頂點間的最短路徑146

6.6 拓撲排序和關鍵路徑148

6.6.1 拓撲排序148

6.6.2 關鍵路徑149

6.7 實驗151

小結152

習題6153

第7章 排序156

7.1 排序概述156

7.1.1 排序的基本概念156

7.1.2 排序算法的性能評價156

7.1.3 待排序的記錄和順序表的類描述156

7.2 插入排序157

7.2.1 直接插入排序157

7.2.2 希爾排序159

7.3 交換排序160

7.3.1 冒泡排序160

7.3.2 快速排序161

7.4 選擇排序164

7.4.1 直接選擇排序164

7.4.2 堆排序166

7.5 歸併排序168

7.6 實驗172

7.6.1 插入排序172

7.6.2 鏈表排序173

7.6.3 區間排序174

小結175

習題7176

第8章 查找179

8.1 查找的基本概念179

8.1.1 什麼是查找179

8.1.2 查找表179

8.1.3 平均查找長度180

8.2 靜態查找表180

8.2.1 順序查找180

8.2.2 二分查找181

8.2.3 分塊查找182

8.3 動態查找表182

8.3.1 二叉排序樹查找183

8.3.2 平衡二叉樹187

8.3.3 B-樹和B+樹189

8.4 哈希表查找190

8.4.1 哈希表的概念190

8.4.2哈希函數190

8.4.3 解決衝突的方法191

8.4.4 哈希表查找性能分析192

8.5 實驗195

8.5.1 尋找山形數組的頂點195

8.5.2 尋找和為指定值的數組元素195

8.5.3 尋找數組元素196

小結197

習題8198

附錄200

附錄A 名校數據結構程序設計考研真題解答(部分)200

附錄B 名詞索引206

參考文獻209