數據結構與算法（Python語言版）

目錄

第1章緒論/1

11算法/1

1.1.1算法的基本概念/1

1.1.2算法的表示/2

1.1.3算法的設計/4

12算法的分析評價/6

1.2.1時間復雜度分析/6

1.2.2時間復雜度分析舉例/8

1.2.3空間復雜度分析/10

13數據結構/11

1.3.1數據與數據結構定義/11

1.3.2數據類型與數據抽象/15

1.3.3抽象數據類型/16

1.3.4數據結構和算法的關系/17

小結/18

習題/19

第2章Python編程基礎/20

21Python數據類型/20

2.1.1常用數據類型/20

2.1.2變量、運算符和表達式/21

2.1.3內置數據類型的常見運算和操作/23

22Python控制結構/27

2.2.1順序結構/27

2.2.2選擇結構/28

2.2.3循環結構/30

23Python函數/34

2.3.1函數概述/34

2.3.2函數的聲明和調用/34

2.3.3參數傳遞/36

2.3.4函數的返回值/38

2.3.5變量的作用域/38

2.3.6函數式編程/40

24Python面向對象編程/42

2.4.1面向對象程序設計/42

2.4.2類的定義和實例化/43

2.4.3屬性/45

2.4.4方法/47

2.4.5類的繼承/48

2.4.6類的特殊方法/50

2.4.7對象的引用、淺拷貝和深拷貝/54

25抽象數據類型面向對象實現/55

2.5.1抽象數據類型和麵向對象方法/55

2.5.2有理數的抽象數據類型表示/55

2.5.3有理數抽象數據類型的Python語言實現/56

小結/58

習題/58

第3章線性表/63

31線性表的概念/63

3.1.1基本術語和概念/63

3.1.2線性表的操作/64

3.1.3線性表的實現基礎/65

32順序表/65

3.2.1順序表的定義/65

3.2.2順序表的基本實現/66

3.2.3順序表例題/68

33單鏈表/69

3.3.1單鏈表的定義/69

3.3.2單鏈表的基本實現/70

3.3.3單鏈表基本操作的實現/72

3.3.4單鏈表例題/76

34鏈表的變形與操作/80

3.4.1帶尾結點引用的單鏈表/80

3.4.2循環單鏈表/82

3.4.3雙向鏈表/86

3.4.4不同結構鏈表總結/89

35有序表及其應用/90

3.5.1有序表的定義/90

3.5.2有序表例題/90

小結/92

習題/93

第4章字符串/98

41字符串的概念/98

4.1.1基本術語和概念/98

4.1.2串的基本操作/99

4.1.3Python中的字符串/100

4.1.4基本串操作例題/100

42字符串匹配算法/103

4.2.1字符串匹配/103

4.2.2樸素的串匹配算法/103

4.2.3無回溯串匹配算法（KMP算法）/105

4.2.4串模式匹配例題/110

小結/114

習題/114

第5章棧和隊列/116

51棧的概念與實現/116

5.1.1棧的結構和操作特點/116

5.1.2棧的表示和實現/117

52棧的應用舉例/121

5.2.1括號匹配問題/122

5.2.2後綴表達式求值/124

5.2.3從中綴表達式到後綴表達式的轉換/126

53隊列的概念與實現/129

5.3.1隊列的結構特點與操作/129

5.3.2隊列的表示和實現/130

54雙端隊列/134

小結/136

習題/137

第6章遞歸/142

61遞歸的定義/142

6.1.1基本概念/142

6.1.2簡單遞歸操作例題/143

6.1.3漢諾塔問題/146

62遞歸的可視化/147

6.2.1遞歸執行過程/147

6.2.2遞歸過程可視化/147

6.2.3遞歸圖形化展示/149

63回溯法/150

6.3.1回溯的概念/150

6.3.2組合問題/151

6.3.3回溯法例題/153

64動態規劃初步/157

6.4.1動態規劃的概念/157

6.4.2動態規劃的應用/158

6.4.3動態規劃例題/161

小結/162

習題/162

第7章二叉樹和樹/166

71樹狀結構基本概念/166

7.1.1樹的定義和基本術語/166

7.1.2樹狀結構的描述/167

7.1.3二叉樹的概念/168

7.1.4二叉樹的性質/169

72二叉樹的存儲/171

7.2.1二叉樹的順序存儲/171

7.2.2二叉樹的鏈式存儲/171

73二叉樹的遍歷及其實現/172

7.3.1二叉樹按層次遍歷的實現/173

7.3.2二叉樹深度優先遍歷的遞歸實現/175

7.3.3二叉樹深度優先遍歷的非遞歸實現/179

74二叉樹遍歷算法的應用/180

75優先隊列與堆/188

7.5.1優先隊列的概念及應用/188

7.5.2堆的概念及實現/190

76哈夫曼樹/195

7.6.1基本概念/195

7.6.2Huffman樹的構造/196

7.6.3最優前綴編碼/198

77樹和森林的存儲和遍歷 /199

7.7.1樹和森林的遍歷/199

7.7.2樹的存儲表示/200

7.7.3樹的遍歷算法實現/204

小結/207

習題/208

第8章圖及其算法/213

81圖的概念/213

8.1.1基本術語和概念/213

8.1.2其他術語和概念/214

82圖的表示與實現/216

8.2.1鄰接矩陣/216

8.2.2鄰接表/217

8.2.3圖表示的Python實現/218

83圖的遍歷及其應用/223

8.3.1深度優先遍歷圖/223

8.3.2廣度優先遍歷圖/225

8.3.3圖遍歷算法的簡單應用/226

8.3.4圖遍歷算法的高階應用/228

84拓撲排序/234

85並查集/236

86連通網的最小生成樹/242

87最短路徑問題/246

8.7.1單源最短路徑的Dijkstra算法/247

8.7.2求解任意頂點間最短路徑的Floyd算法/248

小結/249

習題/250

第9章排序和查找/255

91查找/255

9.1.1基本術語和概念/255

9.1.2順序查找/256

9.1.3二分查找/258

92排序/263

9.2.1基本術語和概念/263

9.2.2選擇排序/265

9.2.3冒泡排序/267

9.2.4插入排序/269

9.2.5希爾排序/273

9.2.6歸並排序/275

9.2.7快速排序/278

小結/280

習題/280

附錄ALeetCode網站在線編程說明/283

參考文獻/285