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