致 谢 编写一本教材绝不是一个人所能完成的工作。在完成这本书的过程中，我很幸运地得到了许多有才华和有奉献精神的人的帮助。我特别要感谢斯坦福大学的以下各位同事，他们以各自不同的方式给予了我帮助： ● 过去几年一直以该书的草稿进行教学的讲师，包括Jerry Cain、Maggie Johnson、Bob Plummer、Mehran Sahami以及Julie Zelenski。 ● 我的助教，Stacey Doerr 和 Brain O Connor，他们为该书精选了作业题，很多作业作为练习题出现在该书中。 ● 所有我所在科部的教师，他们帮助我向学生解释了在我较早版本的手稿中没有包含的概念。 ● Steve Freund和Thetis开发团队的成员，他们提供了一个优秀的计算机环境供学生使用。 ● 教育部的工作人员，特别是Claire Stager和Eddie Wallace，保证了一切都进展顺利。 ● 我的关于计算机科学入门教学研讨会的各位参与者。 ● 斯坦福大学学习该课程的学生，他们完成了很多实验。 非常感谢Addison-Welsey的各位书评员提出的关于改进该书结构和质量的建议： ● Phillip Barry，明尼苏达大学 ● Martin Cohn，布兰代斯大学 ● Dan Ellard，哈佛大学 ● Gopal Gupta，新墨西哥大学 ● Phillip W. Hutto，埃默里大学 ● Randall Pruim，波士顿大学 ● Zhong Shao，耶鲁大学 我也收到了里德学院的Joe Buhler、普雷斯瓦勒公司的Pavel Curtis、巴尔的摩马里兰大学Jim Mayfield的很好的建议。该书的大部分工作是我在里德休假时完成的，非常感谢数学系Joe和他的同事，他们为我提供了十分适合工作的地方。 我还要感谢我的编辑，Susan Hartman和Addison-Welsey的所有工作人员——Cynthia Benn、Lynne Doran Cote、Jackie Davies、Julie Dunn、Peter Gordon、Amy Willcutt、Bob Woodbury和Tom Ziolkowski，感谢他们对本书和以前我出版的图书的支持。 最后，我要感谢我的搭档Lauren Rusk，她又一次展现了其开发编辑的魅力。Lauren的专业知识让该书条理更为清晰，使本书增色不少。没有她，就不可能有这样一本好书诞生。 写 给 教 师 本教程适用于大学编程课程，它覆盖了AMC Curriculum 78报告中所定义的计算机科学2标准课程的材料，并且包括Computing Curriculum 1991算法与数据结构课程中的大部分知识。 本书将教会学生现代软件工程方法论。本书的内容建立在我于1995年写的The Art and Science of C教科书的基础上，并将抽象和接口设计作为核心主题。虽然我写作这两本书是有先后顺序的，但是读者完全可以单独使用本书。本书的第Ⅰ部分包括了The Art and Science of C中学生应该掌握的所有背景知识。这些背景知识对于理解本课程其他部分中的例子和方法已经绰绰有余了。由于第Ⅰ部分的介绍是比较简单，因此学生必须熟悉计算机基础课程中涉及的基本编程概念。但是，读者不需要对C语言有所了解，因为在本书的前几章中将介绍C语言的基础。学习过The Art and Sciena of C课程的学生完全可以跳过第Ⅰ部分的内容。 在学习完了第Ⅰ部分的预备知识之后，学生可以继续该课程的学习。第Ⅱ部分将讨论递归算法。在第Ⅱ部分的4章内容中，穿插了大量的实例。根据我个人的经验，介绍递归算法的最合理时刻是在第Ⅱ门编程课程开始学习的时候。很多学生都会觉得递归是一个难以理解的概念，必须花很多时间才能较好地掌握它。如果在新学期的一开始就面临递归这个难点，那么学生将有更多的时间来掌握它。在本书中，尽可能早地介绍递归概念，其目的是让读者在作业和考试中运用这种知识。期中考试可以检查学生对递归概念的掌握情况，对于那些确确实实理解递归概念比较差的学生，可以给他们以警示，以便他们及时采取相应的补救措施。 如果想压缩学习递归的时间，那么可以跳过第Ⅱ部分的6.1节，这对整个课程的讲述没有什么影响。也许鞍点算法对于部分学生来说有点儿太复杂了，但是它却很好地说明递归算法可以使用很少的代码来解决非常困难的问题。类似地，第7章中大O的理论基础也不是该课程的重点内容。 第Ⅲ部分有双重目的：一方面，它介绍了数据结构课程中涉及的非递归算法的概念，包括堆栈、队列以及符号表；另一方面，这部分为学生提供了一些工具，从而帮助学生理解其他部分中涉及的基于接口编程的数据抽象概念。与这个概念相一致的是抽象数据类型(ADT)，它是由行为而不是由表现形式定义。 本书的一个重要特点是，它不完全使用ANSI C的工具来定义ADT，其中ADT的内部表示对于客户端来说是不可访问的。由于这样的编程风格强调了抽象的难度，因此可以培养学生具有编写良好结构的程序和模块的习惯。我认为在本书中学习的接口是个实用的工具。在许多情况下，学生可以在他们自己的代码中包含和实现这些接口。 在第Ⅲ部分的最后一章，即第11章，将介绍几个重要的概念，例如，函数指针、映射函数以及迭代器。相对来说，迭代器在斯坦福大学的课程中是新近加入的，但是教学效果相当好。根据我们的经验，减少客户代码的复杂性所带来的收益远远超过建立迭代器抽象所做工作的代价。 第Ⅲ和第Ⅳ部分的重点是抽象数据类型。在某种程度上，这是人为划分的结果。这两部分的不同之处在于，第Ⅳ部分中的抽象数据类型是用递归实现的，而第Ⅲ部分则不是。这样安排的好处是第Ⅳ部分在本书中起到综合的作用，将前两部分的递归和ADT进行综合。 尽管第14章中关于表达式树的内容可以跳过，但是我发现尽早地在课程中包括这些内容是很有价值的，因为这样可以减少对C语言编译器操作的神秘感，可以帮助学生更好地理解和控制程序。 第17章确实不是本课程的主要内容，而是为学生继续接下来的学习作的预备。本章主要使用Java语言介绍面向对象编程，讲述主要的概念。尽管有些机构已经开始采用由浅入深的顺序方式介绍Java，但是我们认为，由于下列一些原因，先介绍结构化编程方法再介绍面向对象编程方法是很有意义的： 1. Java环境的变化太快了，无法为教学提供稳固的基础； 2. 学生有必要理解结构化编程方法； 3. 如果在基础课程中强调数据抽象和接口，那么学生学习面向对象编程将更加容易。 在斯坦福大学的经验给我们的启示是，这种策略很有效，它能够使学生相对容易地接受面向对象的概念。