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