本书是一部针对高等学校新工科计算机类专业的实用性教材，采用易于学习和使用的C语言来描述算法，并加以详细注释，重点知识配备了二维码视频讲解，可读性好、实用性强。对于不熟悉C语言而熟悉其他任何一种计算机语言的学习者来说，只要掌握了本书中详细介绍的数据结构及其运算方法，一样能够编写出相应语言的算法描述和上机程序。本书共分为10章，主要包括集合、线性表、栈和队列、树和二叉树、二叉树应用、图、图的应用、查找以及排序等内容。
本书适合作为普通高校计算机及相关专业“数据结构”课程的教材，也可供相关证书考试、考研或从事计算机应用与工程工作的科技工作者参考。

       数据结构是计算机及其相关专业的一门核心骨干课程，主要讨论数据的逻辑结构和存储结构，以及对数据的运算、算法（运算方法和过程）和在计算机系统上的实现（算法执行）。数据的逻辑结构简称数据结构，它是对数据进行有效组织的各种联系方式（方法），总体上有集合结构、线性结构、树形结构、图结构等四种基本结构，以及在基本结构基础上构造出来的各种各样的组合结构。人们在利用计算机进行数据处理时，可以根据需要选用任一种合适的数据结构来组织数据。
      算法就是在数据结构的基础上对数据进行相应运算的方法和过程，思考和解决问题（即如何运算）的思路不同，设计出来的算法也不同，在计算机上执行的快慢程度也不同。当然，如果设计出的算法是正确和有效的，通过执行就能够得到正确的数据处理结果。
      算法并不是一个新鲜的名词，是一直存在着的，在以前传统社会，对数据进行运算的各种算法都是通过手工计算完成的，只有进入现代计算机和信息社会时代，算法才得以在计算机上执行。当然其传统算法也要根据在计算机上执行的需要而做出相应的修改和变化。
      要使自己设计出的算法能够在计算机上执行，必须借助一种计算机语言作为工具，将其编写成相关的程序代码。本书利用C语言作为其算法设计语言，编写出相应的函数定义模块，进而通过函数调用实现其算法功能。算法在计算机上执行时，其待处理的数据来自计算机存储系统中存储的数据，所以现实生活中的数据，包括其选用的数据结构，还必须事先按照一定的存储方法（存储结构），使之有效地保存到计算机存储器中，供算法执行时访问和处理，算法处理结果也需要保存到计算机存储器中，或打印输出供用户使用。
学习“数据结构”课程的目的是要学会根据数据处理问题的需要，选择合适的数据结构和存储结构，根据相应的运算设计出算法，进而编写出相应的程序代码，并在计算机上执行（运行）后得到处理结果。
      本书按照“‘十四五’高等学校新工科计算机类专业系列教材”总体编写规划的要求编写，适合作为普通高校“数据结构”课程的教材。
      本书符合课程自身学科特点，注重突出其实用性、简明性、系统性和基础性，让学生能够收到学以致用、事半功倍的良好效果。
      本书共分为10章。第1章讨论数据的各种基本数据结构，算法的定义以及评价标准等内容，为学习后续各章内容做好准备和铺垫。第2章讨论数据的集合结构，以及相应运算、存储结构和算法实现（即编写代码）。第3章讨论数据的线性结构（线性表），以及相应运算、存储结构和算法实现。第4章讨论数据的栈结构和队列结构（它们都是线性数据结构中的特殊结构），以及它们的运算、存储结构和算法实现。第5章讨论树形结构和其中典型的二叉树结构，以及它们的运算、存储结构和算法实现。第6章讨论二叉树的应用，列举了搜索二叉树、堆和哈夫曼树的定义、运算和相应的算法实现。第7章讨论数据的图结构和运算，以及相应的存储结构和算法实现。第8章讨论图的具体应用，其中包括求一个图的最小生成树、最短路径、拓扑排序和关键路径。第9章讨论对数据进行的各种查找方法和算法，主要有二分查找、索引查找、散列查找和B树查找等。第10章讨论对数据进行的各种排序方法和算法，主要有堆排序、快速排序、归并排序、外存数据文件排序等。
      编者精心编写本书，力求本书内容比同类教材更加系统规范，更加简明实用。由于编者能力所限，错误和不足之处在所难免，敬请广大同行和读者批评指正！
本书中所有习题的详细解答及课件等资源可以在中国铁道出版社教育资源数字化平台 （https://www.tdpress.com/51eds/）免费下载。另外，还可以通过QQ号（771229083）与编者联系。

徐孝凯

2023年3月

第1章绪论 1

1.1数据结构的有关概念 2

1.2算法描述 10

1.3算法评价 11

思考与练习 17

第2章集合 22

2.1集合的定义和抽象数据类型 23

2.2集合的顺序存储结构和操作实现 24

2.2.1集合的顺序存储结构和存储类型定义 24

2.2.2集合运算在顺序存储结构下的操作实现 25

2.2.3对顺序集合进行各种运算的程序示例 29

2.3集合的链式存储结构和操作实现 30

2.3.1链式存储集合的有关概念 30

2.3.2集合运算在链式存储结构下的操作实现 32

2.3.3对链式存储集合进行各种运算的程序示例 36

思考与练习 38

第3章线性表 42

3.1线性表的定义和抽象数据类型 43

3.2线性表的顺序存储结构和操作实现 44

3.3链式存储数据的概念和方法 51

3.4线性表的每种运算在单链表上的操作实现 55

思考与练习 61

第4章栈和队列 65

4.1栈的定义和抽象数据类型 66

4.2栈的顺序存储结构和操作实现 67

4.3栈的链式存储结构和操作实现 70

4.4栈的简单应用举例 72

4.5队列 76

4.5.1队列的定义和抽象数据类型 76

4.5.2队列的顺序存储结构和操作实现 77

4.5.3队列的链式存储结构和操作实现 80

4.5.4队列的应用简介 83

4.6算术表达式的计算 84

4.6.1算术表达式的两种表示 84

4.6.2后缀表达式求值的算法 85

4.6.3把中缀表达式转换为后缀表达式的算法 87

4.7栈与递归 90

4.7.1阶乘求解的递归算法 91

4.7.2求解迷宫问题的递归算法 92

4.7.3求解汉诺塔问题的递归算法 96

思考与练习 98

第5章树和二叉树 103

5.1树的概念 104

5.1.1树的定义 104

5.1.2树的表示 105

5.1.3树的基本术语 106

5.1.4树的性质 107

5.2二叉树 108

5.2.1二叉树的定义 108

5.2.2二叉树的性质 108

5.2.3二叉树的抽象数据类型 110

5.2.4二叉树的存储结构 110

5.3二叉树遍历 113

5.4二叉树其他运算 115

5.5树的存储结构和运算 122

5.5.1树的抽象数据类型 122

5.5.2树的存储结构 122

5.5.3树的运算 123

思考与练习 129

第6章二叉树应用 134

6.1二叉搜索树 135

6.1.1二叉搜索树的定义 135

6.1.2二叉搜索树的抽象数据类型 135

6.1.3二叉搜索树的运算 136

6.1.4二叉搜索树运算的应用程序示例 140

6.2堆 142

6.2.1堆的定义 142

6.2.2堆的抽象数据类型 143

6.2.3堆的存储结构 143

6.2.4堆的运算 144

6.2.5堆运算的应用程序示例 147

6.3哈夫曼树 148

6.3.1基本术语 148

6.3.2构造哈夫曼树 149

6.3.3哈夫曼编码 151

思考与练习 154

第7章图 157

7.1图的概念 158

7.1.1图的定义 158

7.1.2图的基本术语 159

7.1.3图的抽象数据类型 161

7.2图的存储结构 161

7.2.1邻接矩阵 162

7.2.2邻接表 164

7.2.3边集数组 166

7.3图的遍历 168

7.3.1深度优先搜索遍历 168

7.3.2广度优先搜索遍历 171

7.3.3非连通图的遍历 174

7.3.4图的遍历算法的上机调试 174

7.4图的其他运算 177

思考与练习 189

第8章图的应用 192

8.1图的生成树和最小生成树 193

8.1.1生成树和最小生成树的概念 193

8.1.2普里姆算法 194

8.1.3克鲁斯卡尔算法 198

8.2最短路径 201

8.2.1最短路径的概念 201

8.2.2从图中一顶点到其余各顶点的最短路径 202

8.2.3图中每对顶点之间的最短路径 207

8.3拓扑排序 211

8.3.1拓扑排序的概念 211

8.3.2拓扑排序算法 212

8.4关键路径 216

思考与练习 222

第9章查找 226

9.1查找的概念 227

9.2顺序表查找 228

9.2.1顺序查找 228

9.2.2二分查找 229

9.3索引查找 233

9.3.1索引的概念 233

9.3.2索引查找算法 236

9.3.3分块查找 238

9.4散列查找 240

9.4.1散列的概念 240

9.4.2散列函数 241

9.4.3处理冲突的方法 243

9.4.4散列表的运算 246

9.5B树查找 252

9.5.1B树定义 252

9.5.2在B树上查找元素的过程 254

9.5.3在B树上插入元素的过程 255

9.5.4在B树上删除元素的过程 257

思考与练习 258

第10章排序 262

10.1排序的基本概念 263

10.2插入排序 264

10.2.1直接插入排序 264

10.2.2希尔排序 265

10.3选择排序 266

10.3.1直接选择排序 266

10.3.2堆排序 267

10.4交换排序 271

10.4.1气泡排序 271

10.4.2快速排序 272

10.5归并排序 276

10.6各种内排序方法的比较 281

10.7外排序 282

10.7.1外排序的有关概念 282

10.7.2外排序算法 284

10.7.3外排序应用程序运行示例 287

思考与练习 290

徐孝凯，男，国家开放大学教授（退休），主要承担数据结构、数据库、软件工程等多门课程的教学（包括主编、电视主讲、课堂面授等）工作。先后在清华大学等多家出版社策划组织编写过多套计算机本科教材，参与国家开放大学的计算机远程教育和多媒体教育等相关课题的研究工作，参与教育部考试中心有关等级考试课程和教育部全国高校计算机网络统一考试课程的试题库研究与建设工作。

（1）内容系统全面，图文并茂，用多幅图表述和讲解数据的组织结构与算法设计思想，力求归纳知识点之间的联系，总结各类算法设计的规律。

（2）书中所有算法均调试通过。

（3）重要知识点配有二维码视频，方便读者学习。