本书面向初学者，以跨学科的方法介绍计算机科学的基本知识。全书包括两个部分，第一部分介绍编程，包括基本元素、方法、面向对象编程和算法。第二部分则介绍计算机科学的高级主题：算法和数据结构、计算理论和计算机体系结构。本书内容丰富、循序渐进，适合作为高校本科生计算机科学入门课程的教材。

普林斯顿大学历经近30年打造的计算机科学入门课

20世纪的教育基础是“阅读、写作和算术”，现在则是“阅读、写作和计算”。学习编程是科学和工程领域教育的重要组成部分。除了直接应用外，这是理解计算机科学的第一步，进而能够理解为什么计算机会对现代世界产生如此巨大的影响。本书的目的是在科学的应用环境中讲解编程的相关知识。
我们的主要目标是通过提供有效使用计算所需的经验和基本工具来增强学生的能力。我们的方法是教会学生按照一种自然的、令人满意的、创造性的方式编写程序。我们逐步引入基本概念，并引入应用数学和科学领域的经典应用来说明概念，同时为学生提供编写程序来解决问题的机会。我们也设法帮助学生揭开计算的神秘面纱，使他们建立对计算机科学领域的重要知识的基本认识。
本书中的所有程序都使用Java编程语言编写。本书的第一部分教授解决计算问题的基本技能，所使用的编程方法适用于许多现代计算环境，这是一个完整的解决方案，即使没有编程经验的人也能够学会。这里我们强调的是关于编程的基本概念，而不是Java本身。本书的第二部分更多地偏重计算机科学的知识而不再是编程，但是我们仍然经常使用Java程序来交流主要想法。
本书是按照跨学科的方法对传统CS1（computer science）课程进行扩充，我们强调计算在其他学科中的作用，从材料科学到基因组学、天体物理学和网络系统。这种方法会强化学生对于“数学、科学、工程和计算在现代世界中交织在一起”的基本认识。虽然本书是为一年级大学生设计的CS1教科书，但也可用于自学。
范围　本书的第一部分围绕学习编程的三个阶段进行组织：基本元素、函数、面向对象编程。我们提供了读者在进入下一个层次之前需要熟练掌握的基本内容。我们的方法的一个基本特征是使用示例程序来解决有趣问题，并辅以练习，包括从自学练习到需要创造性解决方案的挑战性问题。
基本元素包括变量、赋值语句、内置数据类型、控制流、数组和输入/输出（包括图形和声音等）。
函数是学生首次接触模块化编程的内容。我们假设学生已经熟悉数学函数，在此基础上引入Java函数，然后考虑函数编程的意义，包括函数库和递归。我们强调编程时要将程序划分为可独立调试、可维护和可复用的组件，这是编程的基本思路。
面向对象编程是关于对数据抽象的介绍。我们强调数据类型的概念及其使用Java类机制的实现。我们教授学生如何使用、创建和设计数据类型。模块化、封装和其他现代编程范例是这个阶段的中心概念。
本书的第二部分介绍计算机科学的高级主题：算法和数据结构、计算理论和计算机体系结构。
算法和数据结构将现代编程范例与组织和处理数据的经典方法相结合，这些经典方法在现代应用中仍然有效。我们介绍了用于排序和搜索的经典算法、基本数据结构及其应用，并且强调了如何使用科学方法来理解某段代码的性能特征。
计算理论使用简单的计算机抽象模型，帮助我们解决计算的基本问题。这些知识不仅具有重要的理论意义，而且许多想法在实际的计算应用中也是非常相关甚至可以直接应用的。
计算机体系结构提供了一个理解真实世界中实际计算的途径—在计算理论的抽象计算设备和我们使用的真实计算机之间建立了联系。而且，体系结构的研究还提供了与过去的联系，因为当今计算机和移动设备中的微处理器与20世纪中叶开发的第一台计算机中的没有太大区别。
本书的关键特征之一是注重编程在科学和工程中的应用。我们通过分析编程对特定应用领域产生的巨大影响来引导和激发学生学习每个相应的编程概念，以应用数学、物理和生物科学以及计算机科学本身为例，涉及的问题包括物理系统模拟、数值方法、数据可视化、声音合成、图像处理、财务模拟和信息技术等。具体的例子包括第1章中基于马尔可夫链的网页排名处理，以及后续章节用于解决渗透问题、多体模拟和小世界现象的案例分析。这些应用程序是本书的重要组成部分。它们能够引导学生学习相关主题，说明编程概念的重要性，并为计算在现代科学与工程领域所发挥的重要作用提供有说服力的证据。
在后面的章节中强调了编程发展的历史知识，也着重介绍了艾伦·图灵、冯·诺依曼等人关于计算的基本思想发展和应用的有趣故事。
我们的主要目标是让学生掌握有效解决任何编程问题所需的特定机制和技能。书中使用的代码都是完整的Java程序，读者可以试着使用它们来学习编程。需要说明的是，本书专注于个人编程，并没有涉及大型编程问题。
如何使用本书　本书适合科学应用类相关专业一年级本科生学习计算机科学课程使用。使用本书时，大学生可以在相对熟悉的专业背景下学习编程。通过本书和相关课程的学习，学生能够熟练地将编程技能应用到他们所选专业的后续课程中，并能够认识到深入学习计算机科学是很有意义的。
对于计算机科学专业的学生，在科学应用的背景下学习编程也会受益良多。为了更好地从事科研工作，计算机科学家需要具备关于科学方法的基本知识，也需要了解计算在科学研究中的作用，并应该与生物学家、工程师或物理学家等对于这类问题的认识保持一致。
事实上，我们的跨学科方法可以让计算机科学专业的学生和其他专业的学生在同一门课程中学习编程。我们涵盖了CS1要求的所有内容，而且更注重通过具体应用引出编程的相关概念并吸引学生学习。同时，我们的跨学科方法能够让学生接触到来自不同学科的多种问题，从而帮助他们更明智地选择自己的专业。
无论使用哪种具体的机制，本书都适合在整个大学教学过程的初期使用。首先，这种教学时间的安排使得我们能够利用高中的数学和科学相关知识开展教学；其次，在进入专业时，在大学课程初期学习了编程的学生将能够更有效地使用计算机。就像阅读和写作一样，编程对于任何科学家或工程师来说肯定都是必不可少的技能。掌握了本书相关概念的学生将会在他们的一生中不断地发展这种技能，从而能够更好地理解在他们所选择的领域中出现的问题和项目，并能够更好地利用计算机来解决它们。
前导课程　本书适合一年级本科生。也就是说，只需要科学和数学的入门级基础知识，而不再要求其他额外的知识作为前导。
熟练掌握数学工具和知识是学习本书的重要前提。虽然我们不讨论数学的细节内容，但是确实涉及了学生高中所学的数学课程，包括代数学、几何学和三角学。我们认为本书的目标受众基本掌握了这些知识。事实上，我们的很多编程概念建立在他们相对熟悉的初等数学课程的基础上。
科学好奇心也是一个重要的组成部分。理工科学生天然就迷恋科学探究，喜欢探究自然界发生的一切。我们利用他们的这种爱好，在书中通过简单的程序揭示自然界的规律。除了高中课程所讲授的数学、物理、生物或化学的基础知识以外，我们不需要任何特定的知识。
编程经验不是必需的，如果有编程经验也无妨。讲授编程是我们的主要目标之一，所以我们假设学生都没有编程经验。这是一本入门性质的编程书，但是那些在高中编写了大量程序的学生也可以在学习中有所收获，因为本书中涉及的问题都是跨学科的新问题，而通过编程解决新问题往往是具有挑战性的智力任务。本书适合具有不同背景的学生阅读，因为这些应用程序对新手和专家都有吸引力。
学生不必具备使用计算机的经验。当然，大学生经常使用计算机。例如，与亲友交流、听音乐、处理照片，等等。在本书的学习中，他们将意识到能够以更有趣而且更加重要的方式利用自己的计算机，这会是一个激动人心同时又持久的过程。
总之，几乎所有的大学生都可以在第一学期的课程中学习本书的内容。
目标　对于那些完成了本书课程的学生，当他们开始学习理工科的高年级课程时，他们的教师会对他们有什么期待呢？
本书涵盖了CS1课程，但是任何教过编程基础课程的人都知道，在后续课程中，教师的期望通常很高：每位教师都希望所有的学生能够熟悉计算机环境和课程中所要使用的方法。物理学教授可能会期望学生在周末设计一个程序来进行模拟，工科教授可能会期望学生使用一个特定的包来实现微分方程的数值求解，计算机科学教授可能期望学生了解特定编程环境的细节。一个入门级课程满足如此多样化的期望，这现实吗？每类学生都应该有不同的入门课程吗？
自20世纪后半期计算机广泛使用以来，高等院校一直受这些问题的困扰。我们利用本书给出了这些问题的答案。这是一本介绍通用编程方法的教材，类似于普遍接受的数学、物理、生物和化学等学科的入门课程。本书致力于为所有理工科学生提供所需的基础知识，同时传递出一个清晰的信号，即对计算机科学的了解远不止程序设计这么简单。完成了本书的学习，我们相信学生将具备必要的知识和经验，能够适应新的计算环境，并在不同的应用程序中有效地利用计算机。
对于学生而言，学完了本书对应的课程之后，在后续的学习中可以尝试什么新的课程呢？
我们认为编程并不难学，而且学会利用计算机的力量是非常有价值的。掌握了本书内容的学生，以后将有能力应对职业生涯中出现的各类计算机使用上的挑战。他们学习了如Java提供的现代编程环境，有助于打开任何以后可能遇到的计算问题的大门，并有足够的信心学习、评估和使用其他新的计算工具。对计算机科学感兴趣的学生能够具备深入学习的基础知识，其他理工科学生则可具备将计算融入其他研究中的能力。
本书官网　在下面的网站中，可以找到本书的大量补充信息和其他相关材料：
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年来一直致力于讲授这本教材的教师、研究生和教学人员，以及成千上万名努力学习本书的大学生。

计算机\基础

本书基于“编程是21世纪科学和工程领域教育的重要组成部分”这一趋势，以Java语言为工具，通过跨学科方式对计算机科学进行了生动有趣的介绍，非常适合作为学生和对计算机感兴趣的读者的入门教材。读者只需具备科学和数学的基础知识，便可通过本书开启计算机科学之旅！

本书特点
本书以解决实际问题为宗旨，关注如何通过计算机和编程来解决数学、科学、工程等领域的实际问题。同时，帮助读者揭开计算的神秘面纱，建立对计算机科学领域的系统认知。
本书第一部分基于Java语言，围绕编程的三个阶段组织内容，使读者了解编程的基本元素、函数和面向对象编程的基本知识。第二部分主要介绍算法和数据结构、计算理论和计算机体系结构等高级主题。此外，本书还强调了计算机发展的历史知识和计算思想的发展与应用。
本书的另一独特之处是通过构建一台“玩具型”计算机，分析程序的执行过程，将计算机底层的工作原理和设计方法巧妙融合，更有效地培养读者对计算机系统的理解与认识。

作者简介
罗伯特·塞奇威克（Robert Sedgewick） 普林斯顿大学计算机科学系教授，从1985年开始担任系主任。他于斯坦福大学获得博士学位，师从计算机科学界泰斗高德纳教授。他曾任Adobe公司的董事，并曾在Xerox PARC、IDA和INRIA公司担任研究员。他所编写的算法系列书籍令大批计算机学习者受益匪浅。
凯文·韦恩（Kevin Wayne） 自1998年开始在普林斯顿大学计算机科学系任教，曾荣获2014年ACM杰出教育奖以及普林斯顿大学多个教学方面的奖项。他和Sedgewick教授一起开设计算机导论和数据结构与算法的入门课程，他们共同开设的MOOC课程已吸引了超过100万的学习者。

[美]罗伯特·塞奇威克（Robert Sedgewick） 凯文·韦恩（Kevin Wayne） 著：罗伯特·塞奇威克（Robert Sedgewick） 普林斯顿大学计算机科学系教授，从1985年开始担任系主任。他于斯坦福大学获得博士学位，师从计算机科学界泰斗高德纳教授。他曾任Adobe公司的董事，并曾在Xerox PARC、IDA和INRIA公司担任研究员。他所编写的算法系列书籍令大批计算机学习者受益匪浅。
凯文·韦恩（Kevin Wayne） 自1998年开始在普林斯顿大学计算机科学系任教，曾荣获2014年ACM杰出教育奖以及普林大学大学多个教学方面的奖项。他和Sedgewick一起开设计算机导论和数据结构与算法的入门课程，他们共同开设的MOOC课程已吸引了超过100万的学习者。

信息革命带来了科技的突飞猛进，使我们前所未有地感受到了技术的力量。究其本源，当前的各种便利无不依赖于电子计算体系所支撑的强大算力。编程也好，算法也罢，无外乎对于算力的驾驭问题。
细说起来，编程又分为编程语言和编程思想。如果把编程语言比作武功招式，那么编程思想就是内力。按照传统计算机知识体系，以熟悉一门编程语言作为起手式和基本功，继而开始学习数据结构、各种算法设计、计算机组成原理、编译原理等知识模块，再深入研究可计算性原理、形式语言与自动机等内容。如此从运用入手继而归溯计算机构造方法乃至思想的路径，虽然有助于循序渐进地了解和掌握程序的运行规律、编程语言的设计思想，以便深入理解如何写出优秀的代码。但是，这一路径的每个知识模块背后都是数部艰深的巨著，对于那些希望短时间内能够掌握程序设计思想和语言运用的学习者来说，这趟计算机寻源之旅显得有些漫长。
而本书恰为上述读者提供了一条“捷径”，作者是来自普林斯顿大学的两位大师Robert Sedgewick和Kevin Wayne，书中巧妙地区分了“程序设计思想”与“编程语言使用”之间的微妙关系，通过对Java语言的学习，讲述了通过程序解决问题的重要思路，而没有拘泥于Java的语法和语言特性。更为精彩的是，本书在后半部分构建了一台“玩具型”计算机，并分析了它如何执行前半部分写出的程序。最终把我们熟知的各类知识和应用场景，与计算机深层的工作原理和设计方法结合在了一起。本书已经被普林斯顿大学等多所国际知名大学广泛采用，堪称好评如潮。此次我们配合机械工业出版社引进、翻译本书，就是希望能够为想要攀登计算机这座新世纪高峰的读者提供一条新的便捷之道。
本书能够顺利成稿，要衷心感谢南开大学嵌入式系统与信息安全实验室的孙承君、刘希明、刘振、尹腾召、赵洋、闫美君、权玮虹、曹丁元、李浩然等同学在全书翻译过程中付出的辛苦努力；感谢南开大学计算机学院与网络空间安全学院的各位老师在本书翻译过程中提供的指导和支持；要感谢机械工业出版社的各位同仁的鼎力协助。本书的若干个相似版本均有前辈或同仁进行了翻译，阅读这些译著的过程令我们受益匪浅，特此表示感谢。限于译者水平和经验，译文中难免存在不当之处，恳请读者提出宝贵意见。
最后，还要感谢徵徵和点点两位小朋友，要不是你们，生活不会如此快乐；要不是你们，这本书估计早就翻译完了吧！

译者于马蹄湖畔
2019年9月

出版者的话
译者序
前言
程序列表
电路列表
第1章　编程元素1
1.1　你的第一个程序1
1.2　内置数据类型7
1.3　条件语句与循环语句29
1.4　数组55
1.5　输入/输出76
1.6　案例研究：随机网络冲浪101
第2章　函数和模块113
2.1　函数的定义113
2.2　库和客户程序133
2.3　递归154
2.4　案例研究：渗透176
第3章　面向对象编程193
3.1　使用数据类型193
3.2　创建数据类型224
3.3　设计数据类型252
3.4　案例研究：多体模拟279
第4章　算法和数据结构287
4.1　性能287
4.2　排序和搜索308
4.3　栈和队列327
4.4　符号表362
4.5　案例研究：小世界现象389
第5章　计算理论415
5.1　形式语言416
5.2　图灵机447
5.3　普遍性460
5.4　可计算性471
5.5　难解性480
第6章　构建一台计算机509
6.1　信息表示509
6.2　TOY计算机529
6.3　机器语言编程544
6.4　TOY虚拟机559
第7章　构建计算设备574
7.1　布尔逻辑574
7.2　基本电路模型583
7.3　组合电路589
7.4　时序电路610
7.5　数字设备623
后记 637
术语表 639
索引 645
API 688