第6章 详细设计 Detailed Design 6.1 结构化程序设计 Structural Program Design 6.2 详细设计工具 Detailed Design Tools 6.3 面向数据结构的设计方法 Data Structrue-Oriented Design Method 6.４ 程序复杂程度的定量度量 Program Complexity Measure

第6章 详细设计 ( Detailed Design) 详细设计阶段的目标： 确定应该怎样具体地实现所要求的系统。 精确地描述整个目标系统，从而在编码阶段可以把这个描述翻译成用某种程序设计语言书写的程序。 6．１　结构程序设计(Structural Program Design ) Structrued Constructs 只有顺序、选择、循环这三种基本结构就能实现任何单入口单出口的程序。 B exp A T F 1）“当”型循环 2）直到型循环 顺序结构 (sequence construct) 循环结构 (repetition construct) 选择结构 (condition construct) 结构程序设计： 一种程序设计技术，它采用自顶向下逐步求精的设计方法和单入口单出口的控制结构。

其他常用的控制结构 结构程序设计（续） 经典的结构程序设计：顺序，选择，当型循环 扩展的结构程序设计：顺序，选择+多分支，当型循环+直到型循环 修正的结构程序设计：顺序，选择+多分支，当型循环+直到型循环，break结构 其他常用的控制结构

Non-Structrued Construct 怎样把一个非结构化程序转换成结构化程序 重复编码技术 C1 C2 A B C C1 C2 A B C Non-Structrued Construct Structrued Construct

设标志量技术 While (p) while(p&&!c) { s1; { s1; if(c) break; =>? s2; } flag=1; while(p&&flag) =>? { s1; if (c ) flag=0; s2; else

Non-Structrued Construct 状态变量法 Non-Structrued Construct Structrued Construct

6.2 详细设计工具 Detailed Design Tools 6.2.1 程序流程图 ( Program Flowcharts ) 6.2 详细设计工具 Detailed Design Tools 6.2.1 程序流程图 ( Program Flowcharts ) 6.2.2 盒图 ( Box Diagrams ) 6.2.3 PAD图 ( Problems Analysis Diagrams) 6.2.4 过程设计语言 ( Program Design language ) 6.2.5 判定表 ( Decision Table ) 6.2.6 判定树 ( Decision Tree )

6.2.1 程序流程图( Program Flowcharts ) 开始或停止 准备 选择 多分支选择 注释 预先定义的处理,子程序 循环下界 循环上界 处理 控制流 程序流程图中常用的符号

程序流程图虽然比较直观，灵活，并且比较容易掌握，但是它的随意性和灵活性却使它不可避免地存在着一些缺点： （1）由于程序流程图的特点，它本身并不是逐步求精的好工具。因为它使程序员容易过早地考虑程序的具体控制流程，而忽略了程序的全局结构； （2）程序流程图中用箭头代表控制流，这样使得程序员不受任何约束，可以完全不顾结构程序设计的精神，随意转移控制； （3）程序流程图在表示数据结构方面存在不足。

6.2.2 盒图（N-S图） ( Box Diagrams )

N-S图有以下一些特点： （1）功能域（即某一个特定控制结构的作用域）有明确的规定，并且可以很直观地从N-S图上看出来； （2）它的控制转移不能任意规定，必须遵守结构化程序设计的要求； （3）很容易确定局部数据和全局数据的作用域； （4）很容易表现嵌套关系，也可以表示模块的层次结构。

6.2.3 PAD图 ( Problems Analysis Diagrams)

PAD图提供的定义功能 P1 P2 P3 P4 C P5 def P6 P8 Until C3 UNTIL C2 P9 P10 即可以表示程序逻辑,也可以描绘数据结构. 支持自顶向下,逐步求精方法的使用.

6.2.4 过程设计语言(伪码 pseudocode) ( Program Design language ) PDL语言具有下述特点： （1）PDL虽然不是程序设计语言，但是它与高级程序设计语言非常类似，只要对PDL描述稍加变换就可变成源程序代码。因此，它是详细设计阶段很受欢迎的表达工具。 （2）用PDL写出的程序，既可以很抽象，又可以很具体。因此，容易实现自顶向下逐步求精的设计原则。 （3）PDL描述同自然语言很接近，易于理解。 （4）PDL描述可以直接作为注释插在源程序中，成为程序的内部文档。这对提高程序的可读性是非常有益的。 （5）PDL描述与程序结构相似，因此自动产生程序比较容易。 PDL的缺点是不如图形描述形象直观，因此人们常常将PDL描述与一种图形描述结合起来使用。

6.2.5 判定表( Decision Table ) 程序流程图、N-S图、PAD图或过程设计语言(PDL)都不易清楚的描述含有多重嵌套的条件选择。判定表可以清晰的表示复杂的条件组合与其对应的处理之间的关系。 例子 假设某航空公司规定，乘客可以免费托运重量不超过30公斤的行李。当行李重量 超过30公斤时，对头等舱的国内乘客超重部分每公斤收费 4 元，对其它舱的国内 乘客超重部分每公斤收费 6 元，对外国乘客超重部分每公斤收费比国内乘客多一 倍，对残疾乘客超重部分每公斤收费比正常乘客少一半。用判定表来表示与上述 每种条件组合相对应的动作。 国内乘客 T T T T F F F F 头 等 舱 T F T F T F T F 残疾乘客 F F T T F F T T 条件组合矩阵 所有条件 行李≤30kg T F F F F F F F F 免费 × (W-30)*2 × (W-30)*3 × (W-30)*4 × × (W-30)*6 × × 所有可能的 动作列表 与每种条件组合 所对应的动作表 (W-30)*8 × (W-30)*12 ×

6.2.6 判定树 ( Decision Tree ) 判定表不能表示循环，判定树叶子重复太多 残疾乘客 ---- (W-30)*2 头等舱 6.2.6 判定树 ( Decision Tree ) 残疾乘客 ---- (W-30)*2 头等舱 正常乘客 ---- (W-30)*4 国内乘客 残疾乘客 ---- (W-30)*3 其它舱 正常乘客 ---- (W-30)*6 行李重量 W>30 残疾乘客 ---- (W-30)*4 头等舱 正常乘客 ---- (W-30)*8 外国乘客 行李费 算 法 残疾乘客 ---- (W-30)*6 其它舱 正常乘客 ---- (W-30)*12 行李重量 W≤30 免费 判定表不能表示循环，判定树叶子重复太多

Data Structrue-Oriented Design Method (Jackson Methodology) 6.3 面向数据结构的设计方法 Data Structrue-Oriented Design Method 6.3.1 Jackson图 (Jackson Disgrams) 6.3.2 Jackson程序设计方法 (Jackson Methodology)

6.3.1 Jackson图 (Jackson Disgrams) Jackson图表示方法 Data Structure Notation (sequence construct) (condition construct) (repetition construct) Jackson图表示方法 Data Structure Notation

Jackson图的优点： （1）Jackson图不仅便于表示层次结构，而且也有利于对结构自顶向下分解； （2）Jackson图形象直观，可读性好； （3）Jackson图不仅能表示数据结构，也能表示程序结构（因为程序结构也可以由上述3种基本结构组成）。 Jackson图的缺点： 在选择结构和重复结构中，选择条件或循环结束条件不能直接在Jackson图中表示出来。这样就影响了图形的表达能力，也不利于直接把图翻译成程序。

Improved Jackson Diagrams 分支条件 Condition (condition construct) (sequence construct) (repetition construct) 改进的 Jackson图 Improved Jackson Diagrams

(Jackson Methodology) 例：高考后将考生的基本情况文件（简称考生基本情况文件）和考生高考成绩文件（简称考分文件）合并成一个新文件（简称考生新文件）。考生基本情况文件和考分文件都是由考生记录组成的。为简便起见，考生基本情况文件中的考生记录的内容包括：准考证号、姓名、通讯地址。考分文件中的考生记录的内容包括：准考证号和各门考分。合并后的考生新文件自然也是由考生记录组成，内容包括：准考证号、姓名、通讯地址和各门考分。 Jackson程序设计方法由五个步骤组成：

Input data structure Output data structure 第一步 数据结构表示 对要求解的问题进行分析，确定输入数据和输出数据的逻辑结构，并用Jackson图描述这些数据结构。 Input data structure Output data structure

第二步 找出输入数据结构和输出数据结构的对应关系 第二步 找出输入数据结构和输出数据结构的对应关系 找出输入数据结构和输出数据结构中有对应关系的数据单元，即有直接因果关系、在程序中可以同时处理的数据单元。需要注意的是，对于重复的数据单元，必须是重复的次序、次数都相同才有可能有对应关系。

第三步 确定程序结构图 根据下述三规则，由Jackson图导出相应的程序结构图： （1）为每对有对应关系的数据单元，按照它们在数据结构图中所处的层次，在程序结构图中的相应层次画一个处理框。如果这对数据单元在输入数据结构图和输出数据结构图中所处的层次不同，那么应以它们在输入数据结构图和输出数据结构图中层次较低的那个层次作为它们在程序结构图中的处理框所处的层次； （2）对于输入数据结构中剩余的数据单元，根据它们所处的层次，在程序结构图的相应层次为每个数据单元画上相应的处理框； （3）对于输出数据结构中剩余的数据单元，根据它们所处的层次，在程序结构图的相应层次为每个数据单元画上相应的处理框。

Resultant Program Structure 实际上，这一步是一个综合的过程：每对有对应关系的数据单元合画一个处理框，没有对应关系的数据单元则各画一个处理框。 Resultant Program Structure

第四步 列出并分配所有操作和条件 (Instruction List) 列出所有操作和条件（包括分支条件和循环结束条件），并把它们分配到程序结构图的适当位置。 操作:（1）停止； （2）打开两个输入文件； （3）建立输出文件。 （4）从输入文件中各读一条记录。 （5）生成一条新记录。 （6）将新记录写入输出文件。 （7）关闭全部文件。 条件：I（1）文件结束。

把操作和条件分配到程序结构图的适当位置

Pseudocode describing 第五步 用伪码表示程序 Pseudocode describing Jackson方法中使用的伪码与Jackson图是完全对应的。针对三种基本程序结构，有相对应的Jackson伪码。 （1）顺序结构 (sequence construct) A seq B C D A end

A iter until（或while） condition B A end （2）选择结构 （3）重复结构 A select condition1 B A or condition2 C A or condition3 D A end A iter until（或while） condition B A end (repetition construct) (condition construct)

用Jackson伪码描述的程序(Pseudocode programs)： 产生新文件 seq 打开两个输入文件 从输入文件中各读一条记录 分析考生记录iter until文件结束 处理考生记录 seq 产生准考证号 产生姓名 产生通讯地址

产生考分 生成一条新记录 将新记录写入输出文件 从输入文件中各读一条记录 处理考生记录 end 关闭全部文件 停止 产生新文件 end

［例］一个正文文件由若干个记录组成，每个记录是一个字符串。要求统计每个记录中空格字符的个数，以及文件中空格字符的总个数。要求的输出数据格式是，每复制一行输入字符串之后，另起一行印出这个字符串中的空格数，最后印出文件中空格的总个数。 对于这个简单例子而言，输入和输出数据的结构很容易确定。图6.12是用Jackson图描绘的输入输出数据结构。

图6.12 表示输入输出数据结构的Jackson图

图6.13 描绘统计空格程序结构的Jackson图

Jackson程序设计方法的第四步是列出所有操作和条件，并且把它们分配到程序结构图的适当位置。首先，列出统计空格个数需要的全部操作和条件。 经过简单分析不难把这些操作和条件分配到程序结构图的适当位置，结果为图6.14。 Jackson方法的最后一步是用伪码表示程序处理过程。因为Jackson使用的伪码和Jackson图之间存在简单的对应关系，所以从图6.14很容易得出下面的伪码：

图6.14 把操作和条件分配到程序结构图的适当位置

统计空格seq 打开文件 读入字符串 totalsum∶=0 程序体iter until文件结束 处理字符串seq 印字符串seq 印出字符串 印字符串end sum∶=0 pointer∶=1 分析字符串iter until字符串结束 分析字符select字符是空格

处理空格seq sum∶=sum+1 pointer∶=pointer+1 处理空格end 分析字符or字符不是空格 处理非空格seq 处理非空格end 分析字符end 分析字符串end 印空格数seq 印出空格数目 印空格数end

totalsum∶=totalsum+sum 读入字符串 处理字符串end 程序体end 印总数seq 印出空格总数 印总数end 关闭文件 停止 统计空格end

6 .4 程序复杂度的定量度量 Program Complexity Measure 利用软件设计的基本原理和概念可以定性的衡量软件模块的质量。但定量的度量 程序复杂程度的方法很有价值： 估算程序中软件故障的数量； 估算软件开发的工作量； 比较两个不同的设计或两个不同算法的优劣； 作为模块规模的精确上限。 程序定量度量方法是一个有待进一步研究的重要领域。 1）McCabe 方法 程序图 – 把程序流程图中每个处理符号都退化成一个点，原来连接不同处理符号 的箭头变成连接不同点的有向弧，这样得到的有向图就称为程序图。 程序图仅仅描述程序内部的控制流程，完全不表现对数据的具体操作以及分 支或循环的具体条件。 入口点：程序图中开始点后面的那个节点。 出口点：程序图中停止点前面的那个节点。 用McCabe方法度量得出的结果称为程序的环形复杂度。 程序的环形复杂度 = 强连通图中线性无关的有向环的个数。

6 .4 程序复杂度的定量度量(续) 2）环形复杂度的计算方法 在一个强连通的有向图中，线性无关环的个数由以下公式确定： 6 .4 程序复杂度的定量度量(续) 2）环形复杂度的计算方法 在一个强连通的有向图中，线性无关环的个数由以下公式确定： V(G) = m – n + p 其中： V(G) ---- 有向图 G 中的环数。 m ---- 有向图 G 中的弧数。 n ---- 有向图 G 中的节点数。 p ----有向图 G 中的分离部分的数目。（对于正常的程序，p = 1） 一般来说，由于程序图不是强连通的，要直接应用以上结论到程序图中还不行， 因此要对程序图进行扩展，从其出口点到入口点增画一条虚弧，则原程序图必然成为 强连通图。这样就可以应用以上公式来计算环形复杂度。 3） 环形复杂度的用途： 程序的环形复杂度与程序控制流的复杂程度，也就是与程序结构的复杂程度 有关。程序内分支数或循环个数增加时，环形复杂度就增加，因此它是对测试难 度的一种度量，也能对软件最终的可靠性给出某种预测。 McCabe 发现：环形复杂度高的程序往往是最困难、最容易出问题的程序。 实践表明： 模块规模以 V（ G）≤ 10 为宜。也就是说， V（ G）= 10 是模块 规模的一个更科学更精确的上限。

6 .4 程序复杂度的定量度量(续) V(G)=13-11+1=3 开始 a a K=0 L=0 TOTAL=0 b b 13 条弧 6 .4 程序复杂度的定量度量(续) a a K=0 L=0 TOTAL=0 b b 13 条弧 11 个节点 1 个独立部分 c c 输入A d Do while TOTAL ≤ 1000 and A≠ 0 d e j j e f A＞0 输出K,L, TOTAL i f g TOTAL=TOTAL+A i h g L=L+1 K=K+1 k 停止 h 输入A V(G)=13-11+1=3 k

6-3 画出下列伪码程序的程序流程图和盒图：START 习题 6-1 假设只有SEQUENCE和DO-WHILE两种控制结 　　构，怎样利用它们完成IF-THEN-ELSE操作? 6-2 假设只允许使用SEQUENCE和IF-THEN-ELSE 　　两种控制结构，怎样利用它们完成DO-WHIL 　　操作? 6-3 画出下列伪码程序的程序流程图和盒图：START IF p THEN WHILE q DO f

6-4 图6.18给出的程序流程图代表一个非结构化的程序，请问： END DO ELSE BLOCK g n END BLOCK END IF STOP 6-4 图6.18给出的程序流程图代表一个非结构化的程序，请问： (1) 为什么说它是非结构化的? (2) 设计一个等价的结构化程序。

图6.18 一个非结构化程序

(3) 在(2)题的设计中你使用附加的标志变量flag了吗?若没用，请再设计一个使用flag的程序；若用了，再设计一个不用flag的程序。 6-5 研究下面的伪码程序（见书131页）： 要求： (1) 画出程序流程图。 (2) 程序是结构化的吗?说明理由。 (3) 若程序是非结构化的，请设计一个等价的结构化程序并且画出程序流程图。 (4) 此程序的功能是什么?它完成预定功能有什么隐含的前提条件吗?

6-6 用Ashcroft_Manna技术可以将非结构化的程序转换为结构化程序，图6.19（见书132页）是一个转换的例子。 (2) 进一步简化图6.19(b)给出的结构化设计。 6-7 某交易所规定给经纪人的手续费计算方法如下：总手续费等于基本手续费加上与交易中的每股价格和股数有关的附加手续费。如果交易总金额少于1000元，则基本手续费为交易金额的8.4%；如果交易总金额在1000元到10000元之间，则基本手续费为交易金额的5%，再加34元；

如果交易总金额超过10000元，则基本手续费为交易金额的4%加上134元。当每股售价低于14元时，附加手续费为基本手续费的5%，除非买进、卖出的股数不是100的倍数，在这种情况下附加手续费为基本手续费的9%。当每股售价在14元到25元之间时，附加手续费为基本手续费的2%，除非交易的股数不是100的倍数，在这种情况下附加手续费为基本手续费的6%。当每股售价超过25元时，如果交易的股数零散(即，不是100的倍数)，则附加手续费为基本手续费的4%,否则附加手续费为基本手续费的1%。 要求：

(1) 用判定表表示手续费的计算方法； (2) 用判定树表示手续费的计算方法。 6-8 画出下列伪码程序（见书132页）的流图，计算它的环形复杂度。你觉得这个程序的逻辑有什么问题吗? 6-9 把统计空格程序的Jackson图(图6.13)改画为等价的程序流程图和盒图。 6-10 人机对话由操作员信息和系统信息交替组成。假设一段对话总是由操作员信息开始以系统信息结束，请用Jackson图描绘这样的人机对话过程。