结构化程序设计PPT课件.ppt

1、第4章 结构化程序设计,4.1 关于结构程序设计的基本概念 4.2 结构化程序和结构定理 4.3 结构化程序设计的判别 4.4 结构化程序设计的步骤和原理 4.5 逐步求精的程序设计 4.6 非结构化向结构化的转化 4.7 结构化程序的正确性验证 小结 习题,4.1 关于结构程序设计,1. 定义 结构程序设计是避免使用GOTO语句的一种程序设计 结构程序设计是自顶向下的程序设计 是一种组织和编制程序的方法,利用它编制的程序易于理解和修改 程序结构化的一个主要功能是使得正确性证明容易实现 允许在设计过程中的每一步验证其正确性,即自动导致自我说明与自我捍卫的程序风格 是讨论如何将任何大规模的复杂的

2、流程图程序转换成一种标准形式,使得它们用几种标准的控制结构, 通过重复和嵌套来表示.,结构程序设计的综合描述,结构程序设计的综合描述: 结构程序设计是一种进行程序设计的原则和方法，按照这种原则和方法设计出的程序的特点是：结构清晰、易阅读、易修改、易验证。 结构程序设计语言：按照结构程序设计的要求设计出的程序设计语言称为结构程序设计语言。 结构化程序：利用结构程序设计语言，或按照结构程序设计的思想编制的程序称为“结构化程序” 。,关于GOTO语句的问题,4. 关于GOTO语句的问题 取消GOTO语句，即GOTO有害。理由： GOTO语句使程序的静态结构与它的动态执行之间有很大的差别。这样使程序难

3、阅读、难查错。 去掉GOTO语句可以直接从程序结构上反映出程序运行的过程，结构清晰、便于查错、易验证。 保留GOTO语句 GOTO语句使用起来比较灵活，而且有些情况下能够提高程序的效率，若一味地强调删除GOTO语句，有些情形会使程序过于复杂，增加不必要的计算量。 折中派（Knuth） 不加限制地使用GOTO语句，特别往回跳的GOTO语句，会使程序结构难以理解，这种情形应尽量避免使用GOTO语句。 为提高效率，同时又不破坏程序的良好结构，有控制地使用GOTO语句是有必要的。,结构程序设计结论,结论： 结构程序设计讨论的是一种程序设计的方法和风格。关注的焦点是得到的程序的结构的好坏，而有无GOTO

4、语句并不是一个程序结构好坏的标志。避免和限制使用GOTO语句是得到结构化程序的一种手段，而不是我们的目的。 结构化程序设计既着眼于程序设计的思路清晰，又着眼于程序的结构清晰。即通过结构化的设计方法获得结构化产品,4.2 结构化程序和结构定理,一、结构化程序 下面给结构化程序下一个精确的定义.,流程图程序,流程图程序的组成：函数节点、谓词节点和汇点。 函数节点：只有一条入口线和一条出口线，一般与赋值语句相对应。 谓词节点：有一条入口线和两条出口线，它不改变程序的数据项的值。 汇点：有两条入口线和一条出口线，它不执行任何运算，只起到收集出口线的作用。,f,p,1. 流程图程序 定义：一个用流程图的

5、形式表示出来的程序，称为流程图程序。,流程图程序举例,流程图程序举例:,p,q,g,f,正规程序,4. 正规程序 定义：满足以下两个条件的流程图程序称为正规程序。条件： 具有一条入口线和一条出口线，且 对每个节点，都有一条从入口线到出口线的通路通过该节点。 例：下面两个流程图程序不是正规程序,正规子程序,3. 正规子程序 一个正规程序的某些部分仍然可以是正规程序,这些部分称为正规子程序.,基本程序,4. 基本程序 定义：一个正规程序，如果不包含多余一个节点的正规子程序，称为基本程序。即基本程序是一种不可再分解的正规程序。 例：,f,g,f,g,h,f,g,f,七种重要的基本程序,函数: 序列:

6、 If-then If-then-else,f,g,f,p,f,g,p,f,七种重要的基本程序,while-do: Do-until: Do-while-do:,p,f,p,g,f,p,g,复合程序和结构化程序,5. 复合程序 若一个基本程序的函数节点用另外一个基本程序替换, 所产生的正规程序称为复合程序。 6. 结构化程序 由基本程序的一个固定的基集合（例如，序列、IF-THEN-ELSE、While-DO）构造出的复合程序称为结构化程序。,二、结构化定理,1. 程序函数 已知一正规程序P，对于每个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯

7、一的，那么所有的有序对的集合（X，Y）定义了一个函数，称这个函数为程序P的程序函数，记为P。 例：设程序P由三条语句组成： t:=x; x:=y; y:=t; 对任意的X=(x,y,t), 程序P的执行结果Y=（y,x,x） 因此，程序函数是（x,y,t）,(y,x,x) 本质： 计算输入和输出的关系,二、结构化定理,2. 七种基本程序的程序函数 f = (x,y)| y=f(x) f;g = (x,y)| y = g f(x) if-then = (x,y)|p(x)y=f(x)|p(x)y=x if-then-else = (x,y)| p(x)y=f(x)|p(x)y=g(x),二、结构

8、化定理,while-do = (x,y)|k0 (j:00 (j:1=jk)( p f j(x)| p f k(x)y= f k(x) do f while p do g od = (x,y)| k0 ( j : 0=jk : p f (g f) j(x)| p f (g f) k(x)y= f (g f) k(x),2. 七种基本程序的程序函数(续),二、结构化定理,1）对于序列程序可使用跟踪表的方法计算p 例：语句段：x := x+y; y:= x-y; x:= x-y; 解：假设变量x,y的初值为x0,y0, 有跟踪表：,X3=x2-y2 =x1-(x1-y1) = y1 = y0 Y3

9、 = y2 =x1-y1 =x0+y0y0=x0,P = (x,y),(y,x),3. 程序函数的计算,二、结构化定理,练习： 计算下列语句序列的程序函数： y:=a; y:=x*y+b; y:=x*y+c; y:=x*y+d,3. 程序函数的计算,二、结构化定理,2)无循环程序的程序函数 首先：构造有穷的执行树 然后：对每条路径写出相应的表达式 例：,p,f,h,r,g,q,3. 程序函数的计算,二、结构化定理,执行树：,p = (x,y)| p(x) qf(x)y=gf(x) | p(x) qf(x) r h f(x)y=gh f(x) | p(x) qf(x) r h f(x)y=h f

10、(x) | p(x) | ,3. 程序函数的计算,二、结构化定理,3)循环程序的程序函数,g1,g3,p1,p2,p3,g2,g4,g5,1,g1,2,g3,p1,g2,1,3,p2,p3,g5,3,g4,2,执行树：,3. 程序函数的计算,代换后的执行树：,g1,g3,p1,g2,p2,p3,g5,g4,f1,f3,f1,f2,f2,f3,f1 = (x,y)|y = f2 g1(x) F2 = (x,y)|p1g3(x)y=f1g2g3(x) | p1g3(x)y=f3g3(x) F3= (x,y)|p2(x) p3(x)y=f3 g5(x) | p2(x) p3(x)y=x | p2(x

11、) y=f2 g4(x),二、结构化定理,5 . 程序的函数等价 如果程序P1和程序P2有相同的程序函数，称它们是函数等价的，或简称是等价的。,5. 结构化定理 定理：任一正规程序都可以函数等价与一个由基集合序列，if-then-else，while-do产生的结构化程序。,结构化定理-证明,证明：考察任一正规程序: 首先，从程序的入口处开始给程序的函数节点和谓词节点编号。编号为1，2，3， ，n（若入口处是汇点，那么宴会点的出口线继续考察，直到找到第一个函数节点或谓词节点）。同时将每一个函数节点及谓词节点的出口线用它后面的节点的编号进行编号。如果它后面没有函数节点或谓词节点，即该节点的出口线

12、直接或通过汇点与程序的出口相连时，出口线的编号为0。,1,2,3,4,0,0,结构化定理-证明,对每一个编号为i，出口线编号为j、k的谓词节点p，构造一个新的IF-THEN-ELSE程序gi，如图：,h,其次，对原程序种的每一个编号为i，出口线编号为J的函数节点h，构造一个新的序列程序gi，如图：,i,j,h,L:=j,gi=,p,gi=,p,L:=j,L:=k,j,i,k,结构化定理-证明,最后，利用已经得到的一些gi（I=1,2,3,n），按下图形式构造一个while-do循环。这个循环体是一个对L从1到n进行测试的嵌套的IF-THEN-ELSE程序（最内层的I表示恒等函数）：,L:=1,

13、L0,L=1?,g1,L=2?,g2,L=n-1?,gn-1,L=n?,gn,I,F=,结构化定理-证明,结论: 显然,上面程序的功能和原程序的功能是相同的,因而它和原程序是函数等价的。而且，该程序是由一个固定的基集合序列，IF-THEN-ELSE，WHILE-DO产生的结构化程序，从而定理得证。,结构化定理举例,例：考察如下的流程图程序：,1,2,3,4,0,0,第一步：编号，结果如上图。,结构化定理举例,第二步：重新构造函数节点和谓词节点,e,L:=0,g2 =,g1 =,p,L:=2,L:=3,g3 =,q,L:=0,L:=4,h,L:=1,g4 =,结构化定理举例,第三步：用IF-TH

14、EN-ELSE和WHILE-DO重新构造程序：,L:=1,L0,L=1?,L=2?,p,L:=2,L:=3,e,L:=0,L=3?,q,L:=0,L:=4,L=4?,h,L:=1,I,结构化定理举例,第四步：化简： 上面得到的结构化程序比较庞大，且效率不高，还可以进一步改进，消除一些多余的对L的测试和赋值。 化简的基本思想： 对于某些 j0，如果gj中不包含赋值语句L:=j，则可以用gj代替所有的赋值L:=j。这样代替后，由于j不再赋值给L，因而测试L=j可以从IF-THEN-ELSE结构中去掉。这种替换直到以下情况出现为止： 除了L:=0以外，所有给L赋值的语句均被消除； 每个余下的gi中都

15、包含由相应赋值L:=I（gi是gi经过一些替换以后得到的复合程序） 例：,结构化定理转换的化简,用g4代替所有的L:=4的赋值语句，并删除L=4的测试,L:=1,L0,L=1?,L=2?,p,L:=2,L:=3,e,L:=0,L=3?,q,L:=0,h,L:=1,I,结构化定理转换的化简（续）,用当前的g3替换L:=3的赋值语句，并删除L=3的测试,L:=1,L0,L=1?,L=2?,p,L:=2,e,L:=0,q,L:=0,h,L:=1,I,结构化定理转换的化简（续）,用g2替换L:=2的赋值。,L:=1,L0,L=1?,p,q,L:=0,h,L:=1,I,e,L:=0,结构化定理转换的化简

16、（续）,删除循环中L:=1的赋值，因为除了L:=0的赋值回改变L的取值外，都不会改变L的取值，进而L=1的测试也可以删除。,L:=1,L0,p,q,L:=0,h,e,L:=0,结构化程序的特点,具有层次化结构的程序，有很大的优点： 书写时，自顶向下，逐步求精 阅读时，自底向上，逐步抽象 验证时，分层逐步验证,4.3 结构化程序设计的判别,一个软件是否满足结构化标准可以用Mccabe关于软件复杂性度量的理论判断 有关的定理和推论 任何非结构化的程序是由下列4中情况引起 从循环中转出 从循环外转入 从判定内转出 从判定外转入,4.3 结构化程序设计的判别(续),有关的定理和推论 推论1：一个结构化

17、程序可以按照不转入（出）循环或判定的原则编写。 程序控制结构的表示 用有向图表示。每个节点对应于顺序处理的代码块，弧线对应程序中的转移，箭头代表转移方向。假设只有一个入口和一个出口。如果从出口节点转回到入口节点，则称图是强连通的。,4.3 结构化程序设计的判别(续),定理1：在一个强连同图G中，线性无关的环路数最大值V(G)en1，其中e是弧数，n是节点数。 例如：V(G)=10-6+1 = 5 V(G)的另一种计算方法 V(G)i1 to Q (Ti1)+p+1, 其中，p为程序中条件转移语句的个数，Q是分支情况语句，Ti是第i个分情况语句的情况总数。,4.3 结构化程序设计的判别(续),推

18、论2：一个结构化程序课退化称成最大环路数为1的程序。这种退化是对程序的逐渐抽象，形成只有一个入口和一个出口节点的子图的过程。 定义1：正规子图是仅含顺序、选择和循环的子图。假设m是有一个入口节点和一个出口节点的正规子图，ev为程序的本质复杂性，则ev V(G)m，将反映程序结构的复杂程度。vv越大，程序的结构化程度越差。显然，1= ev =V(G) 推论3：一个结构化程序的本质复杂性ev为1。,4.3 结构化程序设计的判别(续),判别途径 判别一个程序是否满足结构化程序设计标准的要求： 是否有一个入口和出口节点 是否有转入循环或判定的情形 计算程序的本质复杂性 检验结构化程序设计标准的其他要求

19、。,4.4 结构化程序设计的步骤和原理,结构化程序设计的步骤： Step1：需求分析 Step2：系统设计：总体设计和模块设计 Step3：算法和程序实现； Step4：验证和测试 Step5：运行程序和整理文档,4.4 结构化程序设计的步骤和原理,结构化程序设计的原理 抽象 分解 模块化 局部化和信息隐蔽 一致性 完整性：要求一个程序系统不丢失任何重要成分，系统无缺省且独立。独立意义的完整性指一个系统相对完备，除基本的运行环境外，不涉及其他系统。 可验证性：指分解系统和构造模块时应使各模块和整个系统都能方便测试，从而也利于维护和修改,4.5 逐步求精的设计方法,结构化程序设计规则不是使程序写

20、完之后再来验证程序的正确性，而是在算法逐步细化为程序的过程中，确保每一步细化都正确地实现前一步的要求，因此逐步求精既是一种程序设计方法，同时也是验证程序正确性的方法。 逐步求精的思想： 先全局后局部，先整体后细节，先抽象后具体的过程组织人们的思维活动，使得编写的程序结构清晰，容易阅读，易修改。同时它可以实现边设计边验证的方式简化对程序的正确性验证过程。 是一种自顶向下的程序设计方法 举例：,4.5 逐步求精的设计方法（续）,例：编写一个程序，打印前n个素数(n为给定的正整数) Void prime(int n) int i, x; x = 1; for (i=1; in; i+) x = “下

21、一个素数”； printf( “%d”, x); ,对语句x = “下一个素数”求精 int prim； prim false； Do x+; while( isprime(x) ),4.5 逐步求精的设计方法（续）,对函数isprime(x)求精 k=2; Prim = true; While (k=lim ,Lim的确定 是k的上界，即limx1；,“x不能被k整除”的求精 x mod k0 ；,Void prime(int n) int i, x; x = 1; for (i=1; in; i+) do x+; while( isprime(x) ) printf( “%d”, x);

22、,4.5 逐步求精的设计方法（续）,int isprime(int x) k=2; Prim = true; While (k 0 ; k+; return prim ; ,优化： 关于x+, x+=2; 关于上限的确定：x-1是最大的上限；,4.6 非结构化向结构化的转化,法1：代码复制法,方法2：布尔标志法 引入布尔变量, 例：,方法3：结构化定理,4.6 非结构化向结构化的转化(续),例 While P do Begin if q then goto L1 A; B; End L1: ,转化为： Bool := True; While P and Bool do Begin if q t

23、hen goto Bool:=false else begin A; B; end End ,4.7 结构化程序的正确性证明正确性定理,1. 正确性定理 假设已知程序P和一个预期函数 f ，若有fP称程序 P 正确地实现了函数 f ， 或者说程序P是正确的。 根据结构化定理，任何结构化程序都可以用序列、条件和循环3种结构表示出来。 直接验证循环程序的正确性很麻烦，希望用序列和分支结构表示循环结构，以简化循环的正确性证明。,4.7 结构化程序的正确性证明引理,引理1: 已知函数f 和循环程序P：while p do g od，则 f while p do g od的充要条件是： 对所有xD(f

24、)，程序 P 终止，且f if p then g; f fi 证明： （1）必要性。假设fwhile p do g od，那么程序P终止是必然的，否则等式不成立。进一步，考察程序 if p then g；while p do g od fi显然，它和程序P是等价的，因而有， while p do g od = if p then g; while p do g od fi又已知f while p do g od，用f替换程序P得， f if p then g; f fi ok,4.7 结构化程序的正确性证明引理(续),(2) 充分性。 假设程序P终止，且 f if p then g; f fi

25、考察下面一组等价的程序（逐次使用if-then替换f得到的）：if p then g; f fiif p then g; if p then g; f fi fi if p then g; if p then g; ; (if p then g; f fi) fi fi fi由于程序P终止，则这一组程序定是有限的，谓词p在执行有限次以后一定取值为false，这时的if-then语句等价于恒等函数I，即最后的程序为 if p then g; if p then g; ; I fi fi fi显然，该程序等价于 while p do g od于是， f if p then g; f fi 【ok】

26、,4.7 结构化程序的正确性证明引理(续),引理2：已知函数 f 和程序P： do g until p，则f=do g until p的充分必要条件是：对所有的xD(f )，程序终止，且f g；if p then f; fi 引理3：已知函数f和程序P：do1 g while p do2 h od则f=do1 g while p do2 h od的充要条件是：对所有的xD(f )，程序终止，且 f =g；if p then h; f; fi 可知，循环程序的验证可以通过将循环化为递归的方法转换为终止性和由序列和条件组成的无循环程序的验证。,4.7 结构化程序的正确性证明定理1,定理1：已知预期

27、函数f和基本程序P，则f=P的充要条件是：对所有的xD(f )，程序终止，且对不同的基本程序，函数f分别满足下列关系： 情形a：对序列程序，即Pg; h，有 f= (x,y)|y=hg(x) 情形b：对if-then程序，即 P= if p then g fi，有 f= (x,y)|p(x)y=g(x)| p(x)y=x 情形c：对if-then-else程序，即 P= if p then g else h fi，有 f= (x,y)|(p(x)y=g(x)| p(x)y=h(x),4.7 结构化程序的正确性证明定理1(续),情形d：对while-do程序，即 P= while p do g

28、od, 有f= (x,y)|(p(x)y=f g(x)| p(x)y=x) 情形e：对do-until程序，即 P= do g until p od, 有f= (x,y)|(p g(x) y=g(x)| p g(x)y= f g(x) 情形f：对do-while-do程序，即 P= do1 g while p do2 h od, 有f= (x,y)|(p g(x) y= f h g(x)| p g(x)y= g(x) 证明略。,4.7 结构化程序的正确性证明代数方法1,一个终止的循环程序的正确性证明可以转化为序列和条件程序的正确性证明； 跟踪表和条件分离规则是序列和条件程序证明的基本方法；,4

29、.7 结构化程序的正确性证明代数方法2,一、跟踪表 例：有序列程序段：x := x+y; y:= x-y; x:= x-y; 解：假设变量x,y的初值为x0,y0, 有跟踪表：,X3 =x2-y2 =x1-(x1-y1) = y1 = y0 Y3 = y2 =x1-y1 =x0+y0y0 =x0,4.7 结构化程序的正确性证明代数方法3,二、分离规则 条件语句 if p then g else h fi的程序函数为 （pg | p h）为验证条件语句的正确性，需要比较预期函数 f 和上面条件规则是否相等。 1. 复合条件规则的化简 如果g，h是条件语句，就会引入复合条件规则，为比较复合条件规则

30、，需要首先对它进行化简。例如，,4.7 结构化程序的正确性证明代数方法4,(p1(q11r11|q12r12)|p2(q21r21|q22r22) 形式上展开为， p1q11 r11|p1q12r12|p2q21 r21|p2q22r22 一般情况下，这样展开可能是不成立的。例如，当p1为真，q11和q12为假，而p2为真，q21，q22有一个为真时，展开式有意义，而原复合规则无意义。 但是如果p1和p2是分离的，即p1 p2为假时，上述展开始终是成立的。,4.7 结构化程序的正确性证明代数方法5,如果一个条件规则的所有谓词都是分离的，称它为分离规则。例如， (x0(y0z:=x*y|y0z:

31、= -x*y|y0 y0 z:=x*y| x0 y0 z:= -x*y| x0 y0 z:= x*y),4.7 结构化程序的正确性证明代数方法6,2. 将条件规则化为分离规则 原因： 在化简和比较条件规则时，分离条件规则比一般的条件规则使用方便； 一般条件规则的顺序是不能交换的，而分离的条件规则是可以交换的。 因而，在讨论程序的正确性时，总是首先将条件规则化为分离规则,4.7 结构化程序的正确性证明代数方法7,2. 将条件规则化为分离规则 转换方法 对任意的条件规则 (p1r1|p2r2|p3r3|)可转化为 (p1r1|p1p2r2| p1 p2 p3r3|) 例如，条件规则 (x0z:=m

32、ax(x,y|y0z:=min(x,y)可以表示为， (x0z:=max(x,y)|x0 y0z:=min(x,y), 或 (x0(xyz:=x|x0(xyz:=y)|x0 xy z:=x|x0 x0 xy z:=y|x0 y0 xyz:=x),4.7 结构化程序的正确性证明代数方法8,3. 条件语句的正确性证明 假设某一条件语句的程序函数是分离规则(p1r1 | p2r2 | p3r3)预期函数是f(x)。为证明条件语句的正确性，需证明两点：（1）f(x)的定义域和分离规则的定义域相同 （2）利用分离规则的谓词将f(x)的定义域分解，并且有以下关系成立p1(x) r1(x) = f(x) p

33、2(x) r2(x) = f(x) p3(x) r3(x) = f(x) 另外，当f是以条件规则的形式给出时，如(q1s1|q2s2), 这时要证明，,4.7 结构化程序的正确性证明代数方法9,3. 条件语句的正确性证明(续) （1）两个分离规则的定义域相同的，即 p1(x) p2(x) p3(x) = q1(x) q2(x) （2）两个分离规则中的谓词成对合取后，相应的结果是相同的，即p1(x) q1(x) r1(x) = s1(x) p1(x) q2(x) r1(x) = s2(x) p3(x) q1(x) r3(x) = s1(x)p3(x) q2(x) r3(x) = s2(x),4.

34、7 结构化程序的正确性证明代数方法10,例1：已知预期函数f=(x:=-x)，程序P为if x0 then x:=x-2*x else x:=x+2*abs(x) fi证明P是正确的，即P=f(假设x是整数)。 证明: f 和 P的定义域均为整数，因而相同，又 P 的程序函数为 x0 x:=x-2*x |x0 (x:=x-2*x) = (x:=-x) x0 (x:=x+2*abs(x) =(x:=x+2*(-x)=(x:=-x)因而是正确的。,4.7 结构化程序的正确性证明代数方法11,例2：已知预期函数f是(x,y,a:=0,a*x+y,a) (x,y,a是整数，且x0)。程序P是while

35、 x 0 do x,y:=x-1,y+a od证明程序P是正确的。 证明：由于已知x0, 且每循环一次x减 1，因而通过有限次循环后，总有x=0, 即对任何程序是终止的。另，尚需证明：f=(p(x)y=f g(x)| p(x)y=x)对程序P来说，p(x)为x0，且已知x0, 因而p(x)=(x0), p(x)=(x=0)函数的复合y= f g(x)可用跟踪表确定：,4.7 结构化程序的正确性证明代数方法12,这样， x2 = 0 y2 = a0*(x0-1)+y0+a0 = a0*x0+y0 而当x0时，有 x,y,a:=0, a*x+y,a而当x=0时，y=x, 即 x,y,a:=x,y,a此时，预期函数为 x,y,a := 0, a*0+y,a := 0, y, a于是，两种情况下，预期函数均和条件规则中的相应的ri(x)相同，从而程序时正确的。,4.7 结构化程序的正确性证明代数方法13,例3：已知预期函数f为(xyx,y=x+|y|, x-|y| | xy x,y:=x,y else x,y:=y,x fi;if x-yx+y (或yy x,y:=x,y else x,y:=y,x fi;（续）,4.7 结构化程序的正确性证明代数方法14,证明(续)： 这是一个由条件语句组成的序列，它可以看成是复制语句