Статистика частоты слов в C (не C++)

Question

Если строка состоит из слов, разделенных одним пробелом, распечатайте слова в порядке убывания, отсортированные по количеству раз, которые они появляются в строке.

Например входная строка «AB» Ьса Ьса будет генерировать следующий вывод:

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

Для этого я бы использовал тройное дерево. В следующей статье, где структура данных вводится Jon Bentley и Седжвик есть пример в С.

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