[正版新书]数据结构原理与应用(第2版)徐慧、周建美、丁红、朱玲玲、王皓晨 清华大学出版社 数据库

本书在选材与编排上，秉持“五可”原则——“可读”“可学”“可用”“可研”“可练”。全书共9章，在保留第1版的8章经典内容——绪论、线性表、栈和队列、数组和矩阵、树和二叉树、图、查找与排序的基础上，新增第9章“分布与并发数据结构”，以紧跟技术发展趋势。全书有118个算法、80余道应用与示例、300余道练习题、83个微课视频。应用案例涉及数据结构在工程计算、大数据、操作系统、大数据及人工智能等各方面的应用。练习题题型包括填空题、简答题、应用题、算法设计题、上机练习题、AI开放题等，满足学生原理理解、知识应用、模仿与创新、算法训练、实践应用、素养提高等多方面需求。每章小结给出全章知识结构图以及相关算法与应用汇总。微课视频总时长约700分钟，覆盖前8章内容。

本书将经典理论与前沿技术结合，内容编排新颖，图文并茂，配套资料齐全（包含微课、源码、实践教程与学习指导等）。原理叙述直达要义、算法步骤与伪码一一对应、应用示例广泛且富有启发性。

本书不仅适合作为高等学校计算机及相关专业“数据结构”课程的教材，也非常适合从事计算机软件开发与应用的工程技术人员作为参考书籍。

简言之，这是一本“可读”、“可学”、“可用”、 “可研”、 “可练”的教材。

  （1）可读：概念及原理等新知识的介绍，首以文字陈述，并做到精准、简明、扼要，直明要义；后以示例展示，将概念及原理具化，使知识一目了然。所有内容，尽可能图文并茂。本教材选用“C/C++”语言，但不拘泥于两者的严格语法，以可验证实现为界，集两者优点呈现“算法”。

  （2）可学：首先，在算法描述上，教材选用了对学习者要求较低的面向过程的方法，但会借用模板概念解决数据类型的抽象性问题。为进一步简化语法部分，突出问题求解本身，本教材采用南向过程的算法描述，降低学习难度。其次，各种结构都有丰富的应用背景，以学生希冀获取“解决问题”的方法及“学得可用知识与技能”的本能愿望，用问题打开一个个典型结构的篇章，用应用示例展示知识的应用。学生通过理解、记忆、验证、模仿、思考，能切实感到收获。

  （3）可教：首先用实际教学中积累的讲课思路，设计与组织教材内容。采用算法描述与步骤结合在一起的方式，突显设计的关系。教材大量的图示及应用示例，为教师教学提供了大量的教学素材，教辅PPT将尽量展示算法执行过程。并且，通过【算法讨论】的设置，拓展教学深度与广度。

  （4）可研。许多算法介绍后，设置了【算法讨论】，提出相关问题或更深层次的问题，引导思考与研究，开启新探究的启点。例如（1）：给出另一种解决方法的要点，引导学生进行深思与对比。例如（2）：在用顺序表实现“一元多项式求和问题”中，在【算法讨论】中抛出一元稀疏多项求和的问题，为后续新知识进行铺垫，增加教材内容的连贯性。

   （5）可练。教材配套教材提供多层次的练习素材。（1）验证与模仿：教材中有大量的算法，第二章线性表的相关算法如图2所示。教材配套资源将给出教材中所有算法的源码；（2）设计与创新，通过【应用示例】、【算法讨论】和习题，给出触类旁通的问题和有延扩的问题。

    总之，这是一本充分考虑“新工科”人才培养需要和“工程专业认证”对计算机类学生的毕业要求，以“可用”、“实用”为目标，设计与编写的一部具有时代气息的教材。

目录

第1章绪论1

1.1课程属性与术语1

1.1.1数据结构是程序的

重要组成部分1

1.1.2数据结构是提升

编程能力的必备 …2

1.1.3数据结构与术语 …2

1.1.4数据结构决定

算法4

1.2数据结构的研究内容4

1.2.1逻辑结构5

1.2.2存储结构/物理

结构6

1.2.3逻辑结构与物理

结构的关系7

1.2.4非数值计算问题 …8

1.2.5数据结构与程序

设计的关系10

1.3抽象数据类型11

1.3.1抽象数据类型的

定义11

1.3.2抽象数据类型的

实现12

1.4算法与算法分析13

1.4.1算法的概念13

1.4.2算法描述13

1.4.3算法性能分析15

1.5数据结构的重要性与

应用20

1.5.1数据结构的重

要性20

1.5.2数据结构的应用

实例23

1.6小结24

习题125

第2章线性表29

2.1线性表的定义29

2.1.1线性表的逻辑

特性29

2.1.2线性表的抽象数据

类型30

2.2顺序表32

2.2.1顺序表的定义……32

2.2.2顺序表的存储

设计33

2.2.3顺序表的操作及

实现34

2.2.4顺序表应用举例 …40

2.3链表42

2.3.1单链表的定义及

特性42

2.3.2单链表的存储

设计432.3.3单链表的操作及实现44

2.3.4其他形式的链表52

2.3.5链表应用举例56

2.4顺序表与链表的比较60

2.4.1空间性能比较60

2.4.2时间性能比较60

2.4.3环境性能比较60

2.5线性表在大数据处理中的

应用61

2.5.1日志处理61

2.5.2数据预处理与数据清洗 …61

2.5.3数据缓存62

2.5.4数据索引62

2.6小结63

习题264

第3章栈和队列69

3.1栈69

3.1.1栈的定义和特点69

3.1.2顺序栈71

3.1.3链栈75

3.1.4顺序栈和链栈的比较78

3.1.5栈的应用78

3.2队列85

3.2.1队列的定义和特点85

3.2.2循环队列86

3.2.3链队90

3.2.4循环队列与链队列的

比较94

3.2.5队列的应用94

3.3栈与队列在操作系统中的

高级应用96

3.3.1进程调用栈和系统调

用栈96

3.3.2进程调度96

3.3.3内存管理97

3.3.4并发控制98

3.4小结99

习题399

第4章数组和矩阵103

4.1多维数组103

4.1.1数组的定义103

4.1.2数组的顺序存储105

4.2特殊矩阵107

4.2.1对称矩阵107

4.2.2三角矩阵108

4.2.3对角矩阵109

4.3稀疏矩阵110

4.3.1三元组表顺序存储110

4.3.2带行指针向量的链式

存储113

4.3.3十字链表116

4.4数组与矩阵在工程计算中的

应用116

4.4.1结构工程中的力学分析 …117

4.4.2信号处理117

4.4.3图像处理118

4.4.4控制系统设计119

4.4.5电子电路仿真与设计119

4.4.6天气预报与气候建模120

4.4.7金融工程与风险管理121

4.5小结121

习题4122

第5章树和二叉树125

5.1树126

5.1.1树的定义与表示126

5.1.2树的术语127

5.1.3树的抽象数据类型128

5.1.4树的存储设计129

5.1.5树和森林的遍历132

5.2二叉树的定义与特性133

5.2.1二叉树的定义133

5.2.2特殊二叉树134

5.2.3二叉树的性质135

5.2.4二叉树的抽象数据类型…137

5.3二叉树的存储结构138

5.4二叉树操作140

5.4.1二叉树遍历140

5.4.2根据遍历序列确定二

叉树148

5.4.3先、中、后序遍历的非递归

算法150

5.4.4二叉树的其他操作155

5.5线索二叉树158

5.5.1线索二叉树的定义158

5.5.2线索二叉树的建立159

5.5.3线索二叉树的遍历161

5.6树和森林与二叉树的相互

转换164

5.6.1树与二叉树相互转换……164

5.6.2森林与二叉树相互转换…166

5.7最优二叉树及其应用167

5.7.1基本概念167

5.7.2构造最优二叉树168

5.7.3哈夫曼编码173

5.8树结构在机器学习中的应用

举例176

5.8.1决策树及其应用176

5.8.2随机森林及其应用179

5.8.3自然语言处理180

5.9小结181

习题5182

第6章图187

6.1图的定义及相关术语187

6.1.1图的定义187

6.1.2图的术语188

6.1.3图的抽象数据类型191

6.2图的存储及操作193

6.2.1邻接矩阵表示法及操作

举例193

6.2.2邻接表表示法及操作

举例197

6.2.3十字链表表示法及操作

举例200

6.2.4邻接多重表表示法及

操作举例202

6.3图的遍历及应用204

6.3.1深度优先遍历204

6.3.2广度优先遍历207

6.3.3遍历应用举例210

6.4图的应用213

6.4.1最小生成树213

6.4.2最短路径219

6.4.3AOV网与拓扑排序225

6.4.4AOE网与关键路径230

6.5图结构在现代技术中的

应用举例234

6.5.1社交网络分析234

6.5.2交通规划236

6.5.3互联网链接分析236

6.6小结237

习题6238

第7章查找243

7.1查找的基本概念243

7.1.1术语243

7.1.2查找性能244

7.2线性表查找技术245

7.2.1顺序查找245

7.2.2折半查找246

7.2.3串的模式匹配248

7.3树表查找254

7.3.1二叉排序树254

7.3.2平衡二叉树261

7.4散列查找265

7.4.1散列函数的构造方法……266

7.4.2处理冲突的方法268

7.4.3散列表的查找270

7.5查找算法在搜索技术中的

应用272

7.5.1文档检索273

7.5.2数据库查询273

7.5.3字符串匹配274

7.5.4Web搜索引擎274

7.5.5地理信息系统275

7.6小结276

习题 7277

第8章排序279

8.1排序的基本概念279

8.1.1排序的定义279

8.1.2内排序与外排序280

8.1.3排序性能281

8.1.4内部排序方法的分类281

8.1.5待排序记录的存储方式…282

8.2插入排序282

8.2.1直接插入排序283

8.2.2折半插入排序285

8.2.3希尔排序286

8.3交换排序288

8.3.1冒泡排序288

8.3.2快速排序290

8.4选择排序294

8.4.1简单选择排序295

8.4.2树形选择排序296

8.4.3堆排序298

8.5归并排序303

8.6基数排序306

8.6.1分配排序306

8.6.2多关键码排序306

8.6.3基数排序详解3088.7各种排序方法的比较310

8.7.1性能比较310

8.7.2方法选用311

8.8排序技术应用举例312

8.8.1数据库管理系统313

8.8.2电子商务313

8.8.3生物信息学314

8.8.4文件系统314

8.8.5操作系统调度315

8.9小结316

习题8316

第9章分布与并发数据结构319

9.1分布式数据结构319

9.1.1分布式系统基本概念……319

9.1.2分布式数据结构及其

应用323

9.2并发数据结构328

9.2.1并发系统基本概念328

9.2.2并发数据结构及其应用…331

9.3分布与并发数据结构应用

案例333

9.3.1大规模分布式存储系统…333

9.3.2分布式文件系统335

9.3.3区块链技术中的分布式

数据结构338

9.4小结341

习题9341

附录术语表342

参考文献346