第1章 程序设计基础

本章资源

本章主要介绍程序的概念及程序设计语言的分类、C语言的发展历史与特点、程序设计的本质、算法及算法表示方法、结构化的程序设计等内容。目的是使读者初步了解程序设计的内容与方法。

1.1 程序设计语言

计算机和人类之间不能完全使用自然语言进行交流，需要借助计算机能够理解并执行的“计算机语言”。和人类语言类似，计算机语言是语法、语义与词汇的集合，它用来表达计算机程序。计算机语言也称为程序设计语言。

程序设计语言种类较多，C语言是最常用的程序设计语言之一，通过对C语言的扩充还产生了如C++、Java、C#等语言。各种语言具有相通之处，因此学好C语言可以为学习其他语言打下基础。

1.1.1 什么是程序

人们操作计算机完成各项工作，实际上是由计算机执行其中各种程序实现的，如操作系统、文字处理程序、手机内置的各类应用程序等。简单的程序可能仅仅向屏幕输出一段符号，而复杂的程序可以实现更多功能。

程序是用来完成特定功能的一系列指令。通过向计算机发布指令，程序设计人员可以控制其执行某些操作或进行某种运算，从而解决一个具体问题。一个程序总是按照既定顺序执行，完成编程人员设计的任务。虽然每个程序内部执行顺序可能不同，完成的任务有大有小，但程序编译成功进入执行状态后，其功能是不能被随心所欲修改的，除非重新编写、编译并执行程序。

1.1.2 语言的分类

自计算机诞生以来，产生了上千种程序设计语言，有些已被淘汰，有些则得到了推广和发展。程序设计语言经历了由低级到高级的发展过程，可以分为机器语言、汇编语言、高级语言和面向对象的语言。低级语言包括机器语言和汇编语言；高级语言有很多种，包括C、Basic、Fortran等；面向对象的语言包括C++、Visual Basic、Java等。越低级的语言越接近计算机的二进制指令，越高级的语言越接近人类的思维方式。

1．机器语言

机器语言是计算机能够直接识别并执行的二进制指令，执行效率高。但机器语言指令由计算机的指令系统提供，采用二进制，人们阅读与编写比较困难，效率低下，容易出错。不同计算机的指令系统也不同，使得机器指令编写的程序通用性较差。

2．汇编语言

汇编语言采用助记符来代替机器语言的指令码，使机器语言符号化，编程效率得到提高。如加法表示为ADD，指令“ADD AX, DX”的含义是将AX寄存器中的数据与DX寄存器中的数据相加，并将结果存入AX内。汇编程序要转换成二进制形式交由计算机执行，因此执行效率逊于机器语言。使用汇编语言编程，程序设计人员需要对机器硬件有深入了解，没有摆脱对具体机器的依赖，编程仍然具有较大难度。

3．高级语言

为了解决计算机硬件的高速度和程序编制的低效率之间的矛盾，20世纪50年代末期产生了“程序设计语言”，也称高级语言。高级语言比较接近自然语言，直观、精确、通用、易学、易懂，编程效率高，便于移植。例如，语句“c=a+b”表示“求a+b的和，并将结果存入c中”。高级语言有上千种，但实际应用的仅有十几种，如Basic、Pascal、C、Fortran、ADA、COBOL、PL/I等。

4．面向对象的程序设计语言

面向对象的程序设计语言更接近人们的思维习惯。它将事物或某个操作抽象成类，将事物的属性抽象为类的属性，事物所能执行的操作抽象为方法。常用的面向对象语言有Visual C++、Visual Basic、Java等。

计算机不能直接识别高级语言，需要借助编译软件将高级语言编写的源程序转换成计算机能识别的目标程序。

程序执行有编译执行和解释执行两种方式。

（1）编译执行方式是将整个源程序翻译生成一个可执行的目标程序，该目标程序可以脱离编译环境和源程序独立存在和执行。

（2）解释执行方式是将源程序逐句解释成二进制指令，解释一句执行一句，不生成可执行文件，它的执行速度比编译方式慢。

1.1.3 C语言简介

C语言的诞生源于系统程序设计的深入研究和发展。它作为书写UNIX操作系统的语言，伴随着UNIX的发展和流行而得到发展与普及。

（1）1967年，英国剑桥大学的M.Richards在CPL（Combined Programming Language）语言的基础上，实现了BCPL（Basic Combined Programming Language）语言。

（2）1970年，美国贝尔实验室的K.Thompson以BCPL语言为基础，设计了一种类似于BCPL的语言，称为B语言。他用B语言在PDP-7机上实现了第一个实验性的UNIX操作系统。

（3）1972年，贝尔实验室的D.M.Ritchie为克服B语言的诸多不足，在B语言的基础上重新设计了一种语言，由于是B的后继，故称为C语言。

（4）1973年，贝尔实验室的K.Thompson和D.M.Ritchie合作，用C语言重新改写了UNIX操作系统。此后随着UNIX操作系统的发展，C语言的应用越来广泛，影响越来越大。此时的C语言主要还是作为实验室产品在使用，并依赖于具体的机器，直到1977年才出现了独立于具体机器的C语言编译版本。

随着微型计算机的普及，C语言版本也呈现多样化。由于没有统一标准，这些语言之间出现了许多不一致的地方。为了改变这种情况，美国国家标准学会（ANSI）为C语言制定了一套ANSI标准，就是标准C语言。1983年，美国国家标准学会颁布了C语言的新标准版本“ANSI C”。“ANSI C”比标准C语言有了很大的补充和发展。目前C语言的最新版本为ANSI C99, VC++也支持该标准。

C语言使用灵活，并具有强大生命力，已经广泛应用于科学计算、工程控制、网络通信、图像处理等领域。C语言是结构化的程序设计语言，具有如下特点。

（1）语言简洁、使用灵活，便于学习和应用。C语言的书写形式较其他语言更为直观、精炼。

（2）语言表达能力强。运算符达30多种，涉及的范围广，功能强。

（3）数据结构系统化。C语言具有现代语言的各种数据结构，并具有数据类型的构造功能，因此便于实现各种复杂的数据结构的运算。

（4）控制流结构化。C语言提供了功能很强的各种控制流语句（if、while、for、switch等），并以函数作为主要结构，便于程序模块化，符合现代程序设计风格。

（5）C语言生成的程序质量高，程序运行效率高。实验表明，C语言源程序生成的可执行程序的运行效率仅比汇编语言的效率低10%～20%。C语言编程速度快，程序可读性好，易于调试、修改和移植，这些优点是汇编语言无法比拟的。

（6）可移植性好。统计资料表明。C语言程序80%以上的代码是公共的，因此稍加修改就能移植到各种不同型号的计算机上。

C语言也存在一些不足之处，如编程自由度比较大。但总的来说，C语言是一个出色而有效的现代通用程序设计语言。

1.1.4 C语言组成

C程序由函数构成。一个C程序至少由一个函数构成，而且至少包含一个名为main的主函数。函数由函数首部和函数体组成。函数首部指出函数的类型和函数名，函数体由若干条语句构成，语句的末尾用分号表示。

【例1.1】用一个main函数构成的程序，向屏幕输出字符串“I like Programming!”。

    #include<stdio.h>//预处理命令，用于包含文件<stdio.h>
    void main( ) //函数首部，main是函数名，即主函数
    {  printf("I like Programming! \n"); //函数printf输出双引号内的普通字符
    }

程序的运行结果如下。

说明：

（1）函数可以分成函数首部和函数体。花括弧“{}”括起来的是函数体。

（2）语句由一些基本字符和定义符按照C语言的语法规定组成。每个语句以分号结束。

（3）“//”后边的文字为注释，它们不执行，不影响程序的运行。

1.2 计算机的组成与程序设计的本质

程序设计与计算机组成有密切关系，学习计算机组成方面的知识，可以更好地理解程序设计的本质。

1.2.1 计算机系统结构

“计算机之父”冯·诺依曼提出的计算机系统结构如下。

（1）计算机由控制器、运算器、存储器、输入设备和输出设备5个部分构成。

（2）计算机指令和数据均以二进制数形式表示和存放。

（3）计算机按照程序规定的顺序将指令从存储器中取出，并逐条执行。

控制器集中控制其他设备。信息分为数据信息和控制信息两种。如图1-1所示，在控制指令的控制下，数据按照如下方式“流动”：由输入设备输入数据，存储在存储器中，控制器和运算器直接从存储器中取出数据（包括程序代码和运算对象）进行处理，结果存储在存储器内，并由输出设备输出。

图1-1 冯·诺依曼体系结构

1.2.2 程序设计的本质

程序设计的本质是设计能够利用计算机的5个部件完成特定任务的指令序列。

【例1.2】用键盘输入价格与斤数，计算樱桃的总价。

    #include<stdio.h>
    void main()
    {  int price, number, total;
      scanf("%d%d", &price, &number);   //输入两个整数
      total=price*number;               //计算，将price乘以number的积存入total
      printf("total=%d\n", total);      //输出，%d处对应输出total的值
    }

在运行程序时输入数据“10 3”后按“回车键”，显示总价为30，程序的运行结果如下。

说明：

（1）整个程序保存在计算机的存储器中。

（2）数据存储在存储器中。3个变量price、number和total，分别占用一块存储空间，用于存放价格、斤数和总价。

（3）通过键盘输入价格与斤数。

（4）由运算器来执行乘法，求出总价。

（5）通过输出设备显示程序执行的结果。

通过本例可见，一个程序离不开5个部件的配合。一个程序可以没有输入，但是一定要有输出才能知道程序的运行结果。

1.2.3 程序设计的过程

程序设计的一般过程如表1-1所示，在编程解决具体问题时，一般应按照这6个步骤，逐一实施来完成程序。

表1-1 程序设计过程

1．分析和定义实际问题

通过对实际问题的深入分析，准确地提炼、描述要解决的问题，找出已知与未知，明确要求。

2．建立处理模型

实际问题都是有一定规律的数学、物理等过程，用特定方法描述问题的规律和其中的数值关系，是为确定计算机实现算法而做的理论准备。如求解图形面积一类的问题，可以归结为数值积分，积分公式就是为解决这类问题而建立的数学模型。

3．设计算法

将要处理的问题分解成计算机能够执行的若干特定操作，也就是确定解决问题的算法。例如，由于计算机不能识别积分公式，需要将公式转换为计算机能够接受的运算，如选择梯形公式或辛普森（Simpson）公式等。

4．设计流程图

在编写程序前给出处理步骤的流程图，能直观地反映出所处理问题中较复杂的关系，从而在编程时思路清晰，避免出错。流程图是程序设计的良好辅助工具，它作为程序设计资料也便于交流。

5．编写程序

编程是指用某种高级语言按照流程图描述的步骤写出程序，也叫做编码。使用某种语言编写的程序叫源程序。

6．调试程序和运行程序

调试程序和运行程序就是将写好的程序上机检查、编译、调试和运行，并纠正程序中的错误。

1.3 算法的概念和特性

编写程序之前，首先要找出解决问题的方法，并将其转换成计算机能够理解并执行的步骤，即算法。算法设计是程序设计过程中的一个重要步骤。

1.3.1 什么是算法

算法即解决一个问题所采取的一系列步骤。著名的计算机科学家Nikiklaus Wirth提出如下公式：

程序=数据结构+算法

其中，数据结构是指程序中数据的类型和组织形式。

算法给出了解决问题的方法和步骤，是程序的灵魂，决定如何操作数据，如何解决问题。同一个问题可以有多种不同算法。

1.3.2 算法举例

计算机程序的算法，必须是计算机能够运行的方法。理发、吃饭等动作计算机不能运行，而加、减、乘、除、比较和逻辑运算等就是计算机能够执行的操作。

【例1.3】求1+2+3+4+…+100。

第一种算法是书写形如“1+2+3+4+5+6+…+100”的表达式，其中不能使用省略号。这种算法太长，写起来很费时，且经常出错。

第二种算法是利用数学公式：

相比之下，第二种算法要简单得多。但是，并非每个问题都有现成的公式可用，如求100!=1×2×3×4×5×…×100。

【例1.4】求5!=1×2×3×4×5。

    step1:  p=1
    step2:  i=2
    step3:  p=p × i
    step4:  i=i+1
    step5:  如果i<=5，那么转入step3执行
    step6:  输出p，算法结束

其中p和i是变量，它们各占用一块内存，变量中存储的数据是可以改变的。如图1-2所示。变量可以被赋值，也可以取出值参加运算。本例通过循环条件“i<=5”，使得乘法操作被执行4次。

图1-2 变量示意

【例1.5】求1×2×3×…×100。

    step1:  p=1
    step2:  i=2
    step3:  p=p × i
    step4:  i=i+1
    step5:  如果i<=100，那么转入step3执行
    step6:  输出p，算法结束

只需要在【例1.4】算法的基础上，将循环条件改为“i<=100”，使得乘法操作执行99次就可以求出100个数的乘积。

【例1.6】求1×3×5×…×101。

    step1:  p=1
    step2:  i=1
    step3:  p=p×i
    step4:  i=i+2
    step5:  如果i<=101，那么转入step3执行
    step6:  输出p，算法结束

只需要将i的初值改为1、每次循环增加2就可以了。读者在学习过程中要多观摩已有的程序，分析其算法，并力求有所创新。

1.3.3 算法的特性

算法应该具有以下特性。

（1）有穷性。算法经过有限次的运算就能得到结果，而不能无限执行或超出实际可以接受的时间。如果一个程序需要执行1000年才能得到结果，对于程序执行者而言，基本就没有什么意义了。

（2）确定性。算法中的每一个步骤都是确定的，不能含糊、模棱两可。算法中的每一个步骤不应当被解释为多种含义，而应当十分明确。比如，描述“小王递给小李一件他的衣服”，这里，衣服究竟是小王的，还是小李的呢？

（3）输入。算法可以有输入，也可以没有输入，即有0个或多个输入。

（4）输出。算法必须有一个或多个输出，用于显示程序的运行结果。

（5）可行性。算法中的每一个步骤都是可以执行的，都能得到确定的结果，而不能无法执行。比如，用0作为除数就无法执行。

1.4 算法的表示方法

算法的表示方法有很多种，常用的有自然语言、伪代码、传统流程图、N-S流程图、PAD图等。本节主要讲述常用的算法表示方法，其中流程图是学习和掌握的重点。

1.4.1 自然语言

使用自然语言，就是采用人们日常生活中的语言。如求两个数的最大值，可以表示为如果A大于B，那么最大值为A，否则最大值为B。但在描述“陶陶告诉贝贝她的小猫丢了”时，表示的是陶陶的小猫丢了还是贝贝的小猫丢了呢？此处就出现了歧义。可见使用自然语言表示算法时拖沓冗长，容易出现歧义，因此不常使用。

1.4.2 伪代码

伪代码用介于自然语言和计算机语言之间的文字和符号来描述算法。例如，求两个数的最大值可以表示为

if A大于B, then最大值为A, else最大值为B。

伪代码的描述方法比较灵活，修改方便，易于转变为程序，但是当情况比较复杂时，不够直观，而且容易出现逻辑错误。软件专业人员一般习惯使用伪代码，而初学者最好使用流程图。

1.4.3 传统流程图

流程图表示算法比较直观，它使用一些图框来表示各种操作，用箭头表示语句的执行顺序。传统流程图的常用符号如图1-3所示。将【例1.5】求1×2×3×…×100的算法描述为传统流程图，如图1-4所示。用传统流程图表示复杂的算法时不够方便，也不便于修改。

图1-3 传统流程图的常用符号

图1-4 求1×2×3×…×100的传统流程图

1.4.4 N-S流程图

N-S流程图又称盒图，其特点是所有的程序结构均用方框表示。N-S流程图绘制方便，避免了使用箭头任意跳转程序所造成的混乱，更加符合结构化程序设计的原则。它按照从上往下的顺序执行语句。【例1.5】求1×2×3×…×100算法的N-S流程图如图1-5所示。

图1-5 求1×2×3×…×100的N-S流程图

1.5 结构化的程序设计方法

编出程序、得到运行结果只是学习程序设计的基本要求，要全面提高编程的质量和效率，就必须掌握正确的程序设计方法和技巧，培养良好的程序设计风格，使程序具有良好的可读性、可修改性、可维护性。结构化程序设计方法是目前程序设计方法的主流之一。

1.5.1 结构化程序设计

1966年，Bohra和Jacopini提出了顺序结构、选择结构和循环结构3种基本结构，结构化程序设计方法使用这3种基本结构组成算法。已经证明，用3种基本结构可以组成解决所有编程问题的算法。

1．顺序结构

顺序结构按照语句在程序中出现的先后次序执行，其流程图如图1-6所示。顺序结构里的语句可以是单条语句，也可以是一个选择结构或一个循环结构。

图1-6 顺序结构

2．选择结构

选择结构根据条件选择程序的执行顺序。

（1）选择结构一：流程图如图1-7所示，当条件成立时执行语句块①，否则执行语句块②。不管执行哪一个语句块，完成后继续执行选择结构后的语句。选择结构里的语句块可以是顺序语句，也可以是一个选择结构或一个循环结构。

图1-7 选择结构一

（2）选择结构二：流程图如图1-8所示，当条件成立的时候执行语句块，否则什么都不执行。不管执行或不执行语句块，完成后继续执行选择结构后的语句。

图1-8 选择结构二

3．循环结构

循环结构是指设定循环条件，在满足该条件时反复执行程序中的某部分语句，即反复执行循环体。

（1）循环结构一：当型循环结构如图1-9所示。判断条件是否成立，若成立则执行语句块，重复这一过程；当条件不成立时则不再执行循环体。如果第一次条件就不成立，那么该结构的循环体一次也不执行。

图1-9 当型循环结构

（2）循环结构二：直到型循环结构如图1-10所示。先执行一次语句块，然后判断条件是否成立，若成立则执行语句块，重复这一过程，直到条件不成立时不再执行循环体。该结构至少执行一次语句块。

图1-10 直到型循环结构

循环结构里的语句块可以是顺序结构，也可以是一个选择结构或一个循环结构。

1.5.2 结构化程序设计方法

结构化程序设计的思想和方法主要包括以下几个内容。

（1）程序组织结构化。其原则是对任何程序都以顺序结构、选择结构、循环结构作为基本单元来进行组织。这样的程序结构清晰、层次分明，各基本结构间相互独立，方便阅读和修改。

（2）程序设计采用自顶向下、逐步细化、功能模块化的方法，就是将实际问题一步步地分解成有层次又相对独立的子任务，对每个子任务又采用自顶向下、逐步细化的方法继续进行分解，直至分解到一个个功能既简单、明确，又独立的模块，每个模块的设计又可以分解为结构化程序设计的3种基本结构。

习题

一、填空题

（1）程序设计语言从低级到高级可以分为______、______、______和______。

（2）程序有______和______两种执行方式。

（3）算法具有5个特性，分别是______、______、______、______和______。

（4）常用的算法表示方法有______、______、______、______、PAD图等。

（5）结构化程序设计可以被分解为______、______和______的组合或嵌套形式。

（6）程序设计采用______、______、功能模块化的方法。

二、简答题

1．程序设计语言分为几类，各有什么特点？

2．什么是算法，算法有哪些特性？

3．写出求解以下问题的算法，分别画出其传统流程图和N-S图。

（1）有两个变量a和b，请交换两个变量的值。

（2）计算。

4．简述结构化程序设计的一般原则。