像计算机科学家一样思考C++

像计算机科学家一样思考C++

[美]Allen B.Downey　著

黄鑫　夏思雨　译

人民邮电出版社

北京

Simplified Chinese translation copyright ©2013 by Posts and Telecommunications Press

ALL RIGHTS RESERVED

How To Think Like A Computer Scientist, C++ Version, First Edition, by Allen B. Downey

ISBN-13: 978-1441419057

Copyright © 1999 by Allen B. Downey

本书中文简体版由作者Allen B. Downey授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。

版权所有，侵权必究。

黄鑫，毕业于西安交通大学。多年软件开发经验，对设计大型分布式系统有独到的见解。对将更多的开源项目引入Windows平台有浓厚的兴趣。目前致力于推广持续交付这一实践。希望通过自己的努力，让技术改变世界。微博：http://weibo.com/dummyone

夏思雨，1987年8月出生于陕西西安。2009年毕业于华中科技大学，2012年毕业于北京邮电大学。现就职于思特沃克软件技术（西安）有限公司，从事软件开发。微博：http://weibo.com/evainexia

Allen B. Downey是美国Olin工程学院的计算机科学副教授。他曾经在Wellesley College、Colby College和U.C. Berkeley教授计算机科学课程。他在MIT获得学士和硕士学位，并且从U.C. Berkeley获得计算机科学博士学位。Allen基于自己教授计算机程序设计课程的经验，开创了“像计算机科学家一样思考（How to Think Like a Computer Scientist）”的教学理念和方法，并由此编写了几本程序设计语言的图书。其中，《Think Python》、《Think Complexity》由O’Reilly出版；《Think Java》、《Think C++》也广受关注和好评。

本书旨在教会你如何像计算机专家一样思考。我喜欢计算机专家的思考方式，因为他们综合了数学、工程和自然科学的最佳特性。计算机专家像数学家一样，运用形式语言来表达思想（尤其是计算指令）；又像工程师一样进行设计，将组件装配到系统里并对可替换的部件进行评估权衡；还像自然科学家一样，观察复杂系统的行为，形成假设并通过实验来证明预测。

解决问题是一个计算机专家应该具备的最重要的单一技能。该技能包括明确表述问题的能力，有创意地思考解决方案以及清楚准确地表述解决方案。人们后来发现，学习编程的过程是练习解决问题技巧的一个相当好的机会。这就是为什么本章叫做“编程方式”。

同时，本书的另一目的是帮助你准备计算机科学AP考试¹。尽管我们可能并没有直接实现这一目标。比如，本书并没有很多类似AP考试题的练习。但从另一个角度说，如果你完全理解了本书中的概念和C++编程的细节，你就可以在考试中有一个良好的表现。

注释：¹编者注：AP考试全称AdvancedPlacement，是美国大学预修课程。由美国大学理事会主持，AP成绩不但可以抵扣成功申请美国大学的同学入学后相应课程的学分，而且AP成绩也是美国各大学录取学生的重要依据。

你即将学习的编程语言是C++。自1998年起的AP考试都以C++为基础。在这之前，采用的是Pascal。C++和Pascal都是高级编程语言，你可能听说过的其他高级语言有Java、C和FORTRAN。

你可能从“高级编程语言”这个名字中得知还有低级编程语言。低级编程语言一般指的是机器语言或者汇编语言。一般来说，计算机只能执行用低级语言编写的程序。因此，高级语言编写的程序需要先转换成低级语言再执行。高级语言的一个小缺点就是这一转换过程需要耗费一些时间。

但是，高级语言具有巨大的优势。首先，用高级语言编程要容易得多，这意味着该程序的编程时间较短，简明易读，正确性较高。其次，高级语言具有可移植的优势。这意味着用高级语言编写的程序只要经过略微的修改就可以在不同的计算机操作系统上运行。而用低级语言编写的程序只能在某一种计算机系统上运行，若要在另一种系统上运行，则需要重新编写代码。

鉴于这些优势，几乎所有的程序都是用高级语言编写。低级语言只应用在少数特殊场景中。

有两种将高级语言翻译成低级语言的方式：解释或者编译。解释器就是一个读取高级程序并执行的程序。实际上，解释器逐行翻译程序，交替读取代码行及执行命令，如图1-1所示。

图1-1

编译器则会在执行命令前，一次性地将全部高级程序代码翻译成机器语言。通常可以将编译程序作为一个单独的步骤，稍后再执行编译后的代码。在这种情况下，高级程序称为源代码；编译后的程序称为目标代码或者可执行代码。

以下面这种情况为例，假设你用C++编写程序。你可能选择一个文本编辑器来编写程序（文本编辑器就是一个简单的文字处理器）。当程序编写完成时，可以将它保存为 program.cpp。program 是你自己命名的文件名，后缀.cpp 则表示文件为 C++源代码。

然后，根据编程环境，可以关闭文本编辑器，运行编译器。编译器会读取源代码，编译源代码并创建一个包含目标代码的新文件 program.o ，或者可执行文件program.exe，如图1-2所示。

图1-2

下一个步骤就是运行程序，这一步需要程序的执行器。程序的执行器需要加载可运行程序（从硬盘复制到内存）并让计算机开始执行程序。

尽管这一过程看起来有点复杂，但是好消息是在绝大多数的编程环境（有时称为开发环境）中，这些步骤已经能够自动执行。一般来说，只需要编写一段程序，输入一条命令就可以完成编译和运行过程。另一方面，了解程序执行过程中有哪些步骤在后台运行是很有用的，这样在出错的时候你可以很快发现问题所在。

程序就是详细说明如何进行一次计算的一个指令序列。该计算可能是数学计算，比如，解方程组或者计算多项式的根；也可能是符号计算，比如，在文件中搜索和替换文本或者编译一个程序（够奇怪了）。

不同编程语言中的指令（命令或者描述）看起来都不一样，但是每种语言都有一些基本的功能。

输入：从键盘或者其他设备读取数据和文件。

输出：向显示器或者其他设备输入数据，或将数据写入文件。

数学计算：完成基本数学运算，如，加法和乘法等。

测试：检查特定条件并按适当序列执行指令。

复现：在有一定可变性下重复执行某些动作。

不管你相信与否，这几乎是一个程序所有的功能。你所使用过的每个程序，不管多复杂，都是由或多或少类似这样的功能组成的。因此，描述程序的一个方法就是将大而复杂的任务划分成尽可能小的子任务，直到这些小的子任务可以用这些基本功能中的某一个完成。

编程本身是一个复杂的过程，并且由人类而不是机器完成，所以经常会发生一些错误。由于一些奇怪的原因，程序中的错误称为bug，而追踪定位bug并且将其修正的过程则称为调试（Debug）。

程序中发生的错误有不同的种类，知道如何分辨不同的错误可以更快速地定位bug的位置。

编译器只能编译语法正确的程序，否则会导致编译过程失败，无法运行程序。语法指的是程序结构以及与该结构相关的规则。

以英语语法为例，一个句子必须以大写字母开头，句号结尾。诸如“this sentence contains a syntax error.”和“So does this one”这样的两个句子都包含语法错误。

对大多数读者来说，少量语法错误并不是什么大问题。这就是为什么我们可以毫无障碍地阅读E.E.卡明斯的诗歌。

但是编译器并不是如此的宽容。如果你的程序中出现一处语法错误，编译器就会输出错误消息并且退出，而你就无法再运行自己的程序。

更糟糕的是，C++中具有比英语更多的语法规则，并且大多数时候你从编译器得到的错误消息都没有太大帮助。在你刚开始学习编程的时候，你很可能会花费大量的时间查找语法错误。不过随着你经验日益丰富，发生和查找错误需要的时间都会越来越少。

第二种错误是运行时错误。将其称为运行时错误，是因为该错误只有在程序运行时才会发生。

接下来的几周我们要写的各种程序中，运行时错误很少发生。所以你可能需要一段时间才会遇到¹。

注释：¹这不是个好事情吗？——译者注

第三种错误是逻辑和语义错误。如果程序中出现逻辑和语义错误，计算机不会产生任何错误消息，编译和运行过程都会成功。但是程序并没有做它应该做的，而是做了其他的事。只有在极少情况下它才会做你让它做的。

问题在于你写的程序不是你本意想写的程序，程序的意义（语义）有错误。识别逻辑错误是一件很棘手的事情，因为它需要你回头查看程序的输出并且尝试发现哪里出错了。

在本书的学习过程中，你应当获得的最重要的技能之一就是调试。尽管错误的出现让你沮丧，但是调试是编程过程中最需要脑力、最富有挑战性而且最有趣的部分了。

在某些方面调试就像侦察。你需要面对线索，推断出具体过程和事件，这些过程和事件能够得到你所看到的结果。

同时，调试又像是科学实验。一旦你想出来哪里可能出错了，你就会修改你的程序再次尝试。如果你的假设成立，你可以预测到修改后的结果并离可工作的程序更近一步。如果假设失败了，你需要提出一个新的假设。正如福尔摩斯所说，“当你排除了一切不可能的因素之后，剩下的无论看起来有多么不合理，也一定是事实。”（来自柯南道尔的《四个人的签名》）。

对一些人来说，编程和调试是同一件事情。也就是说，编程的过程就是逐步调试直到程序完成你想要的功能的过程。这种观点表明，任何时候你都应该从一个可以正常运行的程序入手，然后进行小的改动并调试通过，这样你的程序可以一直工作。

比如，Linux操作系统包含成千上万行代码，但是它最开始也只是 Linux Torvalds用于探索英特尔 80386芯片的简单程序。Larry Greenfield说：“Linus早期的工程之一就是一段在输出AAAA和BBBB之间切换的程序。然后进化成了Linux。”（来自Linux用户指导测试版1）。

在稍后的章节里，我会提出关于调试和编程练习的更多建议。

自然语言是指人类表达的语言，比如，英语、西班牙语和法语。自然语言不是由人类设计（尽管人类尝试对其强加某些命令）的，而是通过自然演化的。

形式语言则是由人类为了某些特殊应用而设计的语言。例如，数学中使用的记号法就是一种特别擅长表示数字和符号间关系的形式语言。化学家使用某种形式语言来表示分子间的化学结构。而最重要的是：

编程语言是用于表达计算过程的形式语言。

正如我之前提到的，形式语言具有严格的语法规则。例如，3+3=6是一个语法正确的数学表达式，但是3=+6$就不是。同样，H₂O是一个语法正确的化学名词，但是₂Zz就不是。

语法规则有两种：与标识有关的规则或者与结构有关的规则。标识是语言的基本元素，如单词、数字以及化学元素。3=+6$的问题之一是$不是数学里合法的标识（至少据我所知是这样）。类似地，因为化学里没有缩写为Zz的元素，所以 ₂Zz也是不合法的。

第二种语法错误是表达式结构的问题。所谓结构，就是标识的顺序。表达式3=+6$在结构上就不合法，因为不能在等号之后直接使用加号。类似地，分子表达式需要在元素名之后添加下标而不是之前。

当你阅读一句英文或者形式语言的一条语句，你需要找到它的结构（尽管这一行为在阅读自然语言时是无意识的）。这一过程称为语法分析。

举个例子，当你听到一句话：“另一只鞋掉了，”你会知道“另一只鞋”是主语而“掉”是动词。一旦你解析了一个句子的语法，你会了解它是什么意思，就是句子的语义。假设你知道鞋是什么意思和掉了是什么意思，你就会明白这句话的大致含义。

尽管形式语言和自然语言有很多共同的特性，但是他们在标识、结构、语法以及语义上有很多不同。

二义性：自然语言充满了二义性，需要人们根据上下文线索和其他信息理解。而形式语言几乎没有二义性，即形式语言的任何表达式都仅有一个含义，无关上下文。

冗余性：为了弥补歧义和减少误解，自然语言引入了很多冗余，结果自然语言通常都很啰嗦。形式语言则更简明扼要。

文学性：在自然语言中有很多习语和暗喻。如果我说另一只鞋掉了，很有可能指的不是鞋，也没有什么东西掉了。而形式语言则精确地描述了它们表达的意思。

习惯于自然语言的人们（每个人）要适应形式语言通常都很艰难。在某些方面形式语言和自然语言的差别就像是诗歌和散文，但是更甚。

诗歌：词汇的发音和意义都十分重要，而整首诗歌创造某种效果或者情感回应。诗歌中随处可见精心设计的双关语。

散文：相较于诗歌，散文中文字本身的含义更为重要，同时结构也具有更大的意义。散文虽然也有二义性，但是比诗歌容易分析。

程序：计算机程序的含义是纯字面且无歧义的，并且可以通过分析标识和结构将其完整理解。

关于阅读程序（还有其他一些形式语言）的几条建议如下。首先，形式语言比自然语言难以理解得多，需要花费更长时间来阅读。其次，形式语言的结构很重要。所以从头到尾的完整阅读并不是一个好方法。应该学会先将程序解析，识别标识和解释结构。最后，记住细节决定成败。像自然语言中无关大碍的错误拼写和标点符号等，在形式语言中可能产生很大的影响。

按照惯例，人们用新语言编写的第一个程序叫做“Hello World”。因为它所做的所有事情就是输出“Hello,World”。在C++中，这个程序是这样的：

#include <iostream.h>

// main: generate some simple output

void main ()

{

　 cout << "Hello, world." << endl;

　 return 0

}

有些人根据“Hello World”程序的简洁程度评判编程语言的质量。按照这个标准， C++做得相当不错。即便如此，这个简单的程序里依然包含着很难对编程新手解释的某些语言特性。现在，我们会先忽略其中一部分，比如第一行。

第二行以“//”开头，代表注释。注释是指在程序中插入的用于解释程序行为的一些文字。当编译器看到“//”时，它会忽略从该位置开始到行尾的整行内容。

第三行，你暂时可以忽略void，但是请注意main。main是指示程序入口点的特殊命名。当一个程序开始执行时，它从main中的第一条语句按顺序执行直到末尾，然后退出。

main中的语句数目没有限制，但是该例子只包含一条。这是一条基本的输出语句，表示在屏幕上输出或者显示一条消息。

cout 是由系统提供的允许你把内容输出到屏幕的特殊对象。<<符号是一个操作符，表示将一个字符串应用于cout。这会使该字符串显示在屏幕上。

endl也是一个特殊符号，代表一行的结束。当发送endl给cout时，屏幕上的光标会移动到下一行。所以，当下一次输出时，新的内容会在下一行显示。

像所有语句一样，输出语句也是以分号结尾。

你还需要注意这个程序中的其他一些小符号。首先，C++使用花括号（“{”和“}”）对内容分组。在这种情况下，输出语句包含在花括号里，意味着它在main的定义内部。同时，注意语句的缩进，它可以直观地显示该定义的内部都有哪些行。

现在，你可以坐在电脑前自己编译并运行这个程序。具体实现的细节取决于你的编程环境，但是从现在开始，我假定你知道应该如何做。

如前所述，C++编译器对语法检查很严格。当你编写程序时出现任何错误，编译都很有可能不成功。比如，你拼写错了iostream，你可能会得到以下错误消息：

hello.cpp:1: oistream.h: No such file or directory

这一行包含大量隐蔽密集的信息，并不容易读懂。一个更友好的编译器可能会这样表述：

“hello.cpp源代码文件第一行，尝试引用头文件oistream.h。找不到该文件，只找到文件iostream.h。这是否可能是你需要的？”

遗憾的是，很少有编译器这么友好。编译器并不智能，大多数情况下你得到的错误消息只是一个关于错误的提示。学会解析编译器的消息需要花一些时间。

尽管如此，编译器依然是学习语言语法规则的有力工具。从一个可以正常运行的程序入手（比如hello.cpp），用不同的方法修改它并查看结果。如果你得到错误消息，记住错误消息的内容以及导致错误的原因，这样下次再看到的时候就能够知道它是什么意思。

问题解决（problem-solving）：表述问题，找到解决方案并描述该解决方案的过程。

高级语言（high-level language）：类似C++这样，为了便于人类读写而设计的编程语言。

低级语言（low-level language）：为了便于机器执行而设计的编程语言。也称为机器语言或者汇编语言。

可移植性（portability）：程序可以在不同计算机操作系统上运行的属性。

形式语言（formal language）：人类设计的用于特殊目的语言，比如，用于表达数学思想或者计算机程序。所有编程语言都是形式语言。

自然语言（natural language）：人类所说的经过自然进化得到的各种语言。

解释（interpret）：逐句翻译高级语言编写的源程序，边翻译边运行。

编译（compile）：一次性将高级语言程序翻译为低级语言，形成目标代码，为之后的执行做准备。

源代码（source code）：用高级语言编写的未经过编译的程序。

目标代码（object code）：编译器编译程序后的输出。

可执行程序（executable）：可执行的目标代码。

算法（algorithm）：解决同一类型问题的一般过程。

bug：程序中发生的错误。

语法（syntax）：程序的结构。

语义（semantics）：程序的含义。

解析（parse）：检查一个程序并分析其语法结构。

语法错误（syntax error）：程序中无法完成语法解析的错误（因此也无法编译）。

运行时错误（run-time error）：在程序执行时导致程序失败的错误。

逻辑错误（logical error）：程序中发生的导致程序偏离编程本意的错误。

调试（debugging）：发现并解决三种错误的过程。