將非結(jié)構(gòu)化的流程圖轉(zhuǎn)化為結(jié)構(gòu)化的N-S流程圖的通用算法框架

摘要:介紹了將非結(jié)構(gòu)化流程圖等價(jià)的轉(zhuǎn)化為結(jié)構(gòu)化的N-S流程圖的通用算法框架。

關(guān)鍵詞: 流程圖:N-S流程圖:非結(jié)構(gòu)化流程圖:等價(jià)變換

中圖分類號(hào):TP311

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1002-2422(2010)06-0103-02

1 通用轉(zhuǎn)換框架

(1)將每一步的具體的計(jì)算過程抽象、簡化，并用不同的編號(hào)表示不同的過程，簡化的傳統(tǒng)流程圖如圖1所示。

(2)將流程圖看成圖論中的圖。將流程圖中的每個(gè)操作，每個(gè)判斷“是”，“否”均看成圖的頂點(diǎn)，流向箭頭看成有向圖中的有向邊，則可將傳統(tǒng)的流程圖看成一個(gè)有向圖。根據(jù)需要，也可將其視為無向圖，則循環(huán)結(jié)構(gòu)中有圈、分支結(jié)構(gòu)或不同的出口最終匯總時(shí)，也會(huì)出現(xiàn)圈。

(3)將簡單的循環(huán)結(jié)構(gòu)或分支結(jié)構(gòu)用一個(gè)編號(hào)表示，并記錄該編號(hào)的含義，從而進(jìn)一步簡化流程圖。

如果流程圖中出現(xiàn)圖2中的三種情形，都可以簡化。圖2(a)和圖2(c)中可用一個(gè)編號(hào)表示虛線框住的部分，對(duì)圖2(b)需要先通過重復(fù)書寫語句的等價(jià)變換變成類似圖2(a)的樣子。

有了上面的理解，從而一般的框架可抽象為:找出當(dāng)前頂點(diǎn)個(gè)數(shù)最小的圈，依次對(duì)圈中每個(gè)頂點(diǎn)的度進(jìn)行判斷。如果只有一個(gè)頂點(diǎn)的度大于等于3，并且該頂點(diǎn)的度等于4，則為圖2中(a)中的情形;如果只有兩個(gè)頂點(diǎn)的度大于等于3，并且這兩個(gè)頂點(diǎn)的度都等于3，進(jìn)一步若該圈在原有向圖中，也是一個(gè)有向圈，則為圖2中(b)的情形，否則為圖2中(c)的情形。重復(fù)上述過程直到?jīng)]有圈可以簡化。

(4)將流程圖分成一系列順序執(zhí)行的子塊。不包含在任意圈中的頂點(diǎn)自身為一個(gè)子塊。對(duì)于任意的兩個(gè)圈，如果這兩個(gè)圈有一個(gè)相同的頂點(diǎn)，則這兩個(gè)圈中包含的所有頂點(diǎn)屬于同一個(gè)子塊;對(duì)于上述子塊，若包含滿足下面性質(zhì)的頂點(diǎn)一所有指向該頂點(diǎn)的有向邊所在的圈所包含的頂點(diǎn)與所有從該頂點(diǎn)出發(fā)的有向邊所在的圈所包含的頂點(diǎn)的交集只有這個(gè)頂點(diǎn)，則可在該頂點(diǎn)處將該子塊分成兩個(gè)子塊，該頂點(diǎn)包含在后面的子塊里。經(jīng)過上述過程，可將流程圖分成一系列順序執(zhí)行的子塊。該實(shí)例可以分為三個(gè)子塊，A、E分別為兩個(gè)子塊，其余的屬于同一個(gè)子塊。

(5)對(duì)每個(gè)包含多個(gè)圈的子塊，通過逐分支遍歷。動(dòng)態(tài)調(diào)整建立其N-S流程圖。如果只有分支結(jié)構(gòu)，即該子塊中雖然有圈，但沒有有向圈，則總可以通過重復(fù)書寫語句將其轉(zhuǎn)化為N-S流程圖。如果最外層的條件為分支條件，則可以通過重復(fù)書寫語句得到該條件的每個(gè)分支，然后利用第(4)步將每個(gè)分支分解為一系列順序執(zhí)行的子塊。根據(jù)上面的分析，設(shè)計(jì)以下抽象的算法:

①如果該子塊不包含圈，結(jié)束;否則，執(zhí)行第②步。

⑦從子塊的入口，順著箭頭的方向，逐分支遍歷，找到第一個(gè)條件，判斷條件是否包含于任意一個(gè)有向圈中。如果不包含于任何一個(gè)有向圈中，則采用重復(fù)書寫語句的方法得到該條件的每一個(gè)分支，并將每一個(gè)分支分成一系列順序執(zhí)行的子塊，對(duì)每一個(gè)子塊遞歸(轉(zhuǎn)第①步);如果包含于一個(gè)有向圈中，則轉(zhuǎn)第⑤步。

③將該條件作為當(dāng)前子塊的最外層的循環(huán)條件，和該條件位于同一個(gè)有向圈中的其他條件均作為分支條件。按一定的順序遍歷所有分支，通過動(dòng)態(tài)調(diào)整，得到結(jié)構(gòu)化的循環(huán)體和退出循環(huán)后的操作，從而得到相應(yīng)的N-S流程圖。

圖3中的5個(gè)有向圈包含了子塊所有的頂點(diǎn)，為全部可能的遍歷路徑。從子塊的入口，順著箭頭的方向，逐分支遍歷，找到第一個(gè)條件C1，且C1包含在有向圈內(nèi)見圖3(a)和圖3(b)，選擇將C1作為外層循環(huán)條件。由圖1可以看出退出循環(huán)后，在子塊內(nèi)，什么也不做;繼續(xù)找出條件C1不成立時(shí)的循環(huán)體。從包含C1的最簡單的有向圈圖3(a)，通過重復(fù)書寫語句得到圖4(a)，其中畫問號(hào)的地方有待于進(jìn)一步完善，下面繼續(xù)遍歷其他的路徑將其不斷完善。

繼續(xù)找包含條件C1的當(dāng)前最簡單的路徑，對(duì)該實(shí)例還只有一個(gè)有向圈見圖3(b)包含c1，將該圈包含的內(nèi)容融入4(a)，得到圈4(b)，其中兩個(gè)畫問號(hào)的分支需要確定。

從剩下的路徑中選擇一個(gè)簡單的見圖3(c)。圖3(c)表示當(dāng)條件C3不成立時(shí)，無條件執(zhí)行循環(huán);當(dāng)c3成立時(shí)，退出循環(huán)。引入輔助變量flag1，給其賦初值O，當(dāng)flag1=0時(shí)，執(zhí)行循環(huán);當(dāng)flag1=1時(shí)，退出循環(huán)。當(dāng)C3不成立時(shí)，不修改flag1的值，從而繼續(xù)執(zhí)行循環(huán);當(dāng)c3成立時(shí)。修改flag1的值為1，從而退出循環(huán)。所以將圖3(c)進(jìn)一步融入已有的N-S流程圖，得到圖4(c)。進(jìn)一步融入圖3(d)(該圖表示當(dāng)c3成立時(shí)，c4不成立時(shí)，C5不成立時(shí)，無條件執(zhí)行操作H、G)，得圖4(d)。

對(duì)最后的有向圈圖3(e)，表示當(dāng)C2和C3成立，C4不成立，C5成立，退出內(nèi)層的循環(huán)，執(zhí)行完操作J后，無條件進(jìn)入條件C1的循環(huán)體，對(duì)應(yīng)圖4(d)中畫問號(hào)的部分的內(nèi)容。引入輔助變量flag2，賦初值O，修改外層循環(huán)的條件為“當(dāng)c1不成立或flag2==1”，為了使其他分支仍與原來等價(jià)，在外層循環(huán)體內(nèi)的開始部分，增加語句flag2=0;所以4(d)中畫問號(hào)部分的操作為J;flag1=1(跳出內(nèi)層循環(huán));flag2=1(無條件執(zhí)行條件c1的循環(huán)體)。結(jié)果見圖5。

算法框架中所有的其他操作，都是為了將流程圖轉(zhuǎn)換為類似圖1的情形，核心的問題就是處理類似上面的問題。通過上面的分析，可以體會(huì)到如何決定遍歷的順序，如何決定條件類型，以及如何逐分支將當(dāng)前的結(jié)果融入已有的框架，修正得到與已有框架相容的新的框架，最終得到N-S流程圖的過程。上述過程還有待于進(jìn)一步抽象、細(xì)化、完善。要解決上下文的語義識(shí)別、邏輯關(guān)系的理解及其等價(jià)變形。圖4不斷修正得到N-S流程圖的中間過程

(6)將各個(gè)層級(jí)的子塊組裝，將第(3)步中得到的各個(gè)中間編號(hào)，根據(jù)相應(yīng)的記錄逐級(jí)展開還原，得到相應(yīng)的N-S流程圖。對(duì)本例只有一個(gè)子塊有圈，并且第一個(gè)條件即為循環(huán)條件，且沒有第(3)步中的簡化，所以組裝非常簡單，最終的結(jié)果如圖5所示。

2 結(jié)束語

結(jié)合具體的實(shí)例，給出了由非結(jié)構(gòu)化的流程圖轉(zhuǎn)化為與之等價(jià)的N-S流程圖的宏觀算法框架，僅是一種可行的方法，可用于指導(dǎo)一般問題的轉(zhuǎn)換。

參考文獻(xiàn)

[1]鄧德祥.結(jié)構(gòu)化流程圖的回顧與改進(jìn)意見[J].北京:北方工業(yè)大學(xué)學(xué)報(bào)，1992，4(3):81-87.

[2]張廣泉.非結(jié)構(gòu)化程序流程圖及其等價(jià)變換[J].重慶:重慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版)，1993，10(3):28-31.

[3]孫靖民，梁迎春.機(jī)械優(yōu)化設(shè)計(jì)[M](第4版).北京:機(jī)械工業(yè)出版社，2007:130-135.