數據結構

數據結構是計算機及其相關專業的核心課程，是計算機程序設計的基礎，也是程序員考試和許多高校研究生入學考試的必考科目。全書共10章。第1章是數據結構的概述；第2～10章分別討論了順序表、鏈表、棧、隊列、串、數組、廣義表、樹、二叉樹、圖、查找、內部排序、外部排序和文件等基本類型的數據結構。本書中的演演算法都已經過調試，不必修改就能在Turbo C 2.0系統下正常運行。本書可作為計算機及相關專業的教材，也可作為自學或各種計算機培訓班的教材。

《數據結構（C語言版第3版）》特點：

（1）.結構合理、內容緊湊、知識連貫、邏輯性強，並且配有學習與實驗指導書，便於學生學習和實踐。

（2）.所有演演算法都用C語言函數實現，並在TurboC2.0系統下通過調試，無須修改就可被其他函數調用，避免了使用偽演演算法給學生學習帶來的不便。

（3）.例題經典且配有精選的大量習題，既可以使學生快速掌握所學的知識，又能培養學生的應用和創新能力。

（4）.電子教案及程序源代碼可在清華大學出版社網站下載。

層次分明，結構嚴謹，語言簡煉，圖文並茂。

全部演演算法都用C語言編寫，並在TurboC下調試通過，演演算法描述簡捷易懂。

適合作為計算機及相關專業的教材，也可作為自學或各種計算機培訓班的教材。

秦玉平教授，計算機專業博士，遼寧省教學名師，碩士生導師，多年從事計算機演演算法與程序設計類課程的教學與研究。

馬靖善教授，計算機專業碩士，多年從事計算機教學管理工作和演演算法與程序設計類課程的教學與研究。

第1章概述1

1.1數據結構的發展1

1.2基本概念2

1.3演演算法描述與分析5

習題110第2章線性表13

2.1線性表的定義及基本操作13

2.1.1線性表的基本概念13

2.1.2線性表的基本操作14

2.2順序表15

2.2.1順序表的定義15

2.2.2基本操作在順序表上的實現16

2.3鏈表19

2.3.1單鏈表的表示和實現19

2.3.2雙鏈表的表示和實現27

2.3.3循環鏈表的表示和實現32

2.3.4靜態鏈表的表示與實現39

習題244第3章特殊線性表49

3.1棧49

3.1.1棧的定義及其基本操作49

3.1.2順序棧的表示和實現50

3.1.3鏈棧的表示與實現55數據結構（C語言版）（第3版）目錄3.2隊列58

3.2.1隊列的定義及其基本操作58

3.2.2順序隊列的表示和實現59

3.2.3鏈隊列的表示和實現64

3.3串66

3.3.1串的定義及其基本操作66

3.3.2順序串的表示與實現67

3.3.3鏈串的表示和實現72

3.3.4串的模式匹配78

習題384第4章數組和廣義表87

4.1數組87

4.1.1數組的定義及基本操作87

4.1.2數組存儲結構88

4.1.3矩陣的壓縮存儲89

4.2廣義表103

4.2.1廣義表的定義和基本操作103

4.2.2廣義表的存儲104

習題4109第5章樹和二叉樹113

5.1樹的定義和基本操作113

5.1.1樹的定義和基本術語113

5.1.2樹的基本操作114

5.2二叉樹的定義和性質115

5.2.1二叉樹的定義115

5.2.2二叉樹的性質與結論115

5.3二叉樹的存儲118

5.3.1二叉樹的順序存儲結構118

5.3.2二叉樹的鏈式存儲結構122

5.4二叉樹的遍歷及應用123

5.4.1二叉樹的遍歷123

5.4.2二叉樹遞歸遍歷應用舉例127

5.4.3二叉樹的非遞歸遍歷130

5.5線索二叉樹132

5.5.1線索二叉樹的定義132

5.5.2線索化處理演演算法133

5.6樹和森林137

5.6.1樹的存儲結構137

5.6.2樹、森林與二叉樹之間的轉換140

5.6.3樹和森林的遍歷141

5.7赫夫曼樹及其應用142

5.7.1赫夫曼樹142

5.7.2赫夫曼編碼145

習題5148第6章圖153

6.1圖的基本概念153

6.2圖的存儲156

6.2.1鄰接矩陣156

6.2.2鄰接表與逆鄰接表158

6.2.3十字鏈表161

6.2.4鄰接多重表162

6.3圖的遍歷163

6.3.1深度優先搜索及其生成樹163

6.3.2廣度優先搜索及其生成樹164

6.4最小生成樹166

6.4.1Kruskal演演算法166

6.4.2Prim演演算法167

6.5圖的應用168

6.5.1拓撲排序169

6.5.2關鍵路徑170

6.5.3最短路徑173

習題6175第7章查找177

7.1查找的基本概念177

7.2靜態查找表178

7.2.1順序查找179

7.2.2二分查找181

7.2.3分塊查找184

7.3動態查找表186

7.3.1二叉排序樹186

7.3.2平衡二叉樹193

7.3.3B樹與B+樹199

7.3.4鍵樹201

7.4散列表203

7.4.1散列表的定義203

7.4.2散列函數的構造方法204

7.4.3處理衝突的方法206

7.4.4散列表的查找與分析212

習題7213第8章內部排序217

8.1排序的基本概念217

8.2插入排序220

8.3交換排序228

8.4選擇排序232

8.5歸併排序239

8.6計數排序242

8.7基數排序243

8.8各種排序方法的綜合比較246

習題8247第9章外部排序251

9.1外存儲器簡介251

9.2外部排序的方法252

9.3多路歸併排序254

9.4置換選擇排序256

9.5最佳歸併樹258

習題9259第10章文件261

10.1文件的基本概念261

10.2順序文件263

10.3索引文件265

10.3.1ISAM文件266

10.3.2VSAM文件267

10.4散列文件268

10.5多關鍵字文件270

10.5.1多重表文件270

10.5.2倒排文件270

習題10271參考文獻273