Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Come stampare stringa cercata con il più lungo prefisso comune
Forum - C/C++ - Come stampare stringa cercata con il più lungo prefisso comune

Avatar
stayerman (Normal User)
Newbie


Messaggi: 1
Iscritto: 21/06/2012

Segnala al moderatore
Postato alle 11:20
Giovedì, 21/06/2012
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.

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define N (1000)
  6.  
  7. /* Definisco il tipo Nodo*/
  8. struct Nodo
  9. {
  10.    char val[N+1];
  11.    struct Nodo* left;
  12.    struct Nodo* right;
  13. };
  14.  
  15. /*Definisco l'albero binario di ricerca*/
  16. typedef struct Nodo* Albero;
  17.  
  18. /*
  19.    DEFINIZIONE DELLE PROCEDURE E DELLE FUNZIONI
  20. */
  21.  
  22. /*Definizione della procedura di inserimento chiavi*/
  23. void inserisci (Albero *t, char valore[]);
  24.  
  25. /*Definizione della funzione del calcolo dell'altezza*/
  26. int altezza(Albero t);
  27.  
  28. /*Definizione della funzione di ricerca iterativa*/
  29. Albero RicercaIterativa(Albero t, char valore[]);
  30.  
  31. /*Definizione della funzione che restituisce i primi N caratteri uguali*/
  32. int sstringlen (const char * a, const char * b);
  33.  
  34. /*Definizione della funzione che restituisce la sottostringa piu lunga radicata
  35.  * nel sottoalbero*/
  36. int soluzione (Albero t);
  37.  
  38. /*
  39.  * FUNZIONE MAIN
  40. */
  41.  
  42. int main ()
  43. {
  44.    int numchiavi,i;
  45.    char str[N+1];
  46.    char cercare[N+1];
  47.    
  48.    Albero t = NULL;
  49.    
  50.    /*Leggo da input il numero di chiavi*/
  51.    scanf("%d",&numchiavi);
  52.    
  53.    for (i=0; i<numchiavi;i++)
  54.    {
  55.       scanf("%s", str);
  56.       inserisci(&t, str);
  57.    }
  58.    /*Routine di test --- la stampa è in fondo*/
  59.    printf("\n");
  60.    printf("Chiave da cercare: ");
  61.    scanf("%s",cercare);
  62.    
  63.    RicercaIterativa(t,cercare);
  64.    
  65.    return 0;
  66. }
  67.  
  68. /*
  69.    FUNZIONI ALBERO BINARIO DI RICERCA
  70. */
  71.  
  72.  
  73. /*Procedura Inserimento*/
  74. void inserisci (Albero *t, char valore[])
  75. {
  76.    struct Nodo* p;
  77.    struct Nodo* x;
  78.    struct Nodo* e;
  79.    x = *t;
  80.    
  81.    /*Creo il nodo da inserire contenente il valore*/
  82.    e = malloc(sizeof(struct Nodo));
  83.    strcpy(e->val,valore);
  84.    e->left = e->right = NULL;
  85.    
  86.    
  87.    
  88.    /*Se l'albero è vuoto imposto 'e' come radice dell'albero*/
  89.    if (x == NULL)
  90.    {  
  91.       *t = e;
  92.       return;
  93.    }
  94.  
  95.    /*Altrimenti cerca la posizione della foglia nell'albero*/
  96.    while( x!=NULL)
  97.    {
  98.       p = x;
  99.      
  100.       if (strcmp(x->val, valore) < 0)
  101.       {
  102.          x = x->right;
  103.       }
  104.       else
  105.       {
  106.          x = x->left;
  107.       }
  108.    }
  109.    
  110.    /*Ora p punta al padre del nuovo elemento da inserire in t, quindi si
  111.     *procede a linkare p ed e*/
  112.    if (strcmp(p->val, valore) < 0)
  113.    {
  114.       p->right = e;
  115.    }
  116.    else
  117.    {
  118.       p->left = e;
  119.    }
  120. }
  121.  
  122. /*Funzione di ricerca iterativa
  123.  *Restituisce il puntatore al nodo con chiave k, se esiste, altrimenti NULL*/
  124. Albero RicercaIterativa(Albero t, char valore[])
  125. {
  126.    int sol = 0;
  127.    
  128.    while ( (t != NULL) && (strcmp(valore, t->val) != 0))
  129.    {
  130.       if (strcmp(valore, t->val) < 0)
  131.          t = t->left;
  132.       else
  133.          t = t->right;
  134.    }
  135.    
  136.    sol = soluzione(t);
  137.    printf("Risultato: %d",sol);
  138.    
  139.    return t;
  140. }
  141.  
  142.  
  143. int sstringlen (const char * a, const char * b)
  144. {
  145.         int i = 0;
  146.    
  147.         if (a == NULL || b == NULL)
  148.    {
  149.       return 0;
  150.    }
  151.         while (a[i]!= '\0' && b[i]!= '\0' && a[i] == b[i])
  152.    {
  153.                 i++;
  154.    }
  155.         return i;
  156. }
  157.  
  158. /*Funzione che restituisce la sottostringa piu lunga radicata nel sottoalbero*/
  159. int soluzione (Albero t)
  160. {
  161.         int max = 0, maxs, maxd, max2;
  162.    
  163.         if (t->left == NULL && t->right == NULL)
  164.                 return 0;
  165.         if (t->right == NULL)
  166.                 max = sstringlen(t->left->val, t->right->val);
  167.                 maxs = soluzione(t->left);
  168.                 if (max>maxs) return max;
  169.                 else return maxs;
  170.         if (t->left == NULL)  
  171.                 max = sstringlen(t->right->val, t->left->val);
  172.                 maxd = soluzione(t->right);
  173.                 if (max>maxd) return max;
  174.                 else return maxd;
  175.         maxs = soluzione(t->left);
  176.         maxd = soluzione(t->right);
  177.         max = sstringlen(t->right->val, t->left->val);
  178.         max2 = sstringlen(t->left->val, t->right->val);
  179.         if (maxs>maxd) maxd=maxs;
  180.         if (max2>max) max=max2;
  181.         if (maxd>max) return maxd;
  182.         else return max;
  183. }


PM Quote