面向大数据的数据结构与算法设计（Python版）汤羽

面对大数据和人工智能技术及应用的迅猛发展，传统的数据结构与算法课程的教学内容和教学模式亟待改革，以适应大数据和人工智能专业人才培养的需要。本书就是为满足这种需要而编写的。本书共15章，主要内容包括大数据概念、Python语言基础、线性表、栈与队列、数组与字符串、树、图等经典数据结构，键值对、嵌套数据结构、列存储结构等面向大数据计算的新型数据结构，排序算法、查找算法、基础算法设计、机器学习算法基础、大数据框架下的算法设计等经典基础算法和大数据常用算法。
本书兼顾每种数据结构的抽象逻辑结构及其物理存储形式，使学生对数据结构的设计原理、实现方法、存储机制有较深刻的认识。
本书可作为计算机科学与技术、软件工程、大数据技术与应用、人工智能等专业数据结构与算法及相关课程的教材。

目录
第 1 章大数据概论...........................................1
1.1 数据 .........................................................2
1.2 数据结构 .................................................3
1.2.1 数据逻辑结构..............................4
1.2.2 数据物理结构..............................6
1.3 大数据计算 .............................................7
本章小结.............................................................9
本章习题.............................................................9
第 2 章 Python 语言基础......................10
2.1 Python 安装 ........................................11
2.2 Python 数据类型 ................................12
2.2.1 int 类型 ......................................13
2.2.2 float 类型 ...................................14
2.2.3 字符串 .......................................14
2.2.4 序列数据....................................15
2.3 Python 程序控制 ................................16
2.3.1 条件判断................................... 16
2.3.2 循环控制................................... 17
2.3.3 异常处理................................... 18
2.4 Python 函数........................................ 19
本章小结.......................................................... 20
本章习题.......................................................... 20
课程实验.......................................................... 20
第 3 章线性表...................................................... 22
3.1 线性表................................................... 23
3.2 顺序表................................................... 23
3.2.1 顺序表动态存储....................... 24
3.2.2 顺序表静态存储....................... 24
3.2.3 顺序表的实现........................... 24
3.3 链表....................................................... 27
3.3.1 单链表....................................... 27
3.3.2 双链表....................................... 30
3.3.3 单向循环链表........................... 31
3.3.4 双向循环链表........................... 32
3.4 链表应用............................................... 33
本章小结 ..........................................................34
本章习题 ..........................................................34
课程实验 ..........................................................34
第 4 章栈与队列...............................................35
4.1 栈 ...........................................................36
4.1.1 顺序栈 .......................................36
4.1.2 链式栈 .......................................37
4.1.3 栈的应用 ...................................38
4.2 队列 .......................................................39
4.2.1 顺序队列 ...................................39
4.2.2 链式队列 ...................................41
4.2.3 循环队列 ...................................42
本章小结 ..........................................................43
本章习题 ..........................................................43
课程实验 ..........................................................44
第 5 章数组与字符串..................................45
5.1 数组 .......................................................46
5.1.1 数组的定义 ...............................46
5.1.2 数组的表示和实现....................47
5.2 矩阵的压缩存储 ...................................48
5.2.1 特殊矩阵 ...................................48
5.2.2 稀疏矩阵 ...................................50
5.2.3 稀疏矩阵的转置........................50
5.3 字符串 ...................................................51
5.3.1 字符串存储结构....................... 51
5.3.2 字符串的顺序存储................... 51
5.3.3 字符串的链式存储................... 52
5.3.4 字符串匹配算法....................... 52
本章小结.......................................................... 55
本章习题.......................................................... 55
课程实验.......................................................... 55
第 6 章树与二叉树........................................ 57
6.1 树基本概念........................................... 58
6.2 二叉树................................................... 59
6.2.1 二叉树定义............................... 59
6.2.2 二叉树分类............................... 59
6.2.3 二叉树性质............................... 61
6.3 二叉树存储结构................................... 62
6.3.1 二叉树的顺序存储................... 62
6.3.2 二叉树的链式存储................... 63
6.4 二叉树操作........................................... 63
6.4.1 二叉树的遍历........................... 63
6.4.2 二叉树遍历的递归实现........... 63
6.4.3 二叉树遍历的非递归实现 ....... 64
6.4.4 二叉树的创建........................... 65
6.5 树的存储结构....................................... 65
6.5.1 双亲表示法............................... 65
6.5.2 孩子表示法............................... 67
6.5.3 双亲孩子表示法....................... 68
6.5.3 孩子兄弟表示法....................... 68
6.6 树与森林............................................... 69
6.6.1 二叉树与树的转换....................69
6.6.2 二叉树与森林的转换................70
6.7 二叉查找树 ...........................................71
6.7.1 二叉查找树的创建....................71
6.7.2 二叉查找树的插入....................71
6.7.3 二叉查找树的删除....................71
6.8 平衡二叉树 ...........................................72
6.8.1 平衡二叉树的概念....................72
6.8.2 平衡二叉树的插入....................72
6.8.3 平衡二叉树的删除....................73
6.9 赫夫曼树 ...............................................74
6.9.1 赫夫曼树性质............................74
6.9.2 赫夫曼树构造............................75
6.9.3 赫夫曼编码................................75
本章小结...........................................................76
本章习题...........................................................76
课程实验...........................................................77
第 7章图........................................................78
7.1 图基本概念 ...........................................79
7.2 图数据结构 ...........................................80
7.2.1 图邻接矩阵................................80
7.2.2 图邻接表....................................81
7.2.3 图十字链表................................82
7.2.4 图多重邻接表............................83
7.3 图遍历算法 ...........................................85
7.3.1 深度优先遍历............................85
7.3.2 广度优先遍历............................88
7.4 最小生成树........................................... 89
7.4.1 最小生成树性质....................... 89
7.4.2 Prim 算法 .................................. 92
7.4.3 Kruskal 算法 ............................. 92
7.5 最短路径............................................... 94
7.5.1 单源点最短路径的 Dijkstra 算法........................... 94
7.5.2 任意顶点间最短路径的 Floyd 算法......................... 95
7.6 有向图................................................... 95
本章小结.......................................................... 96
本章习题.......................................................... 96
课程实验.......................................................... 98
第 8 章键值对...................................................... 99
8.1 键值对概念......................................... 100
8.2 键值对存储结构................................. 100
8.2.1 概念......................................... 100
8.2.2 一般想法................................. 100
8.2.3 散列函数................................. 101
8.2.4 散列冲突................................. 103
8.2.5 散列冲突的解决方法 ............. 103
8.3 键值对操作......................................... 105
8.3.1 键值对的插入操作 ................. 105
8.3.2 键值对的查找操作 ................. 106
8.3.3 键值对的删除操作 ................. 106
8.3.4 散列查找算法......................... 106
8.4 典型的基于键值对的数据库 ............. 107
8.4.1 Redis........................................107
8.4.2 Memcached..............................108
8.4.3 适用场景 .................................108
本章小结 ........................................................109
本章习题 ........................................................110
课程实验 ........................................................110
第 9 章嵌套数据结构................................ 111
9.1 嵌套数据结构概念 .............................112
9.2 数据模型 .............................................112
9.3 物理存储结构 .....................................113
9.4 数据重构方法 .....................................117
9.5 查询引擎 .............................................118
9.5.1 多层服务树架构......................119
9.5.2 类 SQL.....................................120
9.6 适用场景 .............................................121
本章小结 ........................................................122
本章习题 ........................................................123
课程实验 ........................................................123
第 10 章列存储结构.......................................125
10.1 列存储结构概念...............................126
10.2 列存储数据模型...............................126
10.2.1 重要概念 ...............................126
10.2.2 逻辑模型 ...............................127
10.2.3 物理模型 ...............................129
10.2.4 存储机制............................... 129
10.3 列存储的数据操作 .......................... 131
10.3.1 读操作................................... 131
10.3.2 写操作................................... 131
10.3.3 扫描操作............................... 132
10.3.4 删除操作............................... 132
10.4 列存储的索引 .................................. 133
10.4.1 二级索引............................... 133
10.4.2 索引方案............................... 134
10.5 列存储的适用场景 .......................... 136
本章小结........................................................ 138
本章习题........................................................ 138
课程实验........................................................ 139
第 11 章排序算法............................................. 141
11.1 内部排序 .......................................... 142
11.1.1 插入排序............................... 142
11.1.2 希尔排序............................... 143
11.1.3 冒泡排序............................... 144
11.1.4 快速排序............................... 145
11.2 内部排序算法比较 .......................... 146
11.3 外部排序 .......................................... 147
11.3.1 二路归并排序 ....................... 147
11.3.2 多路归并排序 ....................... 148
本章小结........................................................ 150
本章习题........................................................ 150
课程实验........................................................ 150
第 12 章查找算法.............................................152
12.1 查找概述...........................................153
12.2 顺序表查找.......................................153
12.3 折半查找...........................................153
12.4 索引顺序查找...................................155
12.5 散列表...............................................156
12.5.1 散列表简介............................156
12.5.2 散列函数的构造....................157
12.5.3 解决冲突的方法....................158
12.5.4 散列表查找............................161
本章小结.........................................................163
本章习题.........................................................164
课程实验.........................................................164
第 13 章基础算法设计................................165
13.1 分治法...............................................166
13.1.1 基本思想................................166
13.1.2 整数乘法................................167
13.1.3 求两个矩阵的乘积................169
13.2 动态规划法.......................................172
13.2.1 基本思想................................172
13.2.2 矩阵连乘问题........................173
13.3 贪心算法...........................................175
13.3.1 基本思想................................176
13.3.2 背包问题................................176
13.4 回溯法 .............................................. 177
13.4.1 基本思想............................... 177
13.4.2 单词匹配问题....................... 178
本章小结........................................................ 179
本章习题........................................................ 179
课程实验........................................................ 180
第 14 章机器学习算法基础.................. 181
14.1 监督学习算法................................... 182
14.1.1 朴素贝叶斯算法 ................... 183
14.1.2 决策树算法........................... 185
14.2 无监督学习算法............................... 186
14.2.1 聚类分析............................... 186
14.2.2 层次聚类............................... 186
14.2.3 k-means.................................. 187
14.3 PageRank 算法.............................. 187
14.3.1 背景概述............................... 187
14.3.2 算法概述............................... 188
本章小结........................................................ 189
本章习题........................................................ 189
课程实验........................................................ 189
第 15 章大数据框架下的算法设计................................. 190
15.1 朴素贝叶斯算法实现....................... 191
15.1.1 MapReduce 框架下的朴素贝叶斯算法....................194
15.1.2 Spark 框架下的朴素贝叶斯算法 .........................196
15.1.3 性能分析与比较....................197
15.2 k-means 算法实现 ........................198
15.2.1 MapReduce 框架下的 k-means 算法 ......................201
15.2.2 Spark 框架下的 k-means 算法..........................202
15.2.3 性能分析与比较....................204
15.3 PageRank 算法实现......................204
15.3.1 MapReduce 框架下的PageRank 算法............. 208
15.3.2 Spark 框架下的 PageRank 算法............................ 210
15.3.3 性能分析与比较................... 212
本章小结........................................................ 212
本章习题........................................................ 212
课程实验........................................................ 213
参考文献............................................. 214

汤羽，电子科技大学信息与软件工程学院副院长、专业首席教授、学校学术委员会委员、智能计算系统团队负责人。教授《软件体系架构与设计模式》《大数据计算技术》《信息科学前沿讲座》《计算思维导论》等课程。主编教材《大数据计算与分析》，清华大学出版社，2017年9月第一版。获省级教学成果二等奖1项、校级教学成果一等奖2项。

面向大数据的数据结构与算法设计（Python版）"