數據結構與算法（第2版）

《數據結構與算法（第2版）》是清華大學出版社出版的圖書，作者是（美）Sartaj Sahni。

內容簡介

本書結構合理，內容豐富，算法描述清晰，用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