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

目 錄 

第 1 章 算法基本概念 

1-1 電腦的算法................................2 

1-2 不好的算法與好的算法...................3 

1-2-1　不好的算法 ....................................... 3 

1-2-2　好的算法 ........................................... 7 

1-3　程序執行的時間測量方法 ：時間 

　　 復雜度.........................................8 

1-3-1　基本概念 ........................................ 8 

1-3-2　時間測量復雜度 ............................... 9 

1-4 內存的使用 ：空間復雜度..............12 

1-4-1　基本概念 ......................................... 12 

1-4-2　常見的空間復雜度計算 ................. 14 

1-5 數據結構....................................16 

1-6　習題..........................................16 

第 2 章 數組 

2-1　基本概念....................................20 

2-2　使用索引存取數組內容.................20 

2-3　新數據插入數組...........................20 

2-3-1　假設當下有足夠的連續內存 

　　　 空間 ................................................ 21 

2-3-2　假設當下沒有足夠的連續內存 

　　　 空間 ................................................ 22 

2-4　刪除數組元素..............................22 

2-5　思考數組的優缺點........................23 

2-6　與數組有關的 Python 程序...........24 

2-6-1　建立數組 ......................................... 25 

2-6-2　存取數組內容 ................................. 25 

2-6-3　將數據插入數組 ............................. 26 

2-6-4　刪除數組元素 ................................. 27 

2-6-5　搜尋數組元素 ................................. 28 

2-6-6　更新數組內容 ................................. 28 

2-6-7　Numpy ............................................. 28 

2-7　習題..........................................29 

第 3 章 鏈表 

3-1　鏈表數據形式與內存概念..............32 

3-2　鏈表的數據讀取...........................32 

3-3　新數據插入鏈表...........................33 

3-4　刪除鏈表的節點元素....................34 

3-5　循環鏈表 (circle linked list)..........34 

3-6　雙向鏈表....................................34 

3-7　數組與鏈表基本操作的時間復雜度 

　　　比較..........................................34 

3-8　與鏈表有關的 Python 程序...........35 

3-8-1　建立鏈表 ......................................... 35 

3-8-2　建立鏈表類別和遍歷此鏈表 .......... 36 

3-8-3　在鏈表第一個節點前插入一個 

　　　 新的節點......................................... 37 

3-8-4　在鏈表末端插入新的節點 .............. 39 

3-8-5　在鏈表中間插入新的節點 .............. 40 

3-8-6　在鏈表中刪除指定內容的節點 ...... 42 

3-8-7　建立循環鏈表 ................................. 43 

3-8-8　雙向鏈表 ......................................... 44 

3-9　習題..........................................47 

第 4 章 隊列 

4-1　數據插入 enqueue......................50 

4-2　數據讀取 dequeue......................51 

4-3　使用列表模仿隊列的操作..............51 

4-4　與隊列有關的 Python 模塊...........53 

4-5　習題..........................................54 

第 5 章 棧 

5-1　數據推入 push............................56 

5-2　數據取出 pop..............................57 

5-3　Python 中棧的應用......................58 

5-3-1　使用列表 (list) 模擬棧操作 ............ 58 

5-3-2　自行建立 stack 類別執行相關 

　　　 操作 ................................................ 59 

5-4　函數調用與棧運作?.......................61

5-5　遞歸調用與棧運作?.......................62

5-6　習題?.........................................66

第 6 章?二叉樹

6-1　建立二叉樹?................................68

6-2　刪除二叉樹的節點?.......................70

6-3　搜尋二叉樹的數據?.......................72

6-4　更進一步認識二叉樹?...................74

6-5　內存存儲二叉樹的方法?................75

6-6　Python 中二叉樹的運用?..............77

6-6-1　使用數組建立二叉樹 .....................77

6-6-2　鏈表方式建立二叉樹的根節點 ......79

6-6-3　使用鏈表建立二叉樹 .....................80

6-6-4　遍歷二叉樹使用中序 (inorder)

　　　打印 ................................................80

6-6-5　遍歷二叉樹使用前序 (preorder)

　　　打印 ................................................85

6-6-6　遍歷二叉樹使用後序 (postorder)

　　　打印 ................................................89

6-6-7　二叉樹節點的搜尋 .........................94

6-6-8　二叉樹節點的刪除 .........................96

6-6-9　二叉樹的應用與工作效率 ..............98

6-7　習題?.........................................98

第 7 章?堆積樹

7-1　建立堆積樹?..............................102

7-2　插入數據到堆積樹?.....................103

7-3　取出最小堆積樹的值?.................105

7-4　最小堆積樹與數組?.....................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　插入節點 ....................................... 115

7-7　習題?.......................................115

第 8 章?哈希表

8-1　基本概念?.................................118

8-2　哈希表轉成數組?........................119

8-2-1　哈希表寫入 ................................... 119

8-2-2　哈希碰撞與鏈結法 ....................... 121

8-2-3　哈希碰撞與開放尋址法 ............... 122

8-3　搜尋哈希表?..............................122

8-4　哈希表的規模與擴充?.................124

8-5　好的哈希表與不好的哈希表?........125

8-6　哈希表效能分析?........................126

8-7　Python 程序應用?......................126

8-7-1　Python 建立哈希表 ....................... 127

8-7-2　建立電話號碼簿 ........................... 127

8-7-3　避免數據重復 ............................... 128

8-8　認識哈希表模塊 hashlib?............129

8-8-1　使用 md5( ) 方法計算中文 / 英文

　　　數據的哈希值 ............................... 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 章?數據搜尋

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) 數列?......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　有向無環圖 (directed acycle

　　　graph) .......................................... 209

13-1-6　拓撲排序 (topological sort) ......... 209

13-2　廣度優先搜尋算法概念解說?......209

13-2-1　廣度優先搜尋算法理論 ........... 209

13-2-2　生活實務解說 ............................. 212

13-2-3　最短路徑 ..................................... 215

13-3　Python 實踐廣度優先搜尋算法?...215

13-3-1　好用的 collections 模塊的

　　　deque() ........................................ 215

13-3-2　廣度優先搜尋算法實例.............. 217

13-3-3　廣度優先算法拜訪所有節點 ...... 219

13-3-4　走迷宮 ......................................... 222

13-4　深度優先搜尋算法概念解說?......224

13-4-1　深度優先搜尋算法理論 ........... 224

13-4-2　深度優先搜尋算法實例 ............ 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　業務員旅行?............................259

15-4-1　問題分析 ..................................... 259

15-4-2　算法分析 ..................................... 260

15-5　習題?.....................................266

第 16 章?動態規劃算法

16-1　再談背包問題 ：動態規劃算法?...270

16-1-1　簡單同時正確的算法但是耗時 ... 270

16-1-2　動態規劃算法 ............................. 272

16-1-3　動態算法延伸探討 ..................... 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 章?數據加密到信息安全算法

17-1　數據安全與數據加密?................282

17-1-1　認識數據安全的專有名詞 .......... 282

17-1-2　加密 ............................................. 283

17-2　摩斯密碼 (Morse?code)?..........284

17-3　凱撒密碼?...............................285

17-4　再談文件加密技術?...................287

17-5　全天下只有你可以解的加密程序

????( 你也可能無法解 )?..................288

17-6　哈希函數與 SHA 家族?.............290

17-6-1　再談哈希函數 ............................. 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　數字簽名 (digital?signature)?....304

17-10　數字證書 (digital?certificate)?..306

17-11?習題?....................................309

第 18 章?人工智能破冰之旅 ：KNN 和

K-means 算法

18-1　KNN 算法 : 電影分類?..............312

18-1-1　規劃特徵值 ................................. 312

18-1-2　將 KNN 算法應用在電影分類 ... 312

18-1-3　項目程序實例 ............................. 313

18-1-4　電影分類結論 ............................. 314

18-2　KNN 算法 ：選舉造勢與銷售

?????烤香腸?..................................314

18-2-1　規劃特徵值表 ............................. 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　質數測試?...............................326

19-2　迴文算法?...............................327

19-3　歐幾里得算法?.........................328

19-3-1　土地區塊劃分 ............................. 328

19-3-2　最大公約數 (greatest common

divisor) ........................................ 328

19-3-3　輾轉相除法 ................................. 329

19-3-4　遞歸式函數設計處理歐幾里得

算法 ............................................ 330

19-4　最小公倍數 (least?common

????multiple)?...............................330

19-5　雞兔同籠問題?.........................330

19-6　挖金礦問題?............................332

19-7　習題?.....................................333