算法零基礎一本通（Python版）

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