本书不仅是计算机专业重要的专业基础课,也是从事计算机软件开发必备的专业知识。全书共十二章分为四部分,依次介绍了数据结构的基本概念,线性表、栈、串、队列和数组、树结构和图结构,以及查找和排序等基本运算。每章节从实例入手,系统地介绍了各种常用的数据结构,注重实用性,由浅入深,图文并茂,易教易学。本书内容丰富,概念讲解清楚,叙述严谨流畅,逻辑性强。每章均配有小结和思考与练习。本书可作为计算机专业教材和相关培训教材,也可作为从事计算机软件工作人员的参考用书。

计算机科学技术以惊人的速度迅猛发展，它的应用范围已渗入到社会和生活的各个领域。相应地，数据处理的对象也从简单的数值发展到字符、表格和图形等带有结构的数据。在这里要解决的关键问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织数据、处理数据。数据结构就是研究数据以及数据之间关系的一门学科，主要研究数据之间的逻辑结构及其基本操作在计算机中的表示和实现方法。数据结构课程不仅是计算机专业重要的专业基础课，也是从事计算机软件开发所必备的专业知识。
本书主要面向应用型高等学校计算机类专业的学生，培养技术应用型人才；内容的构造力求体现“以应用为主体”，强调理论知识的理解和运用，实现本、专科教学以实践体系为主和以技术应用能力培养为主的目标。
案例教学是计算机课程教学最有效的方法之一，好的案例对学生理解知识、掌握如何应用知识都十分重要。本书围绕教学内容组织案例，对学生的知识和能力训练具有较强的针对性。全书共分12章，可看成4部分：第一部分（第2～6章），介绍基本的线性结构及有关的典型应用；第二部分（第7、8章），讲述具有广泛应用价值的树形结构，这两部分占据了本书的主要篇幅；第三部分（第9、10章），介绍复杂的数据结构，比如图、稀疏矩阵及广义表等；第四部分（第11、12章），介绍有关外存储器中的数据结构和文件组织。此外，书中还有4个附录，分别是：数据结构实训指导、教学实验报告参考格式、课程应用与学习、“数据结构”考试模拟试题。书中的所有程序都在Turbo C 2.0环境下调试通过。
数据结构是实践性很强的课程，本书注重理论与实践相结合，每章都给出了不同层次、不同难度的思考题并且给出参考答案。通过习题与实训，使学生掌握所学知识，并能灵活运用所学知识解决实际问题。
本书带*的章节为专科层次的选讲部分，必讲部分建议授课64学时，其中上机实训安排20学时以上。教师可根据学时数、专业和学生的实际情况选讲带*号部分中一些较难的例子。
本书适合作为高等学校计算机专业学生的教材，也可供广大从事计算机软件工作的科技人员自学参考。
本书由江西科技学院肖守柏、熊蕾、吴金舟担任主编，由中国科学院博士胡剑锋教授担任主审。在本书编写过程中，得到南昌大学信息工程学院计算机科学与技术系姚立文教授的大力帮助，在此表示深深的谢意。本书是江西省省级精品课程“数据结构与算法”的主讲教材，是作者多年教学改革的成果和结晶，教学资源可在http://jpkc.jxbsu.com:8080/kc/datastructure/index. php网站下载。
由于时间仓促，编者水平有限，书中错误和不妥之处在所难免，敬请广大同行和读者批评指正。

编 者
2012年8月

第1章 绪论 1
1.1 数据结构概述 1
1.1.1 学习数据结构的必要性 1
1.1.2 数据结构的基本概念和术语 2
1.1.3 数据类型与抽象数据类型 5
1.2 " HELLO,WORLD!"程序实例 7
1.2.1 C语言的编写风格 7
1.2.2 C语言预备知识 10
1.3 “数组元素排序”实例 12
1.3.1 算法的特性 14
1.3.2 算法的评价标准 14
1.3.3 算法度量及分析 15
小结 18
思考与练习 19
第2章 线性表 21
2.1 “银行排队”顺序存储实例 21
2.1.1 线性表的定义 22
2.1.2 线性表的基本操作 23
2.1.3 顺序表 23
2.2 “学生健康登记”链式存储实例 26
2.2.1 单链表的定义 27
2.2.2 单链表的基本操作 28
2.3 其他链表 31
2.3.1 循环链表 31
2.3.2 双向链表 32
小结 34
思考与练习 34
第3章 栈和队列 37
3.1 “回文”实例 37
3.1.1 栈的定义及基本运算 38
3.1.2 栈的存储实现和运算实现 39
*3.1.3 栈与递归 46
3.2 “杨辉三角形”实例 48
3.2.1 队列的定义及基本运算 50
3.2.2 队列的存储实现和运算实现 50
小结 57
思考与练习 57
第4章 串 59
4.1 串的基本概念 59
4.1.1 串的定义和术语 59
4.1.2 串的基本运算 60
4.2 “文本加密”实例 61
4.2.1 串的顺序存储 63
4.2.2 顺序串的基本运算 64
4.2.3 串的链式存储 68
*4.2.4 模式匹配 68
小结 72
思考与练习 72
第5章 内部排序 74
5.1 排序的基本概念 74
5.2 “学生成绩插入排序”实例 75
5.2.1 直接插入排序 76
5.2.2 希尔排序 78
5.3 “学生成绩交换排序”实例 80
5.3.1 冒泡排序 82
5.3.2 快速排序 84
5.4 “学生成绩选择排序”实例 86
5.4.1 直接选择排序 87
5.4.2 堆排序 89
5.5 其他排序介绍 94
5.5.1 有序序列的合并 94
5.5.2 二路归并排序 95
*5.5.3 基数排序 97
5.6 各种排序的比较 98
小结 100
思考与练习 101
第6章 查找 103
6.1 “学生成绩不及格的查找”实例 103
6.1.1 顺序查找 105
6.1.2 折半查找 106
6.2 “学生成绩及格的查找”实例 108
6.2.1 索引查找的概念 109
6.2.2 分块查找 110
6.3 “学生成绩优秀的查找”实例 111
6.3.1 哈希表与哈希方法 112
6.3.2 哈希函数的构造方法 114
*6.3.3 处理冲突的方法 116
6.3.4 哈希表的查找分析 119
小结 119
思考与练习 120
第7章 二叉树 122
7.1 “高校篮球比赛”实例 122
7.1.1 二叉树的基本概念 124
7.1.2 二叉树的主要性质 124
7.1.3 二叉树的存储 126
7.2 “高校篮球总决赛”实例 128
7.2.1 遍历二叉树 129
7.2.2 线索二叉树的定义及结构 131
7.2.3 线索二叉树的基本操作 131
7.3 “学生成绩及格的查找”实例 133
7.3.1 二叉排序树 134
*7.3.2 平衡二叉树 137
7.4 “报文”实例 142
7.4.1 哈夫曼树的基本概念 144
7.4.2 哈夫曼编码 145
小结 145
思考与练习 146
第8章 树 148
8.1 “高校教师讲课比赛”实例 148
8.1.1 树的定义及相关术语 150
8.1.2 树的表示 151
8.1.3 树的基本操作 152
8.1.4 树的存储结构 152
8.2 “高校教师讲课比赛”实例二 154
8.2.1 树转换为二叉树 156
8.2.2 树的遍历 157
8.2.3 森林 157
*8.3 树表动态查找 159
8.3.1 B-树和B+树 159
8.3.2 键树 165
小结 167
思考与练习 167
第9章 图 169
9.1 “城际铁路”实例 169
9.1.1 图的定义和术语 170
9.1.2 图的存储表示 173
9.2 “游乐园路线”实例 177
9.2.1 图的遍历 178
9.2.2 最小生成树 181
9.2.3 最短路径 186
*9.3 有向无环图的应用 188
9.3.1 拓扑排序 188
9.3.2 关键路径 190
小结 193
思考与练习 193
第10章 数组、矩阵和广义表 196
10.1 “学生考勤的全勤天数”实例 196
10.1.1 数组的逻辑结构 196
10.1.2 数组的内存映像 198
10.2 “学生考勤的放假天数”实例 199
10.2.1 对称矩阵 200
10.2.2 三角矩阵 200
10.3 “学生考勤的请假天数”实例 201
10.3.1 稀疏矩阵的三元组表存储 202
*10.3.2 稀疏矩阵的十字链表存储 205
10.3.3 广义表的定义 209
*10.3.4 广义表的存储 210
10.3.5 广义表的运算 211
小结 212
思考与练习 213
第11章 文件 216
11.1 文件的基本概念 216
11.1.1 文件及其类别 216
11.1.2 文件记录的逻辑结构和物理结构 217
11.1.3 文件组织与操作 217
11.2 顺序文件 218
11.3 散列文件 219
*11.4 索引文件 220
11.4.1 ISAM文件 221
11.4.2 VSAM文件 222
*11.5 多关键字文件 223
11.5.1 多重表文件 224
11.5.2 倒排文件 224
小结 224
思考与练习 225
*第12章 外部排序 227
12.1 外部排序的基本思想 227
12.2 外部排序的方法 228
小结 232
思考与练习 232
附录A “数据结构”实训指导 234
附录B 教学实验报告参考格式 247
附录C 课程应用与学习实验 250
附录D “数据结构”模拟试题 258
各章思考与练习参考答案 266
参考文献 292

主要著译者顺序姓名学历职称学科专长通讯地址1肖守柏 工作单位江西科技学院 邮政编码 电话13870886614 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

“数据结构”不仅是计算机专业重要的专业基础课，也是从事计算机软件开发必备的专业知识。全书共分12章，主要介绍了数据结构的基本概念，线性表、栈、串、队列和数组，树结构、图结构，以及查找和排序等基本运算。每个章节基本上是从实例入手，然后系统地介绍本实例所涉及的知识点。本书注重应用性、由浅入深、逻辑性强，每章后均配有小结和思考与练习。
本书适合作为高等学校计算机专业学生的教材，也可供广大从事计算机软件工作的科技人员自学参考。