本书从抽象数据类型角度系统介绍数据结构基础理论知识及算法设计方法，在内容选取上符合计算机学科和信息类学科人才培养目标的要求及教学规律和认知规律，在组织编排上体现“先理论、后应用、理论与应用相结合”的原则，并兼顾学科的广度和深度，力求适用面广。
本书特点
●编写目标：定位准确、结构合理、覆盖面广，符合教学规律
●内容知识：概念清楚、循序渐进、深入浅出，便于学生学习
●思考练习：层次分明、紧扣内容、拓宽思路，强化知识理解
●电子教案：立体展示、形象生动、图文并茂，辅助教师教学
●电子教案请登录机工新阅读网站(www.cmpreading.com)下载。
无
“数据结构”是计算机程序设计的重要理论基础，它所讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域及相关领域的其他课程，还是对从事软件工程的实际开发，都有着不可替代的作用。它不仅是计算机学科和信息类学科的核心课程，而且已经成为其他理工专业的热门选修课程。其教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用中涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时空分析技术。从课程学习上讲，“数据结构”的学习是复杂程序设计的训练过程。其教学目的是：着眼于原理与应用的结合，在深化理解和灵活掌握教学内容的基础上，学会把知识用于解决实际问题，书写出符合软件工程规范的文件，编写出结构清晰及正确易读的程序代码。可以说，“数据结构”比“高级程序设计语言”课程有着更高的要求，它注重培养数据抽象能力。本书在内容选取上符合人才培养目标的要求及教学规律和认知规律，在组织编排上体现“先理论、后应用、理论与应用相结合”的原则，并兼顾学科的广度和深度，力求适用面广。
本书共分11章。第1章主要介绍了数据结构的讨论范畴、常用的基本概念和术语，以及算法描述与算法分析；第2章至第8章主要从抽象数据类型的角度介绍了几种常用数据结构，如线性表、栈与队列、串、多维数组、广义表、树与二叉树、图等，分别讨论了它们的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算和在存储结构上实现这些基本运算的方法；第9章主要介绍了插入、交换、选择、归并及基数排序方法的基本思想、排序过程、算法实现、时空性能分析，以及各种排序方法的比较和选择；第10章主要介绍了静态查找表、动态查找表和哈希表的查找方法、算法实现以及各种查找方法的时间性能分析；第11章主要介绍了常用的文件结构及其主要特点、组织方法及查询和更新操作。为了便于理解，本书对数据结构众多知识点的来龙去脉作了详细的解释和说明；每章后面都有算法设计举例，并配有难度各异的适量习题，供读者理解知识及复习提高之用。
本书采用类C语言描述数据结构和操作算法。它是C语言的一个精选子集，同时又采用了C++对C非面向对象的增强功能，例如，动态分配和释放顺序存储结构的空间，利用引用参数传递函数运算的结果等。这些措施使抽象数据类型的定义和数据结构相关操作算法的描述更加简明清晰、可读性更好，既不拘泥于C语言的细节，又容易转换成能够上机执行的C程序或C++程序。
本书可以作为高等院校计算机学科和信息类学科本科和专科教材，也可以作为其他理工专业的选修教材，讲授学时可以为60~80学时。教师可以根据本学校的教学大纲、学时规定、专业特点及学生情况，选讲部分内容。本书结构严谨、层次清楚、概念准确、深入浅出、通俗易懂、便于自学。
由于作者水平有限，在教材中难免有错误，请读者谅解。如果读者有问题需要与作者联系，请发送电子邮件到：pengbo_cau@126.com。
在编写本书的过程中，得到了吴平教授的帮助；参与本书编写的还有孙一林、袁钢、陈昕、邱李华、杨志军、岳乐、张伟娜、王平、徐林等同志，在此表示感谢。
编 者
2007年10月
本书从抽象数据类型角度系统介绍数据结构基础理论知识及算法设计方法，在内容选取上符合计算机学科和信息类学科人才培养目标的要求及教学规律和认知规律，在组织编排上体现“先理论、后应用、理论与应用相结合”的原则，并兼顾学科的广度和深度，力求适用面广。 本书特点 ●编写目标：定位准确、结构合理、覆盖面广，符合教学规律 ●内容知识：概念清楚、循序渐进、深入浅出，便于学生学习 ●思考练习：层次分明、紧扣内容、拓宽思路，强化知识理解 ●电子教案：立体展示、形象生动、图文并茂，辅助教师教学 ●电子教案请登录华章网站(www.hzbook.com)下载。
彭波：暂无
前言
第1章 绪论 1
1.1 数据结构的讨论范畴 1
1.2 数据结构的相关概念 3
1.2.1 基本概念 3
1.2.2 数据结构 4
1.2.3 数据类型 8
1.3 算法描述与算法分析 9
1.3.1 基本概念 9
1.3.2 算法描述 10
1.3.3 算法分析 12
1.4 习题 16
第2章 线性表 18
2.1 线性表的逻辑表示 18
2.1.1 线性表的定义 18
2.1.2 线性表的抽象数据类型 19
2.2 线性表的顺序存储表示与基本操作 19
2.2.1 顺序表 20
2.2.2 顺序表上基本操作的实现 21
2.3 线性表的链式存储表示与基本操作 26
2.3.1 单链表 26
2.3.2 单链表上基本操作的实现 27
2.3.3 循环链表 31
2.3.4 双向链表 33
2.3.5 静态链表 35
2.4 顺序表与链表的比较 36
2.4.1 基于空间的考虑 36
2.4.2 基于时间的考虑 37
2.5 算法设计举例 37
2.6 习题 44
第3章 栈与队列 47
3.1 栈 47
3.1.1 栈的逻辑表示 47
3.1.2 栈的顺序存储表示与基本操作 48
3.1.3 栈的链式存储表示与基本操作 52
3.2 队列 54
3.2.1 队列的逻辑表示 54
3.2.2 队列的顺序存储表示与基本操作 55
3.2.3 队列的链式存储表示与基本操作 59
3.3 算法设计举例 62
3.4 习题 72
第4章 串 75
4.1 串的逻辑表示 75
4.1.1 串的定义 75
4.1.2 串的抽象数据类型 76
4.2 串的顺序存储表示与基本操作 77
4.2.1 静态顺序串 78
4.2.2 动态顺序串 78
4.2.3 顺序串上基本操作的实现 79
4.3 串的链式存储表示与基本操作 84
4.3.1 链串 84
4.3.2 链串上基本操作的实现 85
4.4 串的模式匹配 88
4.4.1 BF算法 88
4.4.2 KMP算法 89
4.5 算法设计举例 93
4.6 习题 98
第5章 多维数组 100
5.1 数组的逻辑表示 100
5.1.1 数组的定义 100
5.1.2 数组的抽象数据类型 101
5.2 数组的顺序存储表示与基本操作 102
5.2.1 数组顺序表 102
5.2.2 数组顺序表上基本操作的实现 104
5.3 矩阵的压缩存储表示与基本操作 106
5.3.1 特殊矩阵 106
5.3.2 稀疏矩阵 110
5.3.3 矩阵压缩存储上基本操作的实现 112
5.4 算法设计举例 119
5.5 习题 122
第6章 广义表 124
6.1 广义表的逻辑表示 124
6.1.1 广义表的定义 124
6.1.2 广义表的抽象数据类型 125
6.2 广义表的链式存储表示与基本操作 126
6.2.1 头尾链表 126
6.2.2 扩展线性链表 127
6.2.3 广义表链式存储上基本操作的
实现 128
6.3 算法设计举例 134
6.4 习题 137
第7章 树与二叉树 139
7.1 树的逻辑表示 139
7.1.1 树的定义 139
7.1.2 树的抽象数据类型 140
7.1.3 树的表示方法 141
7.1.4 树的基本术语 142
7.2 二叉树 143
7.2.1 二叉树与树的关系 143
7.2.2 二叉树的基本性质 144
7.2.3 二叉树的存储表示 147
7.2 4 遍历二叉树 149
7.2 5 线索二叉树 155
7.3 树 160
7.3.1 树的存储表示 160
7.3.2 树与二叉树的转换 164
7.3.3 树的遍历 167
7.4 哈夫曼树及其应用 169
7.4.1 哈夫曼树 169
7.4.2 哈夫曼编码 173
7.5 算法设计举例 177
7.6 习题 188
第8章 图 192
8.1 图的逻辑表示 192
8.1.1 图的定义 192
8.1.2 图的抽象数据类型 192
8.1.3 图的基本术语 193
8.2 图的存储表示与图的构造 197
8.2.1 邻接矩阵 197
8.2.2 邻接表 199
8.2.3 十字链表 200
8.2.4 邻接多重表 202
8.2.5 图的构造 203
8.3 遍历图 206
8.3.1 深度优先遍历 206
8.3.2 广度优先遍历 208
8.4 最小生成树 209
8.4.1 生成树 210
8.4.2 最小生成树 211
8.5 最短路径 217
8.5.1 单源最短路径 217
8.5.2 其他最短路径 219
8.6 拓扑排序 220
8.6.1 拓扑排序的定义 221
8.6.2 拓扑排序的操作 222
8.7 关键路径 224
8.7.1 关键路径的定义 224
8.7.2 关键路径的操作 225
8.8 算法设计举例 227
8.9 习题 230
第9章 排序 234
9.1 基本概念 234
9.2 插入排序 236
9.2.1 直接插入排序 236
9.2.2 希尔排序 237
9.3 交换排序 239
9.3.1 冒泡排序 239
9.3.2 快速排序 240
9.4 选择排序 243
9.4.1 直接选择排序 243
9.4.2 堆排序 244
9.5 归并排序 248
9.5.1 两路归并排序 248
9.5.2 分治法归并排序 249
9.6 基数排序 250
9.6.1 多关键字排序 250
9.6.2 链式基数排序 251
9.7 排序方法比较 254
9.8 算法设计举例 255
9.9 习题 257
第10章 查找 260
10.1 基本概念 260
10.2 静态查找 261
10.2.1 静态查找表的定义与表示 261
10.2.2 顺序查找 262
10.2.3 折半查找 263
10.2.4 分块查找 265
10.3 动态查找 267
10.3.1 动态查找表的定义与表示 267
10.3.2 二叉排序树 268
10.3.3 平衡二叉树 273
10.3.4 B-树 279
10.4 哈希查找 288
10.4.1 哈希表的定义与表示 288
10.4.2 哈希函数的构造方法 290
10.4.3 处理冲突的方法 290
10.4.4 哈希表上的基本操作 293
10.5 算法设计举例 297
10.6 习题 300
第11章 文件 304
11.1 基本概念 304
11.2 顺序文件 306
11.2.1 顺序文件的查找 306
11.2.2 顺序文件的修改 306
11.2.3 顺序文件的特点 307
11.3 索引文件 307
11.3.1 索引文件的分类 307
11.3.2 索引文件的存储 308
11.3.3 索引文件的操作 308
11.3.4 利用查找表建立多级索引 309
11.4 索引顺序文件 309
11.4.1 ISAM文件 309
11.4.2 VSAM文件 312
11.5 哈希文件 313
11.5.1 哈希文件的操作 314
11.5.2 哈希文件的特点 314
11.6 多关键字文件 314
11.6.1 多重表文件 315
11.6.2 倒排文件 316
11.7 文件综合举例 317
11.8 习题 318
参考文献 321
