Lista semplice

di il
16 risposte

Lista semplice

Salve, mi stavo esercitando con le liste semplici e mi sono imbattuto in un metodo che non riesco a far funzionare, il metodo elimina, nello specifico non riesco a cancellare il primo elemento della lista, per il resto tutti gli altri si eliminano, spero che qualcuno possa darmi una dritta..posto il codice:

#include<iostream>
using namespace std;
class nodo {
    public:
        int a;
        nodo* ptr;
        nodo(nodo* p,int b) {
            ptr=p;
            a=b;
        }
        nodo* ricerca(int val) {
            nodo* p=this;
            while(p!=NULL) {
                if(p->a==val) {
                    cout<<"elemento trovato";
                    return p;
                }
                p=p->ptr;
            }
            cout<<"elemento non trovato";
            return 0;
        }
        void elimina(int val) {    
            nodo* P=this;
            nodo* prec=NULL;
            if(P==NULL) {
                cout<<"Lista vuota";
            } else if(P->a==val) {    // da qui
                prec=P;
                P=P->ptr;
                delete prec;    // fino a qua, l'errore dovrebbe essere qui
                }
                else {
                prec=P;
                P=P->ptr;
                while((P!=NULL) && (P->a!=val)) {
                    prec=prec->ptr;
                    P=P->ptr;
                }
                if(P!=NULL) {
                    prec->ptr=P->ptr;
                    delete P;
                } else
                    cout<<"Elemento non presente"<<endl;
 
            }
        }
};
void stampa(nodo* P) {
    nodo* p=P;
    while(p!=NULL) {
        cout<<p->a<<"  "<<p->ptr<<endl;
        p=p->ptr;
    }
}
void inserisci_in_testa(nodo*& testa, int val ) {
	nodo* nuovo=new nodo(nuovo, val);
	nuovo->ptr=testa;
    testa=nuovo;
}
void inserisci_in_coda(nodo* testa,int val) {
    nodo* temp=testa;
    nodo* nuovo=new nodo(nuovo,val);
    nuovo->ptr=NULL;
    if(testa==NULL)
        inserisci_in_testa(testa,val);
    else {
        while(temp->ptr!=NULL)
            temp=temp->ptr;
        temp->ptr=nuovo;
    }
}
int main() {
    nodo* testa=NULL;
    for(int i=0; i<10; i++)
        testa=new nodo(testa,i);
    inserisci_in_testa(testa,10);
    inserisci_in_coda(testa,11);
    inserisci_in_coda(testa,12);
    inserisci_in_coda(testa,13);
    stampa(testa);
    cout<<endl;
    testa->elimina(10);
    cout<<endl;
    stampa(testa);
    cout<<endl;
} 

16 Risposte

  • Re: Lista semplice

    Ciao
    provo ad aiutarti!
    nella routine elimina parli solo degli elementi !=0
    ma il primo elemento della lista è zero!
    visto che non hai indicato un valore ben specifico di inizio lista.
    quindi secondo me quando l'elemento è 0 dovresti farlo "suicidare"
    e poi cambiare il punto di inizio della lista.
    spero di esserti stato d'aiuto
  • Re: Lista semplice

    Il primo elemento della lista è la testa e punta a un nodo, e quando metto 0 intendo NULL che non punta a niente, non che è 0.
    Li ho messi tutti a NULL ora, così si capisce meglio.
  • Re: Lista semplice

    Se vuoi un consiglio lascia perdere il costruttore e riscrivi i vari metodi come funzioni esterne alla classe.

    Un paio di osservazioni:
    - nel c++ di solito si utilizza nullptr e non NULL;
    - sarebbe più chiaro chiamare il membro puntatore "next" e non "ptr".

    Per quanto riguarda il metodo elimina cosa dovrebbe fare? eliminare tutti i nodi con a==val o solo il primo che si incontra?
  • Re: Lista semplice

    Eh ma ormai..il metodo elimina deve eliminare il nodo che ha come valore val
  • Re: Lista semplice

    La seguente lista 1 2 5 2 7 in seguito alla funzione elimina(2) come dovrebbe diventare? 1 5 2 7 o 1 5 7?
  • Re: Lista semplice

    In quel caso forse funziona male perchè ci sono due volte 2(e cancellerebbe il primo penso, ma facciamo finta che non ci siano doppioni) ahahahahah, comunque se abbiamo 1 4 5 76 0, e elimino 5 deve diventare 1 4 76 0 e questo mi funziona, ma quando cerco di eliminare il primo elemento cioè 1, mi da un numero a caso e poi 4 5 76 0
  • Re: Lista semplice

    In quel caso forse funziona male perchè ci sono due volte 2(e cancellerebbe il primo penso, ma facciamo finta che non ci siano doppioni)...
    Deduco non l'abbia scritto tu allora quel codice!

    In ogni caso il problema del metodo elimina si trova effettivamente nel frammento di codice da te indicato e che si riferisce al caso in cui il primo elemento della lista è uguale a val.
    Il problema è che all'uscita da quell'ifelse, il puntatore this (che coincide con il puntatore testa con cui è stato richiamato il metodo elimina dal main) punterà all'area di memoria deallocata in cui era memorizzato il primo elemento della lista. L'area a cui puntava testa, ritornata disponibile in seguito al delete, potrebbe essere sovrascritta con la conseguenza che qualsiasi utilizzo del puntatore testa genererà un risultato imprevedibile.
    Il puntatore P utilizzato nel metodo, che punta correttamente al secondo elemento della lista, all'uscita dalla funzione cesserà di esistere risultando quindi inutilizzabile. In questo modo ogni riferimento certo alla nostra lista andrà perso.
    L'ifelse andrebbe quindi corretto nel seguente modo:
    else if(a == val)
    {
        prec = this;
        this = ptr;
        delete prec;
    }
    peccato però che this sia un puntatore costante e come tale non può essere modificato...
    L'unica soluzione che mi viene in mente è quella di convertire il metodo elimina in una funzione esterna alla classe come già ti avevo suggerito di fare nel mio precedente post.
  • Re: Lista semplice

    Tento un suggerimento, che scrivo direttamente nei commenti del codice:
    	
    	else if( P->a == val )
    	{
    		/* // da qui
    		prec = P;
    		P = P->ptr;
    		delete prec;    // fino a qua, l'errore dovrebbe essere qui
    		*/
    
    		prec = P->ptr;		// Salva il nodo successivo a P.
    		delete P;			// Libera il nodo puntato da P.
    		P = prec;			// Aggiorna P con il nodo appena salvato.
    	}
    
    Non l'ho testato perciò non so se funziona o se possa provocare effetti collaterali.
  • Re: Lista semplice

    Io l'ho scritto il codice, il mio prof lo aveva scritto usando la struct e io ho voluto provare così..
    Comunque grazie della spiegazione, adesso ho capito perchè la testa non si aggiorna, eppure il mio prof usando una struct per gli elementi e una classe per fare la testa gli si aggiorna..
    Ho provato a scrivere la funzione elimina all'esterno della classe, ma non funziona nemmeno, avevo scritto così ma stesso problema..
    
     void elimina(nodo*&testa, int val) {    
                nodo* P=testa;
                nodo* prec=NULL;
                if(P==NULL) {
                    cout<<"Lista vuota";
                } else if(P->a==val) {   // da qui
                    prec=P;      
          			P=P->ptr;         
         			delete prec;     // fino a qua
                    }
                    
    Invece come dovrei fare?
  • Re: Lista semplice

    Unqualunque ha scritto:


    Tento un suggerimento, che scrivo direttamente nei commenti del codice:
    Non l'ho testato perciò non so se funziona o se possa provocare effetti collaterali.
    Ho provato, stesso problema di prima.
  • Re: Lista semplice

    Io l'ho scritto il codice, il mio prof lo aveva scritto usando la struct e io ho voluto provare così..
    Mi riferivo al fatto che se il codice è opera tua dovresti sapere quello che fa.
    In ogni caso struct o class non cambia nulla in questo caso.
    Ho provato a scrivere la funzione elimina all'esterno della classe, ma non funziona nemmeno, avevo scritto così ma stesso problema...
    Il problema prima era che non avevi la possibilità di modificare il puntatore testa(ovvero this), mentre adesso che puoi farlo non lo fai?
    Tento un suggerimento, che scrivo direttamente nei commenti del codice:
    I due frammenti di codice
    prec = P;
    P = P->ptr;
    delete prec;
    e
    prec = P->ptr;
    delete P;
    P = prec;
    sono praticamente equivalenti, l'unica differenza è che nel primo il puntatore prec punta al primo elemento (quello "eliminato"), mentre nel secondo punta come P al secondo elemento della lista.
  • Re: Lista semplice

    Si, è vero, i due frammenti sono praticamente equivalenti. Avrebbe avuto più senso se avessi scritto:
    	else if( P->a == val )
    	{
    		m_pHead = P->ptr;
    		delete P;
    		P = m_pHead;
    	}
    Dove m_pHead sarebbe un puntatore non costante che identifica la testa della lista in condizioni di visibilità, perché se la testa della lista non si aggiorna (e tutto il problema sta proprio lì) allora sarà sicuramente dovuto al fatto che si trova out of scope.
  • Re: Lista semplice

    prec = P->ptr;
    delete P;
    P = prec;
    quindi dovevo riprovare con questo? non funziona comunque
  • Re: Lista semplice

    No, non può funzionare, infatti ho corretto:

    m_pHead = P->ptr;
    delete P;
    P = m_pHead;


    Usando una ipotetica variabile puntatore non costante m_pHead che tiene l'dirizzo del primo elemento della lista, e dev'essere visibile a ogni metodo che accede alla lista.
Devi accedere o registrarti per scrivere nel forum
16 risposte