?目的/目標(biāo) 
　　本書是《數(shù)據(jù)結(jié)構(gòu)與算法分析——C++語(yǔ)言描述》的第四版，論述組織大量數(shù)據(jù)的方法——數(shù)據(jù)結(jié)構(gòu)，以及算法運(yùn)行時(shí)間的估計(jì)——算法分析。隨著計(jì)算機(jī)的速度越來(lái)越快，對(duì)于能夠處理大量輸入數(shù)據(jù)的程序需求變得日益急迫�？墒�，由于在輸入量很大時(shí)程序的低效率顯得非常突出，因此又要求對(duì)效率問題給予更加嚴(yán)密的關(guān)注。通過(guò)在實(shí)際編程之前對(duì)算法進(jìn)行分析，學(xué)生們可以確定一個(gè)特定的解決方案是否可行。例如，在本書中學(xué)生可查閱一些特定的問題并看到精心的實(shí)現(xiàn)怎樣能夠把處理大量數(shù)據(jù)的時(shí)間限制從若干個(gè)世紀(jì)減至不到一秒。因此，若無(wú)運(yùn)行時(shí)間的闡釋，就不會(huì)有算法和數(shù)據(jù)結(jié)構(gòu)的提出。在某些情況下，對(duì)于影響實(shí)現(xiàn)的運(yùn)行時(shí)間的一些微小細(xì)節(jié)都需要認(rèn)真的探究。 
　　一旦解法被確定，接著就要編寫程序。隨著計(jì)算機(jī)功能的日益強(qiáng)大，它們必須解決的問題就變得更加龐大和復(fù)雜，這就要求開發(fā)更加復(fù)雜的程序。本書的目標(biāo)是同時(shí)教授學(xué)生良好的程序設(shè)計(jì)技巧和算法分析能力，使他們開發(fā)的程序能夠具有最高的效率。 
　　本書適合于高等數(shù)據(jù)結(jié)構(gòu)課程或是算法分析第一年的研究生課程。學(xué)生應(yīng)該具有中等程度的程序設(shè)計(jì)知識(shí)，包括指針、遞歸以及面向?qū)ο蟪绦蛟O(shè)計(jì)這樣一些內(nèi)容，此外還要具有一些離散數(shù)學(xué)的基礎(chǔ)。 
　　處理方法 
　　雖然本書的內(nèi)容大部分都與語(yǔ)言無(wú)關(guān)，但是，程序設(shè)計(jì)還是需要使用某種特定的語(yǔ)言。正如書名指出的，我們?yōu)楸緯�選擇了C++。 
　　C++已經(jīng)成為主流系統(tǒng)編程語(yǔ)言。除修復(fù)C語(yǔ)言的許多語(yǔ)法漏洞之外，C++還提供一些直接結(jié)構(gòu)(類和模板)來(lái)實(shí)現(xiàn)作為抽象數(shù)據(jù)類型的泛型數(shù)據(jù)結(jié)構(gòu)。 
　　編寫本書最困難的部分是決定C++所占的篇幅。使用太多C++的特性將使本書難以理解，使用太少又會(huì)使讀者得不到比支持類的C語(yǔ)言教材更多的收獲。 
　　我們所采取的做法是以一種基于對(duì)象的處理方式展示書中的內(nèi)容。這樣，本書幾乎不存在對(duì)繼承的使用。書中以類模板描述泛型數(shù)據(jù)結(jié)構(gòu)。一般我們避免深?yuàn)W的C++特性，但是使用了vector類和string類，如今它們已是C++標(biāo)準(zhǔn)的一部分。本書以前各版通過(guò)把類模板接口從其實(shí)現(xiàn)中分離出來(lái)已經(jīng)做到了對(duì)類模板的實(shí)現(xiàn)。雖然這是有爭(zhēng)議的首選方式，但它揭示出編譯器使讀者難以具體使用代碼的一些問題。因此，這一版中聯(lián)機(jī)代碼把類模板作為一個(gè)獨(dú)立的單元來(lái)介紹，無(wú)需接口與實(shí)現(xiàn)的分離。第1章提供了用于全書的C++特性的綜述，并描述了我們對(duì)類模板的處理方式。附錄A闡述如何能夠重寫類模板以使用分離式編譯。 
　　以C++和Java二者描述的數(shù)據(jù)結(jié)構(gòu)的完全版可在互聯(lián)網(wǎng)上獲得。我們使用類似的編碼約定以使得這兩種語(yǔ)言間平行的結(jié)構(gòu)表現(xiàn)得更加明顯。 
　　第四版最重要的變化概述 
　　本書第四版吸收了大量對(duì)錯(cuò)誤的修正，書中許多部分經(jīng)過(guò)修訂以增加表述的清晰度。此外： 
　　第4章包含AVL樹刪除算法的實(shí)現(xiàn)，它是一個(gè)常常被讀者提出的論題。 
　　第5章已被廣泛修訂和擴(kuò)展，現(xiàn)已包含兩個(gè)更新的算法：杜鵑散列和跳房子散列。此外，還添加了論述通用散列的新的一節(jié)。對(duì)C++中引入的unordered_set和unordered_ map兩個(gè)類模板的簡(jiǎn)要討論也是新加的內(nèi)容。 
　　第6章基本沒有變化，不過(guò)，二叉堆的實(shí)現(xiàn)用到了C++11版引入的移動(dòng)操作(move operation)。 
　　現(xiàn)在的第7章增加了基數(shù)排序的內(nèi)容，并添加了新的一節(jié)，論述下界的證明。排序的程序用到C++11版中引入的移動(dòng)操作。 
　　第8章使用由Seidel和Sharir所作的新的union/find分析，并證明了O(M?(M, N))的界以代替前面各版較弱的O(M log*N)界。 
　　第12章添加了論述后綴樹和后綴數(shù)組的材料，包括Karkkainen和Sanders的后綴數(shù)組線性時(shí)間構(gòu)建算法(及其實(shí)現(xiàn))。刪除了討論確定性跳躍表和AA樹的兩節(jié)。 
　　全書所出現(xiàn)的代碼均用C++11作了更新。值得注意的是，這意味著C++11新特性的使用，包括auto關(guān)鍵字、范圍for循環(huán)、移動(dòng)構(gòu)造和賦值，以及統(tǒng)一初始化(uniform initialization)。 
　　內(nèi)容提要 
　　第1章包含離散數(shù)學(xué)和遞歸的一些復(fù)習(xí)材料。我相信熟練處置遞歸唯一的辦法是反復(fù)不斷地研讀一些好的用法。因此，除第5章外，遞歸遍及本書每一章的例子之中。另外，第1章還介紹了一些材料，作為對(duì)基本C++的回顧，包括在C++類設(shè)計(jì)中對(duì)模板和一些重要結(jié)構(gòu)的討論。 
　　第2章處理算法分析。這一章闡述漸近分析和它的主要弱點(diǎn)。這里提供了許多例子，包括對(duì)對(duì)數(shù)運(yùn)行時(shí)間的深入解釋。通過(guò)直觀地把一些簡(jiǎn)單遞歸程序轉(zhuǎn)變成迭代程序而對(duì)它們進(jìn)行分析。介紹了更復(fù)雜的分治程序，不過(guò)有些分析(求解遞推關(guān)系)將推遲到第7章再詳細(xì)闡述。 
　　第3章包括表、棧和隊(duì)列。這一章包括對(duì)STL中vector類和list類的討論，其中涉及到迭代器的一些材料，并提供對(duì)STL中vector類和list類的重要子集的實(shí)現(xiàn)。 
　　第4章討論樹，重點(diǎn)在查找樹，包括外部查找樹(B樹)。UNIX文件系統(tǒng)和表達(dá)式樹是作為例子來(lái)使用的。本章還介紹了AVL樹和伸展樹。關(guān)于查找樹實(shí)現(xiàn)細(xì)節(jié)的更詳細(xì)的處理放在第12章介紹。樹的另外一些內(nèi)容，如文件壓縮和博弈樹，推遲至第10章討論。外部媒體上的數(shù)據(jù)結(jié)構(gòu)作為幾章中的最后論題來(lái)考慮。STL中set類和map類的討論也在本章進(jìn)行，其中包括一個(gè)重要的例子，該例使用3個(gè)分離的映射高效地解決一個(gè)問題。 
　　第5章討論散列表，包括諸如分離鏈接法以及線性探測(cè)法和平方探測(cè)法這樣一些經(jīng)典算法，此外還有幾個(gè)新算法，即杜鵑散列和跳房子散列。通用散列也在這里討論，而對(duì)可擴(kuò)散列的討論則放在本章末尾進(jìn)行。 
　　第6章是關(guān)于優(yōu)先隊(duì)列的。二叉堆也安排在這里，還有些額外的材料論述優(yōu)先隊(duì)列某些理論上有趣的實(shí)現(xiàn)。斐波那契堆在第11章討論，配對(duì)堆在第12章討論。 
　　第7章是排序。它是關(guān)于編程細(xì)節(jié)和分析的非常特殊的一章。所有重要的通用排序算法均被討論并進(jìn)行了比較。詳細(xì)分析了4種算法：插入排序，希爾排序，堆排序，以及快速排序。本版新增加了基數(shù)排序和一些與選擇相關(guān)問題的下界證明。外部排序的討論安排在本章的末尾進(jìn)行。 
　　第8章討論不相交集算法并證明其運(yùn)行時(shí)間。這是短小且特殊的一章，如果不討論Kruskal算法則該章可以跳過(guò)。 
　　第9章講授圖論算法。圖論算法的趣味性不僅因?yàn)樗鼈冊(cè)趯?shí)踐中經(jīng)常發(fā)生，而且還因?yàn)樗鼈兊倪\(yùn)行時(shí)間強(qiáng)烈地依賴于數(shù)據(jù)結(jié)構(gòu)的恰當(dāng)使用。實(shí)際上，所有標(biāo)準(zhǔn)算法都是和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)、偽代碼以及運(yùn)行時(shí)間的分析一起介紹的。為把這些問題放在一個(gè)適當(dāng)?shù)纳舷挛沫h(huán)境下，本章對(duì)復(fù)雜性理論(包括NP完全性和不可判定性)進(jìn)行了簡(jiǎn)要的討論。 
　　第10章通過(guò)考查一些常見問題的求解技巧來(lái)討論算法設(shè)計(jì)。這一章通過(guò)大量實(shí)例而得到強(qiáng)化。這里及后面各章使用的偽代碼使得學(xué)生對(duì)一個(gè)算法實(shí)例的理解不至于被實(shí)現(xiàn)的細(xì)節(jié)所困擾。 
　　第11章處理攤還分析。對(duì)來(lái)自第4章和第6章的3種數(shù)據(jù)結(jié)構(gòu)以及本章介紹的斐波那契堆進(jìn)行了分析。 
　　第12章討論查找樹算法、后綴樹和后綴數(shù)組、k-d樹、配對(duì)堆。不同于其他各章，本章為查找樹和配對(duì)堆提供了完全和審慎的實(shí)現(xiàn)。材料的安排使得教師可以把一些內(nèi)容整合到其他各章的討論中。例如，第12章中的自頂向下紅黑樹可以和AVL樹(第4章的)一起討論。 
　　第1章～第9章為大多數(shù)一學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程提供了足夠的材料。如果時(shí)間允許，那么第10章也可以包括進(jìn)來(lái)。研究生的算法分析課程可以使用第7章～第11章的內(nèi)容。在第11章所分析的高級(jí)數(shù)據(jù)結(jié)構(gòu)可以容易地在前面各章中查到。第9章中對(duì)NP完全性的討論太過(guò)簡(jiǎn)單，以至于不足以用于這樣的一門算法分析課程。讀者將會(huì)發(fā)現(xiàn)，參閱一些論述NP完全性的著述對(duì)深化本書內(nèi)容大有裨益。 
　　練習(xí) 
　　在每章末尾提供的練習(xí)與正文中講授內(nèi)容的順序相匹配。最后的一些練習(xí)是把一章作為一個(gè)整體來(lái)處理而不是針對(duì)特定的某一節(jié)來(lái)考慮的。難做的練習(xí)標(biāo)以一個(gè)星號(hào)，更難的練習(xí)標(biāo)注兩個(gè)星號(hào)。 
　　參考文獻(xiàn) 
　　參考文獻(xiàn)列于每章的最后。一般說(shuō)來(lái)，這些參考文獻(xiàn)或者是歷史性質(zhì)的，代表著書中材料的原始來(lái)源，或者闡述對(duì)正文中給出結(jié)果的擴(kuò)展和改進(jìn)。有些文獻(xiàn)提供一些練習(xí)的解法。 
　　補(bǔ)充材料 
　　所有讀者均可從網(wǎng)站上獲取下列補(bǔ)充資料： 
　　例子程序的源代碼 
　　勘誤表 
　　此外，下列材料只提供給Pearson Instructor Resource Center 上有資格的教師。如欲獲取這些資料，可訪問IRC或你的Pearson Education銷售代表。 
　　書中挑選的一些練習(xí)的解答 
　　本書中的一些圖示 
　　勘誤表 
　　致謝 
　　在該叢書幾部著作的準(zhǔn)備過(guò)程中作者得到了許許多多朋友的幫助，有些人在本書的其他版本中列出。謝謝所有諸位。 
　　如同往常一樣，Pearson專家們的努力使得本書的寫作過(guò)程更加輕松。我愿意借此機(jī)會(huì)感謝我的編輯Tracy Johnson，以及制作編輯Marilyn Lloyd。賢妻Jill因其所做的每一件工作應(yīng)該得到我特別的感謝。 
　　最后，我還要感謝廣大的讀者，他們發(fā)送E-mail信息并指出較早各版的錯(cuò)誤和矛盾之處。我的網(wǎng)站www.cis.fiu.edu/~weiss也將包含更新后(C++和Java)的源代碼，一個(gè)勘誤表，以及到提交問題報(bào)告的一個(gè)鏈接。 
　　M．A．W． 
　　Miami，F(xiàn)lorida