Должен ли я выделить память для дерева внутри или снаружи вызывающей функции? - PullRequest
Новая
       16

Должен ли я выделить память для дерева внутри или снаружи вызывающей функции?

0 голосов
/ 17 сентября 2018

Я реализую структуру данных trie в C для слов в большом словаре. Словарь содержит строки в следующем формате: 

abacus
babble
cabal
....

Я определяю и выделяю память для дерева вне функции load. load читает каждое слово из словаря и вставляет каждый символ в позицию массива children[27] внутри каждого node. Индексы от 0 до 25 предназначены для символов от a до z и символа апострофа ' в позиции 26.

Проблема в том, что я не знаю, следует ли мне создавать и выделять память для верхнего уровня trie внутри или вне вызывающей функции. Я буду освобождать память, используя другую функцию unload после того, как я закончу использовать три. Я не могу изменить функцию main, поэтому я не уверен, что после ее завершения утечки памяти не будет.

Вот код: 

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// trie data structure for 26 letters and apostrophe
typedef struct node
{
    bool is_word;
    struct node *children[27];
} node;

// allocate memory for trie top level and set them to 0
node *root = calloc(1, sizeof(node));

// loads dictionary into memory, return true if successful
bool load(const char *dictionary)
{
    // open input file
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
        return false;

    int p;    // trie index position
    char c;   // current char

    // scan dictionary word by word
    while (fscanf(fp, "%s", word) != EOF)
    {
        // set head pointer to point to root
        node *head = root;

        // loop through current word
        for (int i = 0; i < strlen(word); i++)
        {
            c = word[i];

            // ASCII to alphabet position, apostrophe last index
            if (isalpha(c))
                p = c - 'a';
            else if (c == '\'')
                p = 26;

            // allocate memory and point head to new node
            if (head->children[p] == NULL)
            {
                head->children[p] = calloc(1, sizeof(node));
                head = head->children[p];
            }
            // otherwise point head to children
            else if (head->children[p] != NULL)
                head = head->children[p];
        }
        // complete word, set flag to true
        head->is_word = true;
    }
    // finished
    fclose(fp);
    return true;
}
...