數據結構（C語言描述）(2012年清華大學出版社出版的圖書)

成書過程

修訂過程

該教材是根據2007年教育部頒發的《高等學校計算機科學與技術專業公共核心知識體系與課程》規範和2011年修訂的《全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合考試大綱》編寫而成。

出版工作

2012年10月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
龍啟銘、戰曉雷	常雪影	時翠蘭	李紅英

內容簡介

全書共分10章。第1章介紹數據結構的地位和主要知識點、數據結構和算法的基本概念和算法分析的簡單方法，以及C語言編程的要點。第2章～第10章對應考試大綱的6個知識單元，包括線性表，棧、佇列與數組，樹與二叉樹，圖，查找，排序等。各章所附習題不包括選擇題，但選擇了綜合套用題。此外，附錄還包含程式索引、實訓作業要求與樣例。

教材目錄

第1章緒論1

1.1 數據結構的概念及分類1

1.1.1 為什麼要學習數據結構1

1.1.2 與數據結構相關的基本術語2

1.1.3 數據結構的分類5

1.1.4 數據結構的存儲結構7

1.1.5 定義在數據結構上的操作8

1.1.6 “好”的數據結構9

1.2 使用C語言描述數據結構9

1.2.1 C語言的數據類型9

1.2.2 算法的控制結構10

1.2.3 算法的函式結構11

1.2.4 動態存儲分配14

1.2.5 邏輯和關係運算的約定15

1.2.6 輸入與輸出16

1.3 算法和算法設計17

1.3.1 算法的定義和特性17

1.3.2 算法的設計步驟17

1.3.3 算法設計的基本方法18

1.4 算法分析與度量21

1.4.1 算法的評價標準22

1.4.2 算法的時間和空間複雜性度量22

1.4.3 算法的漸進分析25

小結29

習題29

第2章線性表32

2.1 線性表32

2.1.1 線性表的定義和特點32

2.1.2 線性表的主要操作33

2.2 順序表34

2.2.1 順序表的定義和特點34

2.2.2 順序表的結構定義35

2.2.3 順序表主要操作的實現36

2.2.4 順序表主要操作的性能分析38

2.2.5 順序表的套用舉例40

2.3 單鍊表41

2.3.1 單鍊表的定義和特點41

2.3.2 單鍊表的結構定義42

2.3.3 單鍊表中指針的操作42

2.3.4 單鍊表中的插入與刪除43

2.3.5 帶頭結點的單鍊表46

2.3.6 單鍊表主要操作的性能分析48

2.3.7 單鍊表的順序訪問與尾遞歸49

2.3.8 單鍊表的套用舉例51

2.4 順序表與線性鍊表的比較53

2.5 線性鍊表的其他變形55

2.5.1 循環鍊表55

2.5.2 雙向鍊表59

2.5.3 靜態鍊表62

2.6 線性表的套用: 一元多項式及其運算63

2.6.1 一元多項式的表示64

2.6.2 多項式的結構定義65

2.6.3 多項式的加法66

2.6.4 多項式的乘法68

小結69

習題70

第3章棧和佇列74

3.1 棧74

3.1.1 棧的概念74

3.1.2 順序棧75

3.1.3 鏈式棧80

3.1.4 棧的混洗82

3.2 佇列83

3.2.1 佇列的概念83

3.2.2 循環佇列85

3.2.3 鏈式佇列88

3.3 棧的套用90

3.3.1 數制轉換91

3.3.2 括弧匹配91

3.3.3 表達式的計算與優先權處理93

3.3.4 棧與遞歸的實現98

3.4 佇列的套用100

3.4.1 列印楊輝三角形與逐行處理100

3.4.2 電路布線與兩點間的最短路徑102

3.5 在算法設計中使用遞歸105

3.5.1 漢諾塔問題與分治法105

3.5.2 迷宮問題與回溯法107

3.5.3 計算組合數與動態規劃111

3.6 雙端佇列113

3.6.1 雙端佇列的概念113

3.6.2 輸入受限的雙端佇列113

3.6.3 輸出受限的雙端佇列114

3.6.4 雙端佇列的順序存儲表示115

3.6.5 雙端佇列的連結存儲表示117

小結117

習題118

第4章數組、串和廣義表122

4.1 數組122

4.1.1 一維數組122

4.1.2 多維數組124

4.1.3 數組的套用舉例126

4.2 特殊矩陣的壓縮存儲127

4.2.1 對稱矩陣的壓縮存儲128

4.2.2 三對角矩陣的壓縮存儲129

4.3 稀疏矩陣131

4.3.1 稀疏矩陣的概念131

4.3.2 稀疏矩陣的三元組表表示131

4.3.3 稀疏矩陣的十字鍊表表示132

4.4 字元串134

4.4.1 字元串的概念134

4.4.2 字元串的初始化和賦值134

4.4.3 C語言中有關字元串的庫函式135

4.4.4 自定義字元串的存儲表示137

4.4.5 串的模式匹配141

4.5 廣義表147

4.5.1 廣義表的概念147

4.5.2 廣義表的性質148

4.5.3 廣義表的連結表示149

4.5.4 三元多項式的表示151

小結153

習題154

第5章樹與二叉樹157

5.1 樹的基本概念157

5.1.1 樹的定義和術語157

5.1.2 樹的基本操作160

5.2 二叉樹161

5.2.1 二叉樹的概念161

5.2.2 二叉樹的性質161

5.2.3 二叉樹的主要操作163

5.3 二叉樹的存儲表示165

5.3.1 二叉樹的順序存儲表示165

5.3.2 二叉樹的鍊表存儲表示166

5.4 二叉樹的遍歷167

5.4.1 二叉樹遍歷的遞歸算法167

5.4.2 遞歸遍歷算法的套用舉例168

5.4.3 二叉樹遍歷的非遞歸算法171

5.4.4 非遞歸遍歷算法的套用舉例176

5.4.5 二叉樹的計數178

5.5 線索二叉樹181

5.5.1 線索二叉樹的概念182

5.5.2 線索二叉樹的種類182

5.5.3 中序線索二叉樹的建立和遍歷183

5.5.4 前序與後序線索二叉樹185

5.6 樹與森林187

5.6.1 樹的存儲表示187

5.6.2 森林與二叉樹的轉換190

5.6.3 樹與森林的深度優先遍歷192

5.6.4 樹與森林的廣度優先遍歷194

5.6.5 樹遍歷算法的套用舉例195

小結196

習題197

第6章樹與二叉樹的套用201

6.1 二叉查找樹201

6.1.1 二叉查找樹的概念201

6.1.2 二叉查找樹的查找202

6.1.3 二叉查找樹的插入203

6.1.4 二叉查找樹的刪除205

6.1.5 二叉查找樹的性能分析207

6.2.1 AVL樹的概念209

6.2.2 平衡化旋轉210

6.2.3 AVL樹的插入212

6.2.4 AVL樹的刪除214

6.2.5 AVL樹的性能分析216

6.3 Huffman樹218

6.3.1 帶權路徑長度的概念218

6.3.2 Huffman樹的概念219

6.3.3 最優判定樹222

6.3.4 Huffman編碼224

6.4 堆225

6.4.1 小根堆和大根堆225

6.4.2 堆的建立227

6.4.3 堆的插入228

6.4.4 堆的刪除230

6.5 並查集230

6.5.1 並查集的定義及其實現230

6.5.2 並查集操作的分析和改進232

6.6 八皇后問題與樹的剪枝234

6.6.1 八皇后問題的提出234

6.6.2 八皇后問題的狀態樹235

6.6.3 八皇后問題算法237

小結238

習題238

第7章圖242

7.1 圖的基本概念242

7.1.1 與圖有關的若干概念242

7.1.2 圖的基本操作245

7.2 圖的存儲結構247

7.2.1 圖的鄰接矩陣表示247

7.2.2 圖的鄰接表表示251

7.2.3 鄰接矩陣表示與鄰接表表示的比較256

7.2.4 圖的鄰接多重表表示256

7.3 圖的遍歷258

7.3.1 深度優先搜尋258

7.3.2 廣度優先搜尋260

7.3.3 連通分量261

7.3.4 重連通圖263

7.3.5 有向圖的強連通分量265

7.4 最小生成樹267

7.4.1 最小生成樹求解和貪婪法267

7.4.2 Kruskal算法269

7.4.3 Prim算法272

7.5 最短路徑274

7.5.1 非負權重的單源最短路徑274

7.5.2 所有頂點之間的最短路徑278

7.5.3 無權重的最短路徑281

7.6 活動網路282

7.6.1 AOV網路與拓撲排序282

7.6.2 AOE網路與關鍵路徑法286

小結291

習題291

第8章查找297

8.1 查找的基本概念297

8.1.1 查找的概念297

8.1.2 查找算法的性能分析298

8.2 順序查找法298

8.2.1 在順序表上的順序查找算法298

8.2.2 線上性鍊表上的順序查找算法302

8.3 折半查找法302

8.3.1 折半查找法302

8.3.2 次優查找樹：折半查找的改進方法305

8.3.3 斐波那契查找：折半查找的變形310

8.3.4 插值查找：折半查找的變形312

8.4 B樹313

8.4.1 索引順序表與分塊查找313

8.4.2 多級索引結構與m叉查找樹315

8.4.3 B樹的概念316

8.4.4 B樹上的查找317

8.4.5 B樹上的插入318

8.4.6 B樹上的刪除320

8.4.7 B+樹321

8.5 散列表及其查找324

8.5.1 散列的概念324

8.5.2 常見的散列函式325

8.5.3 解決衝突的開地址法328

8.5.4 解決衝突的鏈地址法335

8.5.5 散列法分析337

小結338

習題339

第9章內排序344

9.1 排序的概念344

9.1.1 排序的概念344

9.1.2 排序算法的性能345

9.1.3 數據表的結構定義346

9.2 插入排序347

9.2.1 直接插入排序347

9.2.2 基於鍊表的直接插入排序349

9.2.3 折半插入排序350

9.2.4 希爾排序352

9.3 交換排序353

9.3.1 起泡排序354

9.3.2 快速排序356

9.3.3 快速排序的改進算法359

9.4 選擇排序360

9.4.1 簡單選擇排序361

9.4.2 堆排序362

9.4.3 錦標賽排序366

9.5 歸併排序367

9.5.1 二路歸併排序的設計思路367

9.5.2 二路歸併排序的遞歸算法367

9.5.3 基於鍊表的歸併排序算法369

9.5.4 疊代的歸併排序算法371

9.6 基數排序373

9.6.1 基數排序373

9.6.2 MSD基數排序374

9.6.3 LSD基數排序376

9.7 內排序算法的分析和比較379

9.7.1 排序方法的下界379

9.7.2 分布計數排序380

9.7.3 各種內排序方法的比較381

小結384

習題385

第10章外排序389

10.1 主存儲器和外存儲器389

10.1.1 磁帶389

10.1.2 磁碟存儲器390

10.1.3 緩衝區391

10.2 基於磁碟的外排序過程392

10.2.1 基於磁碟排序的過程392

10.2.2 基於磁碟排序的性能分析393

10.3 m路平衡歸併394

10.3.1 m路平衡歸併的過程394

10.3.2 用敗者樹選最小記錄395

10.3.3 敗者樹的構造396

10.4 初始歸併段的生成398

10.4.1 置換-選擇排序398

10.4.2 用敗者樹實現置換-選擇排序398

10.4.3 用小根堆實現置換-選擇排序399

10.4.4 置換-選擇排序的性能分析402

10.5 最佳歸併樹403

10.6 並行操作的緩衝區處理405

10.6.1 使用固定緩衝區實現並行操作405

10.6.2 使用緩衝區佇列實現並行操作405

10.7 磁帶歸併排序407

10.7.1 平衡歸併排序408

10.7.2 多步歸併排序408

10.7.3 多步歸併排序初始歸併段的分配409

小結410

習題411

附錄A 程式索引413

附錄B 實訓作業要求與樣例420

參考文獻426

（註：目錄排版順序為從左列至右列）

教學資源

該教材有配套教材——《數據結構精講與習題詳解——考研輔導與答疑解惑》。

書名	書號	出版社	出版時間	作者
《數據結構精講與習題詳解——考研輔導與答疑解惑》	9787302297932	清華大學出版社	2012.10.01	殷人昆

教材特色

該教材各章除了對數據結構的基本內容做了討論之外，還針對學生在與教師的互動中提出的很多疑問，以及學生在考試和做業務中暴露出來的理解上的偏差，在正文中做了正面的闡述，並通過穿插在正文中的“想想看”提醒學生注意容易被忽略的問題。

該教材在章節安排上遵照了考試大綱的順序。在講解數據結構的基本知識點的過程中，引入了窮舉、遞推、疊代、遞歸等算法的設計，在後續章節中陸續引入了分治、減治、回溯、動態規劃、剪枝和貪婪等算法設計策略，使得算法與數據結構的設計互相滲透。在討論查找、排序等算法時，強調了算法分析，在布置上機作業或實訓中讓學生通過實際比較來了解算法分析的方法。

全書採用C語言作為數據結構及算法的描述工具，適當採用C++的少量語句以簡化程式。算法描述力求結構化，注重編程風格，每個算法基本保持在100行之內。

作者在討論每一個知識單元時，結合教學的經驗和考試輔導的體會，安排了教材內容，對學生讀書容易忽略的地方和隱藏在書中所討論問題背後的東西都有適當的提示。

採用“工科”思維，啟發學生掌握“化複雜為簡單”的方式，從問題入手，通過“問題、子問題”分解，尋找解決方案；
涵蓋了考試大綱的6個知識點：線性表，棧、佇列與數組，樹與二叉樹，圖，查找，排序；對基本知識點講深講透，通過多種套用舉例，讓學生了解不同問題需要採取什麼方法來應對；
通過習題，從不同視點、不同層面訓練學生。

數據結構（C語言描述）(2012年清華大學出版社出版的圖書)

基本介紹