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

《程序设计方法学第二章结构化程序.ppt》由会员分享，可在线阅读，更多相关《程序设计方法学第二章结构化程序.ppt（50页珍藏版）》请在第壹文秘上搜索。

1、第2章 结构化程序 回顾学科地位程序设计语言和程序设计方法 程序设计方法产生与发展程序设计方法学的定义与意义结构化程序设计及其讨论的主要问题本章目标? 有哪些控制结构有哪些控制结构?如何得到良结构的程序如何得到良结构的程序主要内容 什么是结构化程序 结构化定理 一些新的控制结构内容线索 什么是结构化程序什么是结构化程序 流程图程序 正规程序 基本程序 结构化程序 结构化定理结构化定理 一些新的控制结构一些新的控制结构流程图程序 流程图流程图是一个描述程序的控制流程和指令执行情况的有向图。 1）函数结点：有一个入口和一个出口线的结点； 2）谓词结点：有一个入口和两个出口线，且它不改变程序的数据项

2、的值的结点；（只作判断，不做计算） 3）汇点：两个入口和一个出口线，且它不执行任何运算的结点。 例子B1S1B2S2S3TTFFL1: if B1 then goto L2; S1; if B2 then goto L2; S2; goto L1;L2: S3;正规程序一个流程图程序如果满足：（1）只有一个入口和一个出口（2）对于每一个结点，都有一个从入口到出口 的通路（即每个结点都可达）则这个流程图程序称为正规程序。正规程序图例paqbstcdkpgh正规子程序paqbstcd一个正规程序的某些部分仍然是正规程序，把这些部分称为正规子程序正规子程序。正规程序 一个正规程序可以抽象为一个函数结

3、点一个正规程序可以抽象为一个函数结点 组成：正规子程序。组成：正规子程序。bqapk抽象成抽象成=gbPqagg,b是是k的正规子程序，函数结点的正规子程序，函数结点a又是又是g的正规子程序的正规子程序同步练习 判断一个程序是否为正规程序的标准 具有一个入口线和一个出口线； 对每一个结点，都有一条入口线到出口线的通路通过该结点。 （a）（b）（c）基本程序一个正规程序，如果不包含多于一个结点的正规子程序，称为基本程序。一个不可再分解的正规程序仅含一个正规子程序 FFGFPPF同步练习 判断下列程序是正规程序，还是基本程序？（a）（b）（c）（d）（e）7种基本程序If-then-else Wh

4、ile-do Do-until If-then Do-while-do 函数序列基集合为了构造一个程序，可以只使用七种基本程序中的一为了构造一个程序，可以只使用七种基本程序中的一部分。部分。基集合：用以构造程序的基本程序的集合。例如： 序列，if-then-else，while-do 或 序列，if-then-else，do-until 结构化程序 如果一个基本程序的函数结点用另一个基本程序替换，就产生了一个如果一个基本程序的函数结点用另一个基本程序替换，就产生了一个新的正规程序，这样的程序称为复合程序。新的正规程序，这样的程序称为复合程序。 一个复合程序的规模可大可小。它的复杂程度依赖于所使

5、用的基集合。一个复合程序的规模可大可小。它的复杂程度依赖于所使用的基集合。 例如： 基集合序列，if-then-else 产生一个无循环的程序类 基集合序列，do-until 产生的程序类是由基集合序列， if-then ， while-do产生的程序类的子集定义定义: 由基本程序的一个固定的基集合构造出的复合程序称为由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。结构化程序就是我们通常说得好结构的程序。结构化程序。结构化程序就是我们通常说得好结构的程序。主要内容 什么是结构化程序什么是结构化程序 结构化定理结构化定理 程序函数 结构化定理 递归结构程序 一些新的控制结构一些新的控

6、制结构程序函数1 1）程序函数）程序函数已知一正归程序P，对于每一个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯一的，那么所有的有序对的集合（X,Y）定义了一个函数。我们称这个函数为程序P的程序函数，记为P。PXY例：If x yz:=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

7、0(j,1j 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 j0 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）结构化定

8、理结构化定理任一正规程序都可以函数等价于一个由基集合序列，IF-THEN-ELSE，WHILE-DO 产生的结构化程序。 证明过程提供了一种将正规程序转化为结构化程序的方法非结构化非结构化结构化结构化 考察任何一个正规程序。首先，首先，从程序的入口处开始给程序的函数结点和谓词结点编号，编号为1，2，n(如果是汇点，那么沿汇点的出口线继续考察，直到找到第一个函数结点或谓词结点)。同时，将每一个函数及谓词结点的出口线用它后面的节点的号码进行编号。如果他后面没有函数或谓词结点，即该结点的出口线直接或通过汇点和程序的出口相连时，出口线编号为0 其次，其次，对原程序中的每一个编号为i, 出口线编号为j的

9、函数结点h，构造一个新的序列程序gi。其中，L作为计数器。类似地，对每一点编号为i, 出口线编号为j,k的谓词结点，构造一个新的if-then-else程序gi. L=n gn I L=n-1 gn-1 L=2 g2 L=1 g1 L0 L:=1 f=最后，最后，利用已经得到的一些gi（i=1,2,n）按下图的形式构造一个while-do循环，这个循环的循环体是一个对L从1到n进行测试的嵌套的if-then-else程序（最内层的I表示恒等函数）。如果Ix=|xX,则称函数Ix :X X为恒等函数。显然，显然，这个程序的功能和原程序是相同的，因而它和原程序是函数等价的。而且这个程序是一个由基集

10、合序列，IF-THEN-ELSE，WHILE-DO 产生的结构程序。从而，定理得证。实例 原程序 编码 规则1：给程序的函数结点、谓词结点编号，汇点略过 规则2：出口线用它后面的结点的号码进行编号 规则3：出口线后无结点，编号=0q e p h 1 4 3 2实例 编码后，对每一个编号构造一个新的序列程序gi 方法1：函数程序 方法2：谓词程序 P L:=2 L:=3 g1=Q L:=0 L:=4 g3=e L:=0 g2=h L:=1 g4=q e p h 1 4 3 2实例 由gi组合成新结构程序问题：比较庞大，而且效率不高。问题：比较庞大，而且效率不高。解决办法：需要简化，特别是消除一些

11、多余的对解决办法：需要简化，特别是消除一些多余的对L的测试与赋值。的测试与赋值。L=4IL=3L =2eL =1L 0L:=1hL:=1L:=0L:=4qL:=0PL:=2L:=3结构化定理 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经过替换以后得到的复合程序 采用以

12、上步骤得到的程序通常称为递归结构程序。第一步，用g4代替赋值L:=4，并且消除测试, 得到； 结构化结构化递归递归 IL=3L=2eL=1L0L:=1L:=0L:=1qL:=0PL:=2L:=3hg3第二步，用代换后的g3，即L=3通路上的if-then-else程序代替赋值L:=3，并且消除测试L=3，得到 IL 0L:=1L:=0L:=1qPL:=2hL =1L =2eL:=0g2第三步，用g2代替赋值L:=2，得到 I L0 L:=1 L:=0 L:=1 q P h L=1 e L:=0 第四步，L的初值为1，而且只有在程序的出口处才变为0，所以在循环中的赋值L:=1和测试L=1是不需要

13、的，可以消除它们。 L0 L:=1 L:=0 q P h e L:=0 对应的程序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.同步练习 将下列无循环程序转换为结构化程序 Pf g qhkr1234567答案 利用结构化定理中给出的方法,得到等价的结构化程序答案 利用本章介绍方法进行逐步替换，可以得到递归结构程序答案 简化内容线索 什么是结构化程序什么是结构化程序 结构化定理结构化定理 一些新的控制结构一些新的控制结构 事件驱动语句 多重出口循环语句

14、 关于N+1/2循环问题 PDL语言的控制结构 其他事件驱动语句 until EV1 or EV2 or or Evn do S0then case EV1: S1 EV2: S2 EVn: SnC.T.Zahn在1974年提出含义：重复执行S0,一直到出现事件EV1，EV2，EVn之一为止。多重出口循环语句：=exit ：=| := ： S1; ： Sn; endod: S0;G.V.Bochmann在1973年提出关于N+1/2循环问题L1:A; if p then goto L2 fi; B; goto L1;L2:_PBAPDL语言的控制结构序列f;gif-then:if p then

15、 f fiwhile-do:while p do f oddo-until:do f until p odif-then-else:if p then f else g fido-while-do:do1 f while p do2 g od其他一些控制结构 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、将下图转换为结构化程序。如果可能，请将其进一步转化为递归结构程序。f1f2p1f3p2p3f4f4u2、请分别列举出标准C语言和VB语言中的所有控制语句。