数据结构（C语言版）

    书籍
    计算机书籍
《数据结构》(C语言版)针对采用ANSI C实现数据结构进行了全面的描述和深入的讨论。书中详细讨论了栈、队列、链表以及查找结构、高级树结构等功能，对裴波那契堆、伸展树、红黑树、2-3树、2-3-4树、二项堆、最小- 堆、双端堆等新的数据结构进行了有效分析。《数据结构》(C语言版)对一些特殊形式的堆结构，诸如应用在双端优先队列中的最小- 堆和双端堆的数据结构以及左高树、裴波那契堆、二项堆等数据结构，提供了经过编译和测试的程序和算法。《数据结构》(C语言版)深入阐述了平摊复杂性问题，对大多数算法进行了时间复杂性的分析。

作者：(美)Ellis Horowitz (美)Sartaj Sahni (美)Susan Anderson-Freed 译者：李建中 张岩 李治军
Ellis Horowitz于成斯康星-麦迪逊大学获得计算机科学博士学位。他从事数据结构、算法和软件设计等领域的计算机科学教育。

出版者的话
专家指导委员会
译者序
前言
第1章 基本概念
1.1 综述：系统性命周期
1.2 算法描述
1.3 数据抽象
1.4 算法的性能分析
1.5 性能测量
1.6 参考文献和文献选读
第2章 数组与结构
2.1 ADT数组
2.2 结构与共用体
2.3 ADT多项式
2.4 ADT稀疏矩阵
2.5 多维数组的存储表示
2.6 ADT字符串
2.7 参考文献和文献选读
2.8 附加习题

　　数据结构在计算机科学技术中，尤其是在软件设计和发展中起到了举足轻重的作用。几乎所有的计算机软件系统，如操作系统，编辑工具，编译器等都要用到数据结构的基本知识。因此，数据结构是计算机专业教学的核心课程之一，是许多后续课程的重要基础。该课程的学习质量将直接影响计算机软件系列课程的学习效果。目前，国内外有很多介绍数据结构方面的书籍。这些书籍各具特色。本书以内容全面，论述深刻，实践性强等突出特点，可以作为一部优秀的数据结构教材。.
　　本书是由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语言实现)课程的教材，也可供算法与数据结构爱好者自学时参考。
　　限于译者的水平，译文中的疏漏和错误在所难免，欢迎读者批评指正。...
　　李建中 张岩 李治军
　　

　　本书为什么用C语言作为描述语言呢?有以下几个方面的原因：首先，也是最重要的原因，是因为C语言已逐渐成为目前教师授课的首选语言。当然，这与目前C语言已经是个人计算机(PC和Mac)和UNIX32作站的主要开发语言有很大关系。另一个原因是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章，并在原有的散列内容中加入了动态散列的内容。动态散列扩展了传统的方法，能够在不重新编译或设置散列表大小的情况下处理那些不定期增大的文件。
　　如何选用本书作为课程教材
　　如果选用本书作为教材并在一学期之内讲完课程，有两种方法：普通版和精华版。其中普通版适用的对象是计算机专业的初学者，大概可作为他们课程规划的第二或第三门专业课。许多教师(包括作者本人)的授课都是依据普通版进行的。下面给出的纲要可做参考。
　　上面的课程安排也包含了几次编程作业布置，它们接近均匀地分布在整个学期。其中第一次作业的目的在于让学生熟悉编程环境。第二次作业的重点是链表结构(见第4章)，在第4章末尾给出的习题中有一些可选择的内容。外部排序是本课程内容中略过的专题，节省的时间可以用来讲授更为重要的散列技术。由于散列要在课程规划中的多门后续课程中使用，所以在本课程中加入这部分内容。许多教师可能没有时间讲授查找结构章节的内容。或许可以选取一到两个专题作为选学内容。
　　如果选用本书作为研究生一年级或本科生高年级的教材，那么采用下面给出的精华版就更为合适。
　　编程作业和期中考试的安排与普通版基本相同。只是课程内容的进度要快。对于精华版，第9章和第10章的课程内容都安排了两周，所以，每章只能选取一些内容进行讲授。
　　最后，我们给出一个高级数据结构课程的规划。高级课程要求学生了解数据结构的基本内容，尤其是关于链表、树和图的基本内容。教师可以在高级数据结构课程的前四周里讲解上述相关专题的深入内容。
　　对于两个学期的课程安排，可以参考下面的规划。该规划假设学生已经在高级程序语言课程中对算法分析和基本数据结构有所了解。
　　再一次感谢那些帮助我们完成此书的人们。感谢伊利诺伊Wesleyan大学的Lisa Brown教授，感谢她的编程三班的所有学生们，也感谢佛罗里达大学的Dinesh Mehta博士，感谢他们帮助对本书中程序的调试。感谢伊利诺伊Wesleyan大学计算机服务中心的Trey Short和Curtis Kelch提供的技术支持。也感谢AT&T贝尔实验室的Narain Gehani，Arcadia大学的Tomasz Mtildner和Trinity大学的Ronald Prather，他们审阅了本书的初稿。特别感谢本书最早的出版商Barbara和Art Friedman，他们为本书的发行作了很多工作。也感谢W．H．Freeman工作组成员的支持和鼓舞。最后，我们要特别感谢本书的编辑Nola Hague和辅助执行编辑Penny Hull。是他们的热情工作才得以完成本书。...
　　Ellis Horowitz
　　Sartaj Sahni