admin 管理员组文章数量: 1184232
2024年4月26日发(作者：getrealpath的是target目录)
２０１０年１２月 电 脑 学 习 第６期
将非结构化的流程图转化为结构化的
Ｎ—Ｓ流程图的通用算法框架
陈培军 王欣洁 李馨梅
摘 要：介绍了将非结构化流程图等价的转化为结构化的Ｎ－Ｓ流程图的通用算法框架。
关键词： 流程图：Ｎ—Ｓ流程图：非结构化流程图：等价变换
中图分类号：ＴＰ３１１ 文献标识码： Ａ 文章编号：１００２－２４２２（２０１０）０６－０１０３－０２
Ａ Ｇｅｎｅｒａｌ Ｅｑｕｉｖａｌｅｎｔ Ｃ：ｏｎｖｅｒｓｉｏｎ Ｆｒａｍｅｗｏｒｋ Ｆｏｒｍ Ｕｎｓｔｒｕｃｔｕｒｅｄ Ｆｌｏｗｃｈａｒｔ
ｔｏ Ｓｔｒｕｃｔｕｒｅｄ Ｎ－Ｓ Ｆｌｏｗｃｈａｒｔ
Ｃｈｅｎ Ｐｅｉｊｕｎ Ｗａｎｇ Ｘｉｎｊｉｅ Ｌｉ Ｘｉｎｍｅｉ
Ａｂｓｔｒａｃｔ：Ｗｅ ｄｅｓｉｇｎ ａ ｇｅｎｅｒａｌ ｅｑｕｉｖａｌｅｎｔ ｃｏｎｖｅｒｓｉｏｎ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｃｏｎｖｅｒｔｉｎｇ ｕｎｓｔｒｕｃｔｕｒｅｄ ｆｌｏｗｃｈａｒｔ ｉｎｔｏ ｓｔｒｕｃｔｕｒｅｄ Ｎ—Ｓ ｆｌｏｗ—
ｃｈａｒｔ．
Ｋｅｖ ｗ０ｒｄｓ：Ｆｌｏｗｃｈａｒｔ；Ｎ—Ｓ Ｄｉａｇｒａｍ；Ｕｎｓｔｒｕｃｔｕｒｅｄ Ｆｌｏｗｃｈａｒｔ；Ｐｒｏｇｒａｍ Ｅｑｕｉｖａｌｅｎｃｅ
１通用转换框架
（１）将每一步的具体的计算过程抽象、简化，并用不同
的编号表示不同的过程，简化的传统流程图如图１所示。
２（ｂ）需要先通过重复书写语句的等价变换变成类似图２（ａ）
的样子。
有了上面的理解，从而一般的框架可抽象为：找出当前
顶点个数最小的圈，依次对圈中每个顶点的度进行判断。如
果只有一个顶点的度大于等于３，并且该顶点的度等于４，则
为图２中（ａ）中的情形；如果只有两个顶点的度大于等于３，
并且这两个顶点的度都等于３，进一步若该圈在原有向图
中，也是一个有向圈，则为图２中（ｂ）的情形，否则为图２中
（ｃ）的情形。重复上述过程直到没有圈可以简化。
（４）将流程图分成一系列顺序执行的子块。不包含在任
意圈中的顶点自身为一个子块。对于任意的两个圈，如果这
两个圈有一个相同的顶点，则这两个圈中包含的所有顶点属
于同一个子块：对于上述子块，若包含满足下面性质的项
点一所有指向该顶点的有向边所在的圈所包含的顶点与所
有从该顶点出发的有向边所在的圈所包含的顶点的交集只
有这个顶点，则可在该顶点处将该子块分成两个子块，该顶
点包含在后面的子块里。经过上述过程，可将流程图分成一
（Ｃ）
系列顺序执行的子块。该实例可以分为三个子块，Ａ、Ｅ分别
为两个子块，其余的属于同一个子块。
（５）对每个包含多个圈的子块，通过逐分支遍历，动态
调整建立其Ｎ—Ｓ流程图。如果只有分支结构，即该子块中虽
然有圈，但没有有向圈，则总可以通过重复书写语句将其转
化为Ｎ—Ｓ流程图。如果最外层的条件为分支条件，则可以通
过重复书写语句得到该条件的每个分支，然后利用第（４）步
将每个分支分解为一系列顺序执行的子块。根据上面的分
析，设计以下抽象的算法：
图１简化的流程图
图２可进一步简化的
内容的示意图
（２）将流程图看成图论中的图。将流程图中的每个操
作，每个判断“是”，“否”均看成图的顶点，流向箭头看成有
向图中的有向边，则可将传统的流程图看成一个有向图。根
据需要，也可将其视为无向图，则循环结构中有圈、分支结构
或不同的出口最终汇总时，也会出现圈。
（３）将简单的循环结构或分支结构用一个编号表示，并
记录该编号的含义，从而进一步简化流程图。
如果流程图中出现图２中的三种情形，都可以简化。图
①如果该子块不包含圈，结束：否则，执行第②步。
②从子块的入口，顺着箭头的方向，逐分支遍历，找到第
一
２（ａ）和图２（ｃ）中可用一个编号表示虚线框住的部分，对图
个条件，判断条件是否包含于任意一个有向圈中。如果不
收稿日期：２０１０一ｌｌ—Ｏ１
陈培军、王欣洁太原科技大学讲师（山西，太原０３００２４）。
李馨梅东北农业大学理学院信息与计算科学专业２００９级本科生（黑龙江，哈尔滨１５００３０）。
包含于任何一个有向圈中，则采用重复书写语句的方法得到
（无条件执行条件Ｃ１的循环体）。结果见图５。
该条件的每一个分支，并将每一个分支分成一系列顺序执行
的子块，对每一个子块递归（转第①步）；如果包含于一个有
算法框架中所有的其他操作，都是为了将流程图转换为
类似图１的情形，核心的问题就是处理类似上面的问题。通
过上面的分析，可以体会到如何决定遍历的顺序，如何决定
条件类型，以及如何逐分支将当前的结果融入已有的框架，
向圈中，则转第③步。
③将该条件作为当前子块的最外层的循环条件，和该条
件位于同一个有向圈中的其他条件均作为分支条件。按一定
的顺序遍历所有分支，通过动态调整，得到结构化的循环体
和退出循环后的操作，从而得到相应的Ｎ—Ｓ流程图。
Ｉ函 ｌ亩
岫
（ｃ）
中
（ａ）
（ｄ） （ｅ）
（ｂ）
图３图１中所有的有向图
图３中的５个有向圈包含了子块所有的顶点，为全部可
能的遍历路径。从子块的入口，顺着箭头的方向，逐分支遍
历，找到第一个条件Ｃ１，且Ｃ１包含在有向圈内见图３（ａ）和
图３（ｂ），选择将Ｃ１作为外层循环条件。由图１可以看出退
出循环后，在子块内，什么也不做；继续找出条件Ｃｌ不成立
时的循环体。从包含Ｃ１的最简单的有向圈图３（ａ），通过重
复书写语句得到图４（ａ），其中画问号的地方有待于进一步
完善，下面继续遍历其他的路径将其不断完善。
继续找包含条件Ｃ１的当前最简单的路径，对该实例还
只有一个有向圈见图３（ｂ）包含Ｃ１，将该圈包含的内容融入
４（ａ），得到图４（ｂ），其中两个画问号的分支需要确定
从剩下的路径中选择一个简单的见图３（ｃ）。图３（ｃ）
表示当条件Ｃ３不成立时，无条件执行循环；当ｃ３成立时，
退出循环。引入辅助变量ｆｌａｇｌ，给其赋初值０，当ｆｌａｇ１＝＝０
时，执行循环；当ｆｌａｇｌ＝＝ｌ时，退出循环。当ｃ３不成立时，不
修改ｆｌａｇｌ的值，从而继续执行循环；当ｃ３成立时，修改
ｌｆａｇｌ的值为ｌ，从而退出循环。所以将图３（ｃ）进一步融入已
有的Ｎ—Ｓ流程图，得到图４（ｃ）。进一步融入图３（ｄ）（该图
表示当Ｃ３成立时，Ｃ４不成立时，Ｃ５不成立时，无条件执行
操作Ｈ、Ｃ－），得图４（ｄ）。
对最后的有向圈图３（ｅ），表示当Ｃ２和Ｃ３成立，Ｃ４不
成立，Ｃ５成立，退出内层的循环，执行完操作Ｊ后，无条件进
入条件ｃ１的循环体，对应图４（ｄ）中画问号的部分的内容。
引入辅助变量ｎａ异２，赋初值０，修改外层循环的条件为“当
Ｃ１不成立或ｆｌａｇ２＝＝ｌ”，为了使其他分支仍与原来等价，在
外层循环体内的开始部分，增加语句ｆｌａｇ２＝０；所以４（ｄ）中
画问号部分的操作为Ｊ；ｆｌａｇｌ＝ｌ（跳出内层循环）；ｆｌａｇ２＝ｌ
修正得到与已有框架相容的新的框架，最终得到Ｎ－Ｓ流程图
的过程。上述过程还有待于进一步抽象、细化、完善。要解决
上下文的语义识别、逻辑关系的理解及其等价变形。
Ｂ
Ｂ
Ｂ
Ｃ Ｃ
Ｃ
Ｄ
Ｄ
Ｄ
当Ｃ１不成立时 当Ｃｌ不成立时 当Ｃｌ不成立
’
Ｆ
＼ ＜
＼ ２／１
＼Ｃ
Ｇ
Ｇ
Ｇ
＼【：３ Ｋ
ｌｆａｚｌ＝Ｏ Ｋ ｌｆａｉｌ：ｏ
Ｂ
当ｆｌａｇｌ＝Ｏ Ｂ
当ｆｌａｇｌ－－０ Ｋ
Ｃ
、、Ｃ３ Ｃ ＼ｌ： Ｂ
Ｄ
Ｄ
＼ｃ ／ Ｃ
Ｄ
ｔ
Ｄ
ｌａｇ＝１ｌｌ
＇ｌ ￣ｌ－
（ｄ）
图４不断修正得到Ｎ—Ｓ流程图的中间过程
Ａ
Ｂ
Ｃ
上）
ｔｌａｇ２－０
当Ｃｌ小成立时或ｆｌａｇ２＝ｌ
ｌｆａｅ２＝Ｏ
Ｆ
——、 Ｃ２
Ｇ
ｆｌａｇｌ＝０
当ｆｌａｇｌ＝Ｏ
、
—＼
Ｃ４／
Ｎ
３
Ｋ
Ｉ ｉｙ－＇－－－￣ｓ Ｂ
Ｃ Ｉ Ｈ Ｃ
Ｄ ｌｆａｇｌ＝ｌ Ｈ Ｇ Ｄ
ｌｆａｇｌ＝ｌ ｆｌａｇ２＝ｌ Ｇ
Ｅ
图５最终的Ｎ—Ｓ流程图
（６）将各个层级的子块组装，将第（３）步中得到的各
个中间编号，根据相应的记录逐级展开还原，得到相应的Ｎ—
Ｓ流程图。对本例只有一个子块有圈，并且第一个条件即为
循环条件，且没有第（３）步中的简化，所以组装非常简单，最
终的结果如图５所示。
２结束语
结合具体的实例，给出了由非结构化的流程图转化为与
之等价的Ｎ—Ｓ流程图的宏观算法框架，仅是一种可行的方
法，可用于指导一般问题的转换。
参考文献
【１】邓德祥．结构化流程图的回顾与改进意见Ｌ玎．北京：北方工业大
学学报，１９９２，４（３）：８１—８７．
【２］张广泉．非结构化程序流程图及其等价变换Ｌ乃．重庆：重庆师范
学院学报（自然科学版），１９９３，１０（３）：２８—３１．
【３】孙靖民，粱迎春．机械优化设计【Ｍ】（第４版）．北京：机械工业出
版社，２ｏ０７：１３０－１３５．
版权声明：本文标题：将非结构化的流程图转化为结构化的N-S流程图的通用算法框架 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1714108570a666029.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论