将非结构化的流程图转化为结构化的N-S流程图的通用算法框架
作者：陈培军 王欣洁 李馨梅
来源：《电脑学习》2010年第06期
        摘要:介绍了将非结构化流程图等价的转化为结构化的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流程图转换为ns图分别为两个子块,其余的属于同一个子块。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。