[IT认证]哈尔滨工业大学软件工程课件.ppt

2019/4/19,DO WHILE ； ENDDO,REPEAT UNTIL ； ENDREP,- 重复型结构,2019/4/19,DO LOOP ； EXIT WHEN ENDLOOP,DO FOR ； ENDFOR,- 重复型结构,2019/4/19,- 多路选择结构,CASE OF ； WHEN SELECT ； WHEN SELECT ； DEFAULT: ； ENDCASE,2019/4/19,READ/WRITE TO ,- 输入/输出结构,2019/4/19,Enter a vector Set Maximum to the value of the first element in the vector DO for each second one to the last IF value of THEN element is greater than the Maximum value Set Maximum to value of the element ENDDO Print the Maximum value,2019/4/19,设某模块的功能是：读入任意长的 一段英文课文，将其分解为单字。然后 输出一个单词表，并指出每个单词在课 文中所出现的次数。,练习,请按下列给出的文字要求，用 PDL 描述其该模块的算法,2019/4/19, execute process a REPEAT UNTIL condition X8 execute process b IF condition X1 THEN BEGIN execute process f IF condition X6 THEN REPEAT UNTIL condition X7 execute process i ENDREP ELSE BEGIN execute process g execute process h END ENDIF END,练习,请将下列的 PDL 表示的某模块的过程性描述， 改为用：1、N-S 图 2、PAD 图表示,2019/4/19,ELSE CASE OF Xi WHEN condition X2 SELECT DO WHILE condition X5 execute process C ENDDO WHEN condition X3 SELECT process d WHEN condition X4 SELECT process e ENDCASE ENDIF ENDREP execute process j END,2019/4/19,第六章 程序编码,编码的目的: 是使用选定的程序设计 语言，把模块的过程性描述翻译为用该语 言书写的源程序（源代码）,模块的过程性描述 (不可执行的),源程序 (可执行的),编码,6.1 编码的目的,2019/4/19,Winberg 的程序实验结果,2019/4/19,结构化程序设计是一种设计程序的技术，它采用 自顶向下逐步细化的设计方法和单入口(Single entry) 单出口（Single exit）的控制结构。 这种控制结构包 括有： 顺序、选择和循环。,6.2 结构化程序设计 （Structured Programming）,2019/4/19, for(a=1,b=1;a=20) break; if (b%3=1) b+=3; continue; b-=5; ,单入口,单出口,2019/4/19, If (A.LT.B) goto 120 If (B.LT.C) goto 110 100 write(6,*) C goto 140 110 write(6,*) B goto 140 120 If(A.LT.C) goto 130 goto 100 130 write(6,*) A 140 continue,- 单入口多出口结构,2019/4/19,无节制地使用了GOTO语句所产生的程序流程,2019/4/19,一、结构化程序设计的原则,1、使用语言中的顺序、选择、重复等有限的基本控制结构表示程序 2、选用的控制结构只准许有一个入口和一个出口 3、程序语句组成容易识别的块（Block）,每块只有一个入口和一个 出口 4、复杂结构应该用基本控制结构进行组合嵌套来实现 5、严格控制GOTO语句,2019/4/19, F0=F(a); F1=F(b); if(F0*F10) X0=Xm; F0=Fm; else X1=Xm; finish: printf(“%dn”,Xm); ,2019/4/19,Begin,(F0*F1)=0,X0=a X1=b i=1,Xm=(X0+X1)/2 Fm=F(m),Q,(F0*Fm)0,X0=Xm,X1=Xm,F0=Fm,T,T,Xm,F,T,F,F,F0=F(a) F1=F(b),1,1,End,2,2,i=n,i,Q=abs(Fm)eps|abs(X1-X0)eps),2019/4/19, F0=F(a); F1=F(b); if(F0*F10) X0=Xm; F0=Fm; else X1=Xm; printf(“%dn”,Xm); ,2019/4/19, F0=F(a); F1=F(b); if(F0*F10) X0=Xm; F0=Fm; else X1=Xm; i+; printf(“%dn”,Xm); ,2019/4/19,二、程序设计自顶向下，逐步求精,1、程序设计是一个由粗到细的 “渐进” 的过程,2、程序设计不仅包括对控制结构的设计，也包括对数据结构的设计。 二者都要一步一步地细化。,采用逐步细化方法设计程序的步骤,2019/4/19,用逐步细化方法设计一个程序，其功能为 “从一组数中找出最大的数 ”,举例,第一步：列出问题的初步解,1：输入一组数,2：找出其中最大的数,3：输出最大的数,2019/4/19,第二步：分解主要问题,2.1：首先读入一个数并设其为最大的数,2.2：将该数逐次与其它数进行比较,2.3：若有大于该数的则将其保存,2019/4/19,第三步：确定数据结构,3.1：定义一数组 A,3.2：max=A(1),3.3：从A(2)至A(n)开始比较,3.4：若当前数大于max, 则令：max=A(I),2019/4/19,第四步：用PDL描述,Input array A Set Max=A(1) DO for I=2 to N IF MaxA(I) Set Max=A(I) ENDIF ENDDO Print Max,2019/4/19,练习,请用逐步细化方法设计一由下列描述 的程序结构,读入一段任意长度的英语课文，将其分解为单字，然后输出 一张单词表(list of words),并指出每种单词在课文中的出现次数。,2019/4/19,三、程序复杂性的度量,程序复杂性主要是指模块内部程序的复杂性。它 直接关系到软件开发费用的多少，开发周期的长短和 软件和软件内部潜伏错误的多少。同时它也是软件可 理解性的另一种度量。,2019/4/19,为了度量程序复杂性，要求复杂性度量应满足以下假设：,2019/4/19,如果设每行代码的出错率为每100行源程序中可能的 错误数目。例如，每行代码的出错率为 1%，也就是说， 每 100 行源程序中就可能有一个错误。,1、代码行度量法,：统计程序中的源代码的行数,较小的程序 -,1.3%1.8%/行,较大的程序 -,2.7%3.2%/行,2019/4/19,该方法是利用程序模块的程序图中环路的个数，来 计算程序的复杂性的。为此，该方法也称为环路复杂度 计算法。,2、McCabe 度量法,：利用程序的控制流来度量程序的复杂性,它是一种退化了的程序流程图。即:把程序流程图中每个处理符号都退化成一个结点，而原来流程图中的流程线，则变成连接不同结点的有向弧。,2019/4/19,(1)程序图符号,2019/4/19,2019/4/19,(2)从流程图导出程序图,2019/4/19,(3)环路复杂性的计算方法,V(G)=m-n+p,说明： V(G) 是有向图G中环路数；,m: 为图G中弧数；,n: 为图G中节点数；,p: 为图G中强连通分量个数；,V(G)=13-11+1=3,McCabe 的环路复 杂性度量值为 3,2019/4/19,练习,请将右侧给出的 程序流程图转换 为程序图并计算 其环路值。,2019/4/19,程序的环路复杂度则取决于程序控制流的复杂度，也就 是取决于程序结构的复杂程度。当程序内分支或循环个数增 加时，则相应地环域复杂度也随之增加。因此，它是对测试 难度的一种定量度量，也能对软件最终的可靠性给出某种预 测。,(4)、环路复杂度的用途,2019/4/19,练习,请用程序流程图描述下列问题的算法，再将其转换为 程序图并计算其环路值。,请定义一个数组a，要求找出数组中最大数和最小 数，并把最大数和 a0 中的数对调、最小数和a1 中的数对调。,2019/4/19,练习,请画出下列伪代码程序的流程图、程 序图并计算它的环路复杂度。,LOOP : Do While Z0 A=A+1 IF A10 THEN X=A ELSE Y=Z END IF IF Y0 THEN PRINT G E LSE PRINT K END IF STOP,2019/4/19,四、程序效率,程序效率是指程序的执行速度及程序占用 的存储空间。程序编码是最后提高运行速度和 节省存储机会，因此在此阶段不能不考虑程序 的效率。,2019/4/19,1、算法对效率的影响,源程序的效率与详细设计阶段确定的算法的效率 有着直接的关系。当我们把详细设计翻译并转换 成源代码之后，那么算法效率就会反映为程序的 执行速度和存储容量的要求,2019/4/19,（1）在编程序前，尽可能化简有关的算术表达式和逻辑表达式,（2）仔细检查算法中的嵌套的循环，尽可能将某些语句或表达 式移到循环外面,（3）尽量避免使用多维数组,（4）尽量避免使用指针和复杂的表,（5）不要混淆数据类型，避免在表达式中出现类型混杂,（6）尽量采用整数算术表达式和布尔表达式,（7）选用等效的高效率算法,转换过程中的指导原则是：,2019/4/19,举例,请设计求解下列问题的算法,2019/4/19,main() int i,j; float sum; sum=0.0; for(i=1;i=20;i+) for(j=1;j=3;j+) sum=sum+(i+1)*(i+1)*(j+2); printf(“sum=%dn”,sum); ,内循环次数,20X4=80,外循环次数,21,总循环次数,101,2019/4/19,main() int i,j; float sum; sum=0.0; for (j=1;j=3;j+) for (i=1;i=20;i+) sum=sum+(i+1)*(i+1)*(j+2); printf(“sum=%dn”,sum); ,应把变化范围大的循环变量放在内层。,内循环次数,3X21=63,外循环次数,4,总循环次数,67,2019/4/19,main() int i,j; float sum; sum=0.0; for (j=1;j=3;j+) for (i=1;i=20;i+) sum=sum+(i+1)*(i+1)*(j+2); printf(“sum=%dn”,sum); ,j+2 共计执行了,3X20=60次,2019/4/19,main() int i,j; float sum; sum=0.0; for (j=1;j=3;j+) k=j+2; for (i=1;i=20;i+) sum=sum+(i+1)*(i+1)*k; printf(“sum=%dn”,sum); ,j+2 共计执行了,3次,减少了57次,应尽量把与循环变量无关的运算移到循环外去。,2019/4/19,main() int i,j; float sum; sum=0.0; for (j=1;j=3;j+) k=j+2; for (i=1;i=20;i+) sum=sum+(i+1)*(i+1)*k; printf(“sum=%dn”,sum); ,i+1 共计执行了,60X60=120次,2019/4/19,main() int i,j; float sum; sum=0.0; for (j=1;j=3;j+) k=j+2; for (i=1;i=20;i+)