第1章　程序设计的基本元素 1

1.1　你的**个程序 2

1.2　内置数据类型 14

1.3　选择结构和循环结构 56

1.4　数组 100

1.5　输入和输出 140

1.6　案例研究：随机web冲浪模型 188

第2章　函数和模块 209

2.1　定义函数 210

2.2　模块和客户端 248

2.3　递归 290

2.4　案例研究：渗透原理 322

第3章　面向对象程序设计 351

3.1　使用数据类型 352

3.2　创建数据类型 402

3.2　设计数据类型 450

3.4　案例研究：N体模拟 496

第4章　算法和数据结构 511

4.1　性能 512

4.2　排序和查找 556

4.3　栈和队列 590

4.4　符号表 634

4.5　案例研究：小世界现象 684

背景 729

术语表 733

21世纪以前的教育基础是“读、写和算术”；而现在的教育基础则是“读、写和计算”。学习编程是每个科学和工程专业学生教育的重要部分。除了直接的应用外，学习编程是了解计算机科学本质的**步。计算机科学对现代社会产生了毋庸置疑的影响。本书的目的是在科学环境中向需要编程或想学习编程的人们讲授程序设计的基本方法和应用技巧。

我们的主要目标是通过提供经验和必要的基本工具使得学生更加有效地进行计算。我们的方法是向学生灌输这样的理念：编写程序是一种自然而然的、富有成就感的和充满创造性的体验。我们将循序渐进地介绍基本概念，使用应用数学和科学中的典型应用来阐述这些概念，并让学生有机会编写程序来解决相关问题。

我们使用Python编程语言来编写本书中的所有程序—在本书的标题中，我们在“程序设计”之后提及“Python”以强调本书是关于程序设计的基本概念，而不仅仅是Python本身。本书讲授了许多计算问题求解的基本技能，这些技能可以应用于许多现代计算环境中。本书自成体系，其目标人群是没有任何编程经验的人。

相对于传统的CS1课程而言，本书提供一种跨学科的方法。我们将重点讲述计算在其他学科（材料科学、基因组学、天体物理学、网络系统等）中的重要地位。跨学科的方法向学生强调一种基本思想，即在当今世界中，数学、科学、工程和计算紧密结合在一起。同时，作为CS1的课本，本书主要面向对数学、科学和工程感兴趣的大学一年级学生。当然，本书也可用于自学，或者作为程序设计与其他领域相结合的课程的补充材料。

内容范围本书根据学习编程的四个阶段来组织：基本元素、函数、面向对象程序设计和算法。在进入编程的下一阶段之前，我们将向读者提供他们所需要的基本信息，使读者有信心编写每个阶段的程序。本书所讲授方法的基本特征是使用示例程序解决所感兴趣的问题，并提供各种练习题，从自学练习题到需要创新解决方案的挑战性的难题。

基本元素包括变量、赋值语句、内置数据类型、控制流程、数组和输入/输出，以及图形和声音。

函数和模块为学生揭开了模块化程序设计的面纱。我们使用熟悉的数学函数来介绍Python函数，然后讨论使用函数编程的意义，包括库函数和递归函数。贯穿本书，我们强调一种基本理念，即把一个程序分解为可以独立调试、维护和重用的模块。

面向对象程序设计是对数据抽象的介绍。我们强调数据类型的概念，并使用Python的类机制实现数据类型。我们将教会学生如何使用、创建和设计数据类型。模块化、封装和其他现代程序设计理念是面向对象程序设计阶段的中心概念。

算法和数据结构把现代程序设计理念与组织和处理数据的经典方法结合起来，因为经典的方法依旧可以有效地用于现代应用程序。我们介绍了经典的排序和查找算法，同时也介绍了基本的数据结构及其应用，强调了使用科学方法来理解实现的性能特征。

在科学和工程中的应用是本书的一个主要特点。我们通过其对具体应用的影响来强调我们所讨论的每一个程序设计概念。我们的示例来源于应用数学、物理学、生物科学、计算机科学本身，并包括物理系统模拟、数值方法、数据可视化、声音合成、图像处理、金融模拟和信息技术。具体的示例包括第1章用于网页排名的马尔可夫链以及渗透问题、N体模拟、小世界现象的案例研究。这些应用都是正文不可分割的组成部分，为学生提供了资料，表明了程序设计概念的重要性，并提供了计算在现代科学和工程中扮演着重要角色的令人信服的证据。

我们的主要目标是教授学生有效解决任何编程问题所需要的具体机制和技能。我们完全使用Python程序，并鼓励读者也使用Python程序。我们关注个人的程序设计，而不是大型的程序设计。

本书在大学课程中的使用本书主要面向大学一年级课程，其目标是教授新生在科学应用的背景下进行编程。根据本书所讲授的内容，将来主修科学或工程技术领域的学生都将学会在熟悉的背景下编程。修完基于本书的任何课程的学生将为在后续科学和工程技术课程中应用他们的技能做好准备，并会意识到本书所讲授的内容对进一步学习计算机科学是非常有益的。

特别地，将来主修计算机科学的学生将会受益于在科学应用的背景下学习编程。与生物学家、工程师和物理学家一样，计算机科学家在科学方法中也需要相同的基本背景以及科学计算角色的展示。

实际上，跨学科的方法使得大专院校可给将来主修计算机科学的学生以及主修其他科学和工程技术的学生教授同一门课程。我们覆盖了CS1所规定的资料，但是对应用的关注给相关概念带来了活力，并激发了学生学习这些概念的兴趣。跨学科的方法向学生展示了许多不同学科中的问题，可帮助他们更明智地选择主修方向。

无论采用哪种具体机制，本书的使用**安排在全部课程的早期。首先，这种安排允许我们利用高中数学和科学中所熟悉的资料。其次，学生在大学课程的早期学习编程将帮助他们在继续学习其专业课程时有效地使用计算机。像阅读和写作一样，程序设计很显然也是任何科学家和工程师的一项基本技能。掌握本书概念的学生将持续不断地发展这种技能，并从利用计算来解决问题或更好地理解其选择领域的问题和项目中受益。

先修条件本书非常适合于科学和工程技术专业的大学一年级学生。也就是说，我们不需要其他预备知识，本书的知识要求与其他入门级科学和数学课程的要求基本一致。

完备的数学知识很重要。我们没有详细阐述相关的数学知识，但引用了学生在高中已经学习的数学课程，包括代数学、几何学和三角学。本书目标人群中的大多数学生都自动满足这些需求。事实上，我们充分利用了他们在基本课程中所熟悉的知识来介绍基本的编程概念。

科学的求知欲也是一个重要的部分。科学和工程技术的学生天生对如何进行科学探究以帮助解释自然本质的能力非常着迷。我们使用简单的关于自然界的程序示例支持这种偏爱。本书任何特定的知识都没有超出高中课程中的数学、物理、生物和化学的知识范围。

程序设计经验不是必需的，但却是有益的。讲授程序设计是我们的主要目标，因此本书没有要求任何先行的程序设计经验。然而，编写程序解决一个新问题是一项富有挑战性的智力任务，所以在高中阶段编写了许多程序的学生会从选修基于本书的程序设计入门课程中受益。本书可满足各种不同背景的学生的需求，因为本书中的应用无论对新手还是专家都具有吸引力。

使用计算机的经验也不是必需的，况且这根本不是问题。现在大学生经常使用计算机与亲朋好友交流、听音乐、处理照片等。认识到自己可以以有趣而又重要的方式驾驭计算机，是激动人心的。

总之，几乎所有科学和工程技术领域的学生都可以在**个学期的课表中选修基于本书的课程。

目标在科学和工程技术专业的高级课程中，教师希望完成基于本书的课程的学生学到什么样的知识呢？我们覆盖了CS1课程，但任何讲授入门级程序设计课程的教师都知道，教授后续课程的教师期望值很高：每个教师都希望所有的学生熟悉所需使用的计算环境和方法。物理学教授可能期望某些学生在周末设计一个程序运行一个模拟；工程学教授可能期望某些学生使用一个特定的软件包并基于数值方法求解微分方程；计算机科学教授可能期望特定编程环境的详细知识。本书真的可以满足这些不同的期望吗？对于不同的学生，是否需要不同的入门级课程？自从20世纪后期计算机被广泛使用以来，大专院校就一直受到这些类似问题的困扰。对于这些问题，我们给出的解答是本书介绍通用的程序设计入门方法，类似于数学、物理学、生物学和化学中的普遍接受的入门级课程。本书努力为科学和工程技术专业的学生提供必要的基本准备，同时也清楚地传递这样的信息：理解计算机科学比程序设计更重要。学习过本书的学生，教师可期望他们拥有适应新的计算环境和在不同应用中有效利用计算机的必要知识和能力。

完成基于本书的课程的学生，期望在后续课程中学习到什么呢？我们的观点是程序设计并不难学，并且利用计算机能力意义深远。掌握了本书知识的学生可为其未来职业生涯中解决计算挑战做好准备。他们学会了现代编程环境（例如本书介绍的Python语言所提供的编程环境），将为未来可能遇到的任何计算问题打开一扇大门，同时也获得了学习、评价和使用其他计算工具的信心。计算机科学专业的学生将准备好去进一步追寻这些兴趣，科学和工程技术专业的学生将准备好将计算融合到自己的研究中。