Deallocazione Ricorsiva Lista

[miki miki]

Volevo sapere la vostra opinione a riguardo di un programma che riceva in ingresso una lista e deallochi quei nodi che non soddisfano un determinato criterio.
Mettiamo che la lista abbia un campo che contenga numeri interi e si voglia deallocare i nodi che contengano numeri negativi

lista sfrondalista (lista L) { 
                                            lista temp; 
                                            if ( L!=NULL) /*finchè non arrivo in fondo*/
                                            { 
                                              if (L->dato<0)  /*se è un numero negativo*/
                                                        {
                                                            temp=L; /*metto in temp il nodo da cancellare*/
                                                             L=L->next;  /*modifico L*/
                                                             free(temp);  /*cancello*/
                                                           }
                                           return sfrondalista(L)  /*faccio l'invocazione ricorsiva*/
                                          }
                                            returnL /* alla fine riottengo L*/
                                        }

che ne dite? potrebbe funzionare? grazie per i vostri suggerimenti

[simo_85]

potrebbe funzionare?

... Prima di chiederlo, hai provato la funzione in un programma tuo?

[miki miki]

è un progetto per l'università...non devo testarlo.....ma solo essere sicuro che il codice sia valido

[YuYevon]

La situazione è un po' più complessa perché innanzitutto devi considerare la deallocazione della testa: in quel caso non puoi soltanto richiamare la free() sul nodo, ma devi anche "aggiornare" il puntatore alla testa della lista che passi alla funzione, e per fare questo devi passare un puntatore a puntatore. Inoltre, anche deallocando nel mezzo, devi considerare l'aggiornamento del puntatore "next" del nodo precedente. Se tu hai tre nodi come

3 -> -1 -> 4

non soltanto devi eliminare il nodo con -1 ma devi anche aggiornare il puntatore next del nodo 3 affinché punti a 4.

Considera poi che la funzione scritta così rischia di ricorrere "all'infinito": infatti l'aggiornamento di L, cioè L = L -> next, lo fai soltanto sotto la condizione if ma non anche all'esterno, quindi se ad un certo punto della lista il dato risultasse > 0 la funzione continuerebbe ad essere richiamata su quello stesso nodo.

[Ippo343]

Originariamente inviato da miki miki
è un progetto per l'università...non devo testarlo.....ma solo essere sicuro che il codice sia valido

E come fai a sapere che è valido se non lo testi? ^^

Comunque, si, è giusta, ma io se fossi in te non modificherei il nodo:

lista sfrondalista(lista L)
{
    if (L == NULL) return NULL;

    lista nextN = L->next;

    if (L->dato < 0) 
        free(L);

    return sfrondalista(nextN);
}

Così è più semplice e più compatta

[miki miki]

mi è sorto pero' un dubbio....se bisogna cancellare un nodo centrale, usando questo programma...la lista rimane concatenata???

mi spiego meglio:
pensiamo di avere questa lista e di dover rimuovere il nodo con 3 però poi 6 sarà collegato con 4

2->4->6->3->4.

il programma una volta deallocato il nodo contenente 3, collega 6 con 4???


credo di no!!!
ci vorrebbe un'altro puntatore che punti al nodo precedente a quello che si sta valutando...o sbaglio??

[YuYevon]

Originariamente inviato da Ippo343
E come fai a sapere che è valido se non lo testi? ^^

Comunque, si, è giusta, ma io se fossi in te non modificherei il nodo:

lista sfrondalista(lista L)
{
    if (L == NULL) return NULL;

    lista nextN = L->next;

    if (L->dato < 0) 
        free(L);

    return sfrondalista(nextN);
}

Così è più semplice e più compatta

Quella funzione restituirà sempre e comunque NULL al programma chiamante, anche se non è stata deallocata tutta la lista; è dovuto al fatto che nel caso base si restituisce NULL, ma questo è il valore che restituiscono anche tutte le altre attivazioni della funzione fino alla prima. La penultima attivazione restituisce quello che restituisce l'ultima (NULL) quindi appunto NULL, la terzultima quello che restituisce la penultima (NULL) quindi di nuovo NULL e così via fino al programma chiamante.

Abbandonando l'idea di passare alla funzione un puntatore a puntatore per l'eliminazione in testa, che in questo caso è forse addirittura impossibile, la mia soluzione (provata in diversi casi e pare funzionante)

typedef struct _node {
  int dato;
  struct _node *next;
} node;

typedef node * node_ptr;

...

node_ptr erase(node_ptr head)
{
  node_ptr temp;
  
  /* caso base: fine lista */
  if (head == NULL) {
    return NULL;
  }
  
  /* caso generico */

  if (head -> next != NULL) {
    head -> next = erase(head -> next);
  }
  
  if (head -> dato < 0) {
    temp = head -> next;
    free(head);
    return temp;
  } else {
    return head;
  }
}

sembra complicata, ma con un po' di carta e penna risulta più o meno facile.

EDIT: il valore restituito dalla funzione al programma chiamante è il puntatore alla (eventualmente nuova) testa della lista. Se tutta la lista è stata deallocata perché tutti i valori sono minori di 0, allora la funzione restituisce correttamente NULL.

[Ippo343]

Si, scusate, l'ho scritta di fretta ed è sbagliata. Sorry