1.1 一般概念

1.1.1 程序设计语言的发展和分类

1.程序设计语言的发展

众所周知，计算机是在程序控制下自动工作的，要让计算机完成某项任务，就必须编写相应的计算机程序。编程所用的语言叫程序设计语言，这种语言人和计算机都能“看懂”，因此，程序设计语言是人指挥计算机的工具。

计算机中直接参与计算的运算器和控制器等部件都是由逻辑电路构成的电子器件，而逻辑部件只“认识”0和1，所以程序的最终形式都是由0和1组成的二进制代码。

二进制代码形式的语言称为机器语言。早在计算机诞生之初，人们就是直接用机器语言编程。但是，这种在计算机看来十分明了的机器语言程序，在人看来却是一部“天书”。后来，人们又将3个二进制位合并在一起变成八进制。再后来，为了与字节对应，又将4个二进制位合并在一起变成十六进制。将机器语言程序写成八进制，或十六进制形式，要比二进制形式“好看”一些。但是，不管二进制、八进制，还是十六进制，用数字表示指令序列都不直观，不仅专业性极强，而且非常难读难用，编程工作效率低，又极易出错。好在当初计算机应用面很窄，编程工作量不大，矛盾并不十分突出。

随着计算机应用面不断地扩大，程序需求量大增，编程工作量也越来越大，人们便产生了用符号代表机器指令的想法，设计出汇编语言（Assemble Language，又称符号语言）。比如，用ADD表示加法指令，用SUB表示减法指令等，要比用二进制0/1序列“00111011”表示某一条指令直观得多。用汇编语言编写的程序称为汇编源程序。将汇编源程序送入计算机，由计算机自动地将汇编源程序翻译成计算机能够直接执行的二进制程序，而计算机的自动翻译功能是由专用软件——汇编程序（Assembler，又称汇编器）完成的，当然，这个软件也是人们事先编写好，并安装在计算机系统中的。一台计算机配上了汇编程序就相当于人们“教会”计算机认识汇编语言了。再后来，人们又设计出反汇编程序，它能将机器语言程序反过来翻译成汇编语言程序。通过反汇编，人们就可以读懂安装在计算机中的可执行程序。

使用汇编语言减轻了不少人们的编程工作量，但是，汇编语言仍然十分原始，一条汇编语句（也称汇编指令）对应一条机器指令，易读性仍然很差。编制一个程序，哪怕只是用来完成简单计算任务的程序，通常需要成百上千条汇编指令。不仅编程效率低，程序不易调试，而且容易出错。更为麻烦的是，这种语言是完全按照计算机硬件设计的，不同种类的计算机都有自己特有的机器语言和汇编语言，一种类型的机器无法识别另一种类型机器的机器语言，所以，汇编源程序缺乏可移植性。

人们把机器语言和汇编语言归属为低级语言。

汇编语言的出现具有划时代的意义，它启发人们，可以设计出更好用的语言，只需要通过翻译器，将新语言的源程序翻译成机器语言程序。于是，人们期待的，脱离计算机机种的高级程序设计语言（以下简称高级语言）便陆续被设计出来。

第一个高级语言是20世纪50年代中期出现的FORTRAN（FORmula TRANslator）语言，它的取名就意味着它所起的角色（翻译器）。该语言特别适用于编写科学计算（即纯数值计算）程序，直到今天仍然在发挥着作用，可见其生命力之强大。

后来人们又相继设计出用于商业事务处理的COBOL语言（Common Business Oriented Language），适合于算法描述的算法语言ALGOL（ALGOrithmic Language），面向初学者的BASIC语言（Beginner's All-purpose Symbolic Instruction Code）、PL/1语言（Programming Language/1）以及Niklaus Wirth根据结构化程序设计思想设计的PASCAL语言（Philips AutomaticSequence CALculator，同时也为了纪念最早实用计算器的发明者、数学家Blaise Pascal而命名），以及C语言、C++语言和一些更好用、“级别更高”的语言，这些语言在程序设计语言的发展历程中都起到十分重要的作用。

高级语言引入了变量、数组、分支、循环、子程序，以及接近数学语言的表达式等语法成分，用接近英语口语的语句描述处理步骤（例如，if…then…else…），不仅容易理解和记忆，而且一条语句的处理能力相当于几条、几十条，甚至几百条汇编指令，大大地提高了编程效率。

2.程序设计语言的大致分类

高级语言有两种形式，一种是编译型的，另一种是解释型的。

用编译型的高级语言编写的源程序（也称源代码）经过编译程序（Compiler，又称“编译器”）对其编译，产生出机器语言程序（称目标程序），再将一个或几个目标程序与标准库函数程序连接起来，最终构成一个完整的可执行程序。FORTRAN、PASCAL、C等都属于编译型的语言。

BASIC是典型的解释型高级语言，采用解释的方法执行源程序中的语句。通过解释程序（Interpreter，又称解释器）对源程序中的语句边解释边执行，而不产生目标程序文件。目前最流行的网络编程语言Java也属于解释型高级语言。

编译和解释的最大区别是，前者得到一个完整的机器语言程序，执行时可以脱离翻译环境，所以运行速度快；后者则不能脱离解释器单独执行，因而执行速度慢。

从另一角度，又可将高级语言分为面向过程的和面向对象的两大类。凡提供面向对象程序设计手段的语言都属于面向对象的，否则，属于面向过程的。

早期的高级语言（如PASCAL、ALGOL和C等）都是面向过程的。这类语言基于数据类型和处理数据的函数（或称过程）定义。数据在其作用域内可被任何函数访问，数据和处理数据的函数是分离的，缺乏数据保护机制。

面向对象的语言提供的机制支持面向对象的程序设计方法。以类（实际上是类的对象）作为基本单位，把数据以及处理这些数据的代码严密地封装在一起形成类，外部只知有类，但不知（也不必知道）类是如何处理的，只能通过类访问和处理类中的数据，而不能绕过类去访问类中的数据。这样，类内部的处理细节对外是屏蔽的，从而保护了类中的数据，有效地保证数据的完整性和一致性（详见第6章）。

20世纪60年代开发的Simula 67语言提出了对象和类的概念，被认为是面向对象语言的鼻祖。20世纪70年代出现的ADA语言（为纪念第一位有文字记载的女程序员Augusta Ada Lovelace而命名）支持抽象数据类型，是基于对象的语言。但由于它并不全面支持继承，所以仍算不得真正面向对象。再后来的Simulatalk语言和Java语言进一步丰富了面向对象的概念，将信息隐藏得更加严密，通过向对象发送信息的方式进行程序设计。C++语言，以及当前流行的网络编程语言C#、Python等都属于面向对象的程序设计语言。

另外，为了满足不同行业、不同人群的需要，人们还设计出各种各样的专用语言（比如，数控语言、各种辅助设计语言、数据库操作语言），以及专门用来软件开发的各种开发工具（有的也属于编程语言）等，这里不能一一列举。

总之，语言的发展促进了编程技术的发展，而编程技术的发展和编程要求同样也激励着编程语言的发展。易学、好用、功能强大，对使用者所应具备的计算机专业知识要求不高，是未来语言的发展方向。

3.C语言的产生和发展过程

1967年，Martin Richards为编写操作系统和编译器开发了一种特殊的语言Basic Combined Programming Language（缩写为BCPL）。后来，贝尔实验室的Ken Thompson对BCPL进行修改，并取BCPL的首字母B作为名称，即B语言。

1972年，贝尔实验室的Dennis Ritchie再次对B语言进行修改，取BCPL的第二个字母C作为修改后的语言名称，即C语言，并成功地在DEC PDP-11计算机上加以实现（即编写出该语言的编译器）。C语言继承了BCPL语言和B语言的优点，克服其不足。继而，贝尔实验室用C语言开发UNIX操作系统大获成功，引起计算机界高度关注。从此，人们对C语言开发低层软件的能力有了充分的认识。

1978年，Kernighan和Ritchie在Prentice Hall出版的《The C Programming Language》一书引起了人们对C语言的广泛兴趣，C语言得以普及和发展。到20世纪70年代末期，C语言已逐步发展成今天所说的“传统C”（也称Kernighan&Ritchie C）。

1983年，在美国国家标准委员会（ANSI）下属计算机和信息处理分会（X3）指导下，成立了X311技术委员会，该委员会对C语言进行了扩充，制定了统一的C语言标准（即ANSI C）。后来又对ANSI C进行修订，产生了新的ANSI C。此后，虽然产生多种不同的C语言版本，但它们基本上都符合ANSI C标准。

20世纪80年代初，贝尔实验室又在C语言基础上，扩充了支持面向对象的程序设计功能，取名为C++。

历史上比较有影响的C语言和C++语言版本（大多带集成开发环境）有Microsoft公司出品的Microsoft C（简称MSC），Borland公司出品的Turbo C（简称TC）和Borland C++（简称BC），以及Microsoft公司出品的Visual C++（简称VC）等。

本书以ANSI C为基础介绍C语言程序设计方法，同时穿插地介绍一些“好用的”的C++语法成分（比如，输入cin和输出cout，行注释符“//”，引用运算符“&”，运算符new和delete等）。这种以C语言为主，并含有一部分C++语法成分的语言，本书称之为C/C++语言。为便于叙述，后文中的“C语言”多数情况下指的就是C/C++语言。

本书第6章简单介绍C++语言的类和对象的基本用法，以彰显面向过程和面向对象的程序设计的异同之处，使读者对面向对象的程序设计方法有一个粗浅的认识。

4.C语言的特点

C语言具有独特的风格，超短而精巧的源程序，灵活多变的for语句、break语句和continue语句，“变化多端的”指针操作，超高的编译效率（源程序能被编译出效率非常高的目标代码）。

C语言具有丰富的数据类型，以及多种多样的运算符和表达式。其中，自增自减运算、位运算、指针运算、取地址运算等与硬指令极为接近，使得C语言既具有一般高级语言的特征，又保留了部分汇编语言的特点，将高级语言和低级语言的优点融会在一起（所以特别适于开发底层系统软件）。正因为如此，C语言被认为是一种带有低级语言色彩的、介于高级语言和低级语言之间的“中级”结构化程序设计语言。

编译预处理功能也是C语言的特色之一。

C语言的语法格式十分灵活（如for语句），给程序员提供了极大的自由编程空间。

C语言也存在不足之处。例如，因语法规定过于灵活而降低程序的易读性，甚至会造成隐蔽性错误；没有复数类型，纯数值计算能力差等。

另外，C语言运算符的种类繁多，结合性和优先级等概念较复杂，初学者不易全面掌握。

1.1.2 C源程序的基本结构

源程序结构包括物理结构和逻辑结构两个方面。物理结构指的是程序语句和程序块在源程序文件中的排列形式；而逻辑结构指的是程序语句和程序块的执行次序，即程序的流程。

1.物理结构

C语言将一个独立的程序块称为一个函数。一个C源程序文件由一到多个函数组成，这些函数顺序排放在源程序文件中，排放次序并不十分重要（多少有点关系，详见第4章）。这种结构属于模块式结构^[1]。函数是并列的、独立的，而不是嵌套的（一个函数内部不能定义另一个函数）。两个函数之间可以夹杂一些说明性语句，比如，编译预处理命令、全局量的定义或声明等。

每个函数都由一个函数头（包括函数类型、函数名、形参表等）和函数体（用一对花括号括起来的语句序列）组成。

图1-1给出C源程序物理结构示意图。其中，图1-1a是源程序文件结构，图中，双线条代表说明性语句，矩形代表函数；而图1-1b则是其中一个函数的结构。

一个完整的C源程序（可能由一个或多个源程序文件组成）必须有一个名为main的主函数，其余函数均是子函数（子函数名由程序员任取）。运行时总是从主函数的第一条可执行语句开始执行（无论主函数放在什么位置）。仅当被调用时，子函数才得以执行。当执行完主函数的最后一条语句时，这个程序的执行也便终止了。

源程序的任何地方都可以出现注释。

C++提供两种注释方式：行注释和段注释；ANSI C只提供段注释，不提供行注释。

行注释以“//”开头，到本行末为止的内容均是注释。段注释从“/*”起到“*/”止，中间的内容都是注释。

行注释录入方便，但注释内容不能跨行。段注释则可以跨行，也可以夹在程序语句中间，而且段注释中还可以包含行注释。

对于大段大段的注释内容，若采用行注释，每行开头都要加“//”，所以采用段注释要方便些。

注释不是源程序语句，有无注释对程序执行结果没有丝毫影响，通过注释对程序语句、变量、程序段的功能加以注解，便于自己或他人阅读程序。

本书几乎所有的注释都采用行注释，当然，如果需要，也可改为段注释。

2.逻辑结构

程序的逻辑结构指的是，同一函数内语句的执行次序，以及各函数的执行次序。

同一函数内的语句总是顺序排列的。执行时也总是从第一条语句开始一条一条地依次执行。但是，当执行一条控制语句（条件语句、转移语句、循环语句等）时，就会改变语句的执行次序，从而改变了程序的流程方向。

有4种不同的流程结构：顺序结构、分支结构、循环结构和函数调用结构。其中，前3种属于函数内结构，第4种是函数间的调用关系。

处在顺序结构中的语句，执行时严格按照语句的先后次序逐条执行，其流程如图1-2所示（箭头表示流程方向），即执行次序是：语句1、语句2、语句3。

分支结构有二分支和多分支两种，分别由if语句和switch语句实现，参见图1-3。

分支结构的前部通常有一条用于测试判断条件的语句。当程序执行到该语句时，就对事先设置在程序中的判断条件进行测试，根据测试结果，从两个或多个分支中选择一个分支执行（其他分支不被执行）。

循环结构也称重复结构。处在循环结构中的程序段称为循环体，在循环控制条件的控制之下，循环体可以反复执行。循环结构用于反复处理相同或相似的计算步骤。while语句、for语句和do-while语句都可以实现循环结构。

有两种循环结构：当型循环和直到型循环，如图1-4所示。

当型循环的循环控制条件设在循环结构的前部，其执行流程是：先测试控制条件，然后根据测试结果，确定是否执行（或再一次执行）循环体，其意是当控制条件满足时就执行一次循环体；当控制条件不满足时就退出本循环结构。当然，每执行一次循环体之前都要重新检查一次控制条件。

直到型循环的循环控制条件设在循环结构的尾部，其执行流程是：先执行一次循环体，然后测试循环控制条件，确定是再次执行循环体，还是退出本循环结构。当然，也是每执行一次循环体之后都要重新检查一次控制条件。

当型循环和直到型循环的执行流程唯一区别在于，执行循环体前先测试循环控制条件，还是执行循环体后再测试循环控制条件。

顺序、分支、循环3种结构可以穿插出现在同一函数中，而分支结构、循环结构中也可以含有顺序结构、分支结构和循环结构，也就是说，这3种结构可以相互叠加，相互嵌套，形成复杂的程序结构。

函数调用可以改变程序的执行路径（即流程方向）。在执行一个函数时，如果遇到函数调用语句，那么控制（流程）从主调函数的调用点转移到被调函数，开始执行被调用函数。执行完被调函数后，返回到主调函数的调用点，继续执行主调函数中调用语句后面的语句。如图1-5所示。

主函数可以调用子函数，子函数可以调用其他子函数，也可以调用自身（递归调用）。但任何函数（包括主函数本身）都不能调用主函数。

1.1.3 算法的描述和实现

1.程序和算法的关系

当人们着手求解某给定问题，设计求解此问题的处理程序时，先要确定解题方案，从中抽象出问题所涉及的数据及数据结构，设计出求解算法（即如何对这些数据一步步地进行处理，最后得到问题所需要的计算结果），然后按照算法中描述的计算步骤编写计算机程序（这一步称作算法的实现，而前一步则是算法的描述）。这就是著名的Wirth公式“算法+数据结构=程序”所概括的算法、数据结构和程序之间的关系。

按照这一角度，算法就是对计算步骤的描述，而程序则是实现计算步骤的（计算机可以执行的）指令序列，显然，程序中必含有算法。因此，有时候将算法称为程序，或将程序称为算法。

算法有多种描述形式，其中最常用的是自然语言描述形式（即文字叙述形式），以及下面介绍的流程图形式。

2.流程图

流程图也称框图，因为算法是程序的雏形，所以算法的流程图也就是程序的流程图。画流程图时要使用规范的流程图符号。

画流程图时要使用规范的流程图符号。

图1-6给出常用的流程图符号。其中，椭圆（图1-6a）用于标注程序的起点（起始框）和结束点（终止框），框内通常书写“开始”和“结束”；矩形（处理框，图1-6b）内书写程序的处理步骤；菱形（决策框，图1-6c）用于书写程序分支或循环的判断条件；平行四边形（输入/输出框，图1-6d）内书写程序的输入和输出数据；带箭头的线条（流程线，图1-6e）用于指明程序的流程方向；小圆点（旁边带字母等记号，图1-6f）用于指明流程图的连接点，当流程图太大，一处画不完时，通过连接点转到另一处再画，记号相同的，表示同一个流程点。

对于较为复杂的算法，通常先画出粗框图，再画出细框图，并逐步细化，直到容易编程实现为止。

3.示例

下面通过示例介绍如何针对给定问题设计算法，画流程图，以及如何编程实现。

【例1-1】 输入一批正整数，统计其中奇数的个数和偶数的个数。

算法的设计思路

设计求解此题的算法时，可能涉及下面3个问题。

1）如何判定一个整数x是奇数还是偶数？

2）如何统计并记录奇数个数和偶数个数？

3）如何控制循环读数，并判断输入数据是否结束？

判断整数x的奇偶性可以采用“除2判余法”（后述）。

统计并记录奇数和偶数的个数可采用“计数器累加法”。使用两个变量odd和even分别作为奇数个数和偶数个数的计数器，使它们的初值为0（俗称清0）。然后，每当遇到偶数时就将偶数计数器even的值加1，每当遇到奇数时就将奇数计数器odd的值加1。

在使用计数器之前，总是先将其清0，这是一个常识。

读数控制和判断输入数据是否结束，可以这样考虑：因为不知道一共有多少个正整数（只知道是一批），可以约定，在这批正整数后面添加一个值为0的数。于是，依次输入这些整数（输入一个处理一个），当输入的数为0时，就表示输入数据结束。

算法的自然语言描述（文字叙述）

第1步，将计数器odd和even清0，即odd=0，even=0。

第2步，输入第一个数x。

第3步，如果当前输入的x为0，则转第5步；否则执行第3-1步和第3-2步。

第3-1步，如果x是偶数，则计数器even加1；如果x是奇数，则计数器odd加1。

第3-2步，输入下一个数x。

第4步，返回第3步（循环处理）。

第5步，输出统计结果，结束。

判断x奇偶性的具体方法是，用x除以2，考查所得的余数是否为0，若余数为0，则x是偶数；若余数不为0，则x是奇数。取余运算“x%2”能够得出x除以2所剩的余数，于是第3-1步可以描述为“如果x%2等于0，则x是偶数even加1，否则x是奇数odd加1”。

算法的流程图

图1-7为上述算法对应的流程图。

算法的实现程序

输入数据可用输入语句“cin >>x;”实现，输出数据可用输出语句“cout<<even;”实现，循环处理可用循环语句“while(x!=0)”实现，判断x的奇偶性并计数可用条件语句“if(x%2==0)even=even+1;else odd=odd+1;”实现。

再配上必要的编译预处理命令、变量定义，和适当的注释，就可拼装成一个完整的C源程序。由于上述算法结构比较简单，只用一个主函数，无须子函数。

程序如下：

1.1.4 程序设计风格

设计出结构良好的程序是每个程序设计工作者的职责，所以，从一开始就要注意培养良好的设计风格，逐步掌握设计结构良好程序的方法。通常需要考虑程序的易读性、可维护性和用户界面等方面。具体地说，要注意下列几点。

1）语句行首对齐方式（源程序排版格式）。

C语言采用自由书写格式，每行可写多条语句，一条语句可占多行，行首起点任意。

这种自由格式为编程者带来方便，但是，稍不注意，也会造成程序结构上的混乱。

规范的做法是采用“同级左对齐（同层语句行首对齐），子句向右移”的缩排格式，按照程序的逻辑层次对程序进行排版处理。

另外，最好一行只写一句，而不要写多句。这不仅便于阅读，也易于调试。

2）适当地加以注释。注释用于对程序中的变量、语句、程序段的功能进行附加说明，以便于阅读。所以，要对重点变量和重点语句加以注释。如果不加注释不仅他人不易读懂，就是编程者本人，过一段时间后，也可能读不懂自己编写的程序，给程序维护带来困难。

尤其要注意的是，修改程序应同步修改注释。从这一点上说，注释并非越详细越好，过多的注释会增加因修改程序而修改注释的工作量。如果修改了程序，但没有及时修改注释，那么注释反而有害，因为错误的注释使程序更难读懂。

3）合理地使用标识符。选用带实际含义的常量名、变量名和函数名，可以增强程序的易读性。

4）采用“自顶向下”和“自底向上”相结合的设计方法，也就是自顶向下逐步分解，自底向上逐级编程实现。具体地说，在处理“较大问题”（即为求解较复杂问题而设计程序）时，不要急于动手编程，先设计出粗略的处理步骤，画出粗框图，然后将粗框图不断地细化，画出一系列细框图，逐步求精，直到每个框图中的每一步都很容易编程实现。然后对每个细框图分别编程实现（作为一个程序段，或一个独立的函数），并逐级向上拼装成大的功能模块，直到最顶层的粗框。

这种做法的好处在于，易于保持良好的程序结构，即使一时遗漏了某些应当考虑的情况，也只要修改下层程序，不触及或较少触及上层程序。

5）少用或不用goto语句。使用goto语句可以使程序流程“灵活地”转移（也称跳转）到任一处执行。然而，正是这种灵活，极大地损伤了程序结构。跳来跳去，难于理解。出了错，也很难查出错在何处和出错原因。

6）事先考虑周全，少打“补丁”。有一种情况，对程序结构的破坏是“事后所为”。由于开始时考虑不周全，不细致，等到大程序拼装完成后，发现这儿有问题，那儿也有问题。只好用打补丁的办法对程序进行修补。而打补丁通常靠goto语句实现，这就破坏了程序结构。

7）要注意用户界面的设计，力求界面良好。程序中，凡是要求用户输入数据时，都要先输出提示信息，提示用户按程序要求输入相应的数据。

比如，【例1-1】的程序中，输入语句“cin >>x;”之前的那条语句就是输出提示信息的。如果没有这条输出提示信息的语句，那么，当程序运行到输入语句“cin >>x;”，用户屏幕上将出现黑屏（只有一个闪烁的光标，等待用户输数据），出现这种情况时，用户很可能不知如何操作。

必要时，在用户输入数据后，将输入的数据原样显示，供用户自我检查所输入的数据是否是自己想要的。【例1-1】的程序中缺少这样的语句。

8）程序要有容错性。为使程序更加完美，还要对用户输入数据的合法性进行检查。当用户输入数据不符合程序要求时，提示用户重新输入（直到数据合法为止）。也就是允许用户输入数据时出现差错。

为使程序具备容错性，必然会增加程序的长度，有时会增加得很长，不利于对程序主体部分的阅读。由于本书中的示例程序属于教学程序，而非实用性程序，所以都不带容错性检查。但尽管如此，作者仍希望读者在设计程序时，哪怕是练习程序，尽量带容错性检查，以养成良好的程序设计习惯。