目　錄

第1章　緒論　1

1.1　數(shù)據(jù)結(jié)構(gòu)起源　1

1.2　基本概念和術(shù)語(yǔ)　1

1.2.1　基本概念　1

1.2.2　數(shù)據(jù)結(jié)構(gòu)　2

1.3　抽象數(shù)據(jù)類型　4

1.4　算法和算法分析　5

1.4.1　算法　5

1.4.2　算法的時(shí)間復(fù)雜度　5

1.4.3　最壞、最好和平均情況時(shí)間復(fù)

雜度　6

1.4.4　算法的空間復(fù)雜度　7

1.5　微課（一）　7

習(xí)　題　7

第2章　線性表　9

2.1　線性表定義　9

2.2　線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)　10

2.2.1　線性表的順序存儲(chǔ)結(jié)構(gòu)　10

2.2.2　順序表基本運(yùn)算的實(shí)現(xiàn)　10

2.3　線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn)　14

2.3.1　單鏈表的定義和表示　15

2.3.2　單鏈表基本運(yùn)算的實(shí)現(xiàn)　15

2.3.3　帶表頭結(jié)點(diǎn)的單鏈表　20

2.3.4　單循環(huán)鏈表　22

2.3.5　雙向鏈表　22

2.4　順序表與鏈表的比較　23

2.5　線性表的應(yīng)用　24

2.6　微課（二）　27

習(xí)　題　27

第3章　堆棧和隊(duì)列　29

3.1　堆�！�29

3.1.1　堆棧ADT　29

3.1.2　堆棧的順序表示　30

3.1.3　堆棧的鏈接表示　31

3.2　隊(duì)列　32

3.2.1　隊(duì)列ADT　32

3.2.2　隊(duì)列的順序表示　32

3.2.3　隊(duì)列的鏈接表示　35

3.3　表達(dá)式計(jì)算　35

3.3.1　中綴表達(dá)式　35

3.3.2　后綴表達(dá)式及其求值方法　36

3.3.3　中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式　39

3.4　遞歸　41

3.4.1　遞歸的概念　41

3.4.2　遞歸的實(shí)現(xiàn)　42

3.5　微課（三）　43

習(xí)　題　43

第4章　數(shù)組和字符串　45

4.1　數(shù)組　45

4.1.1　一維數(shù)組　45

4.1.2　二維數(shù)組　46

4.1.3　多維數(shù)組　47

4.2　數(shù)組的抽象數(shù)據(jù)類型　47

4.3　特殊矩陣　50

4.3.1　對(duì)稱矩陣　50

4.3.2　三角矩陣　51

4.4　稀疏矩陣　52

4.4.1　稀疏矩陣的抽象數(shù)據(jù)類型　52

4.4.2　稀疏矩陣的簡(jiǎn)單轉(zhuǎn)置算法　54

4.4.3　稀疏矩陣的快速轉(zhuǎn)置算法　55

4.5　字符串　57

4.5.1　字符串的抽象數(shù)據(jù)類型　57

4.5.2　簡(jiǎn)單字符串匹配算法　58

4.5.3　改進(jìn)的字符串匹配算法　61

4.6　微課（四）　65

習(xí)　題　65

第5章　樹(shù)和二叉樹(shù)　67

5.1　樹(shù)　67

5.1.1　樹(shù)的定義　67

5.1.2　基本術(shù)語(yǔ)　67

5.1.3　樹(shù)的抽象數(shù)據(jù)類型　68

5.1.4　樹(shù)的存儲(chǔ)表示　69

5.2　二叉樹(shù)　71

5.2.1　二叉樹(shù)的定義及主要性質(zhì)　71

5.2.2　二叉樹(shù)的抽象數(shù)據(jù)類型　73

5.2.3　二叉樹(shù)的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

表示　74

5.2.4　二叉樹(shù)的遍歷　75

5.2.5　線索二叉樹(shù)的基本概念和構(gòu)造　77

5.3　樹(shù)、森林與二叉樹(shù)的關(guān)系　78

5.3.1　樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換　79

5.3.2　樹(shù)和森林的遍歷　82

5.4　堆和優(yōu)先權(quán)隊(duì)列　83

5.4.1　堆　83

5.4.2　優(yōu)先權(quán)隊(duì)列　85

5.5　哈夫曼樹(shù)及其應(yīng)用　88

5.5.1　哈夫曼樹(shù)的基本概念　88

5.5.2　哈夫曼算法　89

5.5.3　哈夫曼編碼　90

5.6　微課（五）　92

習(xí)　題　92

第6章　集合和搜索　95

6.1　集合的表示　95

6.1.1　基本概念　95

6.1.2　動(dòng)態(tài)集ADT　96

6.1.3　集合的表示　96

6.2　順序搜索　97

6.2.1　無(wú)序表的順序搜索　97

6.2.2　有序表的順序搜索　98

6.3　對(duì)半搜索　98

6.3.1　對(duì)半搜索方法　98

6.3.2　二叉判定樹(shù)　101

6.4　微課（六）　102

習(xí)　題　102

第7章　搜索樹(shù)　104

7.1　二叉搜索樹(shù)　104

7.1.1　二叉搜索樹(shù)的定義和表示　104

7.1.2　二叉搜索樹(shù)基本運(yùn)算的實(shí)現(xiàn)　105

7.2　二叉平衡樹(shù)　109

7.2.1　二叉平衡樹(shù)的定義和表示　109

7.2.2　AVL搜索樹(shù)基本運(yùn)算的實(shí)現(xiàn)　111

7.3　B-樹(shù)　113

7.3.1　B-樹(shù)的定義和表示　114

7.3.2　B-樹(shù)基本運(yùn)算的實(shí)現(xiàn)　116

7.4　微課（七）　120

習(xí)　題　120

第8章　跳表和散列表　122

8.1　跳表　122

8.1.1　跳表的定義和表示　122

8.1.2　跳表基本操作的實(shí)現(xiàn)　123

8.2　散列表　125

8.2.1　散列表的定義和表示　125

8.2.2　散列表基本操作的實(shí)現(xiàn)　127

8.3　微課（八）　132

習(xí)　題　132

第9章　圖　134

9.1　圖的基本概念　134

9.1.1　圖的定義　134

9.1.2　圖的基本術(shù)語(yǔ)　135

9.1.3　圖的類型定義　137

9.2　圖的存儲(chǔ)結(jié)構(gòu)　137

9.2.1　鄰接矩陣表示法　137

9.2.2　鄰接矩陣的實(shí)現(xiàn)　138

9.2.3　圖的鄰接表表示法　141

9.2.4　鄰接表的實(shí)現(xiàn)　141

9.3　圖的遍歷　144

9.3.1　深度優(yōu)先遍歷　144

9.3.2　寬度優(yōu)先遍歷　146

9.4　拓?fù)渑判颉?48

9.4.1　AOV網(wǎng)　148

9.4.2　拓?fù)渑判颉?49

9.5　關(guān)鍵路徑　150

9.5.1　AOE網(wǎng)　150

9.5.2　關(guān)鍵路徑　151

9.6　最小代價(jià)生成樹(shù)　154

9.6.1　基本概念　154

9.6.2　普里姆（Prim）算法　154

9.6.3　克魯斯卡爾（Kruskal）算法　156

9.7　單源最短路徑　159

9.7.1　最短路徑　159

9.7.2　單源最短路徑　159

9.8　所有頂點(diǎn)之間的最短路徑　163



9.9　微課（九）　165

習(xí)　題　165

第10章　排序　168

10.1　排序的基本概念　168

10.2　簡(jiǎn)單排序算法　169

10.2.1　簡(jiǎn)單選擇排序　169

10.2.2　直接插入排序　172

10.2.3　冒泡排序　174

10.3　快速排序算法　177

10.4　兩路合并排序　181

10.5　堆排序　184

10.6　外排序　187

10.6.1　預(yù)處理　187

10.6.2　多路合并　191

10.6.3　最佳合并樹(shù)　195

10.6.4　完整的外排序過(guò)程　196

10.7　微課（十）　196

習(xí)　題　196

附錄　綜合實(shí)驗(yàn)　199