Problema con albero binario in c++

[Unrue]

Dunque,
sto costruendo un algoritmo di Huffman. Il compressore l'ho scritto e credo funzioni bene. Ho un problema però in fase di decompressione. In pratica, con file piccolo, dai 30kb in giù funziona bene, altrimenti si blocca dopo circa 6000/8000 scritture. Questo è il codice:

void Decompressore::decomprimi

(Decompressore*node,int*i,int*numerodisimboliletti,int*simbolitemporanei,FILE*in,FILE*out2){

if(((*i)>7))

{ v=0;

fread(&v,sizeof(unsigned char),1,in);

(*i)=0;

}

if(((*simbolitemporanei)<(*numerodisimboliletti))){

if ((node->left==NULL)&&(node->right==NULL)&&(node->frequenza!=0))
{
fwrite(&node->codice,sizeof(unsigned char),1,out2);

(*simbolitemporanei)++;

decomprimi(PHuff [posiniziale],i,numerodisimboliletti,simbolitemporanei,in,out2);
}
else {
c=v&(1<<(7-(*i)));

(*i)++;

if(c!=0)

{
decomprimi(node>right,i,numerodisimboliletti,simbolitemporanei,in,out2);

}

else {

decomprimi(node->left,i,numerodisimboliletti,simbolitemporanei,in,out2);

}
}


}

}

Dunque, Decompressore*node è il puntatore all'albero in cui vi sono i simboli letti dal file originario. In ogni nodo sono presenti il codice, la frequenza il puntatore al nodo dx ed il puntatore al nodo sx. Numerodisimboliletti è invece il totale appunto dei simboli letti dal file originale. Pe riprova, ho inserito tale codice direttamente nel programma di compressione, per vedere se il problema dipendeva dal salvataggio del file compresso e della struttura in cui annoto i simboli e le frequenze( per ricostruire l'albero), ma non è cambiato nulla.

[GioVesas]

Non ho analizzato il tuo codice, ma la tua nota che tutto funziona fino ai 30Kb mi fa venire in mente i problemi che ho avuto nel trattare stringhe di char più lunghe di 32Kb e problemi di allocazione di dati su puntatori short.

[Unrue]

Non ho analizzato il tuo codice, ma la tua nota che tutto funziona fino ai 30Kb mi fa venire in mente i problemi che ho avuto nel trattare stringhe di char più lunghe di 32Kb e problemi di allocazione di dati su puntatori short.


Ma la cosa più strana è che quando cerco di decomprimere files grandi, si blocca dopo aver scritto 3k o 4k in tutto Aprendo il piccolo file che ha decompresso e confrontandolo con quello originale, i simboli sono tutti giusti! In pratica, quel poco che mi decomprime è giusto. quindi ora penso: se fosse sbagliato l'algoritmo di decompressione, oltre che bloccarsi, dovrebbe sbagliare i simboli. Ma non è così. Il guaio è che non riesco neanche ad isolare l'errore, in quanto il compilatore C++Builder X , facendo il debug, non mi indica l'istruzione che dà l'errore, ma mi indica un'istruzione in assembler, che secondo lui fa un' "application defined-exception" . :muro:

[GioVesas]

E' difficile dire dove e quale errore.
L'unica cosa poco pulita é che
if ((node->left==NULL)&&(node->right==NULL)&&(node->frequenza!=0))
{
}
else
{
qui utilizzi ->left e ->right, ma sei sicuro che non siano NULL quando richiami nuovamente la decomprimi?
}

Prova a fare un test in ingresso alla decomprimi se node == NULL

[Unrue]

E' difficile dire dove e quale errore.
L'unica cosa poco pulita é che
if ((node->left==NULL)&&(node->right==NULL)&&(node->frequenza!=0))
{
}
else
{
qui utilizzi ->left e ->right, ma sei sicuro che non siano NULL quando richiami nuovamente la decomprimi?
}

Prova a fare un test in ingresso alla decomprimi se node == NULL

Avevo provato a farlo, ma non risultano esserci nodi nulli, anche perchè con file di grosse dimensioni è difficile avere meno di 256 simboli, che sono quelli toali dell'ASCII. Mi è venuta in mente una possibile causa: non è per caso che tali file hanno più di 256 simboli, usando il codice ASCII esteso?( o UNICODE, insomma quello, non ricordo il nome :p ) Però se cosi' fosse, dovrebbe dare problemi anche in fase di compressione presumo.

[cdimauro]

Perché non esegui un debug passo passo finché non arrivi alla condizione dell'errore? Altrimenti rischi di continuare a brancolare nel buio...

[GioVesas]

Altra possibilità:
tu richiami ricorsivamente la stessa funzione: non può essere un problema di stack ?
Come dice unrue, prova a fare un debug. inserendo eventualmente un contatore dei nesting della funzione

[Unrue]

Altra possibilità:
tu richiami ricorsivamente la stessa funzione: non può essere un problema di stack ?
Come dice unrue, prova a fare un debug. inserendo eventualmente un contatore dei nesting della funzione

Cos'e' un contatore dei nesting? E in che parte del codice dovrei inserirlo?

[Unrue]

Perché non esegui un debug passo passo finché non arrivi alla condizione dell'errore? Altrimenti rischi di continuare a brancolare nel buio...


Ma sono migliaia di cicli :( Dove dovrei mettere dei breakpoint secondo te?

[GioVesas]

Passo a passo è veramente lunga.
Io farei così:

Puoi definire una variabile esterna alla classe:
int count=0;

poi:

void Decompressore::decomprimi

(Decompressore*node,int*i,int*numerodisimboliletti,int*simbolitemporanei,FILE*in,FILE*out2){

count++;
if (count%100)
printf("%d\n",count);
if(((*i)>7))

Così capisci indicativamente dopo quanto scoppia. Capito il numero, ad es. 5000 fai:

void Decompressore::decomprimi

(Decompressore*node,int*i,int*numerodisimboliletti,int*simbolitemporanei,FILE*in,FILE*out2){

count++;
if (count%100)
printf("%d\n",count);
if (count > 5000)
if (count%10)
printf("%d\n",count);

if(((*i)>7))
Quando hai visto dove sei arrivato (+/- 10) supponi 5020
void Decompressore::decomprimi

(Decompressore*node,int*i,int*numerodisimboliletti,int*simbolitemporanei,FILE*in,FILE*out2){

count++;
if (count%100)
printf("%d\n",count);
if (count > 5020)
printf("%d\n",count);

if(((*i)>7))

e metti un breakpoint sull'ultima printf.

[Unrue]

Allora amico, ho provato con diverse decine di files, e l'errore è sempre lo stesso: il programma si blocca alla chiamata numero 28715 della funzione ricorsiva. L'errore è segnalato nell'istruzione assembler:

77F4ED20 53 PUSH EBX


L'istruzione push scrive nello stack , quindi è proprio un problema di stack. Me lo dà, a seconda del file che comprimo , una delle tre istruzioni che richiama la funzione decomprimi, come puoi vedere dal codice postato in precedenza. Adesso, appurato che è un problema di stack, come si può rimediare? :)

[GioVesas]

Non si può allargare lo stack all'infinito.
L'unica soluzione é fare in modo che la funzione non sia ricorsiva, cioè invece di richiamare se stessa torni con un valore che ti permetta di decidere all'esterno se richiamarla per left o right.

[Unrue]

Non si può allargare lo stack all'infinito.
L'unica soluzione é fare in modo che la funzione non sia ricorsiva, cioè invece di richiamare se stessa torni con un valore che ti permetta di decidere all'esterno se richiamarla per left o right.

Cioè, mi stai dicendo che il problema è che lo stack è troppo piccolo? Ma allora dovrebbe darmi problemi anche in fase di compressione, anche li' uso una funzione ricorsiva, invece no, li' funziona benissimo. E' questo che non capisco.

[cdimauro]

Fai così: usa un IDE decente, che ti permette di controllare le variabili anche dopo che il programma ha generato uno stack fault.
In una variabile, come ti è stato suggerito, memorizzi il livello di ricorsione.
Quando il programma s'interrompe, lo vai a leggere.
Resetti il programma, imposti un breakpoint condizionale (ce l'hanno tutti gli IDE decenti, appunto) e fai in modo di bloccarlo quando il livello di ricorsione ha raggiunto quel valore.
A questo punto controlla passo passo cosa succede, annotati tutti i valori delle variabili interessanti, e cerca di capire da ciò perché il programma è arrivato a quel punto...