算法零基礎(chǔ)一本通（Python版）

目 錄 
第 1 章 算法基本概念 
1-1 計(jì)算機(jī)的算法................................2 
1-2 不好的算法與好的算法...................3 
1-2-1　不好的算法 ....................................... 3 
1-2-2　好的算法 ........................................... 7 
1-3　程序執(zhí)行的時(shí)間測(cè)量方法 ：時(shí)間 
　　 復(fù)雜度.........................................8 
1-3-1　基本概念 ........................................ 8 
1-3-2　時(shí)間測(cè)量復(fù)雜度 ............................... 9 
1-4 內(nèi)存的使用 ：空間復(fù)雜度..............12 
1-4-1　基本概念 ......................................... 12 
1-4-2　常見(jiàn)的空間復(fù)雜度計(jì)算 ................. 14 
1-5 數(shù)據(jù)結(jié)構(gòu)....................................16 
1-6　習(xí)題..........................................16 
第 2 章 數(shù)組 
2-1　基本概念....................................20 
2-2　使用索引存取數(shù)組內(nèi)容.................20 
2-3　新數(shù)據(jù)插入數(shù)組...........................20 
2-3-1　假設(shè)當(dāng)下有足夠的連續(xù)內(nèi)存 
　　　 空間 ................................................ 21 
2-3-2　假設(shè)當(dāng)下沒(méi)有足夠的連續(xù)內(nèi)存 
　　　 空間 ................................................ 22 
2-4　刪除數(shù)組元素..............................22 
2-5　思考數(shù)組的優(yōu)缺點(diǎn)........................23 
2-6　與數(shù)組有關(guān)的 Python 程序...........24 
2-6-1　建立數(shù)組 ......................................... 25 
2-6-2　存取數(shù)組內(nèi)容 ................................. 25 
2-6-3　將數(shù)據(jù)插入數(shù)組 ............................. 26 
2-6-4　刪除數(shù)組元素 ................................. 27 
2-6-5　搜尋數(shù)組元素 ................................. 28 
2-6-6　更新數(shù)組內(nèi)容 ................................. 28 
2-6-7　Numpy ............................................. 28 
2-7　習(xí)題..........................................29 
第 3 章 鏈表 
3-1　鏈表數(shù)據(jù)形式與內(nèi)存概念..............32 
3-2　鏈表的數(shù)據(jù)讀取...........................32 
3-3　新數(shù)據(jù)插入鏈表...........................33 
3-4　刪除鏈表的節(jié)點(diǎn)元素....................34 
3-5　循環(huán)鏈表 (circle linked list)..........34 
3-6　雙向鏈表....................................34 
3-7　數(shù)組與鏈表基本操作的時(shí)間復(fù)雜度 
　　　比較..........................................34 
3-8　與鏈表有關(guān)的 Python 程序...........35 
3-8-1　建立鏈表 ......................................... 35 
3-8-2　建立鏈表類(lèi)別和遍歷此鏈表 .......... 36 
3-8-3　在鏈表個(gè)節(jié)點(diǎn)前插入一個(gè) 
　　　 新的節(jié)點(diǎn)......................................... 37 
3-8-4　在鏈表末端插入新的節(jié)點(diǎn) .............. 39 
3-8-5　在鏈表中間插入新的節(jié)點(diǎn) .............. 40 
3-8-6　在鏈表中刪除指定內(nèi)容的節(jié)點(diǎn) ...... 42 
3-8-7　建立循環(huán)鏈表 ................................. 43 
3-8-8　雙向鏈表 ......................................... 44 
3-9　習(xí)題..........................................47 
第 4 章 隊(duì)列 
4-1　數(shù)據(jù)插入 enqueue......................50 
4-2　數(shù)據(jù)讀取 dequeue......................51 
4-3　使用列表模仿隊(duì)列的操作..............51 
4-4　與隊(duì)列有關(guān)的 Python 模塊...........53 
4-5　習(xí)題..........................................54 
第 5 章 棧 
5-1　數(shù)據(jù)推入 push............................56 
5-2　數(shù)據(jù)取出 pop..............................57 
5-3　Python 中棧的應(yīng)用......................58 
5-3-1　使用列表 (list) 模擬棧操作 ............ 58 
5-3-2　自行建立 stack 類(lèi)別執(zhí)行相關(guān) 
　　　 操作 ................................................ 59 
5-4　函數(shù)調(diào)用與棧運(yùn)作?.......................61
5-5　遞歸調(diào)用與棧運(yùn)作?.......................62
5-6　習(xí)題?.........................................66
第 6 章?二叉樹(shù)
6-1　建立二叉樹(shù)?................................68
6-2　刪除二叉樹(shù)的節(jié)點(diǎn)?.......................70
6-3　搜尋二叉樹(shù)的數(shù)據(jù)?.......................72
6-4　更進(jìn)一步認(rèn)識(shí)二叉樹(shù)?...................74
6-5　內(nèi)存存儲(chǔ)二叉樹(shù)的方法?................75
6-6　Python 中二叉樹(shù)的運(yùn)用?..............77
6-6-1　使用數(shù)組建立二叉樹(shù) .....................77
6-6-2　鏈表方式建立二叉樹(shù)的根節(jié)點(diǎn) ......79
6-6-3　使用鏈表建立二叉樹(shù) .....................80
6-6-4　遍歷二叉樹(shù)使用中序 (inorder)
　　　打印 ................................................80
6-6-5　遍歷二叉樹(shù)使用前序 (preorder)
　　　打印 ................................................85
6-6-6　遍歷二叉樹(shù)使用后序 (postorder)
　　　打印 ................................................89
6-6-7　二叉樹(shù)節(jié)點(diǎn)的搜尋 .........................94
6-6-8　二叉樹(shù)節(jié)點(diǎn)的刪除 .........................96
6-6-9　二叉樹(shù)的應(yīng)用與工作效率 ..............98
6-7　習(xí)題?.........................................98
第 7 章?堆積樹(shù)
7-1　建立堆積樹(shù)?..............................102
7-2　插入數(shù)據(jù)到堆積樹(shù)?.....................103
7-3　取出小堆積樹(shù)的值?.................105
7-4　小堆積樹(shù)與數(shù)組?.....................106
7-5　Python 內(nèi)建堆積樹(shù)模塊 heapq?..107
7-5-1　建立二叉堆積樹(shù) heapify( ) ...........107
7-5-2　推入元素到堆積 heappush( ) ........ 108
7-5-3　從堆積取出和刪除元素
　　　heappop( ) ..................................... 109
7-5-4　推入和取出 heappushpop( ) .......... 110
7-5-5　傳回或是小的 n 個(gè)元素 .... 110
7-5-6　取出堆積的小值和插入新元素 .111
7-5-7　堆積的元素是元組 (tuple) .............111
7-5-8　二叉堆積樹(shù)排序的應(yīng)用 ............... 112
7-6　Python 硬功夫 ：自己建立
　　???堆積樹(shù)?....................................113
7-6-1　自己建立堆積樹(shù) ........................... 113
7-6-2　自己建立方法取出堆積樹(shù)的
　　　小值 .......................................... 114
7-6-3　插入節(jié)點(diǎn) ....................................... 115
7-7　習(xí)題?.......................................115
第 8 章?哈希表
8-1　基本概念?.................................118
8-2　哈希表轉(zhuǎn)成數(shù)組?........................119
8-2-1　哈希表寫(xiě)入 ................................... 119
8-2-2　哈希碰撞與鏈結(jié)法 ....................... 121
8-2-3　哈希碰撞與開(kāi)放尋址法 ............... 122
8-3　搜尋哈希表?..............................122
8-4　哈希表的規(guī)模與擴(kuò)充?.................124
8-5　好的哈希表與不好的哈希表?........125
8-6　哈希表效能分析?........................126
8-7　Python 程序應(yīng)用?......................126
8-7-1　Python 建立哈希表 ....................... 127
8-7-2　建立電話號(hào)碼簿 ........................... 127
8-7-3　避免數(shù)據(jù)重復(fù) ............................... 128
8-8　認(rèn)識(shí)哈希表模塊 hashlib?............129
8-8-1　使用 md5( ) 方法計(jì)算中文 / 英文
　　　數(shù)據(jù)的哈希值 ............................... 130
8-8-2　計(jì)算文件的哈希值 ....................... 131
8-8-3　使用 sha1( ) 方法計(jì)算哈希值 ....... 132
8-8-4　認(rèn)識(shí)此平臺(tái)可以使用的哈希
　　　算法 .............................................. 132
8-8-5　認(rèn)識(shí)跨平臺(tái)可以使用的哈希
　　　算法 .............................................. 133
8-9　習(xí)題?.......................................133
第 9 章?排序
9-1　排序的概念與應(yīng)用?.....................136
9-2　泡沫排序法 (bubble?sort)?..........137
9-2-1　圖解泡沫排序算法 .................... 137
9-2-2　Python 程序?qū)嵗?........................... 140
9-3　雞尾酒排序 (cocktail?sort)?.........142
9-3-1　圖解雞尾酒排序算法 ................... 142
9-3-2　Python 程序?qū)嵗?........................... 144
9-4　選擇排序 (selection?sort)?..........145
9-4-1　圖解選擇排序算法 ....................... 145
9-4-2　Python 程序?qū)嵗?........................... 147
9-4-3　選擇排序的應(yīng)用 ........................... 148
9-5　插入排序 (insertion?sort)?..........149
9-5-1　圖解插入排序算法 ....................... 149
9-5-2　插入排序與玩撲克牌 ................... 151
9-5-3　Python 程序?qū)嵗?........................... 151
9-6　堆積樹(shù)排序 (heap?sort).............152
9-6-1　圖解堆積樹(shù)排序算法 ................... 152
9-6-2　Python 程序?qū)嵗?........................... 154
9-7　快速排序 (quick?sort)?...............157
9-7-1　圖解快速排序算法 ....................... 157
9-7-2　Python 程序?qū)嵗?........................... 159
9-8　合并排序 (merge?sort)?.............159
9-8-1　圖解合并排序算法 ....................... 159
9-8-2　Python 程序?qū)嵗?........................... 163
9-9　習(xí)題?.......................................164
第 10 章?數(shù)據(jù)搜尋
10-1　順序搜尋法
　　　(sequential?search)?..............168
10-1-1　圖解順序搜尋算法 ..................... 168
10-1-2　Python 程序?qū)嵗?......................... 168
10-2　二分搜尋法 (binary?search)?....169
10-2-1　圖解二分搜尋法 ......................... 169
10-2-2　Python 程序?qū)嵗?......................... 170
10-3　搜尋值算法?......................171
10-4　習(xí)題?.....................................171
第 11 章?棧、回溯算法與迷宮
11-1　走迷宮與回溯算法?...................174
11-2　迷宮設(shè)計(jì)棧扮演的角色?............177
11-3　Python 程序走迷宮?.................177
11-4　習(xí)題?.....................................180
第 12 章?從遞歸看經(jīng)典算法
12-1　斐波那契 (Fibonacci) 數(shù)列?......184
12-2　河內(nèi)塔算法?............................185
12-2-1　了解河內(nèi)塔問(wèn)題 ......................... 185
12-2-2　手動(dòng)實(shí)踐河內(nèi)塔問(wèn)題 ................. 187
12-2-3　Python 程序?qū)嵺`河內(nèi)塔問(wèn)題 ..... 191
12-3　八皇后算法?............................193
12-3-1　了解八皇后的題目 ..................... 193
12-3-2　回溯算法與八皇后 ..................... 194
12-3-3　遞歸的解法 ................................. 196
12-4　分形與 VLSI 設(shè)計(jì)算法?.............197
12-4-1　算法基本概念 ............................. 197
12-4-2　Python 程序?qū)嵗?......................... 199
12-5　習(xí)題......................................200
第 13 章?圖形理論
13-1　圖形的基本概念?......................206
13-1-1　基本概念 ..................................... 206
13-1-2　生活實(shí)例的概念擴(kuò)展 ................. 206
13-1-3　加權(quán)圖形 (weighted graph) ......... 207
13-1-4　有向圖形 (directed graph) ........... 208
13-1-5　有向無(wú)環(huán)圖 (directed acycle
　　　graph) .......................................... 209
13-1-6　拓?fù)渑判?(topological sort) ......... 209
13-2　廣度優(yōu)先搜尋算法概念解說(shuō)?......209
13-2-1　廣度優(yōu)先搜尋算法理論 ........... 209
13-2-2　生活實(shí)務(wù)解說(shuō) ............................. 212
13-2-3　短路徑 ..................................... 215
13-3　Python 實(shí)踐廣度優(yōu)先搜尋算法?...215
13-3-1　好用的 collections 模塊的
　　　deque() ........................................ 215
13-3-2　廣度優(yōu)先搜尋算法實(shí)例.............. 217
13-3-3　廣度優(yōu)先算法拜訪所有節(jié)點(diǎn) ...... 219
13-3-4　走迷宮 ......................................... 222
13-4　深度優(yōu)先搜尋算法概念解說(shuō)?......224
13-4-1　深度優(yōu)先搜尋算法理論 ........... 224
13-4-2　深度優(yōu)先搜尋算法實(shí)例 ............ 229
13-5　習(xí)題?.....................................231
第 14 章?圖形理論之短路徑算法
14-1　戴克斯特拉 (Dijkstra’s) 算法?....234
14-1-1　短路徑與快路徑問(wèn)題 .......... 234
14-1-2　戴克斯特拉算法 ......................... 234
14-1-3　Python 程序?qū)嵗?......................... 237
14-2　貝爾曼 - 福特 (Bellman-Ford)
????算法?.....................................238
14-3　A* 算法?.................................241
14-4　習(xí)題?.....................................244
第 15 章?貪婪算法
15-1　選課分析?...............................248
15-1-1　問(wèn)題分析 .................................. 248
15-1-2　算法分析 ..................................... 249
15-1-3　Python 程序?qū)嵗?......................... 250
15-2　背包問(wèn)題 ：貪婪算法不是
　　　完美的結(jié)果?.........................251
15-2-1　問(wèn)題分析 .................................. 251
15-2-2　算法分析 ..................................... 251
15-2-3　Python 實(shí)例 ................................ 251
15-3　電臺(tái)選擇?...............................253
15-3-1　問(wèn)題分析 .................................. 253
15-3-2　算法分析 ..................................... 253
15-3-3　Python 實(shí)例 ................................ 258
15-4　業(yè)務(wù)員旅行?............................259
15-4-1　問(wèn)題分析 ..................................... 259
15-4-2　算法分析 ..................................... 260
15-5　習(xí)題?.....................................266
第 16 章?動(dòng)態(tài)規(guī)劃算法
16-1　再談背包問(wèn)題 ：動(dòng)態(tài)規(guī)劃算法?...270
16-1-1　簡(jiǎn)單同時(shí)正確的算法但是耗時(shí) ... 270
16-1-2　動(dòng)態(tài)規(guī)劃算法 ............................. 272
16-1-3　動(dòng)態(tài)算法延伸探討 ..................... 275
16-1-4　存放順序也不影響結(jié)果..............276
16-1-5　Python 程序?qū)嵗?......................... 276
16-2　旅游行程的安排?......................277
16-2-1　旅游行程概念 ........................... 277
16-2-2　Python 程序?qū)嵗?......................... 277
16-3　習(xí)題?.....................................278
第 17 章?數(shù)據(jù)加密到信息安全算法
17-1　數(shù)據(jù)安全與數(shù)據(jù)加密?................282
17-1-1　認(rèn)識(shí)數(shù)據(jù)安全的專(zhuān)有名詞 .......... 282
17-1-2　加密 ............................................. 283
17-2　摩斯密碼 (Morse?code)?..........284
17-3　凱撒密碼?...............................285
17-4　再談文件加密技術(shù)?...................287
17-5　全天下只有你可以解的加密程序
????( 你也可能無(wú)法解 )?..................288
17-6　哈希函數(shù)與 SHA 家族?.............290
17-6-1　再談哈希函數(shù) ............................. 290
17-6-2　MD5(Message-Digest
Algorithm) ................................... 291
17-6-3　SHA 家族 ....................................292
17-7　密鑰密碼?...............................295
17-7-1　對(duì)稱(chēng)密鑰密碼 ............................. 295
17-7-2　公鑰密碼 ..................................... 297
17-8　訊息鑒別碼 (message
?????authentication?code)?.............302
17-9　數(shù)字簽名 (digital?signature)?....304
17-10　數(shù)字證書(shū) (digital?certificate)?..306
17-11?習(xí)題?....................................309
第 18 章?人工智能破冰之旅 ：KNN 和
K-means 算法
18-1　KNN 算法 : 電影分類(lèi)?..............312
18-1-1　規(guī)劃特征值 ................................. 312
18-1-2　將 KNN 算法應(yīng)用在電影分類(lèi) ... 312
18-1-3　項(xiàng)目程序?qū)嵗?............................. 313
18-1-4　電影分類(lèi)結(jié)論 ............................. 314
18-2　KNN 算法 ：選舉造勢(shì)與銷(xiāo)售
?????烤香腸?..................................314
18-2-1　規(guī)劃特征值表 ............................. 314
18-2-2　回歸方法 ..................................... 314
18-2-3　項(xiàng)目程序?qū)嵗?............................. 315
18-3　K-means 算法?......................316
18-3-1　算法基礎(chǔ) ..................................... 316
18-3-2　程序?qū)嵗?..................................... 317
18-4　習(xí)題?.....................................322
第 19 章?常見(jiàn)職場(chǎng)面試算法
19-1　質(zhì)數(shù)測(cè)試?...............................326
19-2　回文算法?...............................327
19-3　歐幾里得算法?.........................328
19-3-1　土地區(qū)塊劃分 ............................. 328
19-3-2　公約數(shù) (greatest common
divisor) ........................................ 328
19-3-3　輾轉(zhuǎn)相除法 ................................. 329
19-3-4　遞歸式函數(shù)設(shè)計(jì)處理歐幾里得
算法 ............................................ 330
19-4　小公倍數(shù) (least?common
????multiple)?...............................330
19-5　雞兔同籠問(wèn)題?.........................330
19-6　挖金礦問(wèn)題?............................332
19-7　習(xí)題?.....................................333