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


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