前言
數(shù)據(jù)結(jié)構(gòu)研究計(jì)算機(jī)系統(tǒng)內(nèi)表示、組織、處理和存儲(chǔ)數(shù)據(jù)的方式,算法則著重于程序處理流程的優(yōu)化,二者相輔相成,共同提高程序的時(shí)間與空間效率。數(shù)據(jù)結(jié)構(gòu)課程已經(jīng)成為高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)、信息管理與信息系統(tǒng)、軟件工程等專業(yè)的核心課程,并有越來(lái)越多的專業(yè)技術(shù)人員對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)提出了更高的需求。
本書(shū)共10章和兩個(gè)附錄。第1章緒論,主要介紹學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義、數(shù)據(jù)結(jié)構(gòu)的基本概念,算法中的抽象數(shù)據(jù)類型及其在C++語(yǔ)言中的表示與算法實(shí)現(xiàn)的原則,算法的定義、特征及效率分析。第2章線性表,主要介紹線性表的基本概念和邏輯結(jié)構(gòu),線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈表的存儲(chǔ)結(jié)構(gòu),順序表、單鏈表、雙向鏈表及循環(huán)鏈表的相關(guān)操作與C++算法實(shí)現(xiàn)。第3章棧與隊(duì)列,主要介紹棧和隊(duì)列的基本概念、存儲(chǔ)結(jié)構(gòu)和基本操作,以及對(duì)應(yīng)的C++算法實(shí)現(xiàn),并以算術(shù)表達(dá)式轉(zhuǎn)化和求值為例介紹棧和隊(duì)列的應(yīng)用。第4章串,主要介紹串的定義、特點(diǎn)、存儲(chǔ)結(jié)構(gòu)和基本的串處理操作,以及對(duì)應(yīng)的C++算法實(shí)現(xiàn)。第5章數(shù)組和廣義表,主要介紹數(shù)組和廣義表的定義、特點(diǎn)、存儲(chǔ)結(jié)構(gòu)與C++算法實(shí)現(xiàn)。第6章樹(shù)和二叉樹(shù),主要介紹二叉樹(shù)的基本概念、存儲(chǔ)結(jié)構(gòu)及其操作,并研究樹(shù)和森林、二叉樹(shù)之間的相互轉(zhuǎn)換方法，以及樹(shù)的一個(gè)重要應(yīng)用——最優(yōu)樹(shù)和哈夫曼編碼方法。第7章圖,主要介紹圖的基本概念,圖的鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等存儲(chǔ)結(jié)構(gòu),圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷算法、最小生成樹(shù)算法以及其他應(yīng)用算法。第8章查找,主要介紹查找的基本概念,靜態(tài)查找表、動(dòng)態(tài)查找表及哈希表的表示方法,順序查找、折半查找、分塊查找、二叉排序樹(shù)、二叉平衡樹(shù)、B樹(shù)、哈希表等查找方法以及C++算法實(shí)現(xiàn)與算法分析。第9章排序,主要介紹排序的基本概念,插入排序、希爾排序、快速排序、直接選擇排序、堆排序、歸并排序、基數(shù)排序的方法與C++算法實(shí)現(xiàn),以及各種排序算法的比較分析。第10章是一個(gè)綜合案例,通過(guò)實(shí)際生產(chǎn)問(wèn)題的求解過(guò)程，深化讀者對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高讀者的綜合應(yīng)用能力,展示數(shù)據(jù)結(jié)構(gòu)與算法的魅力。附錄A給出本書(shū)中算法實(shí)現(xiàn)時(shí)的文件夾結(jié)構(gòu),附錄B給出本書(shū)中算法實(shí)現(xiàn)時(shí)C++類中間的UML關(guān)系圖。每章習(xí)題及其參考答案可以通過(guò)掃描每章后所附的二維碼得到。
本書(shū)的主要特點(diǎn)如下。
(1) 參照數(shù)據(jù)結(jié)構(gòu)普遍的分類規(guī)范進(jìn)行內(nèi)容編排,涵蓋了一般需要掌握的所有基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法,并對(duì)算法的效率進(jìn)行了對(duì)比分析。
(2) 實(shí)例引入和圖文講解展現(xiàn)了將實(shí)際問(wèn)題轉(zhuǎn)換為抽象的數(shù)據(jù)結(jié)構(gòu)的方法，并設(shè)計(jì)了相應(yīng)的算法。
(3) 基于C++語(yǔ)言面向?qū)ο蟮母拍詈蛯?duì)象類設(shè)計(jì)原則進(jìn)行算法實(shí)現(xiàn),體現(xiàn)了面向?qū)ο蟮娜筇攸c(diǎn)——封裝、繼承和多態(tài),利用封裝實(shí)現(xiàn)其獨(dú)立的原理特點(diǎn),利用繼承實(shí)現(xiàn)各個(gè)數(shù)據(jù)結(jié)構(gòu)之間的關(guān)聯(lián),利用多態(tài)展現(xiàn)數(shù)據(jù)結(jié)構(gòu)在實(shí)際問(wèn)題中的調(diào)用方法。附錄B中涵蓋了各個(gè)C++類對(duì)應(yīng)的UML類圖,從中可清晰地看到每個(gè)類中的屬性與方法,以及各個(gè)類之間的關(guān)系。
(4) 為了滿足教學(xué)過(guò)程中的上機(jī)練習(xí)需求,書(shū)中所有的算法實(shí)現(xiàn)均可以通過(guò)直接編譯運(yùn)行,并附上相應(yīng)的算例和運(yùn)行結(jié)果,便于讀者對(duì)比實(shí)現(xiàn)。同時(shí)，采用.h頭文件與.cpp定義文件分離的方式進(jìn)行算法實(shí)現(xiàn),避免對(duì)數(shù)據(jù)結(jié)構(gòu)重復(fù)定義,引用位置也在附錄A的文件夾結(jié)構(gòu)中詳細(xì)展示。
(5) 建議將書(shū)中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行自主實(shí)現(xiàn),但同時(shí)本書(shū)也介紹了幾種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的標(biāo)準(zhǔn)模板庫(kù)(STL)里的容器,若讀者時(shí)間不足,可以在了解后直接使用現(xiàn)有組件。
(6) 每一章最后通過(guò)掃描二維碼都有匹配的思考和練習(xí)題,包含概念理解、算法拓展、解決實(shí)際問(wèn)題等題型,同時(shí)參考答案里附上了每個(gè)問(wèn)題的解題思路、可執(zhí)行的C++代碼及運(yùn)行結(jié)果供讀者參考。
本書(shū)內(nèi)容豐富、結(jié)構(gòu)合理、實(shí)用性強(qiáng),配有電子課件、完整的程序源代碼、習(xí)題參考答案等教學(xué)資源。
本書(shū)由張千帆任主編,莫嘉銘、王翀任副主編。本書(shū)的編寫(xiě)得到了漆鵬飛、吳慶華的支持,并參考了同行專家的著作和成果,在此向他們表示衷心的感謝！
由于作者水平有限,書(shū)中難免有不當(dāng)之處,敬請(qǐng)專家和讀者批評(píng)指正。
張千帆2020年5月
目錄
第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)1
1.1.1學(xué)習(xí)數(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)的類型4
1.2抽象數(shù)據(jù)類型5
1.2.1C++中的數(shù)據(jù)類型6
1.2.2抽象數(shù)據(jù)類型與C++特性6
1.3算法分析10
1.3.1問(wèn)題、算法與程序10
1.3.2算法效率的度量10
本章小結(jié)14
第2章線性表15
2.1線性表的基本概念15
2.1.1線性表的定義與特點(diǎn)15
2.1.2線性表的存儲(chǔ)結(jié)構(gòu)15
2.2順序表的算法實(shí)現(xiàn)17
2.2.1順序表的創(chuàng)建和插入19
2.2.2順序表內(nèi)結(jié)點(diǎn)的查找23
2.2.3順序表內(nèi)元素的刪除28
2.3單鏈表的算法實(shí)現(xiàn)30
2.3.1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)和一般形式30
2.3.2單鏈表的創(chuàng)建和插入32
2.3.3單鏈表內(nèi)數(shù)據(jù)元素的查找37
2.3.4單鏈表內(nèi)數(shù)據(jù)元素的刪除40
2.3.5單鏈表的合并43
2.4雙向鏈表的算法實(shí)現(xiàn)47
2.4.1雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)和一般形式47
2.4.2雙向鏈表的創(chuàng)建和插入49
2.4.3雙向鏈表內(nèi)元素的查找53
2.4.4雙向鏈表內(nèi)元素的刪除55
2.5循環(huán)鏈表的算法實(shí)現(xiàn)57
2.5.1循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)和一般形式57
2.5.2循環(huán)鏈表的創(chuàng)建58
2.6線性表的應(yīng)用——一元多項(xiàng)式的存儲(chǔ)和相加63
2.6.1一元多項(xiàng)式的存儲(chǔ)和相加的實(shí)現(xiàn)方式63
2.6.2一元多項(xiàng)式的存儲(chǔ)和相加的實(shí)現(xiàn)65
2.7STL的使用68
2.7.1STL簡(jiǎn)介68
2.7.2STL應(yīng)用實(shí)例68
本章小結(jié)69
第3章棧與隊(duì)列71
3.1棧的基本概念71
3.1.1棧的定義與特點(diǎn)71
3.1.2棧的兩類存儲(chǔ)結(jié)構(gòu)71
3.2順序棧的算法實(shí)現(xiàn)72
3.2.1順序棧的建立和順序棧入棧72
3.2.2順序棧出棧74
3.3隊(duì)列的基本概念76
3.3.1隊(duì)列的定義與特點(diǎn)76
3.3.2隊(duì)列的存儲(chǔ)結(jié)構(gòu)77
3.4順序隊(duì)列的算法實(shí)現(xiàn)78
3.4.1順序隊(duì)列的建立和順序隊(duì)列入隊(duì)79
3.4.2順序隊(duì)列出隊(duì)80
3.5循環(huán)隊(duì)列的算法實(shí)現(xiàn)83
3.5.1循環(huán)隊(duì)列的建立和循環(huán)隊(duì)列入隊(duì)83
3.5.2循環(huán)隊(duì)列出隊(duì)85
3.6鏈隊(duì)列的算法實(shí)現(xiàn)87
3.6.1鏈隊(duì)列的建立和鏈隊(duì)列入隊(duì)87
3.6.2鏈隊(duì)列出隊(duì)88
3.7棧和隊(duì)列的應(yīng)用——算術(shù)表達(dá)式的轉(zhuǎn)化和求值89
本章小結(jié)96
第4章串97
4.1串的基本概念97
4.1.1串的定義與特點(diǎn)97
4.1.2串的存儲(chǔ)結(jié)構(gòu)98
4.2串的算法實(shí)現(xiàn)100
4.2.1串賦值算法100
4.2.2求子串算法102
4.2.3串比較算法104
4.2.4串連接算法106
4.3串的模式匹配算法實(shí)現(xiàn)107
4.3.1串的樸素模式匹配算法107
4.3.2改進(jìn)的模式匹配算法109
本章小結(jié)114
第5章數(shù)組和廣義表115
5.1數(shù)組的基本概念115
5.1.1數(shù)組的定義與特點(diǎn)115
5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)116
5.2特殊矩陣的壓縮存儲(chǔ)117
5.3矩陣的算法實(shí)現(xiàn)120
5.4廣義表的基本概念126
5.4.1廣義表的定義與圖形表示126
5.4.2廣義表的存儲(chǔ)結(jié)構(gòu)127
5.5廣義表的算法實(shí)現(xiàn)128
本章小結(jié)134
第6章樹(shù)和二叉樹(shù)135
6.1樹(shù)的基本概念135
6.1.1樹(shù)的定義與基本術(shù)語(yǔ)135
6.1.2樹(shù)的表示形式和存儲(chǔ)結(jié)構(gòu)136
6.2二叉樹(shù)的基本概念140
6.2.1二叉樹(shù)的定義與性質(zhì)140
6.2.2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)142
6.2.3樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換144
6.2.4二叉樹(shù)的遍歷146
6.3二叉樹(shù)算法實(shí)現(xiàn)147
6.3.1二叉樹(shù)的建立147
6.3.2遞歸的二叉樹(shù)前序遍歷、中序遍歷、后序遍歷150
6.3.3非遞歸的二叉樹(shù)前序遍歷153
6.3.4非遞歸的二叉樹(shù)中序遍歷155
6.3.5非遞歸的二叉樹(shù)后序遍歷157
6.4哈夫曼樹(shù)及其應(yīng)用161
6.4.1哈夫曼樹(shù)與哈夫曼編碼161
6.4.2哈夫曼算法實(shí)現(xiàn)162
本章小結(jié)168
第7章圖169
7.1圖的基本概念169
7.1.1圖的定義和術(shù)語(yǔ)169
7.1.2圖的表示與存儲(chǔ)結(jié)構(gòu)173
7.2圖的構(gòu)造算法實(shí)現(xiàn)176
7.2.1圖的基本類定義176
7.2.2構(gòu)造順序表存儲(chǔ)的圖179
7.2.3構(gòu)造鄰接表存儲(chǔ)的無(wú)向圖與有向圖182
7.2.4構(gòu)造十字鏈表存儲(chǔ)的有向圖188
7.2.5構(gòu)造鄰接多重表存儲(chǔ)的無(wú)向圖193
7.3圖的遍歷算法實(shí)現(xiàn)197
7.3.1深度優(yōu)先遍歷算法198
7.3.2廣度優(yōu)先遍歷算法200
7.4最小生成樹(shù)算法實(shí)現(xiàn)204
7.4.1普里姆算法205
7.4.2克魯斯卡爾算法209
7.5圖的應(yīng)用216
7.5.1拓?fù)渑判?16
7.5.2關(guān)鍵路徑220
7.5.3最短路徑——迪杰斯克拉算法225
7.5.4最短路徑——弗洛伊德算法229
本章小結(jié)234
第8章查找235
8.1查找的基本概念235
8.1.1查找的相關(guān)術(shù)語(yǔ)235
8.1.2查找表結(jié)構(gòu)236
8.2順序表查找算法實(shí)現(xiàn)236
8.3有序順序表的折半查找算法實(shí)現(xiàn)240
8.4索引順序表的分塊查找算法實(shí)現(xiàn)245
8.4.1索引表245
8.4.2分塊查找算法實(shí)現(xiàn)246
8.5二叉排序樹(shù)及其算法實(shí)現(xiàn)250
8.5.1二叉排序樹(shù)及其查找過(guò)程250
8.5.2二叉排序樹(shù)建立及插入結(jié)點(diǎn)的過(guò)程251
8.5.3二叉排序樹(shù)刪除結(jié)點(diǎn)的過(guò)程251
8.5.4二叉排序樹(shù)的算法實(shí)現(xiàn)253
8.6平衡二叉樹(shù)及其算法實(shí)現(xiàn)258
8.6.1平衡二叉排序樹(shù)及其構(gòu)造258
8.6.2平衡二叉排序樹(shù)算法實(shí)現(xiàn)261
8.7B樹(shù)及其算法實(shí)現(xiàn)268
8.7.1B樹(shù)268
8.7.2B樹(shù)的查找269
8.7.3B樹(shù)的插入269
8.7.4B樹(shù)的刪除271
8.7.5B樹(shù)的算法實(shí)現(xiàn)273
8.8哈希查找的算法實(shí)現(xiàn)282
8.8.1哈希表282
8.8.2哈希函數(shù)的構(gòu)造方法282
8.8.3哈希沖突的處理方法283
8.8.4哈希表的算法實(shí)現(xiàn)285
本章小結(jié)289
第9章排序290
9.1排序的基本概念290
9.1.1排序相關(guān)術(shù)語(yǔ)介紹290
9.1.2常用的內(nèi)部排序算法類型簡(jiǎn)介291
9.2插入排序的算法實(shí)現(xiàn)292
9.2.1直接插入排序292
9.2.2希爾排序295
9.3交換排序的算法實(shí)現(xiàn)299
9.4選擇排序的算法實(shí)現(xiàn)303
9.4.1直接選擇排序303
9.4.2堆排序306
9.5歸并排序的算法實(shí)現(xiàn)313
9.6基數(shù)排序的算法實(shí)現(xiàn)316
9.7各種內(nèi)部排序方法的比較321
9.7.1時(shí)間性能321
9.7.2空間性能321
9.7.3排序方法的穩(wěn)定性322
9.8外部排序322
本章小結(jié)322
第10章綜合案例323
10.1背景介紹323
10.2問(wèn)題分解323
10.2.1旅行商問(wèn)題323
10.2.2動(dòng)態(tài)規(guī)劃325
10.2.3帶酒店選擇的旅行商問(wèn)題328
10.3總結(jié)與思考331
附錄A文件夾結(jié)構(gòu)332
附錄BUML類圖334
B.1第2章線性表的相關(guān)類圖334
B.2第3章棧與隊(duì)列的相關(guān)類圖336
B.3第4章串的相關(guān)類圖337
B.4第5章數(shù)組和廣義表的相關(guān)類圖338
B.5第6章樹(shù)和二叉樹(shù)的相關(guān)類圖339
B.6第7章圖的相關(guān)類圖341
B.7第8章查找的相關(guān)類圖344
B.8第9章排序的相關(guān)類圖346
參考文獻(xiàn)347
書(shū)單推薦
