第2版前言
本書第2版的初稿完成于2015年12月，作為另一本教材《數(shù)據(jù)結(jié)構(gòu)精講與習(xí)題詳解》（第2版）的寫作參照，相互融合，相互補(bǔ)充，首先完成了該書，再回過(guò)頭來(lái)第二次修改本書，所以本書實(shí)際上是第2版的修訂本。
自從1978年美籍華人冀中田*次在中國(guó)講授“數(shù)據(jù)結(jié)構(gòu)”課開始，很多老師對(duì)課程的內(nèi)容和講授方法做了大量的研究，也可以說(shuō)是在做中學(xué)，總結(jié)出許多好的經(jīng)驗(yàn)，使得課程的教學(xué)比當(dāng)時(shí)進(jìn)步了很多。我本人在這門課程的教學(xué)中也積累了一些心得，非常希望與正在學(xué)習(xí)這門課程的同學(xué)們分享，這是我修改這本教材的初衷。
既然數(shù)據(jù)結(jié)構(gòu)與算法相輔相成，密不可分，而算法就是解決問(wèn)題的過(guò)程描述，那么，描述數(shù)據(jù)結(jié)構(gòu)與算法的語(yǔ)言就應(yīng)該是過(guò)程性的。早期用偽代碼描述，實(shí)踐證明不可持續(xù)，因?yàn)楹芏嘤脗未a描述的算法轉(zhuǎn)換為使用某種編程語(yǔ)言編寫的程序后，怎么也通不過(guò)。原因是很多人編程語(yǔ)言的實(shí)踐能力太差，算法的實(shí)現(xiàn)細(xì)節(jié)太粗糙。所以我認(rèn)為，使用某種過(guò)程性語(yǔ)言，如C、C++等，對(duì)于學(xué)習(xí)和實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法是合適的。
由于數(shù)據(jù)結(jié)構(gòu)課程學(xué)時(shí)的限制（多數(shù)學(xué)校為48～64學(xué)時(shí)），作為本科生的教材，包含的知識(shí)容量應(yīng)有一定限度。知識(shí)點(diǎn)太少，學(xué)生在未來(lái)的學(xué)習(xí)和工作中可聯(lián)想的思考空間狹窄，使解決問(wèn)題的能力受限；知識(shí)點(diǎn)太多，必然淪為百科全書式的閱讀，基礎(chǔ)不牢靠，同樣使得解決問(wèn)題的能力受限。通過(guò)教學(xué)實(shí)踐證明，本書的第1版在內(nèi)容上取材是恰當(dāng)?shù)模秶先〔牡纳疃群蛷V度也是恰當(dāng)?shù)�，但�?lián)想不夠，某些算法的實(shí)現(xiàn)上偏向使用偽代碼描述，造成部分讀者在學(xué)習(xí)上和實(shí)踐上的困惑。本書第2版修改部分包括：
（1）在結(jié)構(gòu)上從第1版的10章改為8章，雖然章數(shù)壓縮了，但敘述內(nèi)容不減反增。增加的知識(shí)點(diǎn)大多作為“擴(kuò)展閱讀”出現(xiàn)，它們不作為考核內(nèi)容，主要是拓展視野。
（2）各章的“想想看”改為“思考題”，目的是增加一些互動(dòng)環(huán)節(jié)。這些思考題觸及的都是可聯(lián)想的內(nèi)容，或者是對(duì)理解正文有用的知識(shí)“點(diǎn)撥”。所謂“學(xué)問(wèn)”就是有“學(xué)”還要有“問(wèn)”。正面的“問(wèn)”有助于理解“應(yīng)該做什么”，反面的“問(wèn)”有助于理解“不該做什么”。
（3）書中所有使用C語(yǔ)言書寫的算法，包括輔助教材《數(shù)據(jù)結(jié)構(gòu)精講與習(xí)題詳解》（第2版）中的800道算法題，都重新使用VC++ 6.0編譯程序調(diào)試過(guò)，有的還按照軟件工程的要求做了邊界值測(cè)試。因?yàn)闀兴惴ǖ恼_運(yùn)行需要構(gòu)建運(yùn)行環(huán)境，所以對(duì)于書中所涉及的主要數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示，絕大多數(shù)都在第2版給出了結(jié)構(gòu)定義、初始化或創(chuàng)建算法、輸出算法等，這樣可由讀者自行搭建運(yùn)行環(huán)境。
�。�4）第3章增加了多棧共享同一存儲(chǔ)時(shí)的棧浮動(dòng)技術(shù)、遞歸程序的非遞歸模擬方法、優(yōu)先隊(duì)列的內(nèi)容；第4章增加了w對(duì)角矩陣的壓縮存儲(chǔ)、稀疏矩陣的鏈表存儲(chǔ)、串的BM模式匹配算法的內(nèi)容；第5章增加了等價(jià)類與并查集的內(nèi)容；第6章增加了構(gòu)造*小生成樹的破圈法、Dijkstra算法的內(nèi)容；第7章增加了跳表、紅黑樹、伸展樹、字典樹的內(nèi)容。此外對(duì)保留的內(nèi)容有部分增刪。教材現(xiàn)有內(nèi)容基本覆蓋大多數(shù)學(xué)校的教學(xué)大綱和考研大綱。
�。�5）附錄增加了詞匯索引，書中出現(xiàn)的重要概念都收錄在索引中，大大方便了讀者查閱相關(guān)的詞匯。
各章所附習(xí)題不包括選擇題，但精選了許多綜合應(yīng)用題，這些習(xí)題的參考解答請(qǐng)參看作者的另一本配套教材《數(shù)據(jù)結(jié)構(gòu)精講與習(xí)題詳解》。
因?yàn)樽髡叩乃接邢�，可能在某些方面有考慮不周的地方，書中難免存在疏漏或錯(cuò)誤，誠(chéng)懇希望讀者提出寶貴意見(jiàn)。
作 者
2016年8月于清華大學(xué)
收起全部↑
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的概念及分類 1
1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1
1.1.2 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本術(shù)語(yǔ) 2
1.1.3 數(shù)據(jù)結(jié)構(gòu)的分類 5
1.1.4 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu) 6
1.1.5 定義在數(shù)據(jù)結(jié)構(gòu)上的操作 7
1.1.6 “好”數(shù)據(jù)結(jié)構(gòu) 7
1.2 使用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu) 7
1.2.1 C語(yǔ)言的數(shù)據(jù)類型 8
1.2.2 算法的控制結(jié)構(gòu) 9
1.2.3 算法的函數(shù)結(jié)構(gòu) 10
1.2.4 動(dòng)態(tài)存儲(chǔ)分配 12
1.2.5 邏輯和關(guān)系運(yùn)算的約定 12
1.2.6 輸入與輸出 13
1.3 算法和算法設(shè)計(jì) 13
1.3.1 算法的定義和特性 13
1.3.2 算法的設(shè)計(jì)步驟 14
1.3.3 算法設(shè)計(jì)的基本方法 15
1.4 算法分析與度量 18
1.4.1 算法的評(píng)價(jià)標(biāo)準(zhǔn) 18
1.4.2 算法的時(shí)間和空間復(fù)雜度度量 18
1.4.3 算法的漸近分析 21
小結(jié) 24
習(xí)題 24
第2章 線性表 27
2.1 線性表 27
2.1.1 線性表的定義和特點(diǎn) 27
2.1.2 線性表的主要操作 28
2.2 順序表 29
2.2.1 順序表的定義和特點(diǎn) 29
2.2.2 順序表的結(jié)構(gòu)定義 30
2.2.3 順序表查找操作的實(shí)現(xiàn) 31
2.2.4 順序表插入和刪除操作的實(shí)現(xiàn) 32
2.2.5 順序表的應(yīng)用：集合運(yùn)算 34
2.3 單鏈表 35
2.3.1 單鏈表的定義和特點(diǎn) 35
2.3.2 單鏈表的結(jié)構(gòu)定義 36
2.3.3 單鏈表中的插入與刪除 36
2.3.4 帶頭結(jié)點(diǎn)的單鏈表 40
2.3.5 單鏈表的遍歷與創(chuàng)建 42
2.3.6 單鏈表的應(yīng)用：集合運(yùn)算 44
2.3.7 循環(huán)鏈表 46
2.3.8 雙向鏈表 50
2.3.9 靜態(tài)鏈表 53
2.4 順序表與線性鏈表的比較 54
2.5 線性表的應(yīng)用：一元多項(xiàng)式及其運(yùn)算 56
2.5.1 一元多項(xiàng)式的表示 56
2.5.2 多項(xiàng)式的結(jié)構(gòu)定義 57
2.5.3 多項(xiàng)式的加法 59
2.5.4 擴(kuò)展閱讀：多項(xiàng)式的乘法 60
小結(jié) 62
習(xí)題 63
第3章 棧和隊(duì)列 66
3.1 棧 66
3.1.1 棧的概念 66
3.1.2 順序棧 67
3.1.3 擴(kuò)展閱讀：多棧處理 70
3.1.4 鏈?zhǔn)綏?73
3.1.5 擴(kuò)展閱讀：棧的混洗 74
3.2 隊(duì)列 76
3.2.1 隊(duì)列的概念 76
3.2.2 循環(huán)隊(duì)列 76
3.2.3 鏈?zhǔn)疥?duì)列 80
3.3 棧的應(yīng)用 82
3.3.1 數(shù)制轉(zhuǎn)換 82
3.3.2 括號(hào)匹配 83
3.3.3 表達(dá)式的計(jì)算與優(yōu)先級(jí)處理 84
3.3.4 棧與遞歸的實(shí)現(xiàn) 88
3.4 隊(duì)列的應(yīng)用 91
3.5 在算法設(shè)計(jì)中使用遞歸 92
3.5.1 漢諾塔問(wèn)題與分治法 92
3.5.2 直接把遞歸過(guò)程改為非遞歸過(guò)程 94
3.5.3 擴(kuò)展閱讀：遞歸過(guò)程的非遞歸模擬算法 95
3.5.4 迷宮問(wèn)題與回溯法 98
3.5.5 計(jì)算組合數(shù)與動(dòng)態(tài)規(guī)劃 101
3.6 擴(kuò)展閱讀：雙端隊(duì)列 102
3.6.1 雙端隊(duì)列的概念 102
3.6.2 輸入受限的雙端隊(duì)列 103
3.6.3 輸出受限的雙端隊(duì)列 104
3.6.4 雙端隊(duì)列的存儲(chǔ)表示 104
3.7 擴(kuò)展閱讀：優(yōu)先隊(duì)列 106
3.7.1 優(yōu)先隊(duì)列的概念 106
3.7.2 優(yōu)先隊(duì)列的實(shí)現(xiàn) 107
小結(jié) 108
習(xí)題 108
第4章 數(shù)組、串和廣義表 112
4.1 數(shù)組 112
4.1.1 一維數(shù)組 112
4.1.2 多維數(shù)組 114
4.2 特殊矩陣的壓縮存儲(chǔ) 116
4.2.1 對(duì)稱矩陣的壓縮存儲(chǔ) 117
4.2.2 三對(duì)角矩陣的壓縮存儲(chǔ) 118
4.2.3 擴(kuò)展閱讀：w對(duì)角矩陣的壓縮存儲(chǔ) 119
4.3 稀疏矩陣 120
4.3.1 稀疏矩陣的概念 120
4.3.2 稀疏矩陣的順序存儲(chǔ)表示 121
4.3.3 稀疏矩陣的鏈表表示 124
4.4 字符串 125
4.4.1 字符串的概念 126
4.4.2 字符串的初始化和賦值 126
4.4.3 自定義字符串的存儲(chǔ)表示 128
4.4.4 串的模式匹配 132
4.5 廣義表 140
4.5.1 廣義表的概念 140
4.5.2 廣義表的性質(zhì) 141
4.5.3 廣義表的鏈接表示 141
4.5.4 擴(kuò)展閱讀：三元多項(xiàng)式的表示 147
新書資訊