number15
17-02-2011, 14:21
Ciao a tutti, son alle prese con un progetto per l'università, un clone del Bunga Bunga dell'università di Insubria postato qua (http://www.hwupgrade.it/forum/showthread.php?t=2311965)
Il mio è questo (http://www.mediafire.com/?84dhpmadzddkaj3).
Come struttura sto usando un albero RB.
Posto parte del main:
int main(void){
char azione[10]; /*inizio stringa, mi indica l'azione da fare- vedere come migliorarlo */
bigInt hash_name = 0; /* per salvare l'hash del nome */
/* per salvare i dati passati quando azione = IN */
char name[MAXWORD];
char sex;
int money, age, height, weight;
float hair, build;
char days[MAXWORD];
/* inizializzo albero*/
rbtree *invitati = createrbtree();
/* Puntatori a struttura nodo */
Invitato *p;
/* Lettura input ed esecuzione comandi */
do {
scanf("%s", azione);
if (strcmp(azione, "in") == 0) { /* azione input inserimento */
scanf("%s %c %d %d %d %d %f %f %s", name, &sex, &money, &age, &height, &weight,
&hair, &build, days);
/* calcola key intera per il nome */
hash_name = hash(name);
if (!search(invitati, hash_name)) { /* se non esiste un invitato di quel nome*/
rbinsert(invitati, hash_name, name, sex, money, age, height, weight, hair, build, days);
} /* chiusura if search*/
else { /* aggiorno invitato*/
p = search(invitati, hash_name);
update_invitato(p, hash_name, name, sex, money, age, height, weight, hair, build, days);
}
} /* chiusura if in */
else if (strcmp(azione, "stampa") == 0) { /* azione input stampa invitato */
scanf("%s", name);
hash_name = hash(name);
p = search(invitati, hash_name); /* cerco invitato*/
if (p)
stampa_invitato(p);
else
printf("Non ci sono invitati di nome %s\n", name);
}
else if (strcmp(azione, "out") == 0) {/* azione input estrometti */
scanf("%s", name);
hash_name = hash(name);
p = search(invitati, hash_name); /* cerco invitato*/
rbdelete(invitati, p);
}
/* fa casino, stampa quello cancellato e non un altro... NON ORDINA*/
else if (strcmp(azione, "invitati") == 0) {/* azione input invitati */
p = treemin(invitati);
printf("(\n");
while(p) {
printf("%s\n", p->i);
p = treesucc(invitati, p);
} /* end of while */
printf(")\n");
}
Il codice dell'algorimto rb è questo:
/* CREATE RB TREE */
rbtree *createrbtree(void) {
rbtree *p = malloc(sizeof(rbtree));
if(!p) {
fprintf(stderr,"Errore di allocazione A\n");
exit(-1);
}
p->root = malloc(sizeof(Invitato));
if(!p->root) {
fprintf(stderr,"Errore di allocazione B\n");
exit(-2);
}
p->nil = p->root;
p->nil->sx = p->nil->dx = p->nil->up = p->nil;
p->nil->c = black;
return p;
}
/* SORT */
void inord(Invitato *p, Invitato *nil, void (*op)(Invitato *))
{
if(p != nil) {
inord(p->sx,nil,op);
(*op)(p);
inord(p->dx,nil,op);
}
}
/* SORT BY KEY */
void inorder(rbtree *p, void (*op)(Invitato *))
{
inord(p->root, p->nil, op);
}
/* SEARCH */
Invitato *search(rbtree *r, key k)
{
Invitato *p = r->root;
while(p != r->nil && k != p->v)
p = k < p->v ? p->sx : p->dx;
return p == r->nil ? NULL : p;
}
Invitato *rbtmin(Invitato *p, Invitato *nil)
{
for(;p->sx != nil;p = p->sx);
return p;
}
Invitato *rbtmax(Invitato *p, Invitato *nil)
{
for(;p->dx != nil;p = p->dx);
return p;
}
/* MIN */
Invitato *treemin(rbtree *r)
{
return rbtmin(r->root,r->nil);
}
/* MAX */
Invitato *treemax(rbtree *r)
{
return rbtmax(r->root,r->nil);
}
/* NODO SUCESSIVO */
Invitato *treesucc(rbtree *r, Invitato *q)
{
Invitato *qq;
if(q->dx != r->nil)
return rbtmin(q->dx,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->dx) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
/* NODO PRECEDENTE */
Invitato *treepred(rbtree *r, Invitato *q)
{
Invitato *qq;
if(q->sx != r->nil)
return rbtmax(q->sx,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->sx) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
void sxrotate(rbtree *r, Invitato *x)
{
Invitato *y = x->dx;
x->dx = y->sx;
if(y->sx != r->nil)
y->sx->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->sx)
y->up->sx = y;
else
y->up->dx = y;
y->sx = x;
x->up = y;
}
void dxrotate(rbtree *r, Invitato *x)
{
Invitato *y = x->sx;
x->sx = y->dx;
if(y->dx != r->nil)
y->dx->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->dx)
y->up->dx = y;
else
y->up->sx = y;
y->dx = x;
x->up = y;
}
Invitato *simpleinsert(rbtree *tree, key hash_name, nome name, sesso sex,
denaro money, eta age, altezza height, peso weight,
capelli hair, costituzione build, presenza days)
{
Invitato *q = malloc(sizeof(Invitato));
Invitato *r = tree->root;
Invitato *s = tree->nil;
q->i = malloc((strlen(name)+1)*sizeof(char));
// q->s = malloc((strlen(sesso)+1)*sizeof(enum));
// q->d = malloc((strlen(money)+1)*sizeof(char));
// q->e = malloc((strlen(age)+1)*sizeof(char));
// q->h = malloc((strlen(height)+1)*sizeof(char));
// q->w = malloc((strlen(weigth)+1)*sizeof(char));
// q->cap = malloc((strlen(hair)+1)*sizeof(char));
// q->b = malloc((strlen(build)+1)*sizeof(char));
q->p = malloc((strlen(days)+1)*sizeof(char));
if(!q) {
fprintf(stderr,"Errore di allocazione C\n");
exit(-4);
}
q->v = hash_name;
strcpy(q->i, name);
q->s = sex;
q->d = money;
q->e = age;
q->h = height;
q->w = weight;
q->cap = hair;
q->b = build;
strcpy(q->p, days);
q->sx = q->dx = tree->nil;
q->c = red;
while(r != tree->nil) {
s = r;
r = hash_name < r->v ? r->sx : r->dx;
}
q->up = s;
if(s == tree->nil)
return tree->root = q;
if(hash_name < s->v)
s->sx = q;
else
s->dx = q;
return q;
}
void rbinsert(rbtree *tree, key hash_name, nome name, sesso sex, denaro money,
eta age, altezza height, peso weight, capelli hair,
costituzione build, presenza days)
{
Invitato *x = simpleinsert(tree, hash_name, name, sex, money,
age, height, weight, hair, build, days);
Invitato *y;
while(x != tree->root && x->up->c == red) {
if(x->up == x->up->up->sx) { /* caso L */
y = x->up->up->dx;
if(y->c == red) {
x->up->c = black; /* caso 1L */
y->c = black; /* caso 1L */
x->up->up->c = red; /* caso 1L */
x = x->up->up; /* caso 1L */
} else {
if(x == x->up->dx) /* caso 2L */
sxrotate(tree,x = x->up); /* caso 2L */
x->up->c = black; /* caso 3L */
x->up->up->c = red; /* caso 3L */
dxrotate(tree,x->up->up); /* caso 3L */
}
} else { /* caso R */
y = x->up->up->sx;
if(y->c == red) {
x->up->c = black; /* caso 1R */
y->c = black; /* caso 1R */
x->up->up->c = red; /* caso 1R */
x = x->up->up; /* caso 1R */
} else {
if(x == x->up->sx) /* caso 2R */
dxrotate(tree,x = x->up); /* caso 2R */
x->up->c = black; /* caso 3R */
x->up->up->c = red; /* caso 3R */
sxrotate(tree,x->up->up); /* caso 3R */
}
}
}
tree->root->c = black;
}
/* FIXUP RBTREE */
void fixup(rbtree *tree, Invitato *x)
{
Invitato *w;
while(x != tree->root && x->c == black) {
if(x == x->up->sx) { /* caso L */
if((w = x->up->dx)->c == red) {
w->c = black; /* caso 1L */
x->up->c = red; /* caso 1L */
sxrotate(tree,x->up); /* caso 1L */
w = x->up->dx; /* caso 1L */
}
if(w->sx->c == black && w->dx->c == black) {
w->c = red; /* caso 2L */
x = x->up; /* caso 2L */
} else {
if(w->dx->c == black) {
w->sx->c = black; /* caso 3L */
w->c = red; /* caso 3L */
dxrotate(tree,w); /* caso 3L */
w = x->up->dx; /* caso 3L */
}
w->c = x->up->c; /* caso 4L */
x->up->c = black; /* caso 4L */
w->dx->c = black; /* caso 4L */
sxrotate(tree,x->up); /* caso 4L */
x = tree->root; /* caso 4L */
}
} else { /* caso R */
if((w = x->up->sx)->c == red) {
w->c = black; /* caso 1R */
x->up->c = red; /* caso 1R */
dxrotate(tree,x->up); /* caso 1R */
w = x->up->sx; /* caso 1R */
}
if(w->dx->c == black && w->sx->c == black) {
w->c = red; /* caso 2R */
x = x->up; /* caso 2R */
} else {
if(w->sx->c == black) {
w->dx->c = black; /* caso 3R */
w->c = red; /* caso 3R */
sxrotate(tree,w); /* caso 3R */
w = x->up->sx; /* caso 3R */
}
w->c = x->up->c; /* caso 4R */
x->up->c = black; /* caso 4R */
w->sx->c = black; /* caso 4R */
dxrotate(tree,x->up); /* caso 4R */
x = tree->root; /* caso 4R */
}
}
}
x->c = black;
}
void rbdelete(rbtree *tree, Invitato *q)
{
Invitato *r, *s;
if(q->sx == tree->nil || q->dx == tree->nil)
r = q;
else
r = treesucc(tree,q);
s = r->sx != tree->nil ? r->sx : r->dx;
s->up = r->up;
if(r->up == tree->nil)
tree->root = s;
else
if(r == r->up->sx)
r->up->sx = s;
else
r->up->dx = s;
if(r != q)
q->v = r->v;
if(r->c == black)
fixup(tree, s);
free(r);
}
L'inserimento, aggiornamento, cancellazione e stampa funzionano.
mi fa casino invece il caso 'invitati'.
Dovrei stamparli in ordine alfabeti.
A volte va, a volte no e inoltre se elimino un invitato (out invitato), capita che facendo 'invitati' me lo mostri ancora, mentre non ne compare più un altro.
La conferma dell'eliminazione però ce l'ho in quanto facendo 'stampa invitato' mi dice che non esiste.
Ho anche un problema con la malloc che ho commentato.
Poi altri dubbi li posto più avanti.
Se poteste aiutarmi ve ne sarei molto grato.
Il mio è questo (http://www.mediafire.com/?84dhpmadzddkaj3).
Come struttura sto usando un albero RB.
Posto parte del main:
int main(void){
char azione[10]; /*inizio stringa, mi indica l'azione da fare- vedere come migliorarlo */
bigInt hash_name = 0; /* per salvare l'hash del nome */
/* per salvare i dati passati quando azione = IN */
char name[MAXWORD];
char sex;
int money, age, height, weight;
float hair, build;
char days[MAXWORD];
/* inizializzo albero*/
rbtree *invitati = createrbtree();
/* Puntatori a struttura nodo */
Invitato *p;
/* Lettura input ed esecuzione comandi */
do {
scanf("%s", azione);
if (strcmp(azione, "in") == 0) { /* azione input inserimento */
scanf("%s %c %d %d %d %d %f %f %s", name, &sex, &money, &age, &height, &weight,
&hair, &build, days);
/* calcola key intera per il nome */
hash_name = hash(name);
if (!search(invitati, hash_name)) { /* se non esiste un invitato di quel nome*/
rbinsert(invitati, hash_name, name, sex, money, age, height, weight, hair, build, days);
} /* chiusura if search*/
else { /* aggiorno invitato*/
p = search(invitati, hash_name);
update_invitato(p, hash_name, name, sex, money, age, height, weight, hair, build, days);
}
} /* chiusura if in */
else if (strcmp(azione, "stampa") == 0) { /* azione input stampa invitato */
scanf("%s", name);
hash_name = hash(name);
p = search(invitati, hash_name); /* cerco invitato*/
if (p)
stampa_invitato(p);
else
printf("Non ci sono invitati di nome %s\n", name);
}
else if (strcmp(azione, "out") == 0) {/* azione input estrometti */
scanf("%s", name);
hash_name = hash(name);
p = search(invitati, hash_name); /* cerco invitato*/
rbdelete(invitati, p);
}
/* fa casino, stampa quello cancellato e non un altro... NON ORDINA*/
else if (strcmp(azione, "invitati") == 0) {/* azione input invitati */
p = treemin(invitati);
printf("(\n");
while(p) {
printf("%s\n", p->i);
p = treesucc(invitati, p);
} /* end of while */
printf(")\n");
}
Il codice dell'algorimto rb è questo:
/* CREATE RB TREE */
rbtree *createrbtree(void) {
rbtree *p = malloc(sizeof(rbtree));
if(!p) {
fprintf(stderr,"Errore di allocazione A\n");
exit(-1);
}
p->root = malloc(sizeof(Invitato));
if(!p->root) {
fprintf(stderr,"Errore di allocazione B\n");
exit(-2);
}
p->nil = p->root;
p->nil->sx = p->nil->dx = p->nil->up = p->nil;
p->nil->c = black;
return p;
}
/* SORT */
void inord(Invitato *p, Invitato *nil, void (*op)(Invitato *))
{
if(p != nil) {
inord(p->sx,nil,op);
(*op)(p);
inord(p->dx,nil,op);
}
}
/* SORT BY KEY */
void inorder(rbtree *p, void (*op)(Invitato *))
{
inord(p->root, p->nil, op);
}
/* SEARCH */
Invitato *search(rbtree *r, key k)
{
Invitato *p = r->root;
while(p != r->nil && k != p->v)
p = k < p->v ? p->sx : p->dx;
return p == r->nil ? NULL : p;
}
Invitato *rbtmin(Invitato *p, Invitato *nil)
{
for(;p->sx != nil;p = p->sx);
return p;
}
Invitato *rbtmax(Invitato *p, Invitato *nil)
{
for(;p->dx != nil;p = p->dx);
return p;
}
/* MIN */
Invitato *treemin(rbtree *r)
{
return rbtmin(r->root,r->nil);
}
/* MAX */
Invitato *treemax(rbtree *r)
{
return rbtmax(r->root,r->nil);
}
/* NODO SUCESSIVO */
Invitato *treesucc(rbtree *r, Invitato *q)
{
Invitato *qq;
if(q->dx != r->nil)
return rbtmin(q->dx,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->dx) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
/* NODO PRECEDENTE */
Invitato *treepred(rbtree *r, Invitato *q)
{
Invitato *qq;
if(q->sx != r->nil)
return rbtmax(q->sx,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->sx) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
void sxrotate(rbtree *r, Invitato *x)
{
Invitato *y = x->dx;
x->dx = y->sx;
if(y->sx != r->nil)
y->sx->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->sx)
y->up->sx = y;
else
y->up->dx = y;
y->sx = x;
x->up = y;
}
void dxrotate(rbtree *r, Invitato *x)
{
Invitato *y = x->sx;
x->sx = y->dx;
if(y->dx != r->nil)
y->dx->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->dx)
y->up->dx = y;
else
y->up->sx = y;
y->dx = x;
x->up = y;
}
Invitato *simpleinsert(rbtree *tree, key hash_name, nome name, sesso sex,
denaro money, eta age, altezza height, peso weight,
capelli hair, costituzione build, presenza days)
{
Invitato *q = malloc(sizeof(Invitato));
Invitato *r = tree->root;
Invitato *s = tree->nil;
q->i = malloc((strlen(name)+1)*sizeof(char));
// q->s = malloc((strlen(sesso)+1)*sizeof(enum));
// q->d = malloc((strlen(money)+1)*sizeof(char));
// q->e = malloc((strlen(age)+1)*sizeof(char));
// q->h = malloc((strlen(height)+1)*sizeof(char));
// q->w = malloc((strlen(weigth)+1)*sizeof(char));
// q->cap = malloc((strlen(hair)+1)*sizeof(char));
// q->b = malloc((strlen(build)+1)*sizeof(char));
q->p = malloc((strlen(days)+1)*sizeof(char));
if(!q) {
fprintf(stderr,"Errore di allocazione C\n");
exit(-4);
}
q->v = hash_name;
strcpy(q->i, name);
q->s = sex;
q->d = money;
q->e = age;
q->h = height;
q->w = weight;
q->cap = hair;
q->b = build;
strcpy(q->p, days);
q->sx = q->dx = tree->nil;
q->c = red;
while(r != tree->nil) {
s = r;
r = hash_name < r->v ? r->sx : r->dx;
}
q->up = s;
if(s == tree->nil)
return tree->root = q;
if(hash_name < s->v)
s->sx = q;
else
s->dx = q;
return q;
}
void rbinsert(rbtree *tree, key hash_name, nome name, sesso sex, denaro money,
eta age, altezza height, peso weight, capelli hair,
costituzione build, presenza days)
{
Invitato *x = simpleinsert(tree, hash_name, name, sex, money,
age, height, weight, hair, build, days);
Invitato *y;
while(x != tree->root && x->up->c == red) {
if(x->up == x->up->up->sx) { /* caso L */
y = x->up->up->dx;
if(y->c == red) {
x->up->c = black; /* caso 1L */
y->c = black; /* caso 1L */
x->up->up->c = red; /* caso 1L */
x = x->up->up; /* caso 1L */
} else {
if(x == x->up->dx) /* caso 2L */
sxrotate(tree,x = x->up); /* caso 2L */
x->up->c = black; /* caso 3L */
x->up->up->c = red; /* caso 3L */
dxrotate(tree,x->up->up); /* caso 3L */
}
} else { /* caso R */
y = x->up->up->sx;
if(y->c == red) {
x->up->c = black; /* caso 1R */
y->c = black; /* caso 1R */
x->up->up->c = red; /* caso 1R */
x = x->up->up; /* caso 1R */
} else {
if(x == x->up->sx) /* caso 2R */
dxrotate(tree,x = x->up); /* caso 2R */
x->up->c = black; /* caso 3R */
x->up->up->c = red; /* caso 3R */
sxrotate(tree,x->up->up); /* caso 3R */
}
}
}
tree->root->c = black;
}
/* FIXUP RBTREE */
void fixup(rbtree *tree, Invitato *x)
{
Invitato *w;
while(x != tree->root && x->c == black) {
if(x == x->up->sx) { /* caso L */
if((w = x->up->dx)->c == red) {
w->c = black; /* caso 1L */
x->up->c = red; /* caso 1L */
sxrotate(tree,x->up); /* caso 1L */
w = x->up->dx; /* caso 1L */
}
if(w->sx->c == black && w->dx->c == black) {
w->c = red; /* caso 2L */
x = x->up; /* caso 2L */
} else {
if(w->dx->c == black) {
w->sx->c = black; /* caso 3L */
w->c = red; /* caso 3L */
dxrotate(tree,w); /* caso 3L */
w = x->up->dx; /* caso 3L */
}
w->c = x->up->c; /* caso 4L */
x->up->c = black; /* caso 4L */
w->dx->c = black; /* caso 4L */
sxrotate(tree,x->up); /* caso 4L */
x = tree->root; /* caso 4L */
}
} else { /* caso R */
if((w = x->up->sx)->c == red) {
w->c = black; /* caso 1R */
x->up->c = red; /* caso 1R */
dxrotate(tree,x->up); /* caso 1R */
w = x->up->sx; /* caso 1R */
}
if(w->dx->c == black && w->sx->c == black) {
w->c = red; /* caso 2R */
x = x->up; /* caso 2R */
} else {
if(w->sx->c == black) {
w->dx->c = black; /* caso 3R */
w->c = red; /* caso 3R */
sxrotate(tree,w); /* caso 3R */
w = x->up->sx; /* caso 3R */
}
w->c = x->up->c; /* caso 4R */
x->up->c = black; /* caso 4R */
w->sx->c = black; /* caso 4R */
dxrotate(tree,x->up); /* caso 4R */
x = tree->root; /* caso 4R */
}
}
}
x->c = black;
}
void rbdelete(rbtree *tree, Invitato *q)
{
Invitato *r, *s;
if(q->sx == tree->nil || q->dx == tree->nil)
r = q;
else
r = treesucc(tree,q);
s = r->sx != tree->nil ? r->sx : r->dx;
s->up = r->up;
if(r->up == tree->nil)
tree->root = s;
else
if(r == r->up->sx)
r->up->sx = s;
else
r->up->dx = s;
if(r != q)
q->v = r->v;
if(r->c == black)
fixup(tree, s);
free(r);
}
L'inserimento, aggiornamento, cancellazione e stampa funzionano.
mi fa casino invece il caso 'invitati'.
Dovrei stamparli in ordine alfabeti.
A volte va, a volte no e inoltre se elimino un invitato (out invitato), capita che facendo 'invitati' me lo mostri ancora, mentre non ne compare più un altro.
La conferma dell'eliminazione però ce l'ho in quanto facendo 'stampa invitato' mi dice che non esiste.
Ho anche un problema con la malloc che ho commentato.
Poi altri dubbi li posto più avanti.
Se poteste aiutarmi ve ne sarei molto grato.