目 录 

第 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