“数据结构与算法”是计算机及其相关专业的重要课程，该课程的内容是计算机软件开发及应用人员必备的专业基础。随着大数据、人工智能、通信技术的发展，计算机软件也越来越朝着智能化、自动化方向发展，结合人工智能技术、大数据技术来开发计算机软件是未来的发展趋势。本书主要介绍了经典的数据结构与算法的知识，包括基础的线性表、栈、队列、串、数组、树、图等数据结构，以及常用的查找和排序技术。在此基础上，本书加入了大数据和AI领域的KNN机器学习、随机梯度下降、神经网络、搜索引擎、大规模矩阵计算、大数据排序等工程实践案例，使读者可以将数据结构和算法的知识与大数据和AI应用紧密结合在一起，融会贯通。
本书内容丰富、层次清晰、深入浅出，在AI、大数据领域的工程实践案例中将理论讲解和代码实现一一对应，尤其适合作为人工智能专业、大数据专业、电子信息类专业的数据结构与算法课程的教材，可以为学生后续学习AI和大数据等专业课程奠定基础。

第1章绪论1

1.1数据结构与算法的重要性1

1.2数据结构的基本概念4

1.3算法和算法分析7

1.3.1算法描述7

1.3.2算法分析9

1.3.3NP问题12

1.4STL与数据结构13

1.4.1STL简介13

1.4.2STL与数据结构的关系14

1.5工程实践和思考15

习题119

第2章线性表21

2.1线性表概述21

2.1.1线性表的定义21

2.1.2线性表的运算22

2.1.3各种常用存储结构22

2.2顺序表的实现25

2.2.1顺序表的存储结构25

2.2.2顺序表的基本运算25

2.2.3顺序表的应用——通讯录30

2.2.4STL中的顺序表——vector32

2.3单链表的实现34

2.3.1单链表的存储结构34

2.3.2单链表的基本运算36

2.3.3单链表的应用——通讯录43

2.4循环链表的实现43

2.5双链表的实现45

2.5.1双链表的基本结构45

2.5.2双链表的基本运算46

2.5.3STL中的双链表——list47

2.6顺序表与链表的比较48

2.6.1时间性能比较48

2.6.2空间性能比较48

2.7工程实践和思考49

问题1：不支持指针的高级语言如何实现链表?49

问题2：随机梯度下降算法52

问题3：操作系统的内存如何管理？58

问题4：荷兰国旗问题62

习题264





第3章线性表的扩展69

3.1各种扩展线性表69

3.1.1栈69

3.1.2队列70

3.1.3串70

3.1.4多维数组72

3.2栈的实现73

3.2.1顺序栈73

3.2.2链栈75

3.2.3栈与递归76

3.2.4STL中的栈——stack78

3.3队列的实现79

3.3.1循环队列79

3.3.2链队列82

3.3.3STL中的队列84

3.4串的实现87

3.4.1串的存储结构87

3.4.2串的模式匹配88

3.4.3KMP算法90

3.4.4STL中的串——string94

3.5多维数组95

3.5.1多维数组的存储95

3.5.2稀疏矩阵的表示和计算97

3.6经典算法分析105

3.6.1穷举法——背包问题105

3.6.2贪心算法——背包问题106

3.6.3分治法——汉诺塔游戏107

3.6.4回溯法——迷宫问题109

3.6.5动态规划——背包问题113

3.7工程实践和思考115

问题1：优先级队列的调度115

问题2：大规模矩阵计算118

问题3：BMP图像处理121

问题4：基于KNN算法的手写数字识别130

习题3137

第4章树140

4.1基本概念140

4.1.1树140

4.1.2二叉树141

4.1.3森林144

4.2基本操作145

4.2.1树的遍历145

4.2.2二叉树的遍历145

4.2.3森林的遍历147

4.2.4树、森林与二叉树的转换148

4.3存储结构149

4.3.1树的存储结构149

4.3.2二叉树的存储结构152

4.4二叉树的实现155

4.4.1二叉树的声明155

4.4.2二叉树的关键算法155

4.4.3递归算法的规律159

4.5哈夫曼树的应用164

4.5.1哈夫曼树的定义与存储结构164

4.5.2哈夫曼树的构造167

4.5.3哈夫曼编码表的构建168

4.5.4哈夫曼编、解码的实现169

4.6工程实践和思考170

问题1:构建算术表达式二叉树170

问题2:在通信系统中如何使用哈夫曼树压缩信息？173

问题3：莫尔斯码174

习题4179

第5章图183

5.1基本概念183

5.1.1图的定义183

5.1.2图的基本术语183

5.2图的存储结构186

5.2.1邻接矩阵187

5.2.2邻接表188

5.2.3十字链表190

5.2.4邻接多重表191

5.2.5边集数组191

5.2.6图的存储结构比较192

5.3图的实现192

5.3.1图的构建192

5.3.2图的遍历194

5.3.3图的析构198

5.4最小生成树198

5.4.1普里姆算法199

5.4.2克鲁斯卡尔算法203

5.5最短路径207

5.5.1Dijkstra算法208

5.5.2Floyd算法211

5.6工程实践与思考213

问题1:图着色问题213

问题2:地铁换乘线路查找问题217

问题3:教学计划安排问题218

问题4：多层神经网络模型220

习题5229

第6章查找232

6.1基本概念232

6.1.1静态查找和动态查找232

6.1.2查找的性能评估232

6.1.3查找结构分类233

6.2线性表查找233

6.2.1顺序查找233

6.2.2折半查找234

6.2.3索引查找237

6.3树表查找238

6.3.1二叉排序树238

6.3.2平衡二叉树244

6.3.3B-树247

6.3.4STL中的树表——set和map253

6.4散列查找256

6.4.1散列技术256

6.4.2散列函数设计257

6.4.3冲突处理258

6.4.4常用的散列函数261

6.5工程实践和思考263

问题1：自然语言处理的基本问题——中文分词263

问题2：数据库索引结构266

问题3：搜索引擎中的索引结构271

习题6275

第7章排序277

7.1基本概念277

7.1.1相关概念277

7.1.2排序性能评估278

7.1.3排序方法分析278

7.2简单排序279

7.2.1起泡排序279

7.2.2直接插入排序281

7.2.3简单选择排序283

7.3复杂排序285

7.3.1希尔排序285

7.3.2快速排序287

7.3.3堆排序289

7.3.4归并排序293

7.3.5排序方法比较297

7.3.6STL中常用的排序算法298

7.4非比较的排序算法299

7.4.1计数排序299

7.4.2桶排序301

7.4.3基数排序303

7.5工程实践和思考304

问题1：电话号码排序304

问题2：大数据下的排序问题307

习题7311

参考文献313

附录314

附录1异常处理314

附录2模板315