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

Question

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

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

bc : 2
ab : 1

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Answer 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 \tyup this \r\ncan work yup 456 it can";
    countWords(text);
}