Double-chained Lists Removal Doubt (C / Orderly Insertion)

Question

Double-chained Lists Removal Doubt (C / Orderly Insertion)

Navigation

#1 by (0 votes)

0

In a C ++ class the teacher had proposed an activity where I had to do a program in the form of a double-chained list with ordered insertion. However, I have a problem in the Removal part. When removing all members from either end to the other (from start to finish or vice versa) the program "chasha" when I remove the last member from the list.

I would like to know the reason for the problem, I believe that it is in the programming of ant / prox since there comes a time when the beginning is equal to the end.

All other functions of the program work, only need to correct this detail in the removal. Below is the base structure, the remove function, and the "find_search" sub-function that it uses.

typedef struct aula{
aula *prox;
aula *ant;
int x;
};

aula *localizar_busca(aula *w, int v){
while (w!=NULL && w->x!=v){
    w=w->prox;
}
if(w == NULL)
    return NULL;
else
    return w;
}


void listar(aula **inicio){
aula *x_aux;
int contador=0;
if(*inicio == NULL){
    printf("\n");
    printf("Fila vazia...");
}
else{
    printf("\n");
    x_aux = *inicio;
    do{
        printf("Elemento %d da fila = %d\n", contador, (x_aux)->x);
        contador+=1;
        x_aux = x_aux->prox;
    }
    while(x_aux!= NULL);
}
}


void remover(aula **inicio, aula **fim){
int aux, contador = 0;
aula *enc;
if(*inicio == NULL){
    printf("\nLista vazia, nao ha elementos a serem removidos.");
}
else{
    printf("\nLista atual: \n");
    listar(&*inicio);
    printf("\n\nEscolha um elemento listado a ser removido: ");
    scanf("%d", &aux);
    enc = localizar_busca(*inicio, aux);
    if(enc == NULL){
        printf("\nElemento nao encontrado.");
    }
    else if(aux == (*inicio)->x){
        printf("\n%d removido com sucesso!", (*inicio)->x);
        (*inicio) = (*inicio)->prox;
        (*inicio)->ant = NULL;
    }
    else if(aux == (*fim)->x){
        printf("\n%d removido com sucesso!", (*fim)->x);
        (*fim) = (*fim)->ant;
        (*fim)->prox = NULL;
    }
    else{
        printf("\n%d removido com sucesso!", enc->x);
        enc->ant->prox = enc->prox;
        enc->prox->ant = enc->ant;
        free(enc);
    }
}
}

Here's the main:

int main(){
aula *novo, *aux, *inicio = NULL, *fim = NULL;
char OP;

do{
    printf("\nEscolha o que deseja fazer: \n1 - Inserir\n2 - Listar\n3 - Buscar\n4 - Remover\n5 - Esvaziar\n6 - Sair\n");
    OP = getche();

    switch(OP){
    case '1':
        inserir(&inicio, &fim);
        break;
    case '2':
        listar(&inicio);
        break;
    case '3':
        buscar_lista(&inicio, &fim);
        break;
    case '4':
        remover(&inicio, &fim);
        break;
    case '5':
        esvaziar(&inicio, &fim);
        break;
    case '6':
        esvaziar(&inicio, &fim);
        break;
    default:
        printf("\nOP invalido");
        break;
    }
    }while(OP!='6');
return 0;
}

c++ struct lista lista-encadeada

asked by anonymous 12.05.2017 / 23:24

1 answer

Xcode update - loss of all simulators How to show data in ascending order mongoosejs + expressjs

score 0 · Accepted Answer

When we analyze what happens if we pass a list with a single node, the problem becomes obvious:

Just to remember: when the list has only one node, **inicio == **fim and (*inicio)->prox == (*inicio)->ant == (*fim)->prox == (*fim)->ant == NULL .

void remover(aula **inicio, aula **fim) {
    int aux, contador = 0;
    aula *enc;

You start by checking that the list contains no nodes, that is, if *inicio is empty. In this case, it is not.

    if(*inicio == NULL) {
        printf("\nLista vazia, nao ha elementos a serem removidos.");
    }
    else {

As it is not, we show the current list and ask which item should be removed:

        printf("\nLista atual: \n");
        listar(&*inicio);
        printf("\n\nEscolha um elemento listado a ser removido: ");
        scanf("%d", &aux);

The user supposedly chooses the last remaining node, and then we do a linear search to find the requested node: If it does not find, we complain.

        enc = localizar_busca(*inicio, aux);
        if(enc == NULL){
            printf("\nElemento nao encontrado.");
        }

Having found, we tested the first case, where the requested value is (*inicio)->x .

As it is, we enter if :

        else if(aux == (*inicio)->x){
            printf("\n%d removido com sucesso!", (*inicio)->x);

First, we reported success a little prematurely.

            (*inicio) = (*inicio)->prox;

Then, we make inicio point to the successor of the initial node, (*inicio)->prox , which as we saw above, is NULL .

            (*inicio)->ant = NULL;

Finally, we make the predecessor node of this successor be NULL , so that we remove the mention of the node to be deleted from the list.

But, (*inicio) is already NULL ! So we are trying to write to an invalid memory position (since we can not dereference a null pointer). Result? Segfault.

Below are the remaining cases, which we will not enter because they are in else . But note that only in the last case that free(enc) é executado, de forma que todas as vezes que removemos um nó do princípio ou do fim da lista, sizeof (class) 'bytes leak ...

        }
        else if(aux == (*fim)->x){
            printf("\n%d removido com sucesso!", (*fim)->x);
            (*fim) = (*fim)->ant;
            (*fim)->prox = NULL;
        }
        else{
            printf("\n%d removido com sucesso!", enc->x);
            enc->ant->prox = enc->prox;
            enc->prox->ant = enc->ant;
            free(enc);
        }
    }
}

My recommendation, therefore, is to include a test case explicitly with enc == *inicio == *fim , where only *inicio = *fim = NULL would be set and the free() would be given to the remaining node. Finally, it is best to report success only after performing all other operations: it is more correct.