1 引言

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

　　2 梯形圖及數(shù)據(jù)結(jié)構(gòu)

　　2.1梯形圖基本介紹

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

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

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

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

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

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

1 引言

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

　　2 梯形圖及數(shù)據(jù)結(jié)構(gòu)

　　2.1梯形圖基本介紹

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

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

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

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

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

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

3轉(zhuǎn)換算法的基本思想

　　3.1梯形圖向二叉樹的轉(zhuǎn)換算法

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

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

　　3.2二叉樹轉(zhuǎn)換成二叉樹雙向鏈表

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

　　二叉樹雙向鏈表按照程序的執(zhí)行順序?qū)⒁豢每枚鏄溥B接起來，每個鏈表結(jié)點(diǎn)代表一棵二叉樹。通常，我們的鏈表結(jié)點(diǎn)中存放了每個二叉樹根結(jié)點(diǎn)的信息，這樣通過對鏈表中的二義樹按照順序進(jìn)行簡化和一次遍歷就可以實(shí)現(xiàn)梯形圖向指令表序列的轉(zhuǎn)化。

　　3.3二叉樹的簡化處理過程

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

4轉(zhuǎn)換算法的實(shí)現(xiàn)

　　4.1主要的數(shù)據(jù)結(jié)構(gòu)

　　4.1.1基本圖元數(shù)據(jù)結(jié)構(gòu)

　　在整個算法的沒汁過程中，采用了面向?qū)ο蟮脑O(shè)計思想，首先將梯形圖中的每一個圖符抽象為一個圖兀對象，對于這些圖兀定義了一個基本圖元類：

　　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;//父指針

　　};

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

　　4.1.2二叉樹的數(shù)據(jù)結(jié)構(gòu)

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

　　Class bTrccLink

　　{pubIic：

　　base卜1lement root;//根節(jié)點(diǎn)圖符

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

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

　　public：

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

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

　　DeleteEl咖ent();//刪除結(jié)點(diǎn)

　　}

　　4.1.3二叉樹雙向鏈袁的數(shù)據(jù)結(jié)構(gòu)

　　梯形圖程序的完整信息采用二叉樹雙向鏈表來存儲，二叉樹艤向鏈表類的數(shù)據(jù)結(jié)構(gòu)抽象如下：

　　class treeI.ist

　　{public：

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

　　bTreeLink*currcnt;//當(dāng)前結(jié)點(diǎn)指針

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

　　public：

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

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

　　4.2二叉樹的簡化算法

　　二叉樹中含有大量的冗余信息，在其向指令表轉(zhuǎn)化的過程中需要對je進(jìn)行簡化處理，采用對每棵二叉樹進(jìn)行一次先序遍歷，對每一個圖元結(jié)點(diǎn)對象進(jìn)行判斷處理。

　　二叉樹的簡化主要是過濾掉梯形網(wǎng)中多余的連接圖元，這里把主要對九種不同的圖元對象做簡化處理：(1)功能單元對象;(2)虛結(jié)點(diǎn)圖元對象;(3)連接單兀包含七種：下分支、右分支、左分支、左轉(zhuǎn)、右轉(zhuǎn)、串聯(lián)連接、和縱向連接。

　　對于不同的圖元類型進(jìn)行不同的處理。

　　這里，簡化函數(shù)中列出了三種類型的圖元的簡化處理算法，其他類型處理類似。

　　Predigcst(bTrccLink*p，int type)

　　{swiIch(type)

　　{case o：//圖元對象為功能單元

　　Break;//功能單元保留

　　casc l：//圖形對象為下分支

　　p_，pareIlt，left=p-lcft;//去除連接結(jié)點(diǎn)

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

　　p-1eft-right-p-right;//連接右子樹

　　brcak;//下分支連接單元簡化處理

　　case 2：//圖元對象為右分支

　　p-parenl_-right-曠lcft;//去除連接結(jié)點(diǎn)

　　p-1eft—right—p—right;//連接右f樹

　　brcak;//右分支連接單元簡化處理

　　case 8：{//縱向連接單元簡化處理)

　　))

5轉(zhuǎn)換實(shí)例

　　圖1所示的是一個具有復(fù)雜串并聯(lián)關(guān)系的梯形圖程序，其中包含的兩個邏輯關(guān)系式如下所示：

　　圖2為該梯形圖程序中的兩個邏輯關(guān)系式對應(yīng)的兩棵二叉樹，包含r梯形圖中描述的所有信息，其中掃描中重復(fù)的結(jié)點(diǎn)我們定義為虛結(jié)點(diǎn)。

　　上面得到的兩棵二叉樹是一個松散的結(jié)構(gòu)，我們采用了二叉樹雙向鏈表將其鏈接起來，使之完整地描述梯形圖的信息。圖3給出了一個含有N棵二叉樹結(jié)點(diǎn)的模型描述。

　　bTree o～bTree挖一1為梯形圖中所包含的二叉樹，一般來說，雙向鏈表結(jié)點(diǎn)中只需要保存二義樹根結(jié)點(diǎn)的地址即可。prior和next為雙向鏈表的前驅(qū)指針和后驅(qū)指針，其中prior指向前一棵二義樹的根結(jié)點(diǎn)，next指向下一棵二叉樹的根結(jié)點(diǎn)，head指針指向雙向鏈表的第一個結(jié)點(diǎn)，current為當(dāng)前指針，指向當(dāng)前結(jié)點(diǎn)，tail指針為尾指針，始終指向鏈表的最后一個結(jié)點(diǎn)。

　　在向指令表轉(zhuǎn)換之前，我們對每一棵=義樹結(jié)點(diǎn)進(jìn)行了簡化處理，采用4.2節(jié)描述的簡化算法，得到如下的精簡結(jié)構(gòu)，如圖4所示。

　　對上面得到的簡化二叉樹，我們只需要經(jīng)過一次后遍歷和一些判斷處理，就町以得到相應(yīng)的指令表序列。

6結(jié)束語

　　本文介紹的這種二叉樹雙向鏈表的數(shù)據(jù)結(jié)構(gòu)簡單、清晰、算法易于實(shí)現(xiàn)，與項(xiàng)日具體相結(jié)合，采用r面向?qū)ο蟮姆椒ú⒂肅++語言來實(shí)現(xiàn)，實(shí)現(xiàn)了數(shù)據(jù)和方法的良好封裝。同時，由于這種簡捷的結(jié)構(gòu)，使后續(xù)的由梯形圖存儲結(jié)構(gòu)到語句表的轉(zhuǎn)換算法的設(shè)計變得簡單，只需要對二叉樹雙向鏈表遍歷一次便叮以得到語句表序列。