Chained list - remove function

Asked

Viewed 2,251 times

2

I am programming a chained list without head, in this program there is a remove function that aims to eliminate all the repeated integers in a list, px: taking the values 8 2 8 3 the function has to return 2 3, but this function apparently went into loop, because the execution does not end, not appearing Runtime and not to errors or warnings in the compilation. follows code:

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

struct reg {
      int conteudo;
      struct reg *prox;
};
typedef struct reg celula;

void insere (celula **p, int x) {
      celula *novo, *q;
       q = *p;

      novo = (celula *)malloc(sizeof(celula));
      novo->conteudo = x;

      if (*p == NULL) {
            novo->prox = NULL;
            *p = novo;
      }

      else {
             while (q->prox != NULL)
                    q = q->prox;

      novo->prox = q->prox;
      q->prox = novo;
      }
}

celula* Remove (celula *p, int x) {
       celula *aq, *q, *aux;
       aq = NULL;
       aux = q = p;

       while (aux != NULL) {

             while (q->prox != NULL && q->conteudo != x) {
                   aq = q;
                   q = q->prox;
             }

             if (aq == NULL) p = q->prox;

             else aq->prox = q->prox;
             free(q);
             aux = aux->prox;
         }
      return q;
}

void imprime (celula *p) {
      celula *q;

      if (p == NULL) printf ("Lista Vazia");

      for (q = p; q != NULL; q = q->prox)
               printf ("%d ", q->conteudo);
      printf("\n");
}

int main() {
      celula *lista = NULL;
      celula *lst = NULL;

      insere(&lista, 8);
      insere(&lista, 2);
      insere(&lista, 8);
      insere(&lista, 3);
      insere(&lista, 8);
      imprime(lista);
      lst = Remove(lista, 8);

      imprime(lst);

return 0;
}
c list

2 answers

5


The function Remove is getting into looping because after the first iteration, the pointer value q is "lost".

There are 2 more problems in this function, follow the code below with the commented problems:

celula* Remove (celula *p, int x) {
       celula *aq, *q, *aux;
       aq = NULL;
       aux = q = p;

       while (aux != NULL)
       {
           // q tem que ser inicializado com o valor aux aqui
           q = aux;
           while (q->prox != NULL && q->conteudo != x) {
               aq = q;
               q = q->prox;
           }

           if (aq == NULL) p = q->prox;
           else aq->prox = q->prox;

           // Como aux pode ter o mesmo valor de q
           // a atualização tem que vir antes do
           // free
           aux = aux->prox;
           free(q);
        }
    // aqui, tem que retornar p e não q
    return p;
}

After execution:

8 2 8 3 8
2 3

EDIT:
Here is an example commented on in a different way to implement this function, with only one looping:

celula* Remove2(celula *p, int x) {
    celula *atual, *anterior;

    atual = p;

    // Lista vazia. Retorna
    if (p == NULL)
        return NULL;    

    anterior = NULL;
    while (atual)
    {        
        if (atual->conteudo == x)
        {

            if (anterior == NULL)                
            {
                //
                // --| Remove um elemento do início da lista |--                    
                //
                p = p->prox; // Atualiza o início da lista
                free(atual);
                atual = p;
                continue;                
            } else 
            {
                //
                // --| Remove um elemento do meio ou final da lista |--
                //
                anterior->prox = atual->prox;
                free(atual);                    
                atual = anterior; // continua a partir do elemento anterior
                continue;
            };
        };
        // Caminha para o próximo elemento
        anterior = atual;
        atual = atual->prox;
    }
    return p;
}

Below, the function tests Remove2:

Remove o 8:
8 8 8 8 8 8 2 8 3 8 8 2 8 3 4 8 8 
2 3 2 3 4 

Remove o 2:
8 8 8 8 8 8 2 8 3 8 8 2 8 3 4 8 8 
8 8 8 8 8 8 8 3 8 8 8 3 4 8 8 

Remove o 4:
8 8 8 8 8 4 8 2 8 3 8 8 2 8 3 4 8 8 4 
8 8 8 8 8 8 2 8 3 8 8 2 8 3 8 8 

Remove o 9:
9 8 8 8 8 4 8 2 9 3 8 8 2 8 3 4 8 8 9 
8 8 8 8 4 8 2 3 8 8 2 8 3 4 8 8

  • Its very coherent solution, the problem is that it ignores the last pointer, e.g., when I ask the exclusion of element 2, occurs the following: input: 8 2 8 3 8, output: 8 8 3, I tried to modify pointers to solve this issue , but I could not.

  • When you assigned aq->prox = q->prox in charge else, he "kills" the last element on the list because q->prox is null in the last element, and he assigned this null to the aq (which is the previous/current element) :)

  • This answer solves the question problem "this function apparently looped", however, there are other problems with pointers (and algorithm) in the code

  • I put a commented example, with a different way to implement the function. I hope it helps :)

2

I believe the error is in your while, because in case you are sending 8, but doing a table test realize that in the first interaction of while it does not enter and passes directly.

Ex: q->Prox != NULL TRUE q->content != x FALSE pq 8 == 8

maybe it solves I could not test

 while (q->prox != NULL ) {
     if(q->conteudo != x){
         aq = q;
     }
     q = q->prox;
 }
  • 1

    If you refer to the internal loop - while (q->Prox != NULL && q->content != x) - I believe it is correct, as it has to come out of the loop itself, since 8 is the first to be deleted, passing for removal in the condition - if (aq == NULL) p = q->Prox; - for this is the first member of the headless list. If it’s the tie with Aux I don’t understand

Browser other questions tagged c list

You are not signed in. Login or sign up in order to post.