目　　錄 第　1章 算法概述　1 1.1　算法的基礎(chǔ)　2 1.1.1　算法的特征　2 1.1.2　何為算法　2 1.2　計(jì)算機(jī)中的算法　3 1.2.1　認(rèn)識(shí)計(jì)算機(jī)中的算法　3 1.2.2　為什么說算法是程序的 靈魂　4 1.3　計(jì)算機(jī)中表示算法的方法　4 1.3.1　用流程圖表示算法　4 1.3.2　用N-S流程圖表示算法　6 1.3.3　用計(jì)算機(jī)語言表示算法　6 1.4　學(xué)習(xí)建議　6 第　2章 數(shù)據(jù)結(jié)構(gòu)　8 2.1　使用列表　9 2.1.1　列表的基本用法　9 2.1.2　刪除列表中的重復(fù)元素 并保持順序不變　10 2.1.3　找出列表中出現(xiàn)次數(shù) 最多的元素　11 2.1.4　排序類定義的實(shí)例　11 2.1.5　使用列表推導(dǎo)式　12 2.1.6　命名切片　13 2.2　使用元組　14 2.2.1　創(chuàng)建并訪問元組　14 2.2.2　修改元組　15 2.2.3　刪除元組　15 2.2.4　使用內(nèi)置方法操作元組　15 2.2.5　將序列分解為單獨(dú)的 變量　16 2.2.6　將序列分解為單獨(dú)的 變量　17 2.2.7　實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列　17 2.3　使用字典　19 2.3.1　創(chuàng)建并訪問字典　19 2.3.2　添加、修改、刪除字典 中的元素　19 2.3.3　映射多個(gè)值　20 2.3.4　使用OrderedDict創(chuàng)建 有序字典　21 2.3.5　獲取字典中的最大值和 最小值　22 2.3.6　獲取兩個(gè)字典中相同的 鍵值對(duì)　23 2.3.7　使用函數(shù)itemgetter()對(duì) 字典進(jìn)行排序　24 2.3.8　使用字典推導(dǎo)式　25 2.3.9　根據(jù)記錄進(jìn)行分組　26 2.3.10　轉(zhuǎn)換并換算數(shù)據(jù)　27 2.3.11　將多個(gè)映射合并為單個(gè) 映射　28 第3章　常用的算法思想　30 3.1　枚舉算法思想　31 3.1.1　枚舉算法基礎(chǔ)　31 3.1.2　實(shí)踐演練—24點(diǎn)游戲　31 3.1.3　實(shí)踐演練—計(jì)算 平方根　32 3.2　遞歸算法思想　32 3.2.1　遞歸算法基礎(chǔ)　33 3.2.2　實(shí)踐演練—解決“斐波 那契數(shù)列”問題　33 3.2.3　實(shí)踐演練—解決 “漢諾塔”問題　34 3.2.4　實(shí)踐演練—解決 “階乘”問題　36 3.3　分治算法思想　37 3.3.1　分治算法基礎(chǔ)　38 3.3.2　實(shí)踐演練—求順序表 中的最大值　38 3.3.3　實(shí)踐演練—判斷某個(gè) 元素是否在列表中　38 3.3.4　實(shí)踐演練—找出一組 序列中第k小的元素　39 3.4　貪心算法思想　39 3.4.1　貪心算法基礎(chǔ)　39 3.4.2　實(shí)踐演練—解決“找零” 問題　40 3.4.3　實(shí)踐演練—解決“汽車 加油”問題　41 3.5　試探算法思想　42 3.5.1　試探算法基礎(chǔ)　42 3.5.2　實(shí)踐演練—解決 “八皇后”問題　42 3.5.3　實(shí)踐演練—解決 “迷宮”問題　44 3.6　迭代算法思想　45 3.6.1　迭代算法基礎(chǔ)　46 3.6.2　實(shí)踐演練—解決“非線程 方程組”問題　46 3.7　技術(shù)解惑　47 3.7.1　衡量算法的標(biāo)準(zhǔn)是什么　47 3.7.2　遞推和遞歸有什么差異　48 3.7.3　總結(jié)分治算法能解決什么 類型的問題　48 3.7.4　分治算法的機(jī)理是什么　48 3.7.5　為什么說貪婪算法并不是 解決問題的最優(yōu)方案　48 3.7.6　回溯算法會(huì)影響算法 效率嗎　49 3.7.7　遞歸算法與迭代算法 有什么區(qū)別　49 第4章　線性表、隊(duì)列和�！�50 4.1　線性表操作　51 4.1.1　線性表的特性　51 4.1.2　順序表操作　52 4.1.3　實(shí)踐演練—實(shí)現(xiàn)線性表 順序存儲(chǔ)的插入操作　53 4.1.4　實(shí)踐演練—實(shí)現(xiàn)線性表 順序存儲(chǔ)的刪除操作　54 4.1.5　實(shí)踐演練—順序表的 插入、檢索、刪除和反轉(zhuǎn) 操作　54 4.2　鏈表操作　57 4.2.1　什么是鏈表　57 4.2.2　實(shí)踐演練—實(shí)現(xiàn)完整 鏈表操作　60 4.2.3　實(shí)踐演練—在鏈表中 增加比較功能　64 4.2.4　實(shí)踐演練—單鏈表 結(jié)構(gòu)字符串　67 4.3　先進(jìn)先出的隊(duì)列　70 4.3.1　什么是隊(duì)列　71 4.3.2　Python語言的隊(duì)列操作　72 4.3.3　實(shí)踐演練—完整的 順序隊(duì)列的操作　72 4.3.4　實(shí)踐演練—基于列表 實(shí)現(xiàn)的優(yōu)先隊(duì)列　73 4.3.5　實(shí)踐演練—基于堆 實(shí)現(xiàn)的優(yōu)先隊(duì)列　74 4.4　后進(jìn)先出的�！�75 4.4.1　什么是�！�75 4.4.2　順序�！�76 4.4.3　鏈�！�77 4.4.4　實(shí)踐演練—實(shí)現(xiàn)順序棧 操作　77 4.4.5　實(shí)踐演練—使用順序表 方法和單鏈表方法實(shí)現(xiàn)�！�78 4.5　實(shí)現(xiàn)堆隊(duì)列操作　79 4.5.1　Python中的堆操作　79 4.5.2　實(shí)踐演練—實(shí)現(xiàn)二叉 堆操作　80 4.6　技術(shù)解惑　82 4.6.1　順序表插入操作的時(shí)間 復(fù)雜度是多少　82 4.6.2　順序表刪除操作的時(shí)間 復(fù)雜度是多少　82 4.6.3　順序表按值查找操作的 時(shí)間復(fù)雜度是多少　82 4.6.4　堆和棧的區(qū)別是什么　82 第5章　樹　84 5.1　樹基礎(chǔ)　85 5.1.1　什么是樹　85 5.1.2　樹的相關(guān)概念　85 5.2　使用列表表示的樹　86 5.3　二叉樹詳解　87 5.3.1　二叉樹的定義　87 5.3.2　二叉樹的性質(zhì)　88 5.3.3　二叉樹的存儲(chǔ)結(jié)構(gòu)　88 5.3.4　實(shí)踐演練—使用嵌套 列表表示樹　90 5.3.5　實(shí)踐演練—把二叉樹的 任何子節(jié)點(diǎn)當(dāng)成二叉樹　91 5.3.6　實(shí)踐演練—實(shí)現(xiàn)二叉 搜索樹查找操作　93 5.3.7　實(shí)踐演練—實(shí)現(xiàn)二叉 搜索樹的刪除操作　97 5.3.8　遍歷二叉樹　104 5.3.9　線索二叉樹　107 5.4　霍夫曼樹　115 5.4.1　霍夫曼樹基礎(chǔ)　115 5.4.2　實(shí)踐演練—使用面向 過程方式和面向?qū)ο蠓绞?實(shí)現(xiàn)霍夫曼樹　117 5.4.3　實(shí)踐演練—實(shí)現(xiàn)霍夫曼 樹的基本操作　118 5.4.4　總結(jié)霍夫曼編碼的算法 實(shí)現(xiàn)　120 5.5　技術(shù)解惑　120 5.5.1　樹和二叉樹的差別是 什么　120 5.5.2　二叉樹和鏈表的效率 比較　121 5.5.3　如何輸出二叉樹中的 所有路徑　121 第6章　圖　122 6.1　圖的起源　123 6.2　圖的相關(guān)概念　124 6.3　存儲(chǔ)結(jié)構(gòu)　127 6.3.1　使用鄰接矩陣表示圖　127 6.3.2　實(shí)踐演練—將鄰接矩陣 輸出成圖　128 6.3.3　使用鄰接表表示圖　129 6.3.4　實(shí)踐演練—使用鄰接表 表示圖　130 6.4　圖的遍歷　131 6.4.1　深度優(yōu)先搜索　131 6.4.2　廣度優(yōu)先搜索　132 6.4.3　實(shí)踐演練—實(shí)現(xiàn)圖的深度 優(yōu)先和廣度優(yōu)先搜索　133 6.5　圖的連通性　135 6.5.1　無向圖的連通分量　135 6.5.2　實(shí)踐演練—通過二維數(shù) 組建立無向圖　136 6.5.3　實(shí)踐演練—根據(jù)鄰接 矩陣?yán)L制無向圖　137 6.5.4　最小生成樹　138 6.5.5　實(shí)踐演練—實(shí)現(xiàn)最小生 成樹和拓?fù)湫蛄小?39 6.5.6　關(guān)鍵路徑　140 6.5.7　實(shí)踐演練—遞歸解決 AOE網(wǎng)最長關(guān)鍵路徑的 問題　141 6.6　尋求最短路徑　143 6.6.1　求某一頂點(diǎn)到其他各頂點(diǎn) 的最短路徑　143 6.6.2　任意一對(duì)頂點(diǎn)間的最短 路徑　145 6.6.3　實(shí)踐演練—使用Dijkstra 算法計(jì)算指定點(diǎn)到其他 各頂點(diǎn)的路徑　146 6.6.4　實(shí)踐演練—使用Floyd- Warshall算法計(jì)算圖的 最短路徑　147 6.6.5　實(shí)踐演練—使用Bellman- Ford算法計(jì)算圖的最短 路徑　148 6.6.6　實(shí)踐演練—使用Dijkstra 算法解決加權(quán)的最短路徑 問題　149 6.7　技術(shù)解惑　150 6.7.1　幾種最短路徑算法的 比較　150 6.7.2　鄰接矩陣與鄰接表的 對(duì)比　152 6.7.3　比較深度優(yōu)先算法和 廣度優(yōu)先算法　152 第7章　查找算法　154 7.1　幾個(gè)相關(guān)概念　155 7.2　基于線性表的查找法　155 7.2.1　順序查找法　155 7.2.2　實(shí)踐演練—實(shí)現(xiàn)順序 查找算法　156 7.2.3　折半查找法　157 7.2.4　實(shí)踐演練—使用折半 查找法查找數(shù)據(jù)　158 7.2.5　插值查找法　160 7.2.6　實(shí)踐演練—使用插值 查找法查找指定的數(shù)據(jù)　160 7.2.7　分塊查找法　161 7.3　基于樹的查找法　162 7.3.1　二叉排序樹　162 7.3.2　實(shí)踐演練—實(shí)現(xiàn)二叉樹 的完整操作　165 7.3.3　平衡二叉樹　167 7.3.4　實(shí)踐演練—實(shí)現(xiàn)平衡 二叉樹的基本操作　170 7.4　散列法　174 7.4.1　散列法的基本思想　174 7.4.2　構(gòu)造散列函數(shù)　175 7.4.3　處理沖突　176 7.4.4　散列表的查找過程　177 7.4.5　實(shí)踐演練—使用散列表 查找數(shù)據(jù)　177 7.5　斐波那契查找法　178 7.5.1　斐波那契查找法介紹　178 7.5.2　實(shí)踐演練—使用斐波 那契查找法　179 7.6　高級(jí)樹表查找算法　180 7.6.1　2-3查找樹介紹　180 7.6.2　紅黑樹介紹　181 7.6.3　實(shí)踐演練—使用紅黑樹 操作數(shù)據(jù)　181 7.6.4　B樹和B+樹　185 7.6.5　實(shí)踐演練—使用B樹 排序數(shù)據(jù)　186 7.6.6　實(shí)踐演練—使用B+樹 操作數(shù)據(jù)　188 7.7　技術(shù)解惑　193 7.7.1　分析查找算法的性能　193 7.7.2　分析散列法的性能　194 第8章　內(nèi)部排序算法　195 8.1　排序基礎(chǔ)　196 8.1.1　排序的目的和過程　196 8.1.2　內(nèi)部排序與外部排序　196 8.1.3　穩(wěn)定排序與不穩(wěn)定排序　196 8.2　插入排序算法　197 8.2.1　直接插入排序　197 8.2.2　實(shí)踐演練—編寫直接 插入排序算法　198 8.2.3　實(shí)踐演練—使用折半 插入排序算法　198 8.2.4　希爾排序　199 8.2.5　實(shí)踐演練—使用希爾 排序算法對(duì)數(shù)據(jù)進(jìn)行 排序　199 8.2.6　實(shí)踐演練—使用希爾 排序處理一個(gè)列表　200 8.3　交換類排序法　201 8.3.1　冒泡排序（相鄰 比序法）　201 8.3.2　快速排序　201 8.3.3　實(shí)踐演練—實(shí)現(xiàn)從大 到小的冒泡排序　202 8.3.4　實(shí)踐演練—使用冒泡 排序算法排序　202 8.3.5　實(shí)踐演練—實(shí)現(xiàn)基本的 快速排列　203 8.4　選擇排序法　204 8.4.1　直接選擇排序　204 8.4.2　樹形選擇排序　204 8.4.3　堆排序　205 8.4.4　實(shí)踐演練—實(shí)現(xiàn)直接 選擇排序　206 8.4.5　實(shí)踐演練—演示選擇 排序的操作步驟　207 8.4.6　實(shí)踐演練—選擇排序和 Python內(nèi)置函數(shù)的效率 對(duì)比　208 8.4.7　實(shí)踐演練—使用堆排序 處理數(shù)據(jù)　209 8.4.8　實(shí)踐演練—實(shí)現(xiàn) 最小堆　210 8.5　歸并排序　211 8.5.1　歸并排序思想　211 8.5.2　兩路歸并算法的思路　212 8.5.3　實(shí)現(xiàn)歸并排序　212 8.5.4　實(shí)踐演練—使用歸并 排序處理指定列表　213 8.5.5　實(shí)踐演練—使用歸并 排序處理兩個(gè)列表　213 8.5.6　實(shí)踐演練—使用兩路 歸并排序處理一個(gè)列表　214 8.6　基數(shù)排序　215 8.6.1　多關(guān)鍵字排序　215 8.6.2　鏈?zhǔn)交鶖?shù)排序　216 8.6.3　實(shí)踐演練—使用基數(shù) 排序處理隨機(jī)數(shù)　217 8.7　技術(shù)解惑　218 8.7.1　插入排序算法的描述　218 8.7.2　希爾排序和插入排序的 速度比較　218 8.7.3　快速排序的時(shí)間耗費(fèi)　218 8.7.4　堆排序與直接選擇排序的 區(qū)別　219 8.7.5　歸并排序的效率與選擇 方法　219 8.7.6　綜合比較各種排序方法　219 第9章　經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題　221 9.1　約瑟夫環(huán)　222 9.1.1　問題描述　222 9.1.2　算法分析　222 9.1.3　具體實(shí)現(xiàn)　222 9.2　大整數(shù)運(yùn)算　224 9.2.1　模擬大整數(shù)乘法的小學(xué) 豎式計(jì)算過程　224 9.2.2　實(shí)現(xiàn)大數(shù)相加運(yùn)算　225 9.3　順序表的修改、查找、統(tǒng)計(jì)、 刪除、銷毀操作　225 9.3.1　算法分析　225 9.3.2　具體實(shí)現(xiàn)　226 9.4　實(shí)現(xiàn)鏈表的基本操作　227 9.4.1　算法分析　227 9.4.2　具體實(shí)現(xiàn)　227 9.5　帶有尾節(jié)點(diǎn)引用的單鏈表　229 9.5.1　算法分析　229 9.5.2　具體實(shí)現(xiàn)　229 9.6　增加新功能的單鏈表結(jié)構(gòu) 字符串　230 9.7　實(shí)現(xiàn)堆排序功能　232 9.7.1　算法分析　232 9.7.2　具體實(shí)現(xiàn)　233 9.8　實(shí)現(xiàn)隊(duì)列、鏈表、順序表和循環(huán) 順序表　234 9.8.1　時(shí)間復(fù)雜度分析　234 9.8.2　具體實(shí)現(xiàn)　234 9.9　基于列表實(shí)現(xiàn)二叉樹　236 9.10　實(shí)現(xiàn)二元表達(dá)式　237 9.11　使用多叉樹尋找最短路徑　239 9.11.1　算法分析　239 9.11.2　具體實(shí)現(xiàn)　239 9.12　實(shí)現(xiàn)AVL樹　240 9.13　使用二維數(shù)組生成有向圖　244 9.14　使用廣度優(yōu)先和深度優(yōu)先遍歷 二叉樹　245 第　10章 數(shù)學(xué)問題的解決　248 10.1　解決一個(gè)數(shù)學(xué)問題　249 10.1.1　問題描述　249 10.1.2　具體實(shí)現(xiàn)　249 10.2　使用遞歸算法計(jì)算兩個(gè)數(shù)的 乘積　250 10.3　利用遞歸算法獲取斐波那契數(shù) 列前n項(xiàng)的值　250 10.4　1000以內(nèi)的完全數(shù)　251 10.4.1　問題描述　251 10.4.2　算法分析　251 10.4.3　具體實(shí)現(xiàn)　252 10.5　多進(jìn)程驗(yàn)證哥德巴赫猜想　253 10.5.1　問題描述　253 10.5.2　算法分析　253 10.5.3　具體實(shí)現(xiàn)　253 10.6　最大公約數(shù)和最小公倍數(shù)　255 10.6.1　問題描述　255 10.6.2　算法分析　255 10.6.3　具體實(shí)現(xiàn)　255 10.7　親密數(shù)　255 10.7.1　問題描述　255 10.7.2　算法分析　256 10.7.3　具體實(shí)現(xiàn)　256 10.8　計(jì)算10000以內(nèi)的自守?cái)?shù)　256 10.8.1　問題描述　256 10.8.2　算法分析　256 10.8.3　具體實(shí)現(xiàn)　257 10.9　水仙花數(shù)　257 10.9.1　問題描述　257 10.9.2　算法分析　257 10.9.3　具體實(shí)現(xiàn)　257 10.10　方程求解　257 10.10.1　用高斯消元法解 方程組　258 10.10.2　用二分法解非線性 方程　260 10.11　求平方根　261 10.11.1　使用二分法求平方根　261 10.11.2　用牛頓迭代法求 平方根　262 10.12　矩陣運(yùn)算　264 10.12.1　問題描述　264 10.12.2　算法分析　264 10.12.3　具體實(shí)現(xiàn)　264 10.13　一元多項(xiàng)式運(yùn)算　265 10.13.1　一元多項(xiàng)式求導(dǎo)　266 10.13.2　實(shí)現(xiàn)多項(xiàng)式的加法、 減法、乘法運(yùn)算　266 10.14　百錢買百雞　267 10.14.1　問題描述　267 10.14.2　算法分析　268 10.14.3　具體實(shí)現(xiàn)　268 10.15　素?cái)?shù)問題　268 10.15.1　求1000以內(nèi)的所有 素?cái)?shù)　269 10.15.2　孿生素?cái)?shù)問題　269 10.15.3　金蟬素?cái)?shù)　270 10.15.4　可逆素?cái)?shù)　271 10.15.5　回文素?cái)?shù)　271 10.15.6　等差素?cái)?shù)數(shù)列　272 10.16　埃及分?jǐn)?shù)式　273 10.16.1　問題描述　273 10.16.2　算法分析　274 10.16.3　具體實(shí)現(xiàn)　274 10.17　對(duì)正整數(shù)分解質(zhì)因數(shù)　274 10.17.1　問題描述　274 10.17.2　算法分析　274 10.17.3　具體實(shí)現(xiàn)　274 第　11章 經(jīng)典算法問題的解決　276 11.1　歌星大獎(jiǎng)賽　277 11.1.1　問題描述　277 11.1.2　具體實(shí)現(xiàn)　277 11.2　借書方案　278 11.2.1　問題描述　278 11.2.2　算法分析　278 11.2.3　具體實(shí)現(xiàn)　278 11.3　捕魚和分魚　279 11.3.1　問題描述　279 11.3.2　算法分析　279 11.3.3　具體實(shí)現(xiàn)　279 11.4　出售金魚　280 11.4.1　問題描述　280 11.4.2　算法分析　280 11.4.3　具體實(shí)現(xiàn)　280 11.5　平分七筐魚　280 11.5.1　問題描述　280 11.5.2　算法分析　281 11.5.3　具體實(shí)現(xiàn)　281 11.6　繩子的長度和井深　281 11.6.1　問題描述　281 11.6.2　算法分析　282 11.6.3　具體實(shí)現(xiàn)　282 11.7　雞兔同籠　282 11.7.1　問題描述　282 11.7.2　算法分析　283 11.7.3　具體實(shí)現(xiàn)　283 11.8　漢諾塔　283 11.8.1　問題描述　283 11.8.2　算法分析　284 11.8.3　具體實(shí)現(xiàn)　284 11.9　馬踏棋盤　285 11.9.1　使用遞歸法　285 11.9.2　貪婪、遞歸、迭代三種 算法的對(duì)比　287 11.10　三色球問題　289 11.10.1　問題描述　289 11.10.2　算法分析　289 11.10.3　具體實(shí)現(xiàn)　289 11.11　計(jì)算年齡　290 11.11.1　問題描述　290 11.12.2　算法分析　290 11.11.3　具體實(shí)現(xiàn)　290 11.12　奇數(shù)幻方問題　291 11.12.1　問題描述　291 11.12.2　具體實(shí)現(xiàn)　291 11.13　常勝將軍問題　291 11.13.1　問題描述　291 11.13.2　算法分析　292 11.13.3　具體實(shí)現(xiàn)　292 11.14　背包問題　292 11.14.1　使用動(dòng)態(tài)規(guī)劃法解決 “背包”問題　292 11.14.2　使用遞歸法解決“背包” 問題　293 11.15　野人與傳教士問題　295 11.15.1　問題描述　295 11.15.2　算法分析　295 11.15.3　具體實(shí)現(xiàn)　295 11.16　三色旗問題　296 11.16.1　問題描述　296 11.16.2　算法分析　296 11.16.3　具體實(shí)現(xiàn)　297 11.17　猴子分桃　297 11.17.1　問題描述　297 11.17.2　算法分析　298 11.17.3　具體實(shí)現(xiàn)　298 11.18　將老師隨機(jī)分配到辦公室　298 11.18.1　問題描述　298 11.18.2　具體實(shí)現(xiàn)　299 11.19　龍的世界　300 11.19.1　問題描述　300 11.19.2　具體實(shí)現(xiàn)　300 11.20　凱撒密碼游戲　301 11.20.1　問題描述　301 11.20.2　算法分析　301 11.20.3　具體實(shí)現(xiàn)　301 第　12章 圖像問題　303 12.1　生命游戲　304 12.1.1　問題描述　304 12.1.2　算法分析　304 12.1.3　具體實(shí)現(xiàn)　304 12.2　黑白棋問題　306 12.2.1　問題描述　306 12.2.2　算法分析　307 12.2.3　具體實(shí)現(xiàn)　307 12.3　馬踏棋盤（騎士周游問題）　311 12.3.1　問題描述　311 12.3.2　算法分析　311 12.3.3　具體實(shí)現(xiàn)　311 12.4　井字棋問題　313 12.4.1　問題描述　313 12.4.2　算法分析　313 12.4.3　具體實(shí)現(xiàn)　313 12.5　用蒙特卡羅方法驗(yàn)證凱利 公式　317 12.5.1　問題描述　317 12.5.2　算法分析　317 12.5.3　具體實(shí)現(xiàn)　317 12.6　繪制Hangman游戲　319 12.6.1　問題描述　319 12.6.2　算法分析　319 12.6.3　具體實(shí)現(xiàn)　320 第　13章 游戲和算法　324 13.1　開發(fā)一個(gè)俄羅斯方塊游戲　325 13.1.1　規(guī)劃圖形　325 13.1.2　具體實(shí)現(xiàn)　325 13.2　跑酷游戲　332 13.3　水果連連看游戲　337 13.4　AI智能貪吃蛇游戲　341 13.5　AI智能五子棋游戲　346