(13条消息) 有限状态机详解（转载） / 四六文摘

以前总觉得有限状态机和无限状态机非常的难理解，原来也就是自己一直没有一个直观的认识，今天看到一篇博客，总算对有限状态机入门了。一看就懂。

转载地址：http://blog.csdn.net/zqixiao_09/article/details/50239337

我们知道，一般编写程序时都要画出流程图，按照流程图结构来编程，如果编写一个比较繁琐，容易思维混乱的程序时，我们可以利用有限状态机模型画出一个状态转移图，这样便可以利用画出的逻辑图来编写程序，简洁且不易出错。
那什么是有限状态机是什么意思呢？百度百科上这样解释：
有限状态机，（英语：Finite-state machine, FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

常见的计算机就是使用有限状态机作为计算模型的：对于内存的不同状态，CPU通过读取内存值进行计算，更新内存中的状态。CPU还通过消息总线接受外部输入设备（如键盘、鼠标）的指令，计算后更改内存中的状态，计算结果输出到外部显示设备（如显示器），以及持久化存储在硬盘。
电脑游戏设计中也经常使用有限状态机模型。以水果忍者游戏为例，游戏中水果的状态是有限状态，其运行轨迹是由模拟物理运动规律的计算公式运算而成的，一个香蕉抛起来后会按照抛物线运行，其每一帧位置变化都是一个状态的改变，状态改变通过计算公式来决定。当然作为游戏不会仅仅这么简单，如果这么简单就是动画了，游戏还有复杂的人机交互事件，比如用手在屏幕上“切”了水果，水果感知到这个事件后，会按照程序逻辑进入爆炸状态。

简单知道其定义是没有用的，在C编程中我们改如何应用呢？

例题1：去除一个字符串中连续的空格，即Ｈ＿＿ｅｌ＿＿＿ｌｏ　变成　Ｈ＿ｅｌ＿ｌｏ；

我们拿到这道题时，可能会想到用getchar()依次取字符，当遇到空格时，继续下一个字符是否为空格，如果是则删除，如果不是则继续；那么问题来了，如果空格后面还有空格呢？如果还有很多空格呢？如果还有其他要求呢？这样很容易造成思维混乱，所以这时我们可以用到有限状态机模型，好像这样说很模糊啊，该怎么使用呢？利用这种方式，最后的就是利用好flag,即标识符；这样吧，我们来画一下这个模型：

这样看好像有点抽象，我来解释一下：
状态0 (flag = 0)若当前字符是空格，输出并跳转到状态1(flag = 1),如果是非空格，则打印字符；
状态1 (flag = 1) 若当前字符为非空格，则输出并跳转到状态0，若是空格，则不打印；
下面几个例题我尽量写得清楚；

我们按照这种逻辑来写程序，看看是不是比较方便，代码如下：

#include <stdio.h>  

int main(int argc, char *argv[])
{
    char flag = 0;
    int ch;
    while((ch = getchar()) != EOF)
    {
        switch(flag)
        {
        case 0:
            if(ch == ' ')
                flag = 1;
            putchar(ch);
            break;
        case 1:
            if(ch == ' ')
                continue;
            flag = 0;
            putchar(ch);
            break;
        default:
            break;
        }
    }
    return 0;
}

程序执行结果如下：

[cpp] view plain copy
fs@ubuntu:~/qiang/char1$ gcc -o test test.c
fs@ubuntu:~/qiang/char1$ ./test
H  el   lo
H el lo

效果很明显；

上面的例题还算简单吧，好像不用这个模型也可以是吧，那好，我们再来一题

例题2：除连续的空格但字符串中的连续空格不变，比如Ｈ_ _ｅｌ＿＿＂ｗｏｒ＿＿＿ｌｄ＂＿＿＿ｌｏ；
大家看看，如果直接写程序是不是很烦，一会就乱掉了，那我们还用这个模型来编写，还是先画图：

#include <stdio.h>  

int main(int argc, char *argv[])
{
    char flag = 0;
    int ch;
    while((ch = getchar()) != EOF){
        switch(flag){
        case 0:
            if(ch == ' ')
                flag = 1;
            if(ch == '"')
                flag = 2;
            putchar(ch);
            break;
        case 1:
            if(ch != ' '){
                flag = 0;
                if(ch == '"')
                    flag = 2;
                putchar(ch);
            }
            break;
        case 2:
            if(ch == '"')
                flag = 0;
            if(ch == '\"')
                ch = '"';
            putchar(ch);
            break;
        default:
            printf("error!\n");
            break;
        }
    }
    return 0;
}

执行结果如下：

[cpp] view plain copy
fs@ubuntu:~/qiang/char1$ ./char3
H  el  "wor   ld"   lo
H el "wor   ld" lo

来个实际点的问题：
例题３：:除单行注释
示例程序：

/*******this is program*****/
#include <stdio.h>
int main()
{
    printf("Hello world!\n");//Hello world!
}

将这段程序中的单行注释去掉，继续画图：

编写程序如下：

#include <stdio.h>  

int main(void)
{
    char flag = 0;
    char ch;
    while((ch = getchar()) != EOF)
    {
        switch(flag)
        {
        case 0:
            if(ch == '/')
                flag = 1;
            else
                putchar(ch);
            break;
        case 1:
            if(ch == '/'){
                flag = 2;
            }
            else{
                putchar('/');
                putchar(ch);
            }
            break;
        case 2:
            if(ch == '\n')
            {
                flag = 0;
                putchar(ch);
            }
            break;
        default:
            break;
        }  

    }
}

执行命令：

fs@ubuntu:~/qiang/char1$ ./quzhushi1 < test.c >result.c

注意命令中用到的重定向，将test.c文件重定向到quzhushi1 中，输出结果重定向到 result.c中

可查看result.c中：

/*******this is program*****/
#include <stdio.h>
int main()
{
    printf("Hello world!\n");//Hello world!
}

单行注释被删除。

例题4：去除单行注释和多行注释
还是这个测试程序：

/*******this is program*****/
#include <stdio.h>
int main()
{
    printf("Hello world!\n");//Hello world!
}

好吧，继续画图，图上比较抽象，大家可以自己思考一下
这次比较复杂，要有5个标识符

测试代码如下：

#include <stdio.h>  

int main()
{
    char ch;
    int flag = 0;
    while((ch = getchar()) != EOF)
    {
        switch(flag)
        {
            case 0:
                if(ch == '/')
                    flag = 1;
                else
                    putchar(ch);
                break;  

            case 1:
                if(ch == '/')
                    flag = 2;
                else if(ch == '*')
                    flag = 3;
                else
                {
                    flag = 0;
                    putchar('/');
                    putchar(ch);
                }
                break;  

            case 2:
                if(ch == '\n')
                {
                    putchar(ch);
                    flag = 0;
                }
                break;  

            case 3:
                if(ch == '*')
                    flag = 4;
                break;  

            case 4:
                if(ch == '/')
                    flag = 0;
                else
                    flag = 3;
                break;
        }
    }
}

执行命令：

fs@ubuntu:~/qiang/char1$ ./quzhushi < test.c >result.c

执行结果：

/*******this is program*****/
#include <stdio.h>
int main()
{
    printf("Hello world!\n");//Hello world!
}

大家可以比较画的图与所写程序，这种方法可以使我们编写程序时有个很好的思路！

(13条消息) 有限状态机详解（转载）

相关推荐