Как изменить мой код (hashtable + связанные списки), чтобы избежать утечек памяти? - PullRequest
Новая
       27

Как изменить мой код (hashtable + связанные списки), чтобы избежать утечек памяти?

0 голосов
/ 20 декабря 2018

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

Я написал код, который загружает словарь (txt файл) в хеш-таблицу / связанный списокСтруктура данных, программа компилирует и обеспечивает ожидаемые результаты, но Valgrind показывает утечки памяти.Все основные функции (создание узлов, заполнение, поиск, печать) работают нормально, кроме функции уничтожения (используется для освобождения памяти от malloc).Valgrind показывает утечки памяти.

Что мне здесь не хватает?Как сделать мой код чище?

Спасибо за ваше время!Вы великолепны!

Я знаю, что, по крайней мере, отчасти причина в моем подходе к заполнению структуры данных - я использую 2 буфера char * (tmp и tmp1, внутри и снаружи цикла) для манипулирования входами изfscanf в узлы.Я предполагаю, что во время выгрузки я могу использовать функцию «free» во внешнем буфере («tmp»), но не во внутреннем буфере («tmp1»).

Я попытался использовать 1 буфер (как внутри, так и снаружи)циклы) и 2 буфера инициализируются статически (char tmp []).Оба метода заполняют структуру всего одним словом (последнее в словаре). 

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

// определяют структуру узла 

typedef struct node
{
    char* word;
    struct node* next;
}node;

// переменная размера хеш-функции и хэш-функция (спасибо,K & R) 

const int hash_elements = 100;

unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
    hashval = *s + 31 * hashval;
    return hashval % hash_elements;
}

// функция для добавления узла в начало ll 

int addnode_start (node** head, char* word)
{
    node* new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        return 1;
    }
    new_node->word = word;
    new_node->next = *head;
    *head = new_node;
    return 0;
}

// функция для освобождения выделенной памяти 

void destroy (node* hashtable)
{
    if (hashtable == NULL)
    {
        return;
    }
    else
    {
        destroy(hashtable->next);
        free(hashtable);
    }
}

// MAIN FUNCTION- помещает строки слов из текстовых файлов в структуры данных хеш-таблиц / связанных списков 

int main (int argc, char* argv[])
{
    if (argc < 2)
    {
        printf("Usage: ./stringdll dictionary.txt\n");
        return 1;
    }

// создает массив для связанных списков (хеш-таблиц) и выделяет память для головок 

node* hashtable[hash_elements];
for (int i = 0; i < hash_elements; i++)
{
    hashtable[i] = malloc(sizeof(node));
    if (hashtable[i] == NULL)
    {
        return 1;
    }
}

//открыть файл словаря для чтения 

char* infile = argv[1];
FILE* input = fopen(infile, "r");
if (input == NULL)
{
    printf("File does not exist.\n");
    return 1;
}

// определить временное хранилище для строк 

char* tmp = malloc(41);

// проверить файл на наличие строк и заполнить связанные списки 

while(fscanf(input, "%s", tmp) != EOF)
{
    char* tmp1 = malloc(41);
    for (int h = 0; h < hash_elements; h++)
    {
        if (hash(tmp) == h)
        {
            if (hashtable[h]->word == '\0')
            {
                hashtable[h]->word = strcpy(tmp1, tmp);
                hashtable[h]->next = NULL;
            }
            else
            {
                int tmp_0 = addnode_start(&hashtable[h], strcpy(tmp1, tmp));
                if (tmp_0 == 1)
                {
                    return 1;
                }
            }
        }
    }
}

// unload Dictionary 

for (int d = 0; d < hash_elements; d++)
{
    destroy (hashtable[d]);
}

return 0;

}

Я ожидаю, что Valgrind покажет, что не было утечек памяти во время работы моей программы.

1 Ответ

0 голосов
/ 20 декабря 2018

Проблемы включают

  1. Ваша первоначальная инициализация хеш-таблицы сомнительна: 

    for (int i = 0; i < hash_elements; i++)
{
    hashtable[i] = malloc(sizeof(node));
    if (hashtable[i] == NULL)
    {
        return 1;
    }
}

    Вы выделяете пространство для узлов, ноВы не заполняете узлы действительными данными.Это распределение кажется совершенно бесполезным.Похоже, было бы не только проще, но и правильнее присвоить NULL элементам хеш-таблицы: 

    for (int i = 0; i < hash_elements; i++) {
    hashtable[i] = NULL;
}

    Из того, что я вижу в вашем другом коде, я думаю, что он справится даже с этим бездругие изменения.

  2. Непонятно, зачем вам нужно динамически выделять пространство для tmp.Похоже, вы не делаете с ним ничего, что потребовало бы динамического выделения - без определенной во время выполнения длины, без использования вне области его объявления, ... - так что, вероятно, было бы чище и проще объявить его как обычныймассив: 

    char tmp[41];

    Вы можете использовать эту версию tmp точно так же, как показывает ее использование сейчас, и вам не нужно ее освобождать.

  3. Вы динамически распределяете пространство для копии входного текста, но никогда не освобождаете ее.Указатели на эти пробелы первоначально записываются в tmp1, а затем присваиваются word членам ваших узлов.Поэтому вам не нужно или не нужно освобождать любое значение, хранящееся в tmp1, потому что вы все еще используете эти указатели, но ваша функция destroy() может и должна освобождать word каждого узла перед освобождением этого узла.

...