Algoritmi e strutture dati/Progetti/Rettangoli/Stesura I
Versione del 8 mar 2006 alle 13:08 di Yoruno (discussione | contributi) (Riportata alla revisione precedente da Yoruno)
#include <stdio.h>
#include <stdlib.h>
/* definizione dei tipi */
typedef enum{red, black} color;
struct rbapple {
int xx;
int yy;
color co;
char touch;
struct rbapple *left;
struct rbapple *right;
struct rbapple *parent;
}; /* struttura di ogni nodo dell'albero dei punti*/"
typedef struct rbapple rbapple;
struct rbalbero {
rbapple *root;
rbapple *nul;
}; /*struttura contenente i puntatori alla radice e alla sentinella"
dell'albero dei punti*/"
struct rbnode {
color co ;
int a;
int b;
int c;
int d;
char campo;
struct rbnode *sinistra;
struct rbnode *destra;
struct rbnode *genitore;
}; /*struttura di ogni nodo dell'albero dei rettangoli*/"
typedef struct rbnode rbnode;
struct rbtree {
rbnode *root;
rbnode *nil;
}; /*struttura contenente i puntatori alla radice e alla sentinella"
dell'albero dei rettangoli*/"
typedef struct rbalbero rbalbero;
typedef struct rbtree rbtree;
/* variabili globali */"
rbtree *spazio=NULL; /*puntatore all'albero dei rettangoli*/
rbtree *blocco=NULL;/*puntatore all'albero contennte i rettangoli facenti
parte di un blocco*/"
rbalbero *foglio=NULL;/*puntatore all'albero dei punti*/
rbalbero *niubbio=NULL;/*puntatore all'albero contenente i punti che vanno
rimossi*/"
int par1=0,
par2=0,
par3=0,
par4=0, /* variabili di input*/"
perimetro= 0,
max_x=0, /*dimensione massima dell'ascissa del piano*/
max_y=0; /*dimensione massima dell'ordinata del piano*/
char com; /*parametro di scelta*/
/*
prototipi di FUNZIONI E PROCEDURE"
*/
/*
procedure principali
*/
void procedura_perimetro(void);
void procedura_blocco(void);
void rbdelete(rbalbero *tree, rbapple *q);
void scorri_albero_rettangoli (rbtree *perno, rbnode *buster, rbalbero *joshua , rbapple *corda,int x, int y,rbalbero *elimina);
void elimina_interni_foglio(rbalbero *tree, rbapple *q,rbnode *helper, int x, int y ,rbalbero *elimina);
void scorri_albero_punti(rbalbero *sanato, rbapple *helper, rbtree *f, rbnode *element, rbalbero *elimina);
void ruotaadestra(rbalbero *andtrea , rbapple *giovanni);
void inizializzacampo(rbnode *pino, rbnode *peppe);
void fixup(rbalbero *tree, rbapple *x);
void elimina_albero_supporto(rbalbero *sanato, rbapple *helper);
void elimina_puntini(rbalbero *sanato, rbapple *helper, rbalbero *albero_punti);
void inserisci_foglio(rbalbero *carmencita, int yukapan, int turu);
void canc_albero(rbapple *plastica, rbapple *impertinente);
void costruisci_foglio(rbnode *attacca, rbnode *lattina, rbalbero *the);
void inserisci_blocco(rbtree *dd, int c, int z, int vv, int sc);
void creablocco(rbnode *at, rbnode *ds, rbtree *pc, rbtree *os, int bin, int ffe, int cut, int fre);
void ruotaasinistra(rbalbero *pat, rbapple *emilia);
void inserisci_punto (rbalbero *carmen, int lardo, int palino);
void elimina_tutto_l_albero(rbnode *uno, rbnode *due);
void rightrotate(rbtree *ssa , rbnode *eew);
void leftrotate(rbtree *gix, rbnode *giz);
void inserisci_in_albero(rbtree *csi, int x , int y, int z, int u);
void installarettangolo1(rbtree *doo, int you, int foo, int sedd, int degr);
void search_block(rbnode *fab, rbnode *anna, rbtree *lobot, char drea, int cse, int cpi);
/*
funzioni
*/
int perimetroeblocco(rbalbero *foglio, int peri, char p_o_b);
int ilpuntoeinterno(rbnode *p,int x, int y);
rbapple *treesucc(rbalbero *tree, rbapple *q);
rbapple *treemin(rbapple *p, rbalbero *tree);
rbapple *minimo_foglio(rbapple *paolo, rbapple *piero);
rbapple *trova_nodofoglio(rbalbero *eustachio, int adalberto , int paola);
rbapple *crea_apple(rbalbero *lindo, int cccp, int ostro);
rbapple *inserisci_apple(rbalbero *orin, int elio, int samaga);
rbalbero *costruisci_blocco(rbtree *star, rbtree *stor, rbalbero *bull, int e, int f,char g);"
rbalbero *crea_rbalbero(int gino);
rbtree *crea_rbtree(void);
rbtree *crea_spazio(rbtree *der, int ddr, int fviva);
rbnode *cercanodino(rbtree *nonnot, int defr, int wwe, int t342, int dds);
rbnode *assegna_rbnode(rbtree *eew, int, int, int, int);
rbnode *metti_un_elemento(rbtree *lls, int d, int f, int r, int t);
/*
implementazione delle FUNZIONI e PROCEDURE"
*/
rbtree *crea_spazio(rbtree *spazio, int x, int y)
/*
questa procedura controlla che non sia già presente uno spazio e ne crea uno di
dimensioni x y; nel caso in cui ci sia già uno spazio, lo cancella e, solo dopo
crea quello richiesto.
Nel primo caso il tempo è O(1), nel secondo dipende dalla funzione che elimina l'
albero precedente.
*/
{
max_x=x;
max_y=y;
if(!spazio)
{
if (!(spazio = crea_rbtree()))
exit(-2);
}
else
{
elimina_tutto_l_albero(spazio->root, spazio->nil);
free(spazio);
if (!(spazio = crea_rbtree()))
exit(-2);
}
return spazio;
}
void procedura_blocco(void)
/*
questa procedura racchiude tutte le operazioni da compiere per calcolare e
stampare a video la descrizione del contorno del blocco
*/
{
if(foglio != NULL)
{"
canc_albero(foglio->root, foglio->nul);"
free(foglio);"
foglio = NULL;"
}"
if(!(par1 >= 0 && par2 >= 0 && par1 <=max_x && par2<=max_y))"
{"
printf(""b -1"");"
}"
else"
{"
foglio = costruisci_blocco(spazio, blocco, foglio, par1, par2,'b');"
if(foglio != NULL)"
{"
if (!(niubbio=crea_rbalbero(1)))"
exit(-2);"
scorri_albero_punti(foglio, foglio->root, spazio, spazio->root, niubbio);"
elimina_puntini(niubbio, niubbio->root,foglio);"
elimina_albero_supporto(niubbio, niubbio->root);"
free(niubbio->nul);"
free(niubbio);"
perimetro = perimetroeblocco(foglio, perimetro, 'b');"
}"
}"
}
void elimina_tutto_l_albero(rbnode *ghigo, rbnode *nil)
/*
questa procedura elimina tutto l'albero passatole in input.
tempo @(n), essendo n i nodi dell'albero da cancellare.
*/
{
if (ghigo->destra!=nil)"
elimina_tutto_l_albero(ghigo->destra,nil);"
if (ghigo->sinistra!=nil)"
elimina_tutto_l_albero(ghigo->sinistra, nil);"
ghigo->genitore = nil;"
free (ghigo);"
}
rbtree *crea_rbtree(void)
/*
questa funzione crea e inizializza la radice e la sentinella di un albero e ne
restituisce il puntatore.
tempo @(1)
*/
{
rbtree *tree = malloc(sizeof(rbtree));
if(!tree)
return NULL;"
if(!(tree->root = malloc(sizeof(rbnode))))
return NULL;"
tree->nil = tree->root;
tree->nil->sinistra = tree->nil->destra = tree->nil->genitore = tree->nil;
tree->nil->co = black;
return tree;
}
void elimina_puntini(rbalbero *sanato, rbapple *helper, rbalbero *albero_punti)
/*
questa procedura elimina i punti interni del blocco, che abbiamo precedentemente
inserito in un albero.
tempo O(n), essendo n i nodi da cancellare. (va anlizzata a parte la procedura
che effettivamente elimina i nodi)
*/
{"
rbapple *kiss;
if (helper->left!=sanato->nul)
elimina_puntini(sanato, helper->left, albero_punti);"
kiss = trova_nodofoglio(albero_punti, helper->xx, helper->yy);"
if (kiss)"
rbdelete(albero_punti, kiss);"
if (helper->right!=sanato->nul)
elimina_puntini(sanato, helper->right,albero_punti);"
}
void elimina_albero_supporto(rbalbero *sanato, rbapple *helper)
/*
questa procedura distrugge completamente un albero di tipo rbalbero.
tempo @(n), essendo n i nodi dell'albero.
*/
{
rbapple *kiss;
if (helper->left!=sanato->nul)
elimina_albero_supporto(sanato, helper->left);"
if (helper->right!=sanato->nul)
elimina_albero_supporto(sanato, helper->right);"
free(helper);"
}
void installarettangolo1(rbtree *spazio, int a, int b, int c, int d)
/*
questa procedura inserisce un rettangolo nell'albero in input.
tempo O(log n) dovuto alla ricerca nell'albero e all'insrimento
*/
{
rbnode *maya =NULL;
if((a < c)&&(a >=0)&&(b < d)&&(b >= 0)&&(c <= max_x)&&(d <=max_y)&&(c >=0)&&(d>=0))
{
maya = cercanodino(spazio, a, b, c, d);
if(maya == NULL)
{
inserisci_in_albero(spazio, a, b, c, d);
}
}
}
void inserisci_in_albero(rbtree* spazio, int a, int b, int c, int d)
/*
questa procedura inserisce un nodo in un'albero rb e ne ripristina le proprietà.
tempo @(log n) dovuto alla ricerca dello spazio nell'albero
*/
{
rbnode *fatur = metti_un_elemento(spazio, a, b, c, d);"
rbnode *iron = NULL;
if (fatur != NULL){
while(fatur != spazio->root && fatur->genitore->c == red)
{
if(fatur->genitore == fatur->genitore->genitore->sinistra)
{
iron = fatur->genitore->genitore->destra;
if(iron->co == red)
{
fatur->genitore->co = black;
iron->co = black;
fatur->genitore->genitore->co = red;
fatur= fatur->genitore->genitore;
}
else
{
if(fatur == fatur->genitore->destra)
{
fatur = fatur->genitore;"
leftrotate(spazio, fatur);"
}
fatur->genitore->co = black;
fatur->genitore->genitore->co = red;
rightrotate(spazio, fatur->genitore->genitore);
}
}
else
{
iron = fatur->genitore->genitore->sinistra;
if(iron->co == red)
{
fatur->genitore->co = black;
iron->co = black;
fatur->genitore->genitore->co = red;
fatur = fatur->genitore->genitore;
}
else
{
if(fatur == fatur->genitore->sinistra)
{
fatur = fatur->genitore;"
rightrotate(spazio, fatur);"
}
fatur->genitore->co = black;
fatur->genitore->genitore->co = red;
leftrotate(spazio, fatur->genitore->genitore);
}
}
}
spazio->root->co = black;}
}
rbnode *metti_un_elemento(rbtree *spazio, int a, int b, int c, int d)
/*
questa procedura inserisce un elemento in un albero rb, come se si trattasse di
un albero binario di ricerca.
tempo @(log n) limitato superiormente dal fatto che l'albero è bilanciato, in
quanto rb.
*/
{
char pink;
rbnode *bruce = spazio->root;
rbnode *purple = spazio->nil;
while(bruce != spazio->nil)
{
purple = bruce;
if(a == purple->a && b == purple->b && c == purple->c && d == purple->d)
return NULL;
else
if(a >= purple->a && b >= purple->b && c <= purple->c && d <= purple->d)
return NULL;
else
if (a < purple->a)
pink = 'n';
else
if(a > purple->a)
pink = 'y';
else
if(a == purple->a && b < purple->b)
pink = 'n';
else
if(a == purple->a && b > purple->b)
pink = 'y';
else
if(a == purple->a && b == purple->b && c < purple->c)
pink = 'n';
else
if(a == purple->a && b == purple->b && c > purple->c)
pink = 'y';
else
if(a == purple->a && b == purple->b && c == purple->c && d <= purple->d)
pink= 'n';
else
pink = 'y';
if (pink == 'n')
bruce =purple->sinistra;
else
bruce=purple->destra;
}
bruce = assegna_rbnode(spazio, a, b, c, d);
bruce->genitore = purple;
if(purple == spazio->nil)
spazio->root = bruce;
else
if(a < purple->a)
purple->sinistra = bruce;
else
if(a > purple->a)
purple->destra = bruce;
else
if(a == purple->a && b < purple->b)
purple->sinistra = bruce;
else
if(a == purple->a && b > purple->b)
purple->destra = bruce;
else
if(a == purple->a && b == purple->b && c < purple->c)
purple->sinistra = bruce;
else
if(a == purple->a && b == purple->b && c > purple->c)
purple->destra = bruce;
else
if(a == purple->a && b == purple->b && c == purple->c && d <= purple->d)
purple->sinistra = bruce;
else
purple->destra = bruce;
return bruce;
}
rbnode *assegna_rbnode(rbtree *spazio, int a, int b, int c, int d)
/*
questa procedura alloca spazio per un nodo di tipo rbtree. In caso no riuscisse
ad allocare spazio in memoria esce dal programma e restituisce un codice di
errore.
tempo @(1)
*/
{
rbnode *figaro = NULL;
if (!(figaro = malloc(sizeof(rbnode))))
exit(-2);
figaro->campo='n';
figaro->co=red;
figaro->a=a;
figaro->b=b;
figaro->c=c;
figaro->d=d;
figaro->destra = spazio->nil;
figaro->sinistra = spazio->nil;
figaro->genitore=spazio->nil;
return figaro;
}
void leftrotate(rbtree* spazio, rbnode* indotto)
/*
questa procedura produce una rotazione necessaria al ripristino delle proprietà
dell'alberorb.
tempo @(1)
*/
{
rbnode *y = indotto->destra;
indotto->destra = y->sinistra;
if (y->sinistra != spazio->nil)
y->sinistra->genitore = indotto;"
y->genitore = indotto->genitore;"
if (indotto->genitore==spazio->nil)
spazio->root = y;"
else
if (indotto==indotto->genitore->sinistra)"
y->genitore->sinistra = y;"
else"
y->genitore->destra = y;"
y->sinistra = indotto;
indotto->genitore = y;
}
void rightrotate(rbtree* perno, rbnode* ghigo)
/*
questa procedura produce una rotazione necessaria al ripristino delle proprietà
dell'alberorb.
tempo @(1)
*/
{
rbnode *mm = ghigo->sinistra;
ghigo->sinistra = mm->destra;
if (mm->destra!=perno->nil)
mm->destra->genitore = ghigo;"
mm->genitore = ghigo->genitore;
if (ghigo->genitore==perno->nil)
perno->root = mm;"
else
if (ghigo==ghigo->genitore->destra)"
mm->genitore->destra = mm;"
else"
mm->genitore->sinistra = mm;"
mm->destra = ghigo;
ghigo->genitore = mm;
}
rbnode *cercanodino(rbtree *spazio, int a, int b, int c, int d)
/*
questa funzione cerca un nodo nell'albero e, in caso lo trovi, ne restituisce il
puntatore; in caso contrario restituisce NULL.
tempo @(log n)
*/
{
rbnode *buffer = NULL;
char macaja;
buffer = spazio->root;
while(buffer != spazio->nil && (buffer->a != a || buffer->b != b || buffer->c != c || buffer->d != d))
{
if(a < buffer->a)
macaja = 'y';
else
if(a > buffer->a)
macaja = 'n';
else
if(a == buffer->a && b < buffer->b)
macaja = 'y' ;
else
if(a == buffer->a && b > buffer->b)
macaja = 'n';
else
if(a == buffer->a && b == buffer->b && c < buffer->c)
macaja = 'y';
else
if(a == buffer->a && b == buffer->b && c > buffer->c)
macaja = 'n';
else
if(a == buffer->a && b == buffer->b && c == buffer->c && d <= buffer->d)
macaja = 'y';
else
macaja = 'n';
if (macaja =='y')
buffer = buffer->sinistra ;
else
buffer=buffer->destra;
}
if(buffer == spazio->nil)
return NULL;
else
return buffer;
}
rbalbero *crea_rbalbero(int a)
/*
questa procedura alloca spazio e inizializza la radice e la sentnella di un
albero di tipo rbalbero.
tempo @(1)
*/
{
rbalbero *tree = malloc(sizeof(rbalbero));
if(!tree)
return NULL;"
if(!(tree->root = malloc(sizeof(rbapple))))
return NULL;"
tree->nul = tree->root;
tree->nul->left = tree->nul->right = tree->nul->parent = tree->nul;
tree->nul->co = black;
if (a==1)"
{"
if (!(tree->nul=malloc(sizeof(rbapple))))"
exit(-2);"
tree->root->left = tree->root->right = tree->root->parent = tree->nul;"
}"
return tree;
}
rbapple *trova_nodofoglio(rbalbero *perno, int puntox, int puntoy)
/*
questa funzione si occupa di trovare un nodo, se esistente, e di restituirne il
puntatore. Nel caso in cui il nodo non esista restituisce NULL.
tempo @(log n)
*/
{
rbapple *giusto=perno->root;
while (giusto!=perno->nul && (giusto->xx!=puntox || giusto->yy!=puntoy))
{
if (puntox<giusto->xx)
giusto = giusto->left;
else
if (puntox>giusto->xx)
giusto = giusto->right;
else
if (puntox == giusto->xx && puntoy < giusto->yy)
giusto = giusto->left;
else
giusto = giusto->right;
}
if (giusto==perno->nul)
return NULL;"
else
return giusto;"
}
void inserisci_punto(rbalbero* perno, int puntox, int puntoy)
/*
questa procedura inserisce un nodo in un'albero rb e ne ripristina le proprietà.
tempo @(log n) dovuto alla ricerca dello spazio nell'albero
*/
{
rbapple *birba = inserisci_apple(perno, puntox, puntoy);
rbapple *cesco;
if (birba!=NULL){
while (birba!=perno->root && birba->parent->co==red)
{
if (birba->parent==birba->parent->parent->left)
{
cesco = birba->parent->parent->right;
if (cesco->co==red)
{
birba->parent->co = black;"
cesco->co = black;"
birba->parent->parent->co = red;"
birba = birba->parent->parent;"
}
else
{
if (birba==birba->parent->right)
{"
birba = birba->parent;"
ruotaasinistra(perno, birba);"
}"
birba->parent->co = black;
birba->parent->parent->co = red;
ruotaadestra(perno, birba->parent->parent);
}
}
else
{
cesco = birba->parent->parent->left;
if (cesco->co==red)
{
birba->parent->co = black;"
cesco->co = black;"
birba->parent->parent->co = red;"
birba = birba->parent->parent;"
}
Per quanto riguarda la discussione del progetto fai riferimento a questo file, che contiene anche il file C del progetto.
