第2章　算法——程序的灵魂

2.1　复习笔记

一、概述

一个程序主要包括以下两方面的信息：

（1）对数据的描述，即数据结构（data structure）。

（2）对操作的描述，即算法（algorithm）。

二、算法概述

1算法定义

广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。

2算法分类

（1）数值运算算法，数值运算的目的是求数值解。

（2）非数值运算算法。

三、算法的特性

1有穷性

一个算法应包含有限的操作步骤，而不能是无限的。

2确定性

算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。

3有零个或多个输入

输入是指在执行算法时需要从外界取得必要的信息。

4有一个或多个输出

算法的目的是为了求解，“解”是指输出。

5有效性

算法中的每一个步骤都应当能有效地执行，并得到确定的结果。

四、怎样表示一个算法

1用自然语言表示算法

自然语言是指人们日常使用的语言，其特点是通俗易懂，但语义语法不严格，描述能力不足。

2用流程图表示算法

（1）概述

美国国家标准化协会ANSI规定了一些常用的流程图符号（如图2-1所示），已为世界各国程序工作者普遍采用。

图2-1　常用的流程图符号

（2）流程图元素

①菱形框

菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。它有一个入口，两个出口，如图2-2所示。

图2-2　菱形框

②连接点

连接点（小圆圈）是用于将画在不同地方的流程线连接起来，如图2-3所示。

图2-3　连接点

③注释框

注释框不是流程图中必要的部分，不反映流程和操作，只是为了对流程图中某些框的操作作必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。

（3）流程图组成

①表示相应操作的框；

②带箭头的流程线；

③框内外必要的文字说明。

3三种基本结构和改进的流程图

（1）传统流程图的弊端

传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。

（2）三种基本结构

①顺序结构

如图2-4所示，虚线框内是一个顺序结构。其中A和B两个框是顺序执行的。顺序结构是最简单的一种基本结构。

图2-4　顺序结构

②选择结构

选择结构又称选取结构或分支结构，如图2-5所示。虚线框内是一个选择结构，此结构中必包含一个判断框，根据给定的条件P是否成立而选择执行A框或B框。

图2-5　选择结构

③循环结构

又称重复结构，即反复执行某一部分的操作，有两类循环结构，如图2-6所示。

图2-6　循环结构

（3）三种结构共同特点

①只有一个入口；

②只有一个出口；

③结构内的每一部分都有机会被执行到；

④结构内不存在“死循环”。

基本结构并不一定只限于上面3种，只要具有上述4个特点的都可以作为基本结构。如图2-7为经典的do…while循环结构、而图2-8为经典的switch选择结构。

图2-7　do…while循环结构

图2-8　switch选择结构

4用N-S流程图表示算法

（1）概述

在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他从属于它的框，或者说，由一些基本的框组成一个大的框，这种流程图又称N-S结构化流程图。

（2）N-S流程图符号

①顺序结构

顺序结构用图2-9形式表示。A和B两个框组成一个顺序结构。

图2-9　顺序结构

②选择结构

选择结构用图2-10表示，其中p为判断条件。

图2-10　选择结构

③循环结构

当型循环结构用图2-11形式表示，当p₁条件成立时反复执行A操作，直到p₁条件不成立为止。

图2-11　当型循环结构

直到型循环结构用图2-12形式表示，先执行A操作，然后判断p₁条件是否成立，如果p₁成立，反复执行A，只当p₁条件不成立才停止循环。

图2-12　直到型循环结构

5用伪代码表示算法

（1）概述

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。

（2）特点

①伪代码书写格式比较自由，容易表达出设计者的思想；

②用伪代码写的算法很容易修改；

③用伪代码很容易写出结构化的算法。

6用计算机语言表示算法

用流程图或伪代码描述一个算法后，还要将它转换成计算机语言程序。用计算机语言表示的算法是计算机能够执行的算法，其必须严格遵循所用语言的语法规则。

五、结构化程序设计方法

1基本思路

结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。

2结构化程序设计方法

（1）自顶向下

（2）逐步细化

（3）模块化设计

（4）结构化编码