數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專業(yè)的核心課程，也是計(jì)算機(jī)及相關(guān)專業(yè)碩士研究生入學(xué)考試的必考科目，而且是理工專業(yè)的熱門公選課程。本書介紹了數(shù)據(jù)結(jié)構(gòu)、算法以及抽象數(shù)據(jù)類型的概念；介紹了線性表、棧和隊(duì)列、字符串和多維數(shù)組、樹和二叉樹、圖等常用數(shù)據(jù)結(jié)構(gòu)；討論了基本的查找和排序技術(shù)。
本書合理規(guī)劃教學(xué)內(nèi)容，梳理知識單元及其拓?fù)浣Y(jié)構(gòu)，兼顧概念層和實(shí)現(xiàn)層，既強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)的基本概念和原理方法，又注重了數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)和實(shí)際運(yùn)用，在提煉基礎(chǔ)知識的同時(shí)，進(jìn)行了適當(dāng)?shù)臄U(kuò)展和提高。
本書內(nèi)容豐富，層次清晰，深入淺出，結(jié)合實(shí)例，可作為計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計(jì)算機(jī)軟件開發(fā)和應(yīng)用的工程技術(shù)人員參考和閱讀。
本書在概念的描述、實(shí)例的選擇、知識的前后銜接、內(nèi)容的組織結(jié)構(gòu)，以及教學(xué)內(nèi)容的理解、教學(xué)目標(biāo)的實(shí)現(xiàn)、教學(xué)意圖的融入、教學(xué)方法的運(yùn)用等方面進(jìn)行了系統(tǒng)思考和統(tǒng)籌設(shè)計(jì)，力圖通過本書為讀者構(gòu)建多層次的知識體系。在問題求解層面，給出問題?想法?算法?程序的思維模式；在算法設(shè)計(jì)層面，采用闡述基本思想偽代碼描述算法C語言實(shí)現(xiàn)算法的過程模式；在算法分析層面，理解什么是好算法，給出算法分析的基本方法；在存儲(chǔ)結(jié)構(gòu)層面，通過存儲(chǔ)示意圖理解數(shù)據(jù)表示，再給出存儲(chǔ)結(jié)構(gòu)定義；在程序?qū)崿F(xiàn)層面，給出所有數(shù)據(jù)結(jié)構(gòu)的C程序?qū)崿F(xiàn)以及使用舉例；在數(shù)據(jù)結(jié)構(gòu)和算法的運(yùn)用層面，通過應(yīng)用實(shí)例理解如何為求解問題設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，如何基于數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法，從而將數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)和程序?qū)崿F(xiàn)有機(jī)地融合在一起。本書是一本難得的易學(xué)易教的好教材。
目錄
第1章緒論1
1.1問題求解與程序設(shè)計(jì)2
1.1.1程序設(shè)計(jì)的一般過程2
1.1.2數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用4
1.1.3算法在程序設(shè)計(jì)中的作用6
1.1.4本書討論的主要內(nèi)容7
1.2數(shù)據(jù)結(jié)構(gòu)的基本概念8
1.2.1數(shù)據(jù)結(jié)構(gòu)8
1.2.2抽象數(shù)據(jù)類型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法14
1.4算法分析15
1.4.1算法的時(shí)間復(fù)雜度16
1.4.2算法的空間復(fù)雜度17
1.4.3算法分析舉例18
1.5擴(kuò)展與提高20
1.5.1從數(shù)據(jù)到大數(shù)據(jù)20
1.5.2算法分析的其他漸進(jìn)符號22
習(xí)題123
第2章線性表25
2.1引言26
2.2線性表的邏輯結(jié)構(gòu)27
2.2.1線性表的定義27
2.2.2線性表的抽象數(shù)據(jù)類型定義27數(shù)據(jù)結(jié)構(gòu)從概念到C實(shí)現(xiàn)目錄2.3線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)29
2.3.1順序表的存儲(chǔ)結(jié)構(gòu)定義29
2.3.2順序表的實(shí)現(xiàn)30
2.3.3順序表的使用34
2.4線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)35
2.4.1單鏈表的存儲(chǔ)結(jié)構(gòu)定義35
2.4.2單鏈表的實(shí)現(xiàn)37
2.4.3單鏈表的使用44
2.4.4雙鏈表45
2.4.5循環(huán)鏈表47
2.5順序表和鏈表的比較48
2.6擴(kuò)展與提高48
2.6.1線性表的靜態(tài)鏈表存儲(chǔ)48
2.6.2順序表的動(dòng)態(tài)分配方式51
2.7應(yīng)用實(shí)例52
2.7.1約瑟夫環(huán)問題52
2.7.2一元多項(xiàng)式求和55
習(xí)題259
第3章棧和隊(duì)列63
3.1引言64
3.2棧65
3.2.1棧的邏輯結(jié)構(gòu)65
3.2.2棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)66
3.2.3棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)68
3.2.4順序棧和鏈棧的比較71
3.3隊(duì)列72
3.3.1隊(duì)列的邏輯結(jié)構(gòu)72
3.3.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)73
3.3.3隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)77
3.3.4循環(huán)隊(duì)列和鏈隊(duì)列的比較80
3.4擴(kuò)展與提高81
3.4.1兩棧共享空間81
3.4.2雙端隊(duì)列82
3.5應(yīng)用舉例83
3.5.1括號匹配問題83
3.5.2表達(dá)式求值85
習(xí)題388第4章字符串和多維數(shù)組91
4.1引言92
4.2字符串92
4.2.1字符串的邏輯結(jié)構(gòu)92
4.2.2字符串的存儲(chǔ)結(jié)構(gòu)94
4.2.3模式匹配94
4.3多維數(shù)組98
4.3.1數(shù)組的邏輯結(jié)構(gòu)98
4.3.2數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址99
4.4矩陣的壓縮存儲(chǔ)100
4.4.1特殊矩陣的壓縮存儲(chǔ)100
4.4.2稀疏矩陣的壓縮存儲(chǔ)102
4.5擴(kuò)展與提高105
4.5.1稀疏矩陣的轉(zhuǎn)置運(yùn)算105
4.5.2廣義表107
4.6應(yīng)用實(shí)例111
4.6.1發(fā)紙牌111
4.6.2八皇后問題112
習(xí)題4115
第5章樹和二叉樹119
5.1引言120
5.2樹的邏輯結(jié)構(gòu)121
5.2.1樹的定義和基本術(shù)語121
5.2.2樹的抽象數(shù)據(jù)類型定義123
5.2.3樹的遍歷操作123
5.3樹的存儲(chǔ)結(jié)構(gòu)124
5.3.1雙親表示法124
5.3.2孩子表示法125
5.3.3孩子兄弟表示法126
5.4二叉樹的邏輯結(jié)構(gòu)127
5.4.1二叉樹的定義127
5.4.2二叉樹的基本性質(zhì)129
5.4.3二叉樹的抽象數(shù)據(jù)類型定義130
5.4.4二叉樹的遍歷操作131
5.5二叉樹的存儲(chǔ)結(jié)構(gòu)133
5.5.1順序存儲(chǔ)結(jié)構(gòu)133
5.5.2二叉鏈表134
5.5.3三叉鏈表138
5.6森林138
5.6.1森林的邏輯結(jié)構(gòu)138
5.6.2樹、森林與二叉樹的轉(zhuǎn)換139
5.7最優(yōu)二叉樹141
5.7.1哈夫曼算法141
5.7.2哈夫曼編碼143
5.8擴(kuò)展與提高145
5.8.1二叉樹遍歷的非遞歸算法145
5.8.2線索二叉樹148
5.9應(yīng)用實(shí)例151
5.9.1堆與優(yōu)先隊(duì)列151
5.9.2并查集154
習(xí)題5155
第6章圖159
6.1引言160
6.2圖的邏輯結(jié)構(gòu)161
6.2.1圖的定義和基本術(shù)語161
6.2.2圖的抽象數(shù)據(jù)類型定義163
6.2.3圖的遍歷操作164
6.3圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)167
6.3.1鄰接矩陣167
6.3.2鄰接表170
6.3.3鄰接矩陣和鄰接表的比較174
6.4最小生成樹175
6.4.1Prim算法176
6.4.2Kruskal算法178
6.5最短路徑182
6.5.1Dijkstra算法183
6.5.2Floyd算法185
6.6有向無環(huán)圖及其應(yīng)用187
6.6.1AOV網(wǎng)與拓?fù)渑判?87
6.6.2AOE網(wǎng)與關(guān)鍵路徑190
6.7擴(kuò)展與提高193
6.7.1圖的其他存儲(chǔ)方法193
6.7.2圖的連通性194
6.8應(yīng)用實(shí)例196
6.8.1七巧板涂色問題196
6.8.2醫(yī)院選址問題198
習(xí)題6200
第7章查找技術(shù)205
7.1概述206
7.1.1查找的基本概念206
7.1.2查找算法的性能207
7.2線性表的查找技術(shù)207
7.2.1順序查找207
7.2.2折半查找208
7.3樹表的查找技術(shù)211
7.3.1二叉排序樹211
7.3.2平衡二叉樹217
7.3.3B樹220
7.4散列表的查找技術(shù)225
7.4.1散列查找的基本思想225
7.4.2散列函數(shù)的設(shè)計(jì)226
7.4.3處理沖突的方法227
7.4.4散列查找的性能分析231
7.4.5開散列表與閉散列表的比較232
7.5各種查找方法的比較232
7.6擴(kuò)展與提高233
7.6.1順序查找的改進(jìn)分塊查找233
7.6.2折半查找的改進(jìn)插值查找234
7.6.3B樹的改進(jìn)B 樹235
習(xí)題7236
第8章排序技術(shù)239
8.1概述240
8.1.1排序的基本概念240
8.1.2排序算法的性能241
8.2插入排序241
8.2.1直接插入排序241
8.2.2希爾排序243
8.3交換排序245
8.3.1起泡排序245
8.3.2快速排序247
8.4選擇排序250
8.4.1簡單選擇排序250
8.4.2堆排序252
8.5歸并排序256
8.5.1二路歸并排序的遞歸實(shí)現(xiàn)256
8.5.2二路歸并排序的非遞歸實(shí)現(xiàn)257
8.6各種排序方法的比較259
8.7擴(kuò)展與提高261
8.7.1排序問題的時(shí)間下界261
8.7.2基數(shù)排序262
習(xí)題8264
附錄A預(yù)備知識269
A.1數(shù)學(xué)術(shù)語269
A.2級數(shù)求和269
A.3集合270
A.4關(guān)系271
附錄BC語言基本語法273
B.1程序結(jié)構(gòu)273
B.2數(shù)據(jù)的基本表現(xiàn)形式常量和變量274
B.3數(shù)據(jù)類型275
B.4控制語句277
B.5函數(shù)278
B.6動(dòng)態(tài)存儲(chǔ)分配281
附錄C詞匯索引283
參考文獻(xiàn)287
書單推薦
