数据科学PYTHON算法详解

目　　录



第　1章 算法概述　1

1.1　算法的基础　2

1.1.1　算法的特征　2

1.1.2　何为算法　2

1.2　计算机中的算法　3

1.2.1　认识计算机中的算法　3

1.2.2　为什么说算法是程序的

灵魂　4

1.3　计算机中表示算法的方法　4

1.3.1　用流程图表示算法　4

1.3.2　用N-S流程图表示算法　6

1.3.3　用计算机语言表示算法　6

1.4　学习建议　6

第　2章 数据结构　8

2.1　使用列表　9

2.1.1　列表的基本用法　9

2.1.2　删除列表中的重复元素

并保持顺序不变　10

2.1.3　找出列表中出现次数

*多的元素　11

2.1.4　排序类定义的实例　11

2.1.5　使用列表推导式　12

2.1.6　命名切片　13

2.2　使用元组　14

2.2.1　创建并访问元组　14

2.2.2　修改元组　15

2.2.3　删除元组　15

2.2.4　使用内置方法操作元组　15

2.2.5　将序列分解为单独的

变量　16

2.2.6　将序列分解为单独的

变量　17

2.2.7　实现优先级队列　17

2.3　使用字典　19

2.3.1　创建并访问字典　19

2.3.2　添加、修改、删除字典

中的元素　19

2.3.3　映射多个值　20

2.3.4　使用OrderedDict创建

有序字典　21

2.3.5　获取字典中的*大值和

*小值　22

2.3.6　获取两个字典中相同的

键值对　23

2.3.7　使用函数itemgetter()对

字典进行排序　24

2.3.8　使用字典推导式　25

2.3.9　根据记录进行分组　26

2.3.10　转换并换算数据　27

2.3.11　将多个映射合并为单个

映射　28

第3章　常用的算法思想　30

3.1　枚举算法思想　31

3.1.1　枚举算法基础　31

3.1.2　实践演练—24点游戏　31

3.1.3　实践演练—计算

平方根　32

3.2　递归算法思想　32

3.2.1　递归算法基础　33

3.2.2　实践演练—解决“斐波

那契数列”问题　33

3.2.3　实践演练—解决

“汉诺塔”问题　34

3.2.4　实践演练—解决

“阶乘”问题　36

3.3　分治算法思想　37

3.3.1　分治算法基础　38

3.3.2　实践演练—求顺序表

中的*大值　38

3.3.3　实践演练—判断某个

元素是否在列表中　38

3.3.4　实践演练—找出一组

序列中第k小的元素　39

3.4　贪心算法思想　39

3.4.1　贪心算法基础　39

3.4.2　实践演练—解决“找零”

问题　40

3.4.3　实践演练—解决“汽车

加油”问题　41

3.5　试探算法思想　42

3.5.1　试探算法基础　42

3.5.2　实践演练—解决

“八皇后”问题　42

3.5.3　实践演练—解决

“迷宫”问题　44

3.6　迭代算法思想　45

3.6.1　迭代算法基础　46

3.6.2　实践演练—解决“非线程

方程组”问题　46

3.7　技术解惑　47

3.7.1　衡量算法的标准是什么　47

3.7.2　递推和递归有什么差异　48

3.7.3　总结分治算法能解决什么

类型的问题　48

3.7.4　分治算法的机理是什么　48

3.7.5　为什么说贪婪算法并不是

解决问题的*优方案　48

3.7.6　回溯算法会影响算法

效率吗　49

3.7.7　递归算法与迭代算法

有什么区别　49

第4章　线性表、队列和栈　50

4.1　线性表操作　51

4.1.1　线性表的特性　51

4.1.2　顺序表操作　52

4.1.3　实践演练—实现线性表

顺序存储的插入操作　53

4.1.4　实践演练—实现线性表

顺序存储的删除操作　54

4.1.5　实践演练—顺序表的

插入、检索、删除和反转

操作　54

4.2　链表操作　57

4.2.1　什么是链表　57

4.2.2　实践演练—实现完整

链表操作　60

4.2.3　实践演练—在链表中

增加比较功能　64

4.2.4　实践演练—单链表

结构字符串　67

4.3　先进先出的队列　70

4.3.1　什么是队列　71

4.3.2　Python语言的队列操作　72

4.3.3　实践演练—完整的

顺序队列的操作　72

4.3.4　实践演练—基于列表

实现的优先队列　73

4.3.5　实践演练—基于堆

实现的优先队列　74

4.4　后进先出的栈　75

4.4.1　什么是栈　75

4.4.2　顺序栈　76

4.4.3　链栈　77

4.4.4　实践演练—实现顺序栈

操作　77

4.4.5　实践演练—使用顺序表

方法和单链表方法实现栈　78

4.5　实现堆队列操作　79

4.5.1　Python中的堆操作　79

4.5.2　实践演练—实现二叉

堆操作　80

4.6　技术解惑　82

4.6.1　顺序表插入操作的时间

复杂度是多少　82

4.6.2　顺序表删除操作的时间

复杂度是多少　82

4.6.3　顺序表按值查找操作的

时间复杂度是多少　82

4.6.4　堆和栈的区别是什么　82

第5章　树　84

5.1　树基础　85

5.1.1　什么是树　85

5.1.2　树的相关概念　85

5.2　使用列表表示的树　86

5.3　二叉树详解　87

5.3.1　二叉树的定义　87

5.3.2　二叉树的性质　88

5.3.3　二叉树的存储结构　88

5.3.4　实践演练—使用嵌套

列表表示树　90

5.3.5　实践演练—把二叉树的

任何子节点当成二叉树　91

5.3.6　实践演练—实现二叉

搜索树查找操作　93

5.3.7　实践演练—实现二叉

搜索树的删除操作　97

5.3.8　遍历二叉树　104

5.3.9　线索二叉树　107

5.4　霍夫曼树　115

5.4.1　霍夫曼树基础　115

5.4.2　实践演练—使用面向

过程方式和面向对象方式

实现霍夫曼树　117

5.4.3　实践演练—实现霍夫曼

树的基本操作　118

5.4.4　总结霍夫曼编码的算法

实现　120

5.5　技术解惑　120

5.5.1　树和二叉树的差别是

什么　120

5.5.2　二叉树和链表的效率

比较　121

5.5.3　如何输出二叉树中的

所有路径　121

第6章　图　122

6.1　图的起源　123

6.2　图的相关概念　124

6.3　存储结构　127

6.3.1　使用邻接矩阵表示图　127

6.3.2　实践演练—将邻接矩阵

输出成图　128

6.3.3　使用邻接表表示图　129

6.3.4　实践演练—使用邻接表

表示图　130

6.4　图的遍历　131

6.4.1　深度优先搜索　131

6.4.2　广度优先搜索　132

6.4.3　实践演练—实现图的深度

优先和广度优先搜索　133

6.5　图的连通性　135

6.5.1　无向图的连通分量　135

6.5.2　实践演练—通过二维数

组建立无向图　136

6.5.3　实践演练—根据邻接

矩阵绘制无向图　137

6.5.4　*小生成树　138

6.5.5　实践演练—实现*小生

成树和拓扑序列　139

6.5.6　关键路径　140

6.5.7　实践演练—递归解决

AOE网*长关键路径的

问题　141

6.6　寻求*短路径　143

6.6.1　求某一顶点到其他各顶点

的*短路径　143

6.6.2　任意一对顶点间的*短

路径　145

6.6.3　实践演练—使用Dijkstra

算法计算指定点到其他

各顶点的路径　146

6.6.4　实践演练—使用Floyd-

Warshall算法计算图的

*短路径　147

6.6.5　实践演练—使用Bellman-

Ford算法计算图的*短

路径　148

6.6.6　实践演练—使用Dijkstra

算法解决加权的*短路径

问题　149

6.7　技术解惑　150

6.7.1　几种*短路径算法的

比较　150

6.7.2　邻接矩阵与邻接表的

对比　152

6.7.3　比较深度优先算法和

广度优先算法　152

第7章　查找算法　154

7.1　几个相关概念　155

7.2　基于线性表的查找法　155

7.2.1　顺序查找法　155

7.2.2　实践演练—实现顺序

查找算法　156

7.2.3　折半查找法　157

7.2.4　实践演练—使用折半

查找法查找数据　158

7.2.5　插值查找法　160

7.2.6　实践演练—使用插值

查找法查找指定的数据　160

7.2.7　分块查找法　161

7.3　基于树的查找法　162

7.3.1　二叉排序树　162

7.3.2　实践演练—实现二叉树

的完整操作　165

7.3.3　平衡二叉树　167

7.3.4　实践演练—实现平衡

二叉树的基本操作　170

7.4　散列法　174

7.4.1　散列法的基本思想　174

7.4.2　构造散列函数　175

7.4.3　处理冲突　176

7.4.4　散列表的查找过程　177

7.4.5　实践演练—使用散列表

查找数据　177

7.5　斐波那契查找法　178

7.5.1　斐波那契查找法介绍　178

7.5.2　实践演练—使用斐波

那契查找法　179

7.6　高级树表查找算法　180

7.6.1　2-3查找树介绍　180

7.6.2　红黑树介绍　181

7.6.3　实践演练—使用红黑树

操作数据　181

7.6.4　B树和B 树　185

7.6.5　实践演练—使用B树

排序数据　186

7.6.6　实践演练—使用B 树

操作数据　188

7.7　技术解惑　193

7.7.1　分析查找算法的性能　193

7.7.2　分析散列法的性能　194

第8章　内部排序算法　195

8.1　排序基础　196

8.1.1　排序的目的和过程　196

8.1.2　内部排序与外部排序　196

8.1.3　稳定排序与不稳定排序　196

8.2　插入排序算法　197

8.2.1　直接插入排序　197

8.2.2　实践演练—编写直接

插入排序算法　198

8.2.3　实践演练—使用折半

插入排序算法　198

8.2.4　希尔排序　199

8.2.5　实践演练—使用希尔

排序算法对数据进行

排序　199

8.2.6　实践演练—使用希尔

排序处理一个列表　200

8.3　交换类排序法　201

8.3.1　冒泡排序（相邻

比序法）　201

8.3.2　快速排序　201

8.3.3　实践演练—实现从大

到小的冒泡排序　202

8.3.4　实践演练—使用冒泡

排序算法排序　202

8.3.5　实践演练—实现基本的

快速排列　203

8.4　选择排序法　204

8.4.1　直接选择排序　204

8.4.2　树形选择排序　204

8.4.3　堆排序　205

8.4.4　实践演练—实现直接

选择排序　206

8.4.5　实践演练—演示选择

排序的操作步骤　207

8.4.6　实践演练—选择排序和

Python内置函数的效率

对比　208

8.4.7　实践演练—使用堆排序

处理数据　209

8.4.8　实践演练—实现

*小堆　210

8.5　归并排序　211

8.5.1　归并排序思想　211

8.5.2　两路归并算法的思路　212

8.5.3　实现归并排序　212

8.5.4　实践演练—使用归并

排序处理指定列表　213

8.5.5　实践演练—使用归并

排序处理两个列表　213

8.5.6　实践演练—使用两路

归并排序处理一个列表　214

8.6　基数排序　215

8.6.1　多关键字排序　215

8.6.2　链式基数排序　216

8.6.3　实践演练—使用基数

排序处理随机数　217

8.7　技术解惑　218

8.7.1　插入排序算法的描述　218

8.7.2　希尔排序和插入排序的

速度比较　218

8.7.3　快速排序的时间耗费　218

8.7.4　堆排序与直接选择排序的

区别　219

8.7.5　归并排序的效率与选择

方法　219

8.7.6　综合比较各种排序方法　219

第9章　经典的数据结构问题　221

9.1　约瑟夫环　222

9.1.1　问题描述　222

9.1.2　算法分析　222

9.1.3　具体实现　222

9.2　大整数运算　224

9.2.1　模拟大整数乘法的小学

竖式计算过程　224

9.2.2　实现大数相加运算　225

9.3　顺序表的修改、查找、统计、

删除、销毁操作　225

9.3.1　算法分析　225

9.3.2　具体实现　226

9.4　实现链表的基本操作　227

9.4.1　算法分析　227

9.4.2　具体实现　227

9.5　带有尾节点引用的单链表　229

9.5.1　算法分析　229

9.5.2　具体实现　229

9.6　增加新功能的单链表结构

字符串　230

9.7　实现堆排序功能　232

9.7.1　算法分析　232

9.7.2　具体实现　233

9.8　实现队列、链表、顺序表和循环

顺序表　234

9.8.1　时间复杂度分析　234

9.8.2　具体实现　234

9.9　基于列表实现二叉树　236

9.10　实现二元表达式　237

9.11　使用多叉树寻找*短路径　239

9.11.1　算法分析　239

9.11.2　具体实现　239

9.12　实现AVL树　240

9.13　使用二维数组生成有向图　244

9.14　使用广度优先和深度优先遍历

二叉树　245

第　10章 数学问题的解决　248

10.1　解决一个数学问题　249

10.1.1　问题描述　249

10.1.2　具体实现　249

10.2　使用递归算法计算两个数的

乘积　250

10.3　利用递归算法获取斐波那契数

列前n项的值　250

10.4　1000以内的完全数　251

10.4.1　问题描述　251

10.4.2　算法分析　251

10.4.3　具体实现　252

10.5　多进程验证哥德巴赫猜想　253

10.5.1　问题描述　253

10.5.2　算法分析　253

10.5.3　具体实现　253

10.6　*大公约数和*小公倍数　255

10.6.1　问题描述　255

10.6.2　算法分析　255

10.6.3　具体实现　255

10.7　亲密数　255

10.7.1　问题描述　255

10.7.2　算法分析　256

10.7.3　具体实现　256

10.8　计算10000以内的自守数　256

10.8.1　问题描述　256

10.8.2　算法分析　256

10.8.3　具体实现　257

10.9　水仙花数　257

10.9.1　问题描述　257

10.9.2　算法分析　257

10.9.3　具体实现　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　矩阵运算　264

10.12.1　问题描述　264

10.12.2　算法分析　264

10.12.3　具体实现　264

10.13　一元多项式运算　265

10.13.1　一元多项式求导　266

10.13.2　实现多项式的加法、

减法、乘法运算　266

10.14　百钱买百鸡　267

10.14.1　问题描述　267

10.14.2　算法分析　268

10.14.3　具体实现　268

10.15　素数问题　268

10.15.1　求1000以内的所有

素数　269

10.15.2　孪生素数问题　269

10.15.3　金蝉素数　270

10.15.4　可逆素数　271

10.15.5　回文素数　271

10.15.6　等差素数数列　272

10.16　埃及分数式　273

10.16.1　问题描述　273

10.16.2　算法分析　274

10.16.3　具体实现　274

10.17　对正整数分解质因数　274

10.17.1　问题描述　274

10.17.2　算法分析　274

10.17.3　具体实现　274

第　11章 经典算法问题的解决　276

11.1　歌星大奖赛　277

11.1.1　问题描述　277

11.1.2　具体实现　277

11.2　借书方案　278

11.2.1　问题描述　278

11.2.2　算法分析　278

11.2.3　具体实现　278

11.3　捕鱼和分鱼　279

11.3.1　问题描述　279

11.3.2　算法分析　279

11.3.3　具体实现　279

11.4　出售金鱼　280

11.4.1　问题描述　280

11.4.2　算法分析　280

11.4.3　具体实现　280

11.5　平分七筐鱼　280

11.5.1　问题描述　280

11.5.2　算法分析　281

11.5.3　具体实现　281

11.6　绳子的长度和井深　281

11.6.1　问题描述　281

11.6.2　算法分析　282

11.6.3　具体实现　282

11.7　鸡兔同笼　282

11.7.1　问题描述　282

11.7.2　算法分析　283

11.7.3　具体实现　283

11.8　汉诺塔　283

11.8.1　问题描述　283

11.8.2　算法分析　284

11.8.3　具体实现　284

11.9　马踏棋盘　285

11.9.1　使用递归法　285

11.9.2　贪婪、递归、迭代三种

算法的对比　287

11.10　三色球问题　289

11.10.1　问题描述　289

11.10.2　算法分析　289

11.10.3　具体实现　289

11.11　计算年龄　290

11.11.1　问题描述　290

11.12.2　算法分析　290

11.11.3　具体实现　290

11.12　奇数幻方问题　291

11.12.1　问题描述　291

11.12.2　具体实现　291

11.13　常胜将军问题　291

11.13.1　问题描述　291

11.13.2　算法分析　292

11.13.3　具体实现　292

11.14　背包问题　292

11.14.1　使用动态规划法解决

“背包”问题　292

11.14.2　使用递归法解决“背包”

问题　293

11.15　野人与传教士问题　295

11.15.1　问题描述　295

11.15.2　算法分析　295

11.15.3　具体实现　295

11.16　三色旗问题　296

11.16.1　问题描述　296

11.16.2　算法分析　296

11.16.3　具体实现　297

11.17　猴子分桃　297

11.17.1　问题描述　297

11.17.2　算法分析　298

11.17.3　具体实现　298

11.18　将老师随机分配到办公室　298

11.18.1　问题描述　298

11.18.2　具体实现　299

11.19　龙的世界　300

11.19.1　问题描述　300

11.19.2　具体实现　300

11.20　凯撒密码游戏　301

11.20.1　问题描述　301

11.20.2　算法分析　301

11.20.3　具体实现　301

第　12章 图像问题　303

12.1　生命游戏　304

12.1.1　问题描述　304

12.1.2　算法分析　304

12.1.3　具体实现　304

12.2　黑白棋问题　306

12.2.1　问题描述　306

12.2.2　算法分析　307

12.2.3　具体实现　307

12.3　马踏棋盘（骑士周游问题）　311

12.3.1　问题描述　311

12.3.2　算法分析　311

12.3.3　具体实现　311

12.4　井字棋问题　313

12.4.1　问题描述　313

12.4.2　算法分析　313

12.4.3　具体实现　313

12.5　用蒙特卡罗方法验证凯利

公式　317

12.5.1　问题描述　317

12.5.2　算法分析　317

12.5.3　具体实现　317

12.6　绘制Hangman游戏　319

12.6.1　问题描述　319

12.6.2　算法分析　319

12.6.3　具体实现　320

第　13章 游戏和算法　324

13.1　开发一个俄罗斯方块游戏　325

13.1.1　规划图形　325

13.1.2　具体实现　325

13.2　跑酷游戏　332

13.3　水果连连看游戏　337

13.4　AI智能贪吃蛇游戏　341

13.5　AI智能五子棋游戏　346