C語言_有限狀态機（Finite State Machine）

基本介紹

許多小型或複雜的應用程式都使用有限狀态機 (FSM)，C 語言中的有限狀态機是嵌入式系統的流行設計模式之一，有限狀态機使開發變得容易和順利。

有很多裝置使用事件基态，如咖啡機、自動售貨機、POS 裝置、門鎖系統等。一些 POS 裝置使用事件表，在事件表中使用事件處理程式注冊事件，通過相關條件觸發事件的執行。

C語言_有限狀态機（FSM）C語言_有限狀态機（Finite State Machine）

本文中，使用C語言建立一個簡易的ATM狀态機。 ATM 機的狀态可以通過即将發生的事件進行更改。ATM狀态機包含以下幾個狀态：

Idle State
Card Inserted State
Pin entered State
Option Selected State
Amount Entered State

初始化時，ATM處于閑置狀态，之後進入插卡狀态，插卡處理完成之後需要使用者輸入密碼，輸入密碼之後進行相關選項的操作，設定選項完成之後輸入金額。建立一個狀态機，按照以下步驟進行：

Gather the information which the user wants.
Analyze the all gather information and sketch the state transition diagram.
create a code skeleton of the state machine.
Make sure the transition (changing state) work properly
Implement all the required information in the code skeleton of the state machine.
Test the implemented state machine.

收集需求——>分析需求繪制狀态圖——>建立代碼架構——>确認狀态轉換是否正确——>編寫狀态的具體動作——>測試狀态機。

實作方法

在C語言中，有兩種常用的方式實作基于事件的狀态機：一種是通過嵌套的switch case（或者if else）實作，一種是look up table（查表）實作。

look up table 查表法實作有限狀态機

結構體數組建立有限狀态機是一種比較優雅的方式。狀态機的狀态和事件封裝在一個結構中，并在适當的狀态和事件上調用函數指針（事件處理程式），程式的可讀性比較好。

#include <stdio.h>
//Different state of ATM machine
typedef enum
{
	Idle_State,
	Card_Inserted_State,
	Pin_Eentered_State,
	Option_Selected_State,
	Amount_Entered_State,
	last_State
} eSystemState;
//Different type events
typedef enum
{
	Card_Insert_Event,
	Pin_Enter_Event,
	Option_Selection_Event,
	Amount_Enter_Event,
	Amount_Dispatch_Event,
	last_Event
} eSystemEvent;
//typedef of function pointer
typedef eSystemState(*pfEventHandler)(void);
//structure of state and event with event handler
typedef struct
{
	eSystemState eStateMachine;
	eSystemEvent eStateMachineEvent;
	pfEventHandler pfStateMachineEvnentHandler;
} sStateMachine;
//function call to dispatch the amount and return the ideal state
eSystemState AmountDispatchHandler(void)
{
	return Idle_State;
}
//function call to Enter amount and return amount entered state
eSystemState EnterAmountHandler(void)
{
	return Amount_Entered_State;
}
//function call to option select and return the option selected state
eSystemState OptionSelectionHandler(void)
{
	return Option_Selected_State;
}
//function call to enter the pin and return pin entered state
eSystemState EnterPinHandler(void)
{
	return Pin_Eentered_State;
}
//function call to processing track data and return card inserted state
eSystemState InsertCardHandler(void)
{
	return Card_Inserted_State;
}
//Initialize array of structure with states and event with proper handler
sStateMachine asStateMachine[] =
{
	{ Idle_State,				Card_Insert_Event,			InsertCardHandler },
	{ Card_Inserted_State,		Pin_Enter_Event,			EnterPinHandler },
	{ Pin_Eentered_State,		Option_Selection_Event,		OptionSelectionHandler },
	{ Option_Selected_State,	Amount_Enter_Event,			EnterAmountHandler },
	{ Amount_Entered_State,		Amount_Dispatch_Event,		AmountDispatchHandler }
};
//main function
int main(int argc, char *argv[])
{
	eSystemState eNextState = Idle_State;
	while (1)
	{
		//Api read the event
		eSystemEvent eNewEvent = read_event();
		if ((eNextState < last_State) && (eNewEvent < last_Event) && 		(asStateMachine[eNextState].eStateMachineEvent == eNewEvent) && (asStateMachine[eNextState].pfStateMachineEvnentHandler != NULL))
		{
			// function call as per the state and event and return the next state of the finite state machine
			eNextState = (*asStateMachine[eNextState].pfStateMachineEvnentHandler)();
		}
		else
		{
			//Invalid
		}
	}
	return 0;
}

狀态機結構體中包含狀态，事件編号，執行狀态的動作。執行動作将傳回對應的狀态值。填寫狀态機的結構體數組，狀态、觸發事件和即将執行的動作。狀态機運作時，初始化狀态機，實踐中，通常從外部API讀入實踐觸發動作的執行。執行狀态機中的動作，傳回下一個狀态的狀态編号。

switch case實作有限狀态機

這是實作狀态機的最簡單方法。使用 if-else 或 switch case 來檢查狀态并觸發事件。如果狀态和觸發事件的組合比對，則執行事件處理程式并更新下一個狀态。這取決于檢查第一個狀态或事件的要求。在下面的示例代碼中，首先驗證狀态，然後檢查觸發的事件。

#include <stdio.h>
//Different state of ATM machine
typedef enum
{
	Idle_State,
	Card_Inserted_State,
	Pin_Eentered_State,
	Option_Selected_State,
	Amount_Entered_State,
} eSystemState;
//Different type events
typedef enum
{
	Card_Insert_Event,
	Pin_Enter_Event,
	Option_Selection_Event,
	Amount_Enter_Event,
	Amount_Dispatch_Event
} eSystemEvent;
//Prototype of eventhandlers
eSystemState AmountDispatchHandler(void)
{
	return Idle_State;
}
eSystemState EnterAmountHandler(void)
{
	return Amount_Entered_State;
}
eSystemState OptionSelectionHandler(void)
{
	return Option_Selected_State;
}
eSystemState EnterPinHandler(void)
{
	return Pin_Eentered_State;
}
eSystemState InsertCardHandler(void)
{
	return Card_Inserted_State;
}
int main(int argc, char *argv[])
{
	eSystemState eNextState = Idle_State;
	eSystemEvent eNewEvent;
	while (1)
	{
		//Read system Events
		eSystemEvent eNewEvent = ReadEvent();
		switch (eNextState)
		{
			case Idle_State:
			{
				if (Card_Insert_Event == eNewEvent)
				{
					eNextState = InsertCardHandler();
				}
			}
			break;
			case Card_Inserted_State:
			{
				if (Pin_Enter_Event == eNewEvent)
				{
					eNextState = EnterPinHandler();
				}
			}
			break;
			case Pin_Eentered_State:
			{
				if (Option_Selection_Event == eNewEvent)
				{
					eNextState = OptionSelectionHandler();
				}
			}
			break;
			case Option_Selected_State:
			{
				if (Amount_Enter_Event == eNewEvent)
				{
					eNextState = EnterAmountHandler();
				}
			}
			break;
			case Amount_Entered_State:
			{
				if (Amount_Dispatch_Event == eNewEvent)
				{
					eNextState = AmountDispatchHandler();
				}
			}
			break;
			default:
				break;
		}
	}
	return 0;
}

使用switch case 和if else實作上面的狀态切換和動作執行，導緻程式很長，不利于後期的維護和修改。可否對上面的程式進行優化，避免這種嵌套的結構呢？

使用二維數組指針精簡switch case嵌套結構

答案是肯定得，我們在上面的程式中，首先是用switch case進行了狀态的判斷，然後使用if else判斷是否有事件觸發動作。那麼相當于這段代碼包含兩層判斷，第一層大的狀态判斷後面跟随着一層判斷。基于這個認知，自然就想到，可否使用一個二維數組，行代表一層判斷，列代表這一層判斷下面的子狀态判斷呢！

下面，使用一個二維數組替代以上switch case的嵌套，實作代碼的精簡：

# include <stdio.h>
typedef enum
{
	Idle_State,
	Card_Inserted_State,
	Pin_Eentered_State,
	Option_Selected_State,
	Amount_Entered_State,
	last_State
} eSystemState;
//Different type events
typedef enum
{
	Card_Insert_Event,
	Pin_Enter_Event,
	Option_Selection_Event,
	Amount_Enter_Event,
	Amount_Dispatch_Event,
	last_Event
} eSystemEvent;
//typedef of 2d array
typedef eSystemState (*const afEventHandler[last_State][last_Event])(void);
//function call to dispatch the amount and return the ideal state
eSystemState AmountDispatchHandler(void)
{
	return Idle_State;
}
//function call to Enter amount and return amount enetered state
eSystemState EnterAmountHandler(void)
{
	return Amount_Entered_State;
}
//function call to option select and return the option selected state
eSystemState OptionSelectionHandler(void)
{
	return Option_Selected_State;
}
//function call to enter the pin and return pin entered state
eSystemState EnterPinHandler(void)
{
	return Pin_Eentered_State;
}
//function call to processing track data and return card inserted state
eSystemState InsertCardHandler(void)
{
	return Card_Inserted_State;
}
int main(int argc, char *argv[])
{
	eSystemState eNextState = Idle_State;
	eSystemEvent eNewEvent;
	// Table to define valid states and event of finite state machine
	static afEventHandler StateMachine =
	{
		[Idle_State] = { [Card_Insert_Event] = InsertCardHandler },
		[Card_Inserted_State] = { [Pin_Enter_Event] = EnterPinHandler },
		[Pin_Eentered_State] = { [Option_Selection_Event] = OptionSelectionHandler },
		[Option_Selected_State] = { [Amount_Enter_Event] = EnterAmountHandler },
		[Amount_Entered_State] = { [Amount_Dispatch_Event] = AmountDispatchHandler },
	};
	while (1)
	{
		// assume api to read the next event
		eSystemEvent eNewEvent = ReadEvent();
		//Check NULL pointer and array boundary
		if ((eNextState < last_State) && (eNewEvent < last_Event) && StateMachine[eNextState][eNewEvent] != NULL)
		{
			// function call as per the state and event and return the next state of the finite state machine
			eNextState = (*StateMachine[eNextState][eNewEvent])();
		}
		else
		{
			//Invalid
		}
	}
	return 0;
}

在上面這段代碼中，使用typedef定義函數指針，傳回值正是執行動作傳回的狀态值。二維數組傳回event，是一個執行動作的過程。這樣的話，在有限狀态機的實作中，定義行為state，列裡面我們放置event，每一列對應一個action，就可以實作根據前一次的state和event，執行目前與之對應的action，而傳回目前執行動作的state，使狀态機正确轉移到下一個狀态。

在上面的實作方法中，一個嵌套的 switch case 替換為一個指向函數的指針數組。精簡了代碼，但是同時也并降低代碼的可讀性。當狀态很多，觸發動作的條件也很多時，會造成記憶體大量的浪費，因為在二維數組中，每一行裡面并非所有的event都是這一行的state必須的。

reference：

https://aticleworld.com/state-machine-using-c/

C語言_有限狀态機（FSM）C語言_有限狀态機（Finite State Machine）

C語言_有限狀态機（Finite State Machine）

基本介紹

實作方法

look up table 查表法實作有限狀态機

switch case實作有限狀态機

使用二維數組指針精簡switch case嵌套結構

繼續閱讀

彙編語言基本概念（續13）

DOG（4）：解析器的部分實作細節先來說說parser一些可能迷惑的地方結果如何傳回?pcd其實是一回事最後的一點說明

NYOJ 269--VF

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

UVA 110 Meta-Loopless Sorts

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

The first led（led逐個點亮過程

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

結構體：typedef與struct的差別

無人機--飛控科普

STM32-UART序列槽通信STM32-UART序列槽通信

hdu7108哈希