一有限狀態機的實現方式
有限狀態機（Finite State Machine或者Finite State Automata)是軟件領域中一種重要的工具，很多東西的模型實際上就是有限狀態機。
FSM的實現方式：
1）switch/case或者if/else
這無意是最直觀的方式，使用一堆條件判斷，會編程的人都可以做到，對簡單小巧的狀態機來說最合適，但是毫無疑問，這樣的方式比較原始，對龐大的狀態機難以維護。
2）狀態表
維護一個二維狀態表，橫坐標表示當前狀態，縱坐標表示輸入，表中一個元素存儲下一個狀態和對應的操作。這一招易於維護，但是運行時間和存儲空間的代價較大。
3）使用State Pattern
使用State Pattern使得代碼的維護比switch/case方式稍好，性能上也不會有很多的影響，但是也不是100％完美。不過Robert C. Martin做了兩個自動產生FSM代碼的工具，for java和for C++各一個，在http://www.objectmentor.com/resources/index上有免費下載，這個工具的輸入是純文本的狀態機描述，自動產生符合State Pattern的代碼，這樣developer的工作只需要維護狀態機的文本描述，每必要冒引入bug的風險去維護code。
4）使用宏定義描述狀態機
一般來說，C++編程中應該避免使用#define，但是這主要是因為如果用宏來定義函數的話，很容易產生這樣那樣的問題，但是巧妙的使用,還是能夠產生奇妙的效果。MFC就是使用宏定義來實現大的架構的。
在實現FSM的時候，可以把一些繁瑣無比的if/else還有花括號的組合放在宏中，這樣，在代碼中可以3）中狀態機描述文本一樣寫，通過編譯器的預編譯處理產生1）一樣的效果，我見過產生C代碼的宏，如果要產生C++代碼，己軟MFC可以，那麼理論上也是可行的。
二狀態機的兩種寫法+實例
有限狀態機FSM思想廣泛應用於硬件控制電路設計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機)。它把復雜的控制邏輯分解成有限個穩定狀態，在每個狀態上判斷事件，變連續處理為離散數字處理，符合計算機的工作特點。同時，因為有限狀態機具有有限個狀態，所以可以在實際的工程上實現。但這並不意味著其只能進行有限次的處理，相反，有限狀態機是閉環系統，有限無窮，可以用有限的狀態，處理無窮的事務。
有限狀態機的工作原理如圖1所示，發生事件(event)後，根據當前狀態(cur_state)，決定執行的動作(action)，並設置下一個狀態號(nxt_state)。
-------------
||-------->執行動作action
發生事件event ----->| cur_state |
||-------->設置下一狀態號nxt_state
-------------
當前狀態
圖1有限狀態機工作原理
e0/a0
--->--
||
-------->----------
e0/a0 ||S0|-----
|-<------------| e1/a1
|| e2/a2V
--------------------
|S2|-----<-----|S1|
----------e2/a2----------
圖2一個有限狀態機實例
--------------------------------------------
當前狀態s0s1s2|事件
--------------------------------------------
a0/s0--a0/s0|e0
--------------------------------------------
a1/s1----|e1
--------------------------------------------
a2/s2a2/s2--|e2
--------------------------------------------
表1圖2狀態機實例的二維表格表示(動作/下一狀態)
圖2為一個狀態機實例的狀態轉移圖，它的含義是：
在s0狀態，如果發生e0事件，那麼就執行a0動作，並保持狀態不變；
如果發生e1事件，那麼就執行a1動作，並將狀態轉移到s1態；
如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
在s1狀態，如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
在s2狀態，如果發生e0事件，那麼就執行a0動作，並將狀態轉移到s0態；
有限狀態機不僅能夠用狀態轉移圖表示，還可以用二維的表格代表。一般將當前狀態號寫在橫行上，將事件寫在縱列上，如表1所示。其中“--”表示空(不執行動作，也不進行狀態轉移)，“an/sn”表示執行動作an,同時將下一狀態設置為sn。表1和圖2表示的含義是完全相同的。
觀察表1可知，狀態機可以用兩種方法實現：豎著寫(在狀態中判斷事件)和橫著寫(在事件中判斷狀態)。這兩種實現在本質上是完全等效的，但在實際操作中，效果卻截然不同。
==================================
豎著寫(在狀態中判斷事件)C代碼片段
cur_state = nxt_state;
switch(cur_state)
{//在當前狀態中判斷事件
case s0://在s0狀態
if(e0_event)
{ //如果發生e0事件，那麼就執行a0動作，並保持狀態不變；
執行a0動作;
//nxt_state = s0; //因為狀態號是自身，所以可以刪除此句，以提高運行速度。
}
else if(e1_event)
{//如果發生e1事件，那麼就執行a1動作，並將狀態轉移到s1態；
執行a1動作;
nxt_state = s1;
}
else if(e2_event)
{ //如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s1://在s1狀態
if(e2_event)
{//如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s2://在s2狀態
if(e0_event)
{ //如果發生e0事件，那麼就執行a0動作，並將狀態轉移到s0態；
執行a0動作;
nxt_state = s0;
}
}
==================================
橫著寫(在事件中判斷狀態)C代碼片段
==================================
//e0事件發生時，執行的函數
void e0_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state)
{
case s0://觀察表1，在e0事件發生時，s1處為空
case s2:
執行a0動作;
*nxt_state = s0;
}
}
//e1事件發生時，執行的函數
void e1_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state)
{
case s0://觀察表1，在e1事件發生時，s1和s2處為空
執行a1動作;
*nxt_state = s1;
}
}
//e2事件發生時，執行的函數
void e2_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state)
{
case s0://觀察表1，在e2事件發生時，s2處為空
case s1:
執行a2動作;
*nxt_state = s2;
}
}
上面橫豎兩種寫法的代碼片段，實現的功能完全相同，但是，橫著寫的效果明顯好於豎著寫的效果。理由如下：
1、豎著寫隱含了優先級排序(其實各個事件是同優先級的)，排在前面的事件判斷將毫無疑問地優先於排在後面的事件判斷。這種if/else if寫法上的限制將破壞事件間原有的關系。而橫著寫不存在此問題。
2、由於處在每個狀態時的事件數目不一致，而且事件發生的時間是隨機的，無法預先確定，導致豎著寫淪落為順序查詢方式，結構上的缺陷使得大量時間被浪費。對於橫著寫，在某個時間點，狀態是唯一確定的，在事件裡查找狀態只要使用switch語句，就能一步定位到相應的狀態，延遲時間可以預先准確估算。而且在事件發生時，調用事件函數，在函數裡查找唯一確定的狀態，並根據其執行動作和狀態轉移的思路清晰簡潔，效率高，富有美感。
總之，我個人認為，在軟件裡寫狀態機，使用橫著寫的方法比較妥帖。
豎著寫的方法也不是完全不能使用，在一些小項目裡，邏輯不太復雜，功能精簡，同時為了節約內存耗費，豎著寫的方法也不失為一種合適的選擇。
在FPGA類硬件設計中，以狀態為中心實現控制電路狀態機(豎著寫)似乎是唯一的選擇，因為硬件不太可能靠事件驅動(橫著寫)。不過，在FPGA裡有一個全局時鐘，在每次上升沿時進行狀態切換，使得豎著寫的效率並不低。雖然在硬件裡豎著寫也要使用IF/ELSIF這類查詢語句(用VHDL開發)，但他們映射到硬件上是組合邏輯，查詢只會引起門級延遲(ns量級)，而且硬件是真正並行工作的，這樣豎著寫在硬件裡就沒有負面影響。因此，在硬件設計裡，使用豎著寫的方式成為必然的選擇。這也是為什麼很多搞硬件的工程師在設計軟件狀態機時下意識地只使用豎著寫方式的原因，蓋思維定勢使然也。
TCP和PPP框架協議裡都使用了有限狀態機，這類軟件狀態機最好使用橫著寫的方式實現。以某TCP協議為例，見圖3，有三種類型的事件：上層下達的命令事件；下層到達的標志和數據的收包事件；超時定時器超時事件。
上層命令(open,close)事件
-----------------------------------
--------------------
|TCP|<----------超時事件timeout
--------------------
-----------------------------------
RST/SYN/FIN/ACK/DATA等收包事件
圖3三大類TCP狀態機事件
由圖3可知，此TCP協議棧采用橫著寫方式實現，有3種事件處理函數，上層命令處理函數(如tcp_close)；超時事件處理函數(tmr_slow)；下層收包事件處理函數(tcp_process)。值得一提的是，在收包事件函數裡，在各個狀態裡判斷RST/SYN/FIN/ACK/DATA等標志(這些標志類似於事件)，看起來象豎著寫方式，其實，如果把包頭和數據看成一個整體，那麼，RST/SYN/FIN/ACK/DATA等標志就不必被看成獨立的事件，而是屬於同一個收包事件裡的細節，這樣，就不會認為在狀態裡查找事件，而是總體上看，是在收包事件裡查找狀態(橫著寫)。
在PPP裡更是到處都能見到橫著寫的現象，有時間的話再細說。我個人感覺在實現PPP框架協議前必須了解橫豎兩種寫法，而且只有使用橫著寫的方式才能比較完美地實現PPP。
用C語言實現有限狀態機--讀《C專家編程》
有限狀態機(finite state machine)是一個數學概念，如果把它運用於程序中，可以發揮很大的作用。它是一種協議，用於有限數量的子程序("狀態")的發展變化。每個子程序進行一些處理並選擇下一種狀態(通常取決於下一段輸入)。
有限狀態機(FSM)可以用作程序的控制結構。FSM對於那些基於輸入的在幾個不同的可選動作中進行循環的程序尤其合適。投幣售貨機就是FSM的一個好例子。另外一個你可以想到的復雜的例子就是你正在用的東西，想到了嗎？沒錯，就是操作系統。在投幣售貨機的例子中，輸入是硬幣，輸出是待售商品，售貨機有"接受硬幣"，"選擇商品"，"發送商品"和"找零錢"等幾種狀態。
它的基本思路是用一張表保存所有可能的狀態，並列出進入每個狀態時可能執行的所有動作，其中最後一個動作就是計算(通常在當前狀態和下一次輸入字符的基礎上，另外再經過一次表查詢)下一個應該進入的狀態。你從一個"初始狀態"開始。在這一過程中，翻譯表可能告訴你進入了一個錯誤狀態，直到到達結束狀態。
在C語言中，有好幾種方法可以用來表達FSM，但它們絕大多數都是基於函數指針數組。一個函數指針數組可以像下面這樣聲明：
void (*state[MAX_STATES]) ();
如果知道了函數名，就可以像下面這樣對數組進行初始化。
extern int a(),b(),c(),d();
int (*state[]) ()={a,b,c,c};
可以通過數組中的指針來調用函數：
(*state[i]) ();
所有函數必須接受同樣的參數，並返回同種類型的返回值(除非你把數組元素做成一個聯合)。函數指針是很有趣的。注意，我們可以去掉指針形式，把上面的調用寫成：
state[i] ();
甚至
(******state[i]) ();
這是一個在ANSI C中流行的不良方法：調用函數和通過指針調用函數(或任意層次的指針間接引用)可以使用同一種語法。
如果你想干得漂亮一點，可以讓狀態函數返回一個指向通用後續函數的指針，並把它轉換為適當的類型。這樣，就不需要全局變量了。如果你不想搞得太花哨，可以使用一個switch語句作為一種簡樸的狀態機，方法是賦值給控制變量並把switch語句放在循環內部。關於FSM還有最後一點需要說明：如果你的狀態函數看上去需要多個不同的參數，可以考慮使用一個參數計數器和一個字符串指針數組，就像main函數的參數一樣。我們熟悉的int argc,char *argv[]機制是非常普遍的，可以成功地應用在你所定義的函數中。
實例：密碼鎖：以思維密碼校驗作為狀態機的例子，連續輸入2479就可以通過密碼測試。
代碼一：
#include
#include
#include
typedef enum
{
STATE0 = 0,
STATE1,
STATE2,
STATE3,
STATE4,
}STATE;
typedef enum
{
INPUT1 = '2',
INPUT2 = '4',
INPUT3 = '7',
INPUT4 = '9',
}INPUT;
int main()
{
char ch;
STATE current_state = STATE0;
while(1)
{
printf("please input number to decode:");
while((ch = getchar())!='/n')
{
if((ch<'0')||(ch>'9'))
{
printf("not number, please input again!/n");
break;
}
switch(current_state)
{
case STATE0:
if(ch == '2') current_state = STATE1;
break;
case STATE1:
if(ch == '4') current_state = STATE2;
break;
case STATE2:
if(ch == '7') current_state = STATE3;
break;
case STATE3:
if(ch == '9') current_state = STATE4;
break;
default:
current_state = STATE0;
break;
}
}
if(current_state == STATE4)
{
printf("corrent, lock is open!/n");
current_state = STATE0;
}
else
{
printf("wrong, unlocked!/n");
current_state = STATE0;
}
}
return 0;
}
代碼二：
//FSMstate.h
typedef enum{
STATE0 = 0,
STATE1,
STATE2,
STATE3,
STATE4,
}STATE;
typedef enum{
INPUT1 = '2',
INPUT2 = '4',
INPUT3 = '7',
INPUT4 = '9',
}INPUT;
typedef struct
{
STATE cur_state;
INPUT input;
STATE next_state;
}STATE_TRANS;
//FSMstate.c
#include
#include"FSMstate.h"
/*typedef enum
{
STATE0 = 0,
STATE1,
STATE2,
STATE3,
STATE4,
}STATE;
typedef enum
{
INPUT1 = '2',
INPUT2 = '4',
INPUT3 = '7',
INPUT4 = '9',
}INPUT;
typedef struct
{
STATE cur_state;
INPUT input;
STATE next_state;
}STATE_TRANS;
*/
STATE_TRANS state_trans_array[]=
{
{STATE0,INPUT1,STATE1},
{STATE1,INPUT2,STATE2},
{STATE2,INPUT3,STATE3},
{STATE3,INPUT4,STATE4},
};
#define STATE_TRANS_CNT (sizeof(state_trans_array)/sizeof(state_trans_array[0]))
int main()
{
int i;
char ch;
STATE state_machine = STATE0;
while(ch!= 'e')
{
ch = getchar();
if((ch>= '0')&&(ch<='9'))
{
for(i = 0;i
{
if((ch==state_trans_array[i].input)&&(state_machine==state_trans_array[i].cur_state))
{
state_machine = state_trans_array[i].next_state;
//continue;
break;
}
else if(i==(STATE_TRANS_CNT-1))
{
state_machine = STATE0;
}
}
if(state_machine == STATE4)
printf("Password correct,state transfer machine pass!/n");
}
}
return 0;
}
四有限狀態機自動機
狀態圖－－一個圖的數據結構！
1.while + switch;
2.狀態機：就是指定系統的所有可能的狀態及狀態間跳轉的條件，然後設一個初始狀態輸入給這台機器，機器就會自動運轉，或最後處於終止狀態，或在某一個狀態不斷循環。
游戲中狀態切換是很頻繁的。可能以前要切換狀態就是if~else，或者設標志，但這些都不太結構化，如果把它嚴格的設為一種標准的狀態機，會清楚的多。
比如控制一扇門的運動，初始時門是關的，當有力作用在門上時，門開始慢慢打開，力的作用完後，門漸漸停止不動，當有反向的力時，門又漸漸關上，知道回到初始關的狀態。這個你會怎麼來編程實現呢。似乎很麻煩，的確，沒有狀態機的思想時會很煩，設很多標志，一堆if條件。
用狀態機的話，不只是代碼更清晰，關鍵是更符合邏輯和自然規律，不同狀態不同處理，滿足條件則跳轉到相關狀態。
偽碼如下：
enum
{
CLOSED, //關上狀態
CLOSING, //正在關狀態
OPENED, //打開狀態
OPENING, //正在開的狀態
}doorState = CLOSED; //初始為關
Update()
{
switch(doorState)
case CLOSED:
if (有人推門)
doorState = OPENING; //跳轉到正在開狀態
break;
case OPENING:
door.Rotation += DeltaAngle; //門的旋轉量遞增
if (門的速度為零) / /力的作用已去
doorState = OPENED; //跳轉到開狀態
break;
case OPENED:
if (有人關門)
doorState = CLOSING;
break;
case CLOSING:
door.Rotation -= DeltaAngle; //門的旋轉量遞減
if (門的旋轉角度減為零)
doorState = CLOSED; //門已關上
break;
}
//而繪制代碼幾乎不用怎麼變,門就是會嚴格按照狀態機的指示去運動，該停就會停
Render()
{
RotateView(door.Rotation);
DrawDoor(door.Position);
}
這是一個簡單但很典型的例子，狀態機的應用太多了。
就說一個基本游戲的運轉:（用到了一個狀態然後還有子狀態）
UpdateGame()
BEGIN;
switch(gameState)
case等待選擇菜單: //它有三個子狀態。
if (選擇菜單項＝＝開始)
{
游戲初始；
gameState =開始游戲
}
if (選擇菜單項＝＝選項)
gameState =設置
if (選擇菜單項＝＝退出)
gameState =退出
case開始：
游戲運行；
if (用戶按退出鍵)
gameState =等待選擇菜單;
...其他的狀態跳轉處理;
case退出:
釋放資源；
退出；
case設置:
分別處理不同的選項，跳轉不同的子狀態；
case .... //其他狀態的處理
END;
某一個狀態可以包含更多的子狀態，這樣最好是同一層次的狀態設為一個枚舉,並分到另一個switch處理如enum STATES{state1, state2, state3}; state2又包含若干狀態則再定義enum SUB_STATE2{sub_state2_1, sub_state2_2, sub_state2_3,};
想很多基本的渲染效果，如淡入淡出，閃爍等等，用狀態的思想會事半功倍，思路也更清晰。
其實像Opengl, Direct3D這樣的渲染引擎本身就是狀態機，當你設置渲染的狀態，這台機器就保持這個狀態進行渲染工作，如保持光照位置，保持片元顏色，直到你再次改變它的狀態。
狀態機的應用實在太廣，相關理論也很多，最近上課學的隨機過程裡也講到一些，數字電路裡的時序邏輯器件也是用狀態機來描述。這些不必多說了。
總之，用狀態機的角度去看待問題，往往能把比較復雜的系統分解為能單獨處理的眾多子狀態，處理也會得心應手。希望大家多用它，很好的東西。
五．用C語言實現一個狀態機，這是一位好心的網友的畢業設計，用nRF24L01組建了一個簡單的網絡，做的一個小的狀態機，網絡中三個節點，開始拓撲為網狀，後來為星型。
#include
#include
#include
//Finite state machine declaration
//state declaration
#define IDLE 0 //idle state in rx mode
#define M_BROADCAST 1 //broadcast state in tx mode,broadcast to be a master point
#define M_WAIT_BROADCAST_ACK 2 //wait for broadcast ack state in rx mode,wait for the point ack in a specific time window
#define M_WAIT_COMMAND 3 //wait for command state,wait for PC command via UART
#define M_BROADCAST_CANCEL 4 //broadcast cancel state,broadcast to cancel master point
#define S_BROADCAST_ACK 5 //slave mode,send back self physical address
#define S_WAIT_COMMAND 6 //slave mode, wait for command from the master point
//state transition trig
//used in master mode
int isReqBeMaster = 0;//Is PC request the point to be master?
int isTimeout = 0;//Is time out?
int isReqCancelMaster = 0;//Is request to cancel master?
//used in slave mode
int isRxBroadcast = 0;//Is there a point broadcast to be master?
int isRxBroadcastCancel = 0;//Is receive broadcast cancel master?
typedef struct fsmtag
{
int state; //state
int timeouttime; //time out time in milliseconds
}fsm;
//function prototype
int main()
{
fsm f;
f.state = IDLE;
f.timeouttime = 0;
while(1)
{
switch(f.state)
{
case IDLE:
puts("IDLE/nWait for isReqBeMaster(1/0) isRxBroadcast(1/0):");
scanf("%d %d",&isReqBeMaster,&isRxBroadcast);
if(isReqBeMaster)
{
f.state = M_BROADCAST;
break;
}
else if(isRxBroadcast)
{
f.state = S_BROADCAST_ACK;
break;
}
else
break;
case M_BROADCAST:
puts("M_BROADCAST/nBroadcasting.../n");
f.state = M_WAIT_BROADCAST_ACK;
case M_WAIT_BROADCAST_ACK:
puts("M_WAIT_BROADCAST_ACK/nWaiting for isTimeout(1/0):");
scanf("%d",&isTimeout);
if(isTimeout)
{
f.state = M_WAIT_COMMAND;
break;
}
else
break;
case M_WAIT_COMMAND:
puts("M_WAIT_COMMAND/nWaiting for isReqCancelMaster(1/0):");
scanf("%d",&isReqCancelMaster);
if(isReqCancelMaster)
{
f.state = IDLE;
break;
}
else
break;
//Slave mode routine
case S_BROADCAST_ACK:
puts("S_BROADCAST_ACK/nAcking.../n");
f.state = S_WAIT_COMMAND;
break;
case S_WAIT_COMMAND:
puts("S_WAIT_COMMAND/nWaiting for isRxBroadcastCancel(1/0):");
scanf("%d",&isRxBroadcastCancel);
if(isRxBroadcastCancel)
{
f.state = IDLE;
break;
}
else
break;
default:
puts("default");
printf("%d/n",rand());
f.state = IDLE;
}
}
return 0;
}
