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