PDA

Visualizza la versione completa : cancellare lista c


processore
30-06-2013, 17:11
salve.
sto guardando la soluzione di un esercizio in c data una lista la cancella tutta ricorsivamente.

questo e il codice.


void delete_list(link head) {
if(head_of_list->next)// testa della lista
delete_list(head_of_list->next);
delete_node(head_of_list);
}

//
// funzione ausiliaria di delete_list
//
void delete_node(link node){
node->next = NULL;
node->value = -1;
free(node);
}

quello che non capisco e come fa a eliminare la lista.
nel senso fino a che head->next e vero entra nell'if e richiama ricorsivamente la funzione spostandosi nel prossimo elemento.
mentre la funzione delete_node lo richiama solo quando arriva all'ultimo elemento perche head->next e falso, quindi elimina solo l'ultimo elemento mentre degli altri restano liberi in memoria...

mi potreste delucidare le idee ?? ce un modo piu facile per eliminare la lista ricorsivamente ?

MItaly
30-06-2013, 17:53
La funzione è sbagliata - o l'hai copiata sbagliata; dovrebbe essere:


void delete_list(link head) {
if(head_of_list->next)// testa della lista
{
delete_list(head_of_list->next);
delete_node(head_of_list);
}
}

con delete_node all'interno dell'if, non fuori, altrimenti ottieni un segmentation fault in delete_node arrivato in fondo alla lista.

Ciò detto, il funzionamento è relativamente semplice una volta entrati nella mentalità ricorsiva: cosa devo fare per eliminare una lista? Prima elimino gli elementi che seguono, quindi dealloco l'elemento corrente, ed è esattamente quello che fa la funzione: se non siamo ancora in fondo alla lista, richiama ricorsivamente sé stessa sul prossimo elemento. A questo punto, quando la delete_list è ritornata, sa che tutti gli elementi dopo sono già stati eliminati, e può procedere a deallocare il nodo corrente usando la delete_node.
Il "caso base" è quando la delete_list riceve NULL - in tal caso, non c'è niente da fare e si limita a ritornare.

P.S.: qui come nell'altro thread, ho proceduto a sistemare tra tag
... il codice e ad indentarlo correttamente, in futuro ricordatene.

processore
30-06-2013, 22:06
scusa quello che non riesco a capire è questo :
fino a che non siamo in findo alla lista entra nell'if e richiama la funzione nel prossimo elemento.

ma facendo cosi la funzione non si sposta nel prossimo elemento ?
non dovrebbe richiamare delete_node a ogni chiamata ricorsiva ?


la funzione messa dal prof e cosi. forse ha sbagliato a scrivere


void delete_list(link head) {
if(head_of_list->next)// testa della lista
delete_list(head_of_list->next);
delete_node(head_of_list);
}

MItaly
30-06-2013, 22:40
Scusa, sono io che ho letto male, la funzione è corretta così come l'ha scritta il tuo professore.


fino a che non siamo in findo alla lista entra nell'if e richiama la funzione nel prossimo elemento.

ma facendo cosi la funzione non si sposta nel prossimo elemento ?
non dovrebbe richiamare delete_node a ogni chiamata ricorsiva ?

Infatti lo richiama: ma dopo aver chiamato ricorsivamente sé stessa sul prossimo elemento.

Quello che devi capire è che non è che la funzione attualmente in esecuzione va su un altro elemento: semplicemente, viene chiamata un'altra volta delete_list sul prossimo elemento, e ogni chiamata ricorsiva ha la sua copia dei parametri e delle variabili locali.

Ti faccio un esempio: supponiamo che la lista sia:
elem1 -> elem2 -> elem3 -> (NULL)

Chiamo delete_list su elem1: delete_list controlla che il prossimo elemento non sia nullo, quindi richiama delete_list su elem2; a sua volta, questa fa lo stesso su elem3. La delete_list che sta operando su elem3 vede che il prossimo elemento non è nullo, quindi non fa alcuna chiamata ricorsiva; elimina elem3 e ritorna; ora siamo tornati nella delete_list che sta operando su elem2; la sua istruzione successiva è delete_node(head_of_list), che qui elimina elem2, e ritorna. Ora siamo nella delete_list su elem1: stesso discorso: elimina elem1 e ritorna al chiamante iniziale.

Loading