/* --------------------------------------------------------------
a l b i n . c
Il programma gestisce in maniera completa -inserzione, cancel-
lazione, visita- un albero binario non del tipo AVL. E' stato
scritto con la tecnica BKF (=Bast Ke Funz). Pertanto potrebbe es-
sere migliorabile. Segnatamente la cancellazione. Oltre alle o-
perazioni citate, e' prevista la stampa. La cosa piu' sensata
sarebbe stata quella di scrivere un applet Java. Poiche' non me
la sento di affrontare lo studio di quest'ultimo ma conosco La-
TeX, ho sfruttato le sue limitate capacita' grafiche. Sufficien-
ti tuttavia, in quanto si tratta di tracciare dei box e delle li-
nee. L'operazione di stampa crea un file temporaneo. Da un'altra
finestra terminale va lanciato uno script che elabora il contenu-
to trasformandolo, tramite un programma C, in statement LaTeX (e'
necessaria la presenza di questo pacchetto). Da LaTeX si ot-
tiene un file .pdf. Ogni volta che la funzione stampa viene invo-
cata, c'e' la sovrascrittura del file temporaneo. La stampa quin-
di e' asincrona.
Ho messo la massima cura, ma non posso garantire l'assenza di er-
rori. Pertanto il tutto va usato cosi' com'e' e a proprio rischio
e pericolo.
Per la compilazione usare:
gcc -ansi -DSTAMPA -O -pedantic -s -W -Wall -o albero albero.c
Lo script per la generazione dell'albero grafico e quanto connes-
so non sono online. Basta richiederli.
-------------------------------------------------------------- */
#include <setjmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#define False 0
#define True !False
#define albero main
#ifdef STAMPA
int altbox = 10, altfr = 5, basebox = 10;
int curv = 2, trabox = 5;
const int box = 5, frdx = 11, frsx = 10;
#endif
jmp_buf restore;
struct foglia
{
struct foglia *sx;
int valore;
struct foglia *retro;
struct foglia *dx;
};
typedef struct foglia* nodo;
#ifdef STAMPA
void arco (nodo n, char *fn)
{
char *riga;
FILE *f;
int a[4], da[4], dim;
int isempty (nodo);
nodo retro;
void vertici (FILE *, int, char *, int);
dim = 40;
riga = (char *) malloc ((unsigned int) dim);
if (isempty (n) == False)
{
arco (n->sx, fn);
if (isempty (n->retro) == False)
{
f = fopen (fn, "r+");
retro = n->retro;
vertici (f, retro->valore, riga, dim);
(void) sscanf (riga, "%*i %i %i %i %i",
&da[0], &da[1], &da[2], &da[3]);
vertici (f, n->valore, riga, dim);
(void) sscanf (riga, "%*i %i %i %i %i",
&a[0], &a[1], &a[2], &a[3]);
a[2] /= 2;
fseek (f, (long) 0, SEEK_END);
if (retro->sx == n)
(void) fprintf (f, "%i %i %i %i %i %i\n", frsx,
a[0] + a[2], a[1] + a[3], da[0] - (a[0] + a[2]),
altfr, curv);
else
(void) fprintf (f, "%i %i %i %i %i %i\n", frdx,
da[0] + da[2], da[1], a[0] + a[2] - (da[0] + da[2]),
altfr, curv);
fclose (f);
}
arco (n->dx, fn);
}
free ((void *) riga);
}
#endif
int between (int inf, int valore, int sup)
{
if (valore < inf)
return (inf);
if (valore > sup)
return (sup);
return (valore);
}
nodo cancella (nodo n, int valore)
{
unsigned int destra, sinistra;
int isempty (nodo);
nodo local, pred, retro, succ;
nodo predecessore (nodo, int), ricerca (nodo, int);
local = ricerca (n, valore);
sinistra = isempty (local->sx) == True;
destra = isempty (local->dx) == True;
/* foglia */
if (sinistra && destra)
{
if (isempty (local->retro) == True)
return ((nodo) NULL);
retro = local->retro;
if (retro->sx == local)
retro->sx = (nodo) NULL;
else
retro->dx = (nodo) NULL;
return (n);
}
/* 1 sottoalbero */
if (sinistra ^ destra)
{
succ = sinistra ? local->dx : local->sx;
retro = local->retro;
if (isempty (retro) == True)
{
succ->retro = (nodo) NULL;
return (succ);
}
if (retro->sx == local)
retro->sx = succ;
else
retro->dx = succ;
return (n);
}
/* 2 sottoalberi */
pred = predecessore (n, valore);
if (local->sx == pred)
local->sx = (nodo) NULL;
local->valore = pred->valore;
retro = pred->retro;
if (retro->sx == pred)
retro->sx = (nodo) NULL;
else
if (retro->dx == pred)
retro->dx = (nodo) NULL;
return (n);
}
#ifdef STAMPA
void disegna (nodo n, int livello, FILE *f, int maxord, int *asc)
{
int isempty (nodo);
if (isempty (n) == False)
{
disegna (n->sx, livello + 1, f, maxord, asc);
(void) fprintf (f, "%i %i %i %i %i %i :%i\n",
box, *asc * (basebox + trabox),
(maxord - 1 - livello) * altbox,
basebox, altbox, curv, n->valore);
*asc += 1;
disegna (n->dx, livello + 1, f, maxord, asc);
}
}
#endif
void insert (nodo *n, int valore, nodo provenienza)
{
int between (int, int, int), isempty (nodo);
if (isempty (*n) == True)
{
/* nuovo nodo */
*n = (nodo) malloc (sizeof (struct foglia));
(*n)->sx = (nodo) NULL;
(*n)->valore = valore;
(*n)->retro = provenienza;
(*n)->dx = (nodo) NULL;
}
else
{
switch (between (-1, valore - (*n)->valore, +1))
{
case -1: /* piu' piccolo - inserisci a sinistra */
insert (&((*n)->sx), valore, *n);
break;
case 0: /* duplicato */
break;
case +1: /* piu' grande - inserisci a destra */
insert (&((*n)->dx), valore, *n);
break;
}
}
}
int isempty (nodo n)
{
if (n == (nodo) NULL)
return (True);
else
return (False);
}
#ifdef STAMPA
void level (nodo n, int livello, int *maxord)
{
int isempty (nodo);
if (isempty (n) == False)
{
if (livello > *maxord)
*maxord = livello;
level (n->sx, livello + 1, maxord);
level (n->dx, livello + 1, maxord);
}
}
#endif
nodo Massimo (nodo n)
{
int isempty (nodo);
if (isempty (n) == True)
longjmp (restore, 0);
if (isempty (n->dx) == False)
return (Massimo (n->dx));
return (n);
}
#ifdef STAMPA
void maxbox (nodo n, int *maxasc)
{
int isempty (nodo);
if (isempty (n) == False)
{
maxbox (n->sx, maxasc);
*maxasc += 1;
maxbox (n->dx, maxasc);
}
}
#endif
nodo minimo (nodo n)
{
int isempty (nodo);
if (isempty (n) == True)
longjmp (restore, 0);
if (isempty (n->sx) == False)
return (minimo (n->sx));
return (n);
}
nodo predecessore (nodo n, int valore)
{
extern int isempty (nodo);
nodo local, tmp;
extern nodo Massimo (nodo), minimo (nodo), ricerca (nodo, int);
local = ricerca (n, valore);
if (isempty (local->sx) == False)
return (Massimo (local->sx));
if (local == minimo (n))
longjmp (restore, 0);
tmp = local->retro;
while (isempty (tmp) == False && local == tmp->sx)
{
local = tmp;
tmp = local->retro;
}
return (tmp);
}
nodo ricerca (nodo n, int valore)
{
extern int between (int, int, int), isempty (nodo);
nodo tmp;
if (isempty (n) == True)
longjmp (restore, 0);
tmp = n;
switch (between (-1, valore - n->valore, +1))
{
case -1: /* piu' piccolo - cerca a sinistra */
tmp = (ricerca (n->sx, valore));
break;
case 0: /* trovato */
break;
case +1: /* piu' grande - cerca a destra */
tmp = (ricerca (n->dx, valore));
break;
}
return (tmp);
}
#ifdef STAMPA
void stampa (nodo n)
{
char fn[L_tmpnam];
FILE *f;
int maxasc, maxord;
void arco (nodo, char *), maxbox (nodo, int *),
disegna (nodo, int, FILE *, int, int *),
level (nodo, int, int *);
(void) sprintf (fn, "%s", __FILE__);
(void) strcpy (strrchr (fn, '.'), ".txt");
remove (fn);
if (isempty (n) == True)
longjmp (restore, 0);
if ((f = fopen (fn, "w")) == NULL)
{
(void) fprintf (stderr, "errore apertura %s\n", fn);
exit (EXIT_FAILURE);
}
maxasc = maxord = 0;
level (n, 1, &maxord);
maxbox (n, &maxasc);
(void) fprintf (f, "%i %i\n", maxasc * (basebox + trabox) - trabox,
maxord * altbox);
(void) fprintf (f, "albero\n");
(void) fprintf (f, "Diagramma albero\n");
maxasc = 0;
disegna (n, 0, f, maxord, &maxasc);
fclose (f);
arco (n, fn);
}
void vertici (FILE *f, int kiave, char *ombra, int dim)
{
char *p, *riga;
int ind;
riga = (char *) malloc ((unsigned int) dim);
fseek (f, (long) 0, SEEK_SET);
(void) fgets (riga, dim, f);
while (! feof (f))
{
riga[strlen (riga) - 1] = '\0';
(void) strcpy (ombra, riga);
p = strtok (riga, " ");
if (atoi (p) == box)
{
for (ind = 0; ind < 6; ind++)
p = strtok ((char *) NULL, " ");
if (atoi (++p) == kiave)
break;
}
(void) fgets (riga, dim, f);
}
free ((void *) riga);
}
#endif
void visita (nodo n, int offset)
{
int incr, ind, isempty (nodo);
incr = 2;
if (isempty (n) == False)
{
visita (n->sx, offset + incr);
for (ind = 0; ind < offset; ind++)
(void) printf (" ");
(void) printf ("%*i\n", incr, n->valore);
visita (n->dx, offset + incr);
}
}
int albero (void) /* main program */
{
char *menu, *oper[] =
{
"[c]ancella ", "[f]ine ", "[i]nserisci ", "[v]isita "
#ifdef STAMPA
, "[s]tampa "
#endif
};
int fine, ind, jump, nop, op, valore;
nodo n, cancella (nodo, int);
void insert (nodo *, int, nodo);
#ifdef STAMPA
void stampa (nodo);
#endif
void visita (nodo, int);
valore = 0;
nop = sizeof oper / sizeof oper[0];
for (ind = 0; ind < nop; ind++)
valore += strlen (oper[ind]);
menu = (char *) malloc (valore);
bzero (menu, valore);
for (ind = 0; ind < nop; ind++)
(void) strcat (menu, oper[ind]);
fine = True;
n = (nodo) NULL; /* inizializzazione albero */
jump = setjmp (restore); /* punto di ritorno */
if (jump)
(void) getchar ();
do
{
(void) printf ("%s", menu); (void) printf ("> ");
op = fgetc (stdin);
switch (op)
{
default: /* errore */
(void) printf ("\noperazioni ammesse: ");
(void) printf ("%s\n\n", menu);
break;
case 'c': /* cancellazione */
(void) fscanf (stdin, "%i", &valore);
n = cancella (n, valore);
break;
case 'f': /* fine */
fine = False;
break;
case 'i': /* inserzione */
(void) fscanf (stdin, "%i", &valore);
insert (&n, valore, (nodo) NULL);
break;
#ifdef STAMPA
case 's': /* stampa */
stampa (n);
break;
#endif
case 'v': /* visita */
visita (n, 0);
break;
}
(void) getchar ();
}
while (fine == True);
free ((void *) menu);
exit (EXIT_SUCCESS);
}
