第3章 工程化问题求解思维 程序（program）是关于问题求解（problem solving）的描述，也是关于问题求解模型的（直接或间接）可执行描述。从问题给定的初始条件或状态出发，经过分析，找到求解模型，并用可以执行的形式描述出来，就是程序开发。所以，程序开发具有3个要素：模型、表现和方法。 建立模型，就是对问题进行分析、抽象，忽略对求解没有影响或影响甚微的枝节，将其纳入可以求解的框架之中。表现就是用一种机器可以直接或间接理解、执行的语言进行描述。经过长期摸索，人们已经找到了这两个方面的结合点，总结出两种有效的程序设计方法：面向过程的程序设计（Procedure Oriented Programming，POP）和面向对象的程序设计（Object Oriented Programming，OOP）。 程序作为问题求解的基本形式，一直在不断发展与完善之中。其最主要的里程碑是20世纪60年代引入的工程化机制，即把一套系统化、规范化、责任化、工具化、可度量化引入到程序开发中。如今这些已经成计算思维的重要内容。 3.1 面向过程的程序开发 面向过程的模型把问题求解看作对于数据施加一系列操作的过程。所以，面向过程的程序描述的核心内容是：数据与操作过程。本节以目前应用最为广泛的C语言为蓝本介绍面向过程程序开发的有关概念和基本方法。 3.1.1 数据类型 1. 数据类型及其基本类型 数据是世界万物的性能和状态的抽象描述。世界万物是复杂多样的，并且是多变的。因此，数据也是复杂的、多样的、多变的。而不同的数据在存储、表示、操作上都有所不同。这就为计算造成极大的困难，甚至让计算无法进行。 分类是一种重要的科学方法，它能使复杂问题简单化。为此，高级程序设计语言要对数据进行分类，以便规范与简化数据的处理过程。一般说来，高级程序设计语言都提供有如下4大基本类数据类型。 （1）整数类型：取值为整数的类型，典型符号是int。 （2）浮点类型：取值可以带小数的类型，典型符号是float和double。 （3）布尔类型：取值为True或False。 （4）容器类型：包括元组、列表、字符串、字典和集合。有的语言只有字符串。 注意：有的书中把浮点类型称为“实数类型”，这是不准确的。因为，实数包括有理数和无理数。这两个概念都是针对十进制数而言的，而计算机内部都是以二进制形式存储的。 2. 数据类型的规范化特征 一般说来，数据类型可以提供如下一些规范化的特征。 1）规范的存储空间 表3.1为在不同字长的计算机中实现C99规定的标准整数类型的一般长度。对于浮点类型也有相应的存储空间。这样，只要确定了一个数据的类型，计算机就知道该用多大的存储空间进行存储。 表3.1 在不同字长的计算机中实现C99规定的标准整数类型的一般长度 （单位：b） 类 型 16位计算机 32位计算机 64位计算机 char 8 8 8 unsigned char 8 8 8 short int 16 16 16 unsigned short int 16 16 16 int 16 32 32 unsigned int 16 32 32 long int 32 32 64 unsigned long int 32 32 64 long long int — — 64 unsigned long long int — — 64 2）规范的存储方式 在C语言中，整数用定点形式存储，带小数的数据用浮点形式存储。目前，多数计算机内的浮点类型采用IEEE 754格式（参见表3.2）。 表3.2 3种浮点类型的IEEE特征 宽度/b 数据类型 机内表示（二进制位数） 取值范围（绝对值） 十进制精度 /b 阶码 尾数 符号 32 float 8 23 1 0，1.175 49 ×10-38 ~3.40 ×1038 6 64 double 11 52 1 0，2.225 ×10-308 ~ 1.797 ×10308 15 79 long double 15 63 1 0，1.2 ×10-4932~ 1.2 ×104932 19 3）不同的可能值集合 3种浮点类型的取值范围参见表3.2。表3.3为不同长度整数的最小取值范围。 表3.3 不同长度整数的最小取值范围 数据长度/b 取值范围 Signed（有符号） Unsigned（无符号） 8 -127 ~ 127 0 ~ 255 16 -32 767 ~ 32 767 0 ~ 65 535 32 -2 147 483 647 ~2 147 483 647 0 ~ 4 294 967 295 64 -9 223 372 036 854 775 807 ~9 223 372 036 854 775 807 0 ~ 264-1（18 446 744 073 709 551 615） 4）规范的书写格式 不同类型的数据常量在程序中的书写形式有所不同。例如，int类型的不可以带小数点，而float和double类型可以采用科学计数法（如把12.34567写成1234567e-5）。 5）规范的可施加操作集合 类型与可以施加的操作种类相关联。例如，对于整数类型数据可以施加操作符*（乘）、/（除）、%（模）、+、-等操作，但对float和double类型数据不可施加%操作。 6）规范所容纳的值的数目 按照数据对象可以容纳的值的数目，可以将数据类型分为标量数据类型（只容纳一个值）和容器类型（可以容纳多个值）。构造数据类型还可以按照数据之间的关系进行区分。 因此，使用数据时，首先要为它们定义数据段类型。这样，以后使用这些数据时，编译器将会据此对于数据进行合法性检查和规范的操作。 3.1.2 标识符及其声明 1. 标识符规则 在程序中需要对数据等实体进行命名，这些名字就称为标识符（identifier）。不同的程序设计语言有不同的标识符规则。C语言要求标识符遵守下列规则。 （1）在C99之前，要求标识符只能是由大小写字母、数字和下画线组成的序列，但不能以数字开头。例如，下列是合法的C标识符： a A Ab _Ax _aX A_x abcd operand1 results 下列是不合法的C标识符： 5_A（数字打头） A-3（含非法字符） 但是，C99允许标识符由通用字符名（universal-character-name）以及其他编译器所允许的字符组成。 （2）C语言区别同一字母的大小写，如abc与abC被看作不同的标识符。 （3）标识符不能使用对于系统有特殊意义的名字。这些对系统有特殊意义的名字称为关键字。下列为C语言关键字，其中粗体的是ANSI C99增加的。 auto break case char const continue default do double else enum extern float for goto if inline int long register restrict restrict return short signed sizeof static struct switch typedef union unsigned void volatile while _Bool _Complex _Imaginary （4）C99对于标识符的长度没有限制，但要求编译器至少记住前63个字符（C89为 31个），要求链接器能至少处理前31个字符且区分字母大小写（C89为6个且不区分字母大小写）。 2. 声明 前面讲过，不同的数据类型决定了该数据在存储、取值、操作、表示等方面的特征。当为一个数据命名后，这个名字就会与对应的数据实体相联系，并附有该数据的类型所具有的特征。声明的一个用途就是定义标识符。例如： int i1,i2; 这个声明就定义了两个int类型的数据名i1和i2。这样，编译器就会为这两个名字分配存储空间，并且在以后用到这两个名字时，都会进行安全性检查，而且把这两个名字与对应的两个存储空间——实体联系起来。但是，有些语言（如Python）不需要声明，就可直接引用。 3.1.3 表达式 表达式是程序中关于数据值的表示。在C语言中，表达式有3种形式：字面量（常量）、数据实体（变量）和含有操作符的表达式。有些程序设计语言还允许使用别名——引用（reference）。 1. 字面量 字面量（literal）是表达式值的直接表示。它们没有独立的存储空间。字面量也属于特定类型，其类型也可以由书写形式直接标明或推断出。例如： 2147483645：由其值可知，在32位系统中，是一个int类型的整数常量（integer）。 3L：由其后缀L知道，它是一个long int类型整数常量。 3.1415f：由其后缀f知道，它是一个float类型浮点常量（floating）。 3.1415：由没有后缀f知道，它是一个double类型浮点常量。 '5' 和 'a'：由单撇知道，它们是两个char类型字符常量（charactor）。 "I am a student."：由双撇知道，它是一个字符串字面量（string literal）。 常量在程序中以直接方式引用，例如： number1 = 30; number2 = number1 + 20; 2. 数据实体 数据实体（object）也称为数据对象，是拥有一块独立存储区域的数据。要使用这种表达式的值，需要访问其所在的内存空间。C语言允许用如下几种方式访问数据实体。 1）用名字访问数据实体——变量 （1）变量及其声明。 可以用名字访问的数据实体通常被称为变量（variable），或者说变量是被命名的数据实体。一个变量在使用之前需要对其声明（定义），以向编译器注册一个名字及其属性，供操作时进行合法性检查。变量有许多属性，数据类型是其中最重要的属性，其他以后逐步介绍。变量被声明后，编译器就会按照指出的属性，为其分配一个适合的存储空间。下面是几个变量的声明： int i; //定义一个int类型变量i float f; //定义一个float类型变量f double d; //定义一个double类型变量d char c; //定义一个char类型变量c 变量的基本特点是可以用名字对其代表的存储空间进行读（取）写（存）操作。在使用时，因其使用的场合不同而具有不同的含义，它有时被当作一个存储空间，有时被当作一个值。例如，对变量进行读操作（如输出）时，被当作一个值；而对变量进行写（要把一个值送到变量）时，被当作一个存储空间。 （2）变量的赋值操作。 向变量送一个值，称为赋值，使用赋值操作符（=）进行。赋值是改变变量值的操作。例如： int i，j; //定义i和j i = 8; //给i 赋值8 j = 5; //给j赋值5 i = i + 3; //给i 赋予i的原值并加3 （3）变量的初始化。 C语言允许在声明一个变量的同时，可以给其一个初始值，称为变量的初始化。例如： int i = 3; //定义一个int类型变量i，并为其赋初值3 float f = 1.234; //定义一个float类型变量f，并为其赋初值1.234 double d = 1.23456; //定义一个double类型变量d，并为其赋初值1.23456 char c = 'a'; //定义一个char类型变量c，并为其赋初值'a' 在C语言程序中，变量的初始化不是必须的。若声明一个变量后，如果没有给它一个值，则它的值到底是什么，是不可预知的。这样，如果不慎使用了这个变量，就会得到不可预知的结果，在某些情况下，还可能因涉及敏感数据而使系统运行出现问题。 （4）变量的“固化”。 用名字访问一个存储空间，有一个特例：当定义时用const修饰后，就成为一个符号常量，也称为常变量或常量。常量只可读、不可写——不可进行赋值操作。例如： const double PI = 3.1415926; PI = 1.23; //错误，不可赋值 2）用指针（pointer）访问数据实体 （1）指针的概念。 程序中使用的任何一个数据实体都存储在内存的特定位置上，这个位置用地址表示。指针变量简称指针，是存储数据实体地址的变量，它提供了使用内存地址访问数据实体的一种形式。 指针变量也有类型。指针的类型就是它所指向的数据实体的数据类型。或者说，一个指针只能指向一种特定的类型。所以说，指针有两个基本属性。 ① 所指向的数据实体的类型为指针的基类型。 ② 所指向的数据实体的地址为指针的值。 （2）指针的声明与初始化。 指针的声明就要标明其所指向的数据类型，并在数据类型与指针变量名之间加一个*，以表明它是指针。例如： int *pi; //定义一个指向int类型的指针 double *pd; //定义一个指向double类型的指针 char *pc; //定义一个指向char类型的指针 指针用地址初始化。如果已知一个数据实体的地址当然很好，不过在程序设计时并不知道这个数据实体的地址，因为在不同的计算机中，数据实体的地址是不相同的。所以，常常用&（取地址操作符）对变量计算来获得实体的地址。在定义指针时，也常用这个操作符来计算一个变量的地址，例如： int i = 3; //定义一个int类型的变量i int *pi = &i; //用变量i的地址初始化int类型的指针pi 这样，指针pi就初始化为指向变量i。 （3）指针的递引用。 定义一个指针后，就可以用其间接访问其所指向的变量。在指针名前加一个*，就表示对指针进行间接操作，称为指针的引用。例如，用*pi就可以访问指针pi所指向的存储空间，即*pi与i等价。 （4）由于指针太灵活，容易失控，所以目前一些流行语言如Java、C＃、Python等都已弃之不用。 3）用引用（reference）访问数据实体 在C++等语言中，引入了别名机制，可以为常量和常量起一个别名，分别称为右值引用和左值引用。 4）Python的数据对象与变量 如前所述，赋值是改变变量值的操作。这样常常会引发副作用。针对这一问题，Python把数据对象分为可变与不可变两类，并且把变量定义为指向数据实体的引用，而不再是数据对象的名字。这样变量的赋值就成为变量所指向数据对象的改变，从而消除了赋值的副作用。此外，变量还不需要声明。 3. 含有操作符的表达式 含有操作符的表达式是操作符与表达式的合法组合，即这类表达式的值是通过一定的操作得到的，如number1 + 3、number + number2等。这个定义是递归的，即组合可以是多层次的，如number = number + number2等。这时，一个重要的问题是当表达式中有两个及其以上的操作符时，哪个操作符具有操作的优先权。 3.1.4 操作符与表达式的求值规则 要了解这种含有操作符表达式的性质，必须了解相关操作符的性质。 1．C语言的操作符 为了彰显高效、灵活的特色，C语言提供了极其丰富的操作符。这些操作符可以用不同的方法进行分类。例如： （1）不同的操作符需要的操作数不同。按照操作数的数量，操作符可以分为如下3种。 ① 一元（单目）操作符，即只有一个操作数，如+（正）、-（负）等。 ② 二元（双目）操作符，即具有两个操作数，如+（加）、-（减）、*（乘）、/（除）等。 ③ 三元（三目）操作符以后介绍。 （2）按照操作功能，操作符可以分为算术操作符（+（正）、-（负）、+（加）、-（减）、*（乘）、/（除）等）、赋值操作符（=）、关系操作符（>=、>、==、!=、<、<=）、逻辑操作符等。其种类繁多，以后会逐步介绍。 2. 几种最常用的操作符及其表达式 1）赋值操作符与赋值表达式 在计算机程序设计语言中，表达式与值之间是一种绑定。赋值操作是改变值与表达式的绑定的操作。 代码3.1 交换两个变量的值的代码段。 // 变量a、b、temp是3个相同类型的变量,且变量a、b已经有确定的值 temp = a; //语句1 a = b; //语句2 b = temp; 说明： （1）在C语言中，“=”被称为赋值操作符（assignment operator）。例如，表达式temp = a操作是将a的值的副本传送给变量temp。所谓传送副本，是指赋值并不改变赋值操作符右表达式的值，只改变其左边的表达式的值。假设a原来的值为3，b原来的值是5，则执行代码3.1中的3个表达式的情况如下。 ① 执行“temp = a;”，将a的副本3送到变量temp中，即temp变为3，a仍为3。 ② 执行“a = b;”，将b 的副本5送到变量a，即a变为5，b仍为5。 ③ 执行“b = temp;”，将temp 的副本3送到变量b，即b变为3，temp仍为3。 这样就实现了变量a与变量b的值的交换，temp只充当了一个中介。 （2）注意，不能把“=”当作等号。例如，表达式a = a + 1，把“=”理解成等号是没有意义的，而作为赋值操作，是把a的值加1后，再赋值给a。 （3）当有多个赋值操作相邻时，应当按照从右向左的顺序进行操作。例如，程序段 int a,b,c; a = b = c = 5; 执行时，先将5赋值给c，再将表达式c = 5的值5赋值给变量b，最后将b =（c = 5）的值5赋值给变量a，整个表达式的值为5。 2）算术操作符与算术表达式 算术运算是数学中最古老、最基础和最初等的部分。表3.4是C语言提供的用于支持算术运算的7种操作符。人们常把它们统称为算术操作符。 表3.4 C语言提供的用于支持算术运算的7个操作符 符 号 + - * / % + - 意 义 正号 负号 乘 除 求余 加 减 操作数个数 1 1 2 2 2 2 2 操作数类型 数值数据 数值数据 数值数据 数值数据 整型 数值数据 数值数据 说明： （1）求余运算是计算两个整数相除所得到的余数，如表达式10%7的值为3。 （2）C99规定，除运算计算两个整数相除时得到的商是向0舍入，如表达式-9/7的值为-1（在C89中可能为-1，也可能为-2），9/7的值为1，2/3的值为0，因此表达式 2/3 * 10000000000的值也是0。所以，使用整数相除时要格外小心。 （3）C99规定，两个整数进行 % 运算，值的符号与被除数相同。 （4）使用/和%时，若右操作数为0时，会得到难以预料的结果。 3）正负号表达式 在C语言中，一元正号（+）和一元负号（-）都是操作符，这一点与普通数学中的概念有所不同。例如，写+5与写5，在普通数学中认为等价，而在C语言中它们的概念有所不同：5表示一个字面值，而+5是一个对常量5进行取正操作的含有操作符的表达式。同理，-5也不是一个常量，是一个对常量5进行取负操作的含有操作符的表达式。 4）判等操作符和关系操作符 C语言提供两种判等操作符（equality operators）：==（相等）、!=（不等）；4种关系操作符（relational operators）：>（大于）、>=（大于等于）、<（小于）、<=（小于等于）。它们都是二元操作符，用来描述两个数据值之间关系为内容的命题。而命题有“真”（true）和“假”（false）两种结果。C语言用0表示“假”（false），用非0表示 “真”（true），即判等表达式和关系表达式的值是int类型。例如，3 > 2、5-3 == 2等，结果为1；而3 > 5、5-3 == 6等，结果为0。C99定义了一个取值为1或0的_Bool类型，如果在源文件中包含了头文件stdbool.h，则可以使用true和false分别代表1和0。 注意：>=、<=、==、!= 这4个关系操作符都由两个字符组成，在使用时，不可在两个字符之间留空格。 3. 操作符的优先级与结合性 在一个含有多个操作符的表达式中，哪个操作符先与操作对象相结合，主要由操作符的优先级和结合性决定。表3.5为C语言中几个常用操作符的优先级别与结合性。 表3.5 C语言中几个常用操作符的优先级别与结合性 优 先 级 名 称 符 号 结 合 性 1 分组 （） 从左向右 2 一元符号 +、- 从右向左 4 乘除号 *、/ 从左向右 5 加减号 +、- 从左向右 7 关系 <、>、<=、>= 从左向右 8 判等 ==、!= 从左向右 15 赋值 = 从右向左 1）操作符的优先级别（precedence） 每一个操作符都有一个优先级别。例如，前面介绍的算术操作符和赋值操作符的优先级别从高到低依次是单目+、单目-，*、/、%，双目+、双目-，=。 当一个表达式中含有多个操作符时，优先级高的操作符具有与操作对象结合的优先权。例如，表达式a = a + -b，执行的顺序是-b,a + (-b),a = (a + (-b))。 2）结合性（associativity） 当一个表达式中两个相邻的操作符优先级相同时，按照结合性决定与操作数结合的先后。C语言中的操作符具有如下两种结合性。 （1）左结合（left associative）。两个优先级相同的操作符相邻时，左边的操作符优先与操作对象结合。算术操作符就是左结合的，所以2/3*1000的含义是(2/3)*1000，其值为0。 （2）右结合（right associative）。两个优先级相同的操作符相邻时，右边的操作符优先与操作对象结合。赋值操作符就是右结合的，所以表达式a = b = c = d = 5执行的顺序是： d = 5这个表达式的值为5，c = (d = 5)这个表达式的值为5，b =（c =（d = 5））这个表达式的值为5，a =（b =（c =（d = 5）））这个表达式的值为5，并且在这个过程中也依次将d、c、b、a的值改变为5。