本书较系统地介绍了各种典型的数据结构，主要包括：线性表、栈和队列、串、数组、树、图、查找、排序和递归等，为了加强对算法的理解，也介绍了算法分析方面的内容。本书叙述选材精炼、概念清楚、注重实用、逻辑性强，各章中所涉及的数据结构与算法都给出了C语言描述，并都附有大量丰富的习题，便于学生理解与掌握。本书可作为高等院校计算机专业及相关专业的教材，也可作为计算机应用技术人员的参考书。

“数据结构”是计算机类专业的一门必修的、重要的核心基础课。数据是用来说明人类活动的事实观念或事物的一些文字、数字或符号。常用的数据类型分数值数据和非数值数据两大类，数值数据包括整数、定点数、浮点数等，非数值数据主要有逻辑数据、内码和交换码等。数据的级别由低向高依次为位、字节、字、数据项、数据字段、记录、文件、数据库等。
计算机科学是算法和算法变换的科学。数据结构主要是研究数据元素之间的关联方式，通常分为逻辑结构和物理结构两大类，同一逻辑结构可以对应不同的物理结构。程序存储是冯•诺依曼机的重要特征之一，构建计算机系统、利用计算机解决问题都是通过程序来实现。算法是求解问题的计算步骤的描述，算法是程序的核心和灵魂。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。在程序设计中，要从数据结构和算法两个方面考虑，才能得到高效而准确的结果。
在非数值计算中，处理对象已从简单数值发展到具有一定结构的数据，这就需要讨论如何有效地组织计算机的存储，并在此基础上有效地实现对象间的运算。数据结构就是研究与解决这些问题的重要基础。
数据结构是计算机程序设计的重要理论技术基础。通过数据结构课的学习，学生不仅可以掌握数据结构的基本内容、典型算法和使用方法，而且能够训练应用数据结构和算法进行具体应用问题的程序设计。
本书分为10章，介绍最常用的数据结构、各种数据结构的逻辑关系、在计算机中的存储表示，以及在数据结构上的运算等。主要内容包括线性表、栈和队列、串、数组、树、图、查找、排序和递归等内容。
本书在结构上呈积木式，注重实践应用，各种常用数据结构的介绍从实际出发，避免抽象的理论论述和复杂的公式推导，典型的算法介绍深入浅出、简洁明了。每章都设有小结和习题。通过这些习题的练习，不仅能加深学生对基本概念和定义的理解，还能通过上机提高编程能力和程序调试能力。
由于编者水平有限，书中不足之处在所难免，敬请读者批评指正。

陈 明
2012年10月

第1章 概论1
1.1 基本概念与术语1
1.2 数据结构的概念3
1.3 数据的逻辑结构5
1.3.1 数据结构的形式化定义5
1.3.2 数据的逻辑结构类型5
1.4 数据的存储结构6
1.4.1 顺序存储方法6
1.4.2 链式存储方法6
1.4.3 索引存储方法7
1.4.4 散列存储方法7
1.5 数据的运算7
1.6 算法与算法特性8
1.6.1 算法及其特性8
1.6.2 算法的描述方法8
1.6.3 算法与程序及数据结构10
1.7 算法性能分析10
1.8 算法度量11
1.8.1 算法时间复杂度11
1.8.2 复杂度函数的增长率13
小结15
习题115
第2章 线性表16
2.1 线性表定义及其运算16
2.1.1 线性表16
2.1.2 线性表的运算17
2.2 线性表的顺序存储19
2.2.1 顺序存储结构19
2.2.2 顺序结构线性表的运算20
2.2.3 顺序存储结构的特点22
2.3 线性表的链式存储23
2.3.1 线性链表23
2.3.2 线性链表的运算26
2.3.3 循环链表29
2.3.4 循环链表的运算29
2.3.5 双向链表30
2.3.6 双向链表的运算31
2.3.7 链式存储结构的特点32
2.4 链式存储结构的应用33
小结36
习题236
第3章 栈和队列38
3.1 栈38
3.1.1 栈的定义及其运算38
3.1.2 栈的顺序存储结构及其运算的实现39
3.1.3 栈的链式存储结构43
3.2 栈的应用44
3.2.1 子程序的调用问题44
3.2.2 算术表达式求值44
3.3 队列47
3.3.1 队列的定义47
3.3.2 队列的顺序存储47
3.3.3 队列的链式存储52
3.4 队列的应用55
小结56
习题356
第4章 串58
4.1 串的基本概念58
4.2 串的存储结构59
4.2.1 串的静态存储结构59
4.2.2 串的动态存储结构61
4.3 串的基本运算62
4.3.1 常见的基本运算62
4.3.2 实现串的基本运算的算法63
4.4 模式匹配65
4.5 串在文本编辑中的应用67
小结68
习题468
第5章 数组70
5.1 数组及其基本操作70
5.1.1 数组的概念70
5.1.2 数组的基本操作72
5.2 数组的存储结构72
5.3 数组在矩阵运算中的应用75
5.3.1 特殊矩阵的压缩存储75
5.3.2 稀疏矩阵的压缩存储77
小结83
习题583
第6章 树85
6.1 树85
6.1.1 树的定义85
6.1.2 树的常用术语86
6.1.3 树的基本操作87
6.2 二叉树87
6.2.1 二叉树的定义87
6.2.2 二叉树的存储结构89
6.2.3 二叉树的遍历91
6.2.4 二叉树遍历的应用93
6.3 线索二叉树94
6.4 树、森林和二叉树的关系97
6.4.1 树的存储结构97
6.4.2 森林与二叉树的转换100
6.4.3 树和森林的遍历102
6.5 哈夫曼树103
6.5.1 哈夫曼树的定义103
6.5.2 哈夫曼树的构造104
小结105
习题6105
第7章 图108
7.1 图的概念及其操作109
7.1.1 图的概念109
7.1.2 图的基本操作113
7.2 图的存储结构113
7.2.1 邻接矩阵113
7.2.2 邻接表115
7.2.3 十字链表118
7.2.4 邻接多重表119
7.3 图的遍历121
7.3.1 深度优先搜索121
7.3.2 广度优先搜索123
7.4 图的应用124
7.4.1 生成树124
7.4.2 最短路径128
7.4.3 拓扑排序131
7.5 关键路径法133
小结139
习题7139

第8章 查找142
8.1 基本概念142
8.2 线性表的查找143
8.2.1 顺序查找143
8.2.2 折半查找145
8.2.3 分块查找147
8.3 二叉查找树148
8.4 哈希表的查找152
8.4.1 哈希表152
8.4.2 构造哈希表的基本方法153
8.4.3 解决冲突的方法154
8.5 各种查找方法的比较156
小结157
习题8157
第9章 排序159
9.1 基本概念159
9.2 内部排序161
9.2.1 插入排序161
9.2.2 冒泡排序164
9.2.3 快速排序166
9.2.4 选择排序168
9.2.5 归并排序173
9.3 内部排序方法比较176
小结177
习题9177
第10章 递归179
10.1 递归的定义与类型179
10.1.1 递归的定义179
10.1.2 递归的类型179
10.2 递归应用举例180
10.2.1 汉诺塔问题180
10.2.2 八皇后问题182
10.3 递归的实现183
10.4 递归到非递归的转换过程187
10.5 递归的时间和空间复杂度190
小结191
习题10191
参考文献192

主要著译者顺序姓名学历职称学科专长通讯地址1陈明 博士 教授 计算机技术 工作单位 中国石油大学邮政编码 电话 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

本书在结构上呈积木式，注重实践应用、各种常用数据结构的介绍从实际出发，避免抽象的理论论述和复杂的公式推导，在典型的算法介绍中深入浅出、简洁明了。每章都设有小结和习题。通过这些习题的练习，不仅能加深对基本概念和定义的理解，而且通过上机，能够提高编程能力和程序调试能力。