C语言频率统计（非C++）

Question

给定一个由单个空格分隔的单词组成的字符串，按照它们出现在字符串中的次数排序，以降序打印单词。

例如“AB BC BC”的输入串将产生以下输出：

bc : 2 
ab : 1 

这个问题将如果C++的数据结构，如地图，使用可以容易地得到解决。但是，如果问题只能在普通的老C中解决，那看起来就更难了。

我应该在这里使用什么样的数据结构和算法？请尽可能详细。我在DS和Algo方面很弱。 :-(

Answer 1

下面是如何我做一个样本。 findWord（）中的搜索可以被优化。分配数量也可以通过分配文字块而不是一次一个来减少。也可以为这种情况实现一个链表。它缺少内存释放。这应该有希望让你去。

#include <stdio.h> 
    #include <assert.h> 
    #include <stdlib.h> 

    #define MAXWORDLEN 128 

    const char* findWhitespace(const char* text) 
    { 
     while (*text && !isspace(*text)) 
      text++; 
     return text; 
    } 

    const char* findNonWhitespace(const char* text) 
    { 
     while (*text && isspace(*text)) 
      text++; 
     return text; 
    } 

    typedef struct tagWord 
    { 
     char word[MAXWORDLEN + 1]; 
     int count; 
    } Word; 

    typedef struct tagWordList 
    { 
     Word* words; 
     int count; 
    } WordList; 

    WordList* createWordList(unsigned int count); 

    void extendWordList(WordList* wordList, const int count) 
    { 
     Word* newWords = (Word*)malloc(sizeof(Word) * (wordList->count + count)); 
     if (wordList->words != NULL) { 
      memcpy(newWords, wordList->words, sizeof(Word)* wordList->count); 
      free(wordList->words); 
     } 
     for (int i = wordList->count; i < wordList->count + count; i++) { 
      newWords[i].word[0] = '\0'; 
      newWords[i].count = 0; 
     } 
     wordList->words = newWords; 
     wordList->count += count; 
    } 

    void addWord(WordList* wordList, const char* word) 
    { 
     assert(strlen(word) <= MAXWORDLEN); 
     extendWordList(wordList, 1); 
     Word* wordNode = &wordList->words[wordList->count - 1]; 
     strcpy(wordNode->word, word); 
     wordNode->count++; 
    } 

    Word* findWord(WordList* wordList, const char* word) 
    { 
     for(int i = 0; i < wordList->count; i++) { 
      if (stricmp(word, wordList->words[i].word) == 0) { 
       return &wordList->words[i]; 
      } 
     } 
     return NULL; 
    } 

    void updateWordList(WordList* wordList, const char* word) 
    { 
     Word* foundWord = findWord(wordList, word); 
     if (foundWord == NULL) { 
      addWord(wordList, word); 
     } else { 
      foundWord->count++; 
     } 
    } 

    WordList* createWordList(unsigned int count) 
    { 
     WordList* wordList = (WordList*)malloc(sizeof(WordList)); 
     if (count > 0) { 
      wordList->words = (Word*)malloc(sizeof(Word) * count); 
      for(unsigned int i = 0; i < count; i++) { 
       wordList->words[i].count = 0; 
       wordList->words[i].word[0] = '\0'; 
      } 
     } 
     else { 
      wordList->words = NULL; 
     } 
     wordList->count = count;  
     return wordList; 
    } 

    void printWords(WordList* wordList) 
    { 
     for (int i = 0; i < wordList->count; i++) { 
      printf("%s: %d\n", wordList->words[i].word, wordList->words[i].count); 
     } 
    } 

    int compareWord(const void* vword1, const void* vword2) 
    { 
     Word* word1 = (Word*)vword1; 
     Word* word2 = (Word*)vword2; 
     return strcmp(word1->word, word2->word); 
    } 

    void sortWordList(WordList* wordList) 
    { 
     qsort(wordList->words, wordList->count, sizeof(Word), compareWord); 
    } 

    void countWords(const char* text) 
    { 
     WordList *wordList = createWordList(0); 
     Word  *foundWord = NULL; 
     const char *beg = findNonWhitespace(text); 
     const char *end; 
     char  word[MAXWORDLEN]; 

     while (beg && *beg) { 
      end = findWhitespace(beg); 
      if (*end) { 
       assert(end - beg <= MAXWORDLEN); 
       strncpy(word, beg, end - beg); 
       word[end - beg] = '\0'; 
       updateWordList(wordList, word); 
       beg = findNonWhitespace(end); 
      } 
      else { 
       beg = NULL; 
      } 
     } 

     sortWordList(wordList); 
     printWords(wordList); 
    } 

int main(int argc, char* argv[]) 
{ 
    char* text = "abc 123 abc 456 def 789 \tyup this \r\ncan work yup 456 it can"; 
    countWords(text); 
} 

Answer 2

，你可以使用一个数据结构，其中包含您可以比较使用的strcmp（我会忽略大小写问题现在）。也就是说一个简单的二进制树

您需要确保树保持平衡你可以看到AVL树或1-2棵树或维基百科或其他地方的红黑树

我不会给出太多的细节，除了要创建一个二叉树结构，每个结点都会有一个可能为空的左右子节点，对于一个叶子节点，两个子节点都是空的。为了使它更简单，使用具有该值和两个子节点的“侵入式”节点，如：

struct Node 
{ 
    char * value; 
    size_t frequency; 
    struct Node * left; 
    struct Node * right; 
}; 

和显然是C你需要做所有的内存管理。

您将有一个函数向下递归树，根据需要进行比较和向左或向右移动。如果发现它会提高频率。如果不是，你的函数应该能够确定插入节点的位置，然后插入和重新平衡逻辑。当然，新节点将包含频率为1的字。

最后，您将需要一种方法来通过树来打印结果。在你的情况下，这可以是一个递归函数。

请注意，替代数据结构会是某种散列表。

如果您正在寻找最高效的解决方案并且手头有大量内存，那么您将使用一种数据结构，从而在您遇到它时分行浏览每个字母。所以“a”给你所有以a开头的单词，然后转到第二个字母“b”等等。对于不知道数据结构的人来说实现起来相当复杂，所以我建议你去用简单的二叉树。

请注意，在打印时，它不会与频率相反，因此您必须先对结果进行排序。 （在使用C++的地图中，你也不会按顺序得到它们）。

Answer 3

我会为此使用三元树。其中数据结构由乔恩·本特利和罗伯特·塞奇威克介绍下面的文章有一个例子C.

http://www.cs.princeton.edu/~rs/strings/