算法設計與分析-C++語言描述(第3版) 算法设计与分析-C++语言描述(第3版)

本書為普通高等教育“十一五”規劃教材。 本書內容分為3部分：算法和算法分析、算法設計策略、求解困難問題。第1部分介紹問題求解方法、算法復雜度和分析、遞歸算法和遞推關系；第2部分討論常用的算法設計策略：基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法；第3部分介紹NP完全問題、隨機算法、近似算法、遺傳算法和密碼算法，其中遺傳算法是本次修訂新增的內容。書中還介紹了兩種新的數據結構：跳錶和伸展樹，以及它們特定的算法分析方法，並對現代密碼學做了簡要論述。

教授，南京郵電大學計算機學院，主持了多項信息產業部基金項目的研究工作，並負責了多項企業辦公自動化和信息管理網絡系統的研製開發。出版多本教材。
曾獲江蘇省普通高校教學成果三等獎，其主持的《數據結構》課程獲江蘇省高校一類優秀課程。

第1部分算法和算法分析

第1章算法問題求解基礎1 
1.1算法概述1 
1.1.1什麼是算法1 
1.1.2為什麼學習算法3 
1.2問題求解方法3 
1.2.1問題和問題求解4 
1.2.2問題求解過程4 
1.2.3系統生命週期5 
1.3算法設計與分析5 
1.3.1算法問題求解過程5 
1.3.2如何設計算法6 
1.3.3如何表示算法6 
1.3.4如何確認算法6 
1.3.5如何分析算法7 
1.4遞歸和歸納7 
1.4.1遞歸7 
1.4.2遞歸算法示例9 
1.4.3歸納證明11 
本章小結12 
習題1 13 

第2章算法分析基礎14 
2.1算法複雜度14 
2.1.1什麼是好的算法14 
2.1.2影響程序運行時間的因素15 
2.1.3算法的時間複雜度16 
2.1.4使用程序步分析算法17 
2.1.5算法的空間複雜度18 
2.2漸近表示法19 
2.2.1大O記號19
2.2.2 ?記號20 
2.2.3 ?記號21 
2.2.4小o記號21 
2.2.5算法按時間複雜度分類21 
2.3遞推關係22 
2.3.1遞推方程22 
2.3.2替換方法23 
2.3.3迭代方法23 
2.3.4主方法24 
2.4分攤分析25 
2.4.1聚集方法26 
2.4.2會計方法26 
2.4.3勢能方法27 
本章小結28 
習題2 28 

第3章伸展樹與跳表30 
3.1伸展樹30 
3.1.1二叉搜索樹30 
3.1.2自調節樹和伸展樹30 
3.1.3伸展操作31 
3.1.4伸展樹類32 
3.1.5旋轉的實現34 
3.1.6插入運算的實現34 
3.1.7分攤分析36 
3.2跳表38 
3.2.1什麼是跳表38 
3.2.2跳表類39 
3.2.3級數分配41 
3.2.4插入運算的實現42 
3.2.5性能分析43 
本章小結44 
習題3 44 

第2部分算法設計策略

第4章基本搜索和遍歷方法45 
4.1基本概念45 
4.2圖的搜索和遍歷46 
4.2.1搜索方法46 
4.2.2鄰接表類47 
4.2.3廣度優先搜索48 
4.2.4深度優先搜索50 
4.3雙連通分量53 
4.3.1基本概念53 
4.3.2發現關節點54 
4.3.3構造雙連通圖57 
4.4與或圖58 
4.4.1問題分解58 
4.4.2判斷與或樹是否可解59 
4.4.3構建解樹61 
本章小結62 
習題4 62 

第5章分治法64 
5.1一般方法64 
5.1.1分治法的基本思想64 
5.1.2算法分析65 
5.1.3數據結構66 
5.2求最大最小元67 
5.2.1分治法求解67 
5.2.2時間分析68 
5.3二分搜索69 
5.3.1分治法求解69 
5.3.2對半搜索70 
5.3.3二叉判定樹71 
5.3.4搜索算法的時間下界73 
5.4排序問題74 
5.4.1合併排序74 
5.4.2快速排序76
5.4.3排序算法的時間下界80 
5.5選擇問題82 
5.5.1分治法求解82 
5.5.2隨機選擇主元82 
5.5.3線性時間選擇算法84 
5.5.4時間分析86 
5.5.5允許重複元素的選擇算法86 
5.6斯特拉森矩陣乘法87 
5.6.1分治法求解87 
5.6.2斯特拉森分治法88 
本章小結88 
習題5 88 

第6章貪心法91 
6.1一般方法91 
6.2背包問題92 
6.2.1問題描述92 
6.2.2貪心法求解92 
6.2.3算法正確性94 
6.3帶時限的作業排序95 
6.3.1問題描述95 
6.3.2貪心法求解95 
6.3.3算法正確性97 
6.3.4可行性判定97 
6.3.5作業排序貪心算法98 
6.3.6一種改進算法99 
6.4最佳合併模式102 
6.4.1問題描述102 
6.4.2貪心法求解103 
6.4.3算法正確性104 
6.5最小代價生成樹105 
6.5.1問題描述105 
6.5.2貪心法求解105
6.5.3普里姆算法106 
6.5.4克魯斯卡爾算法109 
6.5.5算法正確性111 
6.6單源最短路徑111 
6.6.1問題描述112 
6.6.2貪心法求解112 
6.6.3迪傑斯特拉算法112 
6.6.4算法正確性115 
6.7磁帶最優存儲116 
6.7.1單帶最優存儲116 
6.7.2多帶最優存儲117 
6.8貪心法的基本要素119 
6.8.1最優量度標準119 
6.8 .2最優子結構119 
本章小結120 
習題6 120 

第7章動態規劃法122 
7.1一般方法和基本要素122 
7.1.1一般方法122 
7.1.2基本要素123 
7.1.3多段圖問題123 
7.1.4資源分配問題126 
7.1.5關鍵路徑問題127 
7.2每對結點間的最短路徑129 
7.2.1問題描述129 
7.2.2動態規劃法求解130 
7.2.3弗洛伊德算法131 
7.2.4算法正確性132 
7.3矩陣連乘132 
7.3.1問題描述132
7.3.2動態規劃法求解133 
7.3.3矩陣連乘算法134 
7.3.4備忘錄方法136 
7.4最長公共子序列137 
7.4.1問題描述137 
7.4.2動態規劃法求解137 
7.4.3最長公共子序列算法138 
7.4.4算法的改進140 
7.5最優二叉搜索樹140 
7.5.1問題描述140 
7.5.2動態規劃法求解141 
7.5.3最優二叉搜索樹算法143 
7.6 0/1背包144 
7.6 .1問題描述144 
7.6.2動態規劃法求解145 
7.6.3 0/1背包算法框架147 
7.6.4 0/1背包算法150 
7.6.5性能分析152 
7.6.6使用啟發式方法153 
7.7流水作業調度154 
7.7.1問題描述154 
7.7.2動態規劃法求解155 
7.7.3 Johnson算法157 
本章小結158 
習題7 158 

第8章回溯法160 
8.1一般方法160 
8.1.1基本概念160 
8.1.2剪枝函數和回溯法161 
8.1.3回溯法的效率分析163
8.2 n-皇后163 
8.2.1問題描述163 
8.2.2回溯法求解164 
8.2.3 n-皇后算法165 
8.2.4時間分析166 
8.3子集和數167 
8.3.1問題描述167 
8.3.2回溯法求解167 
8.3.3子集和數算法168 
8.4圖的著色170 
8.4.1問題描述170 
8.4.2回溯法求解170 
8.4.3圖著色算法171 
8.4.4時間分析172 
8.5哈密頓環172 
8.5.1問題描述172 
8.5.2哈密頓環算法173 
8.6 0/1背包174 
8.6.1問題描述174 
8.6.2回溯法求解174 
8.6.3限界函數175 
8.6.4 0/1背包算法176 
8.7批處理作業調度178 
8.7.1問題描述178 
8.7.2回溯法求解178 
8.7.3批處理作業調度算法178 
本章小結180 
習題8 180 

第9章分枝限界法182 
9.1一般方法182 
9.1.1分枝限界法概述182
9.1.2 LC分枝限界法184 
9.1.3 15謎問題185 
9.2求最優解的分枝限界法187 
9.2.1上下界函數187 
9.2.2 FIFO分枝限界法188 
9.2.3 LC分枝限界法189 
9.3帶時限的作業排序190 
9.3.1問題描述190 
9.3.2分枝限界法求解190 
9.3.3帶時限作業排序算法191 
9.4 0/1背包193 
9.4.1問題描述193 
9.4.2分枝限界法求解194 
9.4.3 0/1背包算法195 
9.5旅行商問題197 
9.5.1問題描述197 
9.5.2分枝限界法求解198 
9.6批處理作業調度201 
9.6.1問題描述201 
9.6.2分枝限界法求解201 
9.6.3批處理作業調度算法202 
本章小結205 
習題9 205 

第3部分求解困難問題

第10章NP完全問題207 
10.1基本概念207 
10.1.1不確定算法和不確定機208 
10.1.2可滿足性問題210 
10.1.3 P類和NP類問題211 
10.1.4 NP難度和NP完全問題211
10.2 Cook定理和證明212 
10.2.1 Cook定理212 
10.2.2簡化的不確定機模型212 
10.2.3證明Cook定理214 
10.3一些典型的NP完全問題217 
10.3.1最大集團217