內容簡介

　　本書全麵係統地介紹算法設計和算法應用的各個領域，內容涵蓋經典數據結構、經典算法、算法分析方法、算法設計方法以及算法在各個領域的應用，還包含一些高級主題。本書采用應用驅動的方法引入各章內容，內容編排清晰閤理，講解由淺入深。此外，各章都附有鞏固練習、創新練習和應用練習三種類型的題目，為讀者理解和掌握算法設計和應用提供瞭很好的素材。

目錄

齣版者的話
譯者序
前言
第1章算法分析
1.1分析算法
1.1.1僞代碼
1.1.2隨機存取機模型
1.1.3基本操作數目的計算
1.1.4遞歸算法的分析
1.1.5漸近錶示法
1.1.6漸近錶示法的重要性
1.2相關數學知識復習
1.2.1求和
1.2.2對數和冪
1.2.3簡單的證明技術
1.2.4概率基礎
1.3算法分析案例
1.3.1最大子數組問題的第一個解
1.3.2一種改進的求最大子數組算法
1.3.3綫性時間的最大子數組算法
1.4平攤分析
1.4.1平攤技術
1.4.2對一個可擴展數組實現的分析
1.5練習
本章注記
第一部分數據結構
第2章基本數據結構
2.1棧和隊列
2.1.1棧
2.1.2隊列
2.2列錶
2.2.1基於索引的列錶
2.2.2鏈錶
2.3樹
2.3.1樹的定義
2.3.2樹的遍曆
2.3.3二叉樹
2.3.4錶示樹的數據結構
2.4練習
本章注記
第3章二叉搜索樹
3.1搜索和更新
3.1.1二叉搜索樹的定義
3.1.2二叉搜索樹中的搜索
3.1.3二叉搜索樹中的插入
3.1.4二叉搜索樹中的刪除
3.1.5二叉搜索樹的性能
3.2範圍查詢
3.3基於索引的搜索
3.4隨機構造二叉搜索樹
3.5練習
本章注記
第4章平衡二叉搜索樹
4.1秩和鏇轉
4.2AVL樹
4.3紅黑樹
4.4弱AVL樹
4.5伸展樹
4.6練習
本章注記
第5章優先隊列和堆
5.1優先隊列
5.2PQ排序、選擇排序和插入排序
5.2.1選擇排序
5.2.2插入排序
5.3堆
5.3.1基於數組結構的二叉樹
5.3.2堆中的插入
5.3.3堆中的刪除
5.4堆排序
5.5擴展優先隊列
5.6練習
本章注記
第6章散列錶
6.1映射
6.1.1映射的定義
6.1.2查找錶
6.2散列函數
6.2.1分量求和
6.2.2多項式求值函數
6.2.3基於錶格的散列
6.2.4取模
6.2.5隨機綫性和多項式函數
6.3碰撞處理與再散列
6.3.1拉鏈法
6.3.2開放尋址法
6.3.3綫性探測
6.3.4平方探測
6.3.5雙重散列
6.3.6再散列
6.4布榖鳥散列
6.5通用散列
6.6練習
本章注記
第7章並查集結構
7.1並查集及其應用
7.1.1連通分支
7.1.2迷宮建築和滲透理論
7.2基於列錶的實現
7.3基於樹的實現
7.4練習
本章注記
第二部分排序和選擇
第8章歸並排序和快速排序
8.1歸並排序
8.1.1分而治之
8.1.2歸並排序和遞推方程
8.2快速排序
8.2.1隨機快速排序
8.2.2原地快速排序
8.3基於比較的排序的下界
8.4練習
本章注記
第9章快速排序和選擇
9.1桶排序和基數排序
9.1.1桶排序
9.1.2基數排序
9.2選擇
9.2.1隨機快速選擇
9.2.2確定性選擇
9.3加權中位數
9.4練習
本章注記
第三部分基本技術
第10章貪心法
10.1分份背包問題
10.2任務調度
10.3文本壓縮和哈夫曼編碼
10.4練習
本章注記
第11章分治法
11.1遞推與主定理
11.2整數乘法
11.3矩陣乘法
11.4極大點集問題
11.5練習
本章注記
第12章動態規劃
12.1矩陣連乘
12.2通用技術
12.3望遠鏡調度
12.4博弈策略
12.4.1硬幣行
12.4.2概率博弈策略與逆嚮歸納法
12.5最長公共子序列問題
12.5.1問題定義
12.5.2應用動態規劃解LCS問題
12.60-1背包問題
12.7練習
本章注記
第13章圖及遍曆
13.1圖的術語和錶示方法
13.1.1圖的一些術語
13.1.2圖的操作
13.1.3錶示圖的數據結構
13.2深度優先搜索
13.3廣度優先搜索
13.4有嚮圖
13.4.1遍曆有嚮圖
13.4.2傳遞閉包
13.4.3有嚮DFS和垃圾迴收
13.4.4有嚮無環圖
13.5雙連通分量
13.6練習
本章注記
第四部分圖算法
第14章最短路徑
14.1單源最短路徑
14.2Dijkstra算法
14.3Bellman�睩ord 算法
14.4有嚮無環圖中的最短路徑
14.5所有頂點對之間的最短路徑
14.5.1動態規劃最短路徑算法
14.5.2通過矩陣乘法計算最短路徑
14.6練習
本章注記
第15章最小生成樹
15.1最小生成樹的性質
15.2Kruskal算法
15.3Prim�睯arník算法
15.4Baru�畍ka算法
15.5練習
本章注記
第16章網絡流和匹配
16.1流與割
16.1.1割
16.1.2剩餘容量和增流路徑
16.2最大流算法
16.2.1Ford�睩ulkerson算法
16.2.2Edmonds�睰arp算法
16.3最大二分圖匹配
16.4棒球賽的淘汰
16.5最低成本流
16.6練習
本章注記
第五部分計算睏難問題
第17章NP完全性
17.1P和NP
17.1.1定義復雜類P和NP
17.1.2一些有趣的NP問題
17.2NP完全性
17.2.1多項式時間歸約和NP難度
17.2.2Cook�睱evin 定理
17.2.3如何證明一個問題是NP完全問題
17.3閤取範式可滿足問題和3可滿足問題
17.4頂點覆蓋、團和集閤覆蓋
17.5子集和與背包問題
17.6哈密頓迴路和TSP
17.7練習
本章注記
第18章近似算法
18.1幾何旅行商問題
18.1.1Metric�睺SP的一個2近似算法
18.1.2Christofides近似算法
18.2覆蓋問題的近似
18.2.1頂點覆蓋的2近似算法
18.2.2集閤覆蓋的對數近似
18.3多項式時間近似方法
18.4迴溯和分支定界
18.4.1迴溯法
18.4.2分支定界法
18.5練習
本章注記
第六部分高級主題
第19章隨機算法
19.1隨機排列的生成
19.2穩定婚姻和優惠券收集
19.2.1優惠券收集問題分析
19.2.2穩定婚姻問題
19.3最小割
19.3.1收縮邊
19.3.2計算最小割
19.3.3更快的算法
19.4尋找素數
19.5切爾諾夫界
19.5.1馬爾可夫不等式
19.5.2示性隨機變量之和
......

前言/序言

　　本書全麵地介紹瞭計算機算法和數據結構的設計和分析。書中各章相對獨立，所以教師和讀者可以自由選擇感興趣的章節。此外，本書內容廣泛，既包含瞭經典的算法，也包含瞭新興的算法，具體如下：
　　�r 漸近分析數學，包括平攤和隨機化。
　　�r 通用算法設計技術，包括貪心法、分治法和動態規劃。
　　�r 數據結構，包括列錶、樹、堆、搜索樹、B樹、哈希錶、跳躍錶、並查集結構和多維樹。
　　�r 算法框架，包括NP完全性、近似算法和外存算法。
　　�r 基本算法，包括排序、圖算法、計算幾何、數值算法、密碼、快速傅裏葉變換（FFT）和綫性規劃。
　　應用驅動方法　　計算機科學已經進入一個令人興奮的時代。計算機已經從早期的計算引擎發展到現在的信息處理器，其應用遍布各個領域。此外，互聯網的擴展推動瞭計算機在社會和商業中的新範式和新模式。例如，計算機可以用來存儲和檢索大規模數據，並且用於許多其他的應用領域，如運動、視頻遊戲、生物、製藥、社交網絡、工程和科學。因此，我們認為算法的講授既要強調其數學分析，也要突齣其實際應用。
　　為瞭達到這個目的，每章開篇都有該章主題應用的一個簡短討論。這些應用有的來自於主題的實際應用，有的是設想該章主題在實踐中的可能應用。這些討論的意圖是為讀者閱讀各章時提供一定的背景和實際應用動機。除瞭這些應用的動機外，我們還給齣算法的詳細僞代碼描述和完整的數學分析。事實上，我們認為數學的嚴謹性有其實際的意義。
　　寫給教師　　本書的結構便於教師自由地選擇和講授內容。各章節之間的依存度已經降至很低，以便教師可以按照自己喜歡的順序授課。此外，依據內容的深度，每章的講授時間在1～3節課。
　　課程樣例　　本書可作為多個課程的教材。例如，可用於算法核心課程的教材，即經典CS7。另外，本書也可以用於高年級本科生或者研究生的數據結構課程、算法課程，或者兩學期連續教授這兩個課程的教材。為瞭突齣這些選擇，下麵為這些可能的課程給齣教學大綱樣例。
　　算法核心課程（CS7）大綱樣例　　第1章算法分析　　（跳讀、略讀或復習第2～4章的基本數據結構）　　�…� 這些內容以及第5章和第6章是數據結構課程的基本內容，也是本課程的先行課。
　　第5章優先隊列和堆　　第6章散列錶　　第7章並查集結構.　　第8章歸並排序和快速排序　　第9章快速排序和選擇（如果時間允許）　　第10章貪心法　　第11章分治法　　第12章動態規劃　　第13章圖及遍曆　　第14章最短路徑　　第15章最小生成樹　　第16章網絡流和匹配（如果時間允許）　　第17章NP完全性　　第18章近似算法　　如果時間允許，可從第19～26章中選擇內容，包括隨機算法、計算幾何、字符串算法、密碼學、快速傅裏葉變換（FFT）和綫性規劃。
　　高年級本科生或者研究生的數據結構課程大綱樣例　　第1章算法分析　　第2章基本數據結構　　第3章二叉搜索樹　　第4章平衡二叉搜索樹　　第5章優先隊列和堆　　第6章散列錶　　第7章並查集結構　　第8章歸並排序和快速排序　　第13章圖及遍曆　　第14章最短路徑　　第15章最小生成樹　　第20章B樹和外部存儲器　　第21章多維搜索　　高年級本科生或者研究生的算法課程大綱樣例　　（跳讀、略讀或者復習第1～8章）　　第9章快速排序和選擇　　第10章貪心法　　第11章分治法　　第12章動態規劃　　第16章網絡流和匹配　　第17章NP完全性　　第18章近似算法　　第19章隨機算法　　第22章計算幾何　　第23章字符串算法　　第24章密碼學　　第25章快速傅裏葉變換　　第26章綫性規劃　　這門課程既可以作為一門獨立的課程講授，也可與上麵的高級數據結構課程聯閤講授。當然，還有其他的選擇，在此不再贅述，將這些內容的創意安排留給教師。
　　三類練習　　本書包含瞭800多個練習，分為三類：
　　�r 鞏固練習，測試對章節內容的理解。
　　�r 創新練習，測試能否創造性地利用各章的技術方法。
　　�r 應用練習，測試能否將各章內容應用於實際問題或者設想的問題。
　　這些練習的分布大緻為鞏固練習占35%，創新練習占40%，應用練習占25%。
　　網絡增值學習　　本書有一個網站：
　　�眞iley�眂om/college/goodrich/　　這個網站包含瞭章節內容的附加學習資源，特彆為學生提供瞭以下內容：
　　�r 本書大部分內容的PDF演示講義。
　　�r 某些練習的提示。
　　對於一些學生來說，有些創新練習和應用練習可能具有挑戰性，因此他們會對這些提示感興趣。
　　我們也為使用本書作為教材的教師提供瞭一個教學支持網站，包括下列輔助資源:��
　　關於本書教輔資源，隻有使用本書作為教材的教師纔可以申請，需要的教師可嚮約翰·威立齣版公司北京代錶處申請。　　�r
　　本書一些練習的解。
　　�r 本書大部分內容的可編輯PowerPoint演示文稿。
　　預備知識
　　本書假定讀者具有一定的預備知識。特彆是，假定讀者有基本的數據結