本书选用ANSI C 描述数据结构的实现，是数据结构实现方面的经典教科书和专业参考书。
　　书中详细讨论栈、队列、链表以及查找结构、高级的树结构等功能，对斐波那契堆、伸展树、红黑树、2-3树、2-3-4树、二项堆、最小-最大堆、双端堆等新的数据结构进行了有效分析。

　　本书特点：
　　●计算机理论和计算机编程实践相结合
　　●各章节共汇聚400多道习题，难易兼顾
　　●运用易于理解的图表充分展示与分析数据结构的原理

无

本书为什么用C语言作为描述语言呢？有以下几个方面的原因：首先，也是最重要的原因，是因为C语言已逐渐成为目前教师授课的首选语言。当然，这与目前C语言已经是个人计算机（PC和Mac）和UNIX工作站的主要开发语言有很大关系。另一个原因是C编译器和C程序开发环境已发展得较为成熟，可以很好地帮助C语言新手学习和使用。最后一个原因是在计算机科学的编程领域中使用的许多概念，诸如虚拟内存、文件系统、解析器的自动生成、词法分析器以及网络等，都是用C实现的。因此，目前C语言在大学教学规划中开设得较早，其目的就是为学生能够充分理解后来要学的计算机基本概念做准备。
　　本书中出现的程序选用ANSI C描述。ANSI C作为C语言的扩展于1983年正式使用，它支持早期版本所不支持的某些特征，如，它支持在函数头部定义类型信息，这一特征在提高程序的可靠性之外也增加了程序的可读性。作为ANSI C的替代，也有的教师选用Kernighan和 Ritchie设计的C语言（简称K&R C）。该C语言是在他们1978年编写的书《C语言程序设计》中公布的。对于采用K&R C的教师，本书的附录中讨论了如何将本书编写的程序更改到K&R C环境下运行。其实两者的差别是很小的，更改是很容易的，因此，两者的差别基本上是不会影响学生的。
　　本书中的所有程序和算法都是经过编译和测试的。编译和测试是在DOS环境下的Intel/386平台上进行的，采用Turbo C和Turbo C++编译器，同时，程序也在SUN Sparc工作站上SUNOS 4.1系统的C编译器下进行了实际运行。我们直接将编译通过的程序引入本书，避免了程序排版时的更改，从而不会引入任何错误。
　　对于那些应用本书Pascal版的教师们，本书保留了深入的算法讨论和时间复杂性分析。此外，我们也尽量保留本书Pascal版的章节组织和描述风格。但是，我们也对原书作了大量的改进，特别是那些用C语言而不是用Pascal语言描述的部分。例如，对字符串的讨论被安排到了数组那一章。另外，也加入了对指针的讨论，因为用指针来操纵数组在C语言中非常常见。错误消息写到了stderr。程序使用系统函数调用，如malloc，来检查是否得到了正确的返回值。我们使用exit(0)和exit(1)来分别表示程序的正常结束和异常退出。
　　本书中还有一些与C不相关的调整，包括将习题直接放在各节之后。
　　和以前的版本相相比,本书的几个主要新特征之一是加入了抽象数据型。主要想法是将数据的描述和其具体实现区分开来。一些语言（如Ada）能够直接支持这一区分，但C语言不支持。因此，我们提出了一个称为抽象数据型的概念。一般先描述数据型对象，及其函数的名字和参数，老师可以和学生先讨论数据型的描述，然后再分析其如何具体实现以及算法的效率等。
　　在过去的十多年里，数据结构发展很快，也成熟很多。许多新兴的、有用的数据结构被设计出来，许多新型的复杂性分析方式被提了出来。本书尽量跟踪最新的发展前沿。例如，第9章全部用来描述堆结构，并讨论了一些特殊形式的堆，诸如应用在双端优先队列中的最小-最大堆和双端堆。本书也阐述了支持优先队列合并的数据结构，如左高树，它也包括最小和最大形式。而斐波那契堆是一种能够支持左高树全部操作的数据结构。我们还引入了二项树，斐波那契堆只是它的一种特例。
　　第10章更加深入地阐述了2-3树。此外，还有一节专门讨论2-3-4树。由于2-3-4树具有一些2-3树没有的优点，所以，本章对其表示有专门的描述。红黑树是2-3-4树的二叉树形式。所有的这些数据结构都是B树的重要变形，因为其上的保持平衡插入和删除算法都较AVL树简单，且时间复杂性都是控制在O(logn)界限内。
　 本书另一个深入阐述的问题是分摊复杂性。对大多数算法都分析了其最好的时间复杂性、最坏的时间复杂性，偶尔也分析它的平均时间复杂性。分摊复杂性考虑的是一个操作序列执行的效率。这一复杂性分析方法是R. Tarjan首先推广的，并且在许多时候，它要比传统的方法更加精确地反映数据结构的性能。
　　关于符号表和散列编排在第8章，并在原有的散列内容中加入了动态散列的内容。动态散列扩展了传统的方法，能够在不重新编译或设置散列表大小的情况下处理那些不定期增大的文件。
　　如何选用本书作为课程教材
　　如果选用本书作为教材并在一学期之内讲完课程，有两种方法：普通版和精华版。其中普通版适用的对象是计算机专业的初学者，大概可作为他们课程规划的第二或第三门专业课。许多教师（包括作者本人）的授课都是依据普通版进行的。下面给出的纲要可做参考。
　　一学期课程内容进度安排，普通版
　　周　　内　容 本书的对应章节　
1 关于算法和数据组织的引言 第1章　
2 数组 第2章　
3 数组（串） 第一次编程作业　
4 栈和队列 第3章　
5 链表（单向和双向） 第4章　
6 链表 第二次编程作业　
7 树（基本概念，二叉树） 第5章　
8 树（查找，堆） 　
9 期中
10 图（基本概念，表示） 第6章
11 图（最短路径，生成树，拓扑排序） 第三次编程作业
12 内部排序（插入排序，快速排序，归并排序） 第7章
13 内部排序（堆排序，基数排序） 第四次编程作业
14 散列 第8章
15 堆结构（选学内容） 第9章
16 查找结构（选学内容） 第10章
　　上面的课程安排也包含了几次编程作业布置，它们接近均匀地分布在整个学期。其中第一次作业的目的在于让学生熟悉编程环境。第二次作业的重点是链表结构（见第4章），在第4章末尾给出的习题中有一些可选择的内容。外部排序是本课程内容中略过的专题，节省的时间可以用来讲授更为重要的散列技术。由于散列要在课程规划中的多门后续课程中使用，所以在本课程中加入这部分内容。许多教师可能没有时间讲授查找结构章节的内容。或许可以选取一到两个专题作为选学内容。
　　如果选用本书作为研究生一年级或本科生高年级的教材，那么采用下面给出的精华版就更为合适。
　　一学期课程内容进度安排，精华版
　　周 　　　　 内　容 本书的对应章节　
　　1 关于算法和数据组织的引言 第1章　
　　2 数组 第2章　
　　3 栈和队列 第3章 第一次编程作业　
　　4 链表 第4章　
　　5 树 第5章　
　　6 树（续） 第二次编程作业　
　　7 期中 　
　　8 图 第6章　
　　9 图（续） 第三次编程作业
　　10 内部排序 第7章
　　11 外部排序 第7章
　　12 散列 第8章
　　13 堆结构 第9章
　　 第四次编程作业
　　14 堆结构 第9章
　　15 查找结构 第10章
　　16 查找结构 第10章
　　编程作业和期中考试的安排与普通版基本相同。只是课程内容的进度要快。对于精华版，第9章和第10章的课程内容都安排了两周，所以，每章只能选取一些内容进行讲授。
　　最后，我们给出一个高级数据结构课程的规划。高级课程要求学生了解数据结构的基本内容，尤其是关于链表、树和图的基本内容。教师可以在高级数据结构课程的前四周里讲解上述相关专题的深入内容。 一学期课程内容进度安排，高级数据结构课程
　　周 　　　　　　　内　　容 本书的对应章节　
　　1 算法基本内容的回顾 第1～2章　
　　2 基本链表结构的回顾 第3～4章　
　　3 树回顾 第5章　
　　4 图回顾 第6章　
　　5 内部排序的回顾 第7章 第一次编程作业　
　　6 外部排序 第7章　
　　7 外部排序（续） 　
　　8 散列 第8章 第二次编程作业　
　　9 堆结构（最小-最大堆，双端堆，左高树） 第9章
　　10 期中
　　（续） 周 　　　　　　　内　　容 本书的对应章节
　　11 堆结构（斐波那契堆） 第9章
　　12 查找结构（最优二叉查找树） 第10章
　　13 查找结构（AVL树，2-3树，2-3-4树） 第三次编程作业
　　14 查找结构（红黑树，伸展树，数字查找树）
　　15 查找结构（B树，检索树） 第四次编程作业
　　16 查找结构
　　对于两个学期的课程安排，可以参考下面的规划。该规划假设学生已经在高级程序语言课程中对算法分析和基本数据结构有所了解。
　　第一学期 周 　　　 内　　容 本书的对应章节　
　　1 算法和数组的回顾 第1～2章　
　　2 栈和队列 第3章　
　　3 链表（栈，队列，多项式） 第4章　
　　4 链表 　
　　5 树（遍历，集合表示） 第5章 第一次编程作业　
　　6 树（堆，查找） 期中 　
　　7 图（遍历，分支） 第6章　
　　8 图（最小生成树） 　
　　9 图（最短路径） 第二次编程作业
　　10 图 （活动网络）
　　第二学期
　　周 　　　　　　 内　　容 本书的对应章节　
　　1 内部排序（插入，快速，限界，O(1)空间合并，归并） 第7章
　　2 排序（堆，基数，链表，映射表） 　
　　3 外部排序 第7章　
　　4 散列 第8章　
　　5 期中 第一次编程作业　
　　6 堆结构（双端堆，最大-最小堆，左高树） 第9章　
　　7 堆结构（斐波那契堆） 　
　　8 查找结构（AVL树，2-3树，2-3-4树） 第10章　
　　9 查找结构（红黑树，伸展树，数字查找树） 第二次编程作业
　　10 查找结构（B树，检索树）
　　再一次感谢那些帮助我们完成此书的人们。感谢伊利诺伊Wesleyan大学的Lisa Brown教授，感谢她的编程三班的所有学生们，也感谢佛罗里达大学的Dinesh Mehta博士，感谢他们帮助对本书中程序的调试。感谢伊利诺伊Wesleyan大学计算机服务中心的Trey Short和Curtis Kelch提供的技术支持。也感谢AT&T贝尔实验室的Narain Gehani，Arcadia大学的Tomasz M焞dner和Trinity大学的Ronald Prather，他们审阅了本书的初稿。特别感谢本书最早的出版商Barbara和Art Friedman，他们为本书的发行作了很多工作。也感谢W.H. Freeman工作组成员的支持和鼓舞。最后，我们要特别感谢本书的编辑Nola Hague和辅助执行编辑Penny Hull。是他们的热情工作才得以完成本书。　
　　Ellis Horowitz
　　Sartaj Sahni
　　Susan Anderson-Freed

本书选用ANSI C 描述数据结构的实现，是数据结构实现方面的经典教科书和专业参考书。 书中详细讨论栈、队列、链表以及查找结构、高级的树结构等功能，对斐波那契堆、伸展树、红黑树、2-3树、2-3-4树、二项堆、最小-最大堆、双端堆等新的数据结构进行了有效分析。 本书特点： ●计算机理论和计算机编程实践相结合 ●各章节共汇聚400多道习题，难易兼顾 ●运用易于理解的图表充分展示与分析数据结构的原理

Ellis Horowitz Sartaj Sahni Susan Anderson-Freed：Ellis Horowitz:　　Ellis Horowitz于威斯康星-迈迪逊大学获得计算机科学博士学位，从事数据结构、算法和软件设计等领域的计算机科学教育。他是美国国家科学基金会主要调查员。
Sartaj Sahni: Sartaj Sahni于康奈尔大学获得计算机科学博士学位，是佛罗里达大学计算机和信息工程系的资深教授和系主任，是数据结构研究和算法开发方面的资深专家。
Susan Anderson-Freed: Susan Anderson-Freed是Illinois Wesleyan大学计算机科学系的资深教授。她在网络编程方面有着20多年丰富的教学经验。她是数据结构研究领域的资深专家。

李建中 张岩 李治军：暂无简介

数据结构在计算机科学技术中，尤其是在软件设计和发展中起到了举足轻重的作用。几乎所有的计算机软件系统，如操作系统，编辑工具，编译器等都要用到数据结构的基本知识。因此，数据结构是计算机专业教学的核心课程之一，是许多后续课程的重要基础。该课程的学习质量将直接影响计算机软件系列课程的学习效果。目前，国内外有很多介绍数据结构方面的书籍。这些书籍各具特色。本书以内容全面，论述深刻，实践性强等突出特点，可以作为一部优秀的数据结构教材。
　　本书是由Ellis Horowitz、Sartaj Sahni和Susan Anderson-Freed三人合著的。作者Ellis Horowitz是南加利福尼亚大学计算机科学系的教授，曾讲授数据结构、算法分析、程序设计语言等多门课程。Sartaj Sahni是佛罗里达大学计算机与信息科学工程系的杰出教授，教授数据结构及高级数据结构等课程。作者Susan Anderson-Freed是伊利诺伊州Wesleyan大学的教授，有20多年的教学经验。本书的英文版于1993年出版，至2003年已经印刷12次，是一部著名的数据结构教材，目前被国际上的许多著名大学指定为数据结构教科书。这部教材对我国计算机界也有重大的影响。机械工业出版社华章分社独具慧眼，将这部著作引进翻译成中文在国内出版。这必将对我国计算机科学技术的数据结构教学工作以及软件系统的设计开发等产生积极的推动作用。我们有幸承担本书的翻译工作，感到十分荣幸。
　　本书是数据结构的基本教材，阐述了数据结构的一般原理，除了对基本数据结构有着深入的阐述外，还对一些较为复杂的高级数据结构有着深入的讨论。此外，书中还给出了大量的数据结构新颖深刻的应用实例，并配有大量的课后习题。
　　本书包括十章和一个附录。第1章介绍了数据结构的基本概念；第2章介绍了数组和结构两类基本结构；第3章阐述了栈和队列；第4章详述了链表数据结构；第5章详细地讨论树的结构以及对树的操作；第6章阐述了图结构以及图的若干经典算法；第7章介绍各种排序算法；第8章讨论了散列，包括静态散列和动态散列；第9章详细阐述了各种堆结构；第10章详细阐述了各种查找结构。附录描述了ANSI C和K&R C的区别以及相互转换的问题。
　　本书适合作为高等院校计算机专业算法与数据结构（尤其是C语言实现）课程的教材，也可供算法与数据结构爱好者自学时参考。
　　限于译者的水平，译文中的疏漏和错误在所难免，欢迎读者批评指正。　
　　李建中　
　　张岩　
　　李治军

第1章　 基本概念 1
1.1　 综述：系统生命周期 1
1.2　 算法描述 3
1.2.1　 引言 3
1.2.2　 递归算法 6
1.3　 数据抽象 9
1.4　 算法的性能分析 12
1.4.1　 空间复杂性 12
1.4.2　 时间复杂性 14
1.4.3　 渐近记号（O，W，Q） 19
1.4.4　 实际可行的复杂性 24
1.5　 性能测量 26
1.6　 参考文献和文献选读 31
第2章　 数组与结构 32
2.1　 ADT数组 32
2.2　 结构与共用体 34
2.2.1　 结构 34
2.2.2　 共用体 36
2.2.3　 结构的内部实现 37
2.2.4　 自引用结构 37
2.3　 ADT多项式 38
2.4　 ADT稀疏矩阵 43
2.4.1　 概述 43
2.4.2　 矩阵转置 44
2.4.3　 矩阵乘法 47
2.5　 多维数组的存储表示 50
2.6　 ADT字符串 52
2.6.1　 概述 52
2.6.2　 模式匹配 55
2.7　 参考文献和文献选读 59
2.8　 附加习题 59
第3章　 栈与队列 65
3.1　 ADT栈 65
3.2　 ADT队列 68
3.3　 迷宫问题 72
3.4　 表达式求值 75
3.4.1　 概述 75
3.4.2　 后缀表达式求值 77
3.4.3　 中缀表达式到后缀表达式的转换 79
3.5　 多栈和多队列 81
3.6　 参考文献和文献选读 84
3.7　 附加习题 84
第4章　 链表 86
4.1　 指针 86
4.1.1　 指针的危险性 87
4.1.2　 动态存储分配 87
4.2　 单向链表 88
4.3　 动态链栈与动态链队列 93
4.4　 多项式 96
4.4.1　 多项式的单向链表表示 96
4.4.2　 多项式加法 97
4.4.3　 多项式删除 99
4.4.4　 多项式的循环链表表示 100
4.4.5　 小结 103
4.5　 链表的其他操作 104
4.5.1　 单向链表的操作 104
4.5.2　 循环链表的操作 105
4.6　 等价关系 106
4.7　 稀疏矩阵 109
4.8　 双向链表 114
4.9　 参考文献和文献选读 116
4.10　 附加习题 117
第5章　 树 118
5.1　 概述 118
5.1.1　 术语 118
5.1.2　 树的存储表示 119
5.2　 二叉树 121
5.2.1　 抽象数据型 121
5.2.2　 二叉树的性质 123
5.2.3　 二叉树的存储表示 124
5.3　 二叉树的遍历 126
5.4　 二叉树的其他操作 130
5.5　 线索二叉树 133
5.6　 堆 137
5.6.1　 ADT堆 137
5.6.2　 优先级队列 138
5.6.3　 最大堆的插入操作 139
5.6.4　 最大堆的删除操作 140
5.7　 二叉查找树 142
5.7.1　　概述 142
5.7.2　 二叉查找树的查找 143
5.7.3　 二叉查找树的插入 144
5.7.4　 二叉查找树的删除 145
5.7.5　 二叉查找树的高度 145
5.8　 选择树 146
5.9　 森林 148
5.9.1　 森林转换为二叉树 148
5.9.2　 森林的遍历 149
5.10　 集合表示 149
5.10.1　 Union和Find操作 150
5.10.2　 等价类 155
5.11　 二叉树计数 156
5.11.1　 不同的二叉树 156
5.11.2　 栈排列 156
5.11.3　 矩阵乘法 158
5.11.4　 不同的二叉树数量 159
5.12　 参考文献和文献选读 159
5.13　 附加习题 160
第6章　 图 162
6.1　 ADT图 162
6.1.1　 概述 162
6.1.2　 定义 163
6.1.3　 图的存储表示 165
6.2　 图的基本操作 170
6.2.1　 深度优先搜索 171
6.2.2　 广度优先搜索 171
6.2.3　 连通分支 173
6.2.4　 生成树 174
6.2.5　 双连通分支与关节点 175
6.3　 最小代价生成树 179
6.4　 最短路径与传递闭包 183
6.4.1　 单源多目标最短路径 184
6.4.2　 所有顶点对之间的最短路径 187
6.4.3　 传递闭包 188
6.5　 活动网络 190
6.5.1　 AOV网 190
6.5.2　 AOE网 194
6.6　 参考文献和文献选读 200
6.7　 附加习题 200
第7章　 排序 202
7.1　 查找与表验证 202
7.1.1　 概述 202
7.1.2　 顺序查找 202
7.1.3　 折半查找 203
7.1.4　 表验证 204
7.2　 定义 206
7.3　 插入排序 207
7.4　 快速排序 208
7.5　 最优的排序时间 211
7.6　 归并排序 212
7.6.1　 归并 212
7.6.2　 归并排序的迭代算法 216
7.6.3　 归并排序的递归算法 217
7.7　 堆排序 220
7.8　 基数排序 223
7.9　 利用链表和映射表进行排序 227
7.10　 内部排序总结 233
7.11　 外部排序 236
7.11.1　 概述 236
7.11.2　 k 路归并 239
7.11.3　 并行操作的缓冲区处理 240
7.11.4　 归并段的生成 244
7.11.5　 归并段的最优归并 246
7.12　 参考文献和文献选读 249
7.13　 附加习题 249
第8章　 散列 251
8.1　 ADT符号表 251
8.2　 静态散列 252
8.2.1　 散列表 252
8.2.2　 散列函数 253
8.2.3　 溢出处理 254
8.2.4　 溢出处理技术的理论分析 259
8.3　 动态散列 262
8.3.1　 带目录的动态散列 263
8.3.2　 带目录的动态散列的分析 268
8.3.3　 无目录的动态散列 269
8.4　 参考文献和文献选读 272
第9章　 堆结构 274
9.1　 最小-最大堆 274
9.1.1　 定义 274
9.1.2　 最小-最大堆插入 274
9.1.3　 删除最小元素 277
9.2　 双端堆 279
9.2.1　 定义 279
9.2.2　 插入操作 280
9.2.3　 删除最小元素操作 282
9.3　 左高树 284
9.4　 二项堆 289
9.4.1　 分摊代价 289
9.4.2　 二项堆的定义 290
9.4.3　 插入操作 291
9.4.4　 合并操作 291
9.4.5　 删除最小元素操作 291
9.4.6　 代价分摊分析 293
9.5　 斐波那契堆 294
9.5.1　 定义 294
9.5.2　 删除操作 295
9.5.3　 关键字减值操作 295
9.5.4　 级联剪枝操作 296
9.5.5　 分析 297
9.5.6　 F堆的应用 298
9.6　 参考文献和文献选读 299
第10章　 查找结构 301
10.1　 最优二叉查找树 301
10.2　 AVL树 307
10.3　 2-3树 317
10.3.1　　定义与性质 317
10.3.2　 2-3树的查找操作 318
10.3.3　 2-3树的插入操作 318
10.3.4　 2-3树的删除操作 321
10.4　 2-3-4树 325
10.4.1　 定义与性质 325
10.4.2　 2-3-4树的插入操作 327
10.4.3　 2-3-4树的删除操作 329
10.5　 红黑树 331
10.5.1　 定义与性质 331
10.5.2　 红黑树的查找 332
10.5.3　 自顶向下的插入 333
10.5.4　 自底向上的插入 334
10.5.5　 从红黑树删除结点 335
10.6　 B树 337
10.6.1　 m路查找树的定义 337
10.6.2　 m路查找树的查找 338
10.6.3　 B树的定义和性质 338
10.6.4　 B树的插入操作 340
10.6.5　 B树的删除操作 342
10.6.6　 可变长的关键字值 343
10.7　 伸展树 345
10.8　 数字查找树 349
10.8.1　 数字查找树 349
10.8.2　 二叉检索树 350
10.8.3　 Patricia树 351
10.9　 检索树 355
10.9.1　 定义 355
10.9.2　 检索树的查找操作 356
10.9.3　 采样策略 356
10.9.4　 检索树的插入操作 358
10.9.5　 检索树的删除操作 358
10.10　 差分文件 359
10.11　 参考文献和文献选读 362
附录　 ANSI C和K&R C 364
索引 370