1 引言

　　PLC即可編程邏輯控制器，是用來取代用于電機控制的順序繼電器電路的一種器件。梯形圖語言是PLC程序設計中最常用的編程語言，它是與繼電器線路類似的一種編程語言，梯形圖用不同的圖符表示不同的指令，用串、并聯等概念組織圖符的順序位置表述控制邏輯。梯形圖形象直觀，與電氣控制原理圖相呼應。采用梯形圖語言設計順序控制邏輯，具有方便直觀的優點，將控制系統的開關趨邏輯與狀態表示成梯形圖，有利于系統維護與快速故障診斷。由于電氣設計人員對繼電器控制較為熟悉，因此梯形圖編程語言得到了廣泛的應用。但是，梯形圖不能由計算機直接執行，需要將它轉換成計算機能夠識別的命令才能夠執行。在這個轉換的過程中，本文提出了二叉樹雙向鏈表的數據結構來表爾梯形圖功能元件及其拓撲關系，使后續的指令表序列的生成得到簡化。

　　2 梯形圖及數據結構

　　2.1梯形圖基本介紹

　　在梯形圖的圖形編輯界面中，用不同的圖符表示不同的指令。通常，梯形圖的組成中有功能單元、連接單元和空單元。功能單元，如常開指令、脈沖指令、輸出指令等;連接單元為并聯連接(下分支、右分支、左分支、左轉、右轉)、串聯連接和縱向連接。典型的梯形圖如圖1所示。采用動態增加梯形圖的行和列的方法，初始的顯示圖形的區域為2×n，程序，F始標志(start)和結束標志(End)各占1行，n是一個不超過編輯界面寬度的合適的初始值。梯形圖的編輯也有相應的規則和限制，添加這蝗限制和規則是為了簡化后續的數據結構和算法設計。

　　梯形圖編輯遵循的規則如下：(1)所有的功能單元都必須畫在水平線上，不能l畫在乖A分支f：，按照由左向右、由上到下的繪圖原則;(2)由幾個并聯回路組成的串聯同路中，包含功能單元最多的并聯網路放在最左邊，在由幾個串聯回路組成的并聯l川路中。包含功能單元最多的串聯回路放在最上邊;(3)不能將功能單元畫在輸fl{指令的右邊，即輸出指令只能放在一行的最右邊。一個簡單的梯形圖如圖1所示。

　　2.2二叉樹及二叉樹雙向鏈表

　　樹是一種數據結構，數據元素之間有明顯的層次關系。樹(Tree)是n(n≥o)個結點的有限集。在任意一棵非宅樹巾：(1)有且僅有一個特定的稱為根(Root)的結點;(2)當，n>l時，其余結點可分為m(m>o)個互小相交的有限集T1，T2，?，L，j￡巾每一個集合本身又是一棵樹，并且稱為根的子樹(Subtree)。

　　二叉樹是一種樹型結構，它的特點是每個結點至多只有二棵子樹(即二叉樹中不存在度大于2的結點)，并且二義樹的子樹有左右之分，其次序不能任意顛倒。

　　雙向鏈表可以克服單鏈表單阿陛的缺點，在艤向鏈表的結點中有兩個指針域，其一指向汽接后繼，另一指向直接前趨。二叉樹雙向鏈表中以每棵：叉樹作為一個鏈結，將一個二義樹森林以一定的順序連接起來，其中的每個鏈表結點需要保存對應的二叉樹根結點的地址信息。

1 引言

　　PLC即可編程邏輯控制器，是用來取代用于電機控制的順序繼電器電路的一種器件。梯形圖語言是PLC程序設計中最常用的編程語言，它是與繼電器線路類似的一種編程語言，梯形圖用不同的圖符表示不同的指令，用串、并聯等概念組織圖符的順序位置表述控制邏輯。梯形圖形象直觀，與電氣控制原理圖相呼應。采用梯形圖語言設計順序控制邏輯，具有方便直觀的優點，將控制系統的開關趨邏輯與狀態表示成梯形圖，有利于系統維護與快速故障診斷。由于電氣設計人員對繼電器控制較為熟悉，因此梯形圖編程語言得到了廣泛的應用。但是，梯形圖不能由計算機直接執行，需要將它轉換成計算機能夠識別的命令才能夠執行。在這個轉換的過程中，本文提出了二叉樹雙向鏈表的數據結構來表爾梯形圖功能元件及其拓撲關系，使后續的指令表序列的生成得到簡化。

　　2 梯形圖及數據結構

　　2.1梯形圖基本介紹

　　在梯形圖的圖形編輯界面中，用不同的圖符表示不同的指令。通常，梯形圖的組成中有功能單元、連接單元和空單元。功能單元，如常開指令、脈沖指令、輸出指令等;連接單元為并聯連接(下分支、右分支、左分支、左轉、右轉)、串聯連接和縱向連接。典型的梯形圖如圖1所示。采用動態增加梯形圖的行和列的方法，初始的顯示圖形的區域為2×n，程序，F始標志(start)和結束標志(End)各占1行，n是一個不超過編輯界面寬度的合適的初始值。梯形圖的編輯也有相應的規則和限制，添加這蝗限制和規則是為了簡化后續的數據結構和算法設計。

　　梯形圖編輯遵循的規則如下：(1)所有的功能單元都必須畫在水平線上，不能l畫在乖A分支f：，按照由左向右、由上到下的繪圖原則;(2)由幾個并聯回路組成的串聯同路中，包含功能單元最多的并聯網路放在最左邊，在由幾個串聯回路組成的并聯l川路中。包含功能單元最多的串聯回路放在最上邊;(3)不能將功能單元畫在輸fl{指令的右邊，即輸出指令只能放在一行的最右邊。一個簡單的梯形圖如圖1所示。

　　2.2二叉樹及二叉樹雙向鏈表

　　樹是一種數據結構，數據元素之間有明顯的層次關系。樹(Tree)是n(n≥o)個結點的有限集。在任意一棵非宅樹巾：(1)有且僅有一個特定的稱為根(Root)的結點;(2)當，n>l時，其余結點可分為m(m>o)個互小相交的有限集T1，T2，?，L，j￡巾每一個集合本身又是一棵樹，并且稱為根的子樹(Subtree)。

　　二叉樹是一種樹型結構，它的特點是每個結點至多只有二棵子樹(即二叉樹中不存在度大于2的結點)，并且二義樹的子樹有左右之分，其次序不能任意顛倒。

　　雙向鏈表可以克服單鏈表單阿陛的缺點，在艤向鏈表的結點中有兩個指針域，其一指向汽接后繼，另一指向直接前趨。二叉樹雙向鏈表中以每棵：叉樹作為一個鏈結，將一個二義樹森林以一定的順序連接起來，其中的每個鏈表結點需要保存對應的二叉樹根結點的地址信息。

3轉換算法的基本思想

　　3.1梯形圖向二叉樹的轉換算法

　　依據二叉樹的定義，結合PLC梯形圖的特點：以圖符表示操作指令，用圖符的位置表示串并聯的邏輯關系。由于我們采用的梯形同編輯環境是用每一個固定大小的單元格表示一個圖符，因而每一個蹦符抽象為二叉樹中的每一個結點。

　　具體的轉換思想描述如下：對梯形圖巾程序進行從左向右、從上到下的掃描，掃描過程中，識別每個圖符所代表的單元類型(功能單元或者連接單兀)，空單元不需處理，用每個起點表示二義樹的根結點(Root)，以左子樹表示串聯連接，右子樹表示并聯連接。

　　3.2二叉樹轉換成二叉樹雙向鏈表

　　梯形圖中圖元的執行足有同定執行順序的。通常，一棵二叉樹能夠表示一個子過程，一個大型的控制系統南多個子過程按一定的先后順序組織麗成。在梯形圖向二叉樹轉化后得到的足一個二義樹森林，它是一個松散的結構，并不能體現一個系統完整的功能，必須采用一種數據結構將這些二叉樹按照一定的次序組織起來，這里采用二叉樹雙向鏈表。

　　二叉樹雙向鏈表按照程序的執行順序將一棵棵二叉樹連接起來，每個鏈表結點代表一棵二叉樹。通常，我們的鏈表結點中存放了每個二叉樹根結點的信息，這樣通過對鏈表中的二義樹按照順序進行簡化和一次遍歷就可以實現梯形圖向指令表序列的轉化。

　　3.3二叉樹的簡化處理過程

　　由梯形圖得到的二叉樹雙向鏈表含有大最的連接結點的信息，在由二叉樹雙向鏈表向語句表轉化的時候，需l要過濾掉這些結點而形成只含有功能單元的.：義樹雙向鏈表，并兒能完整地描述梯形圖的邏輯功能信息。采用先序遞歸遍歷艤向鏈表中：叉樹結點的方法來完成功能一：義樹鏈表的牛成，在遍歷每一棵二義樹中圖元對象結點的時候，需要進行一系列判斷和處理，由此，我們需要設計一個簡化算法。具體的簡化算法實現見4.2節。

4轉換算法的實現

　　4.1主要的數據結構

　　4.1.1基本圖元數據結構

　　在整個算法的沒汁過程中，采用了面向對象的設計思想，首先將梯形圖中的每一個圖符抽象為一個圖兀對象，對于這些圖兀定義了一個基本圖元類：

　　class bascElcment

　　{public：

　　int type;//圖符單元的類型值

　　char name[20];//嘲符單，i的變譬名

　　char dec[20];//圖符單元的說明

　　int row;//圖符單元所在的行u|

　　int f01umn;//I刳符單元所在的列號

　　bascElcmcnt*lPft;///I：指針

　　bascElcmcnt*r|ght;//右指針

　　baseElcment’parent;//父指針

　　};

　　在梯形圖設計中涉及到的基本指令單元、計時指令單元、計數指令單元、讀寫指令單元、操作指令單了亡、比較指令單元、轉換指令單元等都由慕奉罔元類baseElement派生出來。

　　4.1.2二叉樹的數據結構

　　在梯形圖中，用每一個圖符來表示二叉樹巾的結點，以每個起始圖元對象作為單棵二叉樹的根(Root)。以左子樹表爪串聯連接，右子樹表示并聯連接。定義二叉樹鏈結類bTrecLink如下：

　　Class bTrccLink

　　{pubIic：

　　base卜1lement root;//根節點圖符

　　bTreeLink*next;//指向下一二叉樹

　　bTrccLink。prior;//指向lii『一二叉樹

　　public：

　　Insc九l，ef“);//左子樹插入

　　InsertRight();//右了.樹插入

　　DeleteEl咖ent();//刪除結點

　　}

　　4.1.3二叉樹雙向鏈袁的數據結構

　　梯形圖程序的完整信息采用二叉樹雙向鏈表來存儲，二叉樹艤向鏈表類的數據結構抽象如下：

　　class treeI.ist

　　{public：

　　bTrccLink*head;//雙向鏈表頭指針

　　bTreeLink*currcnt;//當前結點指針

　　bTrceLink*tail;//雙向鏈表尾指針

　　public：

　　InertbTrcc(bTreeI。ink*node，bTreeLink*current);//插入_二義樹鏈結

　　DIeletebTree(bTreeL.nk*node);//刪除二叉樹鏈結}

　　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++語言來實現，實現了數據和方法的良好封裝。同時，由于這種簡捷的結構，使后續的由梯形圖存儲結構到語句表的轉換算法的設計變得簡單，只需要對二叉樹雙向鏈表遍歷一次便叮以得到語句表序列。