вопрос свободной памяти в c удалил определенное значение в связанном списке - PullRequest
Новая
       4

вопрос свободной памяти в c удалил определенное значение в связанном списке

0 голосов
/ 30 января 2019 
typedef struct node_t { int val; struct node_t *next; } node;   

node *deleteNumber(node *node, int i) {
    while (node && node->val == i) {
        node = node->next;
    }
    n = node;
    p = node;
    if (n == NULL)
        return NULL;
    n = n->next;
    while (n) {
        if (n->val == i)
            p->next = n->next;
        else
            p = p->next;
        n = n->next;
    }
    return node;
}

У меня вопрос, как освободить память удаленного узла в связанном списке.Приведенная выше функция node - это связанный список, с которым я бы хотел работать, а int - это значение, которое я хотел бы удалить.Спасибо!

В настоящее время это вызывает ошибку valgrind, и я не знаю, с чего начать.Я попытался бесплатно (н, р), но это не помогает 

> ==1618== 
> ==1618== HEAP SUMMARY:
> ==1618==     in use at exit: 192 bytes in 12 blocks
> ==1618==   total heap usage: 12 allocs, 0 frees, 192 bytes allocated
> ==1618== 
> ==1618== LEAK SUMMARY:
> ==1618==    definitely lost: 128 bytes in 8 blocks
> ==1618==    indirectly lost: 48 bytes in 3 blocks
> ==1618==      possibly lost: 0 bytes in 0 blocks
> ==1618==    still reachable: 16 bytes in 1 blocks
> ==1618==         suppressed: 0 bytes in 0 blocks
> ==1618== Rerun with --leak-check=full to see details of leaked memory
> ==1618== 
> ==1618== For counts of detected and suppressed errors, rerun with: -v
> ==1618== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Ответы [ 2 ]

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

Чтобы free узлы были удалены из списка, вы должны сохранить элемент next, прежде чем освободить узел, так как вы не сможете получить к нему доступ после освобождения узла.

Вот измененныйверсия: 

typedef struct node_t { int val; struct node_t *next; } node;   

node *deleteNumber(node *node, int i) {
    node *next, *n, *p;
    while (node && node->val == i) {
        next = node->next;
        free(node);
        node = next;
    }
    if (node != NULL) {
        p = n = node;
        n = n->next;
        while (n) {
            if (n->val == i) {
                next = p->next = n->next;
                free(n);
                n = next;
            } else {
                p = n;
                n = n->next;
            }
        }
    }
    return node;
}

Чтобы избежать дублирования кода, вы можете использовать более продвинутый подход с двойным указателем: 

typedef struct node_t { int val; struct node_t *next; } node;   

node *deleteNumber(node *node, int i) {
    node **np = &node;

    while (*np) {
        node *n = *np;
        if (n->val == i) {
            *np = n->next;
            free(n);
        } else {
            np = &n->next;
        }
    }
    return node;
}
0 голосов
/ 30 января 2019

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

#include <stdlib.h>

typedef struct node_t {   int val;   struct node_t *next; } node;

node* deleteNumber(node* start, int i) {
    node* n = start;
    node* p = NULL;
    node* t;

    while (n) {
        t = n;
        n = n->next;
        if (t->val == i) {
            if (p)
                p->next = n;
            else
                start = n;
            free(t);
        } else {
            p = t;
        }
    }
    return start;
}

Вот некоторые дополнительные функции для тестирования выше: 

#include <stdio.h>

/* append number to list, returning start of list */
node* addNumber(node* start, int i) {
    node* t;

    t = malloc(sizeof(*t));
    if (t == NULL)
        return start;
    t->next = NULL;
    t->val = i;
    if (start) {
        node* p = start;

        while (p->next)
            p = p->next;
        p->next = t;
    } else {
        start = t;
    }
    return start;
}

/* print elements of list */
void printList(node* list) {
    while (list) {
        printf(" %d", list->val);
        list = list->next;
    }
}

/* free whole list */
void deleteList(node* list) {
    node* t;

    while (list) {
        t = list;
        list = list->next;
        free(t);
    }
}

int main(void) {
    const int test[] = { 2, 3, 4, 2, 5 };
    node* start = NULL;
    int i;

    /* construct a list */
    for (i = 0; i < sizeof(test) / sizeof(test[0]); i++)
        start = addNumber(start, test[i]);
    /* report initial list contents */
    printf("Before:");
    printList(start);
    printf("\n");
    /* delete a number from the list */
    start = deleteNumber(start, 2);
    /* report updated list contents */
    printf("After:");
    printList(start);
    printf("\n");
    /* delete remaining elements of the list to appease Valgrind */
    deleteList(start);
    return 0;
}

В вышеуказанном коде не должно быть ошибок Valgrind.

...