Newsgroup: it.comp.lang.c
Titolo: Labirinto e chiamata fantasma di free()

Ciao a tutti
Sono un principiante e sto provando ad automatizzare la risoluzione di
un comune labirinto, come quelli dell'enigmistica, sfruttando gli alberi
binari (i nodi non hanno più di due diramazioni).
Il programma mi restituisce un bel Segmentation Fault, con gdb ho visto
che esce al momento di chiamare free(), ma io non ho usato questa
funzione nel mio programma.
Ho provato a fare backtrace, ma mi restituisce una lista praticamente
infinita, il che mi fa pensare ad un probelma nelle funzioni ricorsive,
ma non riesco ancora a capire da chi è chiamata free().
Il sorgente lo trovate qui:
http://www.rafb.net/paste/results/z59MBb29.html
Breve descrizione del programma:
Il programma costruisce un albero binario che rappresenta il labirinto
tramite la funzione buildtree(), ogni casella libera del labirinto è
rappresentata da un nodo dell'albero, se da questa casella si diramano
due vie il nodo avrà due rami figli, altrimenti uno punterà punterà a
NULL e l'altro alla casella successiva. La funzione buildtree costruisce
l'albero nodo per nodo, analizzando ogni casella tramite la funzione
ways() e richiamandosi ricorsivamente su ciascuna via disponibile
rilevata da ways(). Per il momento il programma è tarato su una matrice
di prova 10x10.
Secondo voi l'approccio al problema in sè è corretto?
Un saluto a tutti e buone feste
Marco

 
Non ho analizzato la logica, ma 'addnode' ha sicuramente degli errori:
 1. il valore del parametro 'treep' viene sovrascritto immediatamente. Ciò 
non ha alcun senso.
 2. 'addnode' viene invocata ricorsivamente, e l'unica situazione che fa 
interrompere la ricorsione è quella in cui cmp vale 0 (e il programma 
stampa "addnode: duplicate entry"). Eseguendo il programma, tale condizione 
non non si verifica.
Controlla meglio la logica e eseguilo passo-passo con GDB. Se 
usare GDB ti complica la vita, inserisci almeno delle istruzioni che 
stampino nome funzione e valori vari, in modo da seguire il flusso 
dell'esecuzione e capire se il programma sta facendo quello che pensi.
Max

 non non si verifica.
Hai ragione, ho modificato la funzione addnode() e ora non si richiama
più all'infinito e poi ho tolto quell'assegnamento di treep all'inizio
perchè effettivamente non aveva senso, ecco il codice:
Position *addnode(Position *treep, Position *newp) {
	int cmp; 
	if (treep == NULL)
		return newp;
	cmp = numcmp(newp->x + newp->y, treep->x + treep->y); 
	if (cmp == 0)
		printf("addnode: duplicate entry\n");
	else if (cmp < 0) {
		treep->left = addnode(treep->left, newp);
		return treep->left;
	}
	else {
		treep->right = addnode(treep->right, newp);
		return treep->right;
	}
	return treep;
}
Ora eseguendo il programma restituisce "addnode: duplicate entry" e poi
Segmentation Fault. Credo che questo sia dovuto al fatto che la prima
volta che addnode viene chiamata i suoi argomenti, tree e root,
conicidono, infatti sono entrambi il puntatore Position *tree. Quindi
devo trattare il primo nodo in modo diverso...
Grazie dell'aiuto :)

Segmentation fault risolto definitivamente, corregendo le seguenti linee
in addway():
if (nd->left == NULL) {
		nd->left = addnode(nd->left, newnode);
}
else if (nd->right == NULL) {
		nd->right = addnode(nd->right, newnode);
}
Ora però mi dice che il labirinto non ha uscita e comunque il problema
del primo nodo rimane, vedrò...
Ciao e grazie ancora :)