第一讲结构化程序设计基础
一. 程序的三种基本结构
在早期的程序设计中,程序设计基本上是无章可循的,人们可以随心所欲地编写程序,只要符合语言规则并获得正确结果即可.评价一个程序的标准首先看它运行时的效率(运行时间长短和占内存多少).人们往往为了追求时间和内存的微小的节约而千方百计地想出各种小小的”技巧”.但是这样做的结果往往使程序的流程转来转去,使人难以看懂程序和理解设计的思路,使得软件的维护费用日益增高.另一方面由于计算机科学技术的迅速发展,内存量和运行速度都大大提高了,而硬件的价格却不断下降.因而不必为了节省微小的速度和内存而采取使程序晦涩难懂的小技巧,牺牲了程序的易读性.现在评价算法和程序的标准,除了算法正确这一不言而喻的前提外,首先是程序结构清楚,易读性好,其次才是效率.归根结底,只有程序具有良好的结构,易于设计和维护,减少软件成本,从整体来说才是真正的高效率.
荷兰学者Dijkstra提出了“结构化程序设计”的思想,它规定了一套方法,使程序具有合理的结构,以保证和验证程序的正确性.这种方法要求程序设计者不能随心所欲地编写程序,而要按照一定的结构形式来设计和编写程序.它的一个重要目的是使程序具有良好的结构,使程序易于设计,易于理解,易于调试修改,以提高设计和维护程序工作的效率.
结构化程序规定了以下三种基本结构作为程序的基本单元.
(1) 顺序结构.它是最简单,最基本的一种结构. 在这个结构中的各块是只能顺序执行的,见图1-1. 每一块可以包含一条或若干条可执行的指令.
(2) 判断选择结构.见图1-2.
A块或B块.
图
图1-2
(3) 循环结构.见图1-3和图1-4.
图1-3表示的结构称为
”当型”循环.当给定的条件满足时执行A块,否则不执行A块而直接跳到下面部分执行.图1-4表示的结构称为”直到型”循环,它的含义是:执行A块直到满足给定的条件为止(满足了条件就不再执行A块).这两种循环的区别是:当型循环是先判断(条件)再执行,而直到型循环是先执行后判断.
图1-3 图
以上三种基本结构可以派生出其它形式的结构.由这三种基本结构所构成的算法可以处理任何复杂的问题.所谓结构化程序就是由这三种基本结构所组成的程序.
可以看到,三种基本结构都具有以下特点:
①有一个入口.
②有一个出口.
③结构中每一部分都应当有被执行到的机会,也就是说,每一部分都应当有一条从入口到出口的路径通过它(至少通过一次).
④没有死循环(无终止的循环).
结构化程序要求每一基本结构具有单入口和单出口的性质是十分重要的,这是为了便于保证和验证程序的正确性.设计程序时一个结构一个结构地顺序写下来,整个程序结构如同一串珠子一样顺序清楚,层次分明.在需要修改程序时,可以将某一基本结构单独孤立出来进行修改,由于单入口单出口的性质,不致影响到其它的基本结构.
二、结构化流程图
在结构化程序设计中,使用一种”结构化流程图”,所谓流程图是用图形来表示程序设计的方法,它采用一些几何图形来代表各种性质的操作,是程序设计中广泛使用的一种辅助设计手段. 结构化流程图是美国I.Nassi 和B.Schneiderman两人在1973年提出的方法的基础上形成的,因此也称为N-S结构化流程图,它的基本成分有以下三种:
(1)一条简单的指令,用一个矩形框来表示,见图1-5
图1-5
顺序结构可以表示如图1-6
如交换两个变量的值的过程就是顺序结构.见图1-7
图1-7交换变量
(2)判断选择结构用图1-8形式的框图表示:
图1-8
如判断某一年份(year)是否闰年就是一个选择结构, 闰年的判断方法是:如果此年份是400的倍数,则该年为闰年,或者此年份不是100的倍数却是4的倍数,则该年也是闰年. 见图1-9
图1-9
与框图对应if-then语句为:
if year mod 100 = 0
then if year mod 400 = 0 then writeln(…yes‟) else writeln (…no‟)
else if year mod 4 = 0 then writeln (…yes‟) else writeln(…no‟)
(3)循环结构用图1-10和图1-11形式的框图表示.图1-10表示的是当型循环,图1-11表示的是直到型循环.
图1-10 图1-11
如求100个数的和的算法可用直到型循环结构流程图来表示,见图1-12.
图1-12
而判断一个自然数是非为质数的算法可用直到型循环结构流程图来表示,见图1-13.
质数也叫素数,质数的判断是基于这样一条定理:若n是合数(不是质数的数称为合数),则n一定有一个因子大于1,而它的平方小于等于n.这是因为n不是质数,则n可分解成i*j,假设i*i>n,j*j>n,则i*i*j*j>n*n, 即i*j*i*j>n*n,从而推出n*n>n*n,这是不可能的,说明假设不成立, n必有一个因子其平方小于等于n.
由于结构化流程图是一个结构一个结构顺序组成的,因此它不需要象传统的流程图那样的指向线(流程线).所以结构流程图画起来紧凑,占篇幅少,逻辑清楚,容易理解.在结构化程序设计中得到广泛的应用.希望读者能熟练地使用它.下面来看几个具体的例子.
例1-1 用筛选法找出n以内的所有素数(就是质数),并按每行10个数的形式打印出来.n=25时,用筛选法选素数的过程如下:
(1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(2) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(3) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(4) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(5) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
首先确定2是素数,接着把凡是2的倍数的那些数筛去,过程见步骤(2),其中带有删除线的数就是被筛去的数.接着把凡是3的倍数的那些数筛去, 过程见步骤(3). 接着把凡是4的倍数的那些数筛去, 过程见步骤(4).接着把凡是5的倍数的那些数筛去, 过程见步骤(5).这时数列中剩下的未被筛去那些数就都是素数.
筛选法找素数的过程实际上是一个去合数的过程,显然所有被去掉的数都是合数,那么上述的筛选步骤到底要做到第几步才能保证没有合数剩下来呢?沿用前面的质数判断定理,因为任何一个合数一定有一个因子的平方小于等于它本身,所以对任意的n,只要将所有的i(i*i<=n)的倍数筛去, 就能保证没有一个合数剩下来.如n=25时, 筛去5的倍数后就不用再往下做了.为了实现以上算法我们首先可以把2到n这n-1个自然数放在一个数组中,可以用各种方法来表示数组元素中的值已被筛去,例如给数组元素置0或负数.现在我们可以把算法用N-S图描述见图1-14.
