21/06/12 9:20
stayerman
Ciao a tutti, vi seguo da anni ed ero pure iscritto, peccato che per tempo, voglia e altri fatto non ho avuto modo di ricercarmi il vecchio username!
Posto subito il mio problema.
Devo costruire un albero binario di ricerca (di stringhe). inserire manualmente le chiavi, poi, cercare una chiave, se esiste allora devo cercare la stringa radicata nel sottoalbero con il prefisso comune più lungo! Stampare quindi
la lunghezza.
un esempio di input: (il primo è il numero di chiavi, l'ultimo è la chiave da cercare)
7
trentratre
trentini
entrarono
trento
tutti
trentratre
trotterellando
tutti
output aspettato:
1
io sono riuscito a fare tutto ma come output da sempre 0. vi posto il mio codice sperando di poter essere il piu preciso possibile.
Posto subito il mio problema.
Devo costruire un albero binario di ricerca (di stringhe). inserire manualmente le chiavi, poi, cercare una chiave, se esiste allora devo cercare la stringa radicata nel sottoalbero con il prefisso comune più lungo! Stampare quindi
la lunghezza.
un esempio di input: (il primo è il numero di chiavi, l'ultimo è la chiave da cercare)
7
trentratre
trentini
entrarono
trento
tutti
trentratre
trotterellando
tutti
output aspettato:
1
io sono riuscito a fare tutto ma come output da sempre 0. vi posto il mio codice sperando di poter essere il piu preciso possibile.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N (1000)
/* Definisco il tipo Nodo*/
struct Nodo
{
char val[N+1];
struct Nodo* left;
struct Nodo* right;
};
/*Definisco l'albero binario di ricerca*/
typedef struct Nodo* Albero;
/*
DEFINIZIONE DELLE PROCEDURE E DELLE FUNZIONI
*/
/*Definizione della procedura di inserimento chiavi*/
void inserisci (Albero *t, char valore[]);
/*Definizione della funzione del calcolo dell'altezza*/
int altezza(Albero t);
/*Definizione della funzione di ricerca iterativa*/
Albero RicercaIterativa(Albero t, char valore[]);
/*Definizione della funzione che restituisce i primi N caratteri uguali*/
int sstringlen (const char * a, const char * b);
/*Definizione della funzione che restituisce la sottostringa piu lunga radicata
* nel sottoalbero*/
int soluzione (Albero t);
/*
* FUNZIONE MAIN
*/
int main ()
{
int numchiavi,i;
char str[N+1];
char cercare[N+1];
Albero t = NULL;
/*Leggo da input il numero di chiavi*/
scanf("%d",&numchiavi);
for (i=0; i<numchiavi;i++)
{
scanf("%s", str);
inserisci(&t, str);
}
/*Routine di test --- la stampa è in fondo*/
printf("\n");
printf("Chiave da cercare: ");
scanf("%s",cercare);
RicercaIterativa(t,cercare);
return 0;
}
/*
FUNZIONI ALBERO BINARIO DI RICERCA
*/
/*Procedura Inserimento*/
void inserisci (Albero *t, char valore[])
{
struct Nodo* p;
struct Nodo* x;
struct Nodo* e;
x = *t;
/*Creo il nodo da inserire contenente il valore*/
e = malloc(sizeof(struct Nodo));
strcpy(e->val,valore);
e->left = e->right = NULL;
/*Se l'albero è vuoto imposto 'e' come radice dell'albero*/
if (x == NULL)
{
*t = e;
return;
}
/*Altrimenti cerca la posizione della foglia nell'albero*/
while( x!=NULL)
{
p = x;
if (strcmp(x->val, valore) < 0)
{
x = x->right;
}
else
{
x = x->left;
}
}
/*Ora p punta al padre del nuovo elemento da inserire in t, quindi si
*procede a linkare p ed e*/
if (strcmp(p->val, valore) < 0)
{
p->right = e;
}
else
{
p->left = e;
}
}
/*Funzione di ricerca iterativa
*Restituisce il puntatore al nodo con chiave k, se esiste, altrimenti NULL*/
Albero RicercaIterativa(Albero t, char valore[])
{
int sol = 0;
while ( (t != NULL) && (strcmp(valore, t->val) != 0))
{
if (strcmp(valore, t->val) < 0)
t = t->left;
else
t = t->right;
}
sol = soluzione(t);
printf("Risultato: %d",sol);
return t;
}
int sstringlen (const char * a, const char * b)
{
int i = 0;
if (a == NULL || b == NULL)
{
return 0;
}
while (a[i]!= 'Ciao a tutti, vi seguo da anni ed ero pure iscritto, peccato che per tempo, voglia e altri fatto non ho avuto modo di ricercarmi il vecchio username!
Posto subito il mio problema.
Devo costruire un albero binario di ricerca (di stringhe). inserire manualmente le chiavi, poi, cercare una chiave, se esiste allora devo cercare la stringa radicata nel sottoalbero con il prefisso comune più lungo! Stampare quindi
la lunghezza.
un esempio di input: (il primo è il numero di chiavi, l'ultimo è la chiave da cercare)
7
trentratre
trentini
entrarono
trento
tutti
trentratre
trotterellando
tutti
output aspettato:
1
io sono riuscito a fare tutto ma come output da sempre 0. vi posto il mio codice sperando di poter essere il piu preciso possibile.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N (1000)
/* Definisco il tipo Nodo*/
struct Nodo
{
char val[N+1];
struct Nodo* left;
struct Nodo* right;
};
/*Definisco l'albero binario di ricerca*/
typedef struct Nodo* Albero;
/*
DEFINIZIONE DELLE PROCEDURE E DELLE FUNZIONI
*/
/*Definizione della procedura di inserimento chiavi*/
void inserisci (Albero *t, char valore[]);
/*Definizione della funzione del calcolo dell'altezza*/
int altezza(Albero t);
/*Definizione della funzione di ricerca iterativa*/
Albero RicercaIterativa(Albero t, char valore[]);
/*Definizione della funzione che restituisce i primi N caratteri uguali*/
int sstringlen (const char * a, const char * b);
/*Definizione della funzione che restituisce la sottostringa piu lunga radicata
* nel sottoalbero*/
int soluzione (Albero t);
/*
* FUNZIONE MAIN
*/
int main ()
{
int numchiavi,i;
char str[N+1];
char cercare[N+1];
Albero t = NULL;
/*Leggo da input il numero di chiavi*/
scanf("%d",&numchiavi);
for (i=0; i<numchiavi;i++)
{
scanf("%s", str);
inserisci(&t, str);
}
/*Routine di test --- la stampa è in fondo*/
printf("\n");
printf("Chiave da cercare: ");
scanf("%s",cercare);
RicercaIterativa(t,cercare);
return 0;
}
/*
FUNZIONI ALBERO BINARIO DI RICERCA
*/
/*Procedura Inserimento*/
void inserisci (Albero *t, char valore[])
{
struct Nodo* p;
struct Nodo* x;
struct Nodo* e;
x = *t;
/*Creo il nodo da inserire contenente il valore*/
e = malloc(sizeof(struct Nodo));
strcpy(e->val,valore);
e->left = e->right = NULL;
/*Se l'albero è vuoto imposto 'e' come radice dell'albero*/
if (x == NULL)
{
*t = e;
return;
}
/*Altrimenti cerca la posizione della foglia nell'albero*/
while( x!=NULL)
{
p = x;
if (strcmp(x->val, valore) < 0)
{
x = x->right;
}
else
{
x = x->left;
}
}
/*Ora p punta al padre del nuovo elemento da inserire in t, quindi si
*procede a linkare p ed e*/
if (strcmp(p->val, valore) < 0)
{
p->right = e;
}
else
{
p->left = e;
}
}
/*Funzione di ricerca iterativa
*Restituisce il puntatore al nodo con chiave k, se esiste, altrimenti NULL*/
Albero RicercaIterativa(Albero t, char valore[])
{
int sol = 0;
while ( (t != NULL) && (strcmp(valore, t->val) != 0))
{
if (strcmp(valore, t->val) < 0)
t = t->left;
else
t = t->right;
}
sol = soluzione(t);
printf("Risultato: %d",sol);
return t;
}
int sstringlen (const char * a, const char * b)
{
int i = 0;
if (a == NULL || b == NULL)
{
return 0;
}
while (a[i]!= '{parsed_message}' && b[i]!= '{parsed_message}' && a[i] == b[i])
{
i++;
}
return i;
}
/*Funzione che restituisce la sottostringa piu lunga radicata nel sottoalbero*/
int soluzione (Albero t)
{
int max = 0, maxs, maxd, max2;
if (t->left == NULL && t->right == NULL)
return 0;
if (t->right == NULL)
max = sstringlen(t->left->val, t->right->val);
maxs = soluzione(t->left);
if (max>maxs) return max;
else return maxs;
if (t->left == NULL)
max = sstringlen(t->right->val, t->left->val);
maxd = soluzione(t->right);
if (max>maxd) return max;
else return maxd;
maxs = soluzione(t->left);
maxd = soluzione(t->right);
max = sstringlen(t->right->val, t->left->val);
max2 = sstringlen(t->left->val, t->right->val);
if (maxs>maxd) maxd=maxs;
if (max2>max) max=max2;
if (maxd>max) return maxd;
else return max;
}
' && b[i]!= 'Ciao a tutti, vi seguo da anni ed ero pure iscritto, peccato che per tempo, voglia e altri fatto non ho avuto modo di ricercarmi il vecchio username!
Posto subito il mio problema.
Devo costruire un albero binario di ricerca (di stringhe). inserire manualmente le chiavi, poi, cercare una chiave, se esiste allora devo cercare la stringa radicata nel sottoalbero con il prefisso comune più lungo! Stampare quindi
la lunghezza.
un esempio di input: (il primo è il numero di chiavi, l'ultimo è la chiave da cercare)
7
trentratre
trentini
entrarono
trento
tutti
trentratre
trotterellando
tutti
output aspettato:
1
io sono riuscito a fare tutto ma come output da sempre 0. vi posto il mio codice sperando di poter essere il piu preciso possibile.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N (1000)
/* Definisco il tipo Nodo*/
struct Nodo
{
char val[N+1];
struct Nodo* left;
struct Nodo* right;
};
/*Definisco l'albero binario di ricerca*/
typedef struct Nodo* Albero;
/*
DEFINIZIONE DELLE PROCEDURE E DELLE FUNZIONI
*/
/*Definizione della procedura di inserimento chiavi*/
void inserisci (Albero *t, char valore[]);
/*Definizione della funzione del calcolo dell'altezza*/
int altezza(Albero t);
/*Definizione della funzione di ricerca iterativa*/
Albero RicercaIterativa(Albero t, char valore[]);
/*Definizione della funzione che restituisce i primi N caratteri uguali*/
int sstringlen (const char * a, const char * b);
/*Definizione della funzione che restituisce la sottostringa piu lunga radicata
* nel sottoalbero*/
int soluzione (Albero t);
/*
* FUNZIONE MAIN
*/
int main ()
{
int numchiavi,i;
char str[N+1];
char cercare[N+1];
Albero t = NULL;
/*Leggo da input il numero di chiavi*/
scanf("%d",&numchiavi);
for (i=0; i<numchiavi;i++)
{
scanf("%s", str);
inserisci(&t, str);
}
/*Routine di test --- la stampa è in fondo*/
printf("\n");
printf("Chiave da cercare: ");
scanf("%s",cercare);
RicercaIterativa(t,cercare);
return 0;
}
/*
FUNZIONI ALBERO BINARIO DI RICERCA
*/
/*Procedura Inserimento*/
void inserisci (Albero *t, char valore[])
{
struct Nodo* p;
struct Nodo* x;
struct Nodo* e;
x = *t;
/*Creo il nodo da inserire contenente il valore*/
e = malloc(sizeof(struct Nodo));
strcpy(e->val,valore);
e->left = e->right = NULL;
/*Se l'albero è vuoto imposto 'e' come radice dell'albero*/
if (x == NULL)
{
*t = e;
return;
}
/*Altrimenti cerca la posizione della foglia nell'albero*/
while( x!=NULL)
{
p = x;
if (strcmp(x->val, valore) < 0)
{
x = x->right;
}
else
{
x = x->left;
}
}
/*Ora p punta al padre del nuovo elemento da inserire in t, quindi si
*procede a linkare p ed e*/
if (strcmp(p->val, valore) < 0)
{
p->right = e;
}
else
{
p->left = e;
}
}
/*Funzione di ricerca iterativa
*Restituisce il puntatore al nodo con chiave k, se esiste, altrimenti NULL*/
Albero RicercaIterativa(Albero t, char valore[])
{
int sol = 0;
while ( (t != NULL) && (strcmp(valore, t->val) != 0))
{
if (strcmp(valore, t->val) < 0)
t = t->left;
else
t = t->right;
}
sol = soluzione(t);
printf("Risultato: %d",sol);
return t;
}
int sstringlen (const char * a, const char * b)
{
int i = 0;
if (a == NULL || b == NULL)
{
return 0;
}
while (a[i]!= '{parsed_message}' && b[i]!= '{parsed_message}' && a[i] == b[i])
{
i++;
}
return i;
}
/*Funzione che restituisce la sottostringa piu lunga radicata nel sottoalbero*/
int soluzione (Albero t)
{
int max = 0, maxs, maxd, max2;
if (t->left == NULL && t->right == NULL)
return 0;
if (t->right == NULL)
max = sstringlen(t->left->val, t->right->val);
maxs = soluzione(t->left);
if (max>maxs) return max;
else return maxs;
if (t->left == NULL)
max = sstringlen(t->right->val, t->left->val);
maxd = soluzione(t->right);
if (max>maxd) return max;
else return maxd;
maxs = soluzione(t->left);
maxd = soluzione(t->right);
max = sstringlen(t->right->val, t->left->val);
max2 = sstringlen(t->left->val, t->right->val);
if (maxs>maxd) maxd=maxs;
if (max2>max) max=max2;
if (maxd>max) return maxd;
else return max;
}
' && a[i] == b[i])
{
i++;
}
return i;
}
/*Funzione che restituisce la sottostringa piu lunga radicata nel sottoalbero*/
int soluzione (Albero t)
{
int max = 0, maxs, maxd, max2;
if (t->left == NULL && t->right == NULL)
return 0;
if (t->right == NULL)
max = sstringlen(t->left->val, t->right->val);
maxs = soluzione(t->left);
if (max>maxs) return max;
else return maxs;
if (t->left == NULL)
max = sstringlen(t->right->val, t->left->val);
maxd = soluzione(t->right);
if (max>maxd) return max;
else return maxd;
maxs = soluzione(t->left);
maxd = soluzione(t->right);
max = sstringlen(t->right->val, t->left->val);
max2 = sstringlen(t->left->val, t->right->val);
if (maxs>maxd) maxd=maxs;
if (max2>max) max=max2;
if (maxd>max) return maxd;
else return max;
}
aaa
