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

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

Например, входная строка "ab bc bc" будет генерировать следующий вывод:

bc : 2
ab : 1

Проблема будет легко решена, если используются структуры данных C++, такие как карта. Но если проблема может быть решена только в обычном старом C, это выглядит намного сложнее.

Какие структуры данных и алгоритмы я буду использовать здесь? Пожалуйста, будьте настолько конкретными, насколько возможно. Я слабы в DS и Algo. :-(

3 ответа

Вот пример того, как я это сделаю. Поиск в 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 \**** this \r\ncan work *** 456 it can";
 countWords(text);
}
</stdlib.h></assert.h></stdio.h>


Одна структура данных, которую вы можете использовать, - это простое двоичное дерево, содержащее слова, которые вы могли бы сравнить с помощью strcmp. (На данный момент я буду игнорировать проблемы с делами).

Вам нужно будет убедиться, что дерево остается сбалансированным по мере его роста. Для этого найдите AVL деревья или 1-2 дерева или красно-черные деревья на википедию или в другом месте.

Я не буду давать слишком много деталей, кроме того, чтобы создать двоичную древовидную структуру, каждый узел имел бы левый и правый подузел, который мог бы быть нулевым, а для листового узла оба суб-узла равны нулю. Чтобы упростить использование "интрузивного" узла, который имеет значение и два под-узла. Что-то вроде:

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

и, очевидно, C, вам нужно сделать все управление памятью.

У вас будет функция, которая повторяет дерево, сравнивая и перемещаясь влево или вправо по мере необходимости. Если будет найдено, это будет просто вверх по частоте. Если не ваша функция должна быть в состоянии определить место, где нужно вставить узел, а затем логика вставки и перебалансировки. Конечно, новый узел будет содержать слово с частотой 1.

В конце вам понадобится способ рекурсии через ваше дерево, распечатывающее результаты. В вашем случае это может быть рекурсивная функция.

Обратите внимание, что альтернативная структура данных будет какой-то хэш-таблицей.

Если вы ищете наиболее эффективное решение и у вас много памяти, вы должны использовать структуру данных, посредством которой вы будете проходить через каждую букву по мере ее возникновения. Таким образом, "a" дает вам все слова, начинающиеся с a, затем переходите ко второй букве, которая является "b" и т.д. Это довольно сложно реализовать для тех, кто не знает структуры данных, поэтому я бы посоветовал вам пойти с простым двоичным деревом.

Обратите внимание, что при распечатке это не будет в обратном порядке частоты, поэтому вам придется сначала отсортировать результаты. (В C++, используя карту, вы также не получили бы их в этом порядке).


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

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

licensed under cc by-sa 3.0 with attribution.