使用环形复杂度度量程序的复杂程度

第6章详细设计主要内容6.1结构程序设计6.2人机界面设计6.3过程设计的工具6.4面向数据结构的设计方法6.5程序复杂程度的定量度量目的与要求一般了解：Jackson程序设计方法；Warnier程序设计方法。基本掌握：使用环形复杂度度量程序的复杂程度，结构化程序设计方法的特点。重点掌握：详细设计的任务；用流程框图、NS图、PAD图、判定表和判定树以及PDL语言描述算法。重点与难点流程框图、NS图、PAD图、判定表和判定树以及PDL语言描述算法。环形复杂度的度量。目标：确定如何具体实现所要求的系统。不是具体编写程序，而是设计程序的“蓝图”。详细设计的结果决定最终程序代码的质量。E.W.Dijkstra最早提出结构程序设计：程序质量与程序中包含的Goto语句的数量成反比（1965）。1966，Bohm,Jacopini，证明了只用“顺序”、“选择”、“循环”控制结构就能实现任何单入口单出口程序。6.1结构程序设计理论上，最基本的控制结构只有两种：顺序、循环结构（选择结构可由其两者构造）。学界认识到，不是简单去掉Goto语句的问题，而是要创立一种新的程序设计方法。——结构化程序设计（IBM率先成功运用）。结构程序设计：一种设计程序的技术，它采用自顶向下逐步求精的设计方法和单入口单出口的控制结构。使用结构程序设计技术的好处：1）提高软件开发工程的成功率和生产率；2）系统有清晰的层次结构，容易阅读理解；3）单入口单出口的控制结构，容易诊断纠正；4）模块化可以使得软件可以重用；5）程序逻辑结构清晰，有利于程序正确性证明。经典的结构程序设计：只允许使用顺序、IF_THEN_ELSE选择和DO_WHILE循环；扩展的结构程序设计：除了三种基本控制结构，还使用DO_CASE和DO_UNTIL循环；修正的结构程序设计：除了三种基本控制结构和两种扩充结构，还使用BREAK等结构。1）顺序结构：相当于“A、B”2.三种基本控制结构AB(a)顺序结构2）选择结构相当于“IfexpthenAelseBendif”ABexp(b)选择结构3）循环结构：相当于“WhileexpdoA”A(c)循环结构exp1）多分支结构相当于“CaseIofI=1:C1;I=2:C2;I=3:C3;…;I=n:Cn”3.扩充两种控制结构CnC3C1C2(d)多分支结构I=?…2）UNTIL循环结构相当于“RepeatAUntilexp”A(e)UNTIL循环exp6.2人机界面设计6.2.1设计问题1.系统响应时间；2.用户帮助；3.出错信息处理；4.命令交互6.2.2设计过程6.2.3人机界面设计指南1.一般交互指南；2.信息显示指南；3.数据输入指南。6.3过程设计的工具6.3.1程序流程图程序流程图：是一种描述程序的控制结构流程和指令执行情况的有向图。历史悠久、使用广泛、直观描绘控制流程、便于初学者掌握。程序流程图的标准符号示例ASP检索程序流程图：开始加载Include文件定义记数变量、作物变量创建数据库链接对象、记录集对象打开数据库用客户提交的值对作物变量赋值SQL查询语句赋值通过记录集对象打开SQL语句设定的记录记录集末端？记数变量加1，输出记录字段值及图像转跳下一记录关闭数据库链接对象、记录集对象，并释放资源输出记录数和提示结束YN2）程序流程图中用箭头代表控制流，因此程序员不受任何约束，可以完全不顾结构程序设计的精神，随意转移控制。3）程序流程图不易表示数据结构。程序流程图的缺点：1）程序流程图本质上不是逐步求精的好工具，它诱使程序员过早地考虑程序的控制流程，而不去考虑程序的全局结构。6.3.2盒图（N-S图）ABC条件FTElseBThenACase条件Case1ACase2B…CasenN循环条件循环条件Do-While部分Do-Until部分Aa.顺序结构b.选择结构c.多分支结构d.当型循环结构e.直到型循环结构f.调用子程序A图6.4盒图的基本符号盒图的特点有：1）功能域明确，可以从盒图上一眼就看出来；2）不可能任意转移控制；3）很容易确定局部和全程数据的作用域；4）很容易表现嵌套关系，也可以表示模块的层次结构。FTBCDACase1E2F3G4HA：盒图例子示例N-S图的嵌套定义形式PAD（ProblemAnalysisDiagram）是问题分析图。日立公司发明和推广（1973）。6.3.3PAD图P1P2WHILECUNTILCPPP2P1CP1P2Pn…X=L1L2Lndefa.顺序结构b.当型循环结构c.直到型循环结构d.选择结构e.多分支结构f.语句标号g.定义图6.5PAD图的基本符号例子：P1P2UNTILC2P7P4P3Cdefa.初始的PAD图图6.6PAD图例子b.使用def符号细化处理框P2P5P2P8C1UNTILC2P9P10P6PAD图的优点：1）使用表示结构化控制结构的PAD符号所设计出来的程序必然是结构化程序；2）PAD图所描绘的程序结构十分清晰。图中最左面的竖线是程序的主线，即第一层结构。随着程序层次的增加，PAD图逐渐向右延伸，每增加一个层次，图形向右扩展一条竖线。PAD图中竖线的总条数就是程序的层次数；3）用PAD图表现程序，通俗易懂，程序从图中最左竖线上端的结点开始执行，自上而下，从左向右顺序执行，遍历所有结点；4）容易将PAD图转换成高级语言源程序，这种转换可以用软件工具自动完成；5）可用于表示程序逻辑，也可用于描绘数据结构；6）PAD图的符号支持自顶向下、逐步求精的方法。判定表由四部分组成：左上部列出所有条件左下部是所有可能做的动作右上部表示各种条件组合右下部是和每种条件组合相对应的动作6.3.4判定表123456789国内乘客TTTTFFFF头等舱TFTFTFTF残疾乘客FFTTFFTT行李重量W≤30TFFFFFFFF免费×(W-30)×2×(W-30)×3×(W-30)×4××(W-30)×6××(W-30)×8×(W-30)×12×某单位招聘考试，共考核三门课，录取方式是：总分250分（含）以上，且每门课都70分（含）以上录取；如果总分250分（含）以上，其中至少1门在60分（含）以上70分（不含）以下需复试该课程，复试后达到70分（含）以上录取；其他情况都不录取。作出录取过程的决策表。6.3.5判定树判定树是判定表的变种。行李重量W30行李重量W≤30国内乘客外国乘客头等舱其他舱头等舱其他舱残疾乘客正常乘客残疾乘客正常乘客残疾乘客正常乘客残疾乘客正常乘客（W-30）×2（W-30）×4（W-30）×3（W-30）×6（W-30）×4（W-30）×8（W-30）×6（W-30）×12免费图6.7用判定树表示计算行李费的算法行李费算法PDL也称为伪码。如：ifI0then执行订单数据输入模块else报告出错信息endif6.3.6过程设计语言（PDL）PDL的优点：1）可以作为注释直接插在源程序中间；2）可以使用普通的正文编辑程序或文字处理系统来完成PDL的书写和编辑工作；3）现在已经有一些自动处理程序可以自动地把PDL生成程序代码。PDL的缺点：不如图形工具形象直观。6.1结构程序设计6.2人机界面设计6.3过程设计的工具6.4面向数据结构的设计方法6.5程序复杂程度的定量度量6.4面向数据结构的设计方法1）顺序结构ABCD图6.8A由B、C、D三个元素顺序组成6.4.1Jackson图2）选择结构AB°C°D°图6.9根据条件A选择B、C、D中的某一个3）重复结构AB*图6.10A由B出现N次组成6.4.2改进的Jackson图ABCD图6.11改进的Jackson图ABºCºDºABº-ºAB*S(i)S(i)I(i)(a)(b)(c)(d)Jackson方法的目标是：得出对程序处理过程的详细描述。6.4.3Jackson方法Jackson结构程序设计方法由五个步骤组成：1）分析并确定输入数据和输出数据的逻辑结构，并用Jackson图描绘这些数据结构；2）找出输入数据结构和输出数据结构中有对应关系的数据单元；3）用三条规则从描绘数据结构的Jackson图导出描绘程序结构的Jackson图：A．为每对有对应关系的数据单元，按照它们在数据结构图中的层次在程序结构图的相应层次画一个处理框；B．根据输入数据结构中剩余的每个数据单元所处的层次，在程序结构图的相应层次分别为它们画上对应的处理框；C．根据输出数据结构中剩余的每个数据单元所处的层次，在程序结构图的相应层次分别为它们画上对应的处理框；4）列出所有操作和条件（包括分支条件和循环结束条件），并且把它们分配到程序结构图的适当位置；5）用伪码表示程序。顺序结构：AseqBCDAend与三种基本结构对应的伪码是：选择结构Aselectcond1BAorcond2CAorcond3DAend重复结构Aiteruntil(或while)condBAend例：一个正文文件由若干记录组成，每个记录是一个字符串。如：Record1：Howmanystagesarethereinthetraditionalsoftwaredevelopmentmodel?Record2：Afterenteringtheroom,walktothepersonsittingnearesttoyouandgreethim/herwitha“highfive”.Record3：Whatareencapsulatedintoanobject?Record4：Whatdiagramisthefollowingdiagram?Simplydescribethemeaningofit.要求：1）设计程序统计每个记录中空格字符的个数，输出数据的格式是，每读入一个记录（字符串）之后，另起一行打印出这个字符串及其空格数；2）最后打印出文件中空格的总个数。正文文件字符串*字符*空格º非空格ºIIS(a)输入数据结构输出表格表格体空格总数串信息*字符串空格数I输出表格表格体空格总数串信息*字符串空格数I正文文件字符串*字符*空格º非空格ºIIS图6.12表示输入/输出数据结构的Jackson图分析输入、输出数据结构，用Jackson图描绘，并找出两者对应的数据单元：统计空格程序体印总数处理字符串*分析字符串印空格数印字符串分析字符*处理空格º处理非空格ºIIS图6.13描绘统计空格程序结构的Jackson图导出描绘程序结构的Jackson图：注意：改进的Jackson图规定在顺序结构的元素中不能有重复出现或选择出现的元素，因此需要增加中间层次的处理框。（1）停止（2）打开文件（3）关闭文件（4）印出字符串（5）印出空格数目（6）印出空格总数（7）sum:=sum+1（8）totalsum:=totalsum+sum（9）读入字符串（10）sum:=0（11）totalsum:=0（12）pointer:=1（13）pointer:=pointer+1I(1)文件结束I(2)字符串结束S(3)字符是空格列出所有操作和条件：统计空格程序体印总数处理字符串*分析字符串印空格数印字符串分析字符*处理空格º处理非空格ºI(1)I(2)S(3)图6.14最终分配好操作和条件的Jackson图31119261012458971313伪代码表示练习6.1结构程序设计6.2人机界面设计6.3过程设计的工具6.4面向数据结构的设计方法6.5程序复杂程度的定量度量6.5程序复杂度的定量度量定量度量程序复杂度的作用：（1）可估算软件中错误的数量及软件开发工作量；（2）度量的结果可用来比较不同设计或不同算法的优劣；（3）程序的复杂度可作为模块规模的限度。1.流图“退化”的程序流程图，仅描绘程序的控制流程，不表现对数据的具体操作及循环、选择的条件。6.5.1McCabe方法一个圆代表一条或多条语句；一个顺序结构可以合并成一个结点；汇点也是结点；一个顺序处理框序列和一个判断框可映射成一个结点。复合条件：包含了一个或多个布尔运算符（OR、AND、NOR等）。应把复合条件分解为简单条件，每个条件对应一