将非结构化的流程图转化为结构化的N-S流程图的通用算法框架

开篇：润墨网以专业的文秘视角，为您筛选了一篇将非结构化的流程图转化为结构化的N-S流程图的通用算法框架范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:介绍了将非结构化流程图等价的转化为结构化的n-s流程图的通用算法框架。

关键词: 流程图:N-S流程图:非结构化流程图:等价变换

中图分类号:TP311

文献标识码:A

文章编号:1002-2422(2010)06-0103-02

1　通用转换框架

(1)将每一步的具体的计算过程抽象、简化,并用不同的编号表示不同的过程,简化的传统流程图如图1所示。

(2)将流程图看成图论中的图。将流程图中的每个操作,每个判断“是”,“否”均看成图的顶点,流向箭头看成有向图中的有向边,则可将传统的流程图看成一个有向图。根据需要,也可将其视为无向图,则循环结构中有圈、分支结构或不同的出口最终汇总时,也会出现圈。

(3)将简单的循环结构或分支结构用一个编号表示,并记录该编号的含义,从而进一步简化流程图。

如果流程图中出现图2中的三种情形,都可以简化。图2(a)和图2(c)中可用一个编号表示虚线框住的部分,对图2(b)需要先通过重复书写语句的等价变换变成类似图2(a)的样子。

有了上面的理解,从而一般的框架可抽象为:找出当前顶点个数最小的圈,依次对圈中每个顶点的度进行判断。如果只有一个顶点的度大于等于3,并且该顶点的度等于4,则为图2中(a)中的情形;如果只有两个顶点的度大于等于3,并且这两个顶点的度都等于3,进一步若该圈在原有向图中,也是一个有向圈,则为图2中(b)的情形,否则为图2中(c)的情形。重复上述过程直到没有圈可以简化。

(4)将流程图分成一系列顺序执行的子块。不包含在任意圈中的顶点自身为一个子块。对于任意的两个圈,如果这两个圈有一个相同的顶点,则这两个圈中包含的所有顶点属于同一个子块;对于上述子块,若包含满足下面性质的顶点一所有指向该顶点的有向边所在的圈所包含的顶点与所有从该顶点出发的有向边所在的圈所包含的顶点的交集只有这个顶点,则可在该顶点处将该子块分成两个子块,该顶点包含在后面的子块里。经过上述过程,可将流程图分成一系列顺序执行的子块。该实例可以分为三个子块,A、E分别为两个子块,其余的属于同一个子块。

(5)对每个包含多个圈的子块,通过逐分支遍历。动态调整建立其N-S流程图。如果只有分支结构,即该子块中虽然有圈,但没有有向圈,则总可以通过重复书写语句将其转化为N-S流程图。如果最外层的条件为分支条件,则可以通过重复书写语句得到该条件的每个分支,然后利用第(4)步将每个分支分解为一系列顺序执行的子块。根据上面的分析,设计以下抽象的算法:

①如果该子块不包含圈,结束;否则,执行第②步。

⑦从子块的入口,顺着箭头的方向,逐分支遍历,找到第一个条件,判断条件是否包含于任意一个有向圈中。如果不包含于任何一个有向圈中,则采用重复书写语句的方法得到该条件的每一个分支,并将每一个分支分成一系列顺序执行的子块,对每一个子块递归(转第①步);如果包含于一个有向圈中,则转第⑤步。

③将该条件作为当前子块的最外层的循环条件,和该条件位于同一个有向圈中的其他条件均作为分支条件。按一定的顺序遍历所有分支,通过动态调整,得到结构化的循环体和退出循环后的操作,从而得到相应的N-S流程图。

图3中的5个有向圈包含了子块所有的顶点,为全部可能的遍历路径。从子块的入口,顺着箭头的方向,逐分支遍历,找到第一个条件C1,且C1包含在有向圈内见图3(a)和图3(b),选择将C1作为外层循环条件。由图1可以看出退出循环后,在子块内,什么也不做;继续找出条件C1不成立时的循环体。从包含C1的最简单的有向圈图3(a),通过重复书写语句得到图4(a),其中画问号的地方有待于进一步完善,下面继续遍历其他的路径将其不断完善。

继续找包含条件C1的当前最简单的路径,对该实例还只有一个有向圈见图3(b)包含c1,将该圈包含的内容融入4(a),得到圈4(b),其中两个画问号的分支需要确定。

从剩下的路径中选择一个简单的见图3(c)。图3(c)表示当条件C3不成立时,无条件执行循环;当c3成立时,退出循环。引入辅助变量flag1,给其赋初值O,当flag1=0时,执行循环;当flag1=1时,退出循环。当C3不成立时,不修改flag1的值,从而继续执行循环;当c3成立时。修改flag1的值为1,从而退出循环。所以将图3(c)进一步融入已有的N-S流程图,得到图4(c)。进一步融入图3(d)(该图表示当c3成立时,c4不成立时,C5不成立时,无条件执行操作H、G),得图4(d)。

对最后的有向圈图3(e),表示当C2和C3成立,C4不成立,C5成立,退出内层的循环,执行完操作J后,无条件进入条件C1的循环体,对应图4(d)中画问号的部分的内容。引入辅助变量flag2,赋初值O,修改外层循环的条件为“当c1不成立或flag2==1”,为了使其他分支仍与原来等价,在外层循环体内的开始部分,增加语句flag2=0;所以4(d)中画问号部分的操作为J;flag1=1(跳出内层循环);flag2=1(无条件执行条件c1的循环体)。结果见图5。

算法框架中所有的其他操作,都是为了将流程图转换为类似图1的情形,核心的问题就是处理类似上面的问题。通过上面的分析,可以体会到如何决定遍历的顺序,如何决定条件类型,以及如何逐分支将当前的结果融入已有的框架,修正得到与已有框架相容的新的框架,最终得到N-S流程图的过程。上述过程还有待于进一步抽象、细化、完善。要解决上下文的语义识别、逻辑关系的理解及其等价变形。图4不断修正得到N-S流程图的中间过程

(6)将各个层级的子块组装,将第(3)步中得到的各个中间编号,根据相应的记录逐级展开还原,得到相应的N-S流程图。对本例只有一个子块有圈,并且第一个条件即为循环条件,且没有第(3)步中的简化,所以组装非常简单,最终的结果如图5所示。

2　结束语

结合具体的实例,给出了由非结构化的流程图转化为与之等价的N-S流程图的宏观算法框架,仅是一种可行的方法,可用于指导一般问题的转换。

参考文献

[1]邓德祥.结构化流程图的回顾与改进意见[J].北京:北方工业大学学报,1992,4(3):81-87.

[2]张广泉.非结构化程序流程图及其等价变换[J].重庆:重庆师范学院学报(自然科学版),1993,10(3):28-31.

[3]孙靖民,梁迎春.机械优化设计[M](第4版).北京:机械工业出版社,2007:130-135.