轉載自： http://www.cppblog.com/CppExplore/archive/2008/01/23/41726.html
一、狀态機描述
狀态機理論最初的發展在數字電路設計領域。在數字電路方面，根據輸出是否與輸入信号有關，狀态機可以劃分為Mealy型和Moore型狀态機；根據輸出是否與輸入信号同步，狀态機可以劃分為異步和同步狀态機。而在軟體設計領域，狀态機設計的理論俨然已經自成一體。Moore型狀态機的輸出隻和目前狀态有關，和輸入無關，如果在軟體設計領域設計出這種類型的狀态機，則該狀态機接受的事件都是無内蘊資訊的事件（輸入）。Mealy型狀态機的輸入是由目前狀态和輸入共同決定，對應到軟體設計領域，則該狀态機接收的事件含有内蘊資訊，并且影響狀态機的輸出。顯然，這種劃分在軟體設計領域毫無意義。雖然軟體設計領域的狀态機也有同步和異步的劃分，但和數字電路方面的同步異步已經不同。
除了《數字電路》，涉及到狀态機的課程就是《編譯原理》了（本人屬計算機專業，其它專業是否涉及到狀态機就不清楚了）。下面簡單回顧一下《編譯原理》裡有關有限狀态機的描述。在編譯原理課程裡面，對有限狀态機的描述僅限在編譯領域，特定狀态，針對輸入字元，發生狀态改變，沒有額外的行為，另編譯原理裡有限狀态機的構成要素，還包含唯一的初始狀态和一個終态集。數學語言描述如下：一個有限狀态機M是一個五元組，M=(K,E,T,S,Z)。其中（1)K是一個有窮集，其中的每個元素稱為狀态(2)E是一個有窮字母表，它的每個元素稱為一個輸入字元（3）T是轉換函數，是K×E->K上的映射(4)S是K中的元素，是唯一的一個初态（5） Z是K的一個子集，是一個終态集，或者叫結束集。很明顯，狀态機在編譯原理裡的講解已經特化，輸入被定位為字元集，狀态改變的時候沒有額外動作發生。
與編譯原理中的狀态機不同，軟體設計領域中通用狀态機的輸入不是字元集，而是被稱作事件的結構（可以是結構體，也可以是類對象），并且特定的狀态下，針對發生的事件，不僅發生狀态改變，而且産生動作。借鑒編譯原理中狀态機的初始狀态和終态，通用狀态機的數學語言描述如下：一個通用有限狀态機M是一個七元組，M={K,E,T,M,F,S,Z}。其中（1）K是一個有窮集，其中的每個元素稱為狀态(2)E是一個有窮集，它的每個元素稱為一個事件（3）T是轉換函數，是K×E->K上的映射（4）M是一個有窮集，它的每個元素稱為動作（5）F是動作映射函數，是K×E->M上的映射（6)S是K中的元素，是唯一的一個初态（7） Z是K的一個子集，是一個終态集，或者叫結束集。實用的狀态機可以做進一步的優化，首先，可以把 （3）（5）整合在一起，做一個K×E->{K,M}的映射，其次從實用性的角度出發，禁止狀态接收空事件（無輸入的情況下，狀态發生改變），作為彌補，為每個狀态增加進入動作和離開動作，第三，鑒于定時器在系統中，尤其是在狀态機中的重要性，可以為每個狀态增加定時器以及逾時後的狀态轉換。本文後面的講述以及實作暫不考慮把定時器特化，如果需要，可以在狀态的進入動作中初始化定時器（另：關于定時器，以後會寫文章《系統設計之 定時器》）。
二、狀态機分類（後文中如無特别說明，則狀态機指軟體設計領域的通用有限狀态機）
依據狀态之間是否有包含關系，分以下兩種
（1）正常狀态機。狀态機中的所有狀态是不相交的、互斥的。
（2）層次狀态機。狀态機中的狀态之間要麼是互斥的，要麼是真包含的，可以用樹性結構來描述這些狀态集，包含其它狀态的狀态稱為枝節點，不包含其它狀态的狀态稱為葉節點，為友善單樹描述，總是設計一個狀态包含所有的狀态節點，稱為根節點。狀态機的狀态隻能停留在葉節點，而不能停留在枝節點，每個枝節點需要指定一個子節點為它的預設子節點，以便狀态機進入枝節點的時候能夠停留到葉節點。
三、狀态機實作
（1）switch/case if/else方式實作。用于少量狀态（3個及其以下）的時候，不需要引入專門的狀态機子產品。這種方式不能編寫通用的狀态機子產品，不再多說。
（2）面向過程方式：宏是實作面向過程方式的通用方式。雖然在狀态機層面還是可以用面向對象的方式封裝，這裡還是把它稱為面向過程的方式。
1.正常狀态機子產品實作。這個狀态機涉及到機構由上而下為：
頂層結構是狀态機：目前狀态id，預設操作，狀态表，
狀态表：狀态數組
狀态結構：狀态id，狀态名，進入操作，退出操作，預設操作，狀态事件表（數組）
狀态事件結構：操作，事件，下一狀态的id
狀态機的算法是由狀态機的結構決定的。實作如下：
#define SINGLE_STATE_MAX_EVENT 10
typedef int FSM_EVENT_ID;
typedef struct event_param_st
{
FSM_EVENT_ID id;
union
{
int i;
}data;
} FSM_EVENT;
typedef int FSM_STATE_ID;
typedef void ( * FSM_FUNC)(FSM_EVENT * );
typedef struct state_event_st
{
FSM_FUNC func;
FSM_EVENT_ID event;
FSM_STATE_ID state;
} FSM_STATE_EVENT;
typedef struct state_st
{
FSM_STATE_ID id;
char *name;
FSM_FUNC enter_func;
FSM_FUNC exit_func;
FSM_FUNC default_func;
FSM_STATE_EVENT event_table[SINGLE_STATE_MAX_EVENT];
} FSM_STATE;
typedef FSM_STATE STATE_TABLE[];
typedef FSM_STATE * PTR_STATE_TABLE;
#define END_EVENT_ID -1
#define END_STATE_ID -1
#define BEGIN_FSM_STATE_TABLE(state_stable) static STATE_TABLE state_stable =
{
#define BEGIN_STATE(id,name,enter_func,exit_func,default_func)
{id,name,enter_func,exit_func,default_func,
{
#define STATE_EVENT_ITEM(func,event,state)
{func,event,state},
#define END_STATE(id)
{NULL,END_EVENT_ID,END_STATE_ID}}},
#define END_FSM_STATE_TABLE(state_stable)
{END_STATE_ID,NULL,NULL,NULL,NULL,NULL}} ;
typedef struct fsm_st
{
FSM_STATE_ID state_id;
FSM_FUNC default_func;
PTR_STATE_TABLE state_tables;
} FSM;
void fsm_do_event(FSM & fsm, FSM_EVENT & event)
{
FSM_STATE *state=&(fsm.state_tables[fsm.state_id]);
int i=0;
while(state->event_table[i].event!=END_EVENT_ID)
{
if(state->event_table[i].event==event.id)
break;
i++;
}
if(state->event_table[i].event!=END_EVENT_ID)
{
if(state->id!=state->event_table[i].state)
{
if(state->exit_func )
state->exit_func(&event);
}
if(state->event_table[i].func)
state->event_table[i].func(&event);
if(state->id!=state->event_table[i].state)
{
if(fsm.state_tables[state->event_table[i].state].enter_func)
fsm.state_tables[state->event_table[i].state].enter_func(&event);
fsm.state_id=state->event_table[i].state;
}
}
else
{
if(state->default_func)
state->default_func(&event);
else
{
if(fsm.default_func)
fsm.default_func(&event);
}
}
}
以上說明實作原理，有特殊需要的話可以自己定制狀态機，比如上面的狀态事件表數組的上限取的是單個狀态中事件項的最大值，也可以定義為所有事件的個數，這樣的話事件也不需要查詢，可以象狀态樣直接定位，隻是狀态事件表會浪費一些存儲空間。上面的FSM_EVENT僅僅是個例子，實際開發根據需要定義不同的union。上面的算法也是假定狀态表的狀态定義是從0開始，順序遞增的。
對外部調用而言，最後的狀态機結構和事件執行的方法可以封裝為對象。下面舉例說明狀态機的定義(事件和狀态都應該是enum類型，這裡直接使用數字，僅為說明問題而已)。
BEGIN_FSM_STATE_TABLE(my_state_table)
BEGIN_STATE(0 , " first " ,enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm, 1 ,1 )
STATE_EVENT_ITEM(func_fsm, 2 ,2 )
END_STATE(0 )
BEGIN_STATE(1 , " second " ,enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm, 1 ,2 )
STATE_EVENT_ITEM(func_fsm, 2 ,0 )
END_STATE(1 )
BEGIN_STATE(2 , " third " ,enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm, 1 ,0 )
STATE_EVENT_ITEM(func_fsm, 2 ,1 )
END_STATE(2 )
END_FSM_STATE_TABLE(my_state_table)
void enter_fsm(FSM_EVENT * event)
{
printf("enter me\n");
}
void exit_fsm(FSM_EVENT * event)
{
printf("exit me\n");
}
void defualt_fsm(FSM_EVENT * event)
{
printf("i am defualt_fsm\n");
}
void func_fsm(FSM_EVENT * event)
{
printf("i am func_fsm\n");
}
int main()
{
printf("i am main\n");
FSM fsm=
{0,defualt_fsm,my_state_table};
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
FSM_EVENT event;
event.id=1;
event.data.i=1;
fsm_do_event(fsm,event);
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
}