前言 计算机的普及极大地改变了人们的工作和生活。目前各个行业、各个领域都与计算机建立了紧密的联系，也随之带来了开发各种软件的需求。为了能够以最小的成本、最快的速度、最好的质量开发出合乎需要的软件，必须遵循软件工程的原则，把软件的开发和维护标准化、工程化，不能再像以前那样，把软件看作是个人雕琢的精品。就软件产品而言，最重要的就是建立合理的软件体系结构和程序结构，设计有效的数据结构。因此，要做好软件开发工作，必须了解如何组织各种数据在计算机中的存储、传递和转换。这样，“数据结构”这门课程显得格外重要。自1978年美籍华裔学者冀中田在国内首开这门课程以来(当时作者也在场)，经过40余年的发展，本课程已成为各大学计算机专业本科的主干课程，也成为非计算机类学生和研究生学习计算机的必修课程。 “数据结构”课程脱胎于“离散数学结构”，它涉及各种离散结构(如向量、集合、树、图、代数方程、多项式等)在计算机上如何存储和处理。其内容丰富，涉及面广，而且还在随各种基于计算机的应用技术的发展，不断增加新的内容。特别是面向对象技术出现以后，人们认识到，用它开发出来的软件体系结构更加符合人们的习惯，质量更容易得到保证，尤其是更容易适应使用者和用户不断提出的新的需求。因此，在国际上，面向对象技术得到迅速普及，出现了大批面向对象的软件开发工具。为了适合形势的要求，有必要开设结合面向对象技术的“数据结构”课程。 用面向对象的观点讨论数据结构，与传统的面向过程的讲法相比，变化较大。各种数据结构的讨论都是基于抽象数据类型和软件复用的，有新意，也有继承。我们力图与过去的讲授体系保持一致，但又必须引入一些新的概念。为了能够让读者容易学习，我们对内容进行了精选。许多从基本数据结构派生出来的概念，如双端堆、二项堆、最小最大堆、斐波那契堆、左斜树、扁树、B*树等，都舍去了。同时，把动态存储管理部分归到“操作系统”课程，把文件组织部分归到“数据库原理”课程，只保留了重要的应用最广泛的一些结构。对这些结构做全面、深入的讲解，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型实例说明它们在解决应用问题时的动态行为和各种必要的操作，并以C++语言为表述手段，介绍在面向对象程序设计过程中各种数据结构的表达和实现。只要学过C或Pascal语言，就能够很容易地阅读和理解，并因此学习C++语言，提高读者的软件设计和编程能力。 本书是作为清华大学信息学院平台课“数据结构”的教材编写的，在编写过程中得到清华大学信息学院领导的支持，并获得普通高等教育“十一五”国家级规划教材的资助。参与策划的有计算机科学与技术系教师殷人昆、邓俊辉、舒继武、朱仲涛，电子工程系教师朱明方、吴及，自动化系教师李宛洲、刘义，微电子与纳电子学系教师李树国，软件学院教师张力以及信息科学技术学院办公室的教师王娜等。第4章由舒继武执笔，第5章由朱仲涛执笔，第8章由邓俊辉执笔，第9章由吴及执笔，其他各章由殷人昆执笔。作者都是在清华大学从事“数据结构”课程第一线教学的教师，有着丰富的数据结构和软件工程教学的经验，教学效果良好。 全书共分10章。第1章是预备知识，主要介绍什么是数据，数据与信息的关系；什么是数据结构，数据结构的分类。通过学习，读者能够了解抽象数据类型和面向对象的概念，并对对象、类、继承、消息以及其他关系的定义、使用有基本认识。我们选择了具有面向过程和面向对象双重特点的C++语言，可以帮助读者自然而轻松地从传统程序设计观念向面向对象方法转变。在这一章的最后还讨论了算法定义和简单的算法分析方法。 第2章是全书的基础，讨论了线性表、它的数组表示和链表表示，以及利用它们定义出来的各种结构，如顺序表、代数多项式等。通过学习，读者可以了解对象和类的基本实现，并通过模板、多态性等的使用，对数据抽象概念有进一步的理解。 第3章引入4种存取受限的表，即栈、队列、优先级队列和双端队列。通过对它们的定义、实现和应用的深入介绍，使读者能够了解在什么场合使用它们，为以后更复杂的数据结构和算法的实现提供了多种辅助手段。 第4章介绍在许多领域中经常遇到的多维数组、字符串和广义表。这些都是应用广泛又十分灵活的结构。 第5章和第8章介绍在实际应用中最重要的非线性结构——树与图。在管理、电子设计、机械设计、日常生活中的许多方面都会用到它们。 第6章、第7章和第10章介绍集合、跳表、散列、搜索树、索引以及文件等结构。在实际与信息处理相关的应用中，这些结构十分重要。许多非数值处理都涉及这些结构，它们与内存、外存上的数据组织关系密切。例如，在外存组织文件时全面应用了这些结构。它们又是许多新结构的生长点。因此，读者学习这些内容将获益匪浅。 第9章介绍排序。这也是应用十分广泛的技术。只要是数据处理，就少不了排序。如何才能高效地完成排序？本章分别就内存、外存使用的多种排序方法进行介绍和讨论，读者可以深入了解排序的机制，也能从中学到许多程序设计的技巧。 本书的篇幅虽然较大，但给读者以选择。读者可以根据时间、能力，适当对学习的内容加以剪裁。本着少讲多练的原则，可以对每种结构只介绍类定义和关键操作的实现，其他内容可自学。通过上机练习，加深理解。在本书目录中加**的章节可以酌情不讲。 在本书的成书过程中得到清华大学出版社的支持，在此表示衷心的感谢。最后需要说明的是，由于作者的水平有限，书中难免存在疏漏或错误，请读者批评指教。 作者2021年5月

• 课件下载
• 样章下载
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接