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

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