[C] Liste - Ricorsione

di
Anonimizzato18897
il
3 risposte
/
Anonimizzato18897
Utente anonimizzato

[C] Liste - Ricorsione

Ciao a tutti, stavo cercando di svolgere il seguente esercizio
[testo: data una lista linkata semplice, eliminare tutti gli elementi duplicati consecutivi, senza cambiarne l'ordine relativo
esempio: AAA CCC BBB AAAA diventa A C B A].

Ho preso spunto dalla cancellazione ricorsiva del Sedgewick (Algoritmi in C, III edizione, Pearson, 2002)
Qualcuno può dirmi dove sbaglio nella ricorsione? Ho fornito gli output nell'ultima riga.
Grazie. 




//struttura dati
typedef struct node* link;
struct node{ int data; link next;};


//funzione ricorsiva
void DELETEDUPS(link h){
 
    if(!(h->next)) return;                  		//lista vuota
 
    if(h->data==h->next->data){             	//condizioni per cancellazione
        link t = h->next;
        h->next = h->next->next;
        free(t);
    }
 
    DELETEDUPS(h->next);                    	//ricorsione
    return;
}
 
//input     1-->1-->1-->2-->2-->3-->4-->4-->4-->NULL
//output    1-->1-->2-->3-->4-->4-->NULL

3 Risposte

  • C
    candaluar
    Molto attivo
    Iscritto da
    ago, 2013
    Messaggi:
    1900

    Re: [C] Liste - Ricorsione

    Molto probabilmente invece della if 
    if(h->data==h->next->data)
    devi lavorare con un while() per eliminare tutti gli elementi ripetuti, e non solo il primo, fintantoche h->data è uguale a h->next->data.
  • C
    candaluar
    Molto attivo
    Iscritto da
    ago, 2013
    Messaggi:
    1900

    Re: [C] Liste - Ricorsione

    Oppure, se vuoi essere veramente ricorsivo, quando elimini un elemento successivo dovresti ricontrollare l'elemento corrente perchè il nuovo elemento successivo potrebbe essere ancora uguale 
        if(h->data==h->next->data){                //condizioni per cancellazione
        link t = h->next;
        h->next = h->next->next;
        free(t);
        DELETEDUPS(h);                             //ricorsione
    }
    else
        DELETEDUPS(h->next);                       //ricorsione
  • /
    Anonimizzato18897
    Utente anonimizzato

    Re: [C] Liste - Ricorsione

    Grazie mille candaluar, ho risolto facendo una doppia chiamata ricorsiva.
    void DELETEDUPS(link h){
 
    if(!(h->next) ) return;
 
    while(h->data==h->next->data){
        link t = h->next;
        h->next = h->next->next;
        free(t);
        DELETEDUPS(h);
        return;
    }
 
    DELETEDUPS(h->next);
    return;
}
    Discussione chiusa. Come si può chiudere la discussione?
Devi accedere o registrarti per scrivere nel forum
3 risposte