數據結構與演演算法

本書結構合理，內容豐富，演演算法描述清晰，用C語言編寫的演演算法代碼都已調試通過，便於自學，可作為高等院校計算機專業、軍事院校的基礎合訓專業和其他相關專業的教材和參考書，也可供從事計算機軟體開發的科技工作者參考。

本書內容包括基本數據類型、抽象數據類型、順序表、鏈表、串、樹和二叉樹、圖、遞歸與分治演演算法、貪心演演算法、分支限界和動態規劃等內容；重點介紹抽象數據類型、基本數據結構、C語言數據結構描述、數據結構的應用、演演算法設計與分析以及演演算法性能評價等內容，目的是讓讀者理解數據抽象與編程實現的關係，提高用計算機解決實際問題的能力。

第1章數據結構概述/1

1.1基本概念/1

1.1.1數據、數據元素、數據對象/1

1.1.2數據結構/2

1.2數據結構的分類/3

1.3數據類型/5

1.3.1基本類型、組合類型/5

1.3.2抽象數據類型/5

1.4演演算法和演演算法分析/8

1.4.1演演算法概念/8

1.4.2演演算法分析/9

習題/11第2章向量、棧和隊列/13

2.1線性表/13

2.1.1線性表的抽象數據類型/13

2.1.2線性表的結構表示/15

2.2向量/18

2.2.1向量的抽象數據類型/18

2.2.2向量的插入和刪除/20

2.2.3向量的應用/23

2.3棧/26

2.3.1棧的抽象數據類型及其實現/26

2.3.2棧的應用/29

2.4遞歸效率分析/36

2.4.1遞歸方程求解/36

2.4.2生成函數求解遞歸方程/37

2.4.3特徵方程求解遞歸方程/38

2.4.4遞歸樹方法/39

2.5隊列/40

2.5.1隊列的抽象數據類型及其實現/40

2.5.2隊列的應用——模擬銀行活動/46

習題/54

第3章鏈表/56

3.1單鏈表/56

3.1.1基本概念/56

3.1.2單鏈表結點結構/57

3.1.3單鏈表結構/59

3.1.4棧的單鏈表實現/70

3.1.5隊列的單鏈表實現/71

3.1.6單鏈表的應用舉例/75

3.2循環鏈表/80

3.3雙鏈表/82

習題/84第4章串/87

4.1基本概念/87

4.2串的存儲/88

4.3串結構和串的運算/89

4.4模式匹配/91

4.4.1樸素的模式匹配演演算法/91

4.4.2KMP匹配演演算法/92

4.4.3BM匹配演演算法/95

習題/98第5章排序/99

5.1基本概念/99

5.2插入排序/100

5.2.1直接插入排序/100

5.2.2折半插入排序/102

5.2.3Shell排序/104

5.3選擇排序/105

5.3.1直接選擇排序/105

5.3.2樹形選擇排序/107

5.4交換排序/108

5.4.1起泡排序/108

5.4.2快速排序/109

5.5分配排序/113

5.5.1基本思想/113

5.5.2基數排序/114

5.6歸併排序/117

5.7外部排序/120

5.7.1二路合併排序/120

5.7.2多路替代選擇合併排序/121

5.7.3最佳合併排序/122

習題/123第6章查找/125

6.1基本概念/125

6.2順序查找/125

6.3折半查找/127

6.4分塊查找/129

6.5散列查找/131

6.5.1概述/131

6.5.2散列函數/132

6.5.3衝突的處理/134

6.5.4散列查找的效率/137

習題/138第7章樹和二叉樹/140

7.1樹的概念/140

7.2二叉樹/141

7.2.1二叉樹的概念/141

7.2.2二叉樹的性質/141

7.2.3二叉樹的存儲方式/144

7.2.4樹(樹林)與二叉樹的相互轉換/146

7.3樹(樹林)、二叉樹的遍歷/147

7.3.1樹(樹林)的遍歷/147

7.3.2二叉樹的遍歷/147

7.4抽象數據類型BinaryTree以及BinaryTree

結構/148

7.4.1抽象數據類型BinaryTree/148

7.4.2一個完整的包含構建二叉樹與遍歷

實現的例子/150

7.5二叉樹的遍歷演演算法/151

7.5.1非遞歸(使用棧)的遍歷演演算法/151

7.5.2線索化二叉樹的遍歷/153

習題/157第8章樹狀結構的應用/159

8.1二叉排序樹/159

8.1.1二叉排序樹與BinarySTree結構/159

8.1.2二叉排序樹的檢索、插入、刪除

運算/160

8.1.3等概率查找對應的最佳二叉排

序樹/164

8.2平衡的二叉排序樹/166

8.2.1平衡二叉排序樹的定義/166

8.2.2平衡二叉排序樹的插入、

刪除/167

8.2.3AVL樹高度/170

8.3B樹、B+樹/171

8.4鍵樹和23樹/175

8.4.1鍵樹/175

8.4.223樹/176

8.5Huffman最優樹與樹編碼/178

8.5.1Huffman最優樹/178

8.5.2樹編碼/181

8.6堆排序/183

8.7判定樹/189

8.8等價類和並查集/190

8.8.1等價類/190

8.8.2並查集/190

8.9紅黑樹/193

習題/197第9章圖/199

9.1基本概念/199

9.2圖的存儲表示/201

9.2.1相鄰矩陣表示圖/201

9.2.2圖的鄰接表表示/202

9.2.3鄰接多重表/203

9.3基於鄰接表表示的Graph結構/205

9.4圖的遍歷/206

9.4.1深度優先遍歷/206

9.4.2廣度優先遍歷/208

9.5最小代價生成樹/209

9.6單源最短路徑問題/213

9.7每一對頂點間的最短路徑問題/216

9.8有向無迴路圖/218

9.8.1DAG圖和AOV、AOE網/218

9.8.2AOV網的拓撲排序/220

9.8.3AOE網的關鍵路徑/222

習題/224第10章演演算法設計與分析/226

10.1遞歸與分治/226

10.1.1遞歸方法設計/226

10.1.2分治法/227

10.2回溯法/229

10.3分支限界法/234

10.4貪心演演算法/241

10.5動態規劃法/242

習題/245圖目錄/247演演算法目錄/252關鍵詞索引/247參考文獻/250圖目錄

圖1.1基本的邏輯結構3

圖1.2基本存儲方法4

圖1.3游泳池及環形過道8

圖2.1向量的順序存儲19

圖2.2順序存儲的棧26

圖2.3中綴表達式的計值過程30

圖2.4後綴表達式的計值30

圖2.5中綴表達式轉換成後綴表達式的過程31

圖2.6漢諾塔問題的遞歸求解過程33

圖2.7活動記錄的進棧情況35

圖2.8活動記錄的退棧情況36

圖2.9式(2.1)的遞歸樹39

圖2.10式(2.2)的遞歸樹40

圖2.11順序存儲的隊列40

圖2.12隊列的操作41

圖2.13循環隊列的隊空和隊滿41

圖3.1單鏈表56

圖3.2從鏈表中刪除一個結點56

圖3.3往鏈表中插入一個結點56

圖3.4附加頭結點的單鏈表57

圖3.5一個實際的單鏈表結構65

圖3.6空的循環鏈表80

圖3.7雙鏈表結點82

圖3.8雙鏈表82

圖3.9往雙鏈表中插入一個結點82

圖3.10從雙鏈表中刪除一個結點82

圖3.11題3.2用圖85

圖4.1串的順序存儲88圖4.2串的緊縮順序存儲88

圖4.3串的鏈接存儲89

圖4.4第1趟比較91

圖4.5第2趟比較92

圖4.6樸素的模式匹配演演算法執行過程92

圖4.7模式P="abcabcd"的next數組的計算過程95

圖4.8基於KMP匹配演演算法的模式匹配過程96

圖5.1直接插入排序的過程100

圖5.2折半查找過程102

圖5.3Shell排序過程104

圖5.4直接選擇排序106

圖5.5第一次樹形選擇排序選出最小排序碼13107

圖5.6第二次樹形選擇排序選出最小排序碼14107

圖5.7起泡排序過程108

圖5.8第1趟快速排序的比較過程110

圖5.9基數排序的分配和收集過程115

圖5.10二路歸併過程118

圖5.11二路歸併排序示意121

圖5.12實現五路合併敗者樹122

圖5.13實現五路合併一次替代選擇后的敗者樹122

圖5.14順序合併的三路合併樹122

圖5.15三路最佳合併樹123

圖6.1折半查找過程128

圖6.2分塊查找過程130

圖6.3用分離的同義詞子表解決衝突137

圖6.4用結合的同義詞子表解決衝突137

圖6.5幾種不同的解決碰撞方法時的平均檢索長度（橫坐標為負載因子的

取值）138

圖6.6題6.8用圖139

圖7.1家族樹140

圖7.2二叉樹的五種基本形態141

圖7.3表達式二叉樹142

圖7.4深度為3的滿二叉樹142

圖7.5特殊的二叉樹143

圖7.6i與i+1在同一層的完全二叉樹143

圖7.7i與i+1不在同一層的完全二叉樹143

圖7.8完全二叉樹的順序存儲144

圖7.9非完全二叉樹的順序存儲144

圖7.10二叉樹的LeftChildRightChild表示145

圖7.11樹(樹林)與二叉樹之間相互轉換146

圖7.12樹林的例子147

圖7.13圖7.12對應的二叉樹148

圖7.14二叉樹遍歷實例150

圖7.15對稱序線索樹153

圖7.16在對稱序線索化二叉樹中插入新結點156

圖7.17題7.5用圖157

圖7.18題7.7用圖157

圖7.19題7.14用圖158

圖7.20題7.15用圖158

圖8.1二叉排序樹159

圖8.2構造二叉排序樹162

圖8.3二叉排序樹中刪除一個結點164

圖8.4刪除結點11后的另一種形式164

圖8.5兩種不同的二叉排序樹164

圖8.6兩棵擴充二叉樹164

圖8.7最佳二叉排序樹的構造165

圖8.8二叉樹與結點的平衡因子167

圖8.9平衡的二叉排序的生成過程(帶★的點為插入后引起不平衡的點)168

圖8.10二叉排序樹的平衡旋轉169

圖8.11AVL二叉排序樹結點的刪除(結點中右邊數字代表平衡因子)170

圖8.12一棵7階的B樹171

圖8.13B樹的插入173

圖8.14圖8.13中刪除元素80173

圖8.15圖8.13中刪除元素4173

圖8.16在圖8.15中刪除元素60174

圖8.17在圖8.16中刪除元素70174

圖8.18一棵3階的B+樹174

圖8.19鍵樹示例175

圖8.20由圖8.19壓縮后的鍵樹176

圖8.21鍵樹中插入記錄176

圖8.22兩棵不同形式的23樹177

圖8.2323樹的插入177

圖8.24在圖8.22(b)中插入8后23樹的變化圖178

圖8.2523樹的刪除178

圖8.26一棵擴充的二叉樹178

圖8.27赫夫曼最優樹的構造過程179

圖8.28Huffman編碼樹182

圖8.29堆對應的完全二叉樹183

圖8.30堆中插入新結點183

圖8.31堆中根結點的刪除184

圖8.32篩法建堆過程184

圖8.33堆排序過程185

圖8.34三個元素排序的判定樹189

圖8.35鑒別偽幣的判定樹189

圖8.36用父指針表示的樹狀結構存儲的並查集191

圖8.37並查集的查找、合併過程191

圖8.38Union加權規則示意圖192

圖8.39路徑壓縮的例子193

圖8.40一棵階為2的紅黑樹194

圖8.41紅黑樹的生長過程194

圖8.42一棵2階紅黑樹195

圖8.43紅黑樹中刪除元素88195

圖8.44圖8.43調整后的紅黑樹196

圖8.45圖8.44中刪除元素71196

圖8.46圖8.45調整后的紅黑樹196

圖8.47圖8.46中刪除元素63196

圖8.48調整圖8.47后的紅黑樹197

圖8.49題8.15用圖198

圖9.1無向圖和有向圖199

圖9.2圖G4=(V,E)200

圖9.3圖G3的強連通分量201

圖9.4G1的生成樹201

圖9.5G3的生成樹林201

圖9.6圖G5(網路)201

圖9.7圖的鄰接表表示203

圖9.8G5的鄰接表表示204

圖9.9圖9.7(a)的鄰接多重表表示204

圖9.10圖9.7(c)的多重鏈表表示205

圖9.11有向圖深度優先搜索過程206

圖9.12無向圖深度方向優先遍歷207

圖9.13廣度優先生成樹(樹林)209

圖9.14T的變化圖210

圖9.15Prim演演算法構造最小生成樹的過程211

圖9.16Kruskal構造最小生成樹的過程213

圖9.17有向圖G213

圖9.18含三個頂點的有向網路217

圖9.19表達式樹218

圖9.20共享結點后的表達式樹219

圖9.21表示各課程優先關係的AOV網219

圖9.22一個AOV網的例子220

圖9.23圖9.22的關鍵路徑為(a1,a4,a8,a11)或(a1,a4,a7,a10)222

圖9.24題9.1用圖224

圖9.25題9.2用圖224

圖9.26題9.3用圖224

圖9.27題9.5用圖224

圖9.28題9.6用圖225

圖9.29題9.7用圖225

圖9.30題9.10用圖225

圖9.31題9.12用圖225

圖10.1用01矩陣表示的迷宮230

圖10.201背包問題的解空間樹235

圖10.3樹T241

圖10.4樹T0241

圖10.5樹T1242

圖10.6內部結點構造圖242

圖10.7題10.5用圖245

演演算法目錄

演演算法1.1計算修建游泳池工程造價8

演演算法1.2計算兩個n×n矩陣的乘積10

演演算法2.1線性表運算15

演演算法2.2向量運算19

演演算法2.3向量的插入21

演演算法2.4向量的刪除22

演演算法2.5集合併運算23

演演算法2.6集合交運算24

演演算法2.7約瑟夫問題25

演演算法2.8堆棧運算27

演演算法2.9後綴表達式計值31

演演算法2.10求和與階乘的遞歸演演算法33

演演算法2.11漢諾塔問題的遞歸求解實現34

演演算法2.12階乘的遞歸調用35

演演算法2.13隊列的運算42

演演算法2.14優先順序隊列45

演演算法2.15事件驅動模擬49

演演算法3.1單鏈表結點及操作58

演演算法3.2單鏈表中的運算60

演演算法3.3用Nodelib中的函數實現單鏈表的建立和查找68

演演算法3.4基於單鏈表結構的操作方法實現單鏈表的建立和查找69

演演算法3.5鏈棧運算70

演演算法3.6鏈隊列運算72

演演算法3.7列印緩衝池76

演演算法3.8模擬列印緩衝池的實現主函數78

演演算法3.9循環鏈表運算81

演演算法3.10雙鏈表中的運算83演演算法4.1串運算90

演演算法4.2KMP匹配演演算法93

演演算法4.3計算next數組94

演演算法5.1直接插入排序101

演演算法5.2折半插入排序102

演演算法5.3Shell排序105

演演算法5.4直接選擇排序106

演演算法5.5起泡排序108

演演算法5.6快速排序111

演演算法5.7基數排序115

演演算法5.8歸併排序118

演演算法5.9一趟兩組歸併119

演演算法5.10兩組歸併119

演演算法6.1順序查找126

演演算法6.2折半查找128

演演算法6.3線性探測法解決衝突135

演演算法6.4用雙散列函數解決衝突136

演演算法7.1二叉樹構建與遍歷150

演演算法7.2使用棧的二叉樹前序遍歷151

演演算法7.3使用棧的二叉樹對稱序遍歷152

演演算法7.4使用棧的二叉樹後序遍歷152

演演算法7.5對稱序線索化二叉樹154

演演算法7.6在對稱序線索樹中找指定結點的對稱序後繼155

演演算法7.7對稱序遍歷對稱序線索化二叉樹155

演演算法7.8在對稱序線索化二叉樹中插入一新結點156

演演算法8.1將p所指結點插入以q為根結點指針的二叉排序樹中160

演演算法8.2構造二叉排序樹161

演演算法8.3二叉排序樹中結點的刪除162

演演算法8.4構造Huffman樹180

演演算法8.5大根堆185

演演算法9.1基於鄰接表表示圖的深度優先遍歷演演算法207

演演算法9.2Prim演演算法211

演演算法9.3Dijkstra演演算法215

演演算法9.4Floyd演演算法求網路中任意兩頂點間的最短路徑217

演演算法9.5拓撲排序221

演演算法10.1整數劃分227

演演算法10.2迷宮問題230

演演算法10.3n皇后問題233

演演算法10.4背包問題的分支限界法演演算法236

演演算法10.5求兩字元串的最長公共子序列243