Newsgroup: it.comp.lang.c
Titolo: soluzioni + eleganti?

ciao a tutti!
volevo avere un vostro parere riguardo un programma che memorizza valori
dati in input in un albero binario;
premetto che il programma funziona, che le rischieste che mi sono state
fatte dal committente (il mio prof :) sono state adempite.
da voi volevo solamente, sempre se avete tempo e soprattutto voglia, una
soluzione + "elegante" alla funzione di stampa a video: il mio modus
operandi è stato quello di aggiungere una variabile liv all'interno della
struttura nodo, ossia da:
struct nodo {
  int inf;
  struct nodo *alb_sin;
  struct nodo *alb_des;
};
a
struct nodo {
  int inf;
  char liv; /* aggiunta */
  struct nodo *alb_sin;
  struct nodo *alb_des;
};
con questo "stratagemma" conosco l'indentatura per la stampa di ogni
elemento dell'albero, di conseguenza se un elemento ha liv == 5 e inf == 5
la stampa a video sarà:
<altri elementi>
...
...
     5
...
...
<altri elementi>
ovvero 5 spazi di margine dal margine sinistro.
allego il codice (sotto licenza gpl, che ne sai che me lo rubbbano :)!! ):
/* Creazione di un albero binario e visita in ordine anticipato.
   L'etichetta dei nodi è un valore intero, le occorrenze
   multiple dello stesso valore non vengono memorizzate         */
#include <stdio.h>
#include <malloc.h>
struct nodo {
  int inf;
  char liv;
  struct nodo *alb_sin;
  struct nodo *alb_des;
};
int level=0;
struct nodo *alb_bin(void);
struct nodo *crea_nodo(struct nodo *, int);
void anticipato(struct nodo *);
int main()
{
struct nodo *radice;    /* Puntatore alla radice dell'albero  */
radice = alb_bin();     /* Invoca la funzione per la creazione
                           dell'albero binario                */
printf("\nVISITA IN ORDINE ANTICIPATO\n");
anticipato(radice);
return 0;
}
/* Crea l'albero binario. Per ogni etichetta immessa
   dall'utente, invoca la funzione crea_nodo().
   Ritorna al chiamante la radice dell'albero        */
struct nodo *alb_bin(void)
{
struct nodo *p = NULL;
struct nodo x;
do {
printf("\nInserisci un'informazione (0 per finire): ");
  scanf("%d", &x.inf);
   if(x.inf!=0) {
   p = crea_nodo(p, x.inf);      /* Invoca crea_nodo() */
   }
}
while(x.inf!=0);
return(p);                        /* Ritorna la radice */
}
/* Visita ricorsivamente l'albero alla ricerca del punto di
   inserimento. Quando trova la posizione, crea un nodo, vi
   inserisce l'etichetta e ritorna il puntatore a tale nodo.
   Parametri in ingresso:
      p      è il puntatore alla radice
      val    è l'etichetta da inserire nel nodo             */
struct nodo *crea_nodo(struct nodo *p, int val)
{
if(p==NULL) {       /* Il punto di inserimento è stato reperito */
  /* Creazione del nodo */
  p = (struct nodo *) malloc(sizeof(struct nodo));
  p->inf = val;            /* inserimento di val in elemento */
  p->alb_sin = NULL;       /* marca di albero sinistro vuoto */
  p->alb_des = NULL;    /* marca di albero destro vuoto   */
  p->liv = level;
}
else {              /* Ricerca del punto di inserimento */
 if(val > p->inf) {
    /* visita il sottoalbero destro */
  level++;
  p->alb_des = crea_nodo(p->alb_des, val);
 }
  else
   if(val < p->inf) {
      /* visita il sottoalbero sinistro */
    level++;
    p->alb_sin = crea_nodo(p->alb_sin, val);
   }
}
if(level != 0)
 level--;
return(p);                  /* Ritorna il puntatore alla radice */
}
/* Visita l'albero binario in ordine anticipato */
void anticipato(struct nodo *p) /* funzione di stampa che vorrei rendere +
elegante */
{
 int i;
 if(p!=NULL) {
  for(i=0;i<p->liv;i++)
   printf(" ");
  printf("%d\n", p->inf);  /* visita la radice */
  anticipato(p->alb_sin);    /* visita il sottoalbero sinistro */
  anticipato(p->alb_des);    /* visita il sottoalbero destro   */
 }
}

[CUT]
dimenticavo: grazie a tutti!

 int level=0;
Potresti togliere questa variabile globale...
struct nodo *crea_nodo(struct nodo *p, int val) {
        static int level;
 
        if (p == NULL) {
                p = malloc(sizeof(struct nodo)); /* senza cast */
                assert(p);
                p->alb_des = p->alb_sin = NULL;
                p->val = val;
                p->level = level;
                level = 0;
        } else if (val > p->inf) {
                level++;
                p->alb_des = crea_nodo(p->alb_des, val);
        } else if (val < p->inf) {
                level++;
                p->alb_sin = crea_nodo(p->alb_sin, val);
        }
        return p;
}
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
La somma dell'intelligenza sulla terra e` una costante.
La popolazione e` in aumento.

 La popolazione e` in aumento.
secondo me ci si evolve :)))))))

 secondo me ci si evolve :)))))))
sei ottimista
 TEOREMA DI GINSBERG
1. Non puoi vincere.
2. Non puoi pareggiare.
3. Non puoi nemmeno abbandonare.

 3. Non puoi nemmeno abbandonare.
azz, peggio delle leggi di murphy! :)

 
Non č necessario avere 'liv'; quando visiti l'albero per stamparlo con
la funzione ricorsiva opportuna (in pre-o post- visita) tieni un
contatore che determina il 'livello' a cui sei, senza doverlo inserire
nella struttura stessa.
Per info cerca 'Breadth first search' (BFS) e 'Depth first search'
(DFS) in relazione alle strutture dati di tipo 'Tree' (Albero) o
Directed Graph in genere.
Ciao
Claudio


OOOOOOOOOOOOOOOOOOOOOchei
ciao!

 la stampa a video sarà:
Io avrei fatto un'altra soluzione:
struct nodo {
  int inf;
  char liv; /* aggiunta */
  struct nodo *alb_sin;
  struct nodo *alb_des;
};
void stampa (nodo* p, int liv)
{
        int i = 0;
        if (p) {
                for (; i < liv; ++i)
                        putc (' ');
                printf ("%d\n", p->inf);
                stampa (p->alb_sin, liv + 1);
                stampa (p->alb_des, liv + 1);
        }
}
Ovvero: il livello, anzichè sporcarmi la struttura dati, lo uso come 
parametro della funzione. Quando scendo di livello lo passo +1 nella 
chiamata ricorsiva, così incremento la spaziatura davanti ai valori dei 
nodi figli (vabbè, penso ci saresti arrivato anche senza la spiegazione 
:-)). Ciao.
-- 
Andrea Bergia - studente              Linux Registred User #281550
"The one thing we're all waiting for, is peace on Earth and an end to war,
it's a miracle we need, the miracle, the miracle, 
Peace on earth and end to war today,
That time will come one day you'll see when we can all be friends"

 :-)). Ciao.
a dire il vero ci avevo gia pensato ma nn ero + nelle condizioni mentali per
applicare la nuova soluzione!!! so che suona strano al vostro orecchio ma...
son fatto cosě!
txs di tutto!
