返回首页 一步一步写算法

单词统计

在面试环节中,有一道题目也是考官们中意的一道题目:如果统计一段由字符和和空格组成的字符串中有多少个单词?

其实,之所以问这个题目,考官的目的就是想了解一下你对状态机了解多少。

(1) 题目分析

从题目上看,如果对一个字符串进行处理,那么可以有下面几种情形:初始状态,字符状态,空格状态,结束状态。那么这几种状态之间应该怎么迁移呢?

初始状态: 如果输入符号是空格,那么进入空格状态;如果是字符,那么就进入字符状态,同时单词个数+1;如果是结束状态,那么直接返回;

字符状态:如果输入符号是空格,那么进入空格状态;如果是字符,那么什么也不做;如果是结束,直接返回;

空格状态:如果输入符号是空格,那么什么也不做;如果是字符,那么进入字符状态,同时单词个数+1;如果结束状态,那么直接返回。

/*          输入是字符
*           -------->    字符状态 ----------
*          |                               | -->
*      初始状态  输入字符  |  |  输入空格            结束状态
*          |                                 -->
*          --------->    空格状态 ----------|
*            输入是空格
*/

(2)根据上面描述的状态迁移过程,编写对应的代码

typedef enum{
    INIT_STATE = 1,
    WORD_STATE,
    SPACE_STATE,
};

int count_word_number(const char* pStr)
{
    int count = 0;
    int state = INIT_STATE;
    char value ;

    if(NULL == pStr)
        return 0;

    while(value = *pStr++){
        switch (state)
        {
        case INIT_STATE:
            if(' ' != value)
                count ++, state = WORD_STATE;
            else
                state = SPACE_STATE;
            break;

        case WORD_STATE:
            if(' ' == value)
                state = SPACE_STATE;
            else if('
上一篇: 爬楼梯 下一篇: 选择排序