前    言

这本书是为ACM（Association of Computing Machinery，美国计算机学会）课程建议中的CS2课程而设计的。本书的目标是满足这些建议中给出的这门课程的主要要求，其中一条就是：

（1）继续开发一种严格的方法来设计、编码和测试用高级语言编写的程序。

本书继续探讨我作为作者之一的C++书籍——《C++：An Introduction to Computing》中的以对象为中心的设计模式（Object-Centered-Design Paradigm），并以真正的面向对象程序设计（Object-Oriented Programming，OOP）作为高潮，OOP目前已经成为程序设计和系统开发的标准工作模式。本书还继续全面地探讨C++，包括了很多通常不会在第一门课程中涉及但是学生又需要学习的高级话题，例如递归、函数和类模板、继承以及多态性等。本书中贯穿使用的是1997年11月的ANSI/ISO最终稿标准C++。

CS2的另两个目标是：

（2）讲授用作例子数据结构的数据抽象的使用，而不是讲授那些目前程序设计语言中通常提供的基本类型；例如，链表、栈、队列以及树。

（3）提供对这些数据结构的不同实现的理解。

本书从始至终都在强调抽象数据类型（ADTs）。这是对OOP精髓中数据结构的学习。本书不仅覆盖到了通常的数据结构，还将容器和算法从标准模板库中拿出来专门讲解，这些都是C++中最新最强大的标准数据类型和工具。此外，由于很多学生以后工作时主要是作为C程序员；很多库是用C编写的；C风格数据结构往往都实现得非常高效；以及C风格数据结构还常常被用来实现一些更现代化的标准数据类型，所以本书还包含了一些适合数据结构课程的C风格主题。

CS2课程的另一个目标是：

（4）介绍搜索和排序算法以及对它们的分析。

本书对搜索和排序都详细地进行了覆盖。此外，本书还覆盖了算法开发、分析并介绍了算法验证，这样，就提供了对后续计算机科学课程中所需要的重要工具的第一次探讨。

课程建议中还包括了以下的CS2课程目标：

（5）提供对计算机科学不同领域的介绍，从而提供学习计算机科学后续课程的基础。

本书还通过包含来自计算机科学的不同领域的例子和练习，来为以后的理论或应用计算机科学的学习打下基础，从而继续了在C++：An Introduction to Computing中开始对计算机科学的学科的描绘。这些主题包括：

（1）对软件开发过程的描述。

（2）抽象数据类型。

（3）面向对象程序设计。

（4）算法的计算复杂性，通过对标准搜索和排序算法的分析来演示。

（5）正确性证明入门。

（6）数据加密模式（Data Encryption Scheme，DES和公共密钥）。

（7）使用哈夫曼编码的数据压缩。

（8）双向链表和大整数算术。

（9）随机数生成和模拟。

（10）词汇分析和解析。

（11）逆波兰表示和机器代码生成。

（12）简单的系统概念，例如输入/输出缓冲区、形参分析机制、地址解析以及存储管理。

补充材料

为这本书准备了一些补充材料：

（1）一本答案手册，包含了所有练习以及很多编程问题的答案。（采纳本书作为课程教材的教师可向Pearson Education（培生教育出版集团）北京代表处索取）

联系电话：010-88817488/6659

（2）一个包含演讲幻灯片、源代码以及额外资源的相关网站（www.prenhall. com/nyhoff）。

致谢

我对所有以任何方式帮助我准备本书的人表达真诚的感激。特别感谢我的编辑Laura Steele，他的支持和鼓励使得我能够继续工作，而过去几年来和他的友谊使得为Prentice Hall编写教科书成为一种令人愉快的经历。对于Alan Apt，一个在整个出版和学术界获得广泛尊重的出版者，为他给予我的友谊、建议和指导以及不懈的支持和鼓励，我向他表示深深的感激之情。我还要感谢助理编辑Kate Kaibni以令人愉快的风度如此及时地处理了校阅管理以及其他诸多的细节工作。我还必须要感谢助理管理编辑Eileen Clark，艺术导演Heather Scott，产品编辑Sharyn Vitrano和Ann Marie Kalajian，以及所有其他为设计这本吸引读者的书做出如此出色的工作并将它实际地付诸出版的人。他们对细节的关注弥补了我在此方面的不足，他们的合作与友善的忠告是如此令人感激。对于Ralph Ewton（得克萨斯大学埃尔帕索分校），我还欠一份感激之情，他周到的、用心的、敏锐的注释、评论和建议极大地增强了本书的表达。我还要感谢以下的本书手稿的校阅者，感谢他们重要的意见和建议：Adair Dingle（Seattle大学），Jens Gregor（Tennesse大学），Bob Holloway（Wisconsin大学），Robin Rowe（SAIC, Pt. Loam研究中心），Andrew Sung（新墨西哥理工大学）以及Mansour Zand（Nebraska大学）。当然，我必须再次向我的妻子、儿女们以及孙子孙女们表达我的敬意——Jeff，Dawn，Rebecca，Megan，以及Sara，Jim，Greg，Julie，Joshua和Derek，Tom，Joan，还有Abigail——为他们的爱以及在所有这些时间里对我因处于忙碌中而忽略了他们的需求和需要的理解。

Larry R.Nyhoff