算法(第4版)(圖靈出品)

第1章　 基礎(chǔ)
1.1　基礎(chǔ)編程模型
1.1.1　Java程序的基本結(jié)構(gòu)
1.1.2　原始數(shù)據(jù)類型與表達(dá)式
1.1.3　 語句
1.1.4　 簡(jiǎn)便記法
1.1.5　 數(shù)組
1.1.6　 靜態(tài)方法
1.1.7　 API
1.1.8　 字符串
1.1.9　 輸入輸出
1.1.10　 二分查找
1.1.11　 展望
1.2　 數(shù)據(jù)抽象
1.2.1　 使用抽象數(shù)據(jù)類型
1.2.2　 抽象數(shù)據(jù)類型舉例
1.2.3　 抽象數(shù)據(jù)類型的實(shí)現(xiàn)
1.2.4　 更多抽象數(shù)據(jù)類型的實(shí)現(xiàn)
1.2.5　 數(shù)據(jù)類型的設(shè)計(jì)
1.3　 背包、隊(duì)列和棧
1.3.1　 API
1.3.2　 集合類數(shù)據(jù)類型的實(shí)現(xiàn)
1.3.3　 鏈表
1.3.4　 綜述
1.4　 算法分析
1.4.1　 科學(xué)方法
1.4.2　 觀察
1.4.3　 數(shù)學(xué)模型
1.4.4　 增長(zhǎng)數(shù)量級(jí)的分類
1.4.5　 設(shè)計(jì)更快的算法
1.4.6　 倍率實(shí)驗(yàn)
1.4.7　 注意事項(xiàng)
1.4.8　 處理對(duì)于輸入的依賴
1.4.9　 內(nèi)存
1.4.10　 展望
1.5　 案例研究：union-find算法
1.5.1　 動(dòng)態(tài)連通性
1.5.2　 實(shí)現(xiàn)
1.5.3　 展望

第2章　 排序
2.1　 初級(jí)排序算法
2.1.1　 游戲規(guī)則
2.1.2　 選擇排序
2.1.3　 插入排序
2.1.4　 排序算法的可視化
2.1.5　 比較兩種排序算法
2.1.6　 希爾排序
2.2　 歸并排序
2.2.1　 原地歸并的抽象方法
2.2.2　 自頂向下的歸并排序
2.2.3　 自底向上的歸并排序
2.2.4　 排序算法的復(fù)雜度
2.3　 快速排序
2.3.1　 基本算法
2.3.2　 性能特點(diǎn)
2.3.3　 算法改進(jìn)
2.4　 優(yōu)先隊(duì)列
2.4.1　 API
2.4.2　 初級(jí)實(shí)現(xiàn)
2.4.3　 堆的定義
2.4.4　 堆的算法
2.4.5　 堆排序
2.5　 應(yīng)用
2.5.1　 將各種數(shù)據(jù)排序
2.5.2　 我應(yīng)該使用哪種排序算法
2.5.3　 問題的歸約
2.5.4　 排序應(yīng)用一覽

第3章　查找
3.1　符號(hào)表
3.1.1　API
3.1.2　有序符號(hào)表
3.1.3　用例舉例
3.1.4　無序鏈表中的順序查找
3.1.5　有序數(shù)組中的二分查找
3.1.6　對(duì)二分查找的分析
3.1.7　預(yù)覽
3.2　二叉查找樹
3.2.1　基本實(shí)現(xiàn)
3.2.2　分析
3.2.3　有序性相關(guān)的方法與刪除操作
3.3　平衡查找樹
3.3.1　2-3查找樹
3.3.2　紅黑二叉查找樹
3.3.3　實(shí)現(xiàn)
3.3.4　刪除操作
3.3.5　紅黑樹的性質(zhì)
3.4　散列表
3.4.1　散列函數(shù)
3.4.2　基于拉鏈法的散列表
3.4.3　基于線性探測(cè)法的散列表
3.4.4　調(diào)整數(shù)組大小
3.4.5　內(nèi)存使用
3.5　應(yīng)用
3.5.1　我應(yīng)該使用符號(hào)表的哪種實(shí)現(xiàn)
3.5.2　集合的API
3.5.3　字典類用例
3.5.4　索引類用例
3.5.5　稀疏向量

第4章　 圖
4.1　 無向圖
4.1.1　 術(shù)語表
4.1.2　 表示無向圖的數(shù)據(jù)類型
4.1.3　 深度優(yōu)先搜索
4.1.4　 尋找路徑
4.1.5　 廣度優(yōu)先搜索
4.1.6　 連通分量
4.1.7　 符號(hào)圖
4.1.8　 總結(jié)
4.2　 有向圖
4.2.1　 術(shù)語
4.2.2　 有向圖的數(shù)據(jù)類型
4.2.3　 有向圖中的可達(dá)性
4.2.4　 環(huán)和有向無環(huán)圖
4.2.5　 有向圖中的強(qiáng)連通性
4.2.6　 總結(jié)
4.3　 最小生成樹
4.3.1　 原理
4.3.2　 加權(quán)無向圖的數(shù)據(jù)類型
4.3.3　 最小生成樹的API和測(cè)試用例
4.3.4　 Prim算法
4.3.5　 Prim算法的即時(shí)實(shí)現(xiàn)
4.3.6　 Kruskal算法
4.3.7　 展望
4.4　 最短路徑
4.4.1　 最短路徑的性質(zhì)
4.4.2　 加權(quán)有向圖的數(shù)據(jù)結(jié)構(gòu)
4.4.3　 最短路徑算法的理論基礎(chǔ)
4.4.4　 Dijkstra算法
4.4.5　 無環(huán)加權(quán)有向圖中的最短路徑算法
4.4.6　 一般加權(quán)有向圖中的最短路徑問題
4.4.7　 展望

第5章　 字符串
5.1　 字符串排序
5.1.1　 鍵索引計(jì)數(shù)法
5.1.2　 低位優(yōu)先的字符串排序
5.1.3　 高位優(yōu)先的字符串排序
5.1.4　 三向字符串快速排序
5.1.5　 字符串排序算法的選擇
5.2　 單詞查找樹
5.2.1　 單詞查找樹
5.2.2　 單詞查找樹的性質(zhì)
5.2.3　 三向單詞查找樹
5.2.4　 三向單詞查找樹的性質(zhì)
5.2.5　 應(yīng)該使用字符串符號(hào)表的哪種實(shí)現(xiàn)
5.3　 子字符串查找
5.3.1　 歷史簡(jiǎn)介
5.3.2　 暴力子字符串查找算法
5.3.3　 Knuth-Morris-Pratt子字符串查找算法
5.3.4　 Boyer-Moore字符串查找算法
5.3.5　 Rabin-Karp指紋字符串查找算法
5.3.6　 總結(jié)
5.4　 正則表達(dá)式
5.4.1　 使用正則表達(dá)式描述模式
5.4.2　 縮略寫法
5.4.3　 正則表達(dá)式的實(shí)際應(yīng)用
5.4.4　 非確定有限狀態(tài)自動(dòng)機(jī)
5.4.5　 模擬NFA的運(yùn)行
5.4.6　 構(gòu)造與正則表達(dá)式對(duì)應(yīng)的
5.5　 數(shù)據(jù)壓縮
5.5.1　 游戲規(guī)則
5.5.2　 讀寫二進(jìn)制數(shù)據(jù)
5.5.3　 局限
5.5.4　 熱身運(yùn)動(dòng)：基因組
5.5.5　 游程編碼
5.5.6　 霍夫曼壓縮

第6章　 背景
索引

　　本書力圖研究當(dāng)今最重要的計(jì)算機(jī)算法并將一些最基礎(chǔ)的技能傳授給廣大求知者。它適合用做計(jì)算機(jī)科學(xué)進(jìn)階教材，面向已經(jīng)熟悉了計(jì)算機(jī)系統(tǒng)并掌握了基本編程技能的學(xué)生。本書也可用于自學(xué)，或是作為開發(fā)人員的參考手冊(cè)，因?yàn)闀袑?shí)現(xiàn)了許多實(shí)用算法并詳盡分析了它們的性能特點(diǎn)和用途。這本書取材廣泛，很適合作為該領(lǐng)域的入門教材。
　　算法和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)是所有計(jì)算機(jī)科學(xué)教學(xué)計(jì)劃的基礎(chǔ)，但它并不只是對(duì)程序員和計(jì)算機(jī)系的學(xué)生有用。任何計(jì)算機(jī)使用者都希望計(jì)算機(jī)能運(yùn)行得更快一些或是能解決更大規(guī)模的問題。本書中的算法代表了近50年來的大量?jī)?yōu)秀研究成果，是人們工作中必備的知識(shí)。從物理中的N體模擬問題到分子生物學(xué)中的基因序列問題，我們描述的基本方法對(duì)科學(xué)研究而言已經(jīng)必不可少；從建筑建模系統(tǒng)到模擬飛行器，這些算法已經(jīng)成為工程領(lǐng)域極其重要的工具；從數(shù)據(jù)庫(kù)系統(tǒng)到互聯(lián)網(wǎng)搜索引擎，算法已成為現(xiàn)代軟件系統(tǒng)中不可或缺的一部分。這僅是幾個(gè)例子而已，隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)張，這些基礎(chǔ)方法的影響也會(huì)不斷擴(kuò)大。
　　在開始學(xué)習(xí)這些基礎(chǔ)算法之前，我們先要熟悉全書中都將會(huì)用到的棧、隊(duì)列等低級(jí)抽象的數(shù)據(jù)類型。然后依次研究排序、搜索、圖和字符串方面的基礎(chǔ)算法。最后一章將會(huì)從宏觀角度總結(jié)全書的內(nèi)容。
　　獨(dú)特之處
　　本書致力于研究有實(shí)用價(jià)值的算法。書中講解了多種算法和數(shù)據(jù)結(jié)構(gòu)，并提供了大量相關(guān)的信息，讀者應(yīng)該能有信心在各種計(jì)算環(huán)境下實(shí)現(xiàn)、調(diào)試并應(yīng)用它們。本書的特點(diǎn)涉及以下幾個(gè)方面。算法　書中均有算法的完整實(shí)現(xiàn)，并討論了程序在多個(gè)樣例上的運(yùn)行狀況。書中的代碼都是可以運(yùn)行的程序而非偽代碼，因此非常便于投入使用。書中程序是用Java語言編寫的，但其編程風(fēng)格方便讀者使用其他現(xiàn)代編程語言重用其中的大部分代碼來實(shí)現(xiàn)相同算法。
　　數(shù)據(jù)類型
　　我們?cè)跀?shù)據(jù)抽象上采用了現(xiàn)代編程風(fēng)格，將數(shù)據(jù)結(jié)構(gòu)和算法封裝在了一起。
　　應(yīng)用
　　每一章都會(huì)給出所述算法起到關(guān)鍵作用的應(yīng)用場(chǎng)景。這些場(chǎng)景多種多樣，包括物理模擬與分子生物學(xué)、計(jì)算機(jī)與系統(tǒng)工程學(xué)，以及我們熟悉的數(shù)據(jù)壓縮和網(wǎng)絡(luò)搜索等。
　　學(xué)術(shù)性
　　我們非常重視使用數(shù)學(xué)模型來描述算法的性能。我們用模型預(yù)測(cè)算法的性能，然后在真實(shí)的環(huán)境中運(yùn)行程序來驗(yàn)證預(yù)測(cè)。
　　廣度
　　本書討論了基本的抽象數(shù)據(jù)類型、排序算法、搜索算法、圖及字符串處理。我們?cè)谒惴ǖ挠懻撝醒芯繑?shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)范式、歸納法和解題模型。這將涵蓋20世紀(jì)60年代以來的經(jīng)典方法以及近年來產(chǎn)生的新方法。
　　我們的主要目標(biāo)是將今天最重要的實(shí)用算法介紹給盡可能廣泛的群體。這些算法一般都十分巧妙奇特，20行左右的代碼就足以表達(dá)。它們展現(xiàn)出的問題解決能力令人嘆為觀止。沒有它們，創(chuàng)造計(jì)算智能、解決科學(xué)問題、開發(fā)商業(yè)軟件都是不可能的。
　　本書網(wǎng)站
　　本書的一個(gè)亮點(diǎn)是它的配套網(wǎng)站algs4.cs.princeton.edu。這一網(wǎng)站面向教師、學(xué)生和專業(yè)人士，免費(fèi)提供關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的豐富資料。
　　一份在線大綱　包含了本書內(nèi)容的結(jié)構(gòu)并提供了鏈接，瀏覽起來十分方便。
　　全部實(shí)現(xiàn)代碼　書中所有的代碼均可以在這里找到，且其形式適合用于程序開發(fā)。此外，還包括算法的其他實(shí)現(xiàn)，例如高級(jí)的實(shí)現(xiàn)、書中提及的改進(jìn)的實(shí)現(xiàn)、部分習(xí)題的答案以及多個(gè)應(yīng)用場(chǎng)景的客戶端代碼。我們的重點(diǎn)是用真實(shí)的應(yīng)用環(huán)境來測(cè)試算法。
　　習(xí)題與答案　網(wǎng)站還提供了一些附加的選擇題（只需要一次單擊便可獲取答案）、很多算法應(yīng)用的例子、編程練習(xí)和答案以及一些有挑戰(zhàn)性的難題。
　　動(dòng)態(tài)可視化　書是死的，但網(wǎng)站是活的，在這里我們充分利用圖形類演示了算法的應(yīng)用效果。課程資料　網(wǎng)站包含和本書及網(wǎng)上內(nèi)容對(duì)應(yīng)的一整套幻燈片，以及一系列編程作業(yè)、核對(duì)表、測(cè)試數(shù)據(jù)和備課手冊(cè)。
　　相關(guān)資料鏈接　網(wǎng)站包含大量的鏈接，提供算法應(yīng)用的更多背景知識(shí)以及學(xué)習(xí)算法的其他資源。我們希望這個(gè)站點(diǎn)和本書互為補(bǔ)充。一般來說，建議讀者在第一次學(xué)習(xí)某種算法或是希望獲得整體概念時(shí)看書，并把網(wǎng)站作為編程時(shí)的參考或是在線查找更多信息的起點(diǎn)。
　　作為教材
　　本書為計(jì)算機(jī)科學(xué)專業(yè)進(jìn)階的教材，涵蓋了這門學(xué)科的核心內(nèi)容，并能讓學(xué)生充分鍛煉編程、定量推理和解決問題等方面的能力。一般來說，此前學(xué)過一門計(jì)算機(jī)方面的先導(dǎo)課程就足矣，只要熟悉一門現(xiàn)代編程語言并熟知現(xiàn)代計(jì)算機(jī)系統(tǒng)，就都能夠閱讀本書。
　　雖然本書使用Java實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)，但其代碼風(fēng)格使得熟悉其他現(xiàn)代編程語言的人也能看懂。我們充分利用了Java的抽象性（包括泛型），但不會(huì)依賴這門語言的獨(dú)門特性。書中涉及的多數(shù)數(shù)學(xué)知識(shí)都有完整的講解（少數(shù)會(huì)有延伸閱讀），因此閱讀本書并不需要準(zhǔn)備太多數(shù)學(xué)知識(shí)，不過有一定的數(shù)學(xué)基礎(chǔ)當(dāng)然更好。應(yīng)用場(chǎng)景都來自其他學(xué)科的基礎(chǔ)內(nèi)容，同樣也在書中有完整介紹。
　　本書涉及的內(nèi)容是任何準(zhǔn)備主修計(jì)算機(jī)科學(xué)、電氣工程、運(yùn)籌學(xué)等專業(yè)的學(xué)生應(yīng)了解的基礎(chǔ)知識(shí)，并且對(duì)所有對(duì)科學(xué)、數(shù)學(xué)或工程學(xué)感興趣的學(xué)生也十分有價(jià)值。
　　背景介紹
　　這本書意在接續(xù)我們的一本基礎(chǔ)教材《Java程序設(shè)計(jì)：一種跨學(xué)科的方法》，那本書對(duì)計(jì)算機(jī)領(lǐng)域做了概括性介紹。這兩本書合起來可用做兩到三個(gè)學(xué)期的計(jì)算機(jī)科學(xué)入門課程教材，為所有學(xué)生在自然科學(xué)、工程學(xué)和社會(huì)科學(xué)中解決計(jì)算問題提供必備的基礎(chǔ)知識(shí)。
　　本書大部分內(nèi)容來自Sedgewick的算法系列圖書。本質(zhì)上，本書和該系列的第1版和第2版最接近，但還包含了作者多年教學(xué)和學(xué)習(xí)的經(jīng)驗(yàn)。Sedgewick的《C算法（第3版）》、《C++算法（第3版）》、《Java算法（第3版）》更適合用做參考書或是高級(jí)課程的教材，而本書則是專門為大學(xué)一、二年級(jí)學(xué)生設(shè)計(jì)的一學(xué)期教材，也是最新的基礎(chǔ)入門書或從業(yè)者的參考書。
　　致謝
　　本書的編寫花了近40年時(shí)間，因此想要一一列出所有參與人是不可能的。本書的前幾版一共列出了好幾十人，其中包括（按字母順序）Andrew Appel、Trina Avery、Marc Brown、Lyn Dupré、PhilippeFlajolet、Tom Freeman、Dave Hanson、Janet Incerpi、Mike Schidlowsky、Steve Summit和Chris VanWyk。我要感謝他們所有人，盡管其中有些人的貢獻(xiàn)要追溯到幾十年前。至于第4版，我們要感謝試用了本書樣稿的普林斯頓及其他院校的數(shù)百名學(xué)生，以及通過本書網(wǎng)站發(fā)表意見和指出錯(cuò)誤的世界各地的讀者。
　　我們還要感謝普林斯頓大學(xué)對(duì)于高質(zhì)量教學(xué)的堅(jiān)定支持，這是本書得以面世的基礎(chǔ)。Peter Gordon幾乎從本書寫作之初就提出了很多有用的建議，這一版奉行的“歸本溯源”的指導(dǎo)思想也是他最早提出的。關(guān)于第4版，我們要感謝Barbara Wood認(rèn)真又專業(yè)的編輯工作，Julie Nahil對(duì)生產(chǎn)過程的管理，以及Pearson出版公司中為本書的付梓和營(yíng)銷辛勤工作的朋友。所有人都在積極地追趕進(jìn)度，而本書的質(zhì)量并沒有受到絲毫影響。