如何以面向對象的思想設計有限狀態機
狀態機的概念
有限狀態機又稱有限狀態自動機，簡稱狀態機，是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學計算模型，用英文縮寫也被簡稱為 FSM。
FSM 會響應「事件」而改變狀態，當事件發生時，就會調用一個函數，而且 FSM 會執行動作產生輸出，所執行的動作會因為當前系統的狀態和輸入的事件不同而不同。
問題背景
為了更好地描述狀態機的應用，這裡用一個地鐵站的閘機為背景，簡單敘述一下閘機的工作流程：
通常閘機默認是關閉的，當閘機檢測到有效的卡片信息後，打開閘機，當乘客通過後，關閉閘機；如果有人非法通過，那麼閘機就會產生報警，如果閘機已經打開，而乘客仍然在刷卡，那麼閘機將會顯示票價和餘額，並在屏幕輸出「請通過，謝謝」。
在了解了閘機的工作流程之後，我們就可以畫出閘機的狀態圖，狀態圖如下:
在上圖中，線條上面的字表示的是:閘機輸入事件/閘機執行動作，方框內表示的是閘機的狀態。
除了使用狀態圖來表示系統的工作流程外，我們也可以採用狀態表的方式來表示系統的工作流程，狀態表如下所示：
| 起始狀態 | 事件 | 結束狀態 | 動作 |
|---|---|---|---|
| Locked | card | Unlocked | unlock |
| Locked | pass | Locked | alarm |
| Unlocked | card | Unlocked | thankyou |
| Unlocked | pass | Locked | lock |
通過上述我們已經知道閘機的工作流程了，接下來我們來看具體的實現。
代碼實現
嵌套的 switch 語句
使用嵌套的 switch 語句是最為直接的辦法，也是最容易想的方法，第一層 switch 用於狀態管理，第二層 switch 用於管理各個狀態下的各個事件。代碼實現可以用下述偽代碼來實現：
switch(當前狀態)
{
case LOCKED 狀態：
switch(事件)：
{
case card 事件：
切換至 UNLOCKED 狀態;
執行 unlock 動作;
break;
case pass 事件：
執行 alarm 動作;
break;
}
break;
case UNLOCKED 狀態：
switch(事件):
{
case card 事件:
執行 thankyou 動作;
break;
case pass 事件:
切換至 LOCKED 狀態;
執行 lock 動作;
break;
}
break;
}
上述代碼雖然很直觀，但是狀態和事件都出現在一個處理函數中，對於一個大型的 FSM 中，可能存在大量的狀態和事件，那麼代碼量將是非常冗長的。為了解決這個問題，可以採用狀態轉移表的方法來處理。
狀態轉移表
為了減少代碼的長度，可以使用查表法，將各個信息存放於一個表中，根據事件和狀態查找表項，找到需要執行的動作以及即將轉換的狀態。
typedef struct _transition_t
{
狀態;
事件;
轉換為新的狀態;
執行的動作;
}transition_t;
transition_t transitions[] = {
{LOCKED 狀態,card 事件,狀態轉換為UNLOCKED,unlock動作},
{LOCKED 狀態,pass 事件,狀態保持為LOCKED,alarm 動作},
{UNLOCKED 狀態,card 事件,狀態轉換為 UNLOCKED，thankyou動作},
{UNLOCKED 狀態,pass 事件,狀態轉換為 LOCKED,lock 動作}
};
for (int i = 0;i < sizeof(transition)/sizeof(transition[0]);i++)
{
if (當前狀態 == transition[i].狀態 && 事件 == transition[i].事件)
{
切換狀態為:transition[i].轉換為新的狀態;
執行動作:transition[i].執行的動作;
break;
}
}
從上述我們可以看到如果要往狀態機中添加新的流程，那麼只需要往狀態表中添加東西就可以了，也就是說整個狀態機的維護及管理只需要把重心放到狀態轉移表的維護中就可以了，從代碼量也可以看出來，採用狀態轉移表的方法相比於第一種方法也大大地縮減了代碼量，而且也更容易維護。
但是對於狀態轉移表來說，缺點也是顯而易見的，對於大型的 FSM 來說，遍歷狀態轉移表需要花費大量的時間，從而影響代碼的執行效率。
那要怎樣設計代碼量少，又不需要以遍歷狀態轉移表的形式從而花費大量時間的狀態機呢？這個時候就需要以面向對象的思想來設計有限狀態機。
面向對象法設計狀態機
面向對象基本概念
以面向對象的思想實現的狀態機，大量涉及了對於函數指針的用法，必須對這個概念比較熟悉
上述所提到了兩個設計方法都是基於面向過程的一種設計思想，面向過程編程(POP)是一種以過程為中心的編程思想，以正在發生的事件為主要目標，指導開發者利用算法作為基本構建塊構建複雜系統。
即將所要介紹的面向對象編程(OOP)是利用類和對象作為基本構建塊，因此分解系統時，可以從算法開始，也可以從對象開始，然後利用所得到的結構作為框架構建系統。
提到面向對象編程，那自然繞不開面向對象的三個基本特徵：
- 封裝：隱藏對象的屬性和實現細節，僅僅對外公開接口
- 繼承：使用現有類的所有功能，並在無需重新編寫原來的類的情況下對這些功能進行擴展，C 語言使用 struct 的特性實現繼承
- 多態性：使用相同的方法，根據對象的類型調用不同的處理函數。
上述對於面向對象的三個基本特徵做了一個簡單的介紹，封裝和繼承的概念都都比較清晰，多態性這個特點可能會有所迷惑，在這裡筆者用在書中看到一個例子來解釋多態性，例子是這樣的：
要求畫一個形狀，這個形狀是可能是圓形，矩形，星形，無論是什麼圖形，其共性都是需要調用一個畫的方法來進行繪製，繪製的形狀可以通過函數指針調用各自的繪圖代碼繪製，這就是多態的意義，根據對象的類型調用不同的處理函數。
在介紹了上述很基本的概念之後，我們來看狀態機的設計。
實現細節
我們由淺入深地來思考這個問題，首先我們可以想到把閘機當做一個對象，那麼這個這個對象的職責就是處理 card 事件(刷卡)和 pass 事件(通過閘機)，閘機會根據當前的狀態執行不同的動作，也就有了如下的代碼：
enum {LOCKED,UNLOCKED};/*枚舉各個狀態*/
/*定義閘機類*/
typedef struct _turnstile
{
int state;
void (*card)(struct _turnstile *p_this);
void (*pass)(struct _turnstile *p_this);
}turnstile_t;
/* 閘機 card 事件 */
void turnstile_card(turnstile_t *p_this)
{
if (p_this->state == LOCKED)
{
/* 切換至解鎖狀態 */
/* 執行unlock動作,調用 unlock 函數 */
}
else
{
/* 執行 thank you 動作,調用 thank you 函數 */
}
}
/* 閘機 pass 事件*/
void turnstile_pass(turnstile_t *p_this)
{
if (p_this->state == LOCKED)
{
/* 執行 alarm 動作,調用 alarm 函數*/
}
else
{
/* 狀態切換至鎖閉狀態 */
/* 執行 lock 動作,調用 lock 函數 */
}
}
上述代碼的思想實現的有限狀態機相比於前兩種不需要進行大量的遍歷，也不會導致代碼量的冗長，看似已經比較完美了，但是我們再仔細想想，如果此時狀態更改了，那 turnstile_card 函數和 turnstile_pass 函數都要更改，也就是說事件和狀態存在着耦合，這與「高內聚，低耦合」的思想所違背，也就是說如果我們要繼續優化代碼，那需要對事件和狀態進行解耦。
狀態和事件解耦
將事件與狀態相分離，從而使得各個狀態的事件處理函數非常的單一，因此在這裡需要定義一個狀態類：
typedef struct _turnstile_state_t
{
void (*card)(void); /* card 事件處理函數 */
void (*pass)(void); /* pass 事件處理函數 */
}turnstile_state_t;
在定義了狀態類之後，我們就可以使用狀態類創建 lock 和 unlock 的實例並初始化。
turnstile_state_t locked_state = {locked_card,locked_pass};
turnstile_state_t unlocked_state = {unlocked_card,unlocked_pass};
在這裡需要補充一下上述初始化項里函數里的具體實現。
void locked_card(void)
{
/* 狀態切換至解鎖狀態 */
/* 執行 unlock 動作 ,調用 unlock 函數 */
}
void locked_pass(void)
{
/* 執行 alarm 動作，調用 alarm 函數 */
}
void unlocked_card(void)
{
/* 執行 thank you 動作，調用 thank you 函數 */
}
void unlocked_pass(void)
{
/* 狀態切換至鎖閉狀態 */
/* 執行 lock 動作，調用 lock 函數 */
}
這樣，也就實現了狀態與事件的解耦，閘機不再需要判斷當前的狀態，而是直接調用不同狀態提供的 card() 和 pass() 方法。定義了狀態類之後，由於閘機是整個系統的中心，我們還需要定義閘機類，由於 turnstile_state_t 中只存在方法，並不存在屬性，那麼我們可以這樣來定義閘機類：
typedef struct _turnstile_t
{
turnstile_state_t *p_state;
}turnstile_t;
到這裡，我們已經定義了閘機類，閘機狀態類，以及閘機狀態類實例，他們之間的關係如下圖所示：
通過圖中我們也可以看到閘機類是繼承於閘機狀態類的，locked_state 和 unlocked_state 實例是由閘機狀態類派生而來的，那最底下的那個箭頭是為什麼呢？這是在後面需要講到的對於閘機狀態轉換的處理，在獲取輸入事件調用具體的方法進行處理後，我們需要修改閘機類的p_state,所以也就有了這個箭頭。
相比於最開始定義的閘機類，這個顯得更加簡潔了，同時 p_state 可以指向相應的狀態對象，從而調用相應的事件處理函數。
在定義了一個閘機類之後，就可以通過閘機類定義一個閘機實例:
turnstile_t turnstile;
然後通過函數進行初始化：
void turnstile_init(turnstile_t *p_this)
{
p_this->p_state = &locked_state;
}
整個系統閘機作為中心，進而需要定義閘機類的事件處理方法，定義方法如下：
/* 閘機 card 事件*/
void turnstile_card(turnstile_t *p_this)
{
p_this->p_state->card();
}
/* 閘機 pass 事件 */
void turnstile_pass(turnstile_t *p_this)
{
p_this->p_state->pass();
}
到這裡，我們回顧前文所述，我們已經能夠對閘機進行初始化並使得閘機根據不同的狀態執行不同的處理函數了，再回顧整個閘機的工作流程，我們發現閘機在工作的時候會涉及到從 locked 狀態到 unlocked 狀態的相互變化，也就是狀態的轉移,因此狀態轉移函數可以這樣實現：
void turnstile_state_set(turnstile_t *p_this,turnstile_state_t *p_new_state)
{
p_this->p_state = p_new_state;
}
而狀態的轉移是在事件處理之後進行變化的。那麼我們可以這樣修改處理函數，這裡用輸出語句替代閘機動作執行函數：
void locked_card(turnstile_t *p_turnstile)
{
turnstile_state_set(p_turnstile,&unlocked_state);
printf("unlock\n"); /* 執行 unlock 動作 */
}
void locked_pass(turnstile_t *p_turnstile)
{
printf("alarm\n"); /* 執行 alarm 動作*/
}
void unlocked_card(turnstile_t *p_turnstile)
{
printf("thankyou\n"); /* 執行 thank you 動作*/
}
void unlocked_pass(turnstile_t *p_turnstile)
{
turnstile_state_set(p_turnstile,&locked_state);
printf("lock\n"); /* 執行 lock 動作 */
}
既然處理函數都發生了變化，那麼閘機狀態類也應該發生更改，更改如下：
typedef struct _turnstile_state_t
{
void (*card)(turnstile_t *p_turnstile);
void (*pass)(turnstile_t *p_turnstile);
}turnstile_state_t;
但是回顧之前我們給出的閘機類和閘機狀態類的關係，閘機類是繼承於閘機狀態類的，也就是說先有的閘機狀態類後有的閘機類，但是這裡卻在閘機狀態類的方法中使用了閘機類的參數，其實這樣也是可行的，需要提前對閘機類進行處理，總的閘機類狀態類定義如下：
#ifndef __TURNSTILE_H__
#define __TURNSTILE_H__
struct _turnstile_t;
typedef struct _turnstile_t turnstile_t;
typedef struct _turnstile_state_t
{
void (*card)(turnstile_t *p_turnstile);
void (*pass)(turnstile_t *p_turnstile);
}turnstile_state_t;
typedef struct _turnstile_t
{
turnstile_state_t *p_state;
}turnstile_t;
void turnstile_init(turnstile_t *p_this); /* 閘機初始化 */
void turnstile_card(turnstile_t *p_this); /* 閘機 card 事件處理 */
void turnstile_pass(turnstile_t *p_this); /* 閘機 pass 事件處理 */
#endif
上述就是所有的關於狀態機的相關定義了，下面通過上述的定義實現狀態機的實現：
#include <stdio.h>
#include <turnstile.h>
int main(void)
{
int event;
turnstile_t turnstile; /* 閘機實例 */
turnstile_init(&turnstile); /* 初始化閘機為鎖閉狀態 */
while(1)
{
scanf("%d",&event);
switch(event)
{
case 0:
turnstile_card(&turnstile);
break;
case 1:
turnstile_pass(&turnstile);
break;
default:
exit(0);
}
}
上述代碼運行結果如下：
結論
以上便是筆者關於狀態機的全部總結，講述了面向過程和面向對象兩種實現方法，雖然從篇幅上看面向對象的方法要更為複雜，但是代碼的執行效率以及長度都要優於面向過程的方法，所以了解面向對象的程序設計方法是很有必要的。
這篇文章是在筆者學習了《程序設計與數據結構》周立功版後的自己的理解，該書的PDF版可以從立功科技官網的周立功專欄中獲取。
下面給出書籍和文章狀態機代碼匯總的鏈接：
程序設計與數據結構：
鏈接：//pan.baidu.com/s/17ZH7Si1f_9My7BulLs8AVA
提取碼：x1im
FSM:
鏈接：//pan.baidu.com/s/1qO-Dy6bHukBRGxxQ1-KGJA
提取碼：vyn2
最後，如果您覺得我的文章對您有所幫助，歡迎關注筆者的個人公眾號：wenzi嵌入式軟件
