C++分析研究  
C++
日历
<2024年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
  一、状态机实现的要素
 
   首先,分析一下一个普通的状态机究竟要实现哪些内容。
 
   状态机存储从开始时刻到现在的变化,并根据当前输入,决定下一个状态。这意味着,状态机要存储状态、获得输入(我们把它叫做跳转条件)、做出响应。托福改分
 
   如上所示,{s1, s2, s3}均为状态,箭头c1/a1表示在s1状态、输入为c1时,跳转到s2,并进行a1操作。托福答案
 
   最下方为一组输入,状态机应做出如下反应:
 
   当前状态 输入 下一个状态 动作
 
   s1 c1 s2 a1
 
   s2 c2 s3 a2
 
   s3 c1 s2 a3
 
   s2 c2 s3 a2
 
   s3 c1 s2 a3
 
   s2 c1 s_trap a_trap
 
   s_trap c1 s_trap a_trap
 
   当某个状态遇到不能识别的输入时,就默认进入陷阱状态,在陷阱状态中,不论遇到怎样的输入都不能跳出。
 
   为了表达上面这个自动机,我们定义它们的状态和输入类型:
 
   typedef int state;
 
   typedef int condition;
 
   #define
 
   STATES 4
 
   #define
 
   STATE1 0
 
   #define
 
   STATE2 1
 
   #define
 
   STATE3 2
 
   #define
 
   STATETRAP 3
 
   #define
 
   CONDITIONS 2
 
   #define
 
   CONDITION1 0
 
   #define
 
   CONDITION2 1
 
   总结一下,我们需要定义的有状态、输入、行为(动作+下一个状态),其中,行为的个数是"状态数*输入数量"(其中有一些是重复的);其中动作一般来说可以用一个函数指针来实现。
 
   二、具体设计
 
   在嵌入式环境中,由于存储空间比较小,因此把它们全部定义成宏。此外,为了降低执行时间的不确定性,我们使用O(1)的跳转表来模拟状态的跳转。
 
   首先定义跳转类型:
 
   typedef void (*actiontype)(state
 
   mystate, condition condition);
 
   typedef struct
 
   {
 
   state
 
   next;
 
   actiontype
 
   action;
 
   }
 
   trasition, * ptrasition;
 
   然后按照上图中的跳转关系,把三个跳转加一个陷阱跳转先定义出来:
 
   //
 
   (s1, c1, s2, a1)
 
   trasition
 
   t1 = {
 
   STATE2,
 
   action1
 
   };
 
   //
 
   (s2, c2, s3, a2)
 
   trasition
 
   t2 = {
 
   STATE3,
 
   action2
 
   };
 
   //
 
   (s3, c1, s2, a3)
 
   trasition
 
   t3 = {
 
   STATE2,
 
   action3
 
   };
 
   //
 
   (s, c, trap, a1)
 
   trasition
 
   tt = {
 
   STATETRAP,
 
   actiontrap
 
   };
 
   其中的动作,由用户自己完成,在这里仅定义一条输出语句。
 
   void action1(State
 
   state, Condition condition)
 
   {
 
   printf("Action
 
   1 triggered.\n");
 
   }
 
   1
 
   最后定义跳转表:
 
   asition
 
   transition_table[STATES][CONDITIONS] = {
 
   /*
 
   c1, c2*/
 
   /*
 
   s1 */&t1,
 
   &tt,
 
   /*
 
   s2 */&tt,
 
   &t2,
 
   /*
 
   s3 */&t3,
 
   &tt,
 
   /*
 
   st */&tt,
 
   &tt,
 
   };
 
   即可表达上文中的跳转关系。
 
   最后定义状态机,如果不考虑多任务请求,那么状态机仅需要存储当前状态便行了。例如:
 
   typedef struct
 
   {
 
   State
 
   current;
 
   }
 
   StateMachine, * pStateMachine;
 
   State
 
   step(pStateMachine machine, Condition condition)
 
   {
 
   pTrasition
 
   t = transition_table[machine->current][condition];
 
   (*(t->action))(machine->current,
 
   condition);
 
   machine->current
 
   = t->next;
 
   return machine->current;
 
   }
 
   总结:我们现在设计实现好了一个状态机,然后要给这个状态机特定的输入,看看状态机的运转情况,以上面图中的那个状态机为例,我们输入的序列是0和1分别代表c1和C2,然后状态s1,s2分别对应0,1.用程序实现这个内容如下
 
   三、程序实现
 
   程序清单:小型状态机的实现
 
   [cpp
 
   #include<stdio.h>
 
   #include<unistd.h>
 
   #include<stdlib.h>
 
   typedef int state;
 
   typedef int condition;
 
   #define STATENUM 4
 
   #define STATE1 0
 
   #define STATE2 1
 
   #define STATE3 2
 
   #define STATETRAP 3
 
   #define CONDITIONS 2
 
   #define CONDITION1 0
 
   #define CONDITION2 1
 
   typedef void (* actiontype)(state mystate,condition mycondition);
 
   typedef struct{
 
   state next;
 
   actiontype action;
 
   }trasition, *ptrasition;
 
   void action1(state mystate,condition myconditon);
 
   void action2(state mystate,condition myconditon);
 
   void action3(state mystate,condition myconditon);
 
   void actiontrap(state mystate,condition myconditon);
 
   trasition t1={
 
   STATE2,action1
 
   };
 
   trasition t2={
 
   STATE3,action2
 
   };
 
   trasition t3={
 
   STATE2,action3
 
   };
 
   trasition tt={
 
   STATETRAP,actiontrap
 
   };
 
   void action1(state mystate,condition myconditon){
 
   printf("action1 one triggered\n");
 
   }
 
   void action2(state mystate,condition myconditon){
 
   printf("action2 one triggered\n");
 
   }
 
   void action3(state mystate,condition myconditon){
 
   printf("action3 one triggered\n");
 
   }
 
   void actiontrap(state mystate,condition myconditon){
 
   printf("actiontrap one triggered\n");
 
   }
 
   ptrasition transition_table[STATENUM][CONDITIONS] = {
 
   /* c1, c2*/
 
   /* s1 */&t1, &tt,
 
   /* s2 */&tt, &t2,
 
   /* s3 */&t3, &tt,
 
   /* st */&tt, &tt,
 
   };
 
   typedef struct
 
   {
 
   state current;
 
   } StateMachine, * pStateMachine;
 
   state step(pStateMachine machine, condition mycondition)
 
   {
 
   ptrasition t = transition_table[machine->current][mycondition];
 
   (*(t->action))(machine->current, mycondition);
 
   machine->current = t->next;
 
   printf("the current state is %d\n",t->next );
 
   return machine->current;
 
   }
 
   int main(int argc, char *argv[])
 
   {
 
   StateMachine mymachine;
 
   mymachine.current=STATE1;
 
   int mycon;
 
   char ch;
 
   while(1){
 
   scanf("%d",&mycon);
 
   step(&mymachine,mycon);
 
   }
 
   return 0;
 
   }
 
 
 
posted on 2013-10-14 15:42 HAOSOLA 阅读(1808) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖