數(shù)據(jù)結(jié)構(gòu)與算法教程

朱明方 清華大學(xué)電子工程系教授，原電子工程系網(wǎng)絡(luò)與人機(jī)語音通信研究所副所長，計(jì)算機(jī)與網(wǎng)絡(luò)教學(xué)實(shí)驗(yàn)室主任，電子工程系教學(xué)工作委員會委員。長期從事計(jì)算機(jī)基礎(chǔ)教學(xué)和多媒體信息處理方面的科研工作。參與完成國家及部級的科研項(xiàng)目多項(xiàng)，取得優(yōu)秀成果;編寫教材10多本，曾獲部級優(yōu)秀教材一等獎(jiǎng)，多次獲清華大學(xué)教學(xué)優(yōu)秀成果獎(jiǎng)，所編寫的教材得到清華大學(xué)"985工程"的支持。

吳及 博士，清華大學(xué)電子工程系副教授，博士生導(dǎo)師，清華-訊飛語音技術(shù)聯(lián)合實(shí)驗(yàn)室主任。從事數(shù)據(jù)結(jié)構(gòu)與算法方面的教學(xué)工作，以及語音識別和多媒體信號處理方面的科研工作，承擔(dān)了多項(xiàng)國家863科研項(xiàng)目，發(fā)表論文40余篇。擔(dān)任全國人機(jī)語音通訊學(xué)術(shù)會議常設(shè)機(jī)構(gòu)委員，并擔(dān)任多個(gè)國際和全國學(xué)術(shù)會議程序委員會委員以及多個(gè)期刊和學(xué)術(shù)會議的的審稿人。

第1章 緒論 1

1.1 預(yù)備知識 1

1.1.1 集合的笛卡兒積 1

1.1.2 二元關(guān)系 2

1.1.3 二元關(guān)系的基本性質(zhì)和幾種重要關(guān)系 3

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

1.2.1 從實(shí)際問題理解數(shù)據(jù)結(jié)構(gòu) 4

1.2.2 數(shù)據(jù)結(jié)構(gòu)所討論的內(nèi)容 6

1.2.3 如何表示數(shù)據(jù)結(jié)構(gòu) 9

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

1.3.1 什么是抽象數(shù)據(jù)類型 10

1.3.2 抽象數(shù)據(jù)類型的定義與實(shí)現(xiàn) 12

1.4 算法與算法分析 13

1.4.1 什么是算法 13

1.4.2 算法描述 15

1.4.3 常用的算法設(shè)計(jì)方法 16

1.4.4 算法分析 21

習(xí)題 24

上機(jī)練習(xí)題 26

第2章 線性表的順序存儲及其運(yùn)算 27

2.1 線性表的概念 27

2.1.1 什么是線性表 27

2.1.2 線性表的抽象數(shù)據(jù)類型 29

2.2 順序表及其運(yùn)算實(shí)現(xiàn) 30

2.2.1 線性表的順序存儲--順序表 30

2.2.2 順序表的基本運(yùn)算 31

2.2.3 順序表應(yīng)用例--求子集 36

2.3 棧 36

2.3.1 什么是棧 37

2.3.2 棧的抽象數(shù)據(jù)類型 39

2.3.3 順序棧及其運(yùn)算 39

2.4 棧應(yīng)用 42

2.4.1 棧在優(yōu)先級處理中的應(yīng)用 42

2.4.2 棧與分治法 48

2.4.3 棧與回溯法 50

2.4.4 棧與遞歸 55

2.5 隊(duì)列 63

2.5.1 隊(duì)列及其抽象數(shù)據(jù)類型 63

2.5.2 順序隊(duì)列及其運(yùn)算 64

2.5.3 隊(duì)列應(yīng)用例 68

* 2.5.4 優(yōu)先隊(duì)列 72

2.6 數(shù)組與特殊矩陣的表示 74

2.6.1 數(shù)組的順序存儲 74

2.6.2 規(guī)則矩陣的壓縮存儲 76

* 2.6.3 稀疏矩陣的三列二維數(shù)組表示--三元組順序表 78

習(xí)題 81

上機(jī)練習(xí)題 82

第3章 鏈表 83

3.1 線性表的鏈?zhǔn)酱鎯?-線性鏈表 83

3.1.1 線性鏈表的結(jié)構(gòu)特點(diǎn) 83

3.1.2 線性鏈表的運(yùn)算 84

3.2 鏈?zhǔn)綏Ｅc鏈?zhǔn)疥?duì)列 91

3.2.1 棧的鏈?zhǔn)酱鎯?-鏈?zhǔn)綏?91

3.2.2 隊(duì)列的鏈?zhǔn)酱鎯?-鏈?zhǔn)疥?duì)列 95

3.3 循環(huán)鏈表 98

3.3.1 循環(huán)鏈表的結(jié)構(gòu)特點(diǎn) 98

3.3.2 循環(huán)鏈表的基本運(yùn)算 99

3.3.3 鏈表應(yīng)用例 103

*3.4 多重鏈表 109

3.4.1 多重鏈表結(jié)構(gòu) 109

3.4.2 雙向鏈表 110

*3.5 廣義表 112

3.5.1 什么是廣義表 113

3.5.2 廣義表的存儲表示 114

3.5.3 廣義表的基本運(yùn)算 116

習(xí)題 120

上機(jī)練習(xí)題 121

第4章 樹與二叉樹 122

4.1 樹的基本概念 122

4.1.1 什么是樹 122

4.1.2 樹的性質(zhì) 127

4.2 二叉樹 128

4.2.1 什么是二叉樹 128

4.2.2 二叉樹的基本性質(zhì) 128

4.2.3 二叉樹的抽象數(shù)據(jù)類型 131

4.2.4 二叉樹的存儲結(jié)構(gòu) 131

4.2.5 二叉樹的遍歷及其他運(yùn)算 133

* 4.2.6 線索二叉樹 138

4.3 二叉樹應(yīng)用 141

4.3.1 表達(dá)式線性化 141

4.3.2 最優(yōu)二叉樹 143

4.3.3 二叉搜索樹 148

4.3.4 堆 154

* 4.3.5 二叉樹與減治法 160

4.4 樹的運(yùn)算 163

4.4.1 樹的抽象數(shù)據(jù)類型 163

4.4.2 樹的存儲結(jié)構(gòu) 164

4.4.3 樹的遍歷 165

* 4.4.4 樹的其他運(yùn)算 167

* 4.5 樹與回溯法 170

4.5.1 問題解的描述--解空間樹 171

4.5.2 回溯法的求解過程分析--遍歷解空間樹 172

4.5.3 回溯法求解問題的形式化描述 174

* 4.6 森林的遍歷 176

4.6.1 森林與二叉樹的轉(zhuǎn)換 176

4.6.2 森林的遍歷 177

習(xí)題 178

上機(jī)練習(xí)題 179

第5章 圖 180

5.1 圖的基本概念 180

5.1.1 圖的定義和概念 180

5.1.2 圖的抽象數(shù)據(jù)類型 184

*5.1.3 歐拉路徑 185

5.2 圖的存儲結(jié)構(gòu) 186

5.2.1 圖的鄰接矩陣表示 186

5.2.2 圖的鄰接表表示 189

*5.2.3 圖的其他表示方法 192

5.3 圖的遍歷 195

5.3.1 圖的深度優(yōu)先遍歷 195

5.3.2 圖的廣度優(yōu)先遍歷 197

5.3.3 圖遍歷的應(yīng)用 198

*5.3.4 圖的連通性 200

*5.4 有向圖與有向無環(huán)圖 201

5.4.1 有向圖的連通性和傳遞閉包 202

*5.4.2 有向無環(huán)圖和拓?fù)渑判?204

*5.4.3 關(guān)鍵路徑 207

5.5 最小生成樹 208

5.5.1 圖的生成樹與最小生成樹 209

5.5.2 普里姆(Prim)算法 210

5.5.3 克魯斯卡爾(Kruskal)算法 213

5.5.4 貪心算法 215

5.6 最短路徑問題 218

5.6.1 單源最短路徑 218

5.6.2 全源最短路徑 220

5.6.3 動態(tài)規(guī)劃算法 223

5.7 圖應(yīng)用例--城市間公路交通網(wǎng)問題 227

5.7.1 問題描述 227

5.7.2 問題求解思路 228

習(xí)題 228

上機(jī)練習(xí)題 230

第6章 查找 231

6.1 線性查找表 231

6.1.1 順序查找 232

6.1.2 折半查找 232

*6.1.3 斐波那契查找 234

6.1.4 線性查找表的性能比較 234

6.2 二叉搜索樹查找性能 235

6.3 AVL樹 236

6.3.1 BST的旋轉(zhuǎn)操作 237

6.3.2 AVL樹的插入和平衡化旋轉(zhuǎn) 238

*6.3.3 AVL樹的刪除 240

*6.3.4 AVL樹的性能 241

6.4 B-樹 242

6.4.1 多路動態(tài)搜索樹 242

6.4.2 B-樹的查找 243

6.4.3 B-樹的插入 244

*6.4.4 B-樹的刪除 245

6.5 散列方法 246

6.5.1 散列技術(shù) 246

6.5.2 散列函數(shù) 247

6.5.3 沖突處理 250

6.5.4 散列的刪除 252

6.5.5 散列的性能 252

6.6 靜態(tài)索引結(jié)構(gòu) 253

6.6.1 索引查找 253

6.6.2 索引存儲方式 254

*6.6.3 索引文件結(jié)構(gòu) 255

6.7 模式匹配 258

6.7.1 字符串及其ADT 258

6.7.2 字符串的存儲表示 259

6.7.3 字符串的模式匹配及簡單匹配算法 259

6.7.4 字符串匹配的KMP算法 260

習(xí)題 263

上機(jī)練習(xí)題 264

第7章 排序 265

7.1 排序的概念及算法性能分析 265

7.2 基本排序方法 266

7.2.1 冒泡排序 267

7.2.2 插入排序 268

7.2.3 直接選擇排序 272

7.2.4 基本排序方法的比較 273

7.3 快速排序 274

7.3.1 快速排序的過程 274

7.3.2 快速排序的性能分析 275

7.4 歸并排序 276

7.4.1 二路歸并 276

7.4.2 自底向上的歸并排序 276

7.4.3 自頂向下的歸并排序 278

*7.5 錦標(biāo)賽排序 279

7.6 堆排序 280

7.6.1 堆排序的思想 280

7.6.2 堆排序的實(shí)現(xiàn) 282

7.7 內(nèi)排序方法分析 283

*7.7.1 排序方法的下界 283

7.7.2 內(nèi)排序方法的比較 284

7.8 線性時(shí)間復(fù)雜度的排序算法 285

*7.8.1 計(jì)數(shù)排序 285

7.8.2 基數(shù)排序 287

7.9 外部排序 290

7.9.1 外部排序方法 290

*7.9.2 基于敗者樹的k路歸并方法 291

*7.9.3 排序--歸并的改進(jìn) 292

習(xí)題 296

上機(jī)練習(xí)題 297

實(shí)驗(yàn)指導(dǎo) 298

實(shí)驗(yàn)一 順序表及其應(yīng)用 299

實(shí)驗(yàn)二 求解迷宮問題 301

實(shí)驗(yàn)三 簡單算術(shù)表達(dá)式的處理 302

實(shí)驗(yàn)四 求解簡單背包問題 303

實(shí)驗(yàn)五 鏈表及其應(yīng)用 304

實(shí)驗(yàn)六 實(shí)驗(yàn)室機(jī)時(shí)機(jī)位的管理 305

實(shí)驗(yàn)七 實(shí)現(xiàn)Huffman編碼 307

實(shí)驗(yàn)八 文件管理的模擬 309

實(shí)驗(yàn)九 求網(wǎng)絡(luò)站點(diǎn)間的最短連接 312

實(shí)驗(yàn)十 查找最高分與次高分 314

實(shí)驗(yàn)十一 比賽日程安排與成績統(tǒng)計(jì) 316

本書可以作為大專院校數(shù)據(jù)結(jié)構(gòu)課程的教材，也可以作為從事計(jì)算機(jī)應(yīng)用開發(fā)的科技人員的參考書。本書以清華大學(xué)電子系數(shù)據(jù)結(jié)構(gòu)講義為藍(lán)本，主要針對高等院校非計(jì)算機(jī)專業(yè)開設(shè)"數(shù)據(jù)結(jié)構(gòu)"課程的需要而編寫的。全書從應(yīng)用的角度，重點(diǎn)介紹數(shù)據(jù)處理中常用的數(shù)據(jù)結(jié)構(gòu)--線性表、樹與二叉樹、圖，以及基本的數(shù)據(jù)處理技術(shù)--查找和排序方法，同時(shí)通過實(shí)例把回溯法、分治法、貪心法、動態(tài)規(guī)劃法等常用的算法設(shè)計(jì)思想的應(yīng)用融入其中，把數(shù)據(jù)結(jié)構(gòu)的介紹和常用算法設(shè)計(jì)的討論緊密結(jié)合，并且輔之以充足的練習(xí)題，從而使讀者更具體、更深刻地理解各種常用的數(shù)據(jù)結(jié)構(gòu)，及它們與算法之間的關(guān)系，以達(dá)到學(xué)以致用的目的。

前言

第1章 緒論

1.1 數(shù)據(jù)結(jié)構(gòu)的實(shí)踐意義

1.2 數(shù)據(jù)結(jié)構(gòu)的理論意義

1.3 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容和關(guān)鍵問題

習(xí)題

第2章 線性表

2.1 線性表的概念及抽象數(shù)據(jù)類型定義

2.2 線性表的順序存儲

2.3 線性表的鏈?zhǔn)酱鎯?/p>

2.4 線性表的應(yīng)用--一元多項(xiàng)式的表示及相加

2.5 順序表與鏈表的綜合比較

習(xí)題

第3章 棧和隊(duì)列

3.1 棧

3.2 隊(duì)列

習(xí)題

第4章 串

4.1 串的定義與操作

4.2 串的存儲結(jié)構(gòu)及操作

4.3 串操作應(yīng)用舉例

習(xí)題

第5章 數(shù)組和廣義表

5.1 數(shù)組的定義

5.2 數(shù)組的順序表示和實(shí)現(xiàn)

5.3 矩陣的壓縮存儲

5.4 廣義表

習(xí)題

第6章 樹

6.1 樹的定義、操作及基本術(shù)語

6.2 二叉樹

6.3 遍歷二叉樹和線索二叉樹

6.4 樹和森林

6.5 哈夫曼樹及其應(yīng)用

習(xí)題

第7章 圖

7.1 圖定義和術(shù)語

7.2 圖的存儲結(jié)構(gòu)

7.3 圖的遍歷

7.4 圖的連通性

7.5 有向無環(huán)圖及其應(yīng)用

7.6 最短路徑

習(xí)題

第8章 查找

8.1 查找的基本概念

8.2 靜態(tài)查找表

8.3 動態(tài)查找表

8.4 哈希表

習(xí)題

第9章 排序

9.1 概述

9.2 插入排序

9.3 交換排序

9.4 選擇排序

9.5 歸并排序

9.6 外部排序簡介

習(xí)題

第10章 文件

10.1 基本概念

10.2 順序文件

10.3 索引文件

10.4 ISAM文件和VSAM文件

10.5 直接存取文件(散列文件)

習(xí)題

第11章 算法設(shè)計(jì)策略

11.1 分而治之(DivideandConqureAlgorithm)

11.2 貪心算法(GreedyAlgorithm)

11.3 動態(tài)規(guī)劃算法(DynamicProgramming)

11.4 狀態(tài)搜索策略(StateSearch)

11.5 回溯算法(BacktrakingAlgorithm)

11.6 隨機(jī)算法(RandomAlgorithm)

11.7 算法設(shè)計(jì)中關(guān)鍵與技巧

習(xí)題

參考文獻(xiàn)

……