程序设计方法学-第二章结构化程序.ppt

第2章 结构化程序,回顾,学科地位程序设计语言和程序设计方法 程序设计方法产生与发展程序设计方法学的定义与意义结构化程序设计及其讨论的主要问题,本章目标,?有哪些控制结构?如何得到良结构的程序,主要内容,什么是结构化程序结构化定理一些新的控制结构,内容线索,什么是结构化程序流程图程序 正规程序 基本程序 结构化程序 结构化定理一些新的控制结构,流程图程序,流程图是一个描述程序的控制流程和指令执行情况的有向图。1）函数结点：有一个入口和一个出口线的结点；2）谓词结点：有一个入口和两个出口线，且它不改变程序的数据项的值的结点；（只作判断，不做计算）3）汇点：两个入口和一个出口线，且它不执行任何运算的结点。,例子,L1:if B1 then goto L2;S1;if B2 then goto L2;S2;goto L1;L2:S3;,正规程序,一个流程图程序如果满足：（1）只有一个入口和一个出口（2）对于每一个结点，都有一个从入口到出口 的通路（即每个结点都可达）则这个流程图程序称为正规程序。,正规程序图例,正规子程序,一个正规程序的某些部分仍然是正规程序，把这些部分称为正规子程序。,正规程序,一个正规程序可以抽象为一个函数结点组成：正规子程序。,b,q,a,p,抽象成,=,g,b,P,q,a,g,g,b是k的正规子程序，函数结点a又是g的正规子程序,同步练习,判断一个程序是否为正规程序的标准具有一个入口线和一个出口线；对每一个结点，都有一条入口线到出口线的通路通过该结点。,（a）,（b）,（c）,基本程序,一个正规程序，如果不包含多于一个结点的正规子程序，称为基本程序。一个不可再分解的正规程序仅含一个正规子程序,F,G,同步练习,判断下列程序是正规程序，还是基本程序？,（a）,（b）,（c）,（d）,（e）,7种基本程序,If-then-else,While-do,Do-until,If-then,Do-while-do,函数,序列,基集合,为了构造一个程序，可以只使用七种基本程序中的一部分。基集合：用以构造程序的基本程序的集合。例如：序列，if-then-else，while-do或序列，if-then-else，do-until,结构化程序,如果一个基本程序的函数结点用另一个基本程序替换，就产生了一个新的正规程序，这样的程序称为复合程序。一个复合程序的规模可大可小。它的复杂程度依赖于所使用的基集合。例如：基集合序列，if-then-else 产生一个无循环的程序类 基集合序列，do-until 产生的程序类是由基集合序列，if-then，while-do产生的程序类的子集,定义:由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。结构化程序就是我们通常说得好结构的程序。,主要内容,什么是结构化程序结构化定理程序函数结构化定理递归结构程序一些新的控制结构,程序函数,1）程序函数已知一正归程序P，对于每一个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯一的，那么所有的有序对的集合（X,Y）定义了一个函数。我们称这个函数为程序P的程序函数，记为P。,例：If x y then z=x;Else z=y;程序函数1：(x，y，z)，(x，y，min(x，y)程序函数2：z=min(x，y),例：t:=x;x:=y;y:=t;程序函数为：(x，y，t)，(y，x，x),程序函数表示形式：有序对、数据赋值以及条件规则等形式例如：if x y then z:=x else z:=y fi=(x,y,z),(x,y,min(x,y)/有序对的形式(x,y,z)|x yz:=x xyz:=y/条件规则的形式(z:=min(x,y)/数据赋值的形式,基本程序所对应的程序函数,函数：f=(x,y)|y=f(x)序列：f;g=(x,y)|y=g f(x)IF-THEN:if-then=(x,y)|p(x)y=f(x)|p(x)y=x WHILE-DO:while-do=(x,y)|k 0(j,1jk)(p fj(x)p fk(x)y=fk(x),g f(x)表示函数的复合，即g(f(x),Fj(x)表示同一函数的多重复合，即f0(x)=x，fk(x)=f fk-1(x),k=1,2,基本程序所对应的程序函数,DO-UNTIL:do-until=(x,y)|k 0(j,1 jk)(p fj(x)p fk(x)y=fk(x)IF-THEN-ELSE:if-then-else=(x,y)|p(x)y=f(x)|p(x)y=g(x)DO-WHILE-DO:do-while-do=(x,y)|k 0(j,1 jk)(p f(g f)j(x)p f(g f)k(x)y=f(g f)k(x),程序函数是对程序功能的一个精确的描述。定义:如果程序P1和P2有相同的程序函数，称它们是函数等价的，或者简称是等价的。,同步练习,写出下列程序的程序函数1、while x0 do x:=x-1 od=(x,min(0,x)=(x:=min(0,x)2、x:=x+y;y:=x-y=(x,y),(x+y,x)=(x,y:=x+y,x)3、do x:=x+1 until xy od=(x,y),(max(x+1,y+1),y)=(x:=max(x+1,y+1),结构化定理,2）结构化定理任一正规程序都可以函数等价于一个由基集合序列，IF-THEN-ELSE，WHILE-DO 产生的结构化程序。证明过程提供了一种将正规程序转化为结构化程序的方法,非结构化结构化,考察任何一个正规程序。首先，从程序的入口处开始给程序的函数结点和谓词结点编号，编号为1，2，n(如果是汇点，那么沿汇点的出口线继续考察，直到找到第一个函数结点或谓词结点)。同时，将每一个函数及谓词结点的出口线用它后面的节点的号码进行编号。如果他后面没有函数或谓词结点，即该结点的出口线直接或通过汇点和程序的出口相连时，出口线编号为0,其次，对原程序中的每一个编号为i,出口线编号为j的函数结点h，构造一个新的序列程序gi。其中，L作为计数器。类似地，对每一点编号为i,出口线编号为j,k的谓词结点，构造一个新的if-then-else程序gi.,最后，利用已经得到的一些gi（i=1,2,n）按下图的形式构造一个while-do循环，这个循环的循环体是一个对L从1到n进行测试的嵌套的if-then-else程序（最内层的I表示恒等函数）。如果Ix=|xX,则称函数Ix:X X为恒等函数。,显然，这个程序的功能和原程序是相同的，因而它和原程序是函数等价的。而且这个程序是一个由基集合序列，IF-THEN-ELSE，WHILE-DO 产生的结构程序。从而，定理得证。,实例,原程序编码规则1：给程序的函数结点、谓词结点编号，汇点略过规则2：出口线用它后面的结点的号码进行编号规则3：出口线后无结点，编号=0,实例,编码后，对每一个编号构造一个新的序列程序gi方法1：函数程序方法2：谓词程序,实例,由gi组合成新结构程序,问题：比较庞大，而且效率不高。解决办法：需要简化，特别是消除一些多余的对L的测试与赋值。,结构化定理,3）递归结构程序基本思想：对于某些j0，如果在gj中不包含有赋值L:=j，那么可以用程序gj代替所有的赋值L:=j。这样代替以后，由于j不再赋值给L，因而测试L=j可以从if-then-else结构中去掉。这个替换过程可以一直继续到下面两种情况出现为止：a)除了 L:=0以外，所有的给L赋值均被消除；b)每一个余下的gi中都包含有相应的赋值L:=i。gi是gi经过替换以后得到的复合程序采用以上步骤得到的程序通常称为递归结构程序。,第一步，用g4代替赋值L:=4，并且消除测试,得到；,结构化递归,第二步，用代换后的g3，即L=3通路上的if-then-else程序代替赋值L:=3，并且消除测试L=3，得到,第三步，用g2代替赋值L:=2，得到,第四步，L的初值为1，而且只有在程序的出口处才变为0，所以在循环中的赋值L:=1和测试L=1是不需要的，可以消除它们。,对应的程序,L:=1;while L0 do Begin if p then begin e;L:=0;end;else begin if q then L:=0;else h;end;End.,将下列无循环程序转换为结构化程序,同步练习,P,答案,利用结构化定理中给出的方法,得到等价的结构化程序,答案,利用本章介绍方法进行逐步替换，可以得到递归结构程序,答案,简化,内容线索,什么是结构化程序结构化定理一些新的控制结构事件驱动语句 多重出口循环语句关于N+1/2循环问题PDL语言的控制结构其他,事件驱动语句,until EV1 or EV2 or or Evn do S0then case EV1:S1 EV2:S2 EVn:Sn,在1974年提出含义：重复执行S0,一直到出现事件EV1，EV2，EVn之一为止。,多重出口循环语句,：=exit：=|:=：S1;：Sn;endod:S0;,在1973年提出,关于N+1/2循环问题,L1:A;if p then goto L2 fi;B;goto L1;L2:,_,P,B,A,PDL语言的控制结构,其他一些控制结构,与L.Presser提出的一种循环语句loop S1;S2;Sn;end-loop其中，S1;S2;Sn中至少有一个包含下面两种跳出语句之一exit（无条件跳出）exit when p（条件跳出）,其他一些控制结构,提出的一种推广的条件控制结构和循环控制结构条件结构if guard 1:action 1;guard 2:action 2;guard n:action n;fi循环结构loop guard 1:action 1;guard 2:action 2;guard n:action n;pool,其他一些控制结构,D.Gries提出的条件控制结构和循环结构条件if B1S1 B2S2.BnSnfi;循环do B1S1 B2S2.BnSnod;,作业,1、将下图转换为结构化程序。如果可能，请将其进一步转化为递归结构程序。,2、请分别列举出标准C语言和VB语言中的所有控制语句。,