1 引言

　　PLC即可編程邏輯控制器，是用來取代用于電機(jī)控制的順序繼電器電路的一種器件。梯形圖語言是PLC程序設(shè)計(jì)中最常用的編程語言，它是與繼電器線路類似的一種編程語言，梯形圖用不同的圖符表示不同的指令，用串、并聯(lián)等概念組織圖符的順序位置表述控制邏輯。梯形圖形象直觀，與電氣控制原理圖相呼應(yīng)。采用梯形圖語言設(shè)計(jì)順序控制邏輯，具有方便直觀的優(yōu)點(diǎn)，將控制系統(tǒng)的開關(guān)趨邏輯與狀態(tài)表示成梯形圖，有利于系統(tǒng)維護(hù)與快速故障診斷。由于電氣設(shè)計(jì)人員對(duì)繼電器控制較為熟悉，因此梯形圖編程語言得到了廣泛的應(yīng)用。但是，梯形圖不能由計(jì)算機(jī)直接執(zhí)行，需要將它轉(zhuǎn)換成計(jì)算機(jī)能夠識(shí)別的命令才能夠執(zhí)行。在這個(gè)轉(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所示。采用動(dòng)態(tài)增加梯形圖的行和列的方法，初始的顯示圖形的區(qū)域?yàn)?×n，程序，F(xiàn)始標(biāo)志(start)和結(jié)束標(biāo)志(End)各占1行，n是一個(gè)不超過編輯界面寬度的合適的初始值。梯形圖的編輯也有相應(yīng)的規(guī)則和限制，添加這蝗限制和規(guī)則是為了簡化后續(xù)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。

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

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

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

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

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

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

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

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

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

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

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

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

　　3.3二叉樹的簡化處理過程

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

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

　　class bascElcment

　　{public：

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

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

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

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

　　int f01umn;//I刳符單元所在的列號(hào)

　　bascElcmcnt*lPft;///I：指針

　　bascElcmcnt*r|ght;//右指針

　　baseElcment’parent;//父指針

　　};

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

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

　　在梯形圖中，用每一個(gè)圖符來表示二叉樹巾的結(jié)點(diǎn)，以每個(gè)起始圖元對(duì)象作為單棵二叉樹的根(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)

　　梯形圖程序的完整信息采用二叉樹雙向鏈表來存儲(chǔ)，二叉樹艤向鏈表類的數(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)化的過程中需要對(duì)je進(jìn)行簡化處理，采用對(duì)每棵二叉樹進(jìn)行一次先序遍歷，對(duì)每一個(gè)圖元結(jié)點(diǎn)對(duì)象進(jìn)行判斷處理。

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

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

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

　　Predigcst(bTrccLink*p，int type)

　　{swiIch(type)

　　{case o：//圖元對(duì)象為功能單元

　　Break;//功能單元保留

　　casc l：//圖形對(duì)象為下分支

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

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

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

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

　　case 2：//圖元對(duì)象為右分支

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

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

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

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

　　))

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

　　上面得到的兩棵二叉樹是一個(gè)松散的結(jié)構(gòu)，我們采用了二叉樹雙向鏈表將其鏈接起來，使之完整地描述梯形圖的信息。圖3給出了一個(gè)含有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指針指向雙向鏈表的第一個(gè)結(jié)點(diǎn)，current為當(dāng)前指針，指向當(dāng)前結(jié)點(diǎn)，tail指針為尾指針，始終指向鏈表的最后一個(gè)結(jié)點(diǎn)。

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

　　對(duì)上面得到的簡化二叉樹，我們只需要經(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ù)和方法的良好封裝。同時(shí)，由于這種簡捷的結(jié)構(gòu)，使后續(xù)的由梯形圖存儲(chǔ)結(jié)構(gòu)到語句表的轉(zhuǎn)換算法的設(shè)計(jì)變得簡單，只需要對(duì)二叉樹雙向鏈表遍歷一次便叮以得到語句表序列。