本书从无任何背景的初学者的角度介绍了编程的基础知识、算法与数据结构、计算理论、计算机器以及硬件方面的基础知识。

无

20世纪的教育基础是“阅读、写作和算术”，而现在是“阅读、写作和计算机科学”。学习编程是每个学生在科学和工程领域接受教

育时的重要组成部分。除了直接应用外，这也是理解计算机科学的第一步，进而理解为什么计算机对现代世界影响巨大。本书的目的

是在科学的应用环境中讲解编程相关知识。
本书的主要目标是介绍高效计算所必需的经验和基本工具，以此来增强学生的能力。我们的方法是教学生按照一种自然的、令人满意

的、创造性的方式编写程序。书中逐步引入基本概念，并通过应用数学和科学中的经典实例来说明这些概念，同时让学生亲自动手编

程来解决问题。我们设法帮助学生揭开计算的神秘面纱，建立对计算机科学领域的重要知识的基本认识。
本书中的所有程序都使用Java编程语言。我们首先教授解决计算问题的基本技能，这些技能适用于许多现代计算环境，并且是一种自

成体系的解决方案，即使没有编程经验的人也能够学会。这里强调的是编程的基本概念，而不是Java本身。在后续章节中，我们会更

多地偏重计算机科学知识而不再是编程，但是我们仍然经常使用Java程序来说明主要想法。
本书采用跨学科方法讲解传统的CS1（computer science）课程，我们强调计算在其他学科中的作用，从材料科学到基因组学到天体物

理学到网络系统。这种方法帮助学生将现代世界中数学、科学、工程和计算的基本思想融会贯通。虽然是一本为大一学生设计的CS1教

科书，但也可用于自学。
内容与特色
前三章围绕学习编程的三个阶段进行组织，包括基础知识、函数和面向对象编程。在每个阶段，我们都提供了学生需要熟练掌握的基

本技术，为进入下一个阶段的学习做好准备。本书的一大特色是使用示例程序来解决有趣的问题，并辅以丰富的练习，既有自学练习

，也有需要创造性解决方案的挑战性的问题。
第1章主要介绍变量、赋值语句、内置数据类型、控制流、数组和输入/输出（包括图形和声音等）。
第2章是学生首次接触模块化编程。我们假设学生已经熟悉数学中的函数，在此基础上引入Java函数，然后讨论函数编程的意义，包括

函数库和递归。我们强调编程时要将程序划分为可独立调试、可维护和可重用的组件，这是编程的基本思路。
第3章介绍数据抽象，重点是数据类型的概念，以及如何使用Java类机制来实现数据类型。我们教授学生如何使用、创建和设计数据类

型。模块化、封装和其他现代编程范例是这个阶段的核心概念。
接下来的四章介绍计算机科学的高级主题：算法和数据结构、计算理论以及计算机体系结构。
第4章将现代编程范例与组织和处理数据的经典方法相结合，这些方法在现代应用中仍然有效。我们介绍了用于排序和搜索的经典算法

、基本数据结构及其应用，并且强调了如何使用科学方法来理解某段代码的性能特征。
第5章通过简单的计算机抽象模型来解决计算的基本问题，这些知识不仅具有重要的理论意义，而且许多想法在实际计算中也非常重要

，甚至可以直接应用。
第6章和第7章关注计算机器及其构建方法，学习体系结构可以帮助我们理解真实世界中的计算结果——在计算理论的抽象机器和我们

使用的真实计算机之间建立联系。而且，这还有利于回顾历史，因为当今计算机和移动设备中使用的微处理器与20世纪中叶开发的第

一台计算机并没有太大区别。
本书的核心特色是注重编程在科学和工程中的应用。我们通过分析编程对其特定应用领域产生的巨大影响来引导和激发学生学习相应

的概念。我们以应用数学、物理和生物科学以及计算机科学本身为例，涉及的问题包括物理系统模拟、数值方法、数据可视化、声音

合成、图像处理、财务模拟和信息技术等。具体的例子包括第1章中基于马尔可夫链的网页排名，以及后续章节中关于渗流问题、N体

模拟和小世界现象的案例分析。这些应用程序是本书的重要组成部分，它们不仅能够引导学习过程，说明编程概念的重要性，而且为

计算在现代科学与工程领域所发挥的重要作用提供了有说服力的证据。
最后有一个短小的章节介绍了编程的发展历史。在各章中，我们还穿插介绍了图灵、冯·诺依曼等人关于计算基本思想的发展和应用

的有趣故事。
我们的主要目标是让学生掌握有效解决编程问题所需的特定方法和技能。书中使用的代码都是完整的Java程序，读者可以试着运行起

来。需要说明的是，本书主要面向编程初学者，并没有涉及大型编程问题。
教学建议
本书适用于科学应用类相关专业大一学生的计算机科学导论课程。在课堂上，学生可以在相对熟悉的专业背景下学习编程。通过本书

和相关课程的学习，学生能够熟练地将编程技能应用到他们所选专业的后续课程中，并能够认识到进一步深入学习计算机科学是很有

意义的。
对于计算机科学专业的学生，在科学应用的背景下学习编程也受益良多。为了更好地从事科研工作，计算机科学家需要具备关于科学

方法的基本知识，也需要了解计算在科学研究中的作用，并与生物学家、工程师或物理学家等传统领域的专家对于这类问题的认识保

持一致。
事实上，我们的跨学科方法使得计算机科学专业和其他专业的学生可以在同一门课程中学习编程。书中涵盖CS1规定的所有内容，而且

更注重通过具体应用引入编程概念，这更容易引起学生的学习兴趣。同时，跨学科方法让学生接触到来自不同学科的多种问题，能够

帮助他们更明智地选择自己的专业。
无论使用哪种具体的教学方法，本书都适合在学生进入大学的初期使用，这样教师可以利用高中数学及其他科学的知识来开展教学。

此外，在这一阶段学过编程的学生，之后进入专业课程时能够更有效地使用计算机。就像阅读和写作一样，编程对于任何科学家或工

程师来说肯定都是必不可少的技能。掌握了书中相关概念的学生将会在他们的一生中不断提升这种技能，从而更好地理解其专业领域

中遇到的问题和项目，并且更有效地利用计算机来解决它们。
前导课程
本书适合大一学生学习，也就是说，我们只需要科学和数学的入门级基础知识，不需要其他额外的知识作为前导。
熟练掌握数学工具和知识是学习本书的重要前提。虽然我们不讨论数学的细节内容，但是书中确实涉及高中数学知识，包括代数学、

几何学和三角学。我们认为本书的目标读者大多已经掌握了这些内容。事实上，书中很多编程概念是建立在初等数学课程基础上的，

对此学生通常比较熟悉。
好奇心也是一个重要的组成部分。理工科学生天然就带着对科学世界的迷恋，喜欢探究自然界发生的一切。为此，我们会通过简单的

程序来揭示自然世界的规律。除了高中所讲授的数学、物理、生物或化学的基础知识以外，理解这些程序不需要任何特定的知识。
我们不要求学生具备编程经验，当然，有一定编程基础也不错。讲授编程是我们的主要目标之一，所以我们假设学生都没有编程经验

。这是一门入门级的编程课程，但是那些在高中时编写过大量程序的学生也会有所收获，因为本书中涉及的问题都是跨学科的新问题

，而编程解决新问题往往是一项具有挑战性的任务。本书可以用于教授具有不同背景的学生，因为这些应用程序对新手和高手都有吸

引力。
理论上，本书也不要求学生具备使用计算机的经验，不过，现在的学生都经常使用计算机，例如，与亲友聊天、听音乐、处理照片等

。通过学习本书，他们将意识到自己能够以更加有趣而且更加重要的方式利用计算机，这会是一个激动人心同时旷日持久的过程。
总之，几乎所有大学生都可以在第一学期的课程中学习本书的内容。
教学目标
对于那些完成了本书课程的学生，当他们开始学习理工科的高年级课程时，授课教师会有什么期待呢？
本书主要面向计算机基础课程，但是任何教过编程基础课程的人都知道，在以后的课程中，教师的期望通常很高：每位老师都希望所

有学生熟悉计算机环境和课程中所要使用的方法。物理学教授可能期望学生在周末设计一个程序来进行模拟，工科教授可能期望学生

使用一个特定的包来实现微分方程的数值求解，计算机科学教授可能期望学生了解特定编程环境的细节。一门入门级课程要符合如此

多样化的期望，这现实吗? 应该为不同方向的学生开设不同的入门课程吗？
自20世纪末计算机广泛使用以来，高等院校一直受困于这些问题。我们利用本书回答了这些问题。这是一本介绍通用编程方法的教材

，适用于数学、物理、生物和化学等学科的入门课程。计算机科学致力于为所有理工科学生提供所需的基础知识，同时传递出一个清

晰的信号—计算机科学远不止程序设计这么简单。完成了本书的学习后，我们相信学生将会具备必要的知识和经验，能够适应新的计

算环境，并在不同的应用程序中有效地利用计算机。
对于学生而言，学完了本书对应的课程后，可以在后续学习中尝试什么新的课程呢？
我们想说的是，编程并不难学，而且学会有效使用计算机是非常有意义的。如果能够掌握本书中的知识，那么在未来职业生涯中遇到

各类计算机方面的挑战时，学生都有能力应对。虽然本书只涉及Java一种现代编程环境，但通过举一反三，学生将很快打开其他计算

世界的大门，并有足够的信心学习、评估和使用新的计算工具。计算机科学专业的学生将会具备深入学习的基础知识，其他理工科专

业的学生将会掌握将计算融入其他研究中的能力。
教学视频
本书配有一套完整的教学视频，网址如下：
http://www.informit.com/title/9780134493831
与传统的现场讲座一样，这些视频的目的是激发学生阅读本书的兴趣，并提升学习效果。我们的经验是这种方式比现场讲课要好得多

，因为学生可以以选定的速度播放视频，并随时回放和复习。
本书网站
在下面的网站上，可以找到本书的大量补充信息和其他相关材料：
http://introcs.cs.princeton.edu/java
网站上提供了面向授课教师、学生和普通读者的材料。这里对这些材料进行简要介绍，要想了解详细内容，读者可访问网站浏览并查

看。除了一些用于考试的材料外，其他材料都是公开的。
建立本书网站最重要的意义之一就是帮助教师和学生使用自己的计算机来讲授和学习本书。任何拥有电脑和浏览器的人都可以按照网

站上列出的方法开始学习编程。这个过程不会比下载媒体播放器或歌曲更困难。和其他网站一样，本书网站也在不断更新。对于拥有

本书的人来说，这是必不可少的资源。特别需要说明的是，网站上提供了更多的补充材料，这对于本书知识的学习是至关重要的，能

够促进计算机科学成为所有科学家和工程师所接受的基础教育的一个重要组成部分。
对于教师来说，该网站包含有关教学的信息。在过去十年中，我们每周组织两次大规模的授课，并辅以每周两次的讨论，学生以小组

为单位与老师或助教进行交流。在教学过程中，我们形成了一套自己的教学风格，并按照这套风格组织了教学材料。在本书网站中可

以下载教学幻灯片。
对于助教来说，这个网站包含了详细的习题集和编程任务，这些都是与书中的练习相对应的，而且加入了更多细节。每个编程任务都

会在有趣的应用环境中介绍一个相关概念，同时向学生提出一个充满吸引力又有些难度的问题。任务难度的递进体现了我们的教学方

法。本书网站上详细说明了所有作业，并提供了详细的、条理清楚的辅助材料，以帮助学生在规定的时间内完成作业。辅助材料包括

建议的解决方法，以及在讨论课上讲授的内容大纲。
对于学生来说，该网站可以快速访问本书中的大部分内容，包括源代码以及一些建议自学的课外材料。本书网站上也提供了许多习题

答案，包括完整的程序代码和测试数据。网站上还有大量与编程任务相关的信息，包括建议的方法、清单、常见问题解答和测试数据

等。
对于普通读者来说，本书网站可以用于访问与书籍内容相关的所有额外资源。网站上的所有内容都提供链接和其他信息渠道，以供读

者获取关于该主题的更多信息。网站上的内容非常丰富，远远超过读者的需要，但我们的目标是提供足够多的信息，确保满足每位读

者关于本书内容的兴趣。
致谢
写作本书这个项目自1992年启动以来一直处在不断的发展当中，到目前为止，有太多人为之做出了贡献，我们对此表示由衷的感谢。

特别感谢Anne Rogers一直以来的帮助；感谢Dave Hanson、Andrew Appel和Chris van Wyk耐心地解释数据抽象；感谢Lisa

Worthington和Donna Gabai，他们第一次尝试向大一学生讲授这本教材，这是一个巨大的挑战；感谢Doug Clark的耐心，帮助我们完

善了图灵机和电路方面的知识。我们也非常感谢/ dev / 126的努力；感谢普林斯顿大学25年来一直致力于讲授这本教材的教师、研究

生和教学人员，以及成千上万名努力学习本书的学生。
Robert Sedgewick
Kevin Wayne
2016年5月

计算机\基础

本书源于普林斯顿大学自1992年开始为大一学生开设的计算机科学入门课程，经过20多年的发展和完善，形成了独到的跨学科方法，并配有丰富的教辅资源。本书适用于各类理工科专业，特别关注编程在科学和工程中的应用，涵盖材料科学、基因组学、天体物理和网络系统等不同领域的实例，在讲授编程方法的同时注重培养计算思维，为专业领域的深入学习奠定基础。
本书采用Java编程语言。首先介绍解决计算问题的基本技能，包括编程基础知识、函数和面向对象编程。然后讨论计算机科学的高级主题，包括算法和数据结构、计算理论以及计算机体系结构。此外，书中还穿插介绍了图灵、冯·诺依曼等计算机科学家的历史故事。
本书网站introcs.cs.princeton.edu/java提供了大量学习材料，包括章节概览、教学PPT、源代码、习题答案等，对于教师、学生和普通读者都非常有益。
提示：为便于阅读，您手中的这本书只包含第1~4章基础内容，第5~7章进阶内容为在线资源，可访问华章网站www.hzbook.com免费下载。

作者简介
罗伯特·塞奇威克（Robert Sedgewick） 普林斯顿大学计算机科学系创始人，目前仍然在系里担任教授。他于1975年在斯坦福大学获得博士学位，师从计算机科学界泰斗高德纳教授。他是Adobe公司的董事，并曾在Xerox PARC、IDA和INRIA公司担任研究员。他所编写的《算法》系列书籍在业界具有举足轻重的影响力。
凯文·韦恩（Kevin Wayne） 自1998年开始在普林斯顿大学计算机科学系任教，曾荣获众多教学方面的奖项，包括ACM杰出教育奖。他和Sedgewick还是MOOC的先驱，他们共同开设的MOOC课程吸引了超过100万的学习者。

[美] 罗伯特·塞奇威克（Robert Sedgewick） 凯文·韦恩（Kevin Wayne） 著：罗伯特·塞奇威克（Robert Sedgewick） 普林斯顿大学计算机科学系创始人，目前仍然在系里担任教授。他于1975年在斯坦福大学获得博士学位，师从计算机科学界泰斗高德纳教授。他是Adobe公司的董事，并曾在Xerox PARC、IDA和INRIA公司担任研究员。他所编写的《算法》系列书籍在业界具有举足轻重的影响力。
凯文·韦恩（Kevin Wayne） 自1998年开始在普林斯顿大学计算机科学系任教，曾荣获众多教学方面的奖项，包括ACM杰出教育奖。他和Sedgewick还是MOOC的先驱，他们共同开设的MOOC课程吸引了超过100万的学习者。

Contents
1—Elements of Programming . . . . . . . . . . . 1
1.1 Your First Program 2
1.2 Built-in Types of Data 14
1.3 Conditionals and Loops 50
1.4 Arrays 90
1.5 Input and Output 126
1.6 Case Study: Random Web Surfer 170
2—Functions and Modules . . . . . . . . . . . 191
2.1 De?ning Functions 192
2.2 Libraries and Clients 226
2.3 Recursion 262
2.4 Case Study: Percolation 300
3—Object-Oriented Programming. . . . . . . . . 329
3.1 Using Data Types 330
3.2 Creating Data Types 382
3.3 Designing Data Types 428
3.4 Case Study: N-Body Simulation 478
4—Algorithms and Data Structures . . . . . . . . 493
4.1 Performance 494
4.2 Sorting and Searching 532
4.3 Stacks and Queues 566
4.4 Symbol Tables 624
4.5 Case Study: Small-World Phenomenon 670
5—Theory of Computing . . . . . . . . . . . . 715
5.1 Formal Languages 718
5.2 Turing Machines 766
5.3 Universality 786
5.4 Computability 806
5.5 Intractability 822
6—A Computing Machine . . . . . . . . . . . . 873
6.1 Representing Information 874
6.2 TOY Machine 906
6.3 Machine-Language Programming 930
6.4 TOY Virtual Machine 958
7—Building a Computing Device . . . . . . . . . 985
7.1 Boolean Logic 986
7.2 Basic Circuit Model 1002
7.3 Combinational Circuits 1012
7.4 Sequential Circuits 1048
7.5 Digital Devices 1070
Context. . . . . . . . . . . . . . . 1093
Glossary . . . . . . . . . . . . . . . . . . 1097



目　录
第1章　编程基础 1
1.1　你的第一个程序 2
1.2　内置数据类型 14
1.3　条件和循环 50
1.4　数组 90
1.5　输入和输出 126
1.6　案例研究：随机网页浏览 170
第2章　函数与模块 191
2.1　函数的定义 192
2.2　库和客户端 226
2.3　递归 262
2.4　案例研究：渗流 300
第3章　面向对象编程 329
3.1　使用数据类型 330
3.2　创建数据类型 382
3.3　设计数据类型 428
3.4　案例研究：N体模拟 478
第4章　算法与数据结构 493
4.1　性能 494
4.2　排序和搜索 532
4.3　栈和队列 566
4.4　符号表 624
4.5　案例研究：小世界现象 670
在线内容
第5章　计算理论 715
5.1　形式语言 718
5.2　图灵机 766
5.3　普遍性 786
5.4　可计算性 806
5.5　难解性 822
第6章　计算机器 873
6.1　信息表示 874
6.2　TOY机器 906
6.3　机器语言编程 930
6.4　TOY虚拟机 958
第7章　构建计算机器 985
7.1　布尔逻辑 986
7.2　基本电路模型 1002
7.3　组合电路 1012
7.4　时序电路 1048
7.5　数字设备 1070
历史背景 1093
词汇表 1097