“数据结构”是计算机及信息类相关专业的专业基础课程和核心课程。随着计算机在各个学科领域内的深入应用，本课程也成为其他很多专业的热门选修课程。

由张青编著的《数据结构》主要针对各种数据之间的经典逻辑结构及特点，讨论了数据在计算机中的存储结构及操作实现。通过本书的学习，读者应能够熟练掌握线性表、树、图的逻辑特征，并能根据不同的逻辑关系，采用适当的存储结构，对各种典型运算设计相应的算法；在深入理解和掌握本书内容的基础上，培养自己进行复杂程序设计的能力以及运用基本理论和知识解决实际问题的能力。

由张青编著的《数据结构》首先介绍了数据结构的概念及其逻辑结构、存储结构及运算3方面内容涉及的基本概念，然后针对经典的数据结构（即线性表、栈、队列、多维数组、广义表、树和图）的逻辑特征、常用的存储方式及各种基本运算的实现算法作了详细阐述，最后讨论了两种典型运算——排序和查找的各种实现方法。全书采用C语言作为数据结构和算法的描述工具。在一些重点部分，还给出了简单应用举例的完整c语言程序。

《数据结构》结构清晰、层次分明、深入浅出、通俗易懂、适用面广，可以作为普通高等院校计算机和信息类本科或专科教材，也可以作为其他理工类专业的选修课教材。

第1章　绪论　1

　1.1　数据结构的概念和基本术语　1

　　1.1.1　数据结构简介　1

　　1.1.2　基本术语　3

　　1.1.3　顺序存储结构　7

　　1.1.4　链式存储结构　8

　1.2　算法及评价　9

　　1.2.1　算法的概念及特性　9

　　1.2.2　算法描述　9

　　1.2.3　算法评价　12

　1.3　学习“数据结构”课程的意义　14

　1.4　小结　14

　1.5　习题　15

第2章　线性表　17

　2.1　线性表的定义与基本运算　17

　2.2　线性表的顺序存储结构与实现　19

　　2.2.1　顺序表的初始化　20

　　2.2.2　按值查找　20

　　2.2.3　插入　21

　　2.2.4　删除　22

　2.3　线性表的链式存储结构与实现　23

　　2.3.1　单链表　24

　　2.3.2　静态单链表　30

　　2.3.3　循环链表　32

　　2.3.4　双向链表　33

　2.4　一元多项式的表示和运算　35

　2.5　小结　37

　　2.5.1　主要知识点　37

　　2.5.2　习题类型　38

　2.6　习题　38

第3章　特殊线性表　41

　3.1　栈　41

　　3.1.1　栈的定义及其抽象数据类型　41

　　3.1.2　栈的顺序存储和运算实现　42

　　3.1.3　栈的链式存储和运算实现　47

　3.2　栈的应用　48

　3.3　队列　52

　　3.3.1　队列的定义及其抽象数据类型　52

　　3.3.2　队列的顺序存储和运算实现　53

　　3.3.3　队列的链式存储和运算实现　57

　3.4　队列的应用　59

　3.5　小结　63

　　3.5.1　主要知识点　63

　　3.5.2　习题类型　64

　3.6　练习题　65

　3.7　上机实验题　66

第4章　数组、广义表及字符串　68

　4.1　数组的定义　68

　4.2　数组的顺序存储结构　69

　4.3　特殊矩阵及其压缩存储　70

　　4.3.1　特殊矩阵　70

　　4.3.2　压缩存储　71

　4.4　稀疏矩阵的压缩存储　72

　　4.4.1　稀疏矩阵的三元组顺序表　72

　　4.4.2　稀疏矩阵的转置运算　73

　　4.4.3　稀疏矩阵的十字链表存储　75

　4.5　广义表　78

　　4.5.1　基本概念　78

　　4.5.2　广义表的基本运算　80

　　4.5.3　广义表的头尾存储法　80

　　4.5.4　广义表基本操作的实现　82

　4.6　串的基本概念　83

　4.7　串的存储结构　85

　　4.7.1　串的顺序存储结构　85

　　4.7.2　串的链式存储结构　87

　4.8　小结　88

　4.9　习题　89

　4.10　上机实验题　91

第5章　树与二叉树　92

　5.1　树　92

　　5.1.1　树的定义　92

　　5.1.2　树的基本术语　93

　　5.1.3　树的表示　93

　　5.1.4　树的抽象数据类型　94

　5.2　二叉树　95

　　5.2.1　二叉树的定义　95

　　5.2.2　二叉树的抽象数据类型　96

　　5.2.3　二叉树的性质　97

　　5.2.4　二叉树的存储结构　97

　　5.2.5　二叉树的实现　99

　5.3　二叉树的遍历　101

　　5.3.1　二叉树遍历的递归实现　102

　　5.3.2　二叉树遍历的非递归实现　103

　5.4　线索二叉树　107

　　5.4.1　线索二叉树的基本概念　107

　　5.4.2　线索二叉树的基本操作　108

　5.5　树和森林　113

　　5.5.1　树的存储结构　113

　　5.5.2　树和二叉树的转换　116

　　5.5.3　树和森林的遍历　118

　5.6　哈夫曼树及其应用　119

　　5.6.1　哈夫曼树的基本概念及构造方法　119

　　5.6.2　哈夫曼树的实现　120

　　5.6.3　哈夫曼编码　122

　5.7　小结　124

　　5.7.1　主要知识点　124

　　5.7.2　习题类型　124

　5.8　习题　125

　5.9　上机实验题　126

第6章　图　127

　6.1　图的概述　127

　　6.1.1　图的基本概念　127

　　6.1.2　图的抽象数据类型　130

　6.2　图的存储结构　131

　　6.2.1　图的邻接矩阵存储结构　131

　　6.2.2　图的邻接表存储结构　132

　6.3　图的操作　133

　　6.3.1　邻接矩阵存储结构下图的操作　133

　　6.3.2　邻接表存储结构下图的操作　136

　6.4　图的遍历　141

　　6.4.1　图的深度遍历及其实现　141

　　6.4.2　图的广度遍历及其实现　142

　6.5　最小生成树　143

　　6.5.1　最小生成树的基本概念　143

　　6.5.2　普里姆算法　144

　　6.5.3　克鲁斯卡尔算法　147

　6.6　最短路径　148

　　6.6.1　最短路径的基本概念　148

　　6.6.2　从一个结点到其余各结点的最短路径　148

　　6.6.3　每对结点之间的最短路径　150

　6.7　有向无环图及其应用　153

　　6.7.1　拓扑排序　153

　　6.7.2　关键路径　156

　6.8　小结　160

　　6.8.1　主要知识点　160

　　6.8.2　习题类型　160

　6.9　习题　160

第7章　查找　163

　7.1　基本概念　163

　7.2　静态查找表　164

　　7.2.1　顺序表上的查找　164

　　7.2.2　有序表上的查找　165

　　7.2.3　索引顺序表上的查找　168

　7.3　动态查找表　169

　　7.3.1　二叉排序树　169

　　7.3.2　平衡二叉排序树　175

　　7.3.3　b-树　181

　7.4　散列表　186

　　7.4.1　散列表的概念　186

　　7.4.2　散列函数的构造方法　187

　　7.4.3　处理冲突的方法　189

　　7.4.4　散列表的查找　192

　　7.4.5　散列表的性能分析　193

　7.5　小结　194

　　7.5.1　主要知识点　194

　　7.5.2　习题类型　195

　7.6　习题　195

　7.7　上机实验题　197

第8章　排序　198

　8.1　排序的基本概念　198

　8.2　简单的排序方法　200

　　8.2.1　直接选择排序　200

　　8.2.2　直接插入排序　203

　　8.2.3　冒泡排序　205

　8.3　快速排序　208

　8.4　堆排序　212

　8.5　归并排序　217

　8.6　基数排序　222

　8.7　各种内部排序方法的比较与讨论　229

　8.8　小结　230

　　8.8.1　主要知识点　230

　　8.8.2　习题类型　231

　8.9　习题　231

　8.10　上机实验题　234

参考文献　235