數(shù)據(jù)結(jié)構(gòu)

　　本書系統(tǒng)、全面地論述數(shù)據(jù)結(jié)構(gòu)的重要內(nèi)容，包括基本概念和方法、線性表、鏈表、樹、堆結(jié)構(gòu)、圖、排序和搜索結(jié)構(gòu)。在充分繼承國內(nèi)外經(jīng)典教材的合理體系結(jié)構(gòu)和優(yōu)秀內(nèi)容的基礎(chǔ)上，結(jié)合國內(nèi)實際教學情況編寫，內(nèi)容系統(tǒng)、精煉，且經(jīng)過優(yōu)化整合，在深度和廣度上有明顯增強；突出重點、難點，強調(diào)分析問題和解決問題的方法，以及產(chǎn)生這些方法的背景。書中內(nèi)容都經(jīng)過編者深入研究，且在教學實踐中反復驗證，因而較易理解。本書注重啟發(fā)創(chuàng)新思維，培養(yǎng)能力；概念準確，邏輯性強；自然引用面向?qū)ο笤O(shè)計思想，用C++語言描述算法。本書適于作為計算機科學與技術(shù)、軟件工程以及相關(guān)專業(yè)的教材，也可供從事相關(guān)工作的科技與工程人員參考。本書前言設(shè)計解決實際問題的計算機軟件系統(tǒng)，首先需要建立被處理對象的數(shù)據(jù)模型。數(shù)據(jù)和世上萬物一樣，都是具有結(jié)構(gòu)的。因此，人們很自然地用數(shù)據(jù)結(jié)構(gòu)表示應用領(lǐng)域的被處理對象。為了模擬實際問題的求解過程和現(xiàn)實對象的行為，還必須提供對數(shù)據(jù)結(jié)構(gòu)的相應操作。數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)是由下一層數(shù)據(jù)結(jié)構(gòu)表示上一層數(shù)據(jù)結(jié)構(gòu)，直至由程序設(shè)計語言提供的基本數(shù)據(jù)類型表示的過程。評價數(shù)據(jù)結(jié)構(gòu)表示優(yōu)劣的標準主要是其能否方便且有效地實現(xiàn)需要的操作，而實現(xiàn)操作的算法設(shè)計及其效率高低也依賴于數(shù)據(jù)結(jié)構(gòu)表示。因此，數(shù)據(jù)結(jié)構(gòu)的定義、表示以及操作的實現(xiàn)相互關(guān)聯(lián)，都是數(shù)據(jù)結(jié)構(gòu)研究的重要內(nèi)容。計算機軟件系統(tǒng)可看成是通過不同層次的數(shù)據(jù)結(jié)構(gòu)及其操作實現(xiàn)的。通過多層表示，完成計算機對應用領(lǐng)域問題的求解過程。在此，中間層數(shù)據(jù)結(jié)構(gòu)起著核心作用。數(shù)據(jù)結(jié)構(gòu)的研究產(chǎn)生了一批通用性強、具有很高實用價值的中間層數(shù)據(jù)結(jié)構(gòu)，如數(shù)組、字符串、集合、線性表、棧、隊列、鏈表、樹、圖、符號表等。這些結(jié)構(gòu)不僅為我們提供了設(shè)計軟件系統(tǒng)的有用工具，而且向我們展示了在廣泛的應用領(lǐng)域表示與解決問題的精巧思路和技術(shù)。系統(tǒng)地學習和掌握數(shù)據(jù)結(jié)構(gòu)知識和方法，對于提高設(shè)計與開發(fā)軟件系統(tǒng)尤其是復雜軟件系統(tǒng)的能力，無疑是十分重要的。因此，數(shù)據(jù)結(jié)構(gòu)早已成為計算機科學與技術(shù)和軟件工程等專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容豐富，涵蓋了計算機科學與技術(shù)的許多重要的成果，分析問題和解決問題的思路和方法新穎，創(chuàng)新點多，技巧性強，對學生專業(yè)素質(zhì)的培養(yǎng)作用明顯，但同時也是一門較難學習的課程。我校計算機科學與工程系開設(shè)的"數(shù)據(jù)結(jié)構(gòu)"課程一直采用美國南加州大學教授E.Horowitz等編著的《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》作為教材。該書注重培養(yǎng)學生分析問題、解決問題的能力，在數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計以及時空復雜性分析的深度和廣度方面特色明顯。但在教學中也感到該書內(nèi)容的表達形式學生較難理解，方法和技術(shù)的論述還不夠簡明扼要，有的內(nèi)容不夠精煉，部分章節(jié)存在一些小錯誤，教學效果較多依賴于教師的講解。為此，編者在充分繼承該書體系結(jié)構(gòu)和內(nèi)容優(yōu)點的基礎(chǔ)上，吸收其他教材長處，進行優(yōu)化整合，并結(jié)合自身多年的教學改革與實踐經(jīng)驗，編寫了這本教材，力圖使其系統(tǒng)全面，內(nèi)容深刻，表達簡潔，易于理解，以適應計算機科學與技術(shù)及相關(guān)專業(yè)的教學需要。本書共分為8章。第1章論述數(shù)據(jù)結(jié)構(gòu)的基本概念和方法，包括數(shù)據(jù)結(jié)構(gòu)與軟件系統(tǒng)，數(shù)據(jù)抽象與封裝，算法，遞歸，性能分析、性能測量，以及效率與權(quán)衡等。特別引入了代價分攤分析方法，將相關(guān)的操作序列聯(lián)系起來分析，從而得到更接近實際代價的結(jié)果。此外，還從軟件重用的角度描述了C++的模板機制。第2章介紹線性表的概念及其順序表示方法，討論了通過線性表表示的多項式、稀疏矩陣和字符串等結(jié)構(gòu)。在描述著名的字符串模式匹配算法KMP時，采用了簡明易懂的圖示方法。還通過兩個字符串的最長公共子序列問題的求解，展示了利用動態(tài)規(guī)劃改進算法效率的方法。由于棧和隊列是受限的線性表，因此也被整合到這一章。此章不僅給出了通用棧和隊列的實現(xiàn)方法，還分別通過求解迷宮問題、表達式計算以及機場模擬問題描述了棧和隊列的應用。第3章論述以鏈表形式實現(xiàn)線性表的方法和技術(shù)，討論了遍歷通用模板類容器對象的游標技術(shù)。還介紹了廣義表的功能及其實現(xiàn)方法，并結(jié)合C++的動態(tài)類型，討論了異構(gòu)表的實現(xiàn)方法。第4章介紹最基本的非線性結(jié)構(gòu)：樹，包括樹和森林的概念、二叉樹、二叉樹的遍歷及應用、線索二叉樹、勝者樹、敗者樹、森林的二叉樹表示及遍歷、樹在并查集問題中的應用和二叉樹計數(shù)等。特別給出了有一定難度的中序線索二叉樹的后序遍歷算法，還給出了生成所有可能的二叉樹的算法。第5章介紹支持各種優(yōu)先隊列的堆結(jié)構(gòu)，包括最大堆、最大最小堆、雙堆、左偏樹、二項式堆和斐波納契堆。在分析二項式堆和斐波納契堆的性能時，采用了代價分攤方法。第6章介紹更普遍的非線性結(jié)構(gòu)：圖，包括圖的定義和表示方法、圖的遍歷、圖的連通性、最小代價生成樹、最短路徑和傳遞閉包以及活動網(wǎng)絡(luò)等。特別討論了應用斐波納契堆改進最短路徑算法性能的技術(shù)。在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的次序是一種重要的關(guān)系。按照數(shù)據(jù)元素的特定屬性對其進行排序是最頻繁的計算任務之一。第7章介紹各種典型的排序方法，包括插入排序、希爾排序、快速排序、歸并排序、堆排序、基數(shù)排序、基于鏈表和映射表排序結(jié)果的順序化以及外排序。第8章介紹符號表概念以及實現(xiàn)符號表的各種結(jié)構(gòu)，包括二叉查找樹、AVL樹、2-3樹、Splay樹、B樹、B+樹、Trie、靜態(tài)散列和動態(tài)散列等，特別分析了二叉查找樹的平均性能。在分析Splay樹的性能時，采用了代價分攤方法。此外，還論述了上述結(jié)構(gòu)的演變關(guān)系，幫助讀者理解其設(shè)計思想。本書可供各種層次的讀者選用，既適用于教學，也可供從事相關(guān)工作的科技與工程人員參考。可以按"數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)"（64學時，必修）和"高級數(shù)據(jù)結(jié)構(gòu)"（24～32學時，選修）兩門課組織教學。本書的2.4、2.9、3.10、4.5、4.8、4.9、5.2～5.6、6.4、7.8、8.4、8.5、8.7和8.9節(jié)可作為"高級數(shù)據(jù)結(jié)構(gòu)"課程的內(nèi)容，其余作為"數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)"課程的內(nèi)容。本書引用了數(shù)據(jù)結(jié)構(gòu)研究的大量先進成果，在此，作者謹向這些成果的原創(chuàng)者表示崇高的敬意和衷心的感謝。同時，對本書所引用的參考文獻的作者也表示衷心的感謝。在本書的寫作過程中，作者與徐寶文、孫志揮、王茜、徐冬梅、王樹梅、吉根林和張麗暉老師開展了卓有成效的討論，并由此得到很多啟發(fā)。南京大學計算機科學與技術(shù)系陳道蓄教授認真審讀了全部書稿，并提出了十分寶貴的修改意見，在此對他們表示最誠摯的謝意。感謝清華大學出版社的鼓勵與支持。感謝東南大學教學改革基金的資助。還要感謝作者的眾多學生，他們在數(shù)據(jù)結(jié)構(gòu)課程學習過程中表現(xiàn)出的熱情與執(zhí)著給了作者很大的鼓勵，與他們的討論和交流使作者對教學內(nèi)容和教學方法的改進有了更深刻的認識。

暫缺《數(shù)據(jù)結(jié)構(gòu)》作者簡介