[转]用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[]机制是非常普遍的，可以成功地应用在你所定义的函数中。

原文: http://blog.csdn.net/Melody_1208/archive/2007/09/22/1795676.aspx