RISOLTO Eliminare un elemento da una lista c++

[Utente cancellato 302184]

Salve, ho iniziato da poco a studiare le liste e ho dei problemi con la funzione per eliminare un elemento da una lista, in poche parole la funzione non viene eseguita correttamente qundo vado ad eliminare l ultimo elemento della lista, il programa si blocca e si termina, grazie a tutti in anticipo.
Questo è il codice della mia funzione

void elimina(int n)
{
    nodo* q;
    nodo* tmp;
      
    if(p->a==n)
    {
        q=p;
        p=p->next;
        delete q;
    }
    else
    {
        for(q=p; q->next!=NULL; q=q->next)
        {
            if(q->next->a==n)
            {
                tmp=q->next;
                q->next=q->next->next;
                delete tmp;
            }
        }
    }
}

 

[over_coder]

L'errore sta qui:

for(q=p; q->next!=NULL; q=q->next)

Perché se sostituisci l'ultimo elemento poi il ciclo continua, quindi a q viene assegnato q->next che a questo punto è NULL e poi viene verificata la condizione del ciclo, di fatto cercando di dereferenziare un null pointer e mandando in crash il programma.

La soluzione (o "patch" in questo caso) è semplice quindi prova a pensarci un attimo.

 

[Utente cancellato 302184]

Dovrei inserire un controllo per verificare che ciò che viene assegnato, e se è NULL interrompere il ciclo?

 

[over_coder]

Non so se ho interpretato bene, però in un certo senso sì, q non deve essere NULL insieme alla condizione già presente adesso.
E in particolare devi farne la verifica prima.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[Utente cancellato 302184]

Quindi se scrivo

for(q=p; q->next!=NULL, q!=NULL; q=q->next)

Dovrebbe funzionare, perché gli dico di interrompere il ciclo se il nodo successivo punta a NULL o se il nodo corrente punta a NULL condizioni che accade se vado ad eliminare l'ultimo nodo, giusto?

 

[rodhellas]

Salve, ho iniziato da poco a studiare le liste e ho dei problemi con la funzione per eliminare un elemento da una lista, in poche parole la funzione non viene eseguita correttamente qundo vado ad eliminare l ultimo elemento della lista, il programa si blocca e si termina, grazie a tutti in anticipo.
Questo è il codice della mia funzione

void elimina(int n)
{
    nodo* q;
    nodo* tmp;
    
    if(p->a==n)
    {
        q=p;
        p=p->next;
        delete q;
    }
    else
    {
        for(q=p; q->next!=NULL; q=q->next)
        {
            if(q->next->a==n)
            {
                tmp=q->next;
                q->next=q->next->next;
                delete tmp;
            }
        }
    }
}

Ma sei sicuro che funzioni anche per altri valori? Nel primo if ( p da dove la tiri fuori? ), se hai A->B->C, tu cancelli B ma non fai puntare A a C. Per il for, mettici un bruttissimo break dopo il delete e risolvi tutto.

 

[over_coder]

Quindi se scrivo

for(q=p; q->next!=NULL, q!=NULL; q=q->next)

Dovrebbe funzionare, perché gli dico di interrompere il ciclo se il nodo successivo punta a NULL o se il nodo corrente punta a NULL condizioni che accade se vado ad eliminare l'ultimo nodo, giusto?

La condizione più corretta è

for(q=p; q!=NULL && q->next!=NULL; q=q->next)

così da controllare prima che q non sia NULL e poi eventualmente dereferenziarlo.

Per quanto riguarda il primo if io ho interpretato che sia il caso nel quale voglia eliminare il primo elemento della testa e mi pare che lo esegua rimpiazzando correttamente i puntatori.
Certo, c'è da dire che esistono soluzioni molto più eleganti di scrivere la funzione di eliminazione (e in genere di lavorare con le liste) ma poi divago troppo. :P

 

[rodhellas]

La condizione più corretta è

for(q=p; q!=NULL && q->next!=NULL; q=q->next)

così da controllare prima che q non sia NULL e poi eventualmente dereferenziarlo.

Per quanto riguarda il primo if io ho interpretato che sia il caso nel quale voglia eliminare il primo elemento della testa e mi pare che lo esegua rimpiazzando correttamente i puntatori.
Certo, c'è da dire che esistono soluzioni molto più eleganti di scrivere la funzione di eliminazione (e in genere di lavorare con le liste) ma poi divago troppo. :P

Stavo per editare il mio messaggio, mi sono accorto dopo che il primo if si riferiva al primo nodo :cav:

 

[Utente cancellato 302184]

La condizione più corretta è

for(q=p; q!=NULL && q->next!=NULL; q=q->next)

così da controllare prima che q non sia NULL e poi eventualmente dereferenziarlo.

Per quanto riguarda il primo if io ho interpretato che sia il caso nel quale voglia eliminare il primo elemento della testa e mi pare che lo esegua rimpiazzando correttamente i puntatori.
Certo, c'è da dire che esistono soluzioni molto più eleganti di scrivere la funzione di eliminazione (e in genere di lavorare con le liste) ma poi divago troppo. :P

potresti spiegarmi queste soluzioni più eleganti oppure indicarmi un sito dove le spiegano?

 

[rodhellas]

potresti spiegarmi queste soluzioni più eleganti oppure indicarmi un sito dove le spiegano?

Potresti farla ricorsiva ( mi pare si faccia cosi :patpat: ):

struct elimina( int n, node* q ) {  //non ricordo se ci vada struct o altro
  if ( q->a == n ) {
    tmp = q->next;
    delete q;
    return tmp;
  }
  else {
    if( q->next == NULL) {
      return NULL;
    }
    else
      q->next=elimina( n, q->next );
  }
}

 

[Utente cancellato 302184]

Non ci avevo pensato alla ricorsione, non penso sia proprio in quel modo, ma ho capito il concetto, provo subito a farla, grazie

 

[over_coder]

potresti spiegarmi queste soluzioni più eleganti oppure indicarmi un sito dove le spiegano?

Io sono un principiante, c'è gente molto più esperta anche qui sul forum, quindi aggiungo solo un paio di informazioni. :)

Una delle soluzioni più eleganti è sicuramente la soluzione ricorsiva, quindi qualcosa del tipo:

void elimina(nodo* p, int n)
{
    nodo* q = NULL;

    if (p == NULL)
        return;
   
    if (p->a == n) {
        q = p;
        p = p->next;
        delete q;
        return;
    } else {
        elimina(p->next, n)
    }
}

Però le soluzioni ricorsive di base non sono efficienti come quelle iterative benché siano più facili da debuggare e da leggere (sempre in generale). Oltretutto sono molto più intuitive quando si lavora con liste o alberi.

Un'altra possibilità è di utilizzare dei nodi sentinella o una struttura dati per la lista che contenga informazioni supplementari. Però se non implementato bene magari rischia di creare più confusione che altro. :P

Puoi trovare tutto questo anche su Introduction to Algorithms, 3rd Edition, capitolo 10.2 Linked lists. C'è anche la versione italiana del libro.

Per quanto riguarda il codice sarebbe meglio direttamente ritornare il nodo "eliminato" così che la sua deallocazione sia a carico del chiamante che magari ha più informazioni a riguardo. O provvedere con una funzione di eliminazione passata come parametro o soluzioni affini (sopratutto se stai usando il C++).

P.S.
Ho visto le risposte ma invio la mia come l'avevo scritta per non stare qua a modificare tutto. :P

 

[Mursey]

@over_coder per il codice C c'e' il tag code=c

 

[over_coder]

@over_coder per il codice C c'e' il tag code=c

Fantastico, grazie per aver editato anche il post. Non l'avevo visto nel menù a tendina e non ho pensato di provare direttamente come faccio di solito nei forum di XenForo.

 

[Utente cancellato 302184]

@over_coder grazie per le informazioni utili che mi hai dato, grazie a tutti per l'aiuto