统计单词个数

Forums: 

img: 

统计单词个数

这是一个描述灰常简单的题目,就是统计文件中的所有单词,以及出现的次数。这里不考虑标点符号等特殊字符的存在,认为文件中只有一个个的单词。题目说简单比较简单,就是统计一个文件中的单词数目,说复杂可能复杂些,比如单词数目很多,就应该考虑效率的问题;再者想象一下如果有成千上万个文件,这个时候的思路跟一个文件的思路就又大不一样勒。

简单做法

现在考虑简单的情形,统计一个文件中的单词数目。me 们线性组织一个单词薄,然后扫描文件;对于每个单词,首先在单词薄中顺序查找,如果找到那么对应的单词数目加 1,如果没有找到,在单词薄中添加一个新的单词并且数目置为 1 ,直到文件中的所有单词扫完。下面的程序就是采用这个思路,从 input.txt 中读取单词,统计,最后再对单词进行排序,然后按字母表顺序输出。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX 1000
  6. #define NMAX 100
  7.  
  8. typedef struct _tag_word_{
  9.     char word[MAX];
  10.     int n;
  11. }Word;
  12.  
  13. int cmp(const void *a, const void *b)
  14. {
  15.     Word *pa=(Word*)a, *pb = (Word*)b;
  16.     return strcmp(pa->word, pb->word);
  17. }
  18.  
  19. int main()
  20. {
  21.     char str[MAX];
  22.     Word words[NMAX];
  23.     int i, n = 0;
  24.    
  25.     freopen("input.txt", "r", stdin);
  26.     // freopen("output.txt", "w", stdout);
  27.    
  28.     while(scanf("%s", str) != EOF){
  29.         for(i=0; i<n; ++i)
  30.             if(strcmp(str, words[i].word) == 0)
  31.                 break;
  32.        
  33.         if(i>=n){
  34.            strcpy(words[n].word, str);    // words[n] <-- str
  35.            words[n].n = 1;
  36.            ++n;
  37.         }else{
  38.             ++words[i].n;
  39.         }
  40.     }
  41.    
  42.     qsort(words, n, sizeof(Word), cmp);    // sort
  43.    
  44.     printf("word count : %d\n", n);
  45.     for(i=0; i<n; ++i){
  46.         printf("%s : %d\n", words[i].word, words[i].n);
  47.     }
  48.     return 0;
  49. }

c 程序对于描述算法来说很好,但是对于一个实际的程序来说使用 c 就不大理想了。比如上面的,假定单词的长度不超过 1000,单词的数目不超过 100,这样的假定注定对于有些输入就会出现 bug 。所以使用 c++ 会更好些,使用 string 和 vector 或是 list。为嘛不用 java 呢,因为不想用 java,O__O"…。

c++实现:统计文件中单词的个数

前面 c 程序的思路比较底层, 几乎不借助复杂的数据结构。 but, 现在几乎所有语言都有提供诸如 map (tree map/hash map) 这样的结构,使用这种结构省去了我们去搜索一个单词是否存在的过程。再者, c 过于底层, 很多类型使用并不方便,也不安全,比如上面的 word 字符数组, 长度设的长了浪费,短了就可能溢出。

下面是 c++ 的统计单词个数的程序, 供学习和参考用。

  1. #include <iostream>
  2. #include <fstream>
  3. #include <unordered_map>
  4. using namespace std ;
  5.  
  6. int  main()
  7. {
  8.     ifstream ifile("input.txt");    // 文件输入流
  9.     string word;
  10.     unordered_map<string, int> dic;    // 字典 dic, key-value 对
  11.    
  12.     while(ifile >> word){    // 找到一个单词 word
  13.         ++dic[word];    // 对应的单词个数 +1
  14.     }
  15.    
  16.     for(auto item : dic){    // 输出统计结果
  17.         cout << item.first << " " << item.second << '\n';    // 输出 key 和 value
  18.     }
  19.    
  20.     return 0;
  21. }      

补充说明: c++ 提供了的 map 实际上 tree map, 这里使用的 unordered_map 实际上是 hash map, 使用方法一样,底层实现不一样。

精诚所至,金石为开