PLC梯形图的一种数据结构描述方法

　　4.2二叉树的简化算法

　　二叉树中含有大量的冗余信息，在其向指令表转化的过程中需要对je进行简化处理，采用对每棵二叉树进行一次先序遍历，对每一个图元结点对象进行判断处理。

　　二叉树的简化主要是过滤掉梯形网中多余的连接图元，这里把主要对九种不同的图元对象做简化处理：(1)功能单元对象;(2)虚结点图元对象;(3)连接单兀包含七种：下分支、右分支、左分支、左转、右转、串联连接、和纵向连接。

　　对于不同的图元类型进行不同的处理。

　　这里，简化函数中列出了三种类型的图元的简化处理算法，其他类型处理类似。

　　Predigcst(bTrccLink*p，int type)

　　{swiIch(type)

　　{case o：//图元对象为功能单元

　　Break;//功能单元保留

　　casc l：//图形对象为下分支

　　p_，pareIlt，left=p-lcft;//去除连接结点

　　if(p—right!-NUI.I。)//若右了.树存在

　　p-1eft-right-p-right;//连接右子树

　　brcak;//下分支连接单元简化处理

　　case 2：//图元对象为右分支

　　p-parenl_-right-旷lcft;//去除连接结点

　　p-1eft—right—p—right;//连接右f树

　　brcak;//右分支连接单元简化处理

　　case 8：{//纵向连接单元简化处理)

　　))

5转换实例

　　图1所示的是一个具有复杂串并联关系的梯形图程序，其中包含的两个逻辑关系式如下所示：

　　图2为该梯形图程序中的两个逻辑关系式对应的两棵二叉树，包含r梯形图中描述的所有信息，其中扫描中重复的结点我们定义为虚结点。

　　上面得到的两棵二叉树是一个松散的结构，我们采用了二叉树双向链表将其链接起来，使之完整地描述梯形图的信息。图3给出了一个含有N棵二叉树结点的模型描述。

　　bTree o～bTree挖一1为梯形图中所包含的二叉树，一般来说，双向链表结点中只需要保存二义树根结点的地址即可。prior和next为双向链表的前驱指针和后驱指针，其中prior指向前一棵二义树的根结点，next指向下一棵二叉树的根结点，head指针指向双向链表的第一个结点，current为当前指针，指向当前结点，tail指针为尾指针，始终指向链表的最后一个结点。

　　在向指令表转换之前，我们对每一棵=义树结点进行了简化处理，采用4.2节描述的简化算法，得到如下的精简结构，如图4所示。

　　对上面得到的简化二叉树，我们只需要经过一次后遍历和一些判断处理，就町以得到相应的指令表序列。

6结束语

　　本文介绍的这种二叉树双向链表的数据结构简单、清晰、算法易于实现，与项日具体相结合，采用r面向对象的方法并用C++语言来实现，实现了数据和方法的良好封装。同时，由于这种简捷的结构，使后续的由梯形图存储结构到语句表的转换算法的设计变得简单，只需要对二叉树双向链表遍历一次便叮以得到语句表序列。