書在選材與編排上，以可讀可學可用可研可練為目標。全書共8章，內(nèi)容涵蓋緒論、線性表、棧和隊列、數(shù)組和矩陣、樹和二叉樹、圖、查找以及排序。全書共有118個算法、61個示例、21個應用案例、212道練習題。練習題題型包括填空題、簡答題、應用題、算法設計題和上機練習題五類，滿足原理理解、知識應用、模仿、創(chuàng)新、算法訓練及實踐訓練多方面需求。每章小結(jié)給出全章知識結(jié)構(gòu)圖以及相關算法與應用匯總。 本書內(nèi)容豐富、編排新穎、圖文并茂。原理敘述直達要義，算法步驟與偽碼一一對應�？勺鳛楦叩葘W校計算機及相關專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教材，也可供從事計算機軟件開發(fā)與應用的工程技術(shù)人員參考。
數(shù)據(jù)結(jié)構(gòu)課程對計算機相關專業(yè)來講是專業(yè)基礎課，并因其重要性被廣泛作為學位課和考研課。數(shù)據(jù)結(jié)構(gòu)的研究范疇涵蓋典型的邏輯結(jié)構(gòu)、這些邏輯結(jié)構(gòu)在計算機中的實現(xiàn)、算法分析及典型算法與應用等。邏輯結(jié)構(gòu)用于研究對象的抽象與建模，存儲設計的好壞直接決定問題求解的難易和算法性能，這些都是用計算機解決問題時不可或缺的知識與技能。因此，從課程研究內(nèi)容看，數(shù)據(jù)結(jié)構(gòu)課程是一門程序設計基礎課，也是程序設計能力提升的進階課。正因為該課程的重要性，已出版的《數(shù)據(jù)結(jié)構(gòu)》教材林林總總，且其發(fā)展從未停息。2010年，本教學團隊出版了《數(shù)據(jù)結(jié)構(gòu)》（ISBN: 9787302214755）、《數(shù)據(jù)結(jié)構(gòu)實踐教程》（ISBN: 9787302214762）、《數(shù)據(jù)結(jié)構(gòu)習題及學習指導》（ISBN: 9787302214779）系列教材。十多年過去了，時代發(fā)展對工科人才培養(yǎng)的要求不斷變化著。變化的時代和變化的學生使我們積累了與時俱進的教學經(jīng)驗。在獲得首批線下一流本科課程榮譽之際，編者決定重寫《數(shù)據(jù)結(jié)構(gòu)》教程及修訂相關系列教材。為契合新工科人才培養(yǎng)需要和工程專業(yè)認證對計算機類學生的畢業(yè)要求，本教材立足于實用，以可讀可學可教可研可練為宗旨設計編排內(nèi)容并將教材取名為《數(shù)據(jù)結(jié)構(gòu)原理與應用》。
●可讀。撰寫過程中，從多方面考慮教材的可讀性。概念及原理等新知識的介紹首先以文字陳述，并做到精準、簡明、扼要，直明要義；然后以示例展示，將概念及原理具化，使知識一目了然。所有內(nèi)容盡可能圖文并茂。此外，為了簡潔和增加可讀性且考慮專業(yè)特性，本教材選用C/C 語言，但不拘泥于兩者的嚴格語法，集兩者優(yōu)點呈現(xiàn)算法。 ●可學。首先，在算法描述上，教材選用了對學習者要求較低的面向過程的方法，但借用模板概念解決數(shù)據(jù)類型的抽象問題。這里主要考慮到面向?qū)ο蟮某绦蛟O計有完整的理論體系和架構(gòu)，用它描述和理解算法對學生要求很高。而在數(shù)據(jù)結(jié)構(gòu)課程中，語言本身只是一個工具。面向過程的描述進一步簡化語法部分，突出問題求解本身，降低學習難度。其次，各種結(jié)構(gòu)都有豐富的應用背景，滿足學生希冀獲取解決問題的方法及學得可用知識與技能的本能愿望。學生通過理解、記憶、驗證、模仿、思考能切實感到收獲。
●可教。用實際教學中積累的思路設計與組織教材內(nèi)容，例如算法講解給出算法的來龍去脈。首先根據(jù)算法思想分析存儲設計和輔助變量設計，再給出算法設計，并且將算法步驟與算法描述一一對應，呈現(xiàn)代碼的生成過程。教材中大量的圖示及應用示例為教師教學提供了豐富的教學素材，教輔PPT將盡量展示算法執(zhí)行過程。
●可研。許多算法介紹后都設置了算法討論部分，提出相關問題或更深層次的問題，拓展教學深度與廣度，引導思考與研究。例如在用順序表實現(xiàn)一元多項式求和問題中，在算法討論部分拋出一元稀疏多項式求和的問題以激發(fā)思考，也為后續(xù)新知識進行鋪墊，增加教材內(nèi)容的連貫性。
●可練。教材提供多層次的練習素材。填空題用于復習理論知識和加深對原理的理解；簡答題與應用題用于知識的應用與分析能力的訓練；算法設計題與上機練習題用于設計與編程技能訓練。多層次的練習題可滿足學習者各層次上的需求。
總之，這是一本考慮當下聚焦的應用型和創(chuàng)新型人才培養(yǎng)需要，以可用實用為宗旨的一部具有時代氣息的教材。教材的配套資源有教學PPT、書中算法實現(xiàn)的源碼、實踐教程等。另應新時代發(fā)展需求，后期會提供微課。
后感謝教學團隊老師的精誠合作與辛苦付出。周建美編寫了第3章和第4章，季峰和陳森博編寫了第6章，丁紅編寫了第7章，徐慧編寫了其余章節(jié)并進行全稿統(tǒng)稿。團隊其他老師（如管致錦教授、顧頎博士、朱玲玲副教授、陳德裕副教授等）參與了本書的審稿工作，在此也謝謝他們的寶貴意見。
雖然竭盡所能，但由于編者知識、能力和時間有限，書中仍難免有疏漏和不足之處，歡迎專家和讀者批評指正。
編者2021年7月
徐慧，女，博士，南通大學教授，碩士生導師。從事《數(shù)據(jù)結(jié)構(gòu)》等課程教學二十多年。主持的《數(shù)據(jù)結(jié)構(gòu)》課程，獲2020國家一流線下課程。
長期以來，專研教學、教研，積累了豐富的教學經(jīng)驗與個性。教學深受學生喜愛。
教學中，主創(chuàng)了多項高質(zhì)量的教學資源,如 :《數(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)實踐教程》；參編《微機原理》，具備一定的教材編寫基礎。
第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)的關系7
1.2.4非數(shù)值計算問題8
1.2.5數(shù)據(jù)結(jié)構(gòu)與程序設計的關系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
習題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順序表的存儲設計29
2.2.3順序表的操作及實現(xiàn)30
2.2.4順序表應用舉例36
2.3鏈表39
2.3.1單鏈表的定義及特性39
2.3.2單鏈表的存儲設計40
2.3.3單鏈表的操作及實現(xiàn)41
2.3.4其他形式的鏈表50
2.3.5鏈表應用舉例53
2.4順序表與鏈表的比較57
2.4.1空間性能比較58
2.4.2時間性能比較58
2.4.3環(huán)境性能比較58
2.5小結(jié)58
習題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棧的應用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隊列的應用89
3.3小結(jié)91
習題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帶行指針向量的鏈式存儲105
4.3.3十字鏈表108
4.4小結(jié)109
習題4110
第5章樹和二叉樹113
5.1樹114
5.1.1樹的定義與表示114
5.1.2樹的術(shù)語115
5.1.3樹的抽象數(shù)據(jù)類型116
5.1.4樹的存儲設計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二叉樹及其應用157
5.7.1基本概念157
5.7.2構(gòu)造二叉樹158
5.7.3哈夫曼編碼164
5.8小結(jié)167
習題5168
第6章圖171
6.1圖的定義及相關術(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圖的遍歷及應用189
6.3.1深度優(yōu)先遍歷189
6.3.2廣度優(yōu)先遍歷192
6.3.3遍歷應用舉例195
6.4圖的應用199
6.4.1小生成樹199
6.4.2短路徑205
6.4.3AOV網(wǎng)與拓撲排序211
6.4.4AOE網(wǎng)與關鍵路徑216
6.5小結(jié)220
習題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
習題 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多關鍵碼排序288
8.6.3基數(shù)排序詳解289
8.7各種排序方法的比較291
8.7.1性能比較292
8.7.2方法選用293
8.8小結(jié)294
習題8294
附錄術(shù)語表297
參考文獻301
書單推薦
