C утечка памяти при вставке в двусвязный список - PullRequest
Новая
       58

C утечка памяти при вставке в двусвязный список

0 голосов
/ 02 апреля 2020

Привет, я новичок в C и указателях, и у меня возникают проблемы при попытке реализовать структуру двусвязных списков ниже. Утечки памяти произошли в списке InsertEnd я верю? Я очень смущен тем, почему одна работа (по крайней мере, нет утечки памяти на выходе), а другая - нет. Я вставил только части программы, любая помощь или объяснение очень ценится. 

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

typedef struct node *Node;
struct node {
    int value;
    Node next;
    Node prev;
};

typedef struct list *List;
struct list {
    Node first;
    Node last;
    int count;
};

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

Ответы [ 2 ]

1 голос
/ 02 апреля 2020

Прежде всего, речь идет об утечках памяти: в вашем коде нет прямой утечки памяти. Если утечка происходит где-то, это за пределами этих функций. Скорее всего, это потому, что вы создаете один или несколько узлов, а затем забываете free() их, но это не имеет ничего общего с двумя отображаемыми вами функциями.

Я вижу, что вы используете typedef для объявления простых типы указателей, взгляните на этот вопрос и ответьте, чтобы понять, почему это плохая практика, и ее следует избегать: Является ли хорошей идеей вводить указатели по умолчанию? . Кроме того, этот конкретный кусок из Linux документации ядра, который объясняет проблему более подробно.

Во-вторых, реальная проблема в показанном вами коде состоит в том, что вы используете указатели после того, как вы проверили что они недействительны (NULL).

Здесь: 

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
//  ^^^^^^^^ BAD!

А также здесь: 

if (newList== NULL) {
    newList->first = newList->last = n;
//  ^^^^^^^^^^^^^^ BAD!

Если что-то равно NULL, вы не можете разыменовать Это. Измените ваши функции, чтобы безопасно прервать их после обнаружения недопустимого указателя.

Это можно сделать несколькими способами. Вот пример правильного кода: 

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "couldn't create new node\n");
        return NULL;
    }

    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n;

    if (newList == NULL) {
        return;
        // You probably want to return some error value here.
        // In that case change the function signature accordingly.
    }

    n = newNode(value);

    if (newList->count == 0) {
        newList->first = newList->last = n;
    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }

    newList->count++;
}

ПРИМЕЧАНИЕ: проверка newList->count == 0 предполагает, что вы правильно увеличиваете / уменьшаете счет при добавлении / удалении элементов.

1 голос
/ 02 апреля 2020

Это объявление typedef 

typedef struct node *Node;

сбивает с толку и представляет плохой стиль. Рассмотрим, к примеру, это утверждение 

Node n = malloc(sizeof(*n));

, кто-то может подумать, что это опечатка и должно быть написано 

Node *n = malloc(sizeof(*n));

Функция 

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

имеет неопределенное поведение. Если newList равен NULL, то вы пытаетесь использовать память, указанную нулевым указателем. 

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

И первоначально элементы данных newList->first и newList->last могут быть равны NULL. Это также может быть причиной неопределенного поведения, потому что функция не учитывает это.

Перед изменением функции listInsertEnd вы должны определить функцию newNode следующим образом 

Node newNode(int value) 
{
    Node n = malloc(sizeof(*n));

    if ( n != NULL )
    {
        n->value = value;
        n->next = NULL;
        n->prev = NULL;
    }

    return n;
}

Функция не должна выдавать никаких сообщений. Вызывающая функция решает, следует ли выдавать сообщение, если оно требуется.

В этом случае функцию listInsertEnd можно записать следующим образом: 

int listInsertEnd(List newList, int value) 
{
    Node n = newNode(value);
    int success = n != NULL;

    if ( success )
    {
        n->prev = newList->last;  

        if ( newList->first == NULL )
        {
            newList->first = newList->last = n;
        }
        else
        {
            newList->last = newList->last->next = n;
        }

        ++newList->count;
    }

    return success;
}

В пределах main вы должны создать список следующим образом 

int main( void )
{
    struct list list1 = { .first = NULL, .last = NULL, .count = 0 };
    // or
    // struct list list1 = { NULL, NULL, 0 };

и вызвать функцию как 

listInsertEnd) &list1, some_integer_value );
...