Как освободить более сложные вложенные структуры - PullRequest
Новая
       21

Как освободить более сложные вложенные структуры

0 голосов
/ 11 января 2019

Решение в комментариях. 

typedef struct Vertex {
    int i;
    int color;
} vertex;

typedef struct Edge {
    vertex v1;
    vertex v2;
} edge;

typedef struct Node {
    void *p;
    struct Node *next;
} node;

В основном это связанный список (узлов). В моей программе я знаю, содержит ли массив узлов ребра или вершины.

Я не уверен, как правильно освободить список ребер, я пробовал следующее: 

static void freeEdgeList(node *list) {
    if (list == NULL) return;
    node *ptr = list;
    node *tmp;
    do {
        tmp = ptr->next;
        free(&((*((edge *)(ptr->p))).v1));
        free(&((*((edge *)(ptr->p))).v2));
        free(ptr->p);
        free(ptr);
    } while ((ptr = tmp) != NULL);
}

Поскольку моя структура Edge не хранит указатели, достаточно ли этого, чтобы освободить структуру ребер, не освобождая вершины, хранящиеся в ребре? Я немного запутался.

Edit: 

static int addEdge(edge *e, node **list) {
    if ((*list) == NULL) {
        (*list) = malloc(sizeof(node));
        if ((*list) == NULL) return -1;
        (*list)->p = malloc(sizeof(edge));
        if ((*list)->p == NULL) return -1;
        memcpy(&((*list)->p), &e, sizeof(edge));
        (*list)->next = NULL;
    } else {
        node *tmp = (*list);
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = malloc(sizeof(node));
        if (tmp->next == NULL) return -1;
        tmp = tmp->next;
        tmp->p = malloc(sizeof(edge));
        if (tmp->p == NULL) return -1;
        tmp->next = NULL;
        memcpy(&(tmp->p), &e, sizeof(edge));
    }
    return 0;
}

Это функция, которая добавляет ребра в список (изначально передаваемый список равен NULL). Кажется, что правильно добавляются ребра, потому что я могу вывести список на консоль просто отлично. Но если я попытаюсь освободить с помощью: 

static void freeEdgeList(node *list) {
    while (list) {
        node *tmp = list;
        list = list->next;
        free(tmp->p);
        free(tmp);
    }
}

Я получаю другую ошибку (segfault, неверный указатель)

Ответы [ 5 ]

0 голосов
/ 11 января 2019

Как уже упоминали другие, freeEdgeList нуждается в исправлении [следуйте их ответам].

В addEdge ваши memcpy вызовы неверны. Вы копируете в / из адрес указателя, а не то, на что указывает указатель.

Вы хотите: memcpy((*list)->p, e, sizeof(edge)) и memcpy(tmp->p, e, sizeof(edge))

Кроме того, в addEdge, если *list == NULL, вы не установите его для первого / нового элемента.

Кроме того, код можно немного упростить. Например, использование *list везде немного громоздко.

Вот переработанная версия с исправленными ошибками memcpy и *list: 

static int
addEdge(edge *e, node **list)
{
    node *head = *list;
    node *cur;
    node *prev;
    int ret = -1;

    // find the end of the list
    prev = NULL;
    for (cur = head;  cur != NULL;  cur = cur->next)
        prev = cur;

    do {
        // allocate new node
        cur = malloc(sizeof(node));
        if (cur == NULL)
            break;
        cur->next = NULL;

        // add pointer to new edge
        cur->p = malloc(sizeof(edge));
        if (cur->p == NULL) {
            free(cur);
            break;
        }

        // copy in the edge data
        memcpy(cur->p,e,sizeof(edge);

        // link in new node
        if (prev != NULL)
            prev->next = cur;
        else
            head = cur;

        // adjust list pointer
        *list = head;

        ret = 0;
    } while (0);

    return ret;
}
0 голосов
/ 11 января 2019

Редактировать: Кажется, я еще не совсем понял ..

Спасибо за вашу помощь, большое спасибо! Это ясно для меня. 

while (list) {
    node *tmp = list;
    list = list->next;
    free(&(tmp->p));
    free(tmp);
}

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

0 голосов
/ 11 января 2019

Вы можете передать только free именно то, что было возвращено из malloc и его семьи. Поскольку вы предположительно позвонили malloc, чтобы выделить node, вам нужно только освободить node.

Ни vertex, ни edge не содержат полей, которые являются указателями, поэтому освобождать больше нечего. Все, что вам нужно сделать, это: 

static void freeEdgeList(node *list) {
    while (list) {
        node *tmp = list;
        list = list->next;
        free(tmp->p);
        free(tmp);
    }
}

EDIT:

В коде, где вы добавляете ребро, вы неправильно делаете это: 

memcpy(&((*list)->p), &e, sizeof(edge));
...
memcpy(&(tmp->p), &e, sizeof(edge));

Так как e является edge *, то это копирует значение указателя e в поле p вместо того, на что оно указывает. В результате объект edge, на который указывает p, имеет недопустимые значения. Вы вместо этого хотите: 

memcpy((*list)->p, e, sizeof(edge));
...
memcpy(tmp->p, e, sizeof(edge));

Это скопирует значения, содержащиеся в edge, на которые указывает e.

0 голосов
/ 11 января 2019

Правило состоит в том, что если вы не выделяете его, вы не освобождаете его. Структура Edge, как вы сказали, не содержит динамического выделения памяти или указателей, поэтому вы не освобождаете их самостоятельно. Память выделяется как часть Edge и освобождается при ее освобождении.

Поэтому удалите free() s из v1 и v2 и используйте только free(ptr->p).

0 голосов
/ 11 января 2019

Да, это правильно. Поскольку вы не malloc() ing vertex (они не указатели, а переменные, размещенные внутри структуры Edge), то простого free() для структуры Edge будет достаточно

...