《程序设计方法学--第二章结构化程序》由会员分享,可在线阅读,更多相关《程序设计方法学--第二章结构化程序(50页珍藏版)》请在金锄头文库上搜索。
1、第2章 结构化程序,回顾,学科地位 程序设计语言和程序设计方法 程序设计方法产生与发展 程序设计方法学的定义与意义 结构化程序设计及其讨论的主要问题,本章目标,? 有哪些控制结构 ?如何得到良结构的程序,主要内容,什么是结构化程序 结构化定理 一些新的控制结构,内容线索,什么是结构化程序 流程图程序 正规程序 基本程序 结构化程序 结构化定理 一些新的控制结构,流程图程序,流程图是一个描述程序的控制流程和指令执行情况的有向图。 1)函数结点:有一个入口和一个出口线的结点; 2)谓词结点:有一个入口和两个出口线,且它不改变程序的数据项的值的结点;(只作判断,不做计算) 3)汇点:两个入口和一个出
2、口线,且它不执行任何运算的结点。,例子,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
3、的正规子程序,同步练习,判断一个程序是否为正规程序的标准 具有一个入口线和一个出口线; 对每一个结点,都有一条入口线到出口线的通路通过该结点。,(a),(b),(c),基本程序,一个正规程序,如果不包含多于一个结点的正规子程序,称为基本程序。 一个不可再分解的正规程序 仅含一个正规子程序,F,G,同步练习,判断下列程序是正规程序,还是基本程序?,(a),(b),(c),(d),(e),7种基本程序,If-then -else,While-do,Do-until,If-then,Do-while-do,函数,序列,基集合,为了构造一个程序,可以只使用七种基本程序中的一部分。 基集合:用以构造程序
4、的基本程序的集合。 例如: 序列,if-then-else,while-do 或 序列,if-then-else,do-until ,结构化程序,如果一个基本程序的函数结点用另一个基本程序替换,就产生了一个新的正规程序,这样的程序称为复合程序。 一个复合程序的规模可大可小。它的复杂程度依赖于所使用的基集合。 例如: 基集合序列,if-then-else 产生一个无循环的程序类 基集合序列,do-until 产生的程序类是由基集合序列, if-then , while-do产生的程序类的子集,定义: 由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。结构化程序就是我们通常说得好结构的程
5、序。,主要内容,什么是结构化程序 结构化定理 程序函数 结构化定理 递归结构程序 一些新的控制结构,程序函数,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),程序函数表
6、示形式: 有序对、数据赋值以及条件规则等形式 例如: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(
7、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),程序函
8、数是对程序功能的一个精确的描述。 定义:如果程序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 产生的结构
9、化程序。 证明过程提供了一种将正规程序转化为结构化程序的方法,非结构化结构化,考察任何一个正规程序。 首先,从程序的入口处开始给程序的函数结点和谓词结点编号,编号为1,2,n(如果是汇点,那么沿汇点的出口线继续考察,直到找到第一个函数结点或谓词结点)。同时,将每一个函数及谓词结点的出口线用它后面的节点的号码进行编号。如果他后面没有函数或谓词结点,即该结点的出口线直接或通过汇点和程序的出口相连时,出口线编号为0,其次,对原程序中的每一个编号为i, 出口线编号为j的函数结点h,构造一个新的序列程序gi。 其中,L作为计数器。类似地,对每一点编号为i, 出口线编号为j,k的谓词结点,构造一个新的if
10、-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:出口线后无结点,编号
11、=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是g
12、i经过替换以后得到的复合程序 采用以上步骤得到的程序通常称为递归结构程序。,第一步,用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
13、; end; End.,将下列无循环程序转换为结构化程序,同步练习,P,答案,利用结构化定理中给出的方法,得到等价的结构化程序,答案,利用本章介绍方法进行逐步替换,可以得到递归结构程序,答案,简化,内容线索,什么是结构化程序 结构化定理 一些新的控制结构 事件驱动语句 多重出口循环语句 关于N+1/2循环问题 PDL语言的控制结构 其他,事件驱动语句,until EV1 or EV2 or or Evn do S0 then case EV1: S1 EV2: S2 EVn: Sn,C.T.Zahn在1974年提出 含义:重复执行S0,一直到出现事件EV1,EV2,EVn之一为止。,多重出口循
14、环语句,:=exit :=| := : S1; : Sn; endod: S0;,G.V.Bochmann在1973年提出,关于N+1/2循环问题,L1:A; if p then goto L2 fi; B; goto L1; L2:,_,P,B,A,PDL语言的控制结构,其他一些控制结构,J.T.White与L.Presser提出的一种循环语句 loop S1; S2; Sn; end-loop 其中,S1; S2; Sn中至少有一个包含下面两种跳出语句之一 exit(无条件跳出) exit when p(条件跳出),其他一些控制结构,E.W.Dijkstra提出的一种推广的条件控制结构和循环控制结构 条件结构 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 . BnSn fi; 循环 do B1S1 B2S2 . BnSn od;,作业,1、将下图转换为结构化程序。如果可能,请将其进一步转化为递归结构程序。,2、请分别列举出标准C语言和VB语言中的所有控制语句。,