第1章概述1
1.1數據結構的發展1
1.2數據結構的基本概念2
1.3算法與算法分析5
習題1 10
第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單鏈表表示及實現20
2.3.2雙鏈表表示及實現28
2.3.3循環鏈表表示及實現32
2.3.4靜態鏈表表示及實現40
習題245
第3章特殊線性表49
3.1棧49
3.1.1棧的定義和基本操作49
3.1.2順序棧表示及實現50
3.1.3鏈棧表示及實現55
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順序串表示及實現68
3.3.3鏈串表示及實現73
3.3.4串的模式匹配79
習題385
第4章數組和廣義表89
4.1數組89
4.1.1數組的定義和基本操作89
4.1.2數組的存儲結構90
4.1.3矩陣的壓縮存儲91
4.2廣義表105
4.2.1廣義表的定義和基本操作105
4.2.2廣義表的存儲機構106
習題4  112
第5章樹和二叉樹115
5.1樹的定義和基本操作115
5.1.1樹的定義和基本術語115
5.1.2樹的基本操作116
5.2二叉樹117
5.2.1二叉樹的定義和基本操作117
5.2.2二叉樹的性質118
5.2.3二叉樹的遍歷121
5.2.4二叉樹的順序存儲結構122
5.2.5二叉樹的鏈式存儲結構127
5.2.6二叉樹的非遞歸遍歷133
5.2.7線索二叉樹135
5.3樹和森林140
5.3.1樹的存儲結構140
5.3.2樹、森林與二叉樹之間的轉換144
5.3.3樹和森林的遍歷146
5.4赫夫曼樹及其應用147
5.4.1赫夫曼樹147
5.4.2赫夫曼編碼150
習題5153
第6章圖157
6.1圖的定義和基本操作157
6.1.1圖的定義和基本術語157
6.1.2圖的基本操作160
6.2圖的遍歷160
6.2.1深度優先搜索及其生成樹161
6.2.2廣度優先搜索及其生成樹161
6.3圖的存儲162
6.3.1鄰接矩陣162
6.3.2鄰接表與逆鄰接表165
6.3.3十字鏈表169
6.3.4鄰接多重表170
6.4小生成樹171
6.4.1Kruskal算法172
6.4.2Prim算法173
6.5圖的應用175
6.5.1拓撲排序175
6.5.2關鍵路徑177
6.5.3短路徑180
習題6182
第7章查找185
7.1查找的基本概念185
7.2靜態查找表186
7.2.1順序查找187
7.2.2二分查找189
7.2.3分塊查找192
7.3動態查找表194
7.3.1二叉排序樹194
7.3.2平衡二叉樹201
7.3.3B樹與B 樹207
7.4散列表209
7.4.1散列表的定義209
7.4.2散列函數的構造方法210
7.4.3處理衝突的方法212
7.4.4散列表的查找與性能分析218
習題7219
第8章內部排序223
8.1排序的基本概念223
8.2插入排序226
8.2.1直接插入排序226
8.2.2折半插入排序227
8.2.32路插入排序228
8.2.4希爾排序230
8.2.5表插入排序232
8.3交換排序235
8.3.1起泡排序235
8.3.2快速排序237
8.4選擇排序238
8.4.1簡單選擇排序238
8.4.2樹形選擇排序240
8.4.3堆排序243
8.5歸並排序246
8.6計數排序249
8.7基數排序250
8.7.1多關鍵字排序250
8.7.2鏈式基數排序251
8.8各種排序方法的綜合比較253
習題8254
第9章外部排序257
9.1外存儲器簡介257
9.2外部排序方法258
9.3多路平衡歸並260
9.4置換選擇排序261
9.5歸並樹263
習題9 265
參考文獻266

“數據結構”是計算機專業的一門重要的專業必修課，是絕大多數高校招收計算機及相關專業碩士研究生的必考科目之一。
本課程主要研究數據在計算機中的存儲和操作，它涉及一繫列較為實用的算法，這些算法在實際的程序設計中是非常有用的。但這門課程內容豐富、學習量大，其算法又十分抽像。經過多年的教學實踐，我們總結出該課程的一些課程特點和教學方法，為此，我們編寫了這部教材，以滿足廣大學生的要求和計算機教學的需要。
本次再版在保持前三版寫作風格和特色的基礎上，依據讀者的建議，主要做了以下改進：
(1) 刪除了“文件”一章和第7章“鍵樹”一節的內容；
(2) 調整了第1章、第5章和第6章及其他部分章節的結構和內容；
(3) 更新了部分例題和習題；
(4) 所有算法均在Visual C 6.0/2010環境下調試通過，並給出了詳細注釋；
(5) 在知識表述方面進行了反復推敲並做了相應修改。
本書共9章，第1章為概述，主要介紹數據結構的簡單發展史、基本概念和算法的描述與分析方法；第2章為線性表，主要介紹順序表和各種鏈表的存儲表示與實現；第3章為特殊線性表，主要介紹棧、隊列和串的存儲表示與實現；第4章為數組和廣義表，主要介紹數組和廣義表的存儲表示與實現；第5章為樹和二叉樹，主要介紹二叉樹的性質、存儲、遍歷及其應用；第6章為圖，主要討論圖的存儲、遍歷及其應用；第7章為查找，主要介紹靜態查找、動態查找和散列表；第8章為內部排序，主要介紹幾種常用的內部排序算法及性能；第9章為外部排序，主要介紹在內存和外存之間如何調動和組織數據進行排序。
本書的算法都使用C語言函數實現，不用做任何修改即可被其他函數調用。本書結構合理，內容緊湊，知識連貫，表述簡潔，邏輯性強。為使讀者更好地掌握各章節的內容，各章末均配有大量精選習題，可使讀者快速熟悉和掌握所學的知識。本書既可作為計算機專業的本、專科教材，也可作為與計算機學科其他相關專業的教材。
本書第1章、第5章和第8章由馬靖善編寫、修改；第2～4章由秦玉平編寫、修改；第6章由冷強奎編寫、修改；第7章由王麗君編寫、修改；第9章由瀋澤剛編寫、修改。全書由秦玉平統稿，所有算法由秦玉平和冷強奎調試。
本書配有輔教材《數據結構(C語言版)學習與實驗指導》(第4版)，由清華大學出版社出版發行。
在本書的編寫過程中，編者參考了大量有關數據結構的書籍和資料，在此對這些參考文獻的作者一並表示感謝。
由於編者水平有限，書中難免存在錯誤和不當之處，懇請廣大讀者批評指正。 
注：目錄中帶有“”的章節可選講；帶有“”的章節為專科學生選學。
本書受到遼寧省“興遼英纔計劃”教學名師項目(XLYC1906015)的資助。
本書的課件和源代碼可從清華大學出版社官方網站下載。

編者2021年6月