算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）

第1章 概論 1

1．1 什么是數(shù)據(jù)結(jié)構(gòu) 1

1．2 基本概念和術(shù)語 4

1．3 算法和算法分析 7

1．3．1 算法的定義及特性 7

1．3．2 算法的設(shè)計(jì)要求 8

1．3．3 算法效率的衡量方法 9

1．3．4 算法的時間復(fù)雜度 10

1．3．5 算法的空間復(fù)雜度 15

1．4 抽象數(shù)據(jù)類型 16

習(xí)題 18

第2章 線性表 20

2．1 線性表的類型定義 20

2．1．1 線性表的概念 20

2．1．2 線性表的抽象數(shù)據(jù)類型 21

2．2 線性表的順序表示和實(shí)現(xiàn) 22

2．2．1 線性表的順序表示 22

2．2．2 順序表基本運(yùn)算的實(shí)現(xiàn) 23

2．3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 28

2．3．1 線性表的鏈?zhǔn)奖硎?29

2．3．2 單鏈表上基本運(yùn)算的實(shí)現(xiàn) 32

2．4 雙鏈表 40

2．5 循環(huán)鏈表 44

2．6 線性表實(shí)現(xiàn)方法的比較 46

2．7 算法設(shè)計(jì)舉例 47

習(xí)題 52

第3章 棧和隊(duì)列 55

3．1 棧 55

3．1．1 棧的類型定義 55

3．1．2 順序棧的表示和實(shí)現(xiàn) 57

3．1．3 鏈棧的表示和實(shí)現(xiàn) 60

3．2 棧的應(yīng)用舉例 62

3．2．1 十進(jìn)制數(shù)轉(zhuǎn)換為其他進(jìn)制數(shù) 62

3．2．2 表達(dá)式中括號的匹配檢查 63

3．2．3 表達(dá)式求值 64

3．2．4 利用棧消除遞歸 72

3．3 隊(duì)列 77

3．3．1 隊(duì)列的類型定義 77

3．3．2 循環(huán)隊(duì)列―隊(duì)列的順序表示和

實(shí)現(xiàn) 78

3．3．3 鏈隊(duì)列―隊(duì)列的鏈?zhǔn)奖硎竞?/p>

實(shí)現(xiàn) 82

3．4 算法設(shè)計(jì)舉例 83

習(xí)題 87

第4章 串 90

4．1 串的基本概念 90

4．2 串的表示和實(shí)現(xiàn) 91

4．2．1 串的順序存儲結(jié)構(gòu) 91

4．2．2 串的鏈?zhǔn)酱鎯Y(jié)構(gòu) 94

4．3 串的模式匹配 95

4．3．1 樸素的模式匹配算法 95

4．3．2 KMP算法 96

習(xí)題 101

第5章 數(shù)組 104

5．1 數(shù)組的基本概念 104

5．2 矩陣的壓縮存儲 107

5．2．1 特殊矩陣 107

5．2．2 稀疏矩陣 110

5．3 算法設(shè)計(jì)舉例 117

習(xí)題 121

第6章 樹和二叉樹 124

6．1 樹的概念 124

6．2 二叉樹的概念和性質(zhì) 126

6．2．1 二叉樹的概念和抽象數(shù)據(jù)

類型 126

6．2．2 二叉樹的性質(zhì) 129

6．3 二叉樹的表示和實(shí)現(xiàn) 131

6．3．1 二叉樹的存儲結(jié)構(gòu) 131

6．3．2 二叉樹的遍歷運(yùn)算 133

6．3．3 二叉樹的其他基本運(yùn)算 140

6．4 樹和森林 142

6．4．1 樹的存儲結(jié)構(gòu) 143

6．4．2 樹、森林和二叉樹的相互

轉(zhuǎn)換 146

6．4．3 樹和森林的遍歷運(yùn)算 148

6．4．4 樹和森林的其他基本運(yùn)算 151

*6．5 線索二叉樹 154

6．5．1 線索二叉樹的概念 154

6．5．2 線索二叉樹的基本運(yùn)算 157

6．6 算法設(shè)計(jì)舉例 161

習(xí)題 162

第7章 樹和二叉樹的應(yīng)用 166

*7．1 表達(dá)式樹 166

7．2 哈夫曼樹和哈夫曼編碼 171

7．2．1 哈夫曼樹 171

7．2．2 哈夫曼編碼 175

7．3 堆和優(yōu)先級隊(duì)列 178

7．3．1 堆 178

7．3．2 優(yōu)先級隊(duì)列 179

*7．4 并查集 184

7．5 算法設(shè)計(jì)舉例 187

習(xí)題 189

第8章 圖 191

8．1 圖的概念 191

8．2 圖的存儲結(jié)構(gòu) 196

8．2．1 鄰接矩陣 196

8．2．2 鄰接表 200

*8．2．3 十字鏈表 205

*8．2．4 鄰接多重表 205

8．3 圖的遍歷 206

8．3．1 深度優(yōu)先遍歷 207

8．3．2 廣度優(yōu)先遍歷 209

8．3．3 圖的連通分量和生成樹 212

習(xí)題 213

第9章 圖的應(yīng)用 217

9．1 最小生成樹 217

9．1．1 最小生成樹的概念 217

9．1．2 Prim算法 218

9．1．3 Kruskal算法 222

9．2 有向無環(huán)圖及其應(yīng)用 225

9．2．1 拓?fù)渑判?225

9．2．2 關(guān)鍵路徑 230

9．3 最短路徑 236

9．3．1 單源點(diǎn)最短路徑 236

9．3．2 每對頂點(diǎn)之間的最短路徑 240

習(xí)題 243

第10章 集合與查找 247

10．1 基本概念 247

10．2 靜態(tài)查找表上的查找 248

10．2．1 順序查找 248

10．2．2 折半查找 250

10．2．3 分塊查找 254

10．3 動態(tài)查找表上的查找 256

10．3．1 二叉查找樹 256

10．3．2 平衡二叉樹 263

*10．3．3 B樹 275

*10．3．4 B+樹 280

*10．3．5 字典樹 281

10．4 算法設(shè)計(jì)舉例 282

習(xí)題 285

第11章 散列表 288

11．1 散列表的概念 288

11．2 構(gòu)造散列函數(shù)的方法 289

11．2．1 直接定址法 289

11．2．2 折疊法 289

11．2．3 數(shù)字分析法 289

11．2．4 平方取中法 290

11．2．5 除留余數(shù)法 290

11．3 解決沖突的方法 291

11．3．1 閉散列法 291

11．3．2 開散列法 293

11．4 散列表的實(shí)現(xiàn) 294

11．4．1 閉散列表的表示和實(shí)現(xiàn) 294

11．4．2 開散列表的表示和實(shí)現(xiàn) 298

11．4．3 閉散列表與開散列表的

比較 302

11．5 散列表的查找性能分析 302

習(xí)題 303

第12章 排序 306

12．1 排序的基本概念 306

12．2 插入排序 307

12．2．1 直接插入排序 307

12．2．2 折半插入排序 308

12．2．3 希爾排序 309

12．3 交換排序 310

12．3．1 冒泡排序 310

12．3．2 快速排序 311

12．4 選擇排序 315

12．4．1 直接選擇排序 315

12．4．2 堆排序 316

*12．4．3 錦標(biāo)賽排序 320

12．5 歸并排序 320

*12．6 基數(shù)排序 322

12．7 各種內(nèi)部排序方法的比較 324

*12．8 外部排序 327

12．8．1 置換選擇排序 328

12．8．2 多路歸并排序 330

習(xí)題 331

附錄A 上機(jī)實(shí)驗(yàn)參考題目 334

參考文獻(xiàn) 336