“數(shù)據(jù)結(jié)構(gòu)”是計算機類專業(yè)的基礎(chǔ)課程，也是相關(guān)理工類專業(yè)的熱門選修課程。本書是為該課程編寫的教材，適合計算機類專業(yè)和相關(guān)理工類專業(yè)的本科生學(xué)習(xí)。 
本書主要介紹如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)、正確地設(shè)計算法以及對算法的復(fù)雜度進行分析和評價。通過深入理解各種基本數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系、物理存儲和基本操作，初步建立數(shù)據(jù)結(jié)構(gòu)設(shè)計、實現(xiàn)和運用的概念。同時，結(jié)合各種典型案例，討論不同數(shù)據(jù)結(jié)構(gòu)的特點、適用范圍以及基本算法復(fù)雜度的分析方法，為后續(xù)的專業(yè)課程學(xué)習(xí)提供必要的基礎(chǔ)知識。 
本書的學(xué)習(xí)目標如下。 
目標1：掌握線性表、棧和隊列、數(shù)組和廣義表、樹和二叉樹、圖等各種基本數(shù)據(jù)結(jié)構(gòu)的邏輯表達、物理存儲和基本操作；掌握查找、排序的經(jīng)典算法。 
目標2：能夠針對具體應(yīng)用問題，根據(jù)問題的約束條件分析各種可選方案在數(shù)據(jù)存儲、算法效率上的利弊，并選擇恰當?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲表示和與之對應(yīng)的操作方法。 
目標3：能夠結(jié)合具體應(yīng)用案例，合理選擇和改進經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，使之針對具體應(yīng)用能夠有效地存儲和處理數(shù)據(jù)，能夠在此基礎(chǔ)上正確地設(shè)計算法，并對算法進行有效的分析和評價。 
本書共分為8章。第1章主要介紹數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念及術(shù)語，以及算法的定義、特性和算法設(shè)計的目標。第2～4章主要討論各種基本結(jié)構(gòu)的抽象數(shù)據(jù)類型、順序和鏈式表示與實現(xiàn)，以及相關(guān)的應(yīng)用。第5章和第6章在討論樹和圖的抽象數(shù)據(jù)類型、順序和鏈式表示與實現(xiàn)的基礎(chǔ)上，重點討論樹和圖的遍歷方法以及基于此的典型應(yīng)用。第7章和第8章分別討論查找和排序的經(jīng)典算法與改進策略。 
對于廣大讀者來說，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的關(guān)鍵是把握兩條主線。 
一條主線是如何理解和實現(xiàn)物理世界中的各種聯(lián)系在信息世界中的邏輯表示。物理世界中的萬般聯(lián)系都是形象而具體的，需要通過抽象建模抓住這些聯(lián)系的本質(zhì)，即線性、樹形或者圖狀結(jié)構(gòu)，從而將其轉(zhuǎn)換為信息世界中的邏輯表示。例如：生活中的各種排隊可以抽象成線性結(jié)構(gòu)中的隊列，家族譜可以映射為樹形結(jié)構(gòu)，專業(yè)課程的先修/后修關(guān)系可以構(gòu)成有向的圖結(jié)構(gòu)。抽象建模與表示能力是工科類專業(yè)學(xué)生必須具備的基本能力。不論是不是計算機類專業(yè)的學(xué)生，在學(xué)習(xí)這門課程時，都必須牢牢把握這條主線。 
另一條主線是如何在計算機中實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的存儲和操作。存儲的方式主要分為順序存儲和鏈式存儲兩大類�；�本操作一般包括初始化及銷毀操作、訪問型操作和加工型操作三大類。這三類操作在兩種不同存儲模式下的算法的效率是有差異的，需要進行比較分析，總結(jié)各自的優(yōu)勢和不足，從而針對具體的現(xiàn)實問題，選擇恰當?shù)拇鎯Ψ绞絹肀ＷC操作執(zhí)行的效率。在比較分析基礎(chǔ)上得到有效結(jié)論是這條主線中的能力訓(xùn)練要求。 
此外，算法設(shè)計與優(yōu)化也是值得關(guān)注的問題，本書中的查找和排序部分將展示算法設(shè)計與優(yōu)化的思路。例如，排序算法如何從時間復(fù)雜度O(n2)的經(jīng)典算法開始，通過對恰當結(jié)構(gòu)的引入將算法時間復(fù)雜度降到O(nlogn)；查找算法如何從時間復(fù)雜度O(n)的窮舉算法開始，通過對數(shù)據(jù)的排序約束和樹形結(jié)構(gòu)的引入，將時間復(fù)雜度降到O(logn)，甚至在一些特殊規(guī)則的約束下能夠接近O(1)。我們不僅要掌握經(jīng)典算法本身，更要關(guān)注算法優(yōu)化的策略和方向，以便在解決實際問題時能夠設(shè)計出高效的算法。 
最后，從不同學(xué)習(xí)者的角度來討論一下如何學(xué)習(xí)本門課程。 
對于計算機類專業(yè)的學(xué)生，本書所涉及的內(nèi)容均需掌握。在此基礎(chǔ)上，學(xué)生需要大量的訓(xùn)練，以具備抽象建模能力，能夠就實際問題選擇或設(shè)計恰當?shù)臄?shù)據(jù)結(jié)構(gòu)。此外，在編程實現(xiàn)過程中，能夠基于問題的約束，在比較、分析的基礎(chǔ)上選擇恰當?shù)拇鎯Ψ绞胶退惴ǖ膶崿F(xiàn)方式，能夠?qū)λ惴ǖ臅r間和空間復(fù)雜度進行合理的分析，能夠?qū)λ惴ǖ母倪M和優(yōu)化有恰當?shù)乃悸�，從而為實際問題提供高效的解決方案。 
對于其他理工類專業(yè)的學(xué)生，希望通過本門課程的學(xué)習(xí)達成兩點目標：一是具備抽象建模能力，能夠?qū)ξ锢硎澜缰械膯栴}描述進行抽象建模，從而在信息世界里進行合理表達；二是具備算法選擇能力，能夠根據(jù)輸入數(shù)據(jù)的表現(xiàn)形式、數(shù)據(jù)結(jié)構(gòu)的存儲方式和基于此的算法效率特征，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法來高效地解決實際問題。 
本書在構(gòu)思和準備過程中參考了國內(nèi)外相關(guān)的數(shù)據(jù)結(jié)構(gòu)教材，特別是嚴蔚敏、殷人昆、陳越、鄧俊輝等老師編寫的教材，這些經(jīng)典教材的內(nèi)容、寫法給了作者很多啟發(fā)。在本書的編寫過程中，南京航空航天大學(xué)的秦小麟老師給予了很多指導(dǎo)意見。在此一并向這些老師表示感謝。本書第1～3章由孫涵編寫，第4章和第8章由高航老師編寫，第5～7章由黃元元老師編寫，全書由孫涵負責(zé)統(tǒng)稿和審定。 
盡管本書是作者多年教學(xué)經(jīng)驗的總結(jié)，但限于作者的學(xué)識，書中難免有疏漏與不足之處，敬請各位同行與讀者批評指正，以利于我們不斷提升教學(xué)水平、豐富課程內(nèi)容。 


孫涵 
南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院 
2019年12月