C++ Problema funzioni lista

[ilmassa]

Salve a tutti, ringrazio prima di tutto oregon, che mi ha risposto poco tempo fa in 2 topic.

Nel seguente problema, vorrei che la seguente chiamata a funzione, mi cancellasse il valore x nella lista, e mi ritornasse un valore buleano 1=se cancellato , 0=se non cancellato.
Metto le parti del programma che servono alla funzione (quello che ometto riguarda altre funzioni).

main.cpp

int x;lista l1;
cin<<x;
l1.cancella(x);

contatore.h

struct nodo
{
   int valore;
   nodo *succ;
};

class lista
{
  nodo *l;
  bool eliminaval(nodo* l,int x);

public:
  lista(){l=0;}   //Costruttore
  ~lista();       //Distruttore
  bool cancella(int);
};

contatore.cpp

bool lista::cancella(int x)
{
    return eliminaval(l,x);
};


bool lista::eliminaval(nodo* l,int x){

bool cancellato;
nodo* s;
s=l;
while(l->succ!=NULL){                 //controlla elementi da dopo il primo
if(l->succ->valore==x){
l->succ=l->succ->succ;

cancellato=1;
}}; //fine if e fine while

if(s->valore==x){              //controlla se il primo valore è x, se si parte dal succesivo
s=s->succ;
cancellato=1;
}; //fine if

return cancellato;
};// fine funzione eliminaval

Non riesco a capire se è sbagliata la funzione, o in qualche modo l non è raggiungibile .
Mi stampa sempre gli stessi elementi che ho messo in l, e non mi elimina niente.
Naturalmente la stampa la faccio con un'altra funzione l1.stampa(); , ma funziona bene, e i dati vengono stampati, funziona anche se inserisco un elemento con l1.push(x); .
In pratica solo questo pezzo non va.


Ho fatto chiamate simili per altre funzioni, e funzionano bene, però in questo caso l non me lo modifica.

[Scara95]

cin<<x;

è sbagliato, dovrebbe essere:

cin>>x;

[ilmassa]

Ho sbagliato a riscriverlo in modo compatto (dato che il main suppongo non abbia errori in chiamata). In realtà ho questa chiamta in inserimento (ma non è qui l'errore):

case 1:	printf("\nInserisci un elemento: ");
                        if(scanf("%d",&x)!=1)        //inserisco x qui, se ci sono errori ripulisco il buffer
                        {
                            printf("Valore inserito errato\n");
                            fflush(stdin);
                        }
                        else
                         l1.push(x);//Effettua l'inserimento nella lista (qui va tutto bene);

Il prob. dovrebbe essere nella cancellazione dell'elemento.
Le parti di: inserimento, stampa valore e ricerca funzionano perfettamente.
L'unica cosa che non va è la cancellazione.
Il prob. dovrebbe essere dopo la chiamata di l1.cancella(x).
Scusate dell'errore nel riportare in modo compatto il main, gli altri pezzi sono uguali al codice che ho, ci mancano soltanto le altre funzioni che non interessano il prob.

In pratica per esempio inserisco alcuni elementi: 1 , 5 , 7.
Faccio stampa per prova e escono giustamente (dato che l'inserimento lo faccio in testa): 7 , 5 , 1 .

Dico di eliminare per esempio 5.

Provo a stampare e mi ristampa la lista : 7 , 5 , 1.

In pratica non capisco perchè l'eliminazione non avviene.



Ho provato addirittura a scrivere

bool lista::eliminaval(nodo* l,int x){

l=NULL;
};

Per vedere se così l puntava a NULL, ma mi stampa comunque la lista l (non me la cambia).
Non so se c'è qualche prob. nei permessi, però la chiamata viene fatta da una funzione della classe, quindi dovrebbe andare(almeno funziona così per le altre).



La funzione cancella(int); , che è una funzione pub. , chiama la funzione privata eliminaval(nodo* l,int x); , che prende anche la lista l (così nessuno da interfaccia potrà mai toccare "l").
Nel momento in cui modifico l , non succede nulla....cioè l non cambia.

[Ippo343]

Non riesco a capire come mai non elimini l'elemento, però in compenso posso risolverti il mistero del perchè avevi ancora la lista quando mettevi l = NULL.

Quando passi l alla funzione, passi un puntatore ad un oggetto. Ma non passi il puntatore: il puntatore viene passato per valore, non per indirizzo.

Esempio:

void foo (int a)
{
    a++;
}

...
int x = 10;
foo(x);
//x vale ancora 10

Allo stesso modo:

void foo (nodo* n)
{
    n = NULL
}

...
nodo* p = lista;
foo(p);
//p sta ancora puntando a lista

Questo perchè il suo valore non viene modificato dalla chiamata a funzione, dato che è un argomento.

Per eliminare un elemento da una lista ti consiglio però la versione ricorsiva dell'algoritmo: la trovo molto più semplice ed elegante.

node* elimina(node* n, int val)
{
    if (val == n->valore)
        return n->next;
    else
        return elimina(n->next, val);
}

[ilmassa]

La cosa strana è che se faccio la stessa cosa per l'inserimento (usando i puntatori):

void lista::push(int x)
{
    l=insert(l,x);
};

/*Inserisce gli elementi in modo disordinato (inserimento in testa)*/

nodo* lista::insert(nodo *p,int x)
{
    nodo *q;
    cout<<"insert:versione con inserimento in testa"<<endl;
    q=new nodo; //alloca un elemento;il suo indirizzo è q;
    q->valore=x;
    q->succ=p;
    p=q;
    return p;
    };

In questo caso me lo modifica, anche se poi vado nel menù stampa, oppure ne aggiungo altri, me li stampa.
Cioè, anche in questo caso dovrebbe dare lo stesso prob. , però è perfetto XD.


Riguardo il codice:

node* elimina(node* n, int val)
{
    if (val == n->valore)
        return n->next;
    else
        return elimina(n->next, val);
}

Credo che l'unico prob. è se ci siano doppioni.
Cioè in questo caso se trovo il primo valore corrispondente si ferma e mi riporta il puntatore al successivo, ma poi non mi elimina gli altri.


Sto impazzendo davanti questo prog. .

[ilmassa]

Sono riuscito a farlo funzionare, avete idee per migliorarlo?

/*effettua cancellazione elemento*/

bool lista::cancella(int x)
{
    nodo *s;
    l=eliminaprimo(l,x);
    s=l;
    eliminacentro(l,x);
    l=s;
};

nodo* lista::eliminaprimo(nodo* l, int val)    //elimina in modo ricorsivo i primi se sono uguali
{
    if (val == l->valore){
        l=l->succ;
    if(l!=NULL){
    return eliminaprimo(l, val);
    }
    };
    return l;
};

nodo* lista::eliminacentro(nodo* l, int val)  //elimina elementi dopo il primo
{
    if(l!=NULL && l->succ!=NULL)
    if (val == l->succ->valore){
    l->succ=l->succ->succ;
    return eliminacentro(l, val);
    };
    };

[Ippo343]

Perchè hai due diverse versioni della elimina? Mi sembrano fondamentalmente identiche, sono anche tutte e due ricorsive...

Inoltre se usi la versione ricorsiva, non c'è distinzione tra il primo nodo, un nodo centrale, o l'ultimo nodo: funziona in tutti i casi.

Io ti ho scritto proprio la versione iperbasilare, infatti non controlla nemmeno che il nodo sia NULL, però per cancellare eventuali doppioni basta fargli eseguire la ricorsione anche in caso che si elimini il nodo.

Se non lo trovo, il prossimo nodo sarà n->next, e poi controllo di nuovo a partire da lì.
Analogamente, se devi cancellare il nodo, il prossimo nodo sarà n->next->next.

node* elimina(node* n, int val)
{
    if (val == n->valore)
        return elimina(n->next->next, val);
    else
        return elimina(n->next, val);
}

[ilmassa]

node* elimina(node* n, int val)
{
    if (val == n->valore)
        return elimina(n->next->next, val);
    else
        return elimina(n->next, val);
}

Se però avessi un elemento soltanto, esempio 1.
Inserissi come elemento da eliminare 1.

nel primo if, val e n->valore sarebbero uguali.

quindi si attiverebbe la funzione
return elimina(n->next->next, val);

n->next->next punta a una zona di memoria non esistente, e il programma va in crash(almeno così mi ha fatto più volte).
Questo perchè n->next sarebbe il NULL, ma n->next->next non esiste (o meglio, e una zona di memoria dove non si sa che ci sia), e possono accadere cose strane.
Quindi penso che questo mi manda in crash quando provo a usare questa funz. .




------------
Quello che ho usato su:
Con la prima funzione elimino i successivi elementi partendo dal primo , fin quando non raggiungo NULL, oppure se il primo elemento è diverso da quello che cerco si ferma.
In questo modo l punterà sempre l'elemento in testa (e non perdo nulla durante la stampa).
Successivamente faccio partire l'altra funzione che si occuperà di controllare gli elementi (sapendo che il primo è diverso da val).

Se mi capitasse la situazione che mi manda in crash con il tuo algoritmo:
In pratica faccio partire la prima, vede che c'è il valore 1, e lo elimina e punta a NULL.
A questo punto il ciclo termina, perchè l==NULL.
Parte la seconda funzione e vede che il primo elemento è NULL, quindi termina anche questa.

Se avessi 1-2-2-1 , e volessi eliminare 2, la prima controllerebbe se il valore è in testa, non essendoci, partirebbe la seconda, che cancellerebbe tutti gli elementi a partire dal successivo.
Ed l punterebbe sempre in testa.
Usandone solo una, spesso mi ritrovavo pezzi scollegati, se usavo diverse combinazioni di valori.
Così sono sicuro che il primo elemento punterà sempre a qualcosa (essendo diverso da val), e quando stamperò l, l partirà dall'elemento in testa.


Cioè questo per dire che l'ho provata, ma non sembra andare, anche se sono sicuro che esista qualche algoritmo più compresso, ma in grado di controllare tutti i casi, molto simile a quello che dici.

Cioè la prima versione che mi hai postato, funzionava, ma mi eliminava soltanto il primo elemento trovato, e gli altri li lasciava.
La seconda mi da il problema che può in alcuni casi puntare una zona di memoria che non appartiene alla lista di elementi.


Ho trovato anche un'altro caso, se ho 35-1-1-2 e devo togliere 35 che è l'ultimo elemento della coda.
Ho dovuto cambiare il codice di eliminacentro, aggiungendo l'else (se non si trova in mezzo ma alla fine).

nodo* lista::eliminacentro(nodo* l, int val)  //elimina elementi dopo il primo
{
    if(l!=NULL && l->succ!=NULL)
    if (val == l->succ->valore){
    l->succ=l->succ->succ;
    return eliminacentro(l, val);
    }
    else
        return eliminacentro(l->succ, val);;
    };

[Ippo343]

Ops! Le mie scuse... quando ti ho scritto quel pezzetto di codice (che del resto, come ti ho detto, non era nemmeno completo) ero molto di fretta e non ci ho ragionato su molto...

Sono andato a riprendere la mia implementazione dell'algoritmo ricorsivo nella lista. Come ti dicevo, con la versione ricorsiva non esistono casi distinti: che sia in testa, in mezzo, o in fondo alla lista non fa alcuna differenza. Funziona anche se viene chiamato direttamente su NULL.

[L'ultimo parametro è una funzione di comparazione, ho implementato una lista di void* così che possa essere usata per qualsiasi tipo di valore e questo richiede una funzione per fare i confronti]

Node* list_remove(Node* currP, void* value, int (*cmp)(void*, void*))
{
    // Fine della lista
    if (currP == NULL)
        return NULL;

    //Nodo trovato
    if (cmp(currP->data, value) == 0)
    {
        Node* nextP;
        nextP = list_remove(currP->next, value, cmp);
        free(currP);

        return nextP;
    }
    else
    {
        //Controlla il resto della lista
        currP->next = list_remove(currP->next, value, cmp);
        return currP;
    }
}

P.S: dimenticavo: inoltre questa elimina anche eventuali doppioni.

[ilmassa]

Ti ringrazio per la risposta, però questo tipo di chiamata non l'ho mai usata, anche sul libro che sto usando non la riesco a trovare, comunque cercherò di capire.

Nel file .h il prototipo aveva questi elementi:

Node* list_remove(Nodo* l,int x);


Adesso dovrei mandare ?

Node* list_remove(Node* l, ................................);

Ma soprattuto la funzione di comparazione come funziona?
Cioè ho capito che il void serve per confrontare tipi generici, per il resto è buio.

questo richiede una funzione per fare i confronti

Dovrei creare una funzione per cmp ?

Se sto chiedendo troppo, non ti preoccupare, grazie lo stesso, almeno ho approfondito di più sulla parte ricorsiva.
Comunque oltre al fatto che ho letto tutto il libro, ho ricercato anche sull'indice anlitico dello stesso, ma nada.
Naturalmente ho cercato la cosa che più si avvicinava a "funzione di comparazione", ma niente (evidentemente approfondisce altro).


Se non puoi spiegarmi, sai indicarmi qualche libro o dispensa online, dove posso approfondire l'argomento(se ne hai mai usati/e)?
Ho praticamente letto anche tutta la roba su questo sito, spero non mi sia sfuggita.