“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)的核心課程，是從事計(jì)算機(jī)軟件開發(fā)和應(yīng)用人員必備的專業(yè)基礎(chǔ)。隨著計(jì)算機(jī)的日益普及，“數(shù)據(jù)結(jié)構(gòu)”課程也在不斷地發(fā)展。
本書按照清華大學(xué)計(jì)算機(jī)系本科“數(shù)據(jù)結(jié)構(gòu)”大綱的要求，從面向?qū)ο蟮母拍睢?duì)象類設(shè)計(jì)的風(fēng)格和數(shù)據(jù)結(jié)構(gòu)的層次開始,從線性結(jié)構(gòu)到非線性結(jié)構(gòu)，從簡(jiǎn)單到復(fù)，深入地討論了各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系及其在計(jì)算機(jī)中的實(shí)現(xiàn)方式和使用。此外，對(duì)常用的迭代、遞歸、回溯等算法設(shè)計(jì)技巧，搜索和排序算法等都做了詳盡的描述，并引入了簡(jiǎn)單的算法分析。
全書采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的C++語言作為算法的描述工具，強(qiáng)化基本知識(shí)和基本能力的雙基訓(xùn)練。全書條理清晰，通俗易懂，圖文并茂，適于自學(xué)。
與本書配套的《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析——用面向?qū)ο蠓椒ㄅcC++語言描述》一書已經(jīng)由清華大學(xué)出版社出版。本書適合大專院校計(jì)算機(jī)、軟件專業(yè)本科生使用，也可作為教師和有關(guān)科研人員的參考書。
計(jì)算機(jī)的普及極大地改變了人們的工作和生活。目前各個(gè)行業(yè)、各個(gè)領(lǐng)域都與計(jì)算機(jī)建立了緊密的聯(lián)系，也隨之帶來了開發(fā)各種軟件的需求。為了能夠以最少的成本，最快的速度，最好的質(zhì)量開發(fā)出合乎需要的軟件，必須遵循軟件工程的原則，把軟件的開發(fā)、維護(hù)標(biāo)準(zhǔn)化、工程化，不能再像以前那樣，把軟件看作是個(gè)人雕琢的精品。就軟件產(chǎn)品而言，最重要的就是建立合理的軟件體系結(jié)構(gòu)和程序結(jié)構(gòu)，設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)。因此，要做好軟件開發(fā)工作，必須了解如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、傳遞和轉(zhuǎn)換。這樣，《數(shù)據(jù)結(jié)構(gòu)》這門課程顯得格外重要。自1978年美籍華裔學(xué)者冀中田在國(guó)內(nèi)首開這門課程以來(當(dāng)時(shí)作者也在場(chǎng))，經(jīng)過20余年的發(fā)展，本課程已成為各大學(xué)計(jì)算機(jī)專業(yè)本科的主干課程，也成為非計(jì)算機(jī)類學(xué)生和研究生學(xué)習(xí)計(jì)算機(jī)的必修課程。
“數(shù)據(jù)結(jié)構(gòu)”課程脫胎于“離散數(shù)學(xué)結(jié)構(gòu)”，它涉及各種離散結(jié)構(gòu)(如向量、集合、樹、圖、代數(shù)方程、多項(xiàng)式等)在計(jì)算機(jī)上如何存儲(chǔ)和處理。其內(nèi)容豐富，涉及面廣泛，而且還在隨各種基于計(jì)算機(jī)的應(yīng)用技術(shù)的發(fā)展，不斷增加新的內(nèi)容。特別是面向?qū)ο蠹夹g(shù)出現(xiàn)以后，人們認(rèn)識(shí)到，用它開發(fā)出來的軟件體系結(jié)構(gòu)更加符合人們的習(xí)慣，質(zhì)量更容易得到保證，尤其是更容易適應(yīng)使用者和用戶不斷提出的新的需求。因此，在國(guó)際上，面向?qū)ο蠹夹g(shù)得到迅速普及，出現(xiàn)了大批面向?qū)ο蟮能浖_發(fā)工具。為了適合形勢(shì)的要求，有必要開設(shè)結(jié)合面向?qū)ο蠹夹g(shù)的數(shù)據(jù)結(jié)構(gòu)課程。
用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)，與傳統(tǒng)的面向過程的講法相比，變化較大。各種數(shù)據(jù)結(jié)構(gòu)的討論都是基于抽象數(shù)據(jù)類型和軟件復(fù)用的，有新意，也有繼承。我們力圖與過去的講授體系保持一致，但又必須引入一些新的概念。為了能夠讓讀者容易學(xué)習(xí)，我們對(duì)內(nèi)容進(jìn)行了精選。許多從基本數(shù)據(jù)結(jié)構(gòu)派生出來的概念，如雙端堆、二項(xiàng)堆、最小最大堆、斐波那契堆、左斜樹、扁樹、B*樹等都舍去了。同時(shí)，把動(dòng)態(tài)存儲(chǔ)管理部分歸到“操作系統(tǒng)”課程，把文件組織部分歸到“數(shù)據(jù)庫(kù)原理”，只保留了重要的應(yīng)用最廣泛的一些結(jié)構(gòu)。對(duì)這些結(jié)構(gòu)做全面深入的講解，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種典型事例說明它們?cè)诮鉀Q應(yīng)用問題時(shí)的動(dòng)態(tài)行為和各種必要的操作，并以C++語言為表述手段，介紹在面向?qū)ο蟪绦蛟O(shè)計(jì)過程中各種數(shù)據(jù)結(jié)構(gòu)的表達(dá)和實(shí)現(xiàn)。只要是學(xué)過C或PASCAL語言，就能夠很容易地閱讀和理解，并因此學(xué)習(xí)C++語言，提高讀者的軟件設(shè)計(jì)和編程能力。
本書是作為清華大學(xué)信息學(xué)院平臺(tái)課“數(shù)據(jù)結(jié)構(gòu)”的教材編寫的，在編寫過程中得到清華大學(xué)信息學(xué)院領(lǐng)導(dǎo)的支持，并獲得教育部“十一五”規(guī)劃教材的資助。參與策劃的有計(jì)算機(jī)系教師殷人昆、鄧俊輝、舒繼武、朱仲濤，電子系教師朱明方、吳及，自動(dòng)化系教師李宛洲、劉義，微納電子學(xué)系教師李樹國(guó)，軟件學(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)驗(yàn)，教學(xué)效果良好。
全書共分10章。第1章是預(yù)備知識(shí)，主要介紹什么是數(shù)據(jù)，數(shù)據(jù)與信息的關(guān)系；什么是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的分類。通過學(xué)習(xí)，讀者能夠了解抽象數(shù)據(jù)類型和面向?qū)ο蟮母拍睢２?duì)對(duì)象、類、繼承、消息以及其他關(guān)系的定義、使用有基本認(rèn)識(shí)。由于我們選擇了具有面向過程和面向?qū)ο箅p重特點(diǎn)的C++語言，可以幫助讀者自然而輕松地從傳統(tǒng)程序設(shè)計(jì)觀念向面向?qū)ο蠓椒ㄞD(zhuǎn)變。在這一章的最后還討論了算法設(shè)計(jì)和簡(jiǎn)單的算法分析方法。
第2章是全書的基礎(chǔ)，討論了線性表、它的數(shù)組表示和鏈表表示，以及利用它們定義出來的各種結(jié)構(gòu)，如順序表、代數(shù)多項(xiàng)式等。通過學(xué)習(xí)，讀者可以了解對(duì)象和類的基本實(shí)現(xiàn)，并通過模板、多態(tài)性等的使用，對(duì)數(shù)據(jù)抽象概念有進(jìn)一步的理解。
第3章引入4種存取受限的表，即棧、隊(duì)列、優(yōu)先級(jí)隊(duì)列和雙端隊(duì)列。通過對(duì)它們的定義、實(shí)現(xiàn)和應(yīng)用的深入介紹，使讀者能夠了解在什么場(chǎng)合使用它們，為以后更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)，提供了多種輔助手段。
第4章介紹在許多領(lǐng)域中經(jīng)常遇到的多維數(shù)組、字符串和廣義表。這些都是應(yīng)用廣泛又十分靈活的結(jié)構(gòu)。
第5章和第8章介紹在實(shí)際應(yīng)用中最重要的非線性結(jié)構(gòu)——樹與圖。在管理、電子設(shè)計(jì)、機(jī)械設(shè)計(jì)、日常生活中許多方面都會(huì)用到它們。
第6章、第7章和第10章介紹集合、跳表、散列、搜索樹、索引以及文件等結(jié)構(gòu)。在實(shí)際與信息處理相關(guān)的應(yīng)用中，這些結(jié)構(gòu)十分重要。許多非數(shù)值處理都涉及這些結(jié)構(gòu)，它們與內(nèi)存、外存上的數(shù)據(jù)組織關(guān)系密切。例如在外存組織文件時(shí)全面應(yīng)用了這些結(jié)構(gòu)。它們又是許多新結(jié)構(gòu)的生長(zhǎng)點(diǎn)。因此，讀者學(xué)習(xí)這些內(nèi)容將獲益匪淺。
第9章介紹排序。這也是應(yīng)用十分廣泛的技術(shù)。只要是數(shù)據(jù)處理，就少不了排序。如何才能高效地完成排序，本章分別就內(nèi)、外存使用的多種排序方法進(jìn)行介紹和討論，讀者可以深入了解排序的機(jī)制，也能從中學(xué)到許多程序設(shè)計(jì)的技巧。
本書的篇幅雖然較大，但給讀者以選擇。可以根據(jù)時(shí)間、能力，適當(dāng)對(duì)學(xué)習(xí)的內(nèi)容加以剪裁。本著少講多練的原則，可以對(duì)每種結(jié)構(gòu)只介紹類定義和關(guān)鍵操作的實(shí)現(xiàn)，其他內(nèi)容可自學(xué)。通過上機(jī)練習(xí)，加深理解。在本書目錄中加**的章節(jié)可以酌情不講。
在本書的成書過程中得到清華大學(xué)出版社的支持，在此表示衷心的感謝。最后需要說明的是，由于作者們的水平有限，書中肯定存在許多疏漏或錯(cuò)誤，請(qǐng)讀者及時(shí)來信批評(píng)指教。郵件地址是： 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++中的對(duì)象12
1.3.4C++的輸入輸出13
1.3.5C++中的函數(shù)14
1.3.6動(dòng)態(tài)存儲(chǔ)分配17
1.3.7C++中的繼承18
1.3.8多態(tài)性19
1.3.9C++的模板23
1.4算法定義24
1.5算法性能分析與度量26
1.5.1算法的性能標(biāo)準(zhǔn)26
1.5.2算法的后期測(cè)試26
1.5.3算法的事前估計(jì)27
1.5.4算法的漸進(jìn)分析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順序表的定義和特點(diǎn)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é)點(diǎn)的單鏈表59
2.3.5單鏈表的模板類60
2.4線性鏈表的其他變形66
2.4.1循環(huán)鏈表66
2.4.2雙向鏈表69
2.5單鏈表的應(yīng)用：多項(xiàng)式及其運(yùn)算73
2.5.1多項(xiàng)式的表示74
2.5.2多項(xiàng)式的類定義75
2.5.3多項(xiàng)式的加法77
2.5.4多項(xiàng)式的乘法79
2.6靜態(tài)鏈表80
習(xí)題83
第3章棧和隊(duì)列88
3.1棧88
3.1.1棧的定義88
3.1.2順序棧89
3.1.3鏈?zhǔn)綏?2
3.1.4棧的應(yīng)用之一——括號(hào)匹配94
3.1.5棧的應(yīng)用之二——表達(dá)式的計(jì)算95
3.2棧與遞歸101
3.2.1遞歸的概念101
3.2.2遞歸過程與遞歸工作棧105
3.2.3用回溯法求解迷宮問題109
3.3隊(duì)列114
3.3.1隊(duì)列的概念114
3.3.2循環(huán)隊(duì)列114
3.3.3鏈?zhǔn)疥?duì)列118
3.3.4隊(duì)列應(yīng)用舉例：打印二項(xiàng)展開式(a+b)i的系數(shù)120
3.3.5隊(duì)列應(yīng)用舉例：電路布線121
3.4優(yōu)先級(jí)隊(duì)列124
3.4.1優(yōu)先級(jí)隊(duì)列的概念124
3.4.2優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示和實(shí)現(xiàn)125
3.5雙端隊(duì)列126
3.5.1雙端隊(duì)列的概念126
3.5.2雙端隊(duì)列的數(shù)組表示128
3.5.3雙端隊(duì)列的鏈表表示129
習(xí)題131
第4章數(shù)組、串與廣義表135
4.1多維數(shù)組的概念與存儲(chǔ)135
4.1.1多維數(shù)組的概念135
4.1.2多維數(shù)組的存儲(chǔ)表示136
4.2特殊矩陣138
4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)138
4.2.2三對(duì)角線/多對(duì)角線矩陣的壓縮存儲(chǔ)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)字符串的庫(kù)函數(shù)154
4.4.3字符串的實(shí)現(xiàn)156
4.4.4字符串的自定義類158
4.4.5字符串操作的實(shí)現(xiàn)159
4.4.6字符串的模式匹配161
4.4.7字符串的存儲(chǔ)方法167
4.5廣義表169
4.5.1廣義表的定義與性質(zhì)169
4.5.2廣義表的表示170
4.5.3廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)170
4.5.4廣義表的遞歸算法174
4.5.5三元多項(xiàng)式的表示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二叉樹的存儲(chǔ)表示192
5.3.1二叉樹的數(shù)組存儲(chǔ)表示192
5.3.2二叉樹的鏈表存儲(chǔ)表示193
5.4二叉樹遍歷及其應(yīng)用198
5.4.1二叉樹遍歷的遞歸算法198
5.4.2二叉樹遍歷的應(yīng)用200
5.4.3二叉樹遍歷的非遞歸算法203
5.4.4二叉樹的計(jì)數(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樹的存儲(chǔ)表示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其他基于遍歷序列的幾種存儲(chǔ)表示232
5.8堆235
5.8.1最小堆和最大堆235
5.8.2堆的建立236
5.8.3堆的插入與刪除238
5.9Huffman樹及其應(yīng)用240
5.9.1路徑長(zhǎng)度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用位向量實(shí)現(xiàn)集合抽象數(shù)據(jù)類型252
6.1.3用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型257
6.2并查集與等價(jià)類262
6.2.1并查集的定義及其實(shí)現(xiàn)262
6.2.2并查集的應(yīng)用：等價(jià)類劃分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圖的存儲(chǔ)結(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非負(fù)權(quán)值的單源最短路徑376
8.5.2任意權(quán)值的單源最短路徑379
8.5.3所有頂點(diǎn)之間的最短路徑381
8.6用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）383
8.7用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)絡(luò)）388
習(xí)題392
第9章排序397
9.1排序的概念及其算法性能分析397
9.1.1排序的概念397
9.1.2排序算法的性能評(píng)估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快速排序的改進(jìn)算法409
9.3.4三路劃分的快速排序算法412
9.4選擇排序413
9.4.1直接選擇排序413
9.4.2錦標(biāo)賽排序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主存儲(chǔ)器和外存儲(chǔ)器444
10.1.1磁帶444
10.1.2磁盤存儲(chǔ)器446
10.1.3緩沖區(qū)與緩沖池448
10.2文件組織449
10.2.1文件的概念449
10.2.2文件的存儲(chǔ)結(jié)構(gòu)450
10.3外排序459
10.3.1外排序的基本過程459
10.3.2k路平衡歸并與敗者樹461
10.3.3初始?xì)w并段的生成（run generation）466
10.3.4并行操作的緩沖區(qū)處理470
10.3.5最佳歸并樹473
10.4多級(jí)索引結(jié)構(gòu)475
10.4.1靜態(tài)的ISAM方法475
10.4.2動(dòng)態(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可擴(kuò)充散列490
10.5.1二叉Trie樹490
10.5.2將二叉Trie樹轉(zhuǎn)換為目錄表491
10.5.3目錄表擴(kuò)充與收縮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
參考文獻(xiàn)512
新書資訊