本书结合作者多年的教学实践，系统地介绍常用的、典型的数据结构（如线性表、栈、队列、串、数组和广义表、树、图等）和算法，并且评估数据结构和算法的有效性以及对各种实用数据结构的代价和效率进行权衡。

本书特点
　　●语言简明流畅，结构清晰合理，内容深入浅出。
　　●采用类C语言描述数据结构和算法，详细地分析了算法设计方法。
　　●每章都设有算法设计举例，每章后附有习题，供读者进一步练习。
　　●附录中设有实验题目，使读者通过实践加深对理论内容的理解。
　　●本书为教师配有电子教案，请登录机工新阅读网站（www.cmpreading.com）下载。

无

第2版前言
“数据结构”是计算机专业的一门专业基础课，也是重要的核心课程之一。随着计算机技术的飞速发展，计算机在各个学科和领域得到了广泛应用，而应用过程中所面临的首要问题就是对于信息量大、种类繁多、结构复杂的数据和数据关系的处理，由此必须设计出好的数据结构，以便有效地实现数据存储、数据传输和数据处理等操作。
数据结构课程主要培养以下几个方面的知识和能力：1）掌握并能根据实际问题灵活应用基本数据结构的抽象数据类型、存储方法和主要算法；2）掌握基本的算法设计和分析技术；3）掌握并能应用常用的排序、查找方法；4）具备一定的调试算法和程序、项目测试的能力。显然，合理地组织数据、有效地表示数据和正确地处理数据，这三者是提高程序设计质量的关键因素。
本书的特点是注意基本概念的引入和阐述，注重算法设计的分析方法，强调实践环节的重要性。本书的第1版已由机械工业出版社于2004年出版，经过几年的教学使用和实践，同时也结合该课程的发展，本书第2版对书中的部分内容进行了修改。本教材沿用了第1版教材的算法描述方式，即采用类C语言的描述方法。
考虑到初学者对算法设计问题普遍感到比较困难，思路不明确，本书每一章都设有算法设计举例，旨在提高初学者的算法分析和设计能力。每章之后附有习题，以便读者进一步练习并检验学习效果。鉴于本课程是实践性较强的一门课程，本教材在附录中设立了实验题目，以便使读者在掌握理论内容的同时，通过实践环节加深理解。
本书由长期从事数据结构课程教学的教师编写，总结了作者多年的教学实践经验。本书尽量合理地安排内容顺序，教师可以根据内容需要自由地重新组织内容。
本书可作为高等院校计算机及相关专业的教材、参考书和考研辅导，同时也可供计算机科学及工程技术人员参考。对于计算机科学与技术专业，可讲授64学时，对于其他专业，可去掉带星号的章节，讲授48学时。
由于工作的变动，本书第2版重新组织了编写人员，对于第1版的作者表示衷心感谢。
本书第1章由武秀川同志编写，第2、3章由陈守孔同志编写，第4、10章由胡潇琨同志编写，第5、9章由孟佳娜同志编写，第6、8章由陈卓同志编写，第7、11章由张东娜同志编写。孟佳娜同志校阅了各章，并编写了实验题目，陈守孔同志编写了各章习题并对全书统稿定稿。陈卓、孟佳娜和陈守孔同志提供了本书的电子教案。
本书的出版得到机械工业出版社温莉芳女士和王春华编辑的大力支持，在此深表感谢。
由于作者水平有限，加上计算机科学技术的发展十分迅速，书中难免有不妥和挂一漏万之处，恳请广大读者赐教。陈守孔的电子信箱是：skcnmu@163.com, 孟佳娜的电子信箱是：ytumengjn@163.com, 武秀川的电子信箱是：wxc225@126.com。

编　　　者
2007年10月

陈守孔 孟佳娜 武秀川 等：暂无简介

第1版前言
第2版前言
第1章　 概论 1
1.1　 什么是数据结构 1
1.2　 数据结构的基本概念和术语 3
1.3　 抽象数据类型及其表示与实现 6
1.4　 算法和算法分析 9
1.4.1　 算法的定义及特性 9
1.4.2　 算法的设计要求 9
1.4.3　 算法效率的衡量方法及其准则 10
1.4.4　 算法的存储空间需求 13
1.5　 类C语言描述 14
习题 15
第2章　 线性表 17
2.1　 线性表的类型定义　 17
2.1.1　 线性表的概念 17
2.1.2　 线性表的抽象数据类型 18
2.2　 线性表的顺序表示和实现 21
2.2.1　 线性表的顺序表示 21
2.2.2　 顺序表上基本运算的实现 21
2.3　 线性表的链式表示和实现 25
2.3.1　 单链表的表示 25
2.3.2　 单链表操作的实现 27
2.4　 线性表实现方法的比较 33
2.5　 循环链表 34
2.6　 双链表 35
*2.7　 静态链表 36
*2.8　 算法设计举例 38
习题 42
第3章　 栈和队列 44
3.1　 栈 44
3.1.1　 栈的类型定义 44
3.1.2　 栈的表示和实现 45
3.2　 栈的应用举例 49
3.3　 栈与递归 51
3.3.1　 如何实现递归 52
3.3.2　 采用递归算法解决的问题 52
3.3.3　 将递归转换为非递归 54
3.4　 队列 56
3.4.1　 队列的类型定义 56
3.4.2　 循环队列—队列的顺序存储结构 57
3.4.3　 链队列—队列的链式表示和实现 60
*3.5　 算法设计举例 62
习题 64
第4章　 串 67
4.1　 串的类型定义 67
4.2　 串的表示和实现 68
4.2.1　 串的顺序存储结构 69
4.2.2　 串的链式存储结构 70
4.3　 串的模式匹配 71
4.3.1　 朴素的模式匹配算法 71
4.3.2　 KMP算法 72
4.4　 串的应用举例 74
*4.5　 算法设计举例 75
习题 77
第5章　 数组和广义表 79
5.1　 数组的概念及其基本操作 79
5.2　 数组的顺序存储 80
5.3　 矩阵的压缩存储 81
5.3.1　 特殊矩阵　 81
5.3.2　 稀疏矩阵 83
5.4　 广义表 91
5.4.1　 广义表的定义 91
5.4.2　 广义表的存储结构 92
*5.5　 算法设计举例 94
习题 96
第6章　 树 98
6.1　 树的概念及操作 98
6.2　 二叉树 100
6.2.1　 二叉树的概念及操作 100
6.2.2　 二叉树的性质 102
6.2.3　 二叉树的存储结构 104
6.3　 二叉树的遍历 105
*6.4　 线索二叉树 108
6.4.1　 线索二叉树的概念 108
6.4.2　 遍历线索二叉树 110
6.5　 树和森林 112
6.5.1　 树的存储结构 112
6.5.2　 森林、树、二叉树的相互转换 114
6.5.3　 树和森林的遍历 116
6.6　 哈夫曼树及其应用 117
6.6.1　 最优二叉树（哈夫曼树） 117
6.6.2　 哈夫曼编码 119
*6.7　 算法设计举例 121
习题 124
第7章　 图 128
7.1　 图的定义和术语 128
7.2　 图的存储结构 131
7.2.1　 邻接矩阵表示法（数组表示法） 131
7.2.2　 邻接表 132
7.2.3　 十字链表 134
7.2.4　 邻接多重表 135
7.3　 图的遍历 136
7.3.1　 深度优先遍历 136
7.3.2　 广度优先遍历 138
7.4　 图的连通性问题 139
7.4.1　 图的连通分量和生成树 139
7.4.2　 最小生成树 140
7.5　 有向无环图及其应用 144
7.5.1　 拓扑排序 144
7.5.2　 关键路径 146
7.6　 最短路径 150
7.6.1　 从某个源点到其他各顶点的最短
路径 150
7.6.2　 每一对顶点之间的最短路径 152
*7.7　 算法设计举例 154
习题 157
第 8章　 动态存储管理 160
8.1　 概述 160
8.1.1　 问题的提出 160
8.1.2　 内存分配处理 161
8.2　 可利用空间表及分配办法 161
8.2.1　 可利用空间表的三种不同的结构
形式 162
8.2.2　 可利用空间表的三种分配策略 163
8.3　 边界标识法 164
8.3.1　 可利用空间表的结构 164
8.3.2　 分配算法 165
8.3.3　 回收算法 167
8.4　 伙伴系统 169
8.4.1　 可利用空间表的结构 169
8.4.2　 分配算法 170
8.4.3　 回收算法 171
习题 171
第9章　 查找 173
9.1　 静态查找表上的查找 174
9.1.1　 顺序表的查找 174
9.1.2　 折半查找 175
9.1.3　 斐波那契查找 178
9.1.4　 插值查找 179
9.1.5　 分块查找 180
9.2　 动态查找表上的查找 182
9.2.1　 二叉排序树 182
9.2.2　 平衡二叉树 186
*9.2.3　 B-树 194
*9.2.4　 键树 199
9.3　 散列表上的查找 199
9.3.1　 散列表的概念 199
9.3.2　 构造散列函数的方法 200
9.3.3　 解决冲突的方法 202
9.3.4　 散列表的查找性能分析 206
9.3.5　 闭散列法与开散列法的比较 207
*9.4　 算法设计举例 207
习题 210
第10章　 排序 213
10.1　 概述 213
10.2　 插入排序 214
10.2.1　 直接插入排序 214
10.2.2　 折半插入排序 216
10.2.3　 二路插入排序 216
*10.2.4　 表插入排序 218
10.2.5　 希尔排序 220
10.3　 交换排序 221
10.3.1　 起泡排序 221
10.3.2　 快速排序 222
10.4　 选择排序 224
10.4.1　 直接选择排序 225
10.4.2　 树形选择排序 226
10.4.3　 堆排序 226
10.5　 归并排序 229
10.6　 分配排序 230
10.7　 各种内部排序方法的比较 234
10.8　 外部排序 235
10.8.1　 文件管理 235
10.8.2　 外部排序的方法 236
10.8.3　 多路平衡归并排序 237
10.8.4　 置换选择排序 239
10.8.5　 最佳归并树 242
*10.8.6　 磁带排序 243
*10.9　 算法设计举例 244
习题 246
第11章　 文件 249
11.1　 基本概念 249
11.2　 顺序文件 251
11.3　 索引文件 253
11.4　 索引顺序文件 254
11.4.1　 ISAM文件 254
11.4.2　 VSAM文件 257
11.5　 散列文件 259
11.6　 多关键字文件 259
11.6.1　 多重表文件 260
11.6.2　 倒排文件 260
习题 261
附录　 上机实验题目 262
参考文献 264