PDA

Visualizza la versione completa : [C] Codice ricorsivo deallocazione lista


felpone
14-10-2012, 13:59
typedef int itemType;

typedef struct listNode listNode;
typedef listNode *List;
struct listNode {
itemType item;
List next;
};







void freeListR(List head){
if (head==NULL) return;
freeListR(head->next);
free(head);
}



Salve, nella funzione ricorsiva freelistr non riesco a capire come si faccia ad arivare all ultimariga di codice free(head) se appena prima c' la chiamata ricorsiva...

MItaly
14-10-2012, 14:06
La chiamata ricorsiva dealloca tutti i nodi successivi, quindi ritorna, a quel punto viene eseguita la free.
Facciamo un esempio con una lista di tre elementi: chiami freeListR sul primo elemento; head!=NULL, quindi la funzione non esce e richiama s stessa sull'elemento successivo; accade la stessa cosa per questo elemento e per quello successivo.
Al terzo livello di ricorsione freeListR viene richiamata con NULL (dato che siamo all'ultimo elemento, head->next NULL), il che fa s che al quarto livello di ricorsione freeListR ritorni immediatamente. A questo punto viene eseguita la free al terzo livello di ricorsione e la funzione ritorna; idem per il secondo e il primo livello di ricorsione. Quando la "prima chiamata" a freeListR ritorna tutta la lista stata deallocata.

Vincenzo1968
14-10-2012, 17:17
Meglio, comunque, usare la versione iterativa:



void FreeList(List *head)
{
List *n1 = head, *n2;

while ( n1 != NULL )
{
n2 = n1->next;
free(n1);
n1 = n2;
}
}

Loading