《算法》第4版(Sedgewick)

1、- -算法第4版（Sedgewick之巨著，與高德納TAOCP脈相承）定價：99.00會員價：72.27（73折）校園優(yōu)惠價：72.27（73折）原書名：Algorithms,FourthEdition作者：（美）塞奇威克（Sedgewick,R.）（美）韋恩（Wayne,K.）譯者：謝路云叢書名：圖靈程序設計叢書出版社：人民郵電出版社ISBN：9787115293800上架時間：2012-9-29出版日期：2012年10月開本：16開頁碼：636版次：1-1、/、-前言本書力圖研究當今最重要的計算機算法并將一些最基礎的技能傳授給廣大求知者。它適合用做計算機科學進階教材，面向已經(jīng)熟悉了計算機系

2、統(tǒng)并掌握了基本編程技能的學生。本書也可用于自學，或是作為開發(fā)人員的參考手冊，因為書中實現(xiàn)了許多實用算法并詳盡分析了它們的性能特點和用途。這本書取材廣泛，很適合作為該領域的入門教材。算法和數(shù)據(jù)結構的學習是所有計算機科學教學計劃的基礎，但它并不只是對程序員和計算機系的學生有用。任何計算機使用者都希望計算機能運行得更快一些或是能解決更大規(guī)模的問題。本書中的算法代表了近50年來的大量優(yōu)秀研究成果，是人們工作中必備的知識。從物理中的N體模擬問題到分子生物學中的基因序列問題，我們描述的基本方法對科學研究而言已經(jīng)必不可少；從建筑建模系統(tǒng)到模擬飛行器，這些算法已經(jīng)成為工程領域極其重要的工具；從數(shù)據(jù)庫系統(tǒng)到互聯(lián)

3、網(wǎng)搜索引擎，算法已成為現(xiàn)代軟件系統(tǒng)中不可或缺的一部分。這僅是幾個例子而已，隨著計算機應用領域的不斷擴張，這些基礎方法的影響也會不斷擴大。在開始學習這些基礎算法之前，我們先要熟悉全書中都將會用到的棧、隊列等低級抽象的數(shù)據(jù)類型。然后依次研究排序、搜索、圖和字符串方面的基礎算法。最后一章將會從宏觀角度總結全書的內容。獨特之處本書致力于研究有實用價值的算法。書中講解了多種算法和數(shù)據(jù)結構，并提供了大量相關的信息，讀者應該能有信心在各種計算環(huán)境下實現(xiàn)、調試并應用它們。本書的特點涉及以下幾個方面。算法書中均有算法的完整實現(xiàn)，并討論了程序在多個樣例上的運行狀況。書中的代碼都是可以運行的程序而非偽代碼，因此非常

4、便于投入使用。書中程序是用Java語言編寫的，但其編程風格方便讀者使用其他現(xiàn)代編程語言重用其中的大部分代碼來實現(xiàn)相同算法。數(shù)據(jù)類型我們在數(shù)據(jù)抽象上采用了現(xiàn)代編程風格，將數(shù)據(jù)結構和算法封裝在了一起。應用每一章都會給出所述算法起到關鍵作用的應用場景。這些場景多種多樣，包括物理模擬與分子生物學、計算機與系統(tǒng)工程學，以及我們熟悉的數(shù)據(jù)壓縮和網(wǎng)絡搜索等。學術性我們非常重視使用數(shù)學模型來描述算法的性能。我們用模型預測算法的性能，然后在真實的環(huán)境中運行程序來驗證預測。廣度本書討論了基本的抽象數(shù)據(jù)類型、排序算法、搜索算法、圖及字符串處理。我們在算法的討論中研究數(shù)據(jù)結構、算法設計范式、歸納法和解題模型。這將涵蓋

5、20世紀60年代以來的經(jīng)典方法以及近年來產(chǎn)生的新方法。我們的主要目標是將今天最重要的實用算法介紹給盡可能廣泛的群體。這些算法一般都十分巧妙奇特，20行左右的代碼就足以表達。它們展現(xiàn)出的問題解決能力令人嘆為觀止。沒有它們，創(chuàng)造計算智能、解決科學問題、開發(fā)商業(yè)軟件都是不可能的。本書網(wǎng)站本書的一個亮點是它的配套網(wǎng)站。這一網(wǎng)站面向教師、學生和專業(yè)人士，免費提供關于算法和數(shù)據(jù)結構的豐富資料。一份在線大綱包含了本書內容的結構并提供了鏈接，瀏覽起來十分方便。全部實現(xiàn)代碼書中所有的代碼均可以在這里找到，且其形式適合用于程序開發(fā)。此外，還包括算法的其他實現(xiàn)，例如高級的

6、實現(xiàn)、書中提及的改進的實現(xiàn)、部分習題的答案以及多個應用場景的客戶端代碼。我們的重點是用真實的應用環(huán)境來測試算法。習題與答案網(wǎng)站還提供了一些附加的選擇題（只需要一次單擊便可獲取答案）、很多算法應用的例子、編程練習和答案以及一些有挑戰(zhàn)性的難題。動態(tài)可視化書是死的，但網(wǎng)站是活的，在這里我們充分利用圖形類演示了算法的應用效果。課程資料網(wǎng)站包含和本書及網(wǎng)上內容對應的一整套幻燈片，以及一系列編程作業(yè)、核對表、測試數(shù)據(jù)和備課手冊。相關資料鏈接網(wǎng)站包含大量的鏈接，提供算法應用的更多背景知識以及學習算法的其他資源。我們希望這個站點和本書互為補充。一般來說，建議讀者在第一次學習某種算法或是希望獲得整體概念時看書，

7、并把網(wǎng)站作為編程時的參考或是在線查找更多信息的起點。作為教材本書為計算機科學專業(yè)進階的教材，涵蓋了這門學科的核心內容，并能讓學生充分鍛煉編程、定量推理和解決問題等方面的能力。一般來說，此前學過一門計算機方面的先導課程就足矣，只要熟悉一門現(xiàn)代編程語言并熟知現(xiàn)代計算機系統(tǒng)，就都能夠閱讀本書。雖然本書使用Java實現(xiàn)算法和數(shù)據(jù)結構，但其代碼風格使得熟悉其他現(xiàn)代編程語言的人也能看懂。我們充分利用了Java的抽象性（包括泛型），但不會依賴這門語言的獨門特性。.書中涉及的多數(shù)數(shù)學知識都有完整的講解（少數(shù)會有延伸閱讀），因此閱讀本書并不需要準備太多數(shù)學知識，不過有一定的數(shù)學基礎當然更好。應用場景都來自其他學

8、科的基礎內容，同樣也在書中有完整介紹。本書涉及的內容是任何準備主修計算機科學、電氣工程、運籌學等專業(yè)的學生應了解的基礎知識，并且對所有對科學、數(shù)學或工程學感興趣的學生也十分有價值。背景介紹這本書意在接續(xù)我們的一本基礎教材Java程序設計：一種跨學科的方法，那本書對計算機領域做了概括性介紹。這兩本書合起來可用做兩到三個學期的計算機科學入門課程教材，為所有學生在自然科學、工程學和社會科學中解決計算問題提供必備的基礎知識。本書大部分內容來自Sedgewick的算法系列圖書。本質上，本書和該系列的第1版和第2版最接近，但還包含了作者多年教學和學習的經(jīng)驗。Sedgewick的C算法（第3版）、C+算法（

9、第3版）、Java算法（第3版）更適合用做參考書或是高級課程的教材，而本書則是專門為大學一、二年級學生設計的一學期教材，也是最新的基礎入門書或從業(yè)者的參考書。致謝本書的編寫花了近40年時間，因此想要一一列出所有參與人是不可能的。本書的前幾版一共列出了好幾十人，其中包括（按字母順序）AndrewAppel、TrinaAvery、MarcBrown、LynDuprePhilippeFlajolet、TomFreeman、DaveHanson、JanetIncerpi、MikeSchidlowsky、SteveSummit和ChrisVanWyk。我要感謝他們所有人，盡管其中有些人的貢獻要追溯到幾十

10、年前。至于第4版，我們要感謝試用了本書樣稿的普林斯頓及其他院校的數(shù)百名學生，以及通過本書網(wǎng)站發(fā)表意見和指出錯誤的世界各地的讀者。我們還要感謝普林斯頓大學對于高質量教學的堅定支持，這是本書得以面世的基礎。PeterGordon幾乎從本書寫作之初就提出了很多有用的建議，這一版奉行的“歸本溯源”的指導思想也是他最早提出的。關于第4版，我們要感謝BarbaraWood認真又專業(yè)的編輯工作，JulieNahil對生產(chǎn)過程的管理，以及Pearson出版公司中為本書的付梓和營銷辛勤工作的朋友。所有人都在積極地追趕進度，而本書的質量并沒有受到絲毫影響。- -目錄算法:第4版第1章基礎1基礎編程模型4java程

11、序的基本結構4原始數(shù)據(jù)類型與表達式6語句8TOC o 1-5 h z簡便記法9數(shù)組10靜態(tài)方法12api16字符串20輸入輸出21二分查找28展望30數(shù)據(jù)抽象38使用抽象數(shù)據(jù)類型38抽象數(shù)據(jù)類型舉例45抽象數(shù)據(jù)類型的實現(xiàn)52更多抽象數(shù)據(jù)類型的實現(xiàn)55數(shù)據(jù)類型的設計60.1.3背包、隊列和棧74api74集合類數(shù)據(jù)類型的實現(xiàn)81TOC o 1-5 h z鏈表89綜述98算法分析108科學方法108觀察108數(shù)學模型112增長數(shù)量級的分類117設計更快的算法118倍率實驗121注意事項123處理對于輸入的依賴124內存126展望129案例研究：union-find算法1361.5.1動態(tài)連通性13

12、61.5.2實現(xiàn)1401.5.3展望148第2章排序1522.1初級排序算法1532.1.1游戲規(guī)則1532.1.2選擇排序1552.1.3插入排序157TOC o 1-5 h z排序算法的可視化159比較兩種排序算法159希爾排序162歸并排序170原地歸并的抽象方法170自頂向下的歸并排序171自底向上的歸并排序175排序算法的復雜度1772.3快速排序1822.3.1基本算法1822.3.2性能特點1852.3.3算法改進1872.4優(yōu)先隊列1952.4.1api1952.4.2初級實現(xiàn)1972.4.3堆的定義1982.4.4堆的算法1992.4.5堆排序205應用214將各種數(shù)據(jù)排序2

13、14我應該使用哪種排序算法218問題的歸約219排序應用一覽221第3章查找227符號表228api228有序符號表230用例舉例233TOC o 1-5 h z無序鏈表中的順序查找235有序數(shù)組中的二分查找238對二分查找的分析242預覽244二叉查找樹250基本實現(xiàn)250分析255有序性相關的方法與刪除操作257平衡查找樹2692-3查找樹269紅黑二叉查找樹275實現(xiàn)280刪除操作282紅黑樹的性質284散列表293散列函數(shù)293基于拉鏈法的散列表297基于線性探測法的散列表3003.5.1我應該使用符號表的哪種實現(xiàn)3123.5.2集合的api3133.5.3字典類用例3153.5.4索

14、引類用例3183.5.5稀疏向量322第4章圖3294.1無向圖3314.1.1術語表3314.1.2表示無向圖的數(shù)據(jù)類型4.1.3深度優(yōu)先搜索3384.1.4尋找路徑3424.1.5廣度優(yōu)先搜索3444.1.6連通分量3494.1.7符號圖3524.1.8總結3584.2有向圖3644.2.1術語3643334.2.2有向圖的數(shù)據(jù)類型3654.2.3有向圖中的可達性3674.2.4環(huán)和有向無環(huán)圖3695.1.4三向字符串快速排序4675.1.5字符串排序算法的選擇4705.2單詞查找樹4745.2.1單詞查找樹4755.2.2單詞查找樹的性質4835.2.3三向單詞查找樹4855.2.4三向

15、單詞查找樹的性質4875.2.5應該使用字符串符號表的哪種實現(xiàn)4895.3子字符串查找4935.3.1歷史簡介4935.3.2暴力子字符串查找算法4945.3.3knuth-morris-pratt子字符串查找算法4965.3.4boyer-moore字符串查找算法5025.3.5rabin-karp指紋字符串查找算法5055.3.6總結5095.4正則表達式5145.4.1使用正則表達式描述模式5145.4.2縮略寫法5165.4.3正則表達式的實際應用5175.4.4非確定有限狀態(tài)自動機5185.4.5模擬nfa的運行5205.4.6構造與正則表達式對應的5.5數(shù)據(jù)壓縮5295.5.1游戲規(guī)則5295.5.2讀寫二進制數(shù)據(jù)5305.5.3局限5335.5.4熱身運動：基因組5345.5.5游程編碼5375.5.6霍夫曼壓縮540第6章背景558索引611調整數(shù)組大小304內存使用306應用312有向圖中的強連通