首页 > 代码库 > 普通青年的状态机，纯C语言
普通青年的状态机，纯C语言
我们第一次接触到状态机，是在数字电路课程里。计数器、串行奇偶检校、检验三个1连续出现的报错电路 等，都需要状态机作为模型。实现这些功能的电路，与状态机的状态转换图、状态转换表都是等价的。
后来，我们再接触状态机，是在编译原理课程里。状态机用于描述与正则表达式匹配的字符串。
再后来，我们在GUI界面设计中，需要设置一些控件在某些条件下 禁用，某些条件下使能，某些条件下打个对号。这也可以用状态机模型来控制。
1. 不要写成 消息响应/事件处理
状态机和消息响应都是 双层 switch-case 结构。不同的是，状态机的外层是状态，内层是消息；消息响应外层是消息，内层是状态。
有的同学会说，那又有多大的区别呢？代码只是外在形式而非本质，它所反应的是你对模型的理解，或者说，对于问题，你使用了哪种模型。
消息响应适合于这样的情形：有很多种消息，对于同一种消息，你的程序总是给出同一种反应。打个比方，你女朋友喜欢吃冰淇淋，任何时候你给她买，她都高兴，或者转怒为喜，或者转悲为喜，总之，会置心情为"喜"。这种情形，适合用消息响应解决。
而状态机适合于另一种情形，你的程序是"有状态的"，它在不同的情况 (状态)下，会对同一消息做出不同的反应。状态，是一种数据，但是它影响流程的行为。按面向对象的观点，数据与流程间的这种高内聚关系，非常适合用 类 来实现。这是题外话，我们回到女朋友和冰淇淋间的关系。你女朋友可能并非在任何情况下吃了冰淇淋都高兴，比如刚刚吃完十个八个的时候...这与她当前的状态有关。
状态机中，我们需要掌握的核心的数据是：当前状态，当前消息，将迁移到的状态，在迁移中发生的动作。
在状态机代码之前，请先看一段消息响应机制，VC生成的win32api代码大抵如此。我们随便找来一段片断看看：
1 LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
2 {
3 int wmId, wmEvent;
4 PAINTSTRUCT ps;
5 HDC hdc;
6 switch (message)
7 {
8 case WM_COMMAND:
9 wmId = LOWORD(wParam);
10 wmEvent = HIWORD(wParam);
11 case ID_MENU_GO: .... break;
12 case IDM_ABOUT: .... break;
13 case IDM_EXIT: .... break;
14 default:
15 return DefWindowProc(hWnd, message, wParam, lParam);
16 }
17 break;
18 case WM_PAINT: .... break;
19 case WM_DESTROY: ... break;
20 case WM_KEYDOWN: ... break;
21 default: return DefWindowProc(hWnd, message, wParam, lParam);
22 }
23 return 0;
24 }
第6行开始到第22行结束，对每个消息给出一个响应。没错，win32api也把这个传进来的东西称为 message。这是很典型的适合消息响应机制的情形，程序对于相同的消息，处理的方法总是相同的。
我们常常错误地把状态机写成了消息响应，消息这部分处理得不错，但是，由于没有很好地记录和迁移状态，写起来容易把自己写糊涂了。无他，用错了工具。拿螺丝刀打孔，不是工具差，而是工程师选错了工具。
2. 状态机实例，录音机
实例得是相对简单的，不然我们很容易淹没在细节之中，没有足够精力去关注状态机本身的机制了。假设我们仿真一台录音机...
我们先假设你见过录音机。录音机是一种曾经先进的设备，有一个或两个"卡"，可以放进磁带。"卡"前面有几个按键，这几个按键上的标识因为图形简单且示意性强，现在还在广泛使用。它们分别是 播放 > 、暂停 || 、快进 >> 、快退<< 、录音 O 、停止 []。
这几个按键之间是有一定的"互斥关系"的。比如当播放键按下时，我们不应该能把 快进键按下。当然，淘气的同学可能这样干过，我们会听到"咔咔"的声音，然后是家长骂败家玩艺的声音。可以就"互斥关系"开始写程序，但是我觉得这样有点麻烦。
我们认为，这种"互斥关系"是因为录音机是"有状态的"。所以，我们打算用状态机来实现。状态转换图是这样的。请读图的时候关注这四点：当前状态，当前消息，将迁移到的状态，在迁移中发生的动作 (本例中没有) 。
备注：我实在想不起来 暂停 和 停止 之间的关系了，似乎是这样的，又似乎不是。反正大概是那么个意思，不影响对状态机的理解，就这么地吧。
接下来是C代码实现。
3. 接口 及 测试
看到以下代码，有的同学会说，你这不就是主程序么，为什么要把小标题叫做接口。因为，它规定了我们的状态机函数将是什么样子的。
1 enum message { play, stop, forward, backward, record, pause };
2
3 int main(int argc, char *argv[])
4 {
5 char c=0x00;
6 while(1)
7 {
8 c = getchar();
9 switch(c)
10 {
11 case ‘ ‘: state_change(pause); break;
12 case ‘p‘: state_change(play); break;
13 case ‘r‘: state_change(record); break;
14 case ‘s‘: state_change(stop); break;
15 case ‘f‘: state_change(forward); break;
16 case ‘b‘: state_change(backward); break;
17 case ‘q‘: return EXIT_SUCCESS;
18 }
19 }
20 return EXIT_SUCCESS;
21 }
上述代码规定了，状态机迁移函数的原型/签名是 void state_change(enum
message m)。
测试的时候，我们这样做：./state < test.in。test.in的内容是"psfsbspq"，测试时期待看到输出的状态迁移过程。之所以这样做，而不是每次从控制台手动输入，是因为每次测试的内容都应该是相同的--相同的输入，程序有相同的反应--可重现性。或者说，DRY原则。
一个非常值得我们注意的问题。在上述接口中，我们看不到"状态"。事实上，我们将会定义：
enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };
但是，接口以外的代码，是 *不应该* (是不应该，不是 不必要，是一定不要) 知道状态的，既不应该知道当前状态，也不应该知道将要迁移到哪个状态，也不应该知道在迁移过程中应该做什么动作。如果接口以外的代码知道了这些，就侵入了状态机的隐私，子系统的边界就模糊了。而契约的首要任务就是规定边界，规定国家与个人、个人与个人、个人与集体的边界。
这一原则，早在195X年，软件工程刚刚开始的时候就确立了，是最初确立的原则，即 信息隐藏。后面的原则，都是它的儿子孙子。有个比喻讲过这个道理。当你在超市出口付款的时候，你会自己把钱从钱夹里拿出来递给售货员，而不会转过身去对她说，"在我屁股兜里，你自己掏吧，别忘了把零钱放回来。"这既增加了假设--你极端信任她，也增加了她的责任。
接口，最主要的任务就是为了明确责任，把责任分布在子系统边界两侧。其次才是规定调用的方法，即边界长什么样。
4. 状态迁移
以下是状态机的代码片断。
1 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record};
2 void state_change(enum message m)
3 {
4 static enum state s=s_stop;
5 switch (s)
6 {
7 case s_play:
8 if(m==stop)
9 {
10 s = s_stop;
11 printf("stop.\n");
12 }
13 else if (m==pause)
14 {
15 s = s_pause;
16 printf("pause");
17 }
18 break;
我们还是要关注那四个关键点： (1) 当前状态， (2) 当前消息， (3) 将迁移到哪个状态， (4) 迁移中会做哪些动作。
(1) 当前状态必然是第1行的枚举类型中的一个。我们初始化状态为 停止，见第4行。
在第5行到第7行，我们的双重 switch-case 的外层 按当前状态分类，如下。
5 switch (s)
6 {
7 case s_play:
下面还有很多 case，第1行的枚举类型中的每一个状态，都有一个 case。
(2) 当前消息。如果当前状态是第7行了，那么，当前消息由双层 switch-case的内层，即第8行，第13行的 if...else if 来响应。
(3) 将迁移到哪个状态。在 s_play状态 (第7行) 接收到 stop 消息 (第8行)的话，将迁移到 s_stop 状态，即第10行。
(4) 在迁移中会做哪些动作，如果还是这个状态这个消息，会做的动作是 第11行，打印一段文字描述接下来的状态。
在函数 void state_change(enum message m) 中，维护了当前状态，规定了在某种状态下-接收到某个消息，会迁移到哪个状态，在状态迁移中做哪些动作。
主函数在调用state_change时，是通过这一接口，向状态机发送一个消息；由状态机对这个消息做出适合自己当前状态的响应--状态迁移、动作。主函数所看到的，是一个多彩或善变的女人，而她之所以对同一消息做出不同响应的原因，在她的内心深入保留着，那是她不会对你说的状态，以及状态迁移中的波澜壮阔。即使表面上善变的状态机，也是可以理解和预测的，如果她对你倘开心扉，允许你一行一行把附录A中的代码读完，了解所有的 switch-case，了解所有的状态下她将会如何响应每一种消息。
附录A 完整代码
1 #include <stdlib.h>
2 #include <stdio.h>
3
4
5 //recorder
6
7 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };
8 enum message { play, stop, forward, backward, record, pause };
9
10
11 void state_change(enum message m)
12 {
13 static enum state s=s_stop;
14 switch (s)
15 {
16 case s_play:
17 if(m==stop)
18 {
19 s = s_stop;
20 printf("stop.\n");
21 }
22 else if (m==pause)
23 {
24 s = s_pause;
25 printf("pause");
26 }
27 break;
28 case s_pause:
29 if(m==pause)
30 {
31 s = s_play;
32 printf("play.\n");
33 }
34 else if(m==stop)
35 {
36 s = s_stop;
37 printf("stop.\n");
38 }
39 break;
40 case s_stop:
41 if(m==play)
42 {
43 s = s_play;
44 printf("play.\n");
45 }
46 if(m==backward)
47 {
48 s = s_backward;
49 printf("backward.\n");
50 }
51 if(m==forward)
52 {
53 s = s_forward;
54 printf("forward.\n");
55 }
56 if(m==record)
57 {
58 s = s_record;
59 printf("record.\n");
60 }
61 break;
62 case s_forward:
63 if(m==stop)
64 {
65 s = s_stop;
66 printf("stop.\n");
67 }
68 break;
69 case s_backward:
70 if(m==stop)
71 {
72 s = s_stop;
73 printf("stop.\n");
74 }
75 break;
76 case s_record:
77 if(m==stop)
78 {
79 s = s_stop;
80 printf("stop.\n");
81 }
82 break;
83
84
85 }
86
87 }
88
89
90 int main(int argc, char *argv[])
91 {
92 char c=0x00;
93 while(1)
94 {
95 c = getchar();
96 switch(c)
97 {
98 case ‘ ‘: state_change(pause); break;
99 case ‘p‘: state_change(play); break;
100 case ‘r‘: state_change(record); break;
101 case ‘s‘: state_change(stop); break;
102 case ‘f‘: state_change(forward); break;
103 case ‘b‘: state_change(backward); break;
104 case ‘q‘: return EXIT_SUCCESS;
105 }
106
107
108 }
109
110 return EXIT_SUCCESS;
111 }
附录B 状态图源代码 in graphviz
digraph state
{
graph [ nodesep=1.2];
rankdir = LR;
播放 -> 暂停 [label="按下 || "];
暂停 -> 播放 [label="按下 || "];
暂停 -> 停止 [label="按下 []"];
停止 -> 播放 [label="按下 >"];
播放 -> 停止 [label="按下 []"];
停止 -> 快退 [label="按下 <<"];
停止 -> 快进 [label="按下 >>"];
快进 -> 停止 [label="按下 []"];
快退 -> 停止 [label="按下 []"];
停止 -> 录音 [label="按下 O"];
录音 -> 停止 [label="按下 []"];
}
--------------------
博客会手工同步到以下地址：
[http://giftdotyoung.blogspot.com]
[http://blog.csdn.net/younggift]
=======================
后来，我们再接触状态机，是在编译原理课程里。状态机用于描述与正则表达式匹配的字符串。
再后来，我们在GUI界面设计中，需要设置一些控件在某些条件下 禁用，某些条件下使能，某些条件下打个对号。这也可以用状态机模型来控制。
1. 不要写成 消息响应/事件处理
状态机和消息响应都是 双层 switch-case 结构。不同的是，状态机的外层是状态，内层是消息；消息响应外层是消息，内层是状态。
有的同学会说，那又有多大的区别呢？代码只是外在形式而非本质，它所反应的是你对模型的理解，或者说，对于问题，你使用了哪种模型。
消息响应适合于这样的情形：有很多种消息，对于同一种消息，你的程序总是给出同一种反应。打个比方，你女朋友喜欢吃冰淇淋，任何时候你给她买，她都高兴，或者转怒为喜，或者转悲为喜，总之，会置心情为"喜"。这种情形，适合用消息响应解决。
而状态机适合于另一种情形，你的程序是"有状态的"，它在不同的情况 (状态)下，会对同一消息做出不同的反应。状态，是一种数据，但是它影响流程的行为。按面向对象的观点，数据与流程间的这种高内聚关系，非常适合用 类 来实现。这是题外话，我们回到女朋友和冰淇淋间的关系。你女朋友可能并非在任何情况下吃了冰淇淋都高兴，比如刚刚吃完十个八个的时候...这与她当前的状态有关。
状态机中，我们需要掌握的核心的数据是：当前状态，当前消息，将迁移到的状态，在迁移中发生的动作。
在状态机代码之前，请先看一段消息响应机制，VC生成的win32api代码大抵如此。我们随便找来一段片断看看：
1 LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
2 {
3 int wmId, wmEvent;
4 PAINTSTRUCT ps;
5 HDC hdc;
6 switch (message)
7 {
8 case WM_COMMAND:
9 wmId = LOWORD(wParam);
10 wmEvent = HIWORD(wParam);
11 case ID_MENU_GO: .... break;
12 case IDM_ABOUT: .... break;
13 case IDM_EXIT: .... break;
14 default:
15 return DefWindowProc(hWnd, message, wParam, lParam);
16 }
17 break;
18 case WM_PAINT: .... break;
19 case WM_DESTROY: ... break;
20 case WM_KEYDOWN: ... break;
21 default: return DefWindowProc(hWnd, message, wParam, lParam);
22 }
23 return 0;
24 }
第6行开始到第22行结束，对每个消息给出一个响应。没错，win32api也把这个传进来的东西称为 message。这是很典型的适合消息响应机制的情形，程序对于相同的消息，处理的方法总是相同的。
我们常常错误地把状态机写成了消息响应，消息这部分处理得不错，但是，由于没有很好地记录和迁移状态，写起来容易把自己写糊涂了。无他，用错了工具。拿螺丝刀打孔，不是工具差，而是工程师选错了工具。
2. 状态机实例，录音机
实例得是相对简单的，不然我们很容易淹没在细节之中，没有足够精力去关注状态机本身的机制了。假设我们仿真一台录音机...
我们先假设你见过录音机。录音机是一种曾经先进的设备，有一个或两个"卡"，可以放进磁带。"卡"前面有几个按键，这几个按键上的标识因为图形简单且示意性强，现在还在广泛使用。它们分别是 播放 > 、暂停 || 、快进 >> 、快退<< 、录音 O 、停止 []。
这几个按键之间是有一定的"互斥关系"的。比如当播放键按下时，我们不应该能把 快进键按下。当然，淘气的同学可能这样干过，我们会听到"咔咔"的声音，然后是家长骂败家玩艺的声音。可以就"互斥关系"开始写程序，但是我觉得这样有点麻烦。
我们认为，这种"互斥关系"是因为录音机是"有状态的"。所以，我们打算用状态机来实现。状态转换图是这样的。请读图的时候关注这四点：当前状态，当前消息，将迁移到的状态，在迁移中发生的动作 (本例中没有) 。
备注：我实在想不起来 暂停 和 停止 之间的关系了，似乎是这样的，又似乎不是。反正大概是那么个意思，不影响对状态机的理解，就这么地吧。
接下来是C代码实现。
3. 接口 及 测试
看到以下代码，有的同学会说，你这不就是主程序么，为什么要把小标题叫做接口。因为，它规定了我们的状态机函数将是什么样子的。
1 enum message { play, stop, forward, backward, record, pause };
2
3 int main(int argc, char *argv[])
4 {
5 char c=0x00;
6 while(1)
7 {
8 c = getchar();
9 switch(c)
10 {
11 case ‘ ‘: state_change(pause); break;
12 case ‘p‘: state_change(play); break;
13 case ‘r‘: state_change(record); break;
14 case ‘s‘: state_change(stop); break;
15 case ‘f‘: state_change(forward); break;
16 case ‘b‘: state_change(backward); break;
17 case ‘q‘: return EXIT_SUCCESS;
18 }
19 }
20 return EXIT_SUCCESS;
21 }
上述代码规定了，状态机迁移函数的原型/签名是 void state_change(enum
message m)。
测试的时候，我们这样做：./state < test.in。test.in的内容是"psfsbspq"，测试时期待看到输出的状态迁移过程。之所以这样做，而不是每次从控制台手动输入，是因为每次测试的内容都应该是相同的--相同的输入，程序有相同的反应--可重现性。或者说，DRY原则。
一个非常值得我们注意的问题。在上述接口中，我们看不到"状态"。事实上，我们将会定义：
enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };
但是，接口以外的代码，是 *不应该* (是不应该，不是 不必要，是一定不要) 知道状态的，既不应该知道当前状态，也不应该知道将要迁移到哪个状态，也不应该知道在迁移过程中应该做什么动作。如果接口以外的代码知道了这些，就侵入了状态机的隐私，子系统的边界就模糊了。而契约的首要任务就是规定边界，规定国家与个人、个人与个人、个人与集体的边界。
这一原则，早在195X年，软件工程刚刚开始的时候就确立了，是最初确立的原则，即 信息隐藏。后面的原则，都是它的儿子孙子。有个比喻讲过这个道理。当你在超市出口付款的时候，你会自己把钱从钱夹里拿出来递给售货员，而不会转过身去对她说，"在我屁股兜里，你自己掏吧，别忘了把零钱放回来。"这既增加了假设--你极端信任她，也增加了她的责任。
接口，最主要的任务就是为了明确责任，把责任分布在子系统边界两侧。其次才是规定调用的方法，即边界长什么样。
4. 状态迁移
以下是状态机的代码片断。
1 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record};
2 void state_change(enum message m)
3 {
4 static enum state s=s_stop;
5 switch (s)
6 {
7 case s_play:
8 if(m==stop)
9 {
10 s = s_stop;
11 printf("stop.\n");
12 }
13 else if (m==pause)
14 {
15 s = s_pause;
16 printf("pause");
17 }
18 break;
我们还是要关注那四个关键点： (1) 当前状态， (2) 当前消息， (3) 将迁移到哪个状态， (4) 迁移中会做哪些动作。
(1) 当前状态必然是第1行的枚举类型中的一个。我们初始化状态为 停止，见第4行。
在第5行到第7行，我们的双重 switch-case 的外层 按当前状态分类，如下。
5 switch (s)
6 {
7 case s_play:
下面还有很多 case，第1行的枚举类型中的每一个状态，都有一个 case。
(2) 当前消息。如果当前状态是第7行了，那么，当前消息由双层 switch-case的内层，即第8行，第13行的 if...else if 来响应。
(3) 将迁移到哪个状态。在 s_play状态 (第7行) 接收到 stop 消息 (第8行)的话，将迁移到 s_stop 状态，即第10行。
(4) 在迁移中会做哪些动作，如果还是这个状态这个消息，会做的动作是 第11行，打印一段文字描述接下来的状态。
在函数 void state_change(enum message m) 中，维护了当前状态，规定了在某种状态下-接收到某个消息，会迁移到哪个状态，在状态迁移中做哪些动作。
主函数在调用state_change时，是通过这一接口，向状态机发送一个消息；由状态机对这个消息做出适合自己当前状态的响应--状态迁移、动作。主函数所看到的，是一个多彩或善变的女人，而她之所以对同一消息做出不同响应的原因，在她的内心深入保留着，那是她不会对你说的状态，以及状态迁移中的波澜壮阔。即使表面上善变的状态机，也是可以理解和预测的，如果她对你倘开心扉，允许你一行一行把附录A中的代码读完，了解所有的 switch-case，了解所有的状态下她将会如何响应每一种消息。
附录A 完整代码
1 #include <stdlib.h>
2 #include <stdio.h>
3
4
5 //recorder
6
7 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };
8 enum message { play, stop, forward, backward, record, pause };
9
10
11 void state_change(enum message m)
12 {
13 static enum state s=s_stop;
14 switch (s)
15 {
16 case s_play:
17 if(m==stop)
18 {
19 s = s_stop;
20 printf("stop.\n");
21 }
22 else if (m==pause)
23 {
24 s = s_pause;
25 printf("pause");
26 }
27 break;
28 case s_pause:
29 if(m==pause)
30 {
31 s = s_play;
32 printf("play.\n");
33 }
34 else if(m==stop)
35 {
36 s = s_stop;
37 printf("stop.\n");
38 }
39 break;
40 case s_stop:
41 if(m==play)
42 {
43 s = s_play;
44 printf("play.\n");
45 }
46 if(m==backward)
47 {
48 s = s_backward;
49 printf("backward.\n");
50 }
51 if(m==forward)
52 {
53 s = s_forward;
54 printf("forward.\n");
55 }
56 if(m==record)
57 {
58 s = s_record;
59 printf("record.\n");
60 }
61 break;
62 case s_forward:
63 if(m==stop)
64 {
65 s = s_stop;
66 printf("stop.\n");
67 }
68 break;
69 case s_backward:
70 if(m==stop)
71 {
72 s = s_stop;
73 printf("stop.\n");
74 }
75 break;
76 case s_record:
77 if(m==stop)
78 {
79 s = s_stop;
80 printf("stop.\n");
81 }
82 break;
83
84
85 }
86
87 }
88
89
90 int main(int argc, char *argv[])
91 {
92 char c=0x00;
93 while(1)
94 {
95 c = getchar();
96 switch(c)
97 {
98 case ‘ ‘: state_change(pause); break;
99 case ‘p‘: state_change(play); break;
100 case ‘r‘: state_change(record); break;
101 case ‘s‘: state_change(stop); break;
102 case ‘f‘: state_change(forward); break;
103 case ‘b‘: state_change(backward); break;
104 case ‘q‘: return EXIT_SUCCESS;
105 }
106
107
108 }
109
110 return EXIT_SUCCESS;
111 }
附录B 状态图源代码 in graphviz
digraph state
{
graph [ nodesep=1.2];
rankdir = LR;
播放 -> 暂停 [label="按下 || "];
暂停 -> 播放 [label="按下 || "];
暂停 -> 停止 [label="按下 []"];
停止 -> 播放 [label="按下 >"];
播放 -> 停止 [label="按下 []"];
停止 -> 快退 [label="按下 <<"];
停止 -> 快进 [label="按下 >>"];
快进 -> 停止 [label="按下 []"];
快退 -> 停止 [label="按下 []"];
停止 -> 录音 [label="按下 O"];
录音 -> 停止 [label="按下 []"];
}
--------------------
博客会手工同步到以下地址：
[http://giftdotyoung.blogspot.com]
[http://blog.csdn.net/younggift]
=======================
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。