數據結構

《數據結構》(第2版)在保持原書基本框架和特色的基礎上對主要各章如：第一、二、三、四、六及九章等作了增刪和修改。《數據結構》系統地介紹了各種類型的數據結構和查找、排序的各種方法。對每一種數據結構，除了詳細闡述其基本概念和具體實現外，並儘可能對每種操作給出類PASCAL的算法，對查找和排序的各種算法，還着重在時間上作出定量或定性的分析比較，最後一章討論文件的各種組織方法。《數據結構》概念清楚，內容豐富，並有相配套的《數據結構題集》，既便於教學，又便於自學。 ^[1] 

第一章 緒論1

1．1 什麼是數據結構1

1．2 基本概念和術語3

1．3 數據結構的發展簡史及它在計算機科學中所處的地位12

1．4 算法的描述和算法分析13

1．4．1 算法的描述13

1．4．2 算法設計的要求15

1．4．3 算法效率的度量16

1．4．4 算法的存儲空間需求18

第二章 線性表19

2．1 線性表的邏輯結構19

2．2 線性表的順序存儲結構22

2．3 線性表的鏈式存儲結構27

2．3．1 線性鏈表27

2．3．2 循環鏈表35

2．3，3 雙向鏈表35

2．4 一元多項式的表示及相加37

第三章 棧和隊列41

3．1 棧41

3．1．1 抽象數據類型棧的定義41

3．1．2 棧的表示和實現43

3．2 表達式求值45

**3．3 棧與遞歸過程47

3．3．1 遞歸過程及其實現47

3．3．2 遞歸過程的模擬52

3．4 隊列59

3．4．1 抽象數據類型隊列的定義59

3．4．2 鏈隊列——隊列的鏈式存儲結構61

3．4．3 循環隊列——隊列的順序存儲結構63

3．5 離散事件模擬66

第四章 串71

4．1 串及其操作71

4．1．1 串的邏輯結構定義71

4．1．2 串的基本操作72

4．2 串的存儲結構73

4．2．1 靜態存儲結構74

4．2．2 動態存儲結構74

4．3 串基本操作的實現77

4．3．1 靜態結構存儲串時的操作77

4．3．2 模式匹配的一種改進算法80

4．3．3 堆結構存儲串時的操作84

4．4 串操作應用舉例86

4．4．1 文本編輯86

**4．4．2 建立詞索引表87

第五章 數組和廣義表93

5．1 數組的定義和運算93

5．2 數組的順序存儲結構95

5．3 矩陣的壓縮存儲96

5．3．1 特殊矩陣97

5．3．2 稀疏矩陣97

5．4 廣義表的定義107

5．5 廣義表的存儲結構109

**5．6 m元多項式的表示110

**5．7 廣義表的遞歸算法112

5．7．1 求廣義表的深度113

5．7．2 複製廣義表114

5．7．3 建立廣義表的存儲結構115

第六章 樹和二叉樹118

6．1 樹的結構定義和基本操作118

6．2 二叉樹120

6．2．1 定義與基本操作120

6．2．2 二叉樹的性質122

6．2．3 二叉樹的存儲結構124

6．3 遍歷二叉樹和線索二叉樹125

6．3．1 遍歷二叉樹125

5．3．2 線索二叉樹128

6．4 樹和森林134

6．4．1 樹的存儲結構134

6．4．2 森林與二叉樹的轉換135

6．4．3 樹的遍歷137

**6．5 樹與等價問題138

6．6 哈夫曼樹及其應用142

6．6．1 最優二叉樹（哈夫曼樹）142

6．6．2 哈夫曼編碼144

**6．7 回溯法與樹的遍歷148

**6．8 樹的計數150

第七章 圖155

7．1 圖的定義和術語155

7．2 圖的存儲結構159

7．2．1 數組表示法159

7．2．2 鄰接表161

7．2．3 十字鏈表162

7．2．4 鄰接多重表164

7．3 圖的遍歷165

7．3．1 深度優先搜索166

7．3．2 廣度優先搜索167

7．4 圖的連通性問題168

7．4．1 無向圖的連通分量和生成樹168

**7．4．2 有向圖的強連通分量171

7．4．3 最小生成樹171

**7．4．4 關節點和重連通分量174

7．5 有向無環圖及其應用177

7．5．1 拓撲排序179

7．5．2 關鍵路徑184

7．6 最短路徑188

7．6．1 從某個源點到其餘各頂點的最短路徑189

7．6．2 每一對頂點之間的最短路徑191

**7．7 二部圖與圖匹配193

第八章 動態存儲管理198

8．1 概述198

8．2 可利用空間表及分配方法200

8．3 邊界標識法203

8．3．1 可利用空間表的結構203

8．3．2 分配算法204

8．3．3 回收算法206

8．4 夥伴系統208

8．4．1 可利用空間表的結構208

8．4．2 分配算法209

8．4．3 回收算法210

8．5 無用單元收集211

8．6 存儲緊縮216

第九章 查找219

9．1 靜態查找表220

9．1．1 順序表的查找220

9．1．2 有序表的查找223

9．1．3 靜態樹表的查找226

9．1．4 索引順序表的查找230

9．2 動態查找表231

9．2．1 二叉排序樹和平衡二叉樹231

9．2．2 B_樹和B+樹241

9．2．3 鍵樹249

9．3 哈希表253

9．3．1 什麼是哈希表253

9．3．2 哈希函數的構造方法255

9．3．3 處理衝突的方法258

9．3．4 哈希表的查找及其分析260

第十章 內部排序264

10．1 概述264

10．2 插入排序265

10．2．1 直接插入排序265

10．2．2 其它插入排序268

10．2．3 希爾排序272

10．3 快速排序274

10．4 選擇排序278

10．4．1 簡單選擇排序278

10．4．2 樹形選擇排序280

10．4．3 堆排序281

10．5 歸併排序284

10．6 基數排序285

10．6．1 多關鍵字的排序286

10．6．2 鏈式基數排序287

10．7 各種內部排序方法的比較討論289

第十一章 外部排序294

11．1 外存信息的存取294

11．2 外部排序的方法296

11．3 多路平衡歸併的實現298

11．4 置換-選擇排序300

**11．5 緩衝區的並行操作處理305

11．6 最佳歸併樹307

**11．7 磁帶歸併排序308

11．7．1 平衡歸併308

11．7．2 多步歸併308

第十二章 文件311

12．1 有關文件的基本概念311

12．2 順序文件313

12．3 索引文件316

12．4 ISAM文件和VSAM文件318

12．4．1 ISAM文件318

12．4．2 VSAM文件321

12．5 直接存取文件（散列文件）322

12．6 多關鍵字文件324

12．6．1 多重表文件324

12．6．2 倒排文件325

附錄一 類PASCAL語言擴充部分的語法圖327

附錄二 名詞索引329

附錄三 過程和函數索引336

參考書目340