C語(yǔ)言實(shí)現(xiàn)有限狀態(tài)機(jī)
有限狀態(tài)機(jī)(finite state machine)是一個(gè)數(shù)學(xué)概念，如果把它運(yùn)用于程序中，可以發(fā)揮很大的作用。它是一種協(xié)議，用于有限數(shù)量的子程序(”狀態(tài)”)的發(fā)展變化。每個(gè)子程序進(jìn)行一些處理并選擇下一種狀態(tài)(通常取決于下一段輸入)。
有限狀態(tài)機(jī)(FSM)可以用作程序的控制結(jié)構(gòu)。FSM對(duì)于那些基于輸入的在幾個(gè)不同的可選動(dòng)作中進(jìn)行循環(huán)的程序尤其合適。投幣售貨機(jī)就是FSM的一個(gè)好例子。另外一個(gè)你可以想到的復(fù)雜的例子就是你正在用的東西，想到了嗎？沒(méi)錯(cuò)，就是操作系統(tǒng)。在投幣售貨機(jī)的例子中，輸入是硬幣，輸出是待售商品，售貨機(jī)有” 接受硬幣”，”選擇商品”，”發(fā)送商品”和”找零錢(qián)”等幾種狀態(tài)。
它的基本思路是用一張表保存所有可能的狀態(tài)，并列出進(jìn)入每個(gè)狀態(tài)時(shí)可能執(zhí)行的所有動(dòng)作，其中最后一個(gè)動(dòng)作就是計(jì)算(通常在當(dāng)前狀態(tài)和下一次輸入字符的基礎(chǔ)上，另外再經(jīng)過(guò)一次表查詢)下一個(gè)應(yīng)該進(jìn)入的狀態(tài)。你從一個(gè)”初始狀態(tài)” 開(kāi)始。在這一過(guò)程中，翻譯表可能告訴你進(jìn)入了一個(gè)錯(cuò)誤狀態(tài)，直到到達(dá)結(jié)束狀態(tài)。
在C語(yǔ)言中，有好幾種方法可以用來(lái)表達(dá)FSM，但它們絕大多數(shù)都是基于函數(shù)指針數(shù)組。一個(gè)函數(shù)指針數(shù)組可以像下面這樣聲明：
void (*state[MAX_STATES]) ();
如果知道了函數(shù)名，就可以像下面這樣對(duì)數(shù)組進(jìn)行初始化。
extern int a(),b(),c(),d();
int (*state[]) ()={a,b,c,c};
可以通過(guò)數(shù)組中的指針來(lái)調(diào)用函數(shù)：
(*state[i]) ();
所有函數(shù)必須接受同樣的參數(shù)，并返回同種類(lèi)型的返回值(除非你把數(shù)組元素做成一個(gè)聯(lián)合)。函數(shù)指針是很有趣的。注意，我們可以去掉指針形式，把上面的調(diào)用寫(xiě)成：
state[i] ();
甚至
(***state[i]) ();
這是一個(gè)在ANSI C中流行的不良方法：調(diào)用函數(shù)和通過(guò)指針調(diào)用函數(shù)(或任意層次的指針間接引用)可以使用同一種語(yǔ)法。
如果你想干得漂亮一點(diǎn)，可以讓狀態(tài)函數(shù)返回一個(gè)指向通用后續(xù)函數(shù)的指針，并把它轉(zhuǎn)換為適當(dāng)?shù)念?lèi)型。這樣，就不需要全局變量了。如果你不想搞得太花哨，可以使用一個(gè)switch語(yǔ)句作為一種簡(jiǎn)樸的狀態(tài)機(jī)，方法是賦值給控制變量并把switch語(yǔ)句放在循環(huán)內(nèi)部。關(guān)于FSM還有最后一點(diǎn)需要說(shuō)明：如果你的狀態(tài)函數(shù)看上去需要多個(gè)不同的參數(shù)，可以考慮使用一個(gè)參數(shù)計(jì)數(shù)器和一個(gè)字符串指針數(shù)組，就像main函數(shù)的參數(shù)一樣。我們熟悉的int argc,char *argv[]機(jī)制是非常普遍的，可以成功地應(yīng)用在你所定義的函數(shù)中