目录

第1章绪论1

1.1数据结构及其相关概念1

1.1.1数据结构讨论范围1

1.1.2定义和术语5

1.1.3抽象数据类型12

1.2算法及其分析15

1.2.1算法和数据结构关系15

1.2.2算法定义16

1.2.3算法描述18

1.2.4算法分析21

1.3程序设计基础27

1.3.1程序和数据结构关系27

1.3.2静态存储和动态存储28

1.3.3结构体类型28

1.3.4输入/输出29

1.3.5引用类型参数29

1.3.6流程控制（分支、循环等）30

1.3.7递归31

1.3.8软件构造31

1.4数据结构的历史与发展32

1.5人工智能的历史与发展34

1.6智能算法应用36

本章小结38

习题38

与前沿技术链接39

科学家精神39

第2章线性表43

2.1线性表的逻辑结构43

2.1.1线性表的定义43

2.1.2线性表的逻辑特征44

2.2线性表的抽象数据类型44

2.3线性表的顺序存储实现45

2.3.1顺序表46

2.3.2顺序表基本运算的实现46

2.3.3顺序表的基础应用49

2.3.4顺序表的智能应用50

2.4线性表的链式存储实现52

2.4.1线性链表53

2.4.2静态链表58

2.4.3循环链表59

2.4.4双向链表60

2.4.5链表的智能应用61

2.5实际中存储结构的选择63

本章小结63

习题63

与前沿技术链接65

科学家精神65

第3章栈与队列67

3.1栈的定义67

3.1.1栈的定义和术语67

3.1.2栈的抽象数据类型68

3.2栈的存储与实现69

3.2.1栈的顺序存储与实现69

3.2.2栈的链式存储与实现70

3.2.3多栈共享的存储与实现70

3.3栈的应用71

3.3.1栈与递归过程71

3.3.2迷宫问题74

3.3.3表达式求值76

3.3.4栈在智能算法中的应用78

3.4队列的定义79

3.4.1队列的定义和术语79

3.4.2队列的抽象数据类型79

3.5队列的存储与实现79

3.5.1队列的链式存储与实现79

3.5.2队列的顺序存储与实现81

3.6队列的应用82

3.6.1约瑟夫出圈问题83

3.6.2舞伴问题83

3.6.3队列在智能算法中的应用84

本章小结85

习题85

与前沿技术链接87

科学家精神87

第4章串90

4.1串的定义90

4.1.1串的定义和术语90

4.1.2串的抽象数据类型91

4.2串的存储与实现92

4.2.1串的顺序存储与实现92

4.2.2串的堆分配存储与实现93

4.2.3串的链式存储与实现94

4.3模式匹配95

4.3.1朴素模式匹配算法95

4.3.2KMP算法——改进的模式匹配算法97

4.4串的智能算法应用102

本章小结103

习题103

与前沿技术链接104

科学家精神106

第5章数组与广义表108

5.1数组的定义108

5.1.1数组的定义和术语108

5.1.2数组的抽象数据类型109

5.2数组的存储与实现109

5.2.1数组的顺序存储109

5.2.2数组的压缩存储111

5.2.3数组的链式存储115

5.3数组的智能算法应用117

5.4广义表的定义118

5.4.1广义表的定义和术语118

5.4.2广义表的抽象数据类型119

5.5广义表的存储与实现120

5.5.1表头表尾分析法120

5.5.2子表分析法120

5.5.3广义表的操作121

5.6广义表的智能算法应用122

本章小结123

习题123

与前沿技术链接124

科学家精神124

第6章树126

6.1树的相关概念126

6.1.1树的定义和术语126

6.1.2树的抽象数据类型127

6.1.3树的应用和表示方法128

6.2二叉树130

6.2.1二叉树的有关概念130

6.2.2二叉树的存储与实现133

6.2.3二叉树的遍历134

6.3线索二叉树141

6.3.1线索二叉树的表示141

6.3.2二叉树的线索化142

6.3.3线索二叉树的遍历144

6.4树和森林145

6.4.1树的存储结构145

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

6.4.3树和森林的遍历150

6.5树的应用152

6.5.1哈夫曼树152

6.5.2判定树160

6.5.3集合的树形结构表示162

6.6树的知识点结构164

6.7树的智能算法应用165

6.7.1决策树165

6.7.2梯度提升树(GBDT)特征工程166

6.7.3树形递归神经网络(Tree Recursive Neural Network)167

6.7.4深度神经网络压缩169

本章小结170

习题170

与前沿技术链接175

科学家精神175

第7章图177

7.1图的相关概念177

7.1.1图的定义和术语177

7.1.2图的抽象数据类型178

7.2图的存储结构179

7.2.1图的顺序存储179

7.2.2图的链式存储181

7.2.3有向图的十字链表存储183

7.2.4无向图的邻接多重表存储184

7.3图的遍历185

7.3.1深度优先遍历185

7.3.2广度优先遍历187

7.4图与树的联系190

7.4.1生成树190

7.4.2无向图与开放树191

7.4.3最小生成树191

7.5无向图的双连通性196

7.5.1无向图的双连通分量196

7.5.2求关节点算法196

7.6有向图的遍历和强连通性198

7.6.1有向图的遍历198

7.6.2强连通性199

7.7有向无环图的应用200

7.7.1拓扑排序200

7.7.2关键路径202

7.8最短路径205

7.8.1单源最短路径205

7.8.2每对顶点间的最短路径207

7.9图的智能算法应用209

7.9.1图与复杂网络209

7.9.2图与社区发现（GirvanNewman算法）210

7.9.3图与推荐系统（协同过滤算法）211

7.9.4盖板瑕疵检测212

7.10图的知识点结构214

本章小结215

习题215

与前沿技术链接221

科学家精神222

第8章查找225

8.1查找的相关概念225

8.1.1查找表的定义和术语225

8.1.2查找表的抽象数据类型225

8.1.3查找的分类226

8.2静态查找226

8.2.1顺序表的查找线性查找226

8.2.2有序表的查找折半查找228

8.2.3索引顺序表的查找分块查找229

8.3动态查找表230

8.3.1二叉排序树230

8.3.2平衡二叉树234

8.3.3B-树和B+树238

8.4哈希表243

8.4.1哈希表的有关概念243

8.4.2哈希函数的构造方法244

8.4.3处理冲突的方法247

8.4.4哈希表的查找和分析248

8.5查找的知识点结构及扩展252

8.5.1跳表252

8.5.2红黑树253

8.6查找的智能算法应用254

8.6.1最近邻查找算法254

8.6.2哈希查找算法255

8.6.3LSH算法256

本章小结257

习题257

与前沿技术链接258

科学家精神259

第9章内部排序262

9.1排序的相关概念262

9.1.1排序的定义和术语262

9.1.2内部排序263

9.2插入排序264

9.2.1直接插入排序264

9.2.2折半插入排序265

9.2.3表插入排序267

9.2.4希尔排序270

9.3冒泡排序和快速排序272

9.3.1冒泡排序272

9.3.2快速排序273

9.4选择排序276

9.4.1简单选择排序276

9.4.2树形选择排序277

9.4.3堆排序278

9.4.4归并排序280

9.4.5基数排序282

9.5排序算法的比较284

9.6排序的智能算法应用285

9.6.1检索模型285

9.6.2推荐系统287

本章小结288

习题289

与前沿技术链接290

科学家精神291

第10章文件与外部排序293

10.1文件及文件操作293

10.1.1文件的相关概念293

10.1.2文件操作294

10.1.3查询方式295

10.1.4文件分类295

10.2文件组织296

10.2.1顺序方式296

10.2.2索引方式298

10.2.3散列方式299

10.2.4链接方式文件和多重链表文件301

10.2.5ISAM文件302

10.2.6VSAM文件304

10.2.7UNIX文件306

10.3磁盘文件的归并分类307

10.4磁带文件的归并分类311

10.5外部排序的智能算法应用312

10.5.1分布式随机梯度下降313

10.5.2联邦学习314

本章小结315

习题315

与前沿技术链接316

科学家精神317