數據結構（Python語言描述）

目錄

第1章緒論11.1數據結構的相關概念1

1.2抽象數據類型3

1.2.1抽象數據類型的定義3

1.2.2抽象數據類型的描述4

1.3數據的邏輯結構與存儲結構7

1.3.1邏輯結構7

1.3.2存儲結構8

1.4算法的特性與算法的描述8

1.4.1算法的定義8

1.4.2算法的特性9

1.4.3算法的描述9

1.5算法分析11

1.5.1算法設計的要求11

1.5.2算法時間復雜度11

1.5.3算法空間復雜度16

1.6關於數據結構課程的地位及學習方法16

習題19

第2章線性表222.1線性表的定義及抽象數據類型22

2.1.1線性表的邏輯結構23

2.1.2線性表的抽象數據類型23

2.2順序表24

2.2.1表的順序存儲結構24

2.2.2順序表的基本操作25

2.2.3順序表的實現算法分析28

2.2.4順序表的優缺點28

2.2.5順序表應用舉例29

2.3單鏈表31

2.3.1單鏈表的存儲結構31

2.3.2單鏈表的基本操作33

2.3.3鏈式存儲結構與順序存儲結構的比較37

2.3.4單鏈表應用舉例38

2.4循環單鏈表43

2.4.1循環單鏈表的存儲結構43

2.4.2循環單鏈表應用舉例44

2.5雙向鏈表47

2.5.1雙向鏈表的存儲結構47

2.5.2雙向鏈表的插入和刪除操作47

2.5.3雙向鏈表應用舉例49

2.6綜合案例: 一元多項式的表示與相加51

2.6.1一元多項式的表示51

2.6.2一元多項式相加52

2.7小結56

2.8上機實驗57

2.8.1基礎實驗57

2.8.2綜合實驗: 一元多項式相乘58

習題59

〖1〗數據結構(Python語言描述)目錄

第3章棧和隊列623.1棧63

3.1.1棧的基本概念63

3.1.2棧的抽象數據類型64

3.1.3棧的順序表示與實現64

3.1.4棧的鏈式表示與實現67

3.1.5棧的典型應用72

3.2棧與遞歸80

3.2.1設計遞歸算法80

3.2.2分析遞歸調用過程82

3.2.3消除遞歸84

3.3隊列86

3.3.1隊列的定義與抽象數據類型86

3.3.2隊列的順序存儲及實現87

3.3.3隊列的鏈式存儲及實現93

3.4雙端隊列97

3.4.1什麽是雙端隊列97

3.4.2雙端隊列的應用98

3.5小結98

3.6上機實驗99

3.6.1基礎實驗99

3.6.2綜合實驗: 迷宮求解和模擬停車場管理100

習題102

第4章串、數組和廣義表1054.1串的定義及抽象數據類型105

4.1.1什麽是串106

4.1.2串的抽象數據類型106

4.2串的存儲表示107

4.2.1串的順序存儲結構108

4.2.2串的鏈式存儲結構108

4.2.3順序串應用舉例109

4.3串的模式匹配111

4.3.1BruteForce算法111

4.3.2KMP算法112

4.3.3模式匹配應用舉例117

4.4數組118

4.4.1數組的基本概念118

4.4.2數組的順序存儲結構119

4.4.3特殊矩陣的壓縮存儲120

4.4.4稀疏矩陣的壓縮存儲123

4.5廣義表130

4.5.1什麽是廣義表130

4.5.2廣義表的抽象數據類型131

4.5.3廣義表的頭尾鏈表表示131

4.5.4廣義表的擴展線性鏈表表示132

4.6小結133

4.7上機實驗134

4.7.1基礎實驗134

4.7.2綜合實驗: 稀疏矩陣相加134

習題135

第5章樹和二叉樹1385.1樹139

5.1.1樹的定義139

5.1.2樹的邏輯表示140

5.1.3樹的抽象數據類型140

5.2二叉樹142

5.2.1二叉樹的定義142

5.2.2二叉樹的性質143

5.2.3二叉樹的抽象數據類型145

5.2.4二叉樹的存儲表示146

5.3二叉樹的遍歷149

5.3.1二叉樹遍歷的定義149

5.3.2二叉樹的先序遍歷149

5.3.3二叉樹的中序遍歷151

5.3.4二叉樹的後序遍歷152

5.3.5二叉樹的層次遍歷154

5.4二叉樹的線索化155

5.4.1二叉樹的線索化定義155

5.4.2二叉樹線索化方法156

5.4.3線索二叉樹的遍歷157

5.4.4線索二叉樹的應用舉例159

5.5樹、森林與二叉樹161

5.5.1樹的存儲結構161

5.5.2樹轉換為二叉樹163

5.5.3森林轉換為二叉樹164

5.5.4二叉樹轉換為樹和森林165

5.5.5樹和森林的遍歷167

5.6並查集168

5.6.1並查集的定義168

5.6.2並查集的實現168

5.6.3並查集的應用171

5.7二叉樹的典型應用——哈夫曼樹172

5.7.1哈夫曼樹及應用173

5.7.2利用二叉樹求算術表達式的值178

5.8小結183

5.9上機實驗184

5.9.1基礎實驗184

5.9.2綜合實驗: 哈夫曼樹、二叉樹及應用184

習題185

第6章圖1906.1圖的定義與相關概念190

6.1.1圖的定義190

6.1.2圖的相關概念191

6.1.3圖的抽象數據類型193

6.2圖的存儲結構194

6.2.1鄰接矩陣194

6.2.2鄰接表197

6.2.3十字鏈表201

6.2.4鄰接多重表201

6.3圖的遍歷203

6.3.1圖的深度優先遍歷203

6.3.2圖的廣度優先遍歷205

6.4圖的連通性問題207

6.4.1無向圖的連通分量與生成樹207

6.4.2最小生成樹208

6.5有向無環圖214

6.5.1AOV網與拓撲排序214

6.5.2AOE網與關鍵路徑217

6.6最短路徑223

6.6.1利用Dijkstra算法求最短路徑223

6.6.2利用Floyd算法求最短路徑229

6.7圖的應用舉例233

6.7.1距離某個頂點的最短路徑長度為k的所有頂點233

6.7.2求圖中頂點u到頂點v的簡單路徑235

6.8小結237

6.9上機實驗237

6.9.1基礎實驗237

6.9.2綜合實驗: 圖的應用238

習題238

第7章查找2427.1查找的基本概念242

7.2靜態查找243

7.2.1順序表的查找243

7.2.2有序順序表的查找244

7.2.3索引順序表的查找247

7.3動態查找248

7.3.1二叉排序樹248

7.3.2平衡二叉樹254

7.3.3紅黑樹261

7.4B樹與B+樹269

7.4.1B樹269

7.4.2B+樹276

7.5哈希表277

7.5.1哈希表的定義277

7.5.2哈希函數的構造方法278

7.5.3處理沖突的方法279

7.5.4哈希表查找與分析280

7.5.5哈希表應用舉例281

7.6小結286

7.7上機實驗286

7.7.1基礎實驗286

7.7.2綜合實驗: 疫苗接種信息管理系統287

習題287

第8章排序2918.1排序的基本概念291

8.2插入排序292

8.2.1直接插入排序292

8.2.2折半插入排序294

8.2.3希爾排序294

8.2.4插入排序應用舉例295

8.3選擇排序296

8.3.1簡單選擇排序296

8.3.2堆排序297

8.4交換排序302

8.4.1冒泡排序302

8.4.2快速排序304

8.4.3交換排序應用舉例306

8.5歸並排序309

8.6基數排序311

8.6.1基數排序的過程和算法實現311

8.6.2基數排序應用舉例313

8.7小結316

8.8上機實驗317

8.8.1基礎實驗317

8.8.2綜合實驗: 疫苗接種信息管理系統V2.0318

習題319

參考文獻321