purtroppo è un po lunghetto.... non so... vabbene dai ci provo.. basta che non ci sia il mio prof di algo sul forum!!
Allora vi spiego in generale a cosa serve, così ci mettete meno a capire. Questo è il pezzo di un progettino... praticamente devo inserire dei rettangoli di punti con un valore e le coordinate (sono i "fiori") memorizzate nell'albero rb. Ci devo fare delle robe sopra (che faccio con altre funzioni che qui non ci sono) e in più implementare delle funzioni che riescano a gestire un ulteriore punto di vista che è quello dei campi. Se un rettangolo corrisponde ad un prato di fiori, un campo è una componente connessa di uno o più prati. Cioè: un prato da solo è un campo, due prati adiacenti sono due campi, ma se due prati (o più ovviamente) hanno uno o più punti in comune quei due formano un campo unico.
Questo problema l'ho risolto (se andasse!!) con algoritmi union find... ogni prato inserito forma un nuovo campo (campo_make_set), ogni volta che c'è un punto in comune cerco il campo che contiene il prato del fiore vecchio, cerco il campo con il prato nuovo (con la campo_find_set) e li unisco (campo_union).
Funziona ma si blocca se ci sono due campi e ne inserisco un terzo che li unisce, formando un campo di tre prati... si blocca la find!!
Inserisci prende le coordinate del prato e un file con i valori dei fiori, simple_insert è la funzione che inserisce singolarmente ogni fiore (manca il resto della insert per mettere a posto l'albero rb ma c'è e funge)
campi_piano, fiori_piano sono due puntatori globali alle strutture per i fiori e i campi, cont_campi e cont_prati delle var globali intere.
QUESTE SONO LE FUNZIONI E DOPO CI SONO LE STRUTTURE
codice:
void inserisci(int x0, int y0, int x1, int y1, char *nome_file)
{
FILE *input_f;
int num_input, RIGHT_LENGHT, i=0, x=x0, y=y0;
fiore *f;
RIGHT_LENGHT=((x1-x0)+1)*((y1-y0)+1); /*Calcolo la dimensione esatta dell'aray di supporto*/
int dati[RIGHT_LENGHT];
input_f=fopen(nome_file, "r"); /*apro il file in lettura*/
while(fscanf(input_f, "%d", &num_input)==1){ /*ciclo che riempie l'array con i pesi dei fiori*/
if(i<RIGHT_LENGHT){ /*controllo di non uscire dall'array*/
dati[i]=num_input;
++i;
}
}
cont_prati++; /*Inserisco un nuovo prato, quindi incremento il contatore*/
cont_campi++; /*faccio un nuovo campo e incremento, ma la procedura che nete a posto deve decrementare se fonde qualcosa*/
campo_make_set(cont_campi, cont_prati);
for(i=0; i<RIGHT_LENGHT; ++i){
rbinsert(fiori_piano, x, y, dati[i]);
if(x<x1)
x++;
else {
x=x0;
if(y<y1) y++;
}
}
fclose(input_f);
}
codice:
void campo_make_set(int n_campo, int n_prato)
{
campo *c=malloc(sizeof(campo));
prato *p=malloc(sizeof(prato));
c->num=n_campo;
p->num=n_prato;
c->prati=p;
p->next=NULL;
c->next=campi_piano;
campi_piano=c;
}
campo *campo_find_set(int n_prato)
{
campo *c;
prato *p;
for(c=campi_piano; c!=NULL; c=c->next)
for(p=c->prati; p!=NULL; p=p->next)
if(p->num==n_prato)
return c;
}
void campo_union(campo *c, campo *d)
{
prato *p;
if(c->num==d->num || c==NULL || d==NULL)
;
else {
for(p=c->prati; p->next!=NULL; p=p->next)
;
p->next=d->prati;
/*elimina_campo_ptr(d);*//*questa crea problemi che devo mettere a posto*/
}
}
codice:
fiore *simpleinsert(rbtree *tree, key asc, key ord, key peso)
{
fiore *q = malloc(sizeof(fiore));
fiore *r = tree->root;
fiore *s = tree->nil;
campo *c1, *c2;
if(!q) {
fprintf(stderr,"Errore di allocazione C\n");
exit(-4);
}
q->x = asc;
q->y = ord;
q->val = peso;
q->prato = cont_prati;
q->left = q->right = tree->nil;
q->c = red;
while(r != tree->nil) {
s = r;
if(asc==r->x){
if(ord==r->y){
r->val = r->val + peso;
c1=campo_find_set(r->prato);
c2=campo_find_set(cont_prati);
campo_union(c1, c2);
free(q);
return r;
}
r = ord < r->y ? r->left : r->right;
}
else
r = asc < r->x ? r->left : r->right;
}
q->up = s;
if(s == tree->nil)
tree->root = q;
if(asc < s->x || (asc == s->x && ord < s->y))
s->left = q;
else
s->right = q;
return q;
}
codice:
struct fiore {
key x;
key y;
key val;
key prato;
color c;
struct fiore *left, *right, *up;
};
typedef struct fiore fiore;
typedef struct {
fiore *root, *nil;
} rbtree;
struct prato {
key num;
struct prato *next;
};
typedef struct prato prato;
struct campo {
key num;
struct campo *next;
prato *prati;
};