用于状态机

在哪些编程领域我会使用状态机？为什么？我怎么能实现一个？

编辑:请提供一个实际的例子,如果它没有太多要求.

1> Adam Liss..：

---

在哪些编程领域我会使用状态机？

使用状态机来表示可以存在于有限数量的条件(" 状态 ")中的(实际或逻辑)对象,并根据一组固定的规则从一个状态前进到下一个状态.

我为什么要使用状态机？

状态机通常是表示一组复杂规则和条件以及处理各种输入的非常紧凑的方式.您将在嵌入式设备中看到内存有限的状态机.实现得很好,状态机是自我记录的,因为每个逻辑状态代表一个物理条件.状态机可以被实施在一个微小的代码量相对于其程序等效和非常有效地运行.此外,管理状态变化的规则通常可以作为数据存储在表中,从而提供易于维护的紧凑表示.

我该如何实现？

琐碎的例子:

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

笔记:

为简单起见,该示例使用switch()带有显式case/ break状态的a .在实践中,一个case经常会"堕落"到下一个州.

为了便于维护大型状态机,case可以将每个中完成的工作封装在"工作"功能中.获取顶部的任何输入while(),将其传递给worker函数,并检查worker的返回值以计算下一个状态.

为了紧凑,整个switch()可以用函数指针数组替换.每个状态由一个函数体现,其返回值是指向下一个状态的指针. 警告:这可以简化状态机或使其完全不可维护,因此请仔细考虑实现!

嵌入式设备可以实现为仅在灾难性错误时退出的状态机,之后它执行硬重置并重新进入状态机.

---

我的荣幸.请注意,没有检查除零.如果你没有朋友,你应该花更多时间远离StackOverflow.:-)

2> Konrad Rudol..：

---

一些很好的答案已经.对于稍微不同的视角,请考虑在较大的字符串中搜索文本.有人已经提到了正则表达式,这实际上只是一个特例,虽然是一个重要的例子.

考虑以下方法调用:

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

你会如何实施find_in_string？简单的方法将使用嵌套循环,如下所示:

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

除了这是低效的事实,它形成一个状态机!这里的州有点隐藏; 让我稍微重写代码,使它们更加明显:

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

这里的不同状态直接代表我们搜索的单词中的所有不同位置.图中的每个节点都有两个转换:如果字母匹配,则转到下一个状态; 对于每个其他输入(即当前位置的每隔一个字母),返回到零.

这种轻微的重新制定具有巨大的优势:现在可以使用一些基本技术调整它以产生更好的性能.事实上,每个高级字符串搜索算法(暂时折扣索引数据结构)都建立在这个状态机之上,并改进了它的某些方面.

3> EvilTeach..：

---

什么样的任务？

任何任务,但从我所看到的,任何类型的解析经常被实现为状态机.

为什么？

解析语法通常不是一项简单的任务.在设计阶段,绘制状态图以测试解析算法是相当普遍的.将其转换为状态机实现是一项相当简单的任务.

怎么样？

嗯,你只受你想象力的限制.

我已经看到它用case语句和循环完成了.

我已经看过标签和goto语句

我甚至看到它用表示当前状态的函数指针结构完成.当状态改变时,更新一个或多个函数指针.

我已经看到它仅在代码中完成,其中状态的更改仅意味着您在不同的代码段中运行.(没有状态变量,必要时还有redundent代码.这可以作为一种非常简单的排序来演示,这对于非常小的数据集非常有用.

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

没有状态变量,但代码本身代表状态

4> Federico A. ..：

---

的状态的设计模式是一种面向对象的方式由有限状态机的方式来表示的对象的状态.它通常有助于降低该对象实现的逻辑复杂性(嵌套if,许多标志等)

---

该模式的缺点是它有可能为您的项目添加爆炸性的类,使得不清楚究竟发生了什么以及状态转换的流程是什么.

5> Maxam..：

---

大多数工作流程都可以实现为状态机.例如,处理离开应用程序或订单.

如果您使用的是.NET,请尝试使用Windows Workflow Foundation.您可以使用它快速实现状态机工作流程.