數據結構（Python語言描述）（微課版）

李粵平，博士後，深圳職業技術學院副教授，主要研究方向為數據挖據和圖像識別。2008年，畢業於中山大學，獲博士學位。2009年-2012年在哈爾濱工業大學從事博士後研究，獲中國博士後科學基金一等資助。2010 年起開始進行機器學習方面的研究，並在模式識別領域也進行了多年研究，理論知識紮實。2012年，所在視覺計算與圖像處理研發團隊，獲學校科研團隊立項。主持開發了學校《Python語言及其應用》《數據結構》《電腦視覺》《算法分析與設計》和《機器學習實戰》等課程。

第 1章　緒論　1

1.1　基本概念和術語　1

1.2　邏輯結構與存儲結構　2

1.2.1　邏輯結構　2

1.2.2　存儲結構　3

1.3　算法　3

1.3.1　算法的定義　3

1.3.2　算法的特性　4

1.3.3　算法的設計要求　4

1.3.4　算法的效率評價　5

1.3.5　算法的時間復雜度　5

1.3.6　算法的空間復雜度　7

1.4　小結　7

1.5　習題　8

第　2章 線性表　10

2.1　定義　10

2.2　順序表　10

2.2.1　存儲結構　10

2.2.2　基本操作　11

2.3　單鏈表　14

2.3.1　存儲結構　14

2.3.2　基本操作　15

2.3.3　單鏈表與順序表的比較　22

2.4　雙鏈表　23

2.4.1　存儲結構　23

2.4.2　基本操作　23

2.5　循環鏈表　31

2.5.1　存儲結構　31

2.5.2　基本操作　31

2.6　鏈表的應用　36

2.6.1　約瑟夫環　36

2.6.2　多項式相加　39

2.7　小結　42

2.8　習題　43

第3章　棧和隊列　44

3.1　棧　44

3.1.1　定義　44

3.1.2　基本概念　44

3.1.3　順序棧　45

3.1.4　鏈棧　47

3.1.5　棧的應用　49

3.2　隊列　55

3.2.1　定義　55

3.2.2　基本概念　55

3.2.3　順序隊列　56

3.2.4　鏈式隊列　60

3.2.5　隊列的應用　63

3.3　小結　68

3.4　習題　68

第4章　串　70

4.1　串的定義　70

4.2　串的模式匹配算法　70

4.2.1　Brute-Force算法　71

4.2.2　KMP算法　73

4.3　小結　80

4.4　習題　80

第5章　廣義表　81

5.1　定義　81

5.2　基本術語　81

5.3　存儲結構　82

5.4　基本操作　83

5.5　廣義表的應用　83

5.6　小結　86

5.7　習題　86

第6章　樹和二叉樹　87

6.1　樹　87

6.1.1　樹的定義　87

6.1.2　基本術語　88

6.1.3　存儲結構　89

6.2　二叉樹　92

6.2.1　二叉樹的定義　92

6.2.2　二叉樹的基本形態　92

6.2.3　滿二叉樹和完全二叉樹　93

6.2.4　二叉樹的性質　94

6.2.5　順序存儲結構　95

6.2.6　鏈式存儲結構　96

6.2.7　遍歷二叉樹　98

6.2.8　二叉樹的其他操作　101

6.3　樹和森林　102

6.3.1　樹轉換為二叉樹　102

6.3.2　森林轉換為二叉樹　103

6.4　二叉樹的應用　104

6.5　小結　106

6.6　習題　106

第7章　常用二叉樹　108

7.1　二叉搜索樹　108

7.2　堆　116

7.2.1　堆的定義　116

7.2.2　存儲結構　116

7.2.3　基本操作　117

7.3　哈夫曼樹　121

7.3.1　基本術語　121

7.3.2　構造哈夫曼樹　122

7.3.3　哈夫曼樹的實現　123

7.4　平衡二叉樹　125

7.4.1　存儲結構　125

7.4.2　基本操作　126

7.5　小結　131

7.6　習題　132

第8章　圖　134

8.1　圖的基本概念　134

8.1.1　定義　134

8.1.2　基本術語　134

8.2　圖的存儲結構　140

8.2.1　鄰接矩陣　140

8.2.2　鄰接表　143

8.2.3　十字鏈表　149

8.3　圖的遍歷　153

8.3.1　深度優先遍歷　153

8.3.2　廣度優先遍歷　159

8.4　最小生成樹　164

8.4.1　Prim算法　164

8.4.2　Kruskal算法　170

8.5　最短路徑　175

8.5.1　Dijkstra算法　176

8.5.2　Floyd算法　181

8.5.3　Bellman-Ford算法　188

8.6　拓撲排序　193

8.7　AOE網和關鍵路徑　198

8.7.1　AOE網　198

8.7.2　求解關鍵路徑　198

8.8　小結　206

8.9　習題　207

第9章　排序　208

9.1　插入排序　208

9.1.1　直接插入排序　208

9.1.2　希爾排序　211

9.2　選擇排序　213

9.2.1　直接選擇排序　213

9.2.2　堆排序　215

9.3　交換排序　218

9.3.1　冒泡排序　218

9.3.2　快速排序　220

9.4　歸並排序　222

9.5　小結　225

9.6　習題　225

第　10章 查找　227

10.1　基本概念　227

10.2　順序查找　228

10.3　二分查找　228

10.4　分塊查找　229

10.5　B-樹　230

10.5.1　基本概念　230

10.5.2　基本操作　230

10.6　哈希表　235

10.6.1　基本概念　235

10.6.2　構造方法　235

10.6.3　處理沖突　236

10.7　小結　238

10.8　習題　238