Newsgroup: it.comp.lang.c
Titolo: Ancora Alberi Binari!! :(((

ciao a tutti,
siccome sono un masochista, dopo aver risolto il piccolo problemino del
codice postato alcuni giorni fa, ho scritto un programmino un po' piů
complesso:
prelevare da file dei record, inserirli in un albero binario di ricerca
ordinandoli con un campo chiamato "key", riscriverli in modo ordinato in
un'altro file;
In pratica il mio problema non č piů segmentation fault ma se inserisco una
sequenza disordinata di valori, questi non vengono ordinati, anzi appaiono
ancora piů disordinati.
Il bello delle due funzioni č che devono rispettare categoricamente il
prototipo dato dal mio professore e cioč:
int leggi(char *filename, void **root);
int scrivi(char *filename, void *root);
Non riesco a capire inoltre perchč i secondi argomenti vengono dichiarati
con void anzichč con NODO.
#include <stdio.h>
#include <stdlib.h>
typedef struct record
{ int key;
  char info[20];
} REC;
typedef struct nodo
{ REC rec;
  struct nodo *left, *right;
} NODO;
int leggi(char *filename, void **root)
{ FILE *f;
  REC r;
  if(!(f=fopen(filename,"r"))) return -1;
  while(fread(&r,sizeof(REC),1,f))
    insert(root, r);
  fclose(f);
  return 1;
}
int insert(NODO **ptr, REC r)
{
/* se l'albero esiste */
if(*ptr)
    if((*ptr)->rec.key <= r.key)
         insert((&(*ptr)->right), r);
    else
         insert((&(*ptr)->left), r);
  else
/* se l'albero non esiste, viene creata la radice */
  { *Qui ho tolto il cast per fare contenti tutti ;-) */
     *ptr = malloc(sizeof(NODO));
    (*ptr)->rec = r;
    (*ptr)->right = (*ptr)->left = NULL;
  }
}
int scrivi(char *filename, void *root)
{
FILE *fd;
/* posso usare questo assegnamento e poi usare ptr invece che root???*/
NODO *ptr = root;
/* se il file non esiste */
if(!(fd = fopen(filename,"a")))
     return -1;
/* se l'albero non esiste */
if(ptr == NULL)
     return 0;
/* stampa dell'albero ordinato */
if(ptr->left != NULL) scrivi(filename, (ptr)->left);
fwrite(&(ptr->rec), sizeof(REC), 1, fd);
if(ptr->right != NULL) scrivi(filename, (ptr)->right);
fclose(fd);
return 1;
}
main()
{
NODO *ptr=NULL;
leggi("leggi.bin", &ptr);
scrivi("letto.bin", ptr);
printf("File ordinato in letto.bin\n");
}
ps: non fate come l'ultima volta perň, ci sono rimasto un po' maluccio
sapere che la causa dei vostri litigi č stata colpa mia...
grazie mille
ciao,
Luca

 sapere che la causa dei vostri litigi è stata colpa mia...
Ci sei rimasto male ?!? Proprio per quel motivo il post si e' ingigantito e
tra cavolate e cose utili alla fine di cose utili ce ne erano parecchie.
Quando succedono queste cose si approfondisce meglio l'argomeno. Peccato che
non tutti la pensino cosi' e che alcuni siano volgari.
Alex

 close(fd);
fclose... ovviamente...
Alex

 e non un REC visto che ti ostini a tenerla ricorsiva.
Tu hai qualche esempio di una funzione simile a questa in modo iterativo da
postarmi?
Luca

 postarmi?
E' un semplice while !
... funzione(...)
{
........
while(scan){
.........
  scan=(scan->val<=n)?(scan->right):(scan->left);
.........
 }
.........
}
Prova di implementarla tu e se non riesci te la posto volentieri !
(scusa se mi comporto cosi' ma altrimenti che esercizio e' ?!?)
Alex
P.S. ti do il mio modesto parere: l'esercizio, cosi' come te lo ha dato il
professore, e' veramente brutto e troppo restrittivo (oltre al fatto che non
mi piace la implementazione che ti costringe ad utilizzare).

 mi piace la implementazione che ti costringe ad utilizzare).
prova a parlare con il mio professore :-)))
ciao
luca

 ammazza la semplicita' :)) (o sono io negato???)
La funzione che ti presento e' piu' lunga in quanto fa un po' piu' cose:
(se vuoi puoi sempre snellirla pero' !)
int insert(nodo **ptr, int n)
{
     nodo *new_node=malloc(sizeof(nodo));
     nodo *prev_node=NULL;
     nodo *scan=*ptr;
     if(new_node){
          new_node->left=new_node->right=NULL;
          new_node->val=n;
     }else return 0;     /* fallito */
     if(*ptr){
          while(scan){
               prev_node=scan;
               scan=(scan->val<=n)?(scan->right):(scan->left);
          }
          if(prev_node->val<=n) prev_node->right=new_node;
          else prev_node->left=new_node;
     }else{
          *ptr=new_node;
     }
     return 1;     /* successo */
}
Allora con:
if(!insert(&tree,num))
     puts("Inserimento fallito!");
Ecco, in questo modo, in main(), sai se l'inserimento e' avvenuto o meno con
successo.
Per questo stesso motivo la funzione di inserimento ritorna un int (e non e'
void). Ritorna 0 nel caso di fallimento ed 1 di successo.
Se, nella funzione di inserimento, cambi l'allocazione in:
nodo *new_node=NULL; /*malloc(sizeof(nodo)); */
(per forzarne il fallimento) vedrai che il programma ti avverte che
l'inserimento e' fallito ma il programma non si blocca. (provalo!) Se non
avviene l'allocazione ritorna 0.
SOLO se e' avvenuta l'allocazione della memoria (altrimenti si avrebbero dei
grossi problemi) setta il nuovo nodo (new_node): left=NULL, right=NULL e
val=n.
In pratica questo controllo e' opzionale e volendo puoi non metterlo (come
nella tua versione) snellendo cosi' la funzione. (e quindi rimettendo void
invece di int).
Dopo di che un if cerca di capire se il puntatore dato e' NULL (albero vuoto
nella maggior parte dei casi) oppure no.
Se l'albero risulta vuoto (ramo else) imposta *ptr su new_node cambiandone
cosi' il valore (di solito questo corrisponde al primo inserimento).
Se invece if(*ptr) viene valutato come true, il semplice while che
sostituisce la ricorsione, arriva fino alla posizione in cui va messo il
nuovo nodo (new_node).
prev_node e' appunto il padre di tale posizione (scan invece sarebbe la vera
posizione, solo che non esistendo ancora e' ovviamente NULL) e quindi si
setta prev_node->right oppure prev_node->left su new_node (a seconda del
valore di prev_node rispetto al nuovo valore n da inserire).
Per finire la funzione ritorna 1 ad indicare il successo.
Di seguito ti propongo il programma completo con tanto di main().
In tutto il programma funzione completa ho cercato di usare dei nomi simili
se non uguali a quelli che hai usato tu per non crearti confusione.
Spero solo che non vengano spezzate le righe :-(
#include<stdio.h>
#include<stdlib.h>
typedef struct nodo
{
     int val;
     struct nodo *left;
     struct nodo *right;
}nodo;
int insert(nodo  **ptr, int n);
void write(nodo *ptr);
void destroy(nodo **ptr);
int main()
{
     int num;
     nodo *tree=NULL;
     printf("Inserisci dei numeri (0=FINE):\n");
     for(;;){
          scanf("%d",&num);
          if(num==0) break;
          if(!insert(&tree,num))
               puts("Inserimento fallito!");
     }
     write(tree);
     destroy(&tree);
     write(tree);     /* Con albero vuoto no da errore! */
     return 0;
}
int insert(nodo **ptr, int n)
{
     nodo *new_node=malloc(sizeof(nodo));
     nodo *prev_node=NULL;
     nodo *scan=*ptr;
     if(new_node){
          new_node->left=new_node->right=NULL;
          new_node->val=n;
     }else return 0;     /* fallito */
     if(*ptr){
          while(scan){
               prev_node=scan;
               scan=(scan->val<=n)?(scan->right):(scan->left);
          }
          if(prev_node->val<=n) prev_node->right=new_node;
          else prev_node->left=new_node;
     }else{
          *ptr=new_node;
     }
     return 1;     /* successo */
}
void write(nodo *ptr)
{
     if(ptr)
     {
          write(ptr->left);
          printf("%d ",ptr->val);
          write(ptr->right);
     }
}
void destroy(nodo **ptr)
{
     if(*ptr){
          destroy(&(*ptr)->left);
          destroy(&(*ptr)->right);
          free(*ptr);
          *ptr=NULL;
     }
}
/* EOF */
Questo e' un breve esempio.... (spero vada bene, non ci ho perso molto
tempo!)
Il vantaggio della funzione insersci iterativa e' il minor uso della memoria
(che si traduce anche in prestazioni) e l'assenza del costo di aggiuntive
chiamate di funzione che va a scapito delle prestazioni. Da test eseguiti in
risposta a iGor:
"(con rand()%10000 e profondita' 100, circa 400.000 inserimenti) tra
l'inserimento ricorsivo ed iterativo): Il programma chiamando la funzione
iterativa ci mette: 8 secondi circa.
Lo stesso programma chiamando quella ricorsiva ci mette: 12,5 secondi
circa. Inoltre, anche se diventa meno elegante, se nella versione iterativa
metto tutte le variabili static allora arrivo a 7,5. (e' assurdo provare a
farlo con la ricorsiva)."
Il codice e' appena piu' lungo di quello ricorsivo, ma non e' certamente
complicato. Fidati che ne vale la pena, anche se non garantisco che (visto
come sono i professori) il professore l'apprezzera'! D'altro canto potrebbe
anche non apprezzare quella ricorsiva !
Inoltre, come ha fatto notare MachKernel, anche il Cormen-Leiserson-Rivest
(che e' IL testo universitario) presenta questo "algoritmo" in versione
iterativa !
Alex