《结构化程序设计课件》由会员分享，可在线阅读，更多相关《结构化程序设计课件（79页珍藏版）》请在金锄头文库上搜索。
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,七种重要的基本程序,函数:序列:I
6、f-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=xif-then-else = (x,y)| p(x)y=f(x)|p(x)y=g(x),二、结构化定理,while
8、-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=j0,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,第一步：编号，结果如上图。,结构化
9、定理举例,第二步：重新构造函数节点和谓词节点,e,L:=0,g2 =,g1 =,p,L:=2,L:=3,g3 =,q,L:=0,L:=4,h,L:=1,g4 =,结构化定理举例,第三步：用IF-THEN-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代替所有的赋
10、值L:=j。这样代替后，由于j不再赋值给L，因而测试L=j可以从IF-THEN-ELSE结构中去掉。这种替换直到以下情况出现为止： 除了L:=0以外，所有给L赋值的语句均被消除； 每个余下的gi中都包含由相应赋值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,
