數(shù)據(jù)結(jié)構(gòu)是計算機及相關(guān)專業(yè)的核心課程，也是計算機及相關(guān)專業(yè)碩士研究生入學(xué)考試的必考科目，而且是理工專業(yè)的熱門公選課程。本書介紹了數(shù)據(jù)結(jié)構(gòu)、算法以及抽象數(shù)據(jù)類型的概念；介紹了線性表、棧和隊列、字符串和多維數(shù)組、樹和二叉樹、圖等常用數(shù)據(jù)結(jié)構(gòu)；討論了基本的查找和排序技術(shù)。
本書合理規(guī)劃教學(xué)內(nèi)容，梳理知識單元及其拓撲結(jié)構(gòu)，兼顧概念層和實現(xiàn)層，既強調(diào)了數(shù)據(jù)結(jié)構(gòu)的基本概念和原理方法，又注重了數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)和實際運用，在提煉基礎(chǔ)知識的同時，進行了適當?shù)臄U展和提高。
本書內(nèi)容豐富，層次清晰，深入淺出，結(jié)合實例，可作為計算機及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計算機軟件開發(fā)和應(yīng)用的工程技術(shù)人員參考和閱讀。
本書在概念的描述、實例的選擇、知識的前后銜接、內(nèi)容的組織結(jié)構(gòu)，以及教學(xué)內(nèi)容的理解、教學(xué)目標的實現(xiàn)、教學(xué)意圖的融入、教學(xué)方法的運用等方面進行了系統(tǒng)思考和統(tǒng)籌設(shè)計，力圖通過本書為讀者構(gòu)建多層次的知識體系。在問題求解層面，給出問題?想法?算法?程序的思維模式；在算法設(shè)計層面，采用闡述基本思想偽代碼描述算法C語言實現(xiàn)算法的過程模式；在算法分析層面，理解什么是好算法，給出算法分析的基本方法；在存儲結(jié)構(gòu)層面，通過存儲示意圖理解數(shù)據(jù)表示，再給出存儲結(jié)構(gòu)定義；在程序?qū)崿F(xiàn)層面，給出所有數(shù)據(jù)結(jié)構(gòu)的C程序?qū)崿F(xiàn)以及使用舉例；在數(shù)據(jù)結(jié)構(gòu)和算法的運用層面，通過應(yīng)用實例理解如何為求解問題設(shè)計適當?shù)臄?shù)據(jù)結(jié)構(gòu)，如何基于數(shù)據(jù)結(jié)構(gòu)設(shè)計算法，從而將數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計和程序?qū)崿F(xiàn)有機地融合在一起。本書是一本難得的易學(xué)易教的好教材。
目錄
第1章緒論1
1.1問題求解與程序設(shè)計2
1.1.1程序設(shè)計的一般過程2
1.1.2數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用4
1.1.3算法在程序設(shè)計中的作用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算法的時間復(fù)雜度16
1.4.2算法的空間復(fù)雜度17
1.4.3算法分析舉例18
1.5擴展與提高20
1.5.1從數(shù)據(jù)到大數(shù)據(jù)20
1.5.2算法分析的其他漸進符號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實現(xiàn)目錄2.3線性表的順序存儲結(jié)構(gòu)及實現(xiàn)29
2.3.1順序表的存儲結(jié)構(gòu)定義29
2.3.2順序表的實現(xiàn)30
2.3.3順序表的使用34
2.4線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)35
2.4.1單鏈表的存儲結(jié)構(gòu)定義35
2.4.2單鏈表的實現(xiàn)37
2.4.3單鏈表的使用44
2.4.4雙鏈表45
2.4.5循環(huán)鏈表47
2.5順序表和鏈表的比較48
2.6擴展與提高48
2.6.1線性表的靜態(tài)鏈表存儲48
2.6.2順序表的動態(tài)分配方式51
2.7應(yīng)用實例52
2.7.1約瑟夫環(huán)問題52
2.7.2一元多項式求和55
習(xí)題259
第3章棧和隊列63
3.1引言64
3.2棧65
3.2.1棧的邏輯結(jié)構(gòu)65
3.2.2棧的順序存儲結(jié)構(gòu)及實現(xiàn)66
3.2.3棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)68
3.2.4順序棧和鏈棧的比較71
3.3隊列72
3.3.1隊列的邏輯結(jié)構(gòu)72
3.3.2隊列的順序存儲結(jié)構(gòu)及實現(xiàn)73
3.3.3隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)77
3.3.4循環(huán)隊列和鏈隊列的比較80
3.4擴展與提高81
3.4.1兩棧共享空間81
3.4.2雙端隊列82
3.5應(yīng)用舉例83
3.5.1括號匹配問題83
3.5.2表達式求值85
習(xí)題388第4章字符串和多維數(shù)組91
4.1引言92
4.2字符串92
4.2.1字符串的邏輯結(jié)構(gòu)92
4.2.2字符串的存儲結(jié)構(gòu)94
4.2.3模式匹配94
4.3多維數(shù)組98
4.3.1數(shù)組的邏輯結(jié)構(gòu)98
4.3.2數(shù)組的存儲結(jié)構(gòu)與尋址99
4.4矩陣的壓縮存儲100
4.4.1特殊矩陣的壓縮存儲100
4.4.2稀疏矩陣的壓縮存儲102
4.5擴展與提高105
4.5.1稀疏矩陣的轉(zhuǎn)置運算105
4.5.2廣義表107
4.6應(yīng)用實例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樹的存儲結(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二叉樹的存儲結(jié)構(gòu)133
5.5.1順序存儲結(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擴展與提高145
5.8.1二叉樹遍歷的非遞歸算法145
5.8.2線索二叉樹148
5.9應(yīng)用實例151
5.9.1堆與優(yōu)先隊列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圖的存儲結(jié)構(gòu)及實現(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)與拓撲排序187
6.6.2AOE網(wǎng)與關(guān)鍵路徑190
6.7擴展與提高193
6.7.1圖的其他存儲方法193
6.7.2圖的連通性194
6.8應(yīng)用實例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è)計226
7.4.3處理沖突的方法227
7.4.4散列查找的性能分析231
7.4.5開散列表與閉散列表的比較232
7.5各種查找方法的比較232
7.6擴展與提高233
7.6.1順序查找的改進分塊查找233
7.6.2折半查找的改進插值查找234
7.6.3B樹的改進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二路歸并排序的遞歸實現(xiàn)256
8.5.2二路歸并排序的非遞歸實現(xiàn)257
8.6各種排序方法的比較259
8.7擴展與提高261
8.7.1排序問題的時間下界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動態(tài)存儲分配281
附錄C詞匯索引283
參考文獻287
書單推薦
