書在選材與編排上，以可讀可學(xué)可用可研可練為目標(biāo)。全書共8章，內(nèi)容涵蓋緒論、線性表、棧和隊列、數(shù)組和矩陣、樹和二叉樹、圖、查找以及排序。全書共有118個算法、61個示例、21個應(yīng)用案例、212道練習(xí)題。練習(xí)題題型包括填空題、簡答題、應(yīng)用題、算法設(shè)計題和上機(jī)練習(xí)題五類，滿足原理理解、知識應(yīng)用、模仿、創(chuàng)新、算法訓(xùn)練及實踐訓(xùn)練多方面需求。每章小結(jié)給出全章知識結(jié)構(gòu)圖以及相關(guān)算法與應(yīng)用匯總。 本書內(nèi)容豐富、編排新穎、圖文并茂。原理敘述直達(dá)要義，算法步驟與偽碼一一對應(yīng)�？勺鳛楦叩葘W(xué)校計算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教材，也可供從事計算機(jī)軟件開發(fā)與應(yīng)用的工程技術(shù)人員參考。
數(shù)據(jù)結(jié)構(gòu)課程對計算機(jī)相關(guān)專業(yè)來講是專業(yè)基礎(chǔ)課，并因其重要性被廣泛作為學(xué)位課和考研課。數(shù)據(jù)結(jié)構(gòu)的研究范疇涵蓋典型的邏輯結(jié)構(gòu)、這些邏輯結(jié)構(gòu)在計算機(jī)中的實現(xiàn)、算法分析及典型算法與應(yīng)用等。邏輯結(jié)構(gòu)用于研究對象的抽象與建模，存儲設(shè)計的好壞直接決定問題求解的難易和算法性能，這些都是用計算機(jī)解決問題時不可或缺的知識與技能。因此，從課程研究內(nèi)容看，數(shù)據(jù)結(jié)構(gòu)課程是一門程序設(shè)計基礎(chǔ)課，也是程序設(shè)計能力提升的進(jìn)階課。正因為該課程的重要性，已出版的《數(shù)據(jù)結(jié)構(gòu)》教材林林總總，且其發(fā)展從未停息。2010年，本教學(xué)團(tuán)隊出版了《數(shù)據(jù)結(jié)構(gòu)》（ISBN: 9787302214755）、《數(shù)據(jù)結(jié)構(gòu)實踐教程》（ISBN: 9787302214762）、《數(shù)據(jù)結(jié)構(gòu)習(xí)題及學(xué)習(xí)指導(dǎo)》（ISBN: 9787302214779）系列教材。十多年過去了，時代發(fā)展對工科人才培養(yǎng)的要求不斷變化著。變化的時代和變化的學(xué)生使我們積累了與時俱進(jìn)的教學(xué)經(jīng)驗。在獲得首批線下一流本科課程榮譽(yù)之際，編者決定重寫《數(shù)據(jù)結(jié)構(gòu)》教程及修訂相關(guān)系列教材。為契合新工科人才培養(yǎng)需要和工程專業(yè)認(rèn)證對計算機(jī)類學(xué)生的畢業(yè)要求，本教材立足于實用，以可讀可學(xué)可教可研可練為宗旨設(shè)計編排內(nèi)容并將教材取名為《數(shù)據(jù)結(jié)構(gòu)原理與應(yīng)用》。
●可讀。撰寫過程中，從多方面考慮教材的可讀性。概念及原理等新知識的介紹首先以文字陳述，并做到精準(zhǔn)、簡明、扼要，直明要義；然后以示例展示，將概念及原理具化，使知識一目了然。所有內(nèi)容盡可能圖文并茂。此外，為了簡潔和增加可讀性且考慮專業(yè)特性，本教材選用C/C 語言，但不拘泥于兩者的嚴(yán)格語法，集兩者優(yōu)點呈現(xiàn)算法。 ●可學(xué)。首先，在算法描述上，教材選用了對學(xué)習(xí)者要求較低的面向過程的方法，但借用模板概念解決數(shù)據(jù)類型的抽象問題。這里主要考慮到面向?qū)ο蟮某绦蛟O(shè)計有完整的理論體系和架構(gòu)，用它描述和理解算法對學(xué)生要求很高。而在數(shù)據(jù)結(jié)構(gòu)課程中，語言本身只是一個工具。面向過程的描述進(jìn)一步簡化語法部分，突出問題求解本身，降低學(xué)習(xí)難度。其次，各種結(jié)構(gòu)都有豐富的應(yīng)用背景，滿足學(xué)生希冀獲取解決問題的方法及學(xué)得可用知識與技能的本能愿望。學(xué)生通過理解、記憶、驗證、模仿、思考能切實感到收獲。
●可教。用實際教學(xué)中積累的思路設(shè)計與組織教材內(nèi)容，例如算法講解給出算法的來龍去脈。首先根據(jù)算法思想分析存儲設(shè)計和輔助變量設(shè)計，再給出算法設(shè)計，并且將算法步驟與算法描述一一對應(yīng)，呈現(xiàn)代碼的生成過程。教材中大量的圖示及應(yīng)用示例為教師教學(xué)提供了豐富的教學(xué)素材，教輔PPT將盡量展示算法執(zhí)行過程。
●可研。許多算法介紹后都設(shè)置了算法討論部分，提出相關(guān)問題或更深層次的問題，拓展教學(xué)深度與廣度，引導(dǎo)思考與研究。例如在用順序表實現(xiàn)一元多項式求和問題中，在算法討論部分拋出一元稀疏多項式求和的問題以激發(fā)思考，也為后續(xù)新知識進(jìn)行鋪墊，增加教材內(nèi)容的連貫性。
●可練。教材提供多層次的練習(xí)素材。填空題用于復(fù)習(xí)理論知識和加深對原理的理解；簡答題與應(yīng)用題用于知識的應(yīng)用與分析能力的訓(xùn)練；算法設(shè)計題與上機(jī)練習(xí)題用于設(shè)計與編程技能訓(xùn)練。多層次的練習(xí)題可滿足學(xué)習(xí)者各層次上的需求。
總之，這是一本考慮當(dāng)下聚焦的應(yīng)用型和創(chuàng)新型人才培養(yǎng)需要，以可用實用為宗旨的一部具有時代氣息的教材。教材的配套資源有教學(xué)PPT、書中算法實現(xiàn)的源碼、實踐教程等。另應(yīng)新時代發(fā)展需求，后期會提供微課。
后感謝教學(xué)團(tuán)隊老師的精誠合作與辛苦付出。周建美編寫了第3章和第4章，季峰和陳森博編寫了第6章，丁紅編寫了第7章，徐慧編寫了其余章節(jié)并進(jìn)行全稿統(tǒng)稿。團(tuán)隊其他老師（如管致錦教授、顧頎博士、朱玲玲副教授、陳德裕副教授等）參與了本書的審稿工作，在此也謝謝他們的寶貴意見。
雖然竭盡所能，但由于編者知識、能力和時間有限，書中仍難免有疏漏和不足之處，歡迎專家和讀者批評指正。
編者2021年7月
徐慧，女，博士，南通大學(xué)教授，碩士生導(dǎo)師。從事《數(shù)據(jù)結(jié)構(gòu)》等課程教學(xué)二十多年。主持的《數(shù)據(jù)結(jié)構(gòu)》課程，獲2020國家一流線下課程。
長期以來，專研教學(xué)、教研，積累了豐富的教學(xué)經(jīng)驗與個性。教學(xué)深受學(xué)生喜愛。
教學(xué)中，主創(chuàng)了多項高質(zhì)量的教學(xué)資源,如 :《數(shù)據(jù)結(jié)構(gòu)》課程PPT獲省優(yōu)秀多媒體獎；微課數(shù)據(jù)結(jié)構(gòu)之線性表獲2019江蘇省優(yōu)秀微課獎。
主編《數(shù)據(jù)結(jié)構(gòu)》、《數(shù)據(jù)結(jié)構(gòu)實踐教程》；參編《微機(jī)原理》，具備一定的教材編寫基礎(chǔ)。
第1章緒論1
1.1課程屬性與術(shù)語1
1.1.1數(shù)據(jù)結(jié)構(gòu)是程序的重要組成部分1
1.1.2數(shù)據(jù)結(jié)構(gòu)是提升編程能力的2
1.1.3數(shù)據(jù)結(jié)構(gòu)與術(shù)語2
1.1.4數(shù)據(jù)結(jié)構(gòu)決定算法4
1.2數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容4
1.2.1邏輯結(jié)構(gòu)5
1.2.2存儲結(jié)構(gòu)/物理結(jié)構(gòu)6
1.2.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系7
1.2.4非數(shù)值計算問題8
1.2.5數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計的關(guān)系10
1.3抽象數(shù)據(jù)類型11
1.3.1抽象數(shù)據(jù)類型的定義11
1.3.2抽象數(shù)據(jù)類型的實現(xiàn)12
1.4算法與算法分析13
1.4.1算法的概念13
1.4.2算法描述13
1.4.3算法性能分析15
1.5小結(jié)20
習(xí)題121
第2章線性表25
2.1線性表的定義25
2.1.1線性表的邏輯特性25
2.1.2線性表的抽象數(shù)據(jù)類型26
2.2順序表28
2.2.1順序表的定義28
2.2.2順序表的存儲設(shè)計29
2.2.3順序表的操作及實現(xiàn)30
2.2.4順序表應(yīng)用舉例36
2.3鏈表39
2.3.1單鏈表的定義及特性39
2.3.2單鏈表的存儲設(shè)計40
2.3.3單鏈表的操作及實現(xiàn)41
2.3.4其他形式的鏈表50
2.3.5鏈表應(yīng)用舉例53
2.4順序表與鏈表的比較57
2.4.1空間性能比較58
2.4.2時間性能比較58
2.4.3環(huán)境性能比較58
2.5小結(jié)58
習(xí)題259
第3章棧和隊列63
3.1棧63
3.1.1棧的定義和特點63
3.1.2順序棧65
3.1.3鏈棧69
3.1.4順序棧和鏈棧的比較73
3.1.5棧的應(yīng)用73
3.2隊列80
3.2.1隊列的定義和特點80
3.2.2循環(huán)隊列81
3.2.3鏈隊85
3.2.4循環(huán)隊列與鏈隊列的比較89
3.2.5隊列的應(yīng)用89
3.3小結(jié)91
習(xí)題392
第4章數(shù)組和矩陣95
4.1多維數(shù)組95
4.1.1數(shù)組的定義95
4.1.2數(shù)組的順序存儲97
4.2特殊矩陣99
4.2.1對稱矩陣100
4.2.2三角矩陣100
4.2.3對角矩陣101
4.3稀疏矩陣102
4.3.1三元組表順序存儲102
4.3.2帶行指針向量的鏈?zhǔn)酱鎯?05
4.3.3十字鏈表108
4.4小結(jié)109
習(xí)題4110
第5章樹和二叉樹113
5.1樹114
5.1.1樹的定義與表示114
5.1.2樹的術(shù)語115
5.1.3樹的抽象數(shù)據(jù)類型116
5.1.4樹的存儲設(shè)計118
5.1.5樹和森林的遍歷120
5.2二叉樹的定義與特性121
5.2.1二叉樹的定義121
5.2.2特殊二叉樹122
5.2.3二叉樹的性質(zhì)123
5.2.4二叉樹的抽象數(shù)據(jù)類型125
5.3二叉樹的存儲結(jié)構(gòu)127
5.4二叉樹操作129
5.4.1二叉樹遍歷129
5.4.2根據(jù)遍歷序列確定二叉樹137
5.4.3先、中、后序遍歷的非遞歸算法139
5.4.4二叉樹的其他操作145
5.5線索二叉樹148
5.5.1線索二叉樹的定義148
5.5.2線索二叉樹的建立149
5.5.3線索二叉樹的遍歷151
5.6樹和森林與二叉樹的相互轉(zhuǎn)換154
5.6.1樹與二叉樹相互轉(zhuǎn)換154
5.6.2森林與二叉樹相互轉(zhuǎn)換156
5.7二叉樹及其應(yīng)用157
5.7.1基本概念157
5.7.2構(gòu)造二叉樹158
5.7.3哈夫曼編碼164
5.8小結(jié)167
習(xí)題5168
第6章圖171
6.1圖的定義及相關(guān)術(shù)語171
6.1.1圖的定義171
6.1.2圖的術(shù)語172
6.1.3圖的抽象數(shù)據(jù)類型176
6.2圖的存儲及操作177
6.2.1鄰接矩陣表示法及操作舉例177
6.2.2鄰接表表示法及操作舉例181
6.2.3十字鏈表表示法及操作舉例184
6.2.4鄰接多重表表示法及操作舉例186
6.3圖的遍歷及應(yīng)用189
6.3.1深度優(yōu)先遍歷189
6.3.2廣度優(yōu)先遍歷192
6.3.3遍歷應(yīng)用舉例195
6.4圖的應(yīng)用199
6.4.1小生成樹199
6.4.2短路徑205
6.4.3AOV網(wǎng)與拓?fù)渑判?11
6.4.4AOE網(wǎng)與關(guān)鍵路徑216
6.5小結(jié)220
習(xí)題6221
第7章查找225
7.1查找的基本概念225
7.1.1術(shù)語225
7.1.2查找性能226
7.2線性表查找技術(shù)227
7.2.1順序查找227
7.2.2折半查找228
7.2.3串的模式匹配231
7.3樹表查找236
7.3.1二叉排序樹236
7.3.2平衡二叉樹243
7.4散列查找247
7.4.1散列函數(shù)的構(gòu)造方法248
7.4.2處理沖突的方法250
7.4.3散列表的查找253
7.5小結(jié)255
習(xí)題 7256
第8章排序259
8.1排序的基本概念259
8.1.1排序的定義260
8.1.2內(nèi)排序與外排序261
8.1.3排序性能261
8.1.4內(nèi)部排序方法的分類262
8.1.5待排序記錄的存儲方式262
8.2插入排序262
8.2.1直接插入排序263
8.2.2折半插入排序265
8.2.3希爾排序267
8.3交換排序268
8.3.1冒泡排序269
8.3.2快速排序271
8.4選擇排序275
8.4.1簡單選擇排序275
8.4.2樹形選擇排序277
8.4.3堆排序279
8.5歸并排序284
8.6基數(shù)排序287
8.6.1分配排序287
8.6.2多關(guān)鍵碼排序288
8.6.3基數(shù)排序詳解289
8.7各種排序方法的比較291
8.7.1性能比較292
8.7.2方法選用293
8.8小結(jié)294
習(xí)題8294
附錄術(shù)語表297
參考文獻(xiàn)301
書單推薦
![大話數(shù)據(jù)結(jié)構(gòu)[溢彩加強(qiáng)版]](/uploadfile/202011/9787302564713.jpg)
