“數(shù)據(jù)結(jié)構(gòu)”是計算機專業(yè)的核心課程，是從事計算機軟件開發(fā)和應(yīng)用人員必備的專業(yè)基礎(chǔ)。隨著計算機的日益普及，“數(shù)據(jù)結(jié)構(gòu)”課程也在不斷地發(fā)展。
本書按照清華大學(xué)計算機系本科“數(shù)據(jù)結(jié)構(gòu)”大綱的要求，從面向?qū)ο蟮母拍睢ο箢愒O(shè)計的風(fēng)格和數(shù)據(jù)結(jié)構(gòu)的層次開始,從線性結(jié)構(gòu)到非線性結(jié)構(gòu)，從簡單到復(fù)，深入地討論了各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系及其在計算機中的實現(xiàn)方式和使用。此外，對常用的迭代、遞歸、回溯等算法設(shè)計技巧，搜索和排序算法等都做了詳盡的描述，并引入了簡單的算法分析。
全書采用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的C++語言作為算法的描述工具，強化基本知識和基本能力的雙基訓(xùn)練。全書條理清晰，通俗易懂，圖文并茂，適于自學(xué)。
與本書配套的《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析——用面向?qū)ο蠓椒ㄅcC++語言描述》一書已經(jīng)由清華大學(xué)出版社出版。本書適合大專院校計算機、軟件專業(yè)本科生使用，也可作為教師和有關(guān)科研人員的參考書。
計算機的普及極大地改變了人們的工作和生活。目前各個行業(yè)、各個領(lǐng)域都與計算機建立了緊密的聯(lián)系，也隨之帶來了開發(fā)各種軟件的需求。為了能夠以最少的成本，最快的速度，最好的質(zhì)量開發(fā)出合乎需要的軟件，必須遵循軟件工程的原則，把軟件的開發(fā)、維護標準化、工程化，不能再像以前那樣，把軟件看作是個人雕琢的精品。就軟件產(chǎn)品而言，最重要的就是建立合理的軟件體系結(jié)構(gòu)和程序結(jié)構(gòu)，設(shè)計有效的數(shù)據(jù)結(jié)構(gòu)。因此，要做好軟件開發(fā)工作，必須了解如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉(zhuǎn)換。這樣，《數(shù)據(jù)結(jié)構(gòu)》這門課程顯得格外重要。自1978年美籍華裔學(xué)者冀中田在國內(nèi)首開這門課程以來(當時作者也在場)，經(jīng)過20余年的發(fā)展，本課程已成為各大學(xué)計算機專業(yè)本科的主干課程，也成為非計算機類學(xué)生和研究生學(xué)習(xí)計算機的必修課程。
“數(shù)據(jù)結(jié)構(gòu)”課程脫胎于“離散數(shù)學(xué)結(jié)構(gòu)”，它涉及各種離散結(jié)構(gòu)(如向量、集合、樹、圖、代數(shù)方程、多項式等)在計算機上如何存儲和處理。其內(nèi)容豐富，涉及面廣泛，而且還在隨各種基于計算機的應(yīng)用技術(shù)的發(fā)展，不斷增加新的內(nèi)容。特別是面向?qū)ο蠹夹g(shù)出現(xiàn)以后，人們認識到，用它開發(fā)出來的軟件體系結(jié)構(gòu)更加符合人們的習(xí)慣，質(zhì)量更容易得到保證，尤其是更容易適應(yīng)使用者和用戶不斷提出的新的需求。因此，在國際上，面向?qū)ο蠹夹g(shù)得到迅速普及，出現(xiàn)了大批面向?qū)ο蟮能浖_發(fā)工具。為了適合形勢的要求，有必要開設(shè)結(jié)合面向?qū)ο蠹夹g(shù)的數(shù)據(jù)結(jié)構(gòu)課程。
用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構(gòu)，與傳統(tǒng)的面向過程的講法相比，變化較大。各種數(shù)據(jù)結(jié)構(gòu)的討論都是基于抽象數(shù)據(jù)類型和軟件復(fù)用的，有新意，也有繼承。我們力圖與過去的講授體系保持一致，但又必須引入一些新的概念。為了能夠讓讀者容易學(xué)習(xí)，我們對內(nèi)容進行了精選。許多從基本數(shù)據(jù)結(jié)構(gòu)派生出來的概念，如雙端堆、二項堆、最小最大堆、斐波那契堆、左斜樹、扁樹、B*樹等都舍去了。同時，把動態(tài)存儲管理部分歸到“操作系統(tǒng)”課程，把文件組織部分歸到“數(shù)據(jù)庫原理”，只保留了重要的應(yīng)用最廣泛的一些結(jié)構(gòu)。對這些結(jié)構(gòu)做全面深入的講解，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計算機中的存儲表示，并結(jié)合各種典型事例說明它們在解決應(yīng)用問題時的動態(tài)行為和各種必要的操作，并以C++語言為表述手段，介紹在面向?qū)ο蟪绦蛟O(shè)計過程中各種數(shù)據(jù)結(jié)構(gòu)的表達和實現(xiàn)。只要是學(xué)過C或PASCAL語言，就能夠很容易地閱讀和理解，并因此學(xué)習(xí)C++語言，提高讀者的軟件設(shè)計和編程能力。
本書是作為清華大學(xué)信息學(xué)院平臺課“數(shù)據(jù)結(jié)構(gòu)”的教材編寫的，在編寫過程中得到清華大學(xué)信息學(xué)院領(lǐng)導(dǎo)的支持，并獲得教育部“十一五”規(guī)劃教材的資助。參與策劃的有計算機系教師殷人昆、鄧俊輝、舒繼武、朱仲濤，電子系教師朱明方、吳及，自動化系教師李宛洲、劉義，微納電子學(xué)系教師李樹國，軟件學(xué)院教師張力以及信息學(xué)院辦公室的教師王娜等。第4章由舒繼武執(zhí)筆，第5章由朱仲濤執(zhí)筆，第8章由鄧俊輝執(zhí)筆，第9章由吳及執(zhí)筆，其他各章由殷人昆執(zhí)筆。作者們都是在清華大學(xué)從事“數(shù)據(jù)結(jié)構(gòu)”課程第一線教學(xué)的教師，有著豐富的數(shù)據(jù)結(jié)構(gòu)和軟件工程教學(xué)的經(jīng)驗，教學(xué)效果良好。
全書共分10章。第1章是預(yù)備知識，主要介紹什么是數(shù)據(jù)，數(shù)據(jù)與信息的關(guān)系；什么是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的分類。通過學(xué)習(xí)，讀者能夠了解抽象數(shù)據(jù)類型和面向?qū)ο蟮母拍睢２ο蟆㈩悺⒗^承、消息以及其他關(guān)系的定義、使用有基本認識。由于我們選擇了具有面向過程和面向?qū)ο箅p重特點的C++語言，可以幫助讀者自然而輕松地從傳統(tǒng)程序設(shè)計觀念向面向?qū)ο蠓椒ㄞD(zhuǎn)變。在這一章的最后還討論了算法設(shè)計和簡單的算法分析方法。
第2章是全書的基礎(chǔ)，討論了線性表、它的數(shù)組表示和鏈表表示，以及利用它們定義出來的各種結(jié)構(gòu)，如順序表、代數(shù)多項式等。通過學(xué)習(xí)，讀者可以了解對象和類的基本實現(xiàn)，并通過模板、多態(tài)性等的使用，對數(shù)據(jù)抽象概念有進一步的理解。
第3章引入4種存取受限的表，即棧、隊列、優(yōu)先級隊列和雙端隊列。通過對它們的定義、實現(xiàn)和應(yīng)用的深入介紹，使讀者能夠了解在什么場合使用它們，為以后更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的實現(xiàn)，提供了多種輔助手段。
第4章介紹在許多領(lǐng)域中經(jīng)常遇到的多維數(shù)組、字符串和廣義表。這些都是應(yīng)用廣泛又十分靈活的結(jié)構(gòu)。
第5章和第8章介紹在實際應(yīng)用中最重要的非線性結(jié)構(gòu)——樹與圖。在管理、電子設(shè)計、機械設(shè)計、日常生活中許多方面都會用到它們。
第6章、第7章和第10章介紹集合、跳表、散列、搜索樹、索引以及文件等結(jié)構(gòu)。在實際與信息處理相關(guān)的應(yīng)用中，這些結(jié)構(gòu)十分重要。許多非數(shù)值處理都涉及這些結(jié)構(gòu)，它們與內(nèi)存、外存上的數(shù)據(jù)組織關(guān)系密切。例如在外存組織文件時全面應(yīng)用了這些結(jié)構(gòu)。它們又是許多新結(jié)構(gòu)的生長點。因此，讀者學(xué)習(xí)這些內(nèi)容將獲益匪淺。
第9章介紹排序。這也是應(yīng)用十分廣泛的技術(shù)。只要是數(shù)據(jù)處理，就少不了排序。如何才能高效地完成排序，本章分別就內(nèi)、外存使用的多種排序方法進行介紹和討論，讀者可以深入了解排序的機制，也能從中學(xué)到許多程序設(shè)計的技巧。
本書的篇幅雖然較大，但給讀者以選擇。可以根據(jù)時間、能力，適當對學(xué)習(xí)的內(nèi)容加以剪裁。本著少講多練的原則，可以對每種結(jié)構(gòu)只介紹類定義和關(guān)鍵操作的實現(xiàn)，其他內(nèi)容可自學(xué)。通過上機練習(xí)，加深理解。在本書目錄中加**的章節(jié)可以酌情不講。
在本書的成書過程中得到清華大學(xué)出版社的支持，在此表示衷心的感謝。最后需要說明的是，由于作者們的水平有限，書中肯定存在許多疏漏或錯誤，請讀者及時來信批評指教。郵件地址是： yinrk@tsinghua.edu.cn或yinrk@sohu.com。
作者
2006年11月于北京
第1章數(shù)據(jù)結(jié)構(gòu)概論1
1.1數(shù)據(jù)結(jié)構(gòu)的概念1
1.1.1數(shù)據(jù)結(jié)構(gòu)舉例1
1.1.2數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2
1.1.3數(shù)據(jù)結(jié)構(gòu)的分類3
1.1.4數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容4
1.2數(shù)據(jù)結(jié)構(gòu)的抽象形式6
1.2.1數(shù)據(jù)類型6
1.2.2數(shù)據(jù)抽象與抽象數(shù)據(jù)類型7
1.3作為ADT的C++類9
1.3.1面向?qū)ο蟮母拍?
1.3.2C++中的類10
1.3.3C++中的對象12
1.3.4C++的輸入輸出13
1.3.5C++中的函數(shù)14
1.3.6動態(tài)存儲分配17
1.3.7C++中的繼承18
1.3.8多態(tài)性19
1.3.9C++的模板23
1.4算法定義24
1.5算法性能分析與度量26
1.5.1算法的性能標準26
1.5.2算法的后期測試26
1.5.3算法的事前估計27
1.5.4算法的漸進分析32
1.5.5最壞、最好和平均情況36
習(xí)題37
第2章線性表43
2.1線性表43
2.1.1線性表的概念43
2.1.2線性表的類定義44
2.2順序表45
2.2.1順序表的定義和特點45
2.2.2順序表的類定義及其操作45
2.2.3順序表的性能分析50
2.2.4順序表的應(yīng)用52
2.3單鏈表52
2.3.1單鏈表的概念53
2.3.2單鏈表的類定義54
2.3.3單鏈表中的插入與刪除56
2.3.4帶附加頭結(jié)點的單鏈表59
2.3.5單鏈表的模板類60
2.4線性鏈表的其他變形66
2.4.1循環(huán)鏈表66
2.4.2雙向鏈表69
2.5單鏈表的應(yīng)用：多項式及其運算73
2.5.1多項式的表示74
2.5.2多項式的類定義75
2.5.3多項式的加法77
2.5.4多項式的乘法79
2.6靜態(tài)鏈表80
習(xí)題83
第3章棧和隊列88
3.1棧88
3.1.1棧的定義88
3.1.2順序棧89
3.1.3鏈式棧92
3.1.4棧的應(yīng)用之一——括號匹配94
3.1.5棧的應(yīng)用之二——表達式的計算95
3.2棧與遞歸101
3.2.1遞歸的概念101
3.2.2遞歸過程與遞歸工作棧105
3.2.3用回溯法求解迷宮問題109
3.3隊列114
3.3.1隊列的概念114
3.3.2循環(huán)隊列114
3.3.3鏈式隊列118
3.3.4隊列應(yīng)用舉例：打印二項展開式(a+b)i的系數(shù)120
3.3.5隊列應(yīng)用舉例：電路布線121
3.4優(yōu)先級隊列124
3.4.1優(yōu)先級隊列的概念124
3.4.2優(yōu)先級隊列的存儲表示和實現(xiàn)125
3.5雙端隊列126
3.5.1雙端隊列的概念126
3.5.2雙端隊列的數(shù)組表示128
3.5.3雙端隊列的鏈表表示129
習(xí)題131
第4章數(shù)組、串與廣義表135
4.1多維數(shù)組的概念與存儲135
4.1.1多維數(shù)組的概念135
4.1.2多維數(shù)組的存儲表示136
4.2特殊矩陣138
4.2.1對稱矩陣的壓縮存儲138
4.2.2三對角線/多對角線矩陣的壓縮存儲140
4.3稀疏矩陣141
4.3.1稀疏矩陣及其三元組數(shù)組表示141
4.3.2稀疏矩陣的轉(zhuǎn)置145
4.3.3稀疏矩陣的相加和相乘147
4.3.4矩陣的正交鏈表表示152
4.4字符串153
4.4.1字符串的概念153
4.4.2C++有關(guān)字符串的庫函數(shù)154
4.4.3字符串的實現(xiàn)156
4.4.4字符串的自定義類158
4.4.5字符串操作的實現(xiàn)159
4.4.6字符串的模式匹配161
4.4.7字符串的存儲方法167
4.5廣義表169
4.5.1廣義表的定義與性質(zhì)169
4.5.2廣義表的表示170
4.5.3廣義表存儲結(jié)構(gòu)的實現(xiàn)170
4.5.4廣義表的遞歸算法174
4.5.5三元多項式的表示181
習(xí)題183
第5章樹186
5.1樹的基本概念186
5.1.1樹的定義和術(shù)語186
5.1.2樹的抽象數(shù)據(jù)類型188
5.2二叉樹189
5.2.1二叉樹的定義189
5.2.2二叉樹的性質(zhì)190
5.2.3二叉樹的抽象數(shù)據(jù)類型191
5.3二叉樹的存儲表示192
5.3.1二叉樹的數(shù)組存儲表示192
5.3.2二叉樹的鏈表存儲表示193
5.4二叉樹遍歷及其應(yīng)用198
5.4.1二叉樹遍歷的遞歸算法198
5.4.2二叉樹遍歷的應(yīng)用200
5.4.3二叉樹遍歷的非遞歸算法203
5.4.4二叉樹的計數(shù)207
5.5線索二叉樹210
5.5.1線索210
5.5.2中序線索二叉樹的建立和遍歷211
5.5.3中序線索二叉樹的插入與刪除216
5.5.4前序與后序的線索化二叉樹218
5.6樹與森林220
5.6.1樹的存儲表示220
5.6.2森林與二叉樹的轉(zhuǎn)換225
5.6.3樹與二叉樹的轉(zhuǎn)換227
5.7樹與森林的遍歷及其應(yīng)用227
5.7.1樹與森林的深度優(yōu)先遍歷227
5.7.2樹和森林的廣度優(yōu)先遍歷230
5.7.3樹遍歷算法的應(yīng)用231
5.7.4其他基于遍歷序列的幾種存儲表示232
5.8堆235
5.8.1最小堆和最大堆235
5.8.2堆的建立236
5.8.3堆的插入與刪除238
5.9Huffman樹及其應(yīng)用240
5.9.1路徑長度240
5.9.2Huffman樹241
5.9.3Huffman樹的應(yīng)用：最優(yōu)判定樹243
5.9.4Huffman樹的應(yīng)用：Huffman編碼244
習(xí)題246
第6章集合與字典251
6.1集合及其表示251
6.1.1集合的基本概念251
6.1.2用位向量實現(xiàn)集合抽象數(shù)據(jù)類型252
6.1.3用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型257
6.2并查集與等價類262
6.2.1并查集的定義及其實現(xiàn)262
6.2.2并查集的應(yīng)用：等價類劃分267
6.3字典268
6.3.1字典的概念269
6.3.2字典的線性表描述270
6.4跳表273
6.4.1跳表的概念273
6.4.2跳表的類定義274
6.4.3跳表的搜索、插入和刪除276
6.5散列279
6.5.1散列表與散列方法279
6.5.2散列函數(shù)280
6.5.3處理沖突的閉散列方法282
6.5.4處理沖突的開散列方法291
6.5.5散列表分析293
習(xí)題294
第7章搜索結(jié)構(gòu)297
7.1靜態(tài)搜索結(jié)構(gòu)298
7.1.1靜態(tài)搜索表298
7.1.2順序搜索300
7.1.3基于有序順序表的順序搜索和折半搜索302
7.1.4基于有序順序表的其他搜索方法307
7.2二叉搜索樹308
7.2.1二叉搜索樹的概念309
7.2.2二叉搜索樹上的搜索310
7.2.3二叉搜索樹的插入311
7.2.4二叉搜索樹的刪除313
7.2.5二叉搜索樹的性能分析314
7.2.6最優(yōu)二叉搜索樹317
7.3AVL樹320
7.3.1AVL樹的概念321
7.3.2平衡化旋轉(zhuǎn)321
7.3.3AVL樹的插入326
7.3.4AVL樹的刪除329
7.3.5AVL樹的性能分析333
7.4伸展樹334
7.5紅黑樹337
7.5.1紅黑樹的概念和性質(zhì)337
7.5.2紅黑樹的搜索338
7.5.3紅黑樹的插入338
7.5.4紅黑樹的刪除339
習(xí)題342
第8章圖346
8.1圖的基本概念346
8.1.1與圖有關(guān)的若干概念346
8.1.2圖的抽象數(shù)據(jù)類型348
8.2圖的存儲結(jié)構(gòu)349
8.2.1圖的鄰接矩陣表示350
8.2.2圖的鄰接表表示355
8.2.3圖的鄰接多重表表示361
8.3圖的遍歷363
8.3.1深度優(yōu)先搜索364
8.3.2廣度優(yōu)先搜索365
8.3.3連通分量366
8.3.4重連通分量368
8.4最小生成樹370
8.4.1Kruskal算法371
8.4.2Prim算法373
8.5最短路徑375
8.5.1非負權(quán)值的單源最短路徑376
8.5.2任意權(quán)值的單源最短路徑379
8.5.3所有頂點之間的最短路徑381
8.6用頂點表示活動的網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）383
8.7用邊表示活動的網(wǎng)絡(luò)（AOE網(wǎng)絡(luò)）388
習(xí)題392
第9章排序397
9.1排序的概念及其算法性能分析397
9.1.1排序的概念397
9.1.2排序算法的性能評估398
9.1.3排序表的類定義400
9.2插入排序401
9.2.1直接插入排序401
9.2.2折半插入排序403
9.2.3希爾排序404
9.3快速排序405
9.3.1快速排序的過程406
9.3.2快速排序的性能分析407
9.3.3快速排序的改進算法409
9.3.4三路劃分的快速排序算法412
9.4選擇排序413
9.4.1直接選擇排序413
9.4.2錦標賽排序414
9.4.3堆排序419
9.5歸并排序422
9.5.1歸并422
9.5.2歸并排序算法423
9.6基于鏈表的排序算法425
9.6.1鏈表插入排序425
9.6.2鏈表歸并排序427
9.6.3鏈表排序結(jié)果的重排428
9.7分配排序431
9.7.1桶式排序431
9.7.2基數(shù)排序432
9.7.3MSD基數(shù)排序433
9.7.4LSD基數(shù)排序435
9.8內(nèi)部排序算法的分析437
9.8.1排序方法的下界437
9.8.2各種內(nèi)部排序方法的比較439
習(xí)題440
第10章文件、外部排序與搜索444
10.1主存儲器和外存儲器444
10.1.1磁帶444
10.1.2磁盤存儲器446
10.1.3緩沖區(qū)與緩沖池448
10.2文件組織449
10.2.1文件的概念449
10.2.2文件的存儲結(jié)構(gòu)450
10.3外排序459
10.3.1外排序的基本過程459
10.3.2k路平衡歸并與敗者樹461
10.3.3初始歸并段的生成（run generation）466
10.3.4并行操作的緩沖區(qū)處理470
10.3.5最佳歸并樹473
10.4多級索引結(jié)構(gòu)475
10.4.1靜態(tài)的ISAM方法475
10.4.2動態(tài)的m路搜索樹476
10.4.3B樹478
10.4.4B樹的插入480
10.4.5B樹的刪除482
10.4.6B+樹486
10.4.7VSAM489
10.5可擴充散列490
10.5.1二叉Trie樹490
10.5.2將二叉Trie樹轉(zhuǎn)換為目錄表491
10.5.3目錄表擴充與收縮493
10.5.4性能分析494
10.6Trie樹494
10.6.1Trie樹的定義494
10.6.2Trie樹的搜索495
10.6.3在Trie樹上的插入和刪除496
習(xí)題497
附錄A程序索引500
附錄B詞匯索引504
參考文獻512
新書資訊