數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)的核心課程，也是計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)碩士研究生入學(xué)考試的必考科目，而且是理工專(zhuān)業(yè)的熱門(mén)公選課程。本書(shū)介紹了數(shù)據(jù)結(jié)構(gòu)、算法以及抽象數(shù)據(jù)類(lèi)型的概念；介紹了線性表、棧和隊(duì)列、字符串和多維數(shù)組、樹(shù)和二叉樹(shù)、圖等常用數(shù)據(jù)結(jié)構(gòu)；討論了基本的查找和排序技術(shù)。
本書(shū)合理規(guī)劃教學(xué)內(nèi)容，梳理知識(shí)單元及其拓?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í)的同時(shí)，進(jìn)行了適當(dāng)?shù)臄U(kuò)展和提高。
本書(shū)內(nèi)容豐富，層次清晰，深入淺出，結(jié)合實(shí)例，可作為計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計(jì)算機(jī)軟件開(kāi)發(fā)和應(yīng)用的工程技術(shù)人員參考和閱讀。
本書(shū)在概念的描述、實(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ì)，力圖通過(guò)本書(shū)為讀者構(gòu)建多層次的知識(shí)體系。在問(wèn)題求解層面，給出問(wèn)題?想法?算法?程序的思維模式；在算法設(shè)計(jì)層面，采用闡述基本思想偽代碼描述算法C語(yǔ)言實(shí)現(xiàn)算法的過(guò)程模式；在算法分析層面，理解什么是好算法，給出算法分析的基本方法；在存儲(chǔ)結(jié)構(gòu)層面，通過(guò)存儲(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)用層面，通過(guò)應(yīng)用實(shí)例理解如何為求解問(wèn)題設(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ī)地融合在一起。本書(shū)是一本難得的易學(xué)易教的好教材。
目錄
第1章緒論1
1.1問(wèn)題求解與程序設(shè)計(jì)2
1.1.1程序設(shè)計(jì)的一般過(guò)程2
1.1.2數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用4
1.1.3算法在程序設(shè)計(jì)中的作用6
1.1.4本書(shū)討論的主要內(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ù)類(lèi)型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)符號(hào)22
習(xí)題123
第2章線性表25
2.1引言26
2.2線性表的邏輯結(jié)構(gòu)27
2.2.1線性表的定義27
2.2.2線性表的抽象數(shù)據(jù)類(lèi)型定義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)問(wè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括號(hào)匹配問(wèn)題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八皇后問(wèn)題112
習(xí)題4115
第5章樹(shù)和二叉樹(shù)119
5.1引言120
5.2樹(shù)的邏輯結(jié)構(gòu)121
5.2.1樹(shù)的定義和基本術(shù)語(yǔ)121
5.2.2樹(shù)的抽象數(shù)據(jù)類(lèi)型定義123
5.2.3樹(shù)的遍歷操作123
5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)124
5.3.1雙親表示法124
5.3.2孩子表示法125
5.3.3孩子兄弟表示法126
5.4二叉樹(shù)的邏輯結(jié)構(gòu)127
5.4.1二叉樹(shù)的定義127
5.4.2二叉樹(shù)的基本性質(zhì)129
5.4.3二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義130
5.4.4二叉樹(shù)的遍歷操作131
5.5二叉樹(shù)的存儲(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樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換139
5.7最優(yōu)二叉樹(shù)141
5.7.1哈夫曼算法141
5.7.2哈夫曼編碼143
5.8擴(kuò)展與提高145
5.8.1二叉樹(shù)遍歷的非遞歸算法145
5.8.2線索二叉樹(shù)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ù)語(yǔ)161
6.2.2圖的抽象數(shù)據(jù)類(lèi)型定義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最小生成樹(shù)175
6.4.1Prim算法176
6.4.2Kruskal算法178
6.5最短路徑182
6.5.1Dijkstra算法183
6.5.2Floyd算法185
6.6有向無(wú)環(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七巧板涂色問(wèn)題196
6.8.2醫(yī)院選址問(wèn)題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ù)表的查找技術(shù)211
7.3.1二叉排序樹(shù)211
7.3.2平衡二叉樹(shù)217
7.3.3B樹(shù)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開(kāi)散列表與閉散列表的比較232
7.5各種查找方法的比較232
7.6擴(kuò)展與提高233
7.6.1順序查找的改進(jìn)分塊查找233
7.6.2折半查找的改進(jìn)插值查找234
7.6.3B樹(shù)的改進(jìn)B 樹(shù)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簡(jiǎn)單選擇排序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排序問(wèn)題的時(shí)間下界261
8.7.2基數(shù)排序262
習(xí)題8264
附錄A預(yù)備知識(shí)269
A.1數(shù)學(xué)術(shù)語(yǔ)269
A.2級(jí)數(shù)求和269
A.3集合270
A.4關(guān)系271
附錄BC語(yǔ)言基本語(yǔ)法273
B.1程序結(jié)構(gòu)273
B.2數(shù)據(jù)的基本表現(xiàn)形式常量和變量274
B.3數(shù)據(jù)類(lèi)型275
B.4控制語(yǔ)句277
B.5函數(shù)278
B.6動(dòng)態(tài)存儲(chǔ)分配281
附錄C詞匯索引283
參考文獻(xiàn)287
書(shū)單推薦
