清华大学出版社

本书是为全国高等院校计算机及相关专业开设数据结构课程而精心组织和编著的一本实用教材。它从1999年出版以来，一直深受广大读者和专家的好评，相继被许多高校选定为教科书和考研参考书，并被列选为国家级“十一五”规划教材。这次对本书进行了认真和全面的修订，形成第2版，相信会得到更广泛的认可，对数据结构学科的教学和发展产生积极的影响。 本书从计算机学科发展和应用的实际需要出发，对各种常用的数据结构，从逻辑结构、存储结构、运算种类、运算方法和算法等各个方面进行了深入细致的解剖和分析，使读者更容易理解基本概念和知识，能够轻松地进行算法设计和上机操作的训练，大大提高软件开发与设计的专业能力。 另外，与本书配套的习题参考解答也一并被修订和出版，为广大自学读者提供方便。

序 言 时光更迭、历史嬗递。中国经济以她足以令世人惊叹的持续高速发展驶入了一个新的世纪，一个新的千年。世纪之初，以微电子、计算机、软件和通信技术为主导的信息技术革命给我们生存的社会所带来的变化令人目不暇接。软件是优化我国产业结构、加速传统产业改造和用信息化带动工业化的基础产业，是体现国家竞争力的战略性产业，是从事知识的提炼、总结、深化和应用的高智型产业；软件关系到国家的安全，是保证我国政治独立、文化不受侵蚀的重要因素；软件也是促进其他学科发展和提升的基础学科；软件作为20世纪人类文明进步的最伟大成果之一，代表了先进文化的前进方向。美国政府早在1992年“国家关键技术”一文中提出“美国在软件开发和应用上所处的传统领先地位是信息技术及其他重要领域竞争能力的一个关键因素”，“一个成熟的软件制造工业的发展是满足商业与国防对复杂程序日益增长的要求所必需的”，“在很多国家关键技术中，软件是关键的、起推动作用（或阻碍作用）的因素”。在1999年1月美国总统信息技术顾问委员会的报告“21世纪的信息技术”中指出“从台式计算机、电话系统到股市，我们的经济与社会越来越依赖于软件”，“软件研究为基础研究方面最优先发展的领域。”而软件人才的缺乏和激烈竞争是当前国际的共性问题。各国、各企业都对培养、引进软件人才采取了特殊政策与措施。 为了满足社会对软件人才的需要，为了让更多的人可以更快地学到实用的软件理论、技术与方法，我们编著了《普通高等院校计算机专业（本科）实用教程系列》。本套丛书面向普通高等院校学生，以培养面向21世纪计算机专业应用人才（以软件工程师为主）为 目标，以简明实用、便于自学、反映计算机技术最新发展和应用为特色，具体归纳为以下几点： 1．进透基本理论、基本原理、方法和技术，在写法上力求叙述详细，算法具体，通俗易懂，便于自学。 2．理论结合实际。计算机是一门实践性很强的科学，丛书贯彻从实践中来到实践中去的原则，许多技术理论结合实例讲解，以便于学习理解。 3．本丛书形成完整的体系，每本教材既有相对独立性，又有相互衔接和呼应，为总的培养目标服务。 4．每本教材都配以习题和实验，在各教学阶段安排课程设计或大作业，培养学生的实战能力与创新精神。习题和实验可以制作成光盘。 为了适应计算机科学技术的发展，本系列教材将本着与时俱进的精神不断修订更新，及时推出第二版、第三版…… 新世纪曙光激人向上，催人奋进。江泽民同志在十五届五中全会上的讲话：“大力推进国民经济和社会信息化，是覆盖现代化建设全局的战略举措。以信息化带动工业化，发挥后发优势，实现社会生产力的跨越式发展”，指明了我国信息界前进的方向。21世纪日趋开放的国策与更加迅速发展的科技会托起祖国更加辉煌灿烂的明天。 孙家广 2004年1月 第二版前言 本书第一版出版至今已近7年，随着计算机数据结构学科的不断发展和教学的改革需要，在第一版的基础上，整理和加工形成了第二版。 第一版教材深受读者的喜爱，连续14次印刷，发行7万余册，被许多高校选定为教材和考研参考书。有许多读者在网站上发表评论，赞扬本书的风格和特色。 第二版对第一版的内容进行了优化和适当增删，并对一些章节进行了调整，由第1版中的8章修订为10章。原来的第5章“树”，改为第5章的“树和二叉树”和第6章的“特殊二叉树”两章，原来的第6章“图”，改为第7章“图”和第8章“图的应用”两章。 在第二版教材中，增加了“堆”结构的内容、集合结构的内容、线性表应用的内容、栈与队列应用的内容等；扩充了栈与递归应用的实例、二叉树和树查找运算的算法、生成哈夫曼树的算法、对B_树的插入算法等；修改了从二叉搜索树中删除结点的算法、对外存文件进行排序的算法等。当然还对许多内容进行了修改，力争反映该学科的先进性和科学性，反映作为教材的系统性、实用性和可读性。 第2版的内容较丰富，在目录、例题或习题中带星号“*”的内容可以不作为讲授内容和教学要求，留给学生自学。 书中所有算法和程序都在Visual C++ 6.0开发环境下调试运行通过，使得其正确性和有效性得到了进一步验证。 数据结构教材的内容包括两个层面：逻辑层面和实现层面。在逻辑层面上，介绍的是各种数据结构的特点，在每种数据结构上进行插入、删除、查找、遍历等相应运算的方 法，不涉及在计算机上实现运算的算法；在实现层面上，讨论的是如何把对数据结构进行运算的方法和步骤转换为用一种计算机程序设计语言描述的算法，并能够实际运行和得到验证。逻辑层面的学习是基本的和必需的，实现层面的学习是进一步的，对于计算机及信息类专业的学生，这两步都要学，而且都要学好，对于经管农林等类的学生，则应侧重 第1步。 数据结构课程是一门理论性和实践性都很强的课程，只有通过亲自编写算法、上机运行和调试程序，才能够加深理解和掌握所学的知识，提高程序设计和软件研发能力。 使用此教材，最好具有C++语言的基础，因为书中描述的数据类型和算法都是按照C++语言的规则编写的。当然，若是只具有其他计算机语言的基础，则使用该书时应同时自学C++语言。对于一般读者来说，只要有任一种计算机语言的基础，再自学任何其他计算机语言都是不困难的。 与本书配套的《数据结构实用教程习题参考解答》也同时改版，将同此主教材一并出版发行。与本书配套的《数据结构课程实验》一书暂时不需改版，仍可继续与这本第二版主教材配套使用。 在由清华大学出版社组织的此套系列教材中，本人还编著了《C++语言基础教程》一书，该书已重印十多次，便于自学，读者反映较好，并被列选为国家“十一五”规划教材，不妨推荐给读者参考。 衷心希望通过这次改版，使《数据结构实用教程》一书更加受到读者的爱戴和好评，也同时希望读者继续给予批评指正，本人深表谢意！ 作者电子邮箱：[email protected]，联系电话：010-64910302。 徐孝凯 2006年8月 第一版前言 数据结构是普通高校计算机专业和信息管理专业一门必修的核心课程。它的主要任务是讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构、在计算机中的存储结构以及进行各种非数值运算的算法，目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。 数据的逻辑结构分为集合结构、线性结构、树结构和图结构4种。数据的存储结构分为顺序结构、链接结构、索引结构和散列结构4种。对数据进行的非数值运算主要包括插 入、删除、查找、排序、输入和输出等。需要特别指出：数据的存储结构既适用于内存， 也适用于外存，不仅要学会对内存数据操作的算法，而且要学会对外存数据（文件）操作的算法，这样才能够解决实际软件开发的问题，达到学以致用的目的。 在已经出版的众多数据结构教材中，对每一种数据结构类型进行相应运算的算法描述通常是粗略的，离真正用一种计算机语言上机实现还有相当的距离，特别在外存文件的操作上更是如此。本套教材在这方面做了彻底的改变，所给出的每一算法都利用C/C++语言给出了具体的实现，算法的正确性和有效性得到了实际的检验，这样就突出了实用性，使教材更便于教学，特别是自学，克服了以往同类教材只重视理论而轻视算法具体实现的 缺陷。 本套教材包含3本，第一本为主教材《数据结构实用教程》，第二本为实验教材《数据结构课程实验》，第三本为辅助教材《数据结构实用教程习题参考解答》。主教材共分为8章，依次为绪论、线性表、稀疏矩阵和广义表、栈和队列、树、图、查找和排序。在第1章的绪论中，1.2节为算法描述，对于C++语言比较熟悉的教学班和读者，此内容可作为自学阅读内容。主教材没有专门给出文件一章，这是因为，可把文件（这里只讨论磁盘文件）看作存储在外存上的数组，通过文件流操作函数既可顺序存取文件内容，也可随机存取文件中任何位置上的信息块，如何使用文件已经在C/C++语言中学习过，在数据结构课程中只是应用问题，所以不必单列一章介绍。实验教材给出了10个数据结构应用的典型例题，并给出了相应的参考程序。辅助教材给出了主教材中每章习题的大部分参考解答，最后附加了两个综合题，它们是针对不同文件的插入、删除和查找操作的，目的是培养学生对所学知识的实际应用能力。 本人一直从事数据结构的教学和研究工作，编著过多本教材，清华大学出版社已经出版的《数据结构简明教程》一书就是其代表作。现在这套教材是本人多年教学经验的结晶，是对以往教材的继承、丰富和发展，希望能够对数据结构课程的教学起到良好的作用，使读者能够得到满意的收获。 本套教材是根据计算机专业和信息管理专业本科培养目标，对数据结构课程教学的要求编写的。由于内容叙述细致，算法描述具体，便于自学，所以删除部分内容后可作为相应专科学生的教材。具体如何删减，应由办学单位和任课教师定夺。 学习本套教材应具有C语言或C++语言的基础。若只学习过C语言，则应在学习本课程的过程中补充C++语言的输入/输出操作、文件流操作、运算符重载等有关内容。 本课程总学时应安排在80～100学时之间，其中讲授与上机学时之比应为2∶1左右，有条件的学生要尽量多上机。 承蒙北京大学计算机系许卓群教授和北京石油大学计算机系陈明教授认真审阅了本套教材的全部书稿，提出了宝贵的意见，在此谨向他们表示衷心感谢。 尽管本人做了很大的努力，但由于水平有限，加之时间仓促，错误和不足之处在所难免，敬请授课教师和广大读者批评指正。 电子邮箱地址：[email protected]，联系电话：010-64910302。 徐孝凯 1999年10月

版权图片链接