一步一步写算法（之单词统计）

dafengkuang lv.1

发布时间：2023-09-20 00:14:46 230

相关标签：

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

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

（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('\0' == *pStr)
        return count;
        
      break;

    case SPACE_STATE:
      if(' ' != value)
        count ++, state = WORD_STATE;
      else if('\0' == *pStr)
        return count;
      
      break;

    default:
      break;
    }
  }

  return count;
}

（3）编写测试用例，验证代码是否编写正确

void test()
{
  assert(0 == count_word_number(NULL));
  assert(0 == count_word_number(""));
  assert(1 == count_word_number("hello"));
  assert(3 == count_word_number("china baby hello"));
}

总结：

1）状态机是编程人员的基本功，它和另外一种方法回调函数注册一样，使我们在日常开发中经常用到的一种方法

2）状态机是计算机网络通信的重要内容，想要对tcp-ip协议栈加深了解的朋友尤其需要重点掌握

文章来源： https://blog.51cto.com/u_15888909/5880539

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。