哈尔滨工业大学软件工程课件.ppt

2020 3 26 DOWHILE ENDDO REPEATUNTIL ENDREP 重复型结构 2020 3 26 DOLOOP EXITWHENENDLOOP DOFOR ENDFOR 重复型结构 2020 3 26 多路选择结构 CASEOF WHENSELECT WHENSELECT DEFAULT ENDCASE 2020 3 26 READ WRITETO 输入 输出结构 2020 3 26 EnteravectorSetMaximumtothevalueofthefirstelementinthevectorDOforeachsecondonetothelastIFvalueofTHENelementisgreaterthantheMaximumvalueSetMaximumtovalueoftheelementENDDOPrinttheMaximumvalue 2020 3 26 设某模块的功能是 读入任意长的一段英文课文 将其分解为单字 然后输出一个单词表 并指出每个单词在课文中所出现的次数 练习 请按下列给出的文字要求 用PDL描述其该模块的算法 2020 3 26 executeprocessaREPEATUNTILconditionX8executeprocessbIFconditionX1THENBEGINexecuteprocessfIFconditionX6THENREPEATUNTILconditionX7executeprocessiENDREPELSEBEGINexecuteprocessgexecuteprocesshENDENDIFEND 练习 请将下列的PDL表示的某模块的过程性描述 改为用 1 N S图2 PAD图表示 2020 3 26 ELSECASEOFXiWHENconditionX2SELECTDOWHILEconditionX5executeprocessCENDDOWHENconditionX3SELECTprocessdWHENconditionX4SELECTprocesseENDCASEENDIFENDREPexecuteprocessjEND 2020 3 26 第六章程序编码 编码的目的 是使用选定的程序设计语言 把模块的过程性描述翻译为用该语言书写的源程序 源代码 模块的过程性描述 不可执行的 源程序 可执行的 编码 6 1编码的目的 2020 3 26 Winberg的程序实验结果 2020 3 26 结构化程序设计是一种设计程序的技术 它采用自顶向下逐步细化的设计方法和单入口 Singleentry 单出口 Singleexit 的控制结构 这种控制结构包括有 顺序 选择和循环 6 2结构化程序设计 StructuredProgramming 2020 3 26 for a 1 b 1 a 20 break if b 3 1 b 3 continue b 5 单入口 单出口 2020 3 26 If A LT B goto120If B LT C goto110100write 6 Cgoto140110write 6 Bgoto140120If A LT C goto130goto100130write 6 A140continue 单入口多出口结构 2020 3 26 无节制地使用了GOTO语句所产生的程序流程 2020 3 26 一 结构化程序设计的原则 1 使用语言中的顺序 选择 重复等有限的基本控制结构表示程序2 选用的控制结构只准许有一个入口和一个出口3 程序语句组成容易识别的块 Block 每块只有一个入口和一个出口4 复杂结构应该用基本控制结构进行组合嵌套来实现5 严格控制GOTO语句 2020 3 26 F0 F a F1 F b if F0 F10 X0 Xm F0 Fm elseX1 Xm finish printf d n Xm 2020 3 26 Begin F0 F1 0 X0 aX1 bi 1 Xm X0 X1 2Fm 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 2020 3 26 F0 F a F1 F b if F0 F10 X0 Xm F0 Fm elseX1 Xm printf d n Xm 2020 3 26 F0 F a F1 F b if F0 F10 X0 Xm F0 Fm elseX1 Xm i printf d n Xm 2020 3 26 二 程序设计自顶向下 逐步求精 1 程序设计是一个由粗到细的 渐进 的过程 2 程序设计不仅包括对控制结构的设计 也包括对数据结构的设计 二者都要一步一步地细化 采用逐步细化方法设计程序的步骤 2020 3 26 用逐步细化方法设计一个程序 其功能为 从一组数中找出最大的数 举例 第一步 列出问题的初步解 1 输入一组数 2 找出其中最大的数 3 输出最大的数 2020 3 26 第二步 分解主要问题 2 1 首先读入一个数并设其为最大的数 2 2 将该数逐次与其它数进行比较 2 3 若有大于该数的则将其保存 2020 3 26 第三步 确定数据结构 3 1 定义一数组A 3 2 max A 1 3 3 从A 2 至A n 开始比较 3 4 若当前数大于max 则令 max A I 2020 3 26 第四步 用PDL描述 InputarrayASetMax A 1 DOforI 2toNIFMax A I SetMax A I ENDIFENDDOPrintMax 2020 3 26 练习 请用逐步细化方法设计一由下列描述的程序结构 读入一段任意长度的英语课文 将其分解为单字 然后输出一张单词表 listofwords 并指出每种单词在课文中的出现次数 2020 3 26 三 程序复杂性的度量 程序复杂性主要是指模块内部程序的复杂性 它直接关系到软件开发费用的多少 开发周期的长短和软件和软件内部潜伏错误的多少 同时它也是软件可理解性的另一种度量 2020 3 26 为了度量程序复杂性 要求复杂性度量应满足以下假设 2020 3 26 如果设每行代码的出错率为每100行源程序中可能的错误数目 例如 每行代码的出错率为1 也就是说 每100行源程序中就可能有一个错误 1 代码行度量法 统计程序中的源代码的行数 较小的程序 1 3 1 8 行 较大的程序 2 7 3 2 行 2020 3 26 该方法是利用程序模块的程序图中环路的个数 来计算程序的复杂性的 为此 该方法也称为环路复杂度计算法 2 McCabe度量法 利用程序的控制流来度量程序的复杂性 它是一种退化了的程序流程图 即 把程序流程图中每个处理符号都退化成一个结点 而原来流程图中的流程线 则变成连接不同结点的有向弧 2020 3 26 1 程序图符号 2020 3 26 2020 3 26 2 从流程图导出程序图 2020 3 26 3 环路复杂性的计算方法 V G m n p 说明 V G 是有向图G中环路数 m 为图G中弧数 n 为图G中节点数 p 为图G中强连通分量个数 V G 13 11 1 3 McCabe的环路复杂性度量值为3 2020 3 26 练习 请将右侧给出的程序流程图转换为程序图并计算其环路值 2020 3 26 程序的环路复杂度则取决于程序控制流的复杂度 也就是取决于程序结构的复杂程度 当程序内分支或循环个数增加时 则相应地环域复杂度也随之增加 因此 它是对测试难度的一种定量度量 也能对软件最终的可靠性给出某种预测 4 环路复杂度的用途 2020 3 26 练习 请用程序流程图描述下列问题的算法 再将其转换为程序图并计算其环路值 请定义一个数组a 要求找出数组中最大数和最小数 并把最大数和a 0 中的数对调 最小数和a 1 中的数对调 2020 3 26 练习 请画出下列伪代码程序的流程图 程序图并计算它的环路复杂度 LOOP DoWhileZ 0A A 1IFA 10THENX AELSEY ZENDIFIFY0THENPRINTGELSEPRINTKENDIFSTOP 2020 3 26 四 程序效率 程序效率是指程序的执行速度及程序占用的存储空间 程序编码是最后提高运行速度和节省存储机会 因此在此阶段不能不考虑程序的效率 2020 3 26 1 算法对效率的影响 源程序的效率与详细设计阶段确定的算法的效率有着直接的关系 当我们把详细设计翻译并转换成源代码之后 那么算法效率就会反映为程序的执行速度和存储容量的要求 2020 3 26 1 在编程序前 尽可能化简有关的算术表达式和逻辑表达式 2 仔细检查算法中的嵌套的循环 尽可能将某些语句或表达式移到循环外面 3 尽量避免使用多维数组 4 尽量避免使用指针和复杂的表 5 不要混淆数据类型 避免在表达式中出现类型混杂 6 尽量采用整数算术表达式和布尔表达式 7 选用等效的高效率算法 转换过程中的指导原则是 2020 3 26 举例 请设计求解下列问题的算法 2020 3 26 main inti j floatsum 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 d n sum 内循环次数 20X4 80 外循环次数 21 总循环次数 101 2020 3 26 main inti j floatsum 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 d n sum 应把变化范围大的循环变量放在内层 内循环次数 3X21 63 外循环次数 4 总循环次数 67 2020 3 26 main inti j floatsum 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 d n sum j 2共计执行了 3X20 60次 2020 3 26 main inti j floatsum 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 d n sum j 2共计执行了 3次 减少了57次 应尽量把与循环变量无关的运算移到循环外去 2020 3 26 main inti j floatsum 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 d n sum i 1共计执行了 60X60 120次 2020 3 26 main inti j floatsum sum 0 0 for j 1 j 3 j k j 2 for i 1 i 20 i m i 1