有限状态机+函数指针-C语言实现

有读者在后台留言说用c写一篇有限状态机的推文,正好之前也用过,就分享一下吧。

背景

先举一个简单的例子,假设是这样的,一个小孩有两种状态,睡眠,清醒。睡的时候可能会撒尿,微笑,撒尿之后会转为清醒状态,而清醒的时候可能会笑,会吃,吃完之后会转会睡眠状态
用C语言实现,一般写法可能是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//来源:公众号【编程珠玑】
#include <stdio.h>
enum KID_STATUS
{
SLEEP = 0,
WAKE = 1,
INVALID = 2
};
enum KID_ACTION
{
SMILE = 0,
EAT = 1,
PEE = 2
};
/*孩子当前状态*/
static int nowStatus = WAKE;
/*孩子行为*/
int smile(int status)
{
printf("kid smile\n");
return status;
}
int eat(int status)
{
printf("kid eat\n");
return SLEEP;
}
int pee(int status)
{
printf("kid pee\n");
return WAKE;
}
/*孩子产生某个行为*/
void execute(int action)
{
int nextStatus;
/*醒着时的行为*/
if(WAKE == nowStatus)
{
switch(action)
{
case SMILE:
{
nextStatus = smile(nowStatus);
break;
}
case EAT:
{
nextStatus = eat(nowStatus);
break;
}
case PEE:
{
nextStatus = pee(nowStatus);
break;
}
default:
printf("unknow action when wake %d\n",action);
nextStatus = nowStatus;
break;
}
}
/*睡着时的行为*/
else if(SLEEP == nowStatus)
{
switch(action)
{
case SMILE:
{
nextStatus = smile(nowStatus);
break;
}
casePEE:
{
nextStatus = pee(nowStatus);
break;
}
default:
printf("unknow action when sleep %d\n",action);
nextStatus = nowStatus;
break;
}
}
else
{
printf("unknow action\n");
}
nowStatus = nextStatus;
printf("next status is %d\n",nowStatus);
}
int main(void)
{
nowStatus = SLEEP;
execute(EAT);
return 0;
}

这段代码的意图就非常明显了,首先判断当前所在状态, 然后找到其中的行为,最后执行。
但是这段代码有以下几个特点:

  • 新加一种行为需要修改execute函数
  • 新加一种行为需要增加更多分支代码
  • 新加一种状态,需要新增一个大的分支
  • 哪些状态有哪些行为不是很明显

换一种写法

在《高级指针话题-函数指针》中介绍了函数指针,以及在《编程技巧-跳转表》介绍了函数跳转表。这里我们把代码调整一下,看看结合跳转表和状态机,能写出什么样的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//来源:公众号【编程珠玑】地址:https://www.yanbinghu.com
#include <stdio.h>
enum KID_STATUS
{
SLEEP = 0,
WAKE = 1,
INVALID = 2
};
enum KID_ACTION
{
SMILE = 0,
EAT = 1,
PEE = 2
};
/*孩子当前状态*/
static int nowStatus = WAKE;
/*孩子行为*/
int smile(int status)
{
printf("kid smile\n");
return status;
}
int eat(int status)
{
printf("kid eat\n");
return SLEEP;
}
int pee(int status)
{
printf("kid pee\n");
return WAKE;
}
typedef int (*Handler)(int);//函数指针
/*用于处理某种状态的行为*/
typedef struct Act_Handler
{
int action;
Handler handler;
}Act_Handler;
/*某种状态的处理集*/
typedef struct Stat_Handler
{
int status;
int actNum;
Act_Handler *actHandler;
}Stat_Handler;
/*sleep状态行为处理*/
Act_Handler sleepHandler[] =
{
{SMILE,smile},
{PEE,pee}
};
/*wake状态行为处理*/
Act_Handler wakeHandler[] =
{
{SMILE,smile},
{PEE,pee},
{EAT,eat}
};
/*状态处理*/
static Stat_Handler statHandler[] =
{
{SLEEP,sizeof(sleepHandler)/sizeof(Act_Handler),sleepHandler},
{WAKE,sizeof(wakeHandler)/sizeof(Act_Handler),wakeHandler},
};
static int statSize = sizeof(statHandler)/ sizeof(Stat_Handler);
void execute(int action)
{
if(nowStatus >= statSize)
{
printf("unknow status\n");
return;
}
printf("now status is %d,action %d\n",nowStatus,action);
int nextStatus = nowStatus;
Act_Handler *actHandler = statHandler[nowStatus].actHandler;
int actNum = statHandler[nowStatus].actNum;
int actIdx = 0;
/*遍历指定状态下的行为集,找到对应的行为*/
for(actIdx = 0;actIdx < actNum;actIdx++)
{
if(actHandler[actIdx].action == action)
{
nextStatus = (actHandler[actIdx].handler)(action);
break;
}
}
if(actIdx == actNum)
{
printf("did find action %d in status %d\n",action,nowStatus);
}
nowStatus = nextStatus;
printf("next status is %d\n",nowStatus);
}
int main(void)
{
nowStatus = WAKE;
execute(EAT);
return 0;
}

这里简单说明一下execute函数中的执行流程。

  • 判断当前状态合法性
  • 在数组中找到对应状态的行为处理集
  • 在处理集中找到对应的行为
  • 处理结束

这种方式有什么特点呢?可以看到,在需要新加一个动作的时候,只需要在sleepHandler或者wakeHandler中添加,完全不影响execute函数的改动。你甚至可以将不同状态分在不同的文件中管理,使得结构更加清晰明朗。

另外一方面,某种状态下,能执行哪些动作,非常清晰。

不过这样的写法对于初学者来说不太友好,但是不影响你添加新的内容。

有的读者可能会堪虑,在寻找行为的时候,for循环会不会很慢?首先这和case差别不大,通常不会有性能问题,其次除了使用数组,还可以考虑其他数据结构,例如哈希,我在《工作中用不到算法,为什么还要学算法?》中也提到了,数据结构和算法能更好地帮我们解决问题。

总结

本文代码较多,建议在实际环境中运行调试。

守望 wechat
关注公众号[编程珠玑]获取更多原创技术文章
出入相友,守望相助!