数据结构与C++高级教程（第3版） (2008 年度畅销榜NO.2819 )

本书详细介绍了数据间的逻辑关系、存储方式和相关运算。针对各种实际问题，作者以C++程序设计语言为工具，说明了在问题求解过程中类和抽象数据类型的作用，并在许多实例和习题中使用了递归方法。同时，作者还提供了一个学习C++程序设计语言的教程，本教程可供初学者使用，对于已有一定基础的读者，也大有裨益。
本书可作为计算机及相关专业的本科生、研究生的教材和教学参考书，也可供程序开发人员自学。

第1部分 问题求解方法
第1章 程序设计与软件工程基本原理
1.1 问题求解与软件工程
1.2完成一个模块设计
1.3 程序设计关键问题小结
第2章 递归：镜子
2.1 递归解决方案
2.2 事件计数
2.3 检索数组
2.4 组织数据
2.5递归和效率
第3章 数据抽象：墙
3.1 抽象数据类型
3.2规定ADT
3.3实现ADT
第4章 链表
4.1 预备知识
4.2链表程序设计
4.3 链表的变体
4.4 应用：维护库存清单
4.5 C++标准模板库
第5章 求解问题的递归方法
5.1 回溯
5.2 定义语言
5.3 递归与数学归纳的关系
第Ⅱ部分 用抽象数据类型求解问题
第6章 栈
6.1 抽象数据类型———栈
6.2 栈ADT的简单应用
6.3 栈ADT的实现
6.4 应用：代数表达式
6.5 应用：检索问题
6.6 栈和递归之间的关系
第7章 队列
7.1 队列
7.2 队列的简单应用
7.3 队列的实现
7.4 面向位置的ADT小结
7.5 应用：仿真
第8章 C++高级专题
8.1 继承的再讨论
8.2 虚函数与迟绑定
8.3 友元
8.4 表和有序表的再讨论
8.5 类模板
8.6 重载运算符
8.7 迭代器
第9章 算法效率与排序
9.1 算法效率的度量
9.2 排序算法及其效率
第10章 树
10.1 术语
10.2 ADT二叉树
10.3 二叉搜索树
10.4 通用捌
第u章 查找表与优先级队列
11.1 查找表
11 2 优先级队列：查找表的一种变体
第12章 查找表的高级实现
12.1平衡搜索树
12.2 散列法
12.3 多重组织的数据
第13章 图
13.1 术语
13.2 图ADT—
13.3 遍历图
13.4 图的应用
第14章 外部方法
14.1 外部存储器简介
14.2 对外部文件中的数据排序
14.3 外部查找表
附录A C++重要概念回顾
A.1 语言基础
A.2 使用iostream的输入输出操作
A.3 函数
A.4 选择语句
A.5 循环语句
A.6 数组
A.7 字符串
A.8 结构
A.9 C++异常
A.10 文件的输入输出
A.1l 库
A.12 与JAVA的比较
附录B ASCII码表
附录C C++头文件和标准函数
附录D 数学归纳
附录E 标准模板库类
附录F C++语句总结
附录G c++关键字
附录H C1+运算符
词汇表
自测习题答案

欢迎阅读本书。自本书第2版面世以来，通过使用C++和面向对象的方法讲授数据抽象，我们获取了更多经验。这一版本集中反映了C++语言的发展和我们的实践经验。 本书源于Paul Helman和Robert Veroff编著的Intermediateproblem SolvingandDataStructures：WallsandMirrors一书(该书1986年由Benjamin／Cummings有限出版公司出版)。本书基于原书的组织框架和整体观点，其中包括相关的技术以及文字，例如，从原著中选取的图(表)以及习题。Helman和Veroff教授借用了两个非常强大的比喻，墙(wall)和镜子(mirror)，这简化了我们讲解和学习计算机科学的难度。 本书的重点是数据抽象和其他问题求解工具，是作为计算机科学的第二教程来设计的。考虑到大学本科计算机课程的极大灵活性和要求的多样性，本书的主题覆盖了相当广泛的内容以使其适应其他课程。例如，可以在介绍数据结构或高级语言程序设计及其问题求解课程中使用本书。本书的目标仍然是在数据抽象、面向对象程序设计和其他现代问题求解方法方面给学生打下坚实的基础。 致学生 很多大学生阅读并学习过原书第2版。标题中的墙和镜子表示贯穿于整本书的两种基本的问题求解方法。数据抽象将模块的实现细节同程序的其他部分相隔离，很像把你同邻居隔开并隐藏自己的墙。递归是通过重复解决类型绝对相同的小型子问题来解决大问题的一种方法。 编写本书时我们一直将读者放在第一位。我们也曾经是大学生，我们也是坚持学习的教育工作者，我们更能理解清晰表述的重要性，我们的目的是使本书尽可能便于理解。 本书对读者的C++知识有一些基本假设。一些读者可能需要学习C++语言或参考本书附录A。读者需要掌握订和switch语句；for，while和do语句；函数以及参数传递、数组、串、结构和文件。本书在第1章、第3章和第8章中讨论了C++类，我们假设读者没有这方面的基础。我们还假设读者也不具备第2章、第5章中论述的递归函数的使用经验。 本书中所有～+源代码都可以供你使用。前言中稍后部分列出的补充材料告诉读者如何获得这些文件。 方法 本版进一步强调数据抽象和数据结构。本书详细说明了C++语言的优势和不足，同时继续采用容易理解的教学方法和材料。 背景知识 本书假设读者已具备C++或其他语言的基础知识，并有教师帮助他们过渡到C++。本书正式介绍了C++类，并没有采用以前有关C++类的知识。本书的内容包括用C++描述的面向对象程序设计的基本概念、继承、虚函数以及类模板。尽管本书介绍这些内容以及抽象数据类型的实现，但重点仍然是ADT，而不是C++。这些内容在面向对象程序设计部分中有介绍，但我们假设未来的课程将详细讨论面向对象设计和软件工程，因此重点仍是数据抽象。不过，我们确实引入了统一建模语言(UnifiedModelingLanguage，简称UML)作为设计工具。 适应性 本书所涵盖的广泛内容为我们的课程提供了必要的资料。读者可以选择其需要的内容，按照个性化的学习顺序进行。各章的从属关系图说明了在某个章节前应先学习的章节。 第1部分中的各章可以根据学生的背景知识选择。其中有3章大篇幅地介绍了数据抽象和递归。数据抽象和递归都很重要，但到底应先讲哪部分却意见不一。尽管本书递归的章节在前，数据抽象的章节在后，但这一顺序可以重新调整。 第Ⅱ部分的内容也可用灵活的顺序论述。例如，可在介绍栈(第6章)之前或之后介绍高级C++(第8章)；也可以在学完第5章后的任何时候引入算法效率与排序(第9章)；可以在队列之前介绍树，或在查找表一章之前介绍图，或在学完查找表后学习散列法、平衡二叉树和优先级队列(其他顺序亦可)，也可在课程中稍早的时候学外部方法(第14章)，例如，在学完第9章中的归并排序后介绍外部排序。 数据抽象 抽象数据类型的设计及其应用是始终贯穿本书的问题求解方法。我们用几个实例说明了ADT如何设计。我们首先用英语和伪代码定义了所有ADT，然后在论述这些ADT的实现之前，在简单的应用中使用了它们。ADT与实现它的数据结构之间的差异仍然在最前面论述。本书一开始就解释了封装和C++类，并使学生明白C++类如何在ADT的客户程序中将已实现的数据结构隐藏起来。抽象数据类型包括：表、栈、队列、树、查找表、堆和优先级队列，它们构成了我们讨论的基础。 问题求解 本书通过研究计算机科学家所用的方法和思维过程，帮助学生掌握问题求解和程序设计的能力。学习开发、分析和实现解决方案的方法同学习算法一样重要。 本书包括针对示例问题的分析方法，在贯穿整本书的问题解决方案设计过程中，涉及了算法、数据结构以及递归逐步求精。 本书很早就介绍了C++指针和链表的处理，并在构建数据结构时使用了它们。本书还初步介绍了算法的数量级分析方法。这种方法首先非正式地考虑，然后进一步详细地考虑基于数组和基于指针的数据结构的优缺点。各种可能的解决方案的折衷选择及其实现是问题求解的一个核心课题。 最后研究程序设计风格，包括前提和结果的文档和辅助调试手段。循环不变量是实现、验证解决方案的问题求解方法学的重要组成部分。整本书都论述这些课题。 应用 本书的重点章节给出了典型应用，如：折半检索、快速排序和归并排序算法，这些是递归的重要应用，而且还介绍了数量级分析。在诸如平衡二叉树搜索、散列法和文件索引这样一些课题中，又继续讨论搜索问题。在外部文件一节中还将再次讨论搜索和排序问题。 概述 为便于学生学习并允许教师方便地剪裁内容以适应实际课程，本书对教学特点和全书结构进行了精心规划。 组织 第1章到第11章通常是一学期课程的核心内容，其中第1章或第2章可作为学生的复习材料。第11章到第14章的内容取决于这门课程在整个课程体系中的作用。 第1部分：问题求解方法。第工部分第1章强调程序设计和软件工程中的主要问题，并介绍新引入的标准建模语言。接下来的一章讨论递归，该章是为那些对递归这一重要课题不了解的学生准备的。递归地思考问题的能力是计算机科学家应具备的最有用的技能之一，对帮助人们更好地理解问题的性质通常具有重大的价值。这一章详尽地讨论递归，第5章将再次深入地讨论。全书广泛使用递归，包括简单的递归定义和语言识别、搜索、排序等算法。 第3章详细论述数据抽象和抽象数据类型。讨论完ADT规范说明和用途后，本章介绍C++类，并用C++类实现ADT。本章简要介绍继承、C++名字空间和异常。第4章讨论C++指针变量和链表的辅助实现工具。该章还介绍类模板、C++标准模板库，容器和迭代器。使用本书时，可根据学生的背景知识在第1部分的章节中选择，也可以按不同顺序讲解。 第Ⅱ部分：用抽象数据类型求解问题。第Ⅱ部分继续研究数据抽象问题，它是问题求解的方法。这二部分首先详细说明基本的抽象数据类型，如：栈、队列、-y.树、-y.搜索树、查找表、堆以及优先级队列，然后用类实现。在实例中使用了抽象数据类型并比较了它们的实现。 第8章通过进一步讨论继承、类模板和迭代器扩展了C++类的内容。之后介绍虚函数和友元。第9章中，通过引入数量级分析和大O表示法，形式化地描述了前边讨论过的算法的效率，研究了几种搜索和排序算法，包括归并排序和快速排序的效率。第Ⅱ部分还讨论一些高级课题——如平衡搜索树(2-3，2-3-4，红一黑和AVL树)和散列法——它们是被当作查找表的实现来研究的。针对这些实现，我们将进行分析以确定它们各自支持的最优操作。 最后，我们讨论外部直接访问文件中的数据存储。修改了归并排序算法以便对这种数据进行排序，使用外部散列法和B—树索引对其进行搜索。这些搜索算法是已经讨论过的内部散列法方案和2-3树的推广。 补充材料 教师和学生可以在线获得下列补充材料： ·源代码：读者可以使用本书中的所有C++类、函数和程序。 ·勘误表：我们尽力不犯错误，但错误是难免的。勘误表列出了目前已发现的错误和必要的修正（指英文原版书中的勘误表——译者注）。请将您发现的错误反馈给我们（包括英文原版和中文简体翻译版中的错误，我们将分别转达给原著作和中文译者——本书责任编辑注）。这里预致谢意。 ·通过http://www.aw.com./cssupport，你可以得到源代码和勘误表。