结构程序设计 过程设计的工具 面向数据结构的设计方法 程序复杂程度的定量度量

Presentation on theme: "结构程序设计 过程设计的工具 面向数据结构的设计方法 程序复杂程度的定量度量"— Presentation transcript:

1 结构程序设计 过程设计的工具 面向数据结构的设计方法 程序复杂程度的定量度量
详细设计 结构程序设计 过程设计的工具 面向数据结构的设计方法 程序复杂程度的定量度量

2 课程回顾

3 详细设计的任务 关键任务：确定怎样具体地实现用户需要的软件系统，即设计出程序的“蓝图”。 要达到的目标： 要完成的工作： 保证软件的可靠性；
使将来编写出的程序可读性好、容易理解、容易测试、容易修改和维护，这是详细设计阶段最重要的目标。 要完成的工作： 确定软件各个组成部分内的算法以及各部分的内部数据组织 选定某种过程的表达形式来描述各种算法。 进行详细设计的评审

4 结构程序设计 结构程序设计的提出背景 （1）最早由E.W.Dijkstra于1965年提出，建议从高级语言中取消GO TO语句；
（2）1966年Bohm和Jacopini证明了，只用3种基本的控制结构就能实现任何单入口单出口的程序。这3种基本的控制结构是“顺序”、“选择”和“循环”，它们的流程图分别为如下(a)、(b) 、(c)； （3）1968年Dijkstra再次建议从一切高级语言中取消GO TO语句，只使用3种基本控制结构写程序。 （4）1972年IBM公司的Mills进一步提出，程序应该只有一个入口和一个出口，从而补充了结构程序设计的规则。

5 3种基本的控制结构

6 结构程序设计的经典定义 “如果一个程序的代码块仅仅通过顺序、选择和循环这3种基本控制结构进行连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。” 结构程序设计的更全面定义 “结构程序设计是尽可能少用GO TO语句的程序设计方法。最好仅在检测出错误时才使用GO TO语句，而且应该总是使用前向GO TO语句。”

7 其他常用的控制结构 （1）为了实际使用方便起见，常常还允许使用DO-UNTIL和DO-CASE两种控制结构，如下图 (a)、(b)所示。
（2）有时需要立即从循环(甚至嵌套的循环)中转移出来，如果允许使用LEAVE(或BREAK)结构，则不仅方便而且会使效率提高很多。 注：LEAVE或BREAK结构实质上是受限制的GO TO 语句，用于转移到循环结构后面的语句。

8 结构程序设计的分类 （1）经典的结构程序设计：如果只允许使用顺序、IF-THEN-ELSE型分支和DO-WHILE型循环这3种基本控制结构； （2）扩展的结构程序设计：如果除了上述3种基本控制结构之外，还允许使用DO-CASE型多分支结构和DO-UNTIL型循环结构； （3）修正的结构程序设计：如果再加上允许使用LEAVE(或BREAK)结构。

9 用过程工具来表达各个模块的实现算法，分为图形工具、表格工具和语言工具三类
过程设计的工具 １、程序流程图 程序流程图的标准符号

10 循环的标准符号　　　　　　　　注解的使用

11 多出口判断

12 程序流程图的主要优点 对控制流程的描绘很直观，便于初学者掌握。 程序流程图的主要缺点 (1) 诱使程序员过早地考虑程序的控制流程，而不去考虑程序的全局结构。 (2) 由于用箭头代表控制流，因此程序员可以不受约束地转移控制。 (3) 程序流程图不易表示数据结构。

13 ２、盒图(N-S图) 盒图的基本符号

14 盒图（N-S图）的特点 (1) 功能域明确。 (2) 不可能任意转移控制。 (3) 很容易确定局部和全程数据的作用域。 (4) 很容易表现嵌套关系，也可以表示模块的层次结构。 注：盒图没有箭头，因此不允许随意转移控制。

15 ３、PAD图 PAD是问题分析图(problem analysis diagram) ，1973年由日本日立公司发明。
它用二维树形结构的图来表示程序的控制流，将这种图翻译成程序代码比较容易。

16 PAD图的主要优点 (1) 使用PAD符号所设计的程序是结构化程序。 (2) PAD图所描绘的程序结构十分清晰。 (3) 用PAD图表现程序逻辑，易读、易懂、易记。 (4) 容易将PAD图转换成高级语言源程序，这种转换可用软件工具自动完成。 (5) 即可表示程序逻辑，也可描绘数据结构。 (6) PAD符号支持自顶向下、逐步求精的方法。 如下图所示：

17

18 4、判定表 组成 左上部列出所有条件，左下部是所有可能做的动作，右上部是表示各种条件组合的一个矩阵，右下部是和每种条件组合相对应的动作。
表示程序的静态逻辑 4、判定表 组成 左上部列出所有条件，左下部是所有可能做的动作，右上部是表示各种条件组合的一个矩阵，右下部是和每种条件组合相对应的动作。 优点 （1）能够清晰地表示复杂的条件组合与应做的动作之间的对应关系。 （2）能够简洁而又无歧义地描述处理规则。 缺点 不能同时清晰地表示顺序和重复等处理特性。

19 5、判定树 判定树是判定表的变种，也能清晰地表示复杂的条件组合与应做的动作之间的对应关系。 优点（相对于判定表）
形式简单，不需任何说明，一眼就可以看出其含义，因此易于掌握和使用。

20 用判定树表示计算行李费的算法

21 PDL是一种用于描述功能模块的算法设计和加工细节的语言。
６、过程设计语言 概念 （1）过程设计语言（PDL）也称为伪码。它是用正文形式表示数据和处理过程的设计工具。 （2） PDL是一种“混杂”语言 A、 PDL具有严格的关键字外部语法； B、PDL表示实际操作和条件的内部语法又是灵活自由的。 特点 关键字的固定语法。 (2) 自然语言的自由语法。 (3) 数据说明的手段。 (4) 模块定义和调用的技术。

22 优点 (1) 可以作为注释直接插在源程序中间。 (2) 可以使用普通的正文编辑程序或文字处理系统完成PDL的书写和编辑工作。 (3) 通过自动处理程序，可以将PDL生成程序代码。 缺点 不如图形工具形象直观，描述复杂的条件组合与动作间的对应关系时，不如判定表清晰简单。

23 面向数据结构的设计方法 在完成了软件结构设计之后，可以使用面向数据结构的方法来设计每个模块的处理过程。
Jackson方法和Warnier方法是最著名的两个面向数据结构的设计方法。

24 Jackson图 Jackson图的逻辑数据结构 由于数据元素彼此间的逻辑关系只有顺序、选择和重复3类，因此，逻辑数据结构也只有这3类。
1. 顺序结构 顺序结构的数据由一个或多个数据元素组成，每个元素按确定次序出现一次。 A由B、C、D 3个元素顺序组成

25 选择结构的数据包含两个或多个数据元素，每次使用这个数据时按一定条件从这些数据元素中选择一个。
2. 选择结构 选择结构的数据包含两个或多个数据元素，每次使用这个数据时按一定条件从这些数据元素中选择一个。 根据条件A是B或C或D中的某一个

26 3. 重复结构 重复结构的数据，根据使用时的条件由一个数据元素出现零次或多次构成。 A由B出现N次(N≥0)组成

27 Jackson图的优点： （1）便于表示层次结构，而且是对结构进行自顶向下分解的有力工具； （2）形象直观可读性好； （3）既能表示数据结构也能表示程序结构。 Jackson图的缺点： （1）选择条件或循环结束条件不能直接在图上表示出来。 （2）框间连线为斜线，不易在行式打印机上输出。

28 改进的Jackson图

29 Jackson图与层次方框图的比较 相同： Jackson图实质上是层次方框图的一种精化。 不同： （1）层次图中的一个方框通常代表一个模块；而Jackson图中的一个方框通常只代表几个语句。（2）层次图表现的是调用关系；而Jackson图表现的是组成关系，即一个方框中包括的操作仅仅由它下层框中的那些操作组成。

30 Jackson方法 基本步骤（５个） (1) 分析并确定输入数据和输出数据的逻辑结构。
(2) 找出输入数据结构和输出数据结构中有对应关系的数据单元。 注：对应关系是指有直接的因果关系，在程序中可以同时处理的数据单元(对于重复出现的数据单元必须重复的次序和次数都相同才可能有对应关系)。

31 (3) 用下述3条规则从描绘数据结构的Jackson图导出描绘程序结构的Jackson图：
第一，为每对有对应关系的数据单元，按照它们在数据结构图中的层次在程序结构图的相应层次画一个处理框(注意，如果这对数据单元在输入数据结构和输出数据结构中所处的层次不同，则取较低层次对应)； 第二，根据输入数据结构中剩余的每个数据单元所处的层次，在程序结构图的相应层次分别为它们画上对应的处理框； 第三，根据输出数据结构中剩余的每个数据单元所处的层次，在程序结构图的相应层次分别为它们画上对应的处理框。

32 (4) 列出所有操作和条件(包括分支条件和循环结束条件)，并且把它们分配到程序结构图的适当位置。 (5) 用伪码表示程序。

33 3种基本结构对应的伪码 顺序结构对应的伪码，其中‘seq’和‘end’是关键字： A seq B C D A end 重复结构对应的伪码，其中‘iter’、‘until’、‘while’和‘end’是关键字，cond是条件： A iter until(或while) cond A end

34 选择结构对应的伪码，其中‘select’、‘or’和‘end’是关键字，cond1、cond2和cond3分别是执行B、C或D的条件：
A select cond1 B A or cond2 C A or cond3 D A end

35 Jackson 方法举例 　　一个正文文件由若干个记录组成，每个记录是一个字符串。要求统计每个记录中空格字符的个数，以及文件中空格字符的总个数。要求的输出数据格式是，每复制一行输入字符串之后，另起一行印出这个字符串中的空格数，最后印出文件中空格的总个数。

36 （1）确定输入和输出数据的结构 表示输入输出数据结构的Jackson图

37 （2）分析确定在输入数据结构和输出数据结构中有对应关系的数据单元。
注：用虚线箭头把有对应关系的数据单元连接起来，以突出表明这种对应关系。 （3）从输入输出数据结构图导出程序结构图。 注：改进的Jackson图规定顺序执行的处理中不允许混有重复执行或选择执行的处理。 （4）列出所有操作和条件，并且把它们分配到程序结构图的适当位置。 （5）用伪码表示程序处理过程。

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

39 （１）停止 （２）打开文件 （３）关闭文件 （４）印出字符串 （５）印出空格数目 （６）印出空格总数 （７）sum:=sum+1 （８）totalsum:=totalsum+sum （９）读入字符串 （１０）sum:=0 （１１）totalsum:=0 （１２）pointer:=1 （１３）pointer:=pointer+1 I(1)文件结束　I(2)字符串结束 S(3)字符是空格 把操作和条件分配到程序结构图的适当位置

40 统计空格seq 打开文件 读入字符串 totalsum∶=0 程序体iter until文件结束 处理字符串seq …… 处理字符串end
　　　　　　　…… 　处理字符串end 程序体end 印总数seq 印出空格总数 印总数end 关闭文件 停止 统计空格end 处理字符串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

41 程序复杂程度的定量度量 定量度量程序复杂程度的方法的价值：
（１）把程序的复杂程度乘以适当常数即可估算出软件中错误的数量以及软件开发需要用的工作量； （２）定量度量的结果可以用来比较两个不同的设计或两个不同算法的优劣； （３）程序的定量的复杂程度可以作为模块规模的精确限度。 下面着重介绍使用得比较广泛的McCabe方法。

42 McCabe方法 1. 流图 McCabe方法根据程序控制流的复杂程度定量度量程序的复杂程度，这样度量出的结果称为程序的环形复杂度。
为了突出表示程序的控制流，通常使用流图(也称为程序图)描绘。 注：流图实质上是“退化了的”程序流程图，它仅仅描绘程序的控制流程，完全不表现对数据的具体操作以及分支或循环的具体条件

43 符号 结点：在流图中用圆表示，一个圆代表一条或多条语句。程序流程图中的一个顺序的处理框序列和一个菱形判定框，可以映射成流图中的一个结点。 边：在流图中的用箭头线表示，它和程序流程图中的箭头线类似，代表控制流。在流图中一条边必须终止于一个结点，即使这个结点并不代表任何语句(实际上相当于一个空语句)。 区域：由边和结点围成的面积，当计算区域数时应该包括图外部未被围起来的那个区域。

44 由PDL翻译成的流图

45 在条件中包含了一个或多个布尔运算符(逻辑OR，AND，NAND，NOR)。
当过程设计中包含复合条件时 在这种情况下，应该把复合条件分解为若干个简单条件，每个简单条件对应流图中一个结点。 包含条件的结点称为判定节点，从每个判定结点引出两条或多条边。 在条件中包含了一个或多个布尔运算符(逻辑OR，AND，NAND，NOR)。

46 由包含复合条件的PDL映射成的流图

47 2. 计算环形复杂度的方法 环形复杂度定量度量程序的逻辑复杂度。 用下述3种方法中的任何一种来计算环形复杂度。
(1) 流图中的区域数等于环形复杂度。 (2) 流图G的环形复杂度V(G)=E-N+2,其中，E是流图中边的条数，N是结点数。 (3) 流图G的环形复杂度V(G)=P+1，其中，P是流图中判定结点的数目。

48 3. 环形复杂度的用途 程序的环形复杂度取决于程序控制流的复杂程度，当程序内分支数或循环个数增加时，环形复杂度也随之增加，因此它是对测试难度的一种定量度量，也能对软件最终的可靠性给出某种预测。 McCabe研究大量程序后发现，环形复杂度高的程序往往是最困难、最容易出问题的程序。实践表明，模块规模以V(G)≤10为宜。

49 Halstead方法 Halstead方法是另一个著名的方法，它根据程序中运算符和操作数的总数来度量程序的复杂程度。
详细设计完成之后，可以知道程序中使用的不同运算符(包括关键字)的个数n1，以及不同操作数(变量和常数)的个数n2。Halstead给出预测程序长度的公式如下：H=n1 log2 n1+n2 log2 n2 多次验证都表明，预测的长度H与实际长度N非常接近。

50 系统设计小结