數據結構(C語言版·第2版)

"嚴蔚敏 清華大學計算機科學與技術系教授,長期從事數據結構教學和教材建設,和吳偉民合作編著的《數 據 結 構》曾獲“第二屆普通高等學校優秀教材全國特等 獎”和“1996年度國家科學技術進步獎三等獎”。吳偉民 廣東工業大學計算機學院教授,1993年起享受國務院政府特殊津貼。1983年起與嚴蔚敏教授合作的數據結構系列教材和教學軟件,曾先後獲“第二屆普通高等學 校優秀教材全國特等獎”和“1996年度國家科學技術進步獎三等獎”。主要研究領域:計算機系統軟件與系統結構,計算機系統逆向和介入工程技術及工具,數據結構與算法,可視計算及程序可視化運行、調試與測評,程序設計語言與編譯系統,虛擬機和虛擬化技術,智能系統與電器等。其他主要獲獎:電子工業部科技成果二等獎, 國家教委霍英東青年教師三等獎,國家教委曾憲梓高等師範教師三等獎,廣東省計算機學會特等獎等。"

目錄

第1章緒論1

1.1什麼是數據結構1

1.2基本概念和術語4

1.3抽象數據類型的表示與實現10

1.3.1描述語言概要10

1.3.2數據存儲結構的C語言描述12

1.4算法和算法分析16

1.4.1算法16

1.4.2算法設計的要求17

1.4.3算法效率的度量17

1.4.4算法的存儲空間需求20

第2章線性表22

2.1線性表的類型定義22

2.2線性表的順序表示和實現25

2.3線性表的鏈式表示和實現34

2.3.1線性鏈表34

2.3.2循環鏈表39

2.3.3雙向鏈表40

2.3.4線性鏈表新的實現42

2.4一元多項式的表示及相加43

第3章棧和隊列48

3.1棧48

3.1.1抽象數據類型棧的定義48

3.1.2棧的表示和實現49

3.2棧的應用舉例51

3.2.1數制轉換51

3.2.2括號匹配的檢驗52

3.2.3行編輯程序53

3.2.4迷宮求解54

3.2.5表達式求值57

3.3棧與遞歸的實現60

3.4隊列66

3.4.1抽象數據類型隊列的定義66

3.4.2鏈隊列——隊列的鏈式表示和實現68

3.4.3循環隊列——隊列的順序表示和實現70

3.5離散事件模擬72

第4章串78

4.1串類型的定義78

4.2串的表示和實現81

4.2.1C語言串的存儲表示81

4.2.2短串的存儲表示83

4.2.3長串的存儲表示86

4.2.4塊鏈串的存儲表示89

4.3串的模式匹配算法90

4.3.1求子串位置的定位函數 Index(S,T,pos)90

4.3.2模式匹配的一種改進算法91

4.4串操作應用舉例96

4.4.1文本編輯96

4.4.2建立詞索引表97

第5章數組和廣義表104

5.1數組的定義104

5.2數組的順序表示和實現105

5.3矩陣的壓縮存儲109

5.3.1特殊矩陣109

5.3.2稀疏矩陣110

5.4廣義表的定義121

5.5廣義表的存儲結構123

5.6廣義表的遞歸算法125

5.6.1求廣義表的深度126

5.6.2復制廣義表127

5.6.3建立廣義表的存儲結構128

5.7m元多項式的表示130

第6章樹和二叉樹134

6.1樹的定義和基本術語134

6.2二叉樹137

6.2.1二叉樹的定義137

6.2.2二叉樹的性質138

6.2.3二叉樹的存儲結構141

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

6.3.1遍歷二叉樹144

6.3.2線索二叉樹148

6.4堆和優先隊列152

6.4.1優先隊列152

6.4.2堆的定義153

6.4.3堆的基本操作的實現154

6.5赫夫曼樹及其應用157

6.5.1最優二叉樹(赫夫曼樹)157

6.5.2赫夫曼編碼和譯碼160

6.6樹和森林164

6.6.1樹的存儲結構164

6.6.2森林與二叉樹的轉換168

6.6.3樹和森林的遍歷169

6.7並查集與等價問題170

6.7.1等價關系和等價類170

6.7.2並查集的定義和實現171

6.7.3對“並”算法的改進——加權合並法173

6.7.4對“查”算法的改進——路徑壓縮法175

6.8回溯法與樹的遍歷176

6.9樹的計數178

第7章圖182

7.1圖的定義和術語182

7.2圖的存儲結構186

7.2.1數組表示法186

7.2.2鄰接表189

7.2.3十字鏈表192

7.2.4鄰接多重表194

7.3圖的遍歷195

7.3.1深度優先搜索195

7.3.2廣度優先搜索197

7.4圖的連通性問題198

7.4.1無向圖的連通分量和生成樹198

7.4.2有向圖的強連通分量200

7.4.3最小生成樹202

7.4.4關節點和重連通分量208

7.5最短路徑211

7.5.1單個源點到其余各頂點的最短路徑212

7.5.2每一對頂點之間的最短路徑215

7.6有向無環圖及其應用217

7.6.1有向無環圖217

7.6.2拓撲排序218

7.6.3關鍵路徑221

7.7二部圖與圖匹配226

第8章動態存儲管理233

8.1概述233

8.2可利用空間表及分配方法234

8.3邊界標識法238

8.4夥伴系統243

8.5無用單元收集246

8.6存儲緊縮251

第9章查找254

9.1靜態查找表256

9.1.1順序表的查找256

9.1.2有序表的查找259

9.1.3靜態樹表的查找262

9.1.4索引順序表的查找265

9.2動態查找表266

9.2.1二叉排序樹267

9.2.2平衡二叉樹273

9.2.3紅黑樹279

9.2.4B樹和B+樹288

9.2.5跳躍表300

9.2.6鍵樹304

9.3散列表312

9.3.1散列和散列表定義312

9.3.2散列函數及其構造方法313

9.3.3沖突處理方法和散列表構造319

9.3.4散列表的查找及其分析330

9.3.5散列表和其他動態查找表字典操作的效率比較333

9.4布隆過濾器334

9.4.1位向量334

9.4.2布隆過濾器工作原理336

9.4.3布隆過濾器基本型的實現337

9.4.4布隆過濾器的應用和性能分析341

9.4.5布隆過濾器的改進343

第10章內部排序345

10.1概述345

10.2插入排序347

10.2.1直接插入排序347

10.2.2其他插入排序348

10.2.3希爾排序352

10.3快速排序354

10.4選擇排序358

10.4.1簡單選擇排序358

10.4.2樹狀選擇排序360

10.4.3堆排序361

10.5歸並排序362

10.6基數排序364

10.6.1多關鍵字的排序364

10.6.2鏈式基數排序365

10.7各種內部排序方法的比較討論368

第11章外部排序372

11.1外存信息的存取372

11.1.1存儲器層次結構372

11.1.2磁盤信息的存取373

11.1.3高速緩存策略374

11.2外部排序的方法375

11.3多路平衡歸並376

11.4置換選擇排序380

11.5最佳歸並樹385

第12章文件和索引結構387

12.1文件基礎387

12.1.1文件的基本概念387

12.1.2順序文件389

12.1.3索引文件391

12.1.4二叉排序樹索引非順序文件示例393

12.2索引順序文件394

12.2.1索引順序文件概述394

12.2.2ISAM文件395

12.3B+樹索引文件398

12.3.1VSAM文件398

12.3.2現代B+樹索引存儲方式對VSAM的改進400

12.3.3B+樹的實現401

12.3.4B+樹及數據存儲組織與管理的新發展406

12.4直接存取文件(散列文件)407

12.5多關鍵字文件409

12.5.1多重表文件409

12.5.2倒排文件409

12.5.3全文檢索的散列倒排索引示例411

附錄A名詞索引414

附錄B函數索引421

附錄CAnyviewC使用說明428

參考文獻437