導讀： 簡介: 內容簡介：本書全面論述了數據結構和算法分析，即組織大量數據的方法和對算法運行時間的估計。隨著計算機的速度越來越快，對於能夠處理大量輸入數據的程序的需求變得日益 簡介:


內容簡介：
本書全面論述了數據結構和算法分析，即組織大量數據的方法和對算法運行時間的估計。隨著計算機的速度越來越快，對於能夠處理大量輸入數據的程序的需求變得日益迫切。具有諷刺意味的是，由於在輸入量很大時程序的效率明顯降低，因此這又要求更加關注效率問題。通過在實際編程之前對算法進行分析，學生可以確定一個特定的解法是否可行。例如，在本書中學生可看到一些特定的問題，並了解精心的實現如何能夠把處理大量數據的時間從16年減至不到1秒。因此，本書中論述的算法和數據結構均進行了運行時間方面的分析。在某些情況下，還研究了影響實現運行時間的一些微小細節。.
一旦確定了解法，接著就要編寫程序。隨著計算機功能的日益強大，它們必須解決的問題也越來越大，越來越復雜，這就要求開發更加復雜的程序。本書的目的是在教會學生使用良好的程序設計技巧的同時讓學生具備算法分析能力，使得他們開發的這類程序具有最高效率。
本書適用於本科生的高級數據結構課程或是研究生的算法分析課程。使用本書的學生應該具有中等程度的程序設計方面的知識，包括指針、遞歸和面向對象程序設計，還要具有離散數學的某些知識。
方法
雖然本書中的內容大部分都是與語言無關的，但是，程序設計還是需要使用某種特定的語言。正如書名指出的，我們為本書選擇了C++。
C++已經成為系統編程的主流語言。除了修正了許多C語言的語法方面的缺陷之外，C++還提供了直接結構（類和模板）來實現抽象數據類型的通用數據結構。
撰寫本書最困難的部分是確定C++在書中所占的比例。使用太多的C++的特性將使教材變得很晦澀，使用得太少又會和使用支持類的C語言撰寫的教材區別不大。
我們采用的方法是以基於對象的方法來闡述文中的內容。這樣，本書中幾乎沒有用到繼承性。我們采用類模板來描述通用數據結構。通常情況下盡量避免使用深奧的C++特性，而是使用標准C++中的vector和string類。通過采用C++的現代特性來取代在本書第1版中所用的次級特性簡化了很多代碼。本書前幾版已經實現了類模板，方法是將類模板的接口與其實現分離開。毫無疑問，這是一種好方法，但是這種方法暴露出了編譯的問題，讀者事實上很難利用這些代碼。本版中，在線的源代碼將類模板作為一個單元來表示，而不再將接口和實現分離開。本書第1章對書中所用到的C++特性進行了介紹，並闡述了對類模板的處理方法。附錄描述了如何重寫類模板，用於分離編譯。
以Java和C++兩種語言描述的數據結構的完全版在因特網上可以得到。我們使用類似的編碼習慣使得這兩種語言間的相似性表現得更加明顯。
第3版中的主要變化
第3版中包含了大量的錯誤修正，並且書中的大部分章節都經過了修訂以提高其可讀性。另外，本版還有以下幾方面的變化：
·書中的所有代碼都做了更新以適應現代的C++特性。
·第3章進行了大量的修訂，並且討論了標准vector和list類的使用及其實現。標准vector類在其他數據結構的實現中被廣泛使用。
·第4章修訂後包含了關於set和map類的討論，並通過一個擴展的例子介紹了它們在有效算法設計中的應用。在第9章中也包含了一個使用標准map類來實現最短路徑算法的例子。
·第7章討論了標准sort算法，其中包括一個關於實現重載的標准sort算法所涉及的技巧。
·書中提供的源代碼都已經進行了簡化，從而避免了與類模板的分離編譯有關的復雜語法。修訂後的代碼可以使讀者更專心於算法本身，而不是過多地關注C++。
內容概述
第1章包含離散數學和遞歸的一些內容。我相信熟悉遞歸的唯一辦法是反復不斷地看一些好的用法。因此，除第5章外，遞歸遍布本書每一章的例子中。第1章還介紹了一些C++的內容，包括C++基礎知識的回顧以及C++類設計中模板和重要結構的討論。
第2章討論算法分析。這一章闡述了漸近分析和它的主要弱點。這裡提供了許多例子，包括對對數運行時間的深入解釋。通過直觀地把一些簡單遞歸程序轉變成迭代程序，對它們進行分析。這一章還介紹了更復雜的分治程序，不過有些分析（求解遞歸關系）要到第7章再詳細進行。
.第3章包括表、棧和隊列。這一章較之以前的版本進行了大量的修訂。現在包含了關於STL vector和list類的討論，包括有關迭代的內容，並且提供了STL vector和list類的重要子集的實現。
第4章討論樹，重點在查找樹，包括外部查找樹（B樹）。UNIX文件系統和表達式樹是作為例子介紹的。本章還介紹了AVL樹和伸展樹。查找樹實現細節的更詳細討論可在第12章找到。樹的另外一些內容，如文件壓縮和博弈樹，延遲到第10章討論。外部介質上的數據結構作為幾章中的最後論題來考慮。本版中新增的部分是對STL set和map類的討論，包括一個講解了如何使用三個分離的圖來高效率地解決問題的例子。..
第5章相對較短，主要討論散列表。這裡進行了某些分析，本章末尾討論了可擴展散列。
第6章是關於優先隊列的。這一章還講解了二叉堆，還有一些附加內容，論述優先隊列某些理論上很有趣的實現方法。斐波那契堆在第11章討論，配對堆在第12章討論。
第7章是排序。它是關於編程細節和分析的非常特殊的一章，討論並比較了所有重要的通用排序算法。對插入排序、希爾排序、堆排序以及快速排序這四種算法進行了詳細的分析。這一章末尾還討論了外部排序。
第8章討論不相交集算法並證明其運行時間。這一章短且特殊，如果不討論Kruskal算法則這一章可跳過。
第9章講授圖論算法。圖論算法之所以重要，不僅因為它們在實踐中頻繁出現，而且因為它們的運行時間特別依賴於數據結構的恰當使用。實際上，所有標准算法都是和相應的數據結構、偽代碼以及運行時間的分析一起介紹的。為把這些問題放在一個適當的環境下討論，書中提供了對復雜性理論（包括NP完全性和不可判定性）的簡短討論。
第10章通過考查一般的問題求解技巧來介紹算法設計。這一章含有大量的實例。這裡及後面各章使用了偽代碼，使學生對一個示例算法的理解不受具體實現細節的困擾。
第11章處理攤還分析。對第4章和第6章的三種數據結構以及本章介紹的斐波那契堆進行了分析。
第12章討論查找樹算法、k-d樹和配對堆。不同於其他各章，這一章給出了查找樹和配對堆完全的仔細的實現。材料的安排使得教師可以把一些內容納入到其他各章的討論之中。例如，第12章中的自頂向下紅黑樹可以和（第4章的）AVL樹一起討論。
第1章～第9章為大多數一學期的數據結構課程提供了足夠的材料。如果時間允許，第10章也可以包括進來。研究生的算法分析課程可以使用第7章到第11章的內容。在第11章分析的高級數據結構可以很容易地在前面各章中查到。第9章中對NP完全性的討論太過簡短，以至於不能用於算法分析課程。可以使用論述NP完全性的其他書籍來補充本書的這部分不足。
作者簡介：
Mark Allen Weiss，1987年在普林斯頓大學獲得計算機科學博士學位，師從Robert Sedgewick，現任美國佛羅裡達國際大學計算與信息科學學院教授。他曾經擔任全美AP(Advanced Placement)考試計算機學科委員會的主席(2000-2004)。他的主要研究方向是數據結構、算法和教育學。
內容截圖：


歡迎大家重新加入我的小組——數學及計算機愛好者之家
http://www.VeryCD.com/groups/@g2387585/
電腦出現了意外，所以我保證以前的書籍會重新發布。在線時間：晚上9:30——11:30，除非有特別的事情，否則，可以保證在線，白天不定時了。