序

编写本书的动机源于我们对进一步革新计算机科学核心课程的需求。作为对讨论了计算科学入门课程的“Denning报告”（Denning、P. J.、D. E. Comer、D. Gries、M. C. Mulder A. Tucker、J. Turner和P. R. Young，“Computing as a Discipline”，Comm. ACM 32:1，9-23页，1989年1月）的回应，全美的很多学校都修订了他们的课程。这篇报告引起人们关注作为相关学科所有本科课程之基础的三种工作方法或流程——理论、抽象和设计。最近，ACM/IEEE-CS Joint Curriculum Task Force的Computing Curricula 1991报告呼应了“Denning报告”，特别是确定了作为计算科学之本的那些反复出现的关键概念：概念上和形式上的模型、效率，以及抽象的层次。这两份报告的主题总结了我们试图在本书中提供给学生们的内容。

本书由斯坦福大学一门课程的讲义发展而来，该课程名叫“CS109：计算机科学导论”（CS109：Introduction to Computer Science），它是一门两学季课程，有很多目标，第一个目标是为计算机科学专业初学者的进一步学习打下坚实的基础。不过，计算科学在大量的理工学科中变得越来越重要。因此，第二个目标是为那些不会在计算机科学领域进一步深造的学生提供一些该领域的概念性工具。最后，影响更加广泛的目标是让所有学生了解程序设计概念，并建立扎实的计算机科学知识基础。

本书第一版于1992年问世，是基于Pascal语言的。当时之所以选择Pascal作为示例程序的语言，是因为计算机科学科目的Advanced Placement1考试使用了Pascal语言，而且很多大学的程序设计导论课程也是使用Pascal语言。我们欣喜地看到，自从1992年起，C语言已渐趋成为主流入门程序设计语言，因此本书这一版的示例程序都用C语言写成。本书强调抽象和封装的重要性，这应该能为读者学习涉及使用C++的面向对象技术的后续课程提供良好的基础。

1简称AP，指美国高中开设的具有大学水平的课程，即大学预修课程。AP考试的成绩可折抵大学学分，并成为美国大学的重要录取依据。——编者注

与此同时，我们决定对本书的内容进行两大改进。首先，虽然对机器的体系结构有所了解有利于激发对度量运行时间的兴趣，但我们发现几乎所有的课程体系都将体系结构单独作为一门课程，所以有关这一主题的章节在这里并不实用。其次，很多计算理论的入门课程会强调组合和概率，所以我们决定增加这方面的内容，并将其单独作为一章。

本书涵盖的主题通常会出现在离散数学课程以及大二计算机科学的数据结构课程中。我们有意从计算机用户的实际需要着眼，选择了数学方面的基础知识，而不是从数学家的角度去选择，并尝试把数学基础知识与计算科学有效地结合起来。因此，我们希望为学习计算机科学的人提供一种比学习程序设计课程、离散数学课程或计算机科学附属学科课程更佳的感觉。相信随着时间的推移，科学家和工程师都将学习与斯坦福大学这门课程类似的基础课程。这样的计算机科学课程也应该像微积分和物理学的相关课程那样成为标准课程。

阅读前提

从大一新生到研究生都可能选修基于本书的课程。这里我们假设这些学生都有着扎实的程序设计基础，熟悉本版中用到的ANSI C程序设计语言。特别要说的是，我们还希望学生们了解C语言中的结构，诸如递归函数、结构体、指针，以及与指针和结构体有关的运算符，如点运算符、->和&。

计算机科学基础课程相关建议

本书以传统计算机科学课程的方式，将数据结构方面的初级课程（也就是CS2课程）与离散数学课程结合在一起。我们相信，出于如下两个原因，这些主题的整合是十分必要的。

1. 把数学与计算科学更加紧密地联系起来，有助于激发对数学的兴趣。

2. 计算科学与数学是相辅相成的。这样的例子包括，第2章中递归程序设计与数学归纳法之间的关系，第14章，逻辑学中自由/约束变量的区别与程序设计语言中变量范围之间的关系。此外，与启发性程序设计作业有关的建议纵贯全书。

本书的使用方法有很多种。

两学季或两学期的课程

斯坦福大学的CS109A-B系列课程就是典型的两学季课程，不过它们的安排都相当紧，各自要在10周时间内完成40个课时的教学。这两门课程完整涵盖了本书，其中前7章是在CS109A中介绍的，而第8至14章是在CS109B中介绍的。

一学期的CS2类课程

本书也可以用于一学期课程，内容与CS2课程的主题类似。本书中的内容确实太多，一个学期自然讲不完，因此我们建议把精力放在以下这些内容上。

1. 递归算法与递归程序：2.7节和2.8节。

2. 大O分析和程序的运行时间：第3章，除了3.11节求解递推关系的内容。

3. 树：5.2节～5.10节。

4. 表：第6章。有人可能希望按照更为传统的方式，在介绍树之前先介绍表。我们在这里把树视作更为基础的概念，不过这样调换次序存在一个小问题，就是第6章讨论的“词典”抽象数据类型（以及插入、删除和查找操作），在5.7节中就作为与二叉查找树相关的概念介绍了。

5. 集合与关系：7.2节～7.9节以及8.2节～8.6节，强调了表示集合和关系的数据结构。

6. 图算法：9.2节～9.9节。

一学期的离散数学课程

对着重于数学基础的一学期课程而言，教员可以选择介绍以下内容。

1. 数学归纳法和递归程序：第2章。

2. 大O分析、运行时间和递推关系：3.4节～3.11节。

3. 组合学：4.2节～4.8节。

4. 离散概率：4.9节～4.13节。

5. 树的数学方面：5.2节～5.6节。

6. 集合的数学方面：7.2节、7.3节、7.7节、7.10节和7.11节。

7. 关系代数：8.2节、8.7节和8.9节。

8. 图算法与图论：第9章。

9. 自动机和正则表达式：第10章。

10. 上下文无关文法：11.2节～11.4节。

11. 命题逻辑和谓词逻辑：第12章，第14章。

本书特色

为了帮助学生学习这些知识，我们还采取了以下辅助措施。

1. 每章开头都有内容简介，最后都有小结，用来突出本章要点。

2. 除了在节标题或小节标题中提到过的概念和定义外，一些重要的概念和定义用楷体突出显示。

3. 附注栏内容与正文分隔开，这些附注短文有以下用途。

• 有一些是对正文的详细阐述，或是介绍程序或算法设计的微妙之处。

• 其他一些是对正文中要点的总结或强调。这类短文包括了对某几类重要证明（比如各种形式的归纳证明）的概述。

• 少量用于举例说明一些谬误，而且我们希望将其与正文分开可以消除可能出现的误解。

• 少量非常简要地介绍了像不可判定性或计算机发展史这种要花上一整节来介绍的重要 主题。

4. 几乎每节都有习题，在全书分布着逾1000道习题。其中大概有30%标记了一个星号，表示这些习题比那些不带星号的要多费一番思量。还有约10%的习题标记了两个星号，它们是最具挑战性的。

5. 每一章最后还有参考文献。我们不求面面俱到，只不过推荐一些让读者能了解与该章主题有关的高阶教科书，以及那些最具历史意义的相关论文。

封面简介

使用象征图书内容的漫画或图片作为封面是计算机科学教科书的传统。本书用龟背来表示计算机科学的世界，也还有其他很多象征符号代表着那些更高阶计算机科学教科书，本书内容正是为这些书打基础的，这些符号有下面这些。

泰迪熊。R. Sethi，Programming Languages: Concepts and Constructs，Addison-Wesley，Reading，Mass.，1989。

棒球运动员。J. D. Ullman，Principles of Database and Knowledge-Base Systems，Computer Science Press，New York，1988。

圆柱。J. L. Hennessy和D. A. Patterson，Computer Architecture: a Quantitative Approach，Morgan-Kaufmann，San Mateo，Calif.，1990。

龙。A. V. Aho、R. Sethi和J. D. Ullman，Compiler Design: Principles, Techniques, and Tools，Addison-Wesley，Reading，Mass.，1986。

三角龙。J. L. Peterson和A. Silberschatz，Operating Systems Concepts，第二版， Addison-Wesley， Reading，Mass.，1985。

致谢

很多同事与学生阅读了本书，提出了很多对改进本书表述很有价值的建议，在此我们深表感谢。还要特别感谢Brian Kernighan、Don Knuth、Apostolos Lerios和Bob Martin，他们详细阅读了本书最初Pascal版本的手稿，并提出了很多宝贵意见。此外，我们已经收到Michael Anderson、Margaret Johnson、Udi Manber、Joseph Naor、Prabhakar Ragde、Rocky Ross和Shuky Sagiv对本书Pascal版本做出的课程测试报告，在此对他们表示由衷的感谢。

还有很多人找出了本书原稿以及Pascal版本各印次中的错误。为此，我们还要感谢以下人士：Susan Aho、Michael Anderson、Aaron Edsinger、Lonnie Eldridge、Todd Feldman、Steve Friedland、Christopher Fuselier、Mike Genstil、Paul Grubb III、Barry Hayes、John Hwang、Hakan Jakobsson、Arthur Keller、Dean Kelley、James Kuffner Jr.、Steve Lindell、Richard Long、Mark MacDonald、Simone Martini、Hugh McGuire、Alan Morgan、Monnia Oropeza、Rodrigo Philander、Andrew Quan、Stuart Reges、John Stone、Keith Swanson、Steve Swenson、Sanjai Tiwari、Eric Traut和Lynzi Ziegenhagen。

感谢Geoff Clem、Jon Kettenring和Brian Kernighan在筹备本书C语言版的过程中提出的建设性意见。

感谢Peter Ullman绘制了本书中的很多图片，感谢Dan Clayton、Anthony Dayao、Mat Howard和Ron Underwood在TEX字体方面提供的帮助，还要感谢Hester Glynn和Anne Smith在手稿准备阶段提供的帮助。

代码、勘误和注释的在线访问

大家可以匿名访问FTP主机ftp-cs.stanford.edu获取本书中主要程序的副本。请使用用户名anonymous，并用该用户名加上主机名作为密码登录该FTP。然后可以执行cd fcsc，来找到书里出现的程序。我们还打算在该目录中保存勘误信息，以及可以提供的课程讲义。

Alfred V.Aho

于新泽西州查塔姆

Jeffrey D.Ullman

于加州斯坦福

1994年7月