PM-第二章 结构化程序设计

第二章结构化程序设计一节关于结构程序设计1.定义结构程序设计是避免使用GOTO语句的一种程序设计结构程序设计是自顶向下的程序设计是一种组织和编制程序的方法,利用它编制的乘隙易于理解和修改程序结构化的一个主要功能是似的正确性证明容易实现允许在设计过程中的每一步验证其正确性,即自动导致自我说明与自我捍卫的程序风格事态论如何将任何大规模的复杂的流程途程许转换成一种标准形式,使得它们用几种标准的控制结构,通过重复和嵌套来表示.结构程序设计的综合描述结构程序设计的综合描述:结构程序设计是一种进行程序设计的原则和方法，按照这种原则和方法设计出的程序的特点是：结构清晰、易阅读、易修改、易验证。结构程序设计语言：按照结构程序设计的要求设计出的程序设计语言称为结构程序设计语言。结构化程序：利用结构程序设计语言，或按照结构程序设计的思想编制的程序称为“结构化程序”。关于GOTO语句的问题2.关于GOTO语句的问题取消GOTO语句，即GOTO有害。理由：GOTO语句使程序的静态结构与它的动态执行之间有很大的差别。这样使程序难阅读、难查错。去掉GOTO语句可以直接从程序结构上反映出程序运行的过程，结构清晰、便于查错、易验证。保留GOTO语句GOTO语句使用起来比较灵活，而且有些情况下能够提高程序的效率，若一味地强调删除GOTO语句，有些情形会使程序过于复杂，增加不必要的计算量。折中派（Knuth）不加限制地使用GOTO语句，特别往回跳的GOTO语句，会使程序结构难以理解，这种情形应尽量避免使用GOTO语句。为提高效率，同时又不破坏程序的良好结构，有控制地使用GOTO语句是有必要的。结构程序设计结论结论：结构程序设计讨论的是一种程序设计的方法和风格。关注的焦点是得到的程序的结构的好坏，而有无GOTO语句并不是一个程序结构好坏的标志。避免和限制使用GOTO语句是得到结构化程序的一种手段，而不是我们的目的。2.2节结构化程序和结构定理一、结构化程序下面给结构化程序下一个精确的定义.流程图程序流程图程序的组成：函数节点、谓词节点和汇点。函数节点：只有一条入口线和一条出口线，一般与赋值语句相对应。谓词节点：有一条入口线和两条出口线，它不改变程序的数据项的值。汇点：有两条入口线和一条出口线，它不执行任何运算，只起到收集出口线的作用。fp1.流程图程序定义：一个用流程图的形式表示出来的程序，称为流程图程序。流程图程序举例流程图程序举例:pqgf正规程序2.正规程序定义：满足以下两个条件的流程图程序称为正规程序。条件：具有一条入口线和一条出口线，且对每个节点，都有一条从入口线到出口线的通路通过该节点。例：下面两个流程图程序不是正规程序pfgpf正规子程序3.正规子程序一个正规程序的某些部分仍然可以是正规程序,这些部分称为正规子程序.基本程序4.基本程序定义：一个正规程序，如果不包含多余一个节点的正规子程序，称为基本程序。即基本程序是一种不可再分解的正规程序。例：fgfghfgf七种重要的基本程序函数:序列:If-thenIf-then-elsefgfpfgpf七种重要的基本程序while-do:Do-until:Do-while-do:pfpgfpg复合程序和结构化程序5.复合程序若一个基本程序的函数节点用另外一个基本程序替换,所产生的正规程序称为复合程序。6.结构化程序由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。二、结构化定理1.程序函数已知一正规程序P，对于每个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯一的，那么所有的有序对的集合{（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)}七种基本程序的程序函数(续)[while-do]={(x,y)|k0((j:0<=j<k:p·fj(x))|¬p·fk(x)y=fk(x))}[do-until]={(x,y)|k>0(j:1<=j<k)(

¬p·fj(x)|p·fk(x)y=fk(x))}[dofwhilepdogod]={(x,y)|k0(

j:0<=j<k:p·f·(g·f)j(x))|¬p·f·(g·f)k(x)y=f·(g·f)k(x))}程序函数的计算1）对于序列程序可使用跟踪表的方法计算[p]

例：语句段：x:=x+y;y:=x-y;x:=x-y;

解：假设变量x,y的初值为x0,y0,…

有跟踪表：语句xyx:=x+yx1=x0+y0y1=y0y:=x-yy2=x1–y1x2=x1x:=x-yX3=x2-y2y3=y2X3=x2-y2=x1-(x1-y1)=y1=y0Y3=y2=x1-y1=x0+y0–y0=x0[P]={((x,y),(y,x)}程序函数的计算练习：计算下列语句序列的程序函数：

y:=a;y:=x*y+b;y:=x*y+c;y:=x*y+d程序函数的计算2)无循环程序的程序函数首先：构造有穷的执行树然后：对每条路径写出相应的表达式例：pfhrgq程序函数的计算执行树：pfhrqghrgg[p]={(x,y)|p(x)qf(x)y=gf(x)|p(x)

qf(x)rhf(x)y=ghf(x)|p(x)

qf(x)

rhf(x)y=hf(x)|p(x)…|…程序函数的计算3)循环程序的程序函数g1g3p1p2p3g2g4g51g12g3p1g213p2p3g23g42执行树：代换后的执行树：g1g3p1g2p2p3g5g4f1f3f1f2f2f3f1={(x,y)|y=f2g1(x)}F2={(x,y)|p1g3(x)y=f1g2g3(x)|p1g3(x)y=f3g3(x)}F3={(x,y)|p2(x)p3(x)y=f3g5(x)|p2(x)p3(x)y=x|

p2(x)y=f2g4(x)}程序的函数等价1.程序的函数等价如果程序P1和程序P2有相同的程序函数，称它们是函数等价的，或简称是等价的。结构化定理2.结构化定理定理：任一正规程序都可以函数等价与一个由基集合{序列，if-then-else，while-do}产生的结构化程序。结构化定理-证明证明：考察任一正规程序:

首先，从程序的入口处开始给程序的函数节点和谓词节点编号。编号为1，2，3，…，n（若入口处是汇点，那么宴会点的出口线继续考察，直到找到第一个函数节点或谓词节点）。同时将每一个函数节点及谓词节点的出口线用它后面的节点的编号进行编号。如果它后面没有函数节点或谓词节点，即该节点的出口线直接或通过汇点与程序的出口相连时，出口线的编号为0。peqh123400结构化定理--证明对每一个编号为i，出口线编号为j、k的谓词节点p，构造一个新的IF-THEN-ELSE程序gi，如图：h其次，对原程序种的每一个编号为i，出口线编号为J的函数节点h，构造一个新的序列程序gi，如图：ijhL:=jgi=pgi=pL:=jL:=kjik结构化定理--证明最后，利用已经得到的一些gi（I=1,2,3,…,n），按下图形式构造一个while-do循环。这个循环体是一个对L从1到n进行测试的嵌套的IF-THEN-ELSE程序（最内层的I表示恒等函数）：L:=1L>0L=1?g1L=2?g2L=n-1?gn-1L=n?gn•••I•••F=结构化定理--证明结论:显然,上面程序的功能和原程序的功能是相同的,因而它和原程序是函数等价的。而且，该程序是由一个固定的基集合{序列，IF-THEN-ELSE，WHILE-DO}产生的结构化程序，从而定理得证。结构化定理举例例：考察如下的流程图程序：peqh123400第一步：编号，结果如上图。结构化定理举例第二步：重新构造函数节点和谓词节点eL:=0g2=g1=pL:=2L:=3g3=qL:=0L:=4hL:=1g4=结构化定理举例第三步：用IF-THEN-ELSE和WHILE-DO重新构造程序：L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0L:=4L=4?hL:=1I结构化定理举例第四步：化简：上面得到的结构化程序比较庞大，且效率不高，还可以进一步改进，消除一些多余的对L的测试和赋值。化简的基本思想：对于某些j>0，如果gj中不包含赋值语句L:=j，则可以用gj代替所有的赋值L:=j。这样代替后，由于j不再赋值给L，因而测试L=j可以从IF-THEN-ELSE结构中去掉。这种替换直到以下情况出现为止：除了L:=0以外，所有给L赋值的语句均被消除；每个余下的gi’中都包含由相应赋值L:=I（gi’是gi经过一些替换以后得到的复合程序）例：结构化定理转换的化简用g4代替所有的L:=4的赋值语句，并删除L=4的测试L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0hL:=1I结构化定理转换的化简（续）用当前的g3’替换L:=3的赋值语句，并删除L=3的测试L:=1L>0L=1?L=2?pL:=2eL:=0qL:=0hL:=1I结构化定理转换的化简（续）用g2’替换L:=2的赋值。L:=1L>0L=1?