Освобождение временного узла при добавлении в связанный список - PullRequest
Новая
       46

Освобождение временного узла при добавлении в связанный список

0 голосов
/ 14 июня 2019

У меня есть функция с именем addMod, которая при вызове добавляет узел к определенному индексу массива Module struct LinkedLists с именем modules, содержащегося в структуре System. Структура Module имеет строковое поле, два поля типа int и указатель на следующий Module, причем первые три поля инициализируются в соответствии с аргументами, указанными в addMod. addMod примерно выглядит так: 

int addMod(System *system, const char *text, int num1, int num2, int index) {
    Module *temp = malloc(sizeof(Module));
    Module *current;
    temp->next = NULL;

    if ([any of the constructors are invalid]) return 0;

    temp->text = malloc(strlen(text)+1);
    strcpy(temp->text, text);
    temp->num1 = num1; temp->num2 = num2;

    if (!system->modules[index]) {
        system->modules[index] = temp; //If there are no modules in the LinkedList at the given index, makes the head = temp.
    }
    else {
        if (system->compare(temp, system->modules[index]) <= 0) { //compare is a func pointer field of system that compares two Modules to see in what order they should be. Here, we check if temp should become the head of modules[index].
            temp->next = system->modules[index]; //Assigns the current head as the module following temp.
            system->modules[index] = temp; //Makes temp the current head.
        }
        else {
            current = system->modules[index];
            while (current->next && system->compare(temp, current->next) > 0) { //While current isn't the last node in the LinkedList and temp comes after the node after current
                current = current->next;
             }
            temp->next = current->next; //Adds temp in between current and current->next.
            current->next = temp;
        }
    }
    return 1;
}

Все вышеперечисленное работает должным образом, за исключением того, что при печати содержимого system консоль указывает, что есть утечка памяти, которую я предполагаю, потому что я не могу должным образом освободить temp на основании того, что мне говорит valgrind. Моя проблема в том, что я не знаю, где его освободить - кажется, что где бы я ни находился, это вызывает ошибку после печати содержимого. Насколько я понимаю, я должен убедиться, что никакие другие переменные не зависят от значения, содержащегося в temp, но я не могу найти способ сделать это с учетом каждого возможного окончания моего оператора if, приводящего к присваиванию temp до узла в modules. Помещение free(temp) между логикой и return 1 также приводит к segfault, я полагаю, потому что я часто снова вызываю malloc temp при многократном вызове addMod.

Таким образом, чтобы добавить новый узел в LinkedList, который может быть заполнен или не заполнен, в котором этот новый узел может быть вставлен в любую произвольную позицию в LinkedList, мне нужно выделить память для временного узла, чтобы я мог могу вставить его позже. Где мне освободить эту выделенную память после того, как я успешно вставил узел?

1 Ответ

1 голос
/ 14 июня 2019

Предполагая, что вы управляете экземпляром System нормально (большое предположение, поскольку я не могу увидеть этот код), у вас есть гигантская дыра в распределении памяти temp с последующим жестким return 0 в состоянии, гдепроверка "конструктор" не проходит.Более конкретно: 

Module *temp = malloc(sizeof(Module)); // memory allocated here...
Module *current;
temp->next = NULL;

if ([any of the constructors are invalid]) 
    return 0; // and leaked here.

Это может быть так же просто, как обмен чека.Очевидно, что другой код, который должен освободить динамические выделения, также должен быть рассмотрен и оценен.

Более простой подход

Код добавления узла сложный и это не должно быть.В конце концов, все, что вам действительно нужно, это найти место, где находится ваш новый узел.

  1. Если слот в таблице пуст, это первый узел в этом списке.
  2. Если слот в таблице НЕ пуст, найдите отсортированное местоположение и вставьте его туда..

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

Это сделано так.Обратите внимание, что большая часть этого кода просто делает объект Module безопасным.Фактическая вставка - это всего лишь один цикл while и несколько назначений указателей.Предполагается, что таблица в System изначально содержит NULL-записи: 

int addMod(System *system, const char *text, int num1, int num2, int index)
{
    // allocate new node here
    Module *temp = malloc(sizeof *temp);
    if (temp == NULL)
    {
        perror("Failed to allocate new Module");
        return 0;
    }


    size_t len = strlen(text);
    temp->text = malloc(len + 1);
    if (temp->text == NULL)
    {
        perror("Failed to allocate module name");
        free(temp);
        return 0;
    }

    // finish copying member data
    memcpy(temp->text, text, len);
    temp->text[len] = 0;
    temp->num1 = num1;
    temp->num2 = num2;

    // now find where it belongs, and set next appropriately    
    Module **pp = system->modules + index;
    while (*pp && system->compare(temp, *pp) <= 0)
        pp = &(*pp)->next;

    temp->next = *pp;
    *pp = temp;
    return 1;
}

Поймите, что это получается из того, как я думаю ваш System тип выглядит так, как он никогда не был представлен:

typedef struct System
{
    Module *modules[MAX_MODULES];
    int (*compare)(const Module* lhs, const Module *rhs);

} System;

Я вполне уверен, что это похоже на это.Конечно, вам придется адаптироваться, если это не так.Я предлагаю вам просмотреть это и пройти через это в отладчике.Ничто не заменит его в прямом эфире.

Удачи.

...