摘要：狀態(tài)機模式是一種行為模式，在《設計模式》這本書中對其有詳細的描述，通過多態(tài)實現(xiàn)不同狀態(tài)的調(diào)轉(zhuǎn)行為的確是一種很好的方法，只可惜在嵌入式環(huán)境下，有時只能寫純C代碼，并且還需要考慮代碼的重入和多任務請求跳轉(zhuǎn)等情形，因此實現(xiàn)起來著實需要一番考慮。本文主要為你實現(xiàn)一個簡單的有限狀態(tài)機，沒有考慮代碼的重入和多任務跳轉(zhuǎn)，為以后復雜的狀態(tài)機實現(xiàn)，打下基礎。

?本文來源：用C語言實現(xiàn)有限狀態(tài)自動機FSM

一、狀態(tài)機實現(xiàn)的要素

首先，分析一下一個普通的狀態(tài)機究竟要實現(xiàn)哪些內(nèi)容。

狀態(tài)機存儲從開始時刻到現(xiàn)在的變化，并根據(jù)當前輸入，決定下一個狀態(tài)。這意味著，狀態(tài)機要存儲狀態(tài)、獲得輸入（我們把它叫做跳轉(zhuǎn)條件）、做出響應。

如上圖所示，{s1, s2, s3}均為狀態(tài)，箭頭c1/a1表示在s1狀態(tài)、輸入為c1時，跳轉(zhuǎn)到s2，并進行a1操作。

最下方為一組輸入，狀態(tài)機應做出如下反應：

當前狀態(tài)	輸入	下一個狀態(tài)	動作
s1	c1	s2	a1
s2	c2	s3	a2
s3	c1	s2	a3
s2	c2	s3	a2
s3	c1	s2	a3
s2	c1	s_trap	a_trap
s_trap	c1	s_trap	a_trap

?

當某個狀態(tài)遇到不能識別的輸入時，就默認進入陷阱狀態(tài)，在陷阱狀態(tài)中，不論遇到怎樣的輸入都不能跳出。

為了表達上面這個自動機，我們定義它們的狀態(tài)和輸入類型：

1 2 3 4 5 6 7 8 9 10 11 12

typedef?int?s tate; typedef?int?c ondition; #define STATES 4 #define STATE1 0 #define STATE2 1 #define STATE3 2 #define STATETRAP 3 #define CONDITIONS 2 #define CONDITION1 0 #define CONDITION2 1

?總結(jié)一下，我們需要定義的有狀態(tài)、輸入、行為（動作+下一個狀態(tài)），其中，行為的個數(shù)是“狀態(tài)數(shù)*輸入數(shù)量”（其中有一些是重復的）；其中動作一般來說可以用一個函數(shù)指針來實現(xiàn)。

二、具體設計

? ? ? ?在嵌入式環(huán)境中，由于存儲空間比較小，因此把它們?nèi)慷x成宏。此外，為了降低執(zhí)行時間的不確定性，我們使用O(1)的跳轉(zhuǎn)表來模擬狀態(tài)的跳轉(zhuǎn)。

首先定義跳轉(zhuǎn)類型：

1 2 3 4 5 6 7

typedef?void? (*actiontype)(state mystate, condition condition); typedef?struct { ????state next; ????actiontype action; } trasition, * ptrasition;

?

然后按照上圖中的跳轉(zhuǎn)關系，把三個跳轉(zhuǎn)加一個陷阱跳轉(zhuǎn)先定義出來：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// (s1, c1, s2, a1) trasition t1 = { ????STATE2, ????action1 }; // (s2, c2, s3, a2) trasition t2 = { ????STATE3, ????action2 }; // (s3, c1, s2, a3) trasition t3 = { ????STATE2, ????action3 }; // (s, c, trap, a1) trasition tt = { ????STATETRAP, ????actiontrap };

?

其中的動作，由用戶自己完成，在這里僅定義一條輸出語句。

1 2 3 4

void?action1(State state, Condition condition) { ????printf ( "Action 1 triggered.\n" ); }

1	最后定義跳轉(zhuǎn)表：

1 2 3 4 5 6 7

ptrasition transition_table[STATES][CONDITIONS] = { /*????? c1,? c2*/ /* s1 */ &t1, &tt, /* s2 */ &tt, &t2, /* s3 */ &t3, &tt, /* st */ &tt, &tt, };

?

即可表達上文中的跳轉(zhuǎn)關系。

最后定義狀態(tài)機，如果不考慮多任務請求，那么狀態(tài)機僅需要存儲當前狀態(tài)便行了。例如：

1 2 3 4 5 6 7 8 9 10 11 12

typedef?struct { ????State current; } StateMachine, * pStateMachine; State step(pStateMachine machine, Condition condition) { ????pTrasition t = transition_table[machine->current][condition]; ????(*(t->action))(machine->current, condition); ????machine->current = t->next; ????return? machine->current; }

總結(jié)：我們現(xiàn)在設計實現(xiàn)好了一個狀態(tài)機，然后要給這個狀態(tài)機特定的輸入，看看狀態(tài)機的運轉(zhuǎn)情況，以上面圖中的那個狀態(tài)機為例，我們輸入的序列是0和1分別代表c1和C2，然后狀態(tài)s1，s2分別對應0，1.用程序?qū)崿F(xiàn)這個內(nèi)容如下

三、程序?qū)崿F(xiàn)

程序清單：小型狀態(tài)機的實現(xiàn) #include<stdio.h> #include<unistd.h> #include<stdlib.h> typedef int state; typedef int condition;#define STATENUM 4 #define STATE1 0 #define STATE2 1 #define STATE3 2 #define STATETRAP 3#define CONDITIONS 2 #define CONDITION1 0 #define CONDITION2 1typedef void (* actiontype)(state mystate,condition mycondition); typedef struct{state next;actiontype action; }trasition, *ptrasition;void action1(state mystate,condition myconditon); void action2(state mystate,condition myconditon); void action3(state mystate,condition myconditon); void actiontrap(state mystate,condition myconditon); trasition t1={STATE2,action1 }; trasition t2={STATE3,action2 }; trasition t3={STATE2,action3 }; trasition tt={STATETRAP,actiontrap };void action1(state mystate,condition myconditon){printf("action1 one triggered\n"); } void action2(state mystate,condition myconditon){printf("action2 one triggered\n"); } void action3(state mystate,condition myconditon){printf("action3 one triggered\n"); } void actiontrap(state mystate,condition myconditon){printf("actiontrap one triggered\n"); }ptrasition transition_table[STATENUM][CONDITIONS] = { /* c1, c2*/ /* s1 */&t1, &tt, /* s2 */&tt, &t2, /* s3 */&t3, &tt, /* st */&tt, &tt, }; typedef struct {state current; } StateMachine, * pStateMachine;state step(pStateMachine machine, condition mycondition) {ptrasition t = transition_table[machine->current][mycondition];(*(t->action))(machine->current, mycondition);machine->current = t->next;printf("the current state is %d\n",t->next );return machine->current; } int main(int argc, char *argv[]) {StateMachine mymachine;mymachine.current=STATE1;int mycon;char ch;while(1){scanf("%d",&mycon); step(&mymachine,mycon);}return 0; }
程序輸入與輸出結(jié)果示例：
四、外部參考 【1】 嵌入式設計模式：有限狀態(tài)自動機的C語言實現(xiàn)? http://www.cnblogs.com/autosar/archive/2012/06/22/2558604.html

總結(jié)

以上是生活随笔為你收集整理的用C语言实现有限状态自动机FSM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。