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

图书标准信息

• 作者 汤羽 林迪
• 出版社 人民邮电出版社
• 出版时间 2022-12
• 版次 1
• ISBN 9787115593412
• 定价 59.80元
• 装帧 其他
• 开本 其他
• 纸张 胶版纸
• 字数 336千字

【内容简介】

面对大数据和人工智能技术及应用的迅猛发展，传统的数据结构与算法课程的教学内容和教学模式亟待改革，以适应大数据和人工智能专业人才培养的需要。本书就是为满足这种需要而编写的。本书共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