1 引言

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

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

　　2.1梯形圖基本介紹

　　在梯形圖的圖形編輯界面中，用不同的圖符表示不同的指令。通常，梯形圖的組成中有功能單元、連接單元和空單元。功能單元，如常開(kāi)指令、脈沖指令、輸出指令等;連接單元為并聯(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è)不超過(guò)編輯界面寬度的合適的初始值。梯形圖的編輯也有相應(yīng)的規(guī)則和限制，添加這蝗限制和規(guī)則是為了簡(jiǎn)化后續(xù)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。

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

　　2.2二叉樹(shù)及二叉樹(shù)雙向鏈表

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

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

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

1 引言

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

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

　　2.1梯形圖基本介紹

　　在梯形圖的圖形編輯界面中，用不同的圖符表示不同的指令。通常，梯形圖的組成中有功能單元、連接單元和空單元。功能單元，如常開(kāi)指令、脈沖指令、輸出指令等;連接單元為并聯(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è)不超過(guò)編輯界面寬度的合適的初始值。梯形圖的編輯也有相應(yīng)的規(guī)則和限制，添加這蝗限制和規(guī)則是為了簡(jiǎn)化后續(xù)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。

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

　　2.2二叉樹(shù)及二叉樹(shù)雙向鏈表

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

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

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

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

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

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

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

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

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

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

　　3.3二叉樹(shù)的簡(jiǎn)化處理過(guò)程

　　由梯形圖得到的二叉樹(shù)雙向鏈表含有大最的連接結(jié)點(diǎn)的信息，在由二叉樹(shù)雙向鏈表向語(yǔ)句表轉(zhuǎn)化的時(shí)候，需l要過(guò)濾掉這些結(jié)點(diǎn)而形成只含有功能單元的.：義樹(shù)雙向鏈表，并兒能完整地描述梯形圖的邏輯功能信息。采用先序遞歸遍歷艤向鏈表中：叉樹(shù)結(jié)點(diǎn)的方法來(lái)完成功能一：義樹(shù)鏈表的牛成，在遍歷每一棵二義樹(shù)中圖元對(duì)象結(jié)點(diǎn)的時(shí)候，需要進(jìn)行一系列判斷和處理，由此，我們需要設(shè)計(jì)一個(gè)簡(jiǎn)化算法。具體的簡(jiǎn)化算法實(shí)現(xiàn)見(jià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è)算法的沒(méi)汁過(guò)程中，采用了面向?qū)ο蟮脑O(shè)計(jì)思想，首先將梯形圖中的每一個(gè)圖符抽象為一個(gè)圖兀對(duì)象，對(duì)于這些圖兀定義了一個(gè)基本圖元類(lèi)：

　　class bascElcment

　　{public：

　　int type;//圖符單元的類(lèi)型值

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

　　char dec[20];//圖符單元的說(shuō)明

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

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

　　bascElcmcnt*lPft;///I：指針

　　bascElcmcnt*r|ght;//右指針

　　baseElcment’parent;//父指針

　　};

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

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

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

　　Class bTrccLink

　　{pubIic：

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

　　bTreeLink*next;//指向下一二叉樹(shù)

　　bTrccLink。prior;//指向lii『一二叉樹(shù)

　　public：

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

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

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

　　}

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

　　梯形圖程序的完整信息采用二叉樹(shù)雙向鏈表來(lái)存儲(chǔ)，二叉樹(shù)艤向鏈表類(lèi)的數(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);//插入_二義樹(shù)鏈結(jié)

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

　　4.2二叉樹(shù)的簡(jiǎn)化算法

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

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

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

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

　　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。)//若右了.樹(shù)存在

　　p-1eft-right-p-right;//連接右子樹(shù)

　　brcak;//下分支連接單元簡(jiǎn)化處理

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

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

　　p-1eft—right—p—right;//連接右f樹(shù)

　　brcak;//右分支連接單元簡(jiǎn)化處理

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

　　))

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

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

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

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

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

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

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

6結(jié)束語(yǔ)

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