[C] Contare nodi cancellati in lista tramite funzione ricorsiva

[iz8eej]

Salve a tutti ho realizzato una funzione che ricorsivamente cancella tutti i nodi di una lista multipli di tre ricevuta in input.La funzione restituisce la lista modificata e riceve anche una variabile di tipo puntatore che dovrebbe tenere traccia del numero di nodi cancellati.La funzione che ho realizzato sulla lista opera perfettamente ma non riesce a tenere traccia del numero di nodi cancellati.Come potrei implementare l'uso della vbariabile ?

le limitazioni sono che, non posso modificare il main, ne definire una var globale, e non posso modificare i parametri in input e output della funzione, sono il suo contenuto.

la funzione:

Tipo_lista elimina_multipli_tre_ric(Tipo_lista l, int *n)
{
 if (l == NULL)
   {
        *n = 0;
        return NULL;
   }
 if (l->Next == NULL)
        {
          if (l->Value % 3 == 0)
           {
            *n = *n+1;
            free(l);
            return NULL;
           }
          else
           {
            *n = 0;
            return l;
           }
         }
 else
  {
    if (l->Value %3 == 0)
      {
                *n = *n+1;
                Tipo_lista temp;
                temp = l;
                l = l->Next;
                free(temp);
                l = elimina_multipli_tre_ric(l, n);
                return l;
      }
       else
      {
               l->Next = elimina_multipli_tre_ric(l->Next, n);
               return l;
      }
   }
}

il resto del programma:

#include <stdio.h>
#include <stdlib.h>



// definizione della struttura

struct Tag_nodo
{
 int Value;
 struct Tag_nodo *Next;
};

typedef struct Tag_nodo Tipo_nodo;
typedef Tipo_nodo *Tipo_lista;



// prototipi delle funzioni

Tipo_lista insert_ric(Tipo_lista l, int val);
int conta_nodi_ric(Tipo_lista l);
Tipo_lista elimina_multipli_tre_ric(Tipo_lista l, int *n);
void stampa_ric(Tipo_lista l);
int inserisci_in_stack(int numero, int stack[],int sp);
void stampa_stack(int stack[], int sp);


//main

int main()
{
  Tipo_lista l = NULL;
  int n;
  int sp = 0;
  int stack[10];

  l = insert_ric(l, 3);
  l = insert_ric(l, 6);
  l = insert_ric(l, 8);
  l = insert_ric(l, 5);
  l = insert_ric(l, 12);
  l = insert_ric(l, 4);

   printf("\n\n");

   stampa_ric(l);

   printf("\nLa lista contiene %d nodi\n\n", conta_nodi_ric(l));

   l =  elimina_multipli_tre_ric(l, &n);

   sp = inserisci_in_stack(n, stack, sp);

   printf("\nsp = %d\n", sp);

   printf("\nn = %d\n\n", n);

   stampa_ric(l);

   stampa_stack(stack, sp);

      system("PAUSE");
      return 0;
}




// Funzioni



Tipo_lista insert_ric(Tipo_lista l, int val)
 {
   if ((l == NULL) || (l->Value > val))    // se la lista è vuota o l'inserimento è in testa
     {
      Tipo_lista Temp;
      Temp = (Tipo_lista)malloc(sizeof(Tipo_nodo));
      if (Temp == NULL)
       {
        printf("Errore di allocazione nodo nella memoria");
        exit(1);
       }
       Temp->Value = val;
       Temp->Next = l;
       return Temp;
       }
   else
    {
     l->Next = insert_ric(l->Next, val);
     return l;
    }
  }


int conta_nodi_ric(Tipo_lista l)
 {
  if (l == NULL)
      return 0;
  else
      return conta_nodi_ric(l->Next) + 1;
}



void stampa_ric(Tipo_lista l)
 {
  if (l == NULL)
  return;
  else
  {
   printf("%d\n", l->Value);
   stampa_ric(l->Next);
   }
 }



int inserisci_in_stack(int numero, int stack[],int sp)
{
 stack[sp] = numero;
 sp = sp + 1;
 return sp;
 }



void stampa_stack(int stack[], int sp)
{
   int i;
   
   printf("\nElementi dello stack\n");
   for (i=sp-1; i>=0; i--)
       printf("%d\n", stack[i]);
}

grazie a tutti

[{Bl4d3}]

Tipo_lista elimina_multipli_tre_ric(Tipo_lista l, int *n)
{
  if (l == NULL)
    return NULL;
  else
  {
    if (l->Value %3 == 0)
    {
      *n = *n+1;
      Tipo_lista temp;
      temp = l;
      l = l->Next;
      free(temp);
      return elimina_multipli_tre_ric(l, n);
    }
    else
    {
      l->Next = elimina_multipli_tre_ric(l->Next, n);
      return l;
    }
  }
}

[iz8eej]

l'ho provata ma n da solo numeri a casaccio.

Questo approccio alla funzione lo avevo fatto prima di realizzare quella che ho postato.
Inoltre, questo approccio alla funzione, secondo quanto dice il prof., è sbagliato (anche se funziona) in quanto per il metodo "divide et impera", bisogna implementare la funzione prima nel caso in cui la lista abbia un solo nodo.In questo modo la divisione del problema è più chiara.

[{Bl4d3}]

lasciando stare le idee del tuo professore sul metodo divide-et-impera (quelle sono personali)... non avevo visto il main, n ti dà numeri a casaccio perchè non l'hai inizializzata a 0 (cosa che dovresti sempre fare), quindi somma 1 ad un valore che c'era già prima:

int main()
{
  ...
  int n = 0;
  ...
}

vedi un pò...

[iz8eej]

ammesso che che io non posso modificare il main ? (come ho specificato nel post)

per esempio la funzione:

int conta_nodi_ric(Tipo_lista l)
 {
  if (l == NULL)
      return 0;
  else
      return conta_nodi_ric(l->Next) + 1;
}

non viene inizializzata ma ritorna il valore esatto come mai ?

grazie

[{Bl4d3}]

Originariamente inviato da iz8eej
ammesso che che io non posso modificare il main ? (come ho specificato nel post)

per esempio la funzione:

int conta_nodi_ric(Tipo_lista l)
 {
  if (l == NULL)
      return 0;
  else
      return conta_nodi_ric(l->Next) + 1;
}

non viene inizializzata ma ritorna il valore esatto come mai ?

grazie

questo funziona perchè la funziona ritorna un valore intero, non deve modificare una variabile già esistente.

Per quanto riguarda la funzione in questione allora deve essere strutturata in un altro modo:

Tipo_lista elimina_multipli_tre_ric(Tipo_lista l, int *n)
{
 if (l == NULL)
   {
        *n = 0;
        return NULL;
   }
 if (l->Next == NULL)
        {
          if (l->Value % 3 == 0)
           {
            *n = 1;
            free(l);
            return NULL;
           }
          else
           {
            *n = 0;
            return l;
           }
         }
 else
  {
    l->next = elimina_multipli_tre_ric(l->next, n);
    if (l->Value %3 == 0)
      {
                *n = *n+1;
                Tipo_lista temp;
                temp = l;
                l = l->Next;
                free(temp);
      }
    return l;
   }
}

vedi se così va...

[iz8eej]

cosi' funziona molte grazie, se posso, come mai nella funzione che ho fatto io non riesce a incrementare la variabile ?

[{Bl4d3}]

perchè nella funzione che fai tu prima aggiungi 1, e poi richiami ricorsivamente sul nodo successivo, quando arriva alla fine, l == NULL mette *n = 0 e quindi perdi tutto.

In quella che ho fatto io fai prima la chiamata ricorsiva, quindi arrivi prima alla fine, pone *n = 0, e poi tornando indietro aggiunge man mano che cancella.

(Secondo me devi capire meglio come funziona la ricorsione)

[iz8eej]

(Secondo me devi capire meglio come funziona la ricorsione)

è quello che sto cercando di fare

In effetti ci sono delle cose che ho compreso e altre che non mi sono molto chiare.
Ad esempio non mi è chiaro come fa ad iterare la funzione se la ricorsione finisce dopo che ha raggiunto la file della lista.Mi spiego:
Appena interviene la chiamata ricorsiva (nel cosa in cui la lista non è vuota) questa "itera" finchè non arriva allultimo nodo(attraverso il ramo del primo if "if (l->Next == NULL)"), e in questo caso pone *n = 0, oppure a 1 e inizializza la var n.Ma a questo punto la ricorsione è terminata e non ho contato i nodi, come fa a contare il resto ?

grazie.

[{Bl4d3}]

Originariamente inviato da iz8eej
è quello che sto cercando di fare

In effetti ci sono delle cose che ho compreso e altre che non mi sono molto chiare.
Ad esempio non mi è chiaro come fa ad iterare la funzione se la ricorsione finisce dopo che ha raggiunto la file della lista.Mi spiego:
Appena interviene la chiamata ricorsiva (nel cosa in cui la lista non è vuota) questa "itera" finchè non arriva allultimo nodo(attraverso il ramo del primo if "if (l->Next == NULL)"), e in questo caso pone *n = 0, oppure a 1 e inizializza la var n.Ma a questo punto la ricorsione è terminata e non ho contato i nodi, come fa a contare il resto ?

grazie.

Scusa, ma hai una lacuna abbastanza grossa sul concetto di ricorsione.

Allora, quando tu fai una chiamata ricorsiva, semplicemente viene fatto un push sullo stack del processo (non so se hai qualche nozione di sistemi operativi), e il processo inizia a lavorare con questo nuovo spazio di indirizzamento. Praticamente la funzione che hai chiamato diventa un elemento di questo stack e viene posto in cima allo stack, quando la chiamata ricorsiva termina viene fatto un pop e il controllo ritorna alla funzione precedente e riprende l'esecuzione dall'istruzione dopo la chiamata ricorsiva.
Quindi questa funzione chiama ricorsivamente, quando arriva alla fine man mano ritorna indietro nelle chiamate ricorsive, ed effettua le operzioni che deve fare. Non so se sono stato chiaro, ti consiglio di cercare un pò in rete per informarti un pò.

Prova a cominciare da qui:
http://en.wikipedia.org/wiki/Recursi...ter_science%29
http://it.wikipedia.org/wiki/Ricorsione