內(nèi) 容 簡(jiǎn) 介
“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)學(xué)科研究的主題之一。本書(shū)采用類(lèi)C語(yǔ)言描述，系統(tǒng)地介紹了各種數(shù)據(jù)結(jié)構(gòu)和排序、查找算法。全書(shū)共分為9章，主要內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)與算法簡(jiǎn)介、線性表、棧和隊(duì)列、串、數(shù)組及廣義表、樹(shù)和二叉樹(shù)、圖、查找和排序等。對(duì)于各種數(shù)據(jù)結(jié)構(gòu)，本書(shū)給出了基本概念、抽象數(shù)據(jù)類(lèi)型以及相關(guān)的操作，并且對(duì)各種算法的運(yùn)行時(shí)間進(jìn)行了分析。
本書(shū)對(duì)數(shù)據(jù)結(jié)構(gòu)中的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行了深入的剖析，著重培養(yǎng)學(xué)生的動(dòng)手能力，對(duì)經(jīng)典算法、重點(diǎn)算法及應(yīng)用算法進(jìn)行了詳細(xì)的講解，以使學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。
本書(shū)可作為計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)的大學(xué)本科教材，也可作為應(yīng)用型專(zhuān)業(yè)以及成人教育、工程技術(shù)人員的培訓(xùn)教材。
前 言
本書(shū)訂正了第2版中的筆誤、描述不規(guī)范等問(wèn)題，簡(jiǎn)化了使用不多的內(nèi)容；每章的編程項(xiàng)目都有完整的C程序?qū)崿F(xiàn)代碼，并都在VC++6.0環(huán)境下編譯通過(guò)，運(yùn)行正確。
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課，是十分重要的核心課程。它側(cè)重于體系和思想上的訓(xùn)練，是程序設(shè)計(jì)的靈魂，為計(jì)算機(jī)語(yǔ)言課程設(shè)計(jì)提供了方法性的理論指導(dǎo)，所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。算法與數(shù)據(jù)結(jié)構(gòu)之間存在著相輔相成的關(guān)系。解決一個(gè)問(wèn)題既可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，也可以選擇不同的算法。數(shù)據(jù)結(jié)構(gòu)的選擇決定了算法執(zhí)行所需要的時(shí)間與空間，影響算法的效率；反之，算法的優(yōu)劣又決定了某個(gè)數(shù)據(jù)結(jié)構(gòu)是否適合解決這個(gè)問(wèn)題。
全書(shū)共分為9章，由淺入深、系統(tǒng)地討論了各種數(shù)據(jù)結(jié)構(gòu)的基本概念和相關(guān)操作，還介紹了查找和排序算法。各章的具體內(nèi)容介紹如下。
第1章是緒論，介紹了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的意義、數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，并且指出了數(shù)據(jù)結(jié)構(gòu)和算法之間的關(guān)系，給出了分析算法的方法。
第2章主要介紹了線性表的概念、抽象數(shù)據(jù)類(lèi)型及其基本操作，最后列舉了一些線性表的應(yīng)用實(shí)例。
第3章主要介紹了受限制的線性表，即棧和隊(duì)列；重點(diǎn)介紹了棧和隊(duì)列的抽象數(shù)據(jù)類(lèi)型及其實(shí)現(xiàn)，并列舉了幾個(gè)應(yīng)用實(shí)例。
第4章主要介紹了串這一非數(shù)值數(shù)據(jù)結(jié)構(gòu)，包括串的抽象數(shù)據(jù)類(lèi)型及其基本操作與串的模式匹配算法。
第5章介紹了數(shù)組這一數(shù)據(jù)類(lèi)型在計(jì)算機(jī)中的存儲(chǔ)，重點(diǎn)介紹了稀疏矩陣在計(jì)算機(jī)中的壓縮存儲(chǔ)及其操作的實(shí)現(xiàn)，同時(shí)還介紹了廣義表的概念。
第6章討論了樹(shù)形結(jié)構(gòu)及其相關(guān)算法。
第7章討論了圖形結(jié)構(gòu)及其相關(guān)算法。圖形結(jié)構(gòu)是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其應(yīng)用也非常廣泛，該章在介紹了圖的遍歷算法以后還采用遍歷算法推導(dǎo)出了其他常用算法。
第8章討論了在線性表和樹(shù)上的查找算法，還介紹了期望查找復(fù)雜度為O(1)的哈希表查找算法。
第9章重點(diǎn)介紹了插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序等算法及其思想和分析，在最后還介紹了外部排序算法。
本書(shū)示例較多，講解細(xì)致，對(duì)數(shù)據(jù)結(jié)構(gòu)中的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行了深入的剖析，著重培養(yǎng)學(xué)生的動(dòng)手能力，突出實(shí)用性；對(duì)經(jīng)典算法、重點(diǎn)算法及應(yīng)用算法進(jìn)行了詳細(xì)的講解，以使學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。本書(shū)采用類(lèi)C語(yǔ)言來(lái)描述算法。類(lèi)C語(yǔ)言是偽碼和C語(yǔ)言組合而成的一個(gè)描述工具，采用了C語(yǔ)言的核心部分，并為描述方便進(jìn)行了擴(kuò)充。
本書(shū)可作為計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)的大學(xué)本科教材，也可作為應(yīng)用型專(zhuān)業(yè)以及成人教育、工程技術(shù)人員的培訓(xùn)教材。
本書(shū)主要由陳琳琳、李建林任主編，由孫啟虎、李橙、郭龍?jiān)慈胃敝骶�。何光明、趙傳申、許娟、王珊珊、石雅琴、鄭愛(ài)琴、許悅、陳珍、陳鳳、盧振俠、曹冬梅、楊橙、陳莉萍等人員在內(nèi)容編寫(xiě)、程序測(cè)試、文字校對(duì)等工作中也付出了辛勤勞動(dòng)，在此一并表示衷心的感謝！
本書(shū)配有電子教案，并提供程序源代碼，以方便讀者自學(xué)，請(qǐng)到清華大學(xué)出版社網(wǎng)站下載。
限于作者水平，書(shū)中難免存在不當(dāng)之處，懇請(qǐng)廣大讀者批評(píng)指正。
編 者
目 錄
第1章 緒論 1
1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義 1
1.1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 1
1.1.2 學(xué)習(xí)算法的意義 2
1.2 數(shù)據(jù)結(jié)構(gòu) 3
1.2.1 數(shù)據(jù)結(jié)構(gòu)概述 3
1.2.2 基本概念 3
1.3 抽象數(shù)據(jù)類(lèi)型 5
1.4 算法 6
1.4.1 算法概述 7
1.4.2 算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系 8
1.4.3 算法的度量 8
1.5 算法分析 9
1.5.1 數(shù)學(xué)基礎(chǔ) 9
1.5.2 所需分析的問(wèn)題 11
1.5.3 運(yùn)行時(shí)間的計(jì)算 11
1.5.4 檢驗(yàn)?zāi)愕姆治?span id="epizqqp1gsyu" class="Apple-tab-span" style="white-space:pre"> 13
小結(jié) 15
自測(cè)題答案 16
編程項(xiàng)目 17
第2章 線性表 18
2.1 線性表的定義 18
2.1.1 線性表概述 18
2.1.2 線性表的抽象數(shù)據(jù)類(lèi)型 19
2.1.3 線性表的相關(guān)操作 20
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 22
2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu) 22
2.2.2 相關(guān)操作的實(shí)現(xiàn) 23
2.2.3 順序存儲(chǔ)結(jié)構(gòu)的分析 29
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 29
2.3.1 線性鏈表與相關(guān)操作實(shí)現(xiàn) 29
2.3.2 雙向鏈表與相關(guān)操作實(shí)現(xiàn) 38
2.3.3 循環(huán)鏈表及其相關(guān)操作的
實(shí)現(xiàn) 41
2.3.4 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分析 42
2.4 線性表的應(yīng)用 43
2.4.1 一元多項(xiàng)式的抽象數(shù)據(jù)類(lèi)型 43
2.4.2 多項(xiàng)式的順序表實(shí)現(xiàn) 43
小結(jié) 46
自測(cè)題答案 47
編程項(xiàng)目 48
第3章 棧和隊(duì)列 49
3.1 棧 49
3.1.1 棧概述 49
3.1.2 棧的實(shí)現(xiàn) 50
3.1.3 棧的實(shí)現(xiàn)方式比較 54
3.2 棧的應(yīng)用 55
3.2.1 平衡符號(hào) 55
3.2.2 表達(dá)式求值 57
3.2.3 函數(shù)調(diào)用 61
3.2.4 遞歸與棧 62
3.3 隊(duì)列 67
3.3.1 隊(duì)列概述 67
3.3.2 隊(duì)列的實(shí)現(xiàn) 69
3.3.3 隊(duì)列實(shí)現(xiàn)方法比較 76
3.4 隊(duì)列的應(yīng)用 76
3.4.1 排列問(wèn)題 76
3.4.2 非排列問(wèn)題 77
小結(jié) 79
自測(cè)題答案 79
編程項(xiàng)目 81
第4章 串 82
4.1 串的定義 82
4.1.1 串 82
4.1.2 串的抽象數(shù)據(jù)類(lèi)型 83
4.2 串的存儲(chǔ)實(shí)現(xiàn) 84
4.2.1 串的順序存儲(chǔ)結(jié)構(gòu) 84
4.2.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 87
4.3 串的模式匹配 88
4.3.1 簡(jiǎn)單模式匹配算法 88
4.3.2 KMP算法 90
4.3.3 其他模式匹配算法 94
小結(jié) 96
自測(cè)題答案 97
編程項(xiàng)目 98
第5章 數(shù)組及廣義表 99
5.1 數(shù)組的定義 99
5.1.1 數(shù)組的基本概念 99
5.1.2 數(shù)組的抽象數(shù)據(jù)類(lèi)型 100
5.2 數(shù)組的順序存儲(chǔ) 101
5.2.1 數(shù)組的順序存儲(chǔ)方式 101
5.2.2 數(shù)組的順序存儲(chǔ)的
基本操作 102
5.3 矩陣的壓縮存儲(chǔ) 104
5.3.1 特殊矩陣 104
5.3.2 稀疏矩陣 107
5.4 廣義表 115
5.4.1 廣義表的定義 115
5.4.2 廣義表的存儲(chǔ) 117
5.4.3 廣義表的基本操作 118
小結(jié) 122
自測(cè)題答案 123
編程項(xiàng)目 125
第6章 樹(shù)和二叉樹(shù) 126
6.1 樹(shù)的定義與基本操作 126
6.1.1 樹(shù)的定義與相關(guān)術(shù)語(yǔ) 126
6.1.2 樹(shù)的抽象數(shù)據(jù)類(lèi)型 128
6.2 二叉樹(shù) 129
6.2.1 二叉樹(shù)的定義與基本操作 129
6.2.2 二叉樹(shù)的性質(zhì) 131
6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 133
6.2.4 二叉樹(shù)的遍歷 135
6.2.5 線索化二叉樹(shù) 140
6.3 樹(shù)和森林 144
6.3.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 144
6.3.2 森林、樹(shù)、二叉樹(shù)的
相互轉(zhuǎn)化 147
6.3.3 樹(shù)和森林的遍歷 148
6.4 哈夫曼樹(shù)與哈夫曼編碼 149
6.4.1 哈夫曼樹(shù) 150
6.4.2 哈夫曼編碼 153
小結(jié) 157
自測(cè)題答案 158
編程項(xiàng)目 160
第7章 圖 161
7.1 圖的定義 161
7.1.1 圖的定義和相關(guān)術(shù)語(yǔ) 161
7.1.2 圖的抽象數(shù)據(jù)類(lèi)型 165
7.2 圖的存儲(chǔ)方式 166
7.2.1 數(shù)組表示法 167
7.2.2 鄰接表法 169
7.2.3 十字鏈表法 171
7.2.4 鄰接多重表 173
7.3 圖的遍歷 175
7.3.1 深度優(yōu)先遍歷 175
7.3.2 廣度優(yōu)先遍歷 177
7.4 圖的連通性 180
7.4.1 無(wú)向圖的連通性 180
7.4.2 有向圖的連通性 183
7.5 最小生成樹(shù) 184
7.5.1 基本概念 184
7.5.2 Prim算法 185
7.5.3 Kruskal算法 187
7.6 最短路徑 189
7.6.1 從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的
最短路徑 189
7.6.2 所有點(diǎn)對(duì)的最短路徑 192
7.7 有向無(wú)環(huán)圖的應(yīng)用 195
7.7.1 拓?fù)渑判?span id="epizqqp1gsyu" class="Apple-tab-span" style="white-space:pre"> 195
7.7.2 求解關(guān)鍵路徑 199
小結(jié) 204
自測(cè)題答案 205
編程項(xiàng)目 209
第8章 查找 210
8.1 線性表上的查找 210
8.1.1 順序表上的查找 210
8.1.2 有序表上的查找 211
8.1.3 索引順序表上的查找 215
8.1.4 線性表上的查找算法比較 217
8.2 樹(shù)上的查找 218
8.2.1 二叉排序樹(shù) 218
8.2.2 平衡二叉樹(shù) 226
8.2.3 B-樹(shù) 233
8.3 哈希表 241
8.3.1 哈希表概述 241
8.3.2 哈希函數(shù)的構(gòu)造 242
8.3.3 沖突的解決方法 245
8.3.4 哈希表的查找分析 251
小結(jié) 252
自測(cè)題答案 254
編程項(xiàng)目 257
第9章 排序 258
9.1 插入排序 258
9.1.1 直接插入排序 259
9.1.2 折半插入排序 260
9.1.3 2路插入排序 261
9.1.4 希爾排序 263
9.2 交換排序 266
9.2.1 冒泡排序 266
9.2.2 快速排序 267
9.3 選擇排序 271
9.3.1 直接選擇排序 271
9.3.2 樹(shù)形選擇排序 273
9.3.3 堆排序 274
9.4 歸并排序 278
9.5 基數(shù)排序 281
9.6 各種內(nèi)部排序方法比較 283
9.7 外部排序 286
9.7.1 選擇外部排序的理由 286
9.7.2 簡(jiǎn)單外部排序算法 287
9.7.3 多路合并排序 289
9.7.4 替換-選擇排序 289
小結(jié) 292
自測(cè)題答案 293
編程項(xiàng)目 296
附錄 各章編程項(xiàng)目參考答案 297
參考文獻(xiàn) 391
