Segmentation Fault When Removing List Occurrences

2

The following code has the purpose of removing all occurrences of an integer in a list (linked lists), returning at the end the number of elements removed. Home Give me the segmentation fault error. Thanks for any explanation.

typedef struct lligada {
    int valor;
    struct lligada *prox;
} *LInt;

int removeAll (LInt *l, int x){
    int r = 0;
    LInt pt = *l, ant = NULL;
    while (pt != NULL){
        if (pt -> valor == x){
            ant -> prox = pt -> prox;
            pt = pt -> prox;
            r++;
        }
        else {
            ant  = pt;
            pt = pt -> prox;
        }
    }

    return r;
}
    
asked by anonymous 26.04.2018 / 20:35

2 answers

2

You have 2 problems with your code:

  • You are not doing free of nodes that are removed, so there is a memory leak. This problem, although not noticeable because it does not immediately launch a segmentation fault , ends up leaving your program incorrect, and in a case where it is overused and will continue to manifest itself.

  • You are accessing the ant with no guarantee that it has been assigned:

    LInt pt = *l, ant = NULL; //ant null aqui
    while (pt != NULL){
        if (pt -> valor == x){
            ant -> prox = pt -> prox; //utilizado aqui
    

    Note that if the first node is to be removed, then ant is still NULL because there is no element before it. This causes ant->prox to immediately segmentation fault , since it can not dereferentize null / 0.

To fix both issues you could rewrite your removeAll to:

int removeAll (LInt *l, int x){
    int r = 0;
    LInt pt = *l, ant = NULL;
    while (pt != NULL){
        if (pt -> valor == x){
            if (ant == NULL){ //se é o primeiro nó
                *l = pt->prox; //avança a cabeça da lista para o seguinte
            }
            else { //senão faz o que já tinha
                ant -> prox = pt -> prox;
            }
            LInt toDelete = pt; //guarda o nó a remover com free
            pt = pt -> prox;
            free(toDelete); //remove o nó que já não é necessário
            r++;
        }
        else {
            ant = pt;
            pt = pt -> prox;
        }
    }

    return r;
}

See this example working on Ideone

    
27.04.2018 / 01:02
0

Suggest:

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

struct lligada
{
    int valor;
    struct lligada *next;
};
typedef struct lligada *LInt;

// protótipos
int removeAll (LInt *l, int x);


int removeAll (LInt *l, int x)
{
    int r = 0;
    LInt pt = *l;
    LInt ant = NULL;

    while (pt != NULL)
    {
        if (pt -> valor == x)
        {
            r++;

            ant->next = pt->next->next; 
            free( pt );
        }

        else
        {
            ant = pt;
            pt = pt -> next;
        }
    }

    return r;
}
    
26.04.2018 / 23:09