ragazzi ho il segunte codice che mi calcola la distanza tra due alberi con un algoritmo detto di selkow. lasciando stare come funziona l'algoritmo, il mio problema è il seguente : ho la classe Node e il campo etichetta è di tipo char, a me serve pero operare su stringhe. ho provato con l'etichetta di tipo string ma non va. poi devo fare il confronto tra stringhe di ogni etichetta di due alberi.
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <iostream.h>
int max_depth = 64;
int depth_incr = 64;
int debug = 0;
int nid = 0;
class Node {
public:
Node(char il, Node * ilmc, Node * irs, double ici) :
l(il), lmc(ilmc), rs(irs), cid(ici), stsize(0) { id = ++nid;}
char l; /* etichetta nodo */
Node * lmc; /* child piu a sinistra*/
Node * rs; /* fratello destro */
double cid; /* costi di insertion or deletion */
double ccid; /* costo cumunlativo insertion or deletion */
int stsize; /* size del sotto albero radicato nel nodo corrent */
int id;
};
Node *
read_tree()
/* ritorna a tree in the depth-label-cost line format letto da stdin */
{
Node * * p = (Node * *)malloc((max_depth+1)*sizeof(Node *));
/* p[i] "current parent" di depth i */
p[0] = 0;
int depth;
double cid;
char lab;
scanf("%d %c %lf", &depth, &lab, &cid);
while(depth >= 0) {
Node * n = new Node(lab,0,0,cid);
if(depth > max_depth) {
max_depth += depth_incr;
realloc(p, (max_depth+1)*sizeof(Node *));
}
if(depth == 0) p[0] = n;
else {
p[depth] = n;
Node * parent = p[depth-1];
Node * lsib = parent->lmc;
if(lsib == 0) parent->lmc = n;
else {
while(lsib->rs != 0) lsib = lsib->rs;
lsib->rs = n;
}
}
scanf("%d %c %lf", &depth, &lab, &cid);
}
Node * ans = p[0];
free(p);
return ans;
}
void
write_tree_aux(Node * t, int depth)
/* helper for write_tree */
{
if(debug) printf("%3d %3d", t->id, depth);
for(int i = 0; i < depth; i++) printf(" ");
printf("%c %5.2f\n", t->l, t->cid);
for(Node * c = t->lmc; c != 0; c = c->rs)
write_tree_aux(c, depth+1);
}
void
write_tree(Node * t)
/* scrive il subtree rooted in t sullo stdout */
{
write_tree_aux(t, 0);
}
double
ccid(Node * t)
/* calcola e ritorna il ccid member per subtree(t) */
{
t->ccid = t->cid;
for(Node * c = t->lmc; c; c = c->rs)
t->ccid += ccid(c);
return t->ccid;
}
int
upd(Node * a, Node * b)
/* ritorna il costo di updating a's label to b's label */
{ if (a->l==b->l)
return 0;
else return 1;
}
double
min(double x, double y, double z)
/* minimo di x, y, and z */
{
if(x <= y) if(x <= z) return x; else return z;
else if(y <= z) return y; else return z;
}
int
num_children(Node * n)
/* ritorna il numero di children di n */
{
int ans = 0;
for(Node * c = n->lmc; c; c = c->rs) ans++;
return ans;
}
double
dist(Node * a, Node * b)
/* ritorna la edit distance between trees rooted in a e b */
{
if(debug) printf("dist(%d,%d)=?\n", a->id, b->id);
(void)ccid(a);
(void)ccid(b);
int m = num_children(a), n = num_children(b);
double * d = (double *) malloc((m+1)*(n+1)*sizeof(double));
#define D(x,y) d[(n+1)*(x)+(y)]
D(0,0) = upd(a,b);
Node * cx, * cy;
int i,j;
for(cy = b->lmc, j=1; cy; cy = cy->rs, j++)
D(0,j) = D(0,j-1) + cy->ccid;
for(cx = a->lmc, i=1; cx; cx = cx->rs, i++)
D(i,0) = D(i-1,0) + cx->ccid;
for(cx = a->lmc, i=1; cx; cx = cx->rs, i++)
for(cy = b->lmc, j=1; cy; cy = cy->rs, j++)
D(i,j) = min(D(i-1,j-1) + dist(cx,cy),
D(i,j-1) + cy->ccid, D(i-1,j) + cx->ccid);
double ans = D(m,n);
free(d);
if(debug) printf("dist(%d,%d)=%5.2f\n", a->id, b->id, ans);
return ans;
if (ans==0)
printf ("alberi uguali\n");
}
int numnodi(Node *a)
{int i;
Node *cx;
int dato=1;
for(cx = a->lmc, i=1; cx; cx = cx->rs, i++)
dato=dato+numnodi(cx);
return dato;
}
int
main(int argc, char * argv[])
{ int vito2,vito3;
int vito;
do{
if(argc > 1 && strncmp(argv[1], "-d", 2) == 0) debug = 1;
Node * a = read_tree();
write_tree(a); printf("\n");
Node * b = read_tree();
write_tree(b); printf("\n");
vito2=num_children(a);
vito3=numnodi(a);
printf("figli di a %d\n", vito2);
printf("nodi di a %d\n", vito3);
printf("Distance: %5.2f\n", dist(a,b));
cout << "premi 0 per continuare o un tasto per terminare\n";
scanf("%d", &vito);}
while (vito == 0);
}
