[C] Problema semplice con liste e ricorsione

[-Ivan-]

Premesso che tutto il main e le altre funzioni non contengono errori, io ho scritto questa funzione:

lista *precedente(lista *temp, lista *testa)
{
    while(temp!=testa)
    {
         precedente(temp->prec, testa);
         return temp;
    }
}

e la richiamo qua:

while (temp != testa)
     { 
          if (temp->simbolo == precedente(temp, testa)->simbolo)
          {
               printf("\n trovata: %c", temp->simbolo);
               getch();
          }
          temp=temp->prec;
     }

In sostanza ho una lista con collegamenti al precedente ed al successivo elemento che contengono in simbolo una lettera.
Io devo partire dall'ultimo elemento e cercare se ce ne sono altri che contengono la stessa lettera.
Il codice scritto sopre ristampa la lista invece di stampare solo le lettere che sono presenti più di una volta.

[tglman]

via subito con un paio di perplessita!

ma come funziona la funzione precedente??

Quale il suo scopo ??

[cionci]

Sinceramente non capisco cosa vuoi fare con quella funzione... A me sembra che ritorni sempre il valore passato come primo parametro...

Attenzione che getch non è una funzione che appartiene alla libreria standard del C...

[tglman]

è normale che quel codice si comporti cosi!!

forse doveva essere seplicemente cosi:

lista *coda =temp;
temp=temp->prec;
while (temp != testa)
     { 
          if (temp->simbolo == coda->simbolo)
          {
               printf("\n trovata: %c", temp->simbolo);
               getch();
          }
          temp=temp->prec;
     }

[-Ivan-]

Originariamente inviato da tglman

via subito con un paio di perplessita!

ma come funziona la funzione precedente??

Quale il suo scopo ??

Sarebbe farmi tornare sempre l'elemento precedente a quello da cui parto e che poi uso per confrontarlo qui:
if (temp->simbolo == precedente(temp, testa)->simbolo)

[-Ivan-]

Originariamente inviato da tglman

è normale che quel codice si comporti cosi!!

forse doveva essere seplicemente cosi:

lista *coda =temp;
temp=temp->prec;
while (temp != testa)
     { 
          if (temp->simbolo == coda->simbolo)
          {
               printf("\n trovata: %c", temp->simbolo);
               getch();
          }
          temp=temp->prec;
     }

Ma così non mi confronta solo un elemento con il precedente e poi il precedente con il precedente ancora?
Io dovrei fare:
if (temp->simbolo == temp->prec->simbolo || temp->simbolo == temp->prec->prec->simbolo || temp->simbolo == temp->prec->prec->prec->simbolo eccetera)
tanto per farvi capire, cioè devo confrontare ogni elemento con tutti gli altri. In realtà poi devo eliminarlo enon stampare una scritta a video però questo non c'entra ora.
Il problema è la funzione ricorsiva che mi permette di confrontare un elemento con tutti gli altri che non riesco a fare, io con la ricorsione non ci sono mai andato d'accordo.

[cionci]

Quella funzione non funziona

Primo il while è inutile...visto che viene eseguito subito il return...
Secondo a cosa ti serve la ricorsione se non sfrutti il valore ritornato dalla ricorsione ?
Terzo cosa ritorna quella funzione se temp è uguale a testa ?

[-Ivan-]

Originariamente inviato da cionci

Sinceramente non capisco cosa vuoi fare con quella funzione... A me sembra che ritorni sempre il valore passato come primo parametro...

Attenzione che getch non è una funzione che appartiene alla libreria standard del C...

Anche al compilatore gli sembra così .

[cionci]

In pratica tu vuoi ottenere tutti gli elementi duplicati presenti nella lista ?

Come faresti con un vettore ? Con la lista devi fare nello stesso modo...
Ti faccio vedere con un vettore:

for(i = 0; i < n; ++i)
   for(j = 0; j < n; ++j)
     if(v[i] = v[j] && j != i) 
         /* questo elemento è doppio */

j != i va messo perchè ogni elemento altrimenti sarebbe doppio di se stesso

Stessa cosa con la lista, traduciamo passo per passo:

for(i=0; i<n; ++i)

for(inizializzazione; condizione di arresto; avanzamento)

Parto dal presupposto che tu voglia fare un controllo partire dal fondo, visto che hai una lista doppiamente linkata o linkata all'indietro.

for(p1 = coda; p1 != NULL; p1 = p1->prec)

Stessa cosa per l'altro for:

for(p2 = coda; p2 != NULL; p2 = p2->prec)

Ovviamente testa->prec deve essere NULL per funzionare
Il resto te lo lascio fare a te

[-Ivan-]

Originariamente inviato da cionci

In pratica tu vuoi ottenere tutti gli elementi duplicati presenti nella lista ?

Come faresti con un vettore ? Con la lista devi fare nello stesso modo...
Ti faccio vedere con un vettore:

for(i = 0; i < n; ++i)
   for(j = 0; j < n; ++j)
     if(v[i] = v[j] && j != i) 
         /* questo elemento è doppio */

j != i va messo perchè ogni elemento altrimenti sarebbe doppio di se stesso

Stessa cosa con la lista, traduciamo passo per passo:

for(i=0; i<n; ++i)

for(inizializzazione; condizione di arresto; avanzamento)

Parto dal presupposto che tu voglia fare un controllo partire dal fondo, visto che hai una lista doppiamente linkata o linkata all'indietro.

for(p1 = coda; p1 != NULL; p1 = p1->prec)

Stessa cosa per l'altro for:

for(p2 = coda; p2 != NULL; p2 = p2->prec)

Ovviamente testa->prec deve essere NULL per funzionare
Il resto te lo lascio fare a te

Così lo sapevo fare solo che non mi piace molto, mi sembrava ci fosse un modo per farlo con una funzione ricorsiva che era un po' più elegante come metodo.
Vabbè se proprio non funziona stasera lo faccio così, grazie dell'aiuto a tutti.

ps:
prima di usare liste usavo vettori ed avevo scritto questa:

int successivo(int i, int len)
{
    while(i>len)
    {
         successivo(i, len);
         return i+1;
    }
}

e la utilizzavo allo stesso modo, solo che questa funzionava.

[cionci]

Originariamente inviato da -Ivan-

prima di usare liste usavo vettori ed avevo scritto questa:

int successivo(int i, int len)
{
    while(i>len)
    {
         successivo(i, len);
         return i+1;
    }
}

e la utilizzavo allo stesso modo, solo che questa funzionava.

Mah...a me sembra che abbia gli stessi identici errori che hai fatto sulla prima La ricorsione non fa niente, la funzione ritorna sempre i + 1 e il while non ha senso.

[-Ivan-]

Originariamente inviato da cionci

Mah...a me sembra che abbia gli stessi identici errori che hai fatto sulla prima La ricorsione non fa niente, la funzione ritorna sempre i + 1 e il while non ha senso.

Si probabilmente è scritta malissimo perchè come ho già detto con la ricorsione non ho molta confidenza, però funzionava, nel senso che a me serviva che restituisse tutti gli "i" a partire da quello dato in avanti per fare il controllo su ogni elemento del vettore senza dover usare due for.

[cionci]

Non è che è scritta male...quella funzione non fa altro che ritornare i+1 !!!

Cioè puoi riscrivere la funzione successivo in questo modo:

int successivo(int i, int len)
{
    if(i<len)
         return i+1;
}

Nota che sia in questa che ho scritto ora che in quella che hai scritto te c'è lo stesso errore. Se i >= len cosa fa ? Non l'hai definito. Il compilatore ti avrebbe dovuto segnalare l'errore...

Ti provo a fare una lezioncina per spiegarti come funziona la ricorsione.
Quando scrivi una funzione ricorsiva devi sempre immaginarti due situazioni: la prima è quella in cui la ricorsione si arresta. La secondo è quella alternativa, in cui sai per certo di avere un dato valido su cui lavorare.

Per una lista la condizione di arresto è solitamente quella in cui il valore del puntatore passato alla funzione è pari a NULL.
Ad esempio scriviamo una semplice funzione che ricerca la prima occorrenza di un elemento x in una lista e se lo trova torna il puntatore all'elemento (arrestando al ricorsione), altrimenti ritorna NULL.
E' naturale che si ritorni NULL, in quanto nessuna occorrenza di x è stata trovata.

lista * cerca(lista *l, int x)
{
    if(l == NULL) /* condizione di arresto */
       return NULL;

Ora pensiamo al caso in cui il dato passato è valido...devo verificare il valore del campo dati.

lista * cerca(lista *l, int x)
{
    if(l == NULL) /* condizione di arresto */
       return NULL; 
    else
       if(l->info == x) /* verifico che l'elemento puntato abbia il valore x */
          return l; /* ho trovato la prima occorrenza di x, ritorno il puntatore e arresto la ricorsione*/
       else
           /* ora devo effetture la ricorsione perché non ho trovato il valore x */
           return cerca(l->next, x); /* ritorno subito il risultato perché non ci devo altre operazioni */
    return NULL; /* qualche compilatore ti restituisce uno warning se non c'è questo return, anche se è irraggiungibile */
}

Faccio un po' di pulizia per evitare qualche else o return di troppo

lista * cerca(lista *l, int x)
{
    if(l != NULL)
    {
       if(l->info == x) 
       {
          return l; 
       }
       else
       {
          return cerca(l->next, x); 
       }
   }
   /* questo return viene raggiunto solo se l è NULL, quindi è la nostra condizione di arresto */
   return NULL; 
}