Найти k наиболее часто встречающихся слов из файла

// Программа для поиска k наиболее часто встречающихся слов в файле
#include <stdio.h>
#include <string.h>
#include <ctype.h>

  
# define MAX_CHARS 26
# define MAX_WORD_SIZE 30

  
// Узел Trie

struct TrieNode

{

    bool isEnd; // указывает конец слова

    unsigned frequency;  // количество вхождений слова

    int indexMinHeap; // индекс слова в minHeap

    TrieNode* child[MAX_CHARS]; // представляет 26 слотов каждый от 'a' до 'z'.

};

  
// Узел Min Heap

struct MinHeapNode

{

    TrieNode* root; // указывает на конечный узел TRIE

    unsigned frequency; // количество вхождений

    char* word; // фактическое слово сохранено

};

  
// Мин куча

struct MinHeap

{

    unsigned capacity; // общий размер кучи мин

    int count; // указывает количество заполненных слотов.

    MinHeapNode* array; // представляет коллекцию minHeapNodes

};

  
// Служебная функция для создания нового узла Trie
TrieNode* newTrieNode()
{

    // Выделим память для узла Trie

    TrieNode* trieNode = new TrieNode;

    // Инициализировать значения для нового узла

    trieNode->isEnd = 0;

    trieNode->frequency = 0;

    trieNode->indexMinHeap = -1;

    for( int i = 0; i < MAX_CHARS; ++i )

        trieNode->child[i] = NULL;

    return trieNode;

}

  
// Вспомогательная функция для создания Min Heap заданной емкости

MinHeap* createMinHeap( int capacity )

{

    MinHeap* minHeap = new MinHeap;

    minHeap->capacity = capacity;

    minHeap->count  = 0;

    // Выделить память для массива узлов с минимальной кучей

    minHeap->array = new MinHeapNode [ minHeap->capacity ];

    return minHeap;

}

  
// Вспомогательная функция для замены двух минимальных узлов кучи. Эта функция
// нужен в minHeapify

void swapMinHeapNodes ( MinHeapNode* a, MinHeapNode* b )

{

    MinHeapNode temp = *a;

    *a = *b;

    *b = temp;

}

  
// Это стандартная функция minHeapify. Это делает одну вещь дополнительно.
// Обновляет minHapIndex в Trie, когда два узла меняются местами
// в минимальной куче

void minHeapify( MinHeap* minHeap, int idx )

{

    int left, right, smallest;

    left = 2 * idx + 1;

    right = 2 * idx + 2;

    smallest = idx;

    if ( left < minHeap->count &&

         minHeap->array[ left ]. frequency <

         minHeap->array[ smallest ]. frequency

       )

        smallest = left;

    if ( right < minHeap->count &&

         minHeap->array[ right ]. frequency <

         minHeap->array[ smallest ]. frequency

       )

        smallest = right;

    if( smallest != idx )

    {

        // Обновляем соответствующий индекс в узле Trie.

        minHeap->array[ smallest ]. root->indexMinHeap = idx;

        minHeap->array[ idx ]. root->indexMinHeap = smallest;

        // Переставляем узлы в мин куче

        swapMinHeapNodes (&minHeap->array[ smallest ], &minHeap->array[ idx ]);

        minHeapify( minHeap, smallest );

    }

}

  
// Стандартная функция для построения кучи

void buildMinHeap( MinHeap* minHeap )

{

    int n, i;

    n = minHeap->count - 1;

    for( i = ( n - 1 ) / 2; i >= 0; --i )

        minHeapify( minHeap, i );

}

  
// Вставляем слово в кучу, функция обрабатывает 3 случая, описанных выше

void insertInMinHeap( MinHeap* minHeap, TrieNode** root, const char* word )

{

    // Случай 1: слово уже присутствует в minHeap

    if( (*root)->indexMinHeap != -1 )

    {

        ++( minHeap->array[ (*root)->indexMinHeap ]. frequency );

        // просачиваться вниз

        minHeapify( minHeap, (*root)->indexMinHeap );

    }

    // Случай 2: слово отсутствует и куча не заполнена

    else if( minHeap->count < minHeap->capacity )

    {

        int count = minHeap->count;

        minHeap->array[ count ]. frequency = (*root)->frequency;

        minHeap->array[ count ]. word = new char [strlen( word ) + 1];

        strcpy( minHeap->array[ count ]. word, word );

        minHeap->array[ count ]. root = *root;

        (*root)->indexMinHeap = minHeap->count;

        ++( minHeap->count );

        buildMinHeap( minHeap );

    }

    // Случай 3: слово отсутствует и куча заполнена. И частота слова

    // больше, чем root. Корень является наименее частым словом в куче,

    // заменить корень новым словом

    else if ( (*root)->frequency > minHeap->array[0]. frequency )

    {

        minHeap->array[ 0 ]. root->indexMinHeap = -1;

        minHeap->array[ 0 ]. root = *root;

        minHeap->array[ 0 ]. root->indexMinHeap = 0;

        minHeap->array[ 0 ]. frequency = (*root)->frequency;

        // удаляем ранее выделенную памятку и

        delete [] minHeap->array[ 0 ]. word;

        minHeap->array[ 0 ]. word = new char [strlen( word ) + 1];

        strcpy( minHeap->array[ 0 ]. word, word );

        minHeapify ( minHeap, 0 );

    }

}

  
// Вставляет новое слово в Trie и Heap

void insertUtil ( TrieNode** root, MinHeap* minHeap,

                        const char* word, const char* dupWord )

{

    // Базовый вариант

    if ( *root == NULL )

        *root = newTrieNode();

    // В слове еще больше символов

    if ( *word != '\0' )

        insertUtil ( &((*root)->child[ tolower( *word ) - 97 ]),

                         minHeap, word + 1, dupWord );

    else // полное слово обработано

    {

        // слово уже присутствует, увеличить частоту

        if ( (*root)->isEnd )

            ++( (*root)->frequency );

        else

        {

            (*root)->isEnd = 1;

            (*root)->frequency = 1;

        }

        // Вставить в мин кучу также

        insertInMinHeap( minHeap, root, dupWord );

    }

}

  
// добавить слово в Trie & min heap. Обертка над вставкой Util

void insertTrieAndHeap(const char *word, TrieNode** root, MinHeap* minHeap)

{

    insertUtil( root, minHeap, word, word );

}

  
// Вспомогательная функция для отображения результатов, минимальная куча
// содержит k наиболее часто встречающихся слов на данный момент, в любое время

void displayMinHeap( MinHeap* minHeap )

{

    int i;

    // печатаем верхнее слово K с частотой

    for( i = 0; i < minHeap->count; ++i )

    {

        printf( "%s : %d\n", minHeap->array[i].word,

                            minHeap->array[i].frequency );

    }

}

  
// Основная функция, которая принимает файл в качестве входных данных, добавляет слова в кучу
// и Trie, наконец, показывает результат из кучи

void printKMostFreq( FILE* fp, int k )

{

    // Создаем минимальную кучу размера k

    MinHeap* minHeap = createMinHeap( k );

    // Создать пустую Trie

    TrieNode* root = NULL;

    // Буфер для хранения одного слова за раз

    char buffer[MAX_WORD_SIZE];

    // Читаем слова одно за другим из файла. Вставьте слово в Три и Мин Хип

    while( fscanf( fp, "%s", buffer ) != EOF )

        insertTrieAndHeap(buffer, &root, minHeap);

    // Min Heap будет иметь k наиболее часто встречающихся слов, поэтому выведите узлы Min Heap

    displayMinHeap( minHeap );

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int k = 5;

    FILE *fp = fopen ("file.txt", "r");

    if (fp == NULL)

        printf ("File doesn't exist ");

    else

        printKMostFreq (fp, k);

    return 0;

}