本書采用程序員最廣泛采用的面向?qū)ο驝++語言來描述數(shù)據(jù)結(jié)構(gòu)和算法,并把數(shù)據(jù)結(jié)構(gòu)原理和算法分析技術(shù)有機(jī)地結(jié)合在一起,系統(tǒng)介紹了各種類型的數(shù)據(jù)結(jié)構(gòu)及排序、檢索的各種方法。作者非常注意對(duì)每一種數(shù)據(jù)結(jié)構(gòu)的不同存儲(chǔ)方法及有關(guān)算法進(jìn)行分析比較。書中還引入了一些比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)與先進(jìn)的算法分析技術(shù),并介紹了可計(jì)算性理論的一般知識(shí)。書中分別給出了C++實(shí)現(xiàn)方法和偽碼實(shí)現(xiàn)方法,便于讀者根據(jù)情況選擇。本書作者維護(hù)的網(wǎng)站上可下載相關(guān)代碼、編程項(xiàng)目和輔助練習(xí)資料。
本書概念清楚，邏輯性強(qiáng)，內(nèi)容新穎：? 本書作者是國際上數(shù)據(jù)結(jié)構(gòu)和算法分析領(lǐng)域的權(quán)威，他出版的有關(guān)C、C++、Java等語言的數(shù)據(jù)結(jié)構(gòu)的各個(gè)版本教材均已由各家出版社引進(jìn)國內(nèi)，得到了廣大讀者的認(rèn)可。? 本書是作者多年教學(xué)實(shí)踐經(jīng)驗(yàn)的積淀，配套資源很豐富。作者維護(hù)的網(wǎng)站上可下載相關(guān)代碼、編程項(xiàng)目和輔助練習(xí)資料。 ? 本書描述了許多表示數(shù)據(jù)的技術(shù)，并將數(shù)據(jù)結(jié)構(gòu)和算法分析有機(jī)地結(jié)合在一本教材中， 有助于讀者根據(jù)問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)， 并對(duì)算法的時(shí)間、 空間復(fù)雜性進(jìn)行必要的控制。? 本書采用當(dāng)前流行的面向?qū)ο蟮腃++程序設(shè)計(jì)語言來描述數(shù)據(jù)結(jié)構(gòu)和算法，作者加強(qiáng)了面向?qū)ο蟮挠懻摚?特別是增加了設(shè)計(jì)模式的相關(guān)內(nèi)容。
及第1~10章由張銘翻譯， 第11~17章由劉曉丹翻譯。另外， 肖之屏、 劉智沖、 方譯萌、 王子琪、 王晟、 盛達(dá)魁、 劉金寶、 賀一駿、 桂歡等人也參加了本書的翻譯工作， 在此對(duì)他們的辛勤勞動(dòng)表示感謝。由于水平有限， 難免有不妥之處， 歡迎讀者批評(píng)指正。
前 言
人們研究數(shù)據(jù)結(jié)構(gòu)的目的， 是為了學(xué)會(huì)編寫效率更高的程序。現(xiàn)在的計(jì)算機(jī)速度一年比一年快， 為什么還需要高效率的程序呢？這是由于人類解決問題的雄心與能力是同步增長的。現(xiàn)代計(jì)算技術(shù)在計(jì)算能力和存儲(chǔ)容量上的革命， 僅僅提供了解決更復(fù)雜問題的有效工具， 而對(duì)程序高效率的要求永遠(yuǎn)也不會(huì)過時(shí)。
程序高效率的要求不會(huì)也不應(yīng)該與合理的設(shè)計(jì)和簡明清晰的編碼相矛盾。高效率程序的設(shè)計(jì)基于良好的信息組織和優(yōu)秀的算法， 而不是基于“編程小伎倆”。一名程序員如果沒有掌握設(shè)計(jì)簡明清晰程序的基本原理， 就不可能編寫出有效的程序。反過來說， 對(duì)開發(fā)代價(jià)和可維護(hù)性的考慮不應(yīng)該作為性能不高的借口。設(shè)計(jì)中的通用性（generality in design）應(yīng)該在不犧牲性能的情況下達(dá)到， 但前提是設(shè)計(jì)人員知道如何去衡量性能， 并且把性能作為設(shè)計(jì)和實(shí)現(xiàn)不可分割的一部分。大多數(shù)計(jì)算機(jī)科學(xué)系的課程設(shè)置都意識(shí)到要培養(yǎng)良好的程序設(shè)計(jì)技能， 首先應(yīng)該強(qiáng)調(diào)基本的軟件工程原理。因此， 一旦程序員學(xué)會(huì)了設(shè)計(jì)和實(shí)現(xiàn)簡明清晰程序的原理， 下一步就應(yīng)該學(xué)習(xí)有效的數(shù)據(jù)組織和算法， 以提高程序的效率。
途徑： 本書描述了許多表示數(shù)據(jù)的技術(shù)。這些技術(shù)包括以下原則：
1. 每一種數(shù)據(jù)結(jié)構(gòu)和每一個(gè)算法都有其時(shí)間、 空間的代價(jià)和效率。當(dāng)面臨一個(gè)新的設(shè)計(jì)問題時(shí)， 設(shè)計(jì)者要透徹地掌握權(quán)衡時(shí)間、 空間代價(jià)和算法有效性的方法， 以適應(yīng)問題的需要。這就需要懂得算法分析原理， 而且還需要了解所使用的物理介質(zhì)的特性(例如， 當(dāng)數(shù)據(jù)存儲(chǔ)在磁盤上與存儲(chǔ)在主存中， 就有不同的考慮)。
2. 與代價(jià)和效率有關(guān)的是時(shí)空權(quán)衡。例如， 人們通常增加空間代價(jià)來減少運(yùn)行時(shí)間， 或者反之。程序員所面對(duì)的時(shí)空權(quán)衡問題普遍存在于軟件設(shè)計(jì)和實(shí)現(xiàn)的各個(gè)階段， 因此這個(gè)概念必須牢記于心。
3. 程序員應(yīng)該充分了解一些現(xiàn)成的方法， 以免做不必要的重復(fù)開發(fā)工作。因此， 學(xué)生們需要了解經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法， 以及程序中常見的設(shè)計(jì)模式。
4. 數(shù)據(jù)結(jié)構(gòu)服從于應(yīng)用需求。學(xué)生們必須把分析應(yīng)用需求放在第一位， 然后再尋找一個(gè)與實(shí)際應(yīng)用相匹配的數(shù)據(jù)結(jié)構(gòu)。要做到這一點(diǎn)， 需要應(yīng)用上述三條原則。
筆者講授數(shù)據(jù)結(jié)構(gòu)多年， 發(fā)現(xiàn)設(shè)計(jì)在課程中起到了非常重要的作用。本教材的幾個(gè)版本中逐步增加了設(shè)計(jì)模式和接口。本書第一版完全沒有提到設(shè)計(jì)模式。第二版有一些篇幅講解了幾個(gè)設(shè)計(jì)模式的例子， 并且介紹了字典ADT和比較器類。編寫本書第三版的基本數(shù)據(jù)結(jié)構(gòu)和算法時(shí)， 都直接介紹了一些相關(guān)的設(shè)計(jì)模式。
教學(xué)建議： 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)的書籍往往囿于下面這兩種情形之一： 一種是教材， 一種是百科全書。有的書籍試圖融合這兩種編排， 但通常是二者都沒有組織好。本書是作為教材來編寫的。我相信， 了解如何選擇或設(shè)計(jì)解決問題的高效數(shù)據(jù)結(jié)構(gòu)的基本原理是十分重要的， 這比死記硬背書本內(nèi)容要重要得多。因此， 我在本書中涵蓋了大多數(shù)、 但不是全部的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。為了闡述一些重要原理， 也包括了某些并非廣泛使用的數(shù)據(jù)結(jié)構(gòu)。另外， 還介紹了一些相對(duì)較新、 但即將得到廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)。
在本科教學(xué)體系中， 本書適用于低年級(jí)（二年級(jí)或三年級(jí)）的高級(jí)數(shù)據(jù)結(jié)構(gòu)課程或者高年級(jí)的算法課程。第三版中加入了很多新的素材。通常， 這本書被用來講授一些超過常規(guī)一年級(jí)的CS2課程， 也可作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的介紹。讀者應(yīng)該已有兩個(gè)學(xué)期的基本編程經(jīng)驗(yàn)， 并具備一些C++基礎(chǔ)技能。對(duì)已經(jīng)熟悉部分內(nèi)容的讀者會(huì)有一些優(yōu)勢(shì)。數(shù)據(jù)結(jié)構(gòu)的學(xué)生如果先學(xué)完離散數(shù)學(xué)課程， 也頗有益處。不過， 第2章還是給出了比較完整的數(shù)學(xué)預(yù)備知識(shí)， 這些知識(shí)對(duì)理解本書的內(nèi)容還是很有必要的。讀者如果在閱讀中遇到不熟悉的知識(shí)， 可以回頭看看相應(yīng)的章節(jié)。
大二學(xué)生掌握的基本數(shù)據(jù)結(jié)構(gòu)和算法分析的背景知識(shí)(相對(duì)于從傳統(tǒng)CS2課程中獲得的基礎(chǔ)知識(shí))并不太多， 可以對(duì)他們?cè)敿?xì)地講解第1～11章的內(nèi)容， 再從第13章選擇一些專題來講解， 我就是這樣來給二年級(jí)學(xué)生講課的。背景知識(shí)更豐富的學(xué)生， 可以先閱讀第1章， 跳過第2章中除參考書目之外的內(nèi)容， 簡要地瀏覽第3章和第4章， 然后詳細(xì)閱讀第5~12章。另外， 教師可以根據(jù)程序設(shè)計(jì)實(shí)習(xí)的需要， 選擇第13章以后的某些專題內(nèi)容。高年級(jí)的算法課程可以著重講解第11章和第14~17章。
第13章是針對(duì)大型程序設(shè)計(jì)練習(xí)而編寫的。我建議所有選修數(shù)據(jù)結(jié)構(gòu)的學(xué)生， 都應(yīng)該做一些高級(jí)樹結(jié)構(gòu)或其他較復(fù)雜的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的上機(jī)實(shí)習(xí)， 例如第12章中的跳躍表(skip list)或稀疏矩陣。所有這些數(shù)據(jù)結(jié)構(gòu)都不會(huì)比二叉檢索樹更難， 而且學(xué)完第5章的學(xué)生都有能力來實(shí)現(xiàn)它們。
我盡量合理地安排章節(jié)順序。教師可以根據(jù)需要自由地重新組織內(nèi)容。讀者掌握了第1~6章后， 后續(xù)章節(jié)的內(nèi)容就相對(duì)獨(dú)立了。顯然， 外排序依賴于內(nèi)排序和磁盤文件系統(tǒng)。Kruskal最小支撐樹算法使用了6.2節(jié)關(guān)于并查（UNION/FIND）的算法。9.2節(jié)的自組織線性表提到了8.3節(jié)討論的緩沖區(qū)置換技術(shù)。第14章的討論基于本書的例題。17.2節(jié)依賴于圖論知識(shí)。在一般情況下， 大多數(shù)主題都只依賴于同一章中討論的內(nèi)容。
幾乎每一章都是以“深入學(xué)習(xí)導(dǎo)讀”一節(jié)結(jié)束的。它并不是這一章的綜合參考索引， 而是為了通過這些導(dǎo)讀書籍或文章提供給讀者更廣泛的信息和樂趣。在有些情況下我還提供了作為計(jì)算機(jī)科學(xué)家應(yīng)該知道的重要背景文章。
關(guān)于C++： 本書中的所有示例程序都是用C++編寫的， 但是我并不想難倒那些對(duì)C++不熟悉的讀者。在努力保持C++優(yōu)點(diǎn)的同時(shí)， 使示例程序盡量簡明、 清晰。C++在本書中只是作為闡釋數(shù)據(jù)結(jié)構(gòu)的工具。此外， 特別用到了C++隱蔽實(shí)現(xiàn)細(xì)節(jié)的特性， 例如類（class）、 私有類成員（private class member）、 構(gòu)造函數(shù)（constructor）、 析構(gòu)函數(shù)（destructor）。這些特性支持了一個(gè)關(guān)鍵概念： 體現(xiàn)于抽象數(shù)據(jù)類型（abstract data type）中的邏輯設(shè)計(jì)與體現(xiàn)于數(shù)據(jù)結(jié)構(gòu)中的物理實(shí)現(xiàn)的分離。
為了使得本書清晰易懂， 我回避了某些C++的最重要特性。書中有意排除或盡量少使用一些特性， 而這些特性是經(jīng)驗(yàn)豐富的C++程序員經(jīng)常使用的， 例如類的層次（class hierarchy）、 繼承（inheritance）和虛函數(shù)（virtual function）， 運(yùn)算符和函數(shù)的重載（operator and function overloading）也很少使用。在很多情況下， 更傾向于使用C的原始語義， 而不是C++所提供的一些類似功能。
當(dāng)然上述C++的特性在實(shí)際程序中是合理的程序設(shè)計(jì)基礎(chǔ)， 但是它們只能掩蓋而不是加強(qiáng)本書所闡述的原理。例如， 對(duì)于程序員來說， 類的繼承在避免重復(fù)編碼和降低程序錯(cuò)誤率方面是一個(gè)很重要的工具； 但是從教學(xué)的標(biāo)準(zhǔn)觀點(diǎn)來看， 類的繼承在若干類中分散了單個(gè)邏輯單元的描述， 從而使程序更難理解。因此， 僅當(dāng)類的繼承對(duì)闡述文章的觀點(diǎn)有明顯作用時(shí)， 我才使用它（見5.3.1節(jié)）。避免代碼重復(fù)和減少錯(cuò)誤是很重要的目標(biāo)， 請(qǐng)不要把本書中的示例程序直接復(fù)制到自己的程序中， 而只是把它們看成是對(duì)數(shù)據(jù)結(jié)構(gòu)原理的闡釋。
一個(gè)痛苦的選擇是， 作者要決定在示例代碼中是否使用模板（template）。在編寫本書的第一版時(shí)， 我決定不使用模板， 因?yàn)榭紤]到它們的語義對(duì)于不熟悉C++語言的人來說掩蓋了代碼的含義。在隨后的幾年中， 使用C++的計(jì)算機(jī)科學(xué)課程急劇地增加了， 因此我假設(shè)現(xiàn)在的讀者比以前的讀者更熟悉模板的語義。因此本書在示例代碼中大量使用了模板。
本書中的C++程序提供了有關(guān)數(shù)據(jù)結(jié)構(gòu)原理的真實(shí)闡釋， 是對(duì)文字闡述的補(bǔ)充。不宜脫離相關(guān)文字闡述而孤立地閱讀或使用示例程序， 因?yàn)榇罅康谋尘靶畔谖淖株U述中， 而不是包含在代碼中。代碼是對(duì)文字闡述的完善， 而不是相反的作用。這不是一系列具有商業(yè)質(zhì)量的類的實(shí)現(xiàn)。如果讀者想尋找一些標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)的完整實(shí)現(xiàn)， 或者要在你的代碼中使用這些數(shù)據(jù)結(jié)構(gòu)， 那么應(yīng)該在Internet上尋找。
例如， 這些例子中所做的參數(shù)檢查， 比起商業(yè)軟件要少得多， 因?yàn)檫@種檢查將降低算法的清晰度。某些參數(shù)檢查和約束檢查（例如是否從一個(gè)空容器中刪除值）是以調(diào)用Assert的形式完成的。Assert的輸入是一個(gè)布爾表達(dá)式， 一旦這個(gè)表達(dá)式的值為假（false）， 程序就立即終止。函數(shù)遇到一個(gè)壞參數(shù)就終止程序， 這在真實(shí)程序中通常是不必要的， 但有益于理解一個(gè)數(shù)據(jù)結(jié)構(gòu)是怎樣工作的。在實(shí)際的程序應(yīng)用中， C++異常處理機(jī)制（exception handling features）用來處理一些輸入數(shù)據(jù)錯(cuò)誤。然而， Assert提供了一種機(jī)制， 既有益于闡明一個(gè)數(shù)據(jù)結(jié)構(gòu)的工作條件， 也有利于采用真正的異常處理機(jī)制來代替。請(qǐng)參看附錄中的Assert實(shí)現(xiàn)。
在示例程序中， 我嚴(yán)格區(qū)分了“C++實(shí)現(xiàn)”和“偽碼”（pseudocode）。一個(gè)標(biāo)明“C++實(shí)現(xiàn)”的示例程序在一個(gè)以上的編譯器中被真正編譯過。偽碼的示例通常具有與C++接近的語法， 但是一般包含一行以上更高級(jí)的描述。當(dāng)我發(fā)現(xiàn)簡單的、 盡管并不十分精確的描述具有更好的教學(xué)效果時(shí)， 就使用偽碼。
習(xí)題和項(xiàng)目設(shè)計(jì)： 只靠讀書是不能學(xué)會(huì)靈活使用數(shù)據(jù)結(jié)構(gòu)的。一定要編寫實(shí)際的程序， 比較不同的數(shù)據(jù)結(jié)構(gòu)技術(shù)來觀察在一種給定的條件下哪一種數(shù)據(jù)結(jié)構(gòu)更有效。
數(shù)據(jù)結(jié)構(gòu)課程最重要的教學(xué)安排之一， 就是學(xué)生應(yīng)該在什么時(shí)候開始學(xué)習(xí)使用指針和動(dòng)態(tài)存儲(chǔ)分配， 從而編程實(shí)現(xiàn)鏈表和樹這樣的數(shù)據(jù)結(jié)構(gòu)。這也是學(xué)生們學(xué)習(xí)遞歸的時(shí)機(jī)。在教學(xué)體系中， 這是學(xué)生學(xué)習(xí)重大設(shè)計(jì)（significant design）的第一門課， 因?yàn)橥ǔＰ枰褂谜鎸?shí)數(shù)據(jù)結(jié)構(gòu)來引出重大設(shè)計(jì)練習(xí)。最后， 基于內(nèi)存和基于硬盤的數(shù)據(jù)訪問的本質(zhì)區(qū)別， 必須要在編程實(shí)踐中才能理解。基于以上原因， 一門數(shù)據(jù)結(jié)構(gòu)課程沒有大量的編程環(huán)節(jié)是不能成功的。在計(jì)算機(jī)系， 數(shù)據(jù)結(jié)構(gòu)是課程計(jì)劃中最難的一門編程課程。
學(xué)生還需要在解決問題中鍛煉分析能力。本書提供了450個(gè)習(xí)題和編程項(xiàng)目， 希望讀者能夠好好利用它們。
與作者聯(lián)系的方法及相關(guān)資料的獲取： 本書難免有一些錯(cuò)誤， 有些方面還有待進(jìn)一步研究。非常歡迎讀者指正， 并提出建設(shè)性意見。作者在Internet上的E-mail地址是shaffer@vt.edu， 也可以給以下的地址寫信：
Cliff Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
本書的電子版和上課中使用的一些幻燈片材料， 可以從以下網(wǎng)站獲取：
http://www.cs.vt.edu/~shaffer/book.html示例代碼也可以從上面的網(wǎng)站得到。弗吉尼亞技術(shù)學(xué)院二年級(jí)數(shù)據(jù)結(jié)構(gòu)課程網(wǎng)頁的URL為
http://ei.cs.vt.edu/～cs3114致謝： 本書得到了許多友人的幫助。我想特別感謝其中的幾位， 他們對(duì)本書的出版貢獻(xiàn)最大。對(duì)于沒有被提及的朋友， 在此表示歉意。
弗吉尼亞技術(shù)學(xué)院在1994年秋季的學(xué)術(shù)休假中使得整個(gè)出書的事情成為可能， 我是從那時(shí)開始著手準(zhǔn)備的。在編寫這本書的第二版時(shí)， 系主任Dennis Kafura和Jack Carroll對(duì)本書給予了重要的精神支持。Mike Keenan、 Lenny Heath和Jeff Shaffer對(duì)本書最初版本的內(nèi)容提供了有價(jià)值的意見。尤其是Lenny Heath多年來一直與我深入地討論算法設(shè)計(jì)和分析的有關(guān)問題， 以及怎樣把二者講授給學(xué)生的方法。十分感謝Steve Edwards花了很多時(shí)間幫助我?guī)状沃貙懥说诙妗?第三版的C++代碼和Java代碼， 并與我討論程序設(shè)計(jì)的原則。Layne Watson提供了有關(guān)Mathematica軟件的幫助， Bo Begole、 Philip Isenhour、 Jeff Nielsen和Craig Struble提供了一些技術(shù)上的幫助。感謝Bill McQuain、 Mark Abrams和Dennis Kafura回答了一些有關(guān)C++和Java的問題。
對(duì)于許多評(píng)閱了本書手稿的朋友， 本人欠情甚深。這些評(píng)閱者是： J.David Bezek (Evansville大學(xué))， Douglas Campbell(Brigham Young大學(xué))， Karen Davis (Cincinnati大學(xué))， Vijay Kumar Garg(Texas-Austin大學(xué))， Jim Miller(Kansas大學(xué))， Bruce Maxim(Michigan-Dearborn大學(xué))， Jeff Parker(Agile Networks/Harvard)， Dana Richards(George Mason大學(xué))， Jack Tan(Houston大學(xué))和Lixin Tao(Concordia大學(xué))。要不是他們的熱心幫助， 本書會(huì)出現(xiàn)更多技術(shù)上的錯(cuò)誤， 內(nèi)容也將更加淺顯。
關(guān)于這本第二版的出版， 我想感謝下列評(píng)閱者： Gurdip Singh(Kansas州立大學(xué))， Peter Allen (Columbia大學(xué))， Robin Hill (Wyoming大學(xué))， Norman Jacobson (California-Irvine大學(xué))， Ben Keller (弗吉尼亞技術(shù)學(xué)院)和Ken Bosworth (Idaho州立大學(xué))。另外， 我要感謝Neil Stewart和Frank J.Thesen對(duì)改進(jìn)本書提出的意見和建議。
第三版的評(píng)閱者包括Randall Lechlitner(Houstin大學(xué), Clear Lake)和Brian C. Hipp(York技術(shù)學(xué)院)。感謝他們的建議。
Prentice Hall是本書第一版和第二版的出版方。沒有出版社眾多朋友的幫助， 不可能有本書的出版， 因?yàn)樽髡卟豢赡茏约河〕鰰鴣怼Ｒ虼耍?幾年來我要感謝Kate Hargett、 Petra Rector、 Laura Steele和Alan Apt這幾位編輯。感謝本書第二版的責(zé)任編輯Irwin Zucker， 還有本書C++版的責(zé)任編輯Kathleen Caren和Java版的責(zé)任編輯Ed DeFelippis， 他們?cè)诒緯咏霭娴淖蠲y的日子里， 保持各個(gè)方面運(yùn)作良好。感謝Bill Zobrist和Bruce Gregory使我著手此事。感謝Prentice Hall的Truly Donovan、 Linda Behrens和Phyllis Bregman在本書出版過程中給予的幫助。感謝Tracy Dunkelberger在交回版權(quán)給我時(shí)提供的幫助。可能還有許多沒有被提及的Prentice Hall出版社的朋友， 他們也默默地提供了幫助。
本人非常感謝Dover出版社的Shelley Kronzek在第三版的出版過程中付出的一切。第三版中有許多擴(kuò)展， 包括Java和C++代碼， 以及一些改正。我相信這是迄今為止最好的一版。但是不知道學(xué)生會(huì)不會(huì)希望有一本免費(fèi)的在線教材， 還是低價(jià)的印刷版本。最終， 我相信兩個(gè)版本會(huì)提供更多的選擇。編輯James Miller和設(shè)計(jì)經(jīng)理Marie Zaczkiewicz為確保本書的高質(zhì)量出版付出了辛勤的工作。
我十分感激Hanan Samet傳授給我有關(guān)數(shù)據(jù)結(jié)構(gòu)的知識(shí)。我從他那里學(xué)到了許多原理與知識(shí)， 當(dāng)然本書中可能出現(xiàn)的錯(cuò)誤并不是他的責(zé)任。感謝我的妻子Terry對(duì)我的愛與支持， 還有兩個(gè)女兒Irena和Kate帶給我的歡樂， 可以讓我從艱苦的工作中解脫出來。最后， 也是最重要的， 感謝這些年來選修數(shù)據(jù)結(jié)構(gòu)的學(xué)生， 是他們使我知道了在數(shù)據(jù)結(jié)構(gòu)課程中什么是重要的而什么應(yīng)該忽略， 許多深入的問題也是他們提供的。這本書獻(xiàn)給他們。
Cliff A.Shaffer在美國馬里蘭大學(xué)獲得學(xué)士、碩士和博士學(xué)位，現(xiàn)在在Virginia Polytechnic理工學(xué)院計(jì)算機(jī)科學(xué)系擔(dān)任教授，主要講授問題求解、數(shù)據(jù)結(jié)構(gòu)與算法分析、算法理論等課程，積累了豐富的教學(xué)經(jīng)驗(yàn)，并出版了多部著作。
目 錄
第一部分 預(yù) 備 知 識(shí)
第1章 數(shù)據(jù)結(jié)構(gòu)和算法
1.1 數(shù)據(jù)結(jié)構(gòu)的原則
1.2 抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)
1.3 設(shè)計(jì)模式
1.4 問題、 算法和程序
1.5 深入學(xué)習(xí)導(dǎo)讀
1.6 習(xí)題
第2章 數(shù)學(xué)預(yù)備知識(shí)
2.1 集合和關(guān)系
2.2 常用數(shù)學(xué)術(shù)語
2.3 對(duì)數(shù)
2.4 級(jí)數(shù)求和與遞歸
2.5 遞歸 目 錄
第一部分 預(yù) 備 知 識(shí)
第1章 數(shù)據(jù)結(jié)構(gòu)和算法
1.1 數(shù)據(jù)結(jié)構(gòu)的原則
1.2 抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)
1.3 設(shè)計(jì)模式
1.4 問題、 算法和程序
1.5 深入學(xué)習(xí)導(dǎo)讀
1.6 習(xí)題
第2章 數(shù)學(xué)預(yù)備知識(shí)
2.1 集合和關(guān)系
2.2 常用數(shù)學(xué)術(shù)語
2.3 對(duì)數(shù)
2.4 級(jí)數(shù)求和與遞歸
2.5 遞歸
2.6 數(shù)學(xué)證明方法
2.7 估計(jì)
2.8 深入學(xué)習(xí)導(dǎo)讀
2.9 習(xí)題
第3章 算法分析
3.1 概述
3.2 最佳、 最差和平均情況
3.3 換一臺(tái)更快的計(jì)算機(jī)， 還是換一種更快的算法
3.4 漸近分析
3.5 程序運(yùn)行時(shí)間的計(jì)算
3.6 問題的分析
3.7 容易混淆的概念
3.8 多參數(shù)問題
3.9 空間代價(jià)
3.10加速你的程序
3.11實(shí)證分析
3.12深入學(xué)習(xí)導(dǎo)讀
3.13習(xí)題
3.14項(xiàng)目設(shè)計(jì)
第二部分 基本數(shù)據(jù)結(jié)構(gòu)
第4章 線性表、 棧和隊(duì)列
4.1 線性表
4.2 棧
4.3 隊(duì)列
4.4 字典
4.5 深入學(xué)習(xí)導(dǎo)讀
4.6 習(xí)題
4.7 項(xiàng)目設(shè)計(jì)
第5章 二叉樹
5.1 定義及主要特性
5.2 遍歷二叉樹
5.3 二叉樹的實(shí)現(xiàn)
5.4 二叉檢索樹
5.5 堆與優(yōu)先隊(duì)列
5.6 Huffman編碼樹
5.7 深入學(xué)習(xí)導(dǎo)讀
5.8 習(xí)題
5.9 項(xiàng)目設(shè)計(jì)
第6章 樹
6.1 樹的定義與術(shù)語
6.2 父指針表示法
6.3 樹的實(shí)現(xiàn)
6.4 K叉樹
6.5 樹的順序表示法
6.6 深入學(xué)習(xí)導(dǎo)讀
6.7 習(xí)題
6.8 項(xiàng)目設(shè)計(jì)
第三部分 排序與檢索
第7章 內(nèi)排序
7.1 排序術(shù)語及記號(hào)
7.2 三種代價(jià)為Θ(n2)的排序算法
7.3 Shell排序
7.4 歸并排序
7.5 快速排序
7.6 堆排序
7.7 分配排序和基數(shù)排序
7.8 對(duì)各種排序算法的實(shí)驗(yàn)比較
7.9 排序問題的下限
7.10深入學(xué)習(xí)導(dǎo)讀
7.11習(xí)題
7.12項(xiàng)目設(shè)計(jì)
第8章 文件管理和外排序
8.1 主存儲(chǔ)器和輔助存儲(chǔ)器
8.2 磁盤
8.3 緩沖區(qū)和緩沖池
8.4 程序員的文件視圖
8.5 外排序
8.6 深入學(xué)習(xí)導(dǎo)讀
8.7 習(xí)題
8.8 項(xiàng)目設(shè)計(jì)
第9章 檢索
9.1 檢索未排序和已排序的數(shù)組
9.2 自組織線性表
9.3 集合檢索
9.4 散列方法
9.5 深入學(xué)習(xí)導(dǎo)讀
9.6 習(xí)題
9.7 項(xiàng)目設(shè)計(jì)
第10章 索引技術(shù)
10.1 線性索引
10.2 ISAM
10.3 基于樹的索引
10.4 2-3樹
10.5 B樹
10.6 深入學(xué)習(xí)導(dǎo)讀
10.7 習(xí)題
10.8 項(xiàng)目設(shè)計(jì)
第四部分 高級(jí)數(shù)據(jù)結(jié)構(gòu)
第11章 圖
11.1 術(shù)語和表示法
11.2 圖的實(shí)現(xiàn)
11.3 圖的遍歷
11.4 最短路徑問題
11.5 最小支撐樹
11.6 深入學(xué)習(xí)導(dǎo)讀
11.7 習(xí)題
11.8 項(xiàng)目設(shè)計(jì)
第12章 線性表和數(shù)組高級(jí)技術(shù)
12.1 廣義表
12.2 矩陣的表示方法
12.3 存儲(chǔ)管理
12.4 深入學(xué)習(xí)導(dǎo)讀
12.5 習(xí)題
12.6 項(xiàng)目設(shè)計(jì)
第13章 高級(jí)樹結(jié)構(gòu)
13.1 Trie結(jié)構(gòu)
13.2 平衡樹
13.3 空間數(shù)據(jù)結(jié)構(gòu)
13.4 深入學(xué)習(xí)導(dǎo)讀
13.5 習(xí)題
13.6 項(xiàng)目設(shè)計(jì)
第五部分 算 法 理 論
第14章 分析技術(shù)
14.1 求和技術(shù)
14.2 遞歸關(guān)系
14.3 均攤分析
14.4 深入學(xué)習(xí)導(dǎo)讀
14.5 習(xí)題
14.6 項(xiàng)目設(shè)計(jì)
第15章 下限
15.1 下限證明介紹
15.2 線性表檢索的下限
15.3 查找最大值
15.4 對(duì)抗性下限證明
15.5 狀態(tài)空間下限證明
15.6 找到第i大元素
15.7 優(yōu)化排序
15.8 深入學(xué)習(xí)導(dǎo)讀
15.9 習(xí)題
15.10 項(xiàng)目設(shè)計(jì)
第16章 算法模式
16.1 動(dòng)態(tài)規(guī)劃
16.2 隨機(jī)算法
16.3 數(shù)值算法
16.4 深入學(xué)習(xí)導(dǎo)讀
16.5 習(xí)題
16.6 項(xiàng)目設(shè)計(jì)
第17章 計(jì)算的限制
17.1 歸約
17.2 難解問題
17.3 不可解問題
17.4 深入學(xué)習(xí)導(dǎo)讀
17.5 習(xí)題
17.6 項(xiàng)目設(shè)計(jì)
第六部分 附 錄
附錄A 實(shí)用函數(shù)
參考文獻(xiàn)
詞匯表
新書資訊