从图中可以看出，自动售货机控制器存在的状态数量是比较多的，但是无论何时，自动售货机总处于空闲、售货、商品价格设置、时间设置、测试等诸多状态之中的一个．这些状态之间是互斥的。同时，上面列举的所有状态都包含子状态，例如：状态S2(时间设置状态)包括日期设置、时分秒设置、星期设置等子状态，而对于S3(日期设置状态)又包括S4(日期显示状态)和S5(日期编辑状态)两个子状态。因此，对于自动售货机控制器这样一个系统，其内部的状态机是一种层次型状态机。本文根据层次型状态机的互斥与包含的双重特性，提出层次型有限状态机模型，并且用来实现自动售货机控制器。模型使用树结构来描述状态集，包含其他状态的状态称为“树枝节点”，不包含其他状态的状态称为“叶子节点”。为方便用单树结构描述，总是设计一个状态包含所有的状态节点，称为“根节点”，它是一个虚拟的节点，在系统中没有状态与其对应。状态机只能停留在叶子节点，而不能停留在树枝节点，每个树枝节点需指定一个子节点为它的默认子节点，以便状态机进入树枝节点时能停留到叶子节点。

3 层次型有限状态机模型
3．1 数据结构定义
    HFSM模型采用树结构实现有限状态机，树上的每一个节点都对应了自动售货机状态机的一个状态。其中根节点是一个特殊的节点，它对应的是一个虚拟的并不存在的状态，其目的是为了构造一棵单树，而不是每一个功能对应一棵树。节点的数据结构如下：

    其中，id为状态编号，每个状态编号在整个系统状态机中是唯一的；name为状态名；enter_func为状态进入操作；exit_func为状态退出操作；event_table为事件表；sub_state_table为子状态表。因为叶子节点没有子状态，而树枝节点没有状态事件表，所以结构中的事件表与子状态可以共享一段存储空间。事件表中每个元素是另外一个结构FSM_STATE_EVENT，它有事件id(与事件源一一对应)、事件操作(func)和下一状态编号(next_state_id)三个成员。图2所示的状态图子集经过处理形成图3所示的状态树，它是整个自动售货机状态树的一部分。

3．2 状态转换算法
    在有限状态机中，是通过事件的驱动而进行状态转换的。状态转换算法的关键就在于查找下一状态在状态树中的位置，也就是在状态树中查找下一状态的时间复杂度的问题。与常规状态机不同，层次型状态机中的各个状态不仅存在互斥关系，还存在包含关系，特别是当前状态与下一状态关系就更为紧密了，不仅存在局部相关性，而且在很多情况下，它们之间在状态树中表现为兄弟节点关系。因此，要在状态树查找下一状态，需先查找当前节点的兄弟节点，再查找父节点的兄弟节点。如此循环，直到找到下一状态或试图查找根节点的兄弟节点(根节点没有父节点，所以要查找的下一状态是不存在的)。
    状态查找算法如下：

    有限状态机的一般状态转换过程是：系统首先执行exit_func退出当前状态，然后执行驱动此次状态转换的事件操作func，最后执行enter_func进入新状态。为了便于遍历状态树，系统为层次型有限状态机建立一个状态堆栈，堆栈中记录的数据是当前状态在状态树中对应的节点路径上所有节点(自身除外，因为没有必要人栈)的地址。堆栈的初始状态如图4所示，此时系统处于空闲S1状态，栈中只有根节点信息。在某个事件或一系列事件的驱动下(比如通过按键显示系统的当前日期)，系统将要从空闲状态转换到日期显示状态S4。从图3的自动售货机状态树可以看出，系统需要经过S1一S2一S3一S4的过程，中间的S2和S3是不可停留的状态。当按下管理键盘的“Time”键时，系统先执行exit_idle函数退出S1(空闲状态)，然后根据空闲状态的事件表得到下一状态编号，再通过状态查找算法搜索状态树，最后到达目的状态S4。S2与S3是两个中间状态，但是这两个状态节点的地址需要入栈。