Chained List - remove function

Question

Chained List - remove function

Navigation

#1 by (4 votes)
#2 by (2 votes)

2

I'm programming a headless threaded list, in this program there is a remove function that aims to delete all repeated integers in a list, px: by taking the values 8 2 8 3 8 the function has to return 2 3, however this function apparently looped because the execution does not end, not appearing runtime and not errors or warnings in compilation. follow 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 lista

asked by anonymous 27.10.2016 / 15:09

2 answers

2

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

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

Maybe this solves I could not test

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

27.10.2016 / 16:01

Auto Load classes in PHP Android applications, what are the advantages and disadvantages of the tools? [closed]

score 4 · Accepted Answer

The Remove function is entering looping because after the first iteration, the value of the q pointer "loses".

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

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 a commented example of a different way to implement this function, with just 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 tests of the Remove2 function:

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