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