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

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

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