Aiuto ricerca in una stringa

di il
18 risposte

Aiuto ricerca in una stringa

Salve,

sono vicino alla data del mio esame di programmazione e ho bisogno di creare un programma da portare poi all'esame..

Si vuole simulare la gestione di un dizionario della lingua italiana. Il dizionario è
indicizzato tramite le lettere dell’alfabeto ed ogni parola contiene il suo significato. Ci
sono al massimo 10 parole per ogni lettera e le parole sono inserite in ordine alfabetico
(supporre che il dizionario sia pieno).
Permettere all’utente di:
· Data una parola, ricercarla nel dizionario e visualizzare il significato (la
ricerca deve essere binaria)
· Visualizzare tutte le parole che finiscono con tre caratteri dati dall’utente (ad
esempio “sto”)
Provvedere all’implementazione dell’algoritmo per la simulazione del dizionario.


Per quanto riguarda il secondo punto, potete aiutarmi almeno dicendomi come posso fare? Mi mancano proprio le idee..

Ecco il codice che ho scritto fino ad adesso..
#include <stdio.h>
#include <string.h>
int ricerca_binaria(char chiave[], char *parole[], int n);
void main()
{
     char chiave[10];
	 int n,indice;
	 char *parole[3]={"Antonio","Jasmine","Vincenzo"};
	 char *vocab[3]={"Il mio nome","Il nome della mia ragazza","Il nome del mio amico"};
	 printf("Inserisci la parola da cercare: ");
	 gets(chiave);
	 n=3;
	 indice=ricerca_binaria(chiave,parole,n);
	 if(indice>=0)
	 {
                  printf("%s: %s\n",chiave,vocab[indice]);
     }
     else
                  printf("Chiave non trovata\n");
                       
     getch();
}


int ricerca_binaria(char chiave[], char *parole[], int n)
{
    int mediano, primo=0, ultimo=n-1;
    while (primo<=ultimo)
    {
          mediano=(primo+ultimo)/2;
          if(strcmp(chiave,parole[mediano])==0)
             return mediano;
          else if(strcmp(chiave,parole[mediano])<0)
             ultimo=mediano-1;
          else 
             primo=mediano+1;
    }
    return -1;
}
Grazie per eventuali risposte.. Per me è panico totale..

18 Risposte

  • Re: Aiuto ricerca in una stringa

    Potresti usare strstr vedere se una stringa S2 è contenuta in un altra stringa S1 . Questa funzione ti ritorna la posizione dove ha trovato la prima l'occorrenza. se questa posizione si trova a strlen(S2) caratteri lontano dalla fine allora S1 è una stringa valida.

    la definizione lo puoi trovare quì:
    http://www.cplusplus.com/reference/clibrary/cstring/strstr/
  • Re: Aiuto ricerca in una stringa

    Scusa non ho capito come faccio a verificare se sono gli ultimi tre caratteri.. Con la strstr estraggo la chiave non tutta la parola... O sbaglio?
  • Re: Aiuto ricerca in una stringa

    Stringa S1: "prova" strlen(S1) = 6
    stringa S2: "ova" strlen(S2) = 3
    char * pos = strstr(S1,S2);

    //pos inizia dalla lettera o di S1

    if(pos!=NULL)
    se strlen(pos) == strlen(S2) stringa S1 è stringa valida.
  • Re: Aiuto ricerca in una stringa

    Potrebbe anche capitarti il seguente caso:

    S1 = "provaprova";
    S2 = "ova";

    la procedura di prima non funziona perche strstr ti trova la prima occorrenza, allora come fare:
    
    char s1[] = "Provaprova";
    char s2[] = "ova";
    char *pos = s1;
    
    do
    {
    	pos = strstr(pos,s2);
    	if(pos!= NULL)
    	{
    		if(strlen(pos) == strlen(s2))
    		{
    			//trovato
    			break;
    		}
    		else
    		{
    			pos++;
    		}
    	}
    }while(pos != NULL);
    
  • Re: Aiuto ricerca in una stringa

    Allora io mi devo muovere in questo array char *parole[3]={"Antonio","Jasmine","Vincenzo"};

    ho una chiave di tre lettere...

    Ho avviato il procedimento che mi hai scritto ma non riesco a visualizzare tutta la parola.. Dice che c'è ma non la riesco a visualizzare.. se quelle 3 lettere sono alla fine di 10 parole come faccio a visualizzarle tutte?
  • Re: Aiuto ricerca in una stringa

    Quello è un vettore di 3 stringhe. tu la ricerca lo fai una stringa x volta. così sai qual'è la stringa che contiene la chiave.
  • Re: Aiuto ricerca in una stringa

    Tipo una cosa così:
    
    #include <stdio.h>
    #include <string.h>
    
    bool trova(char *s1, char *s2)
    {
    	char *pos = strstr(s1,s2);
    	bool ret = false;
    	pos = s1;
    	do
    	{
    		pos = strstr(pos,s2);
    		if(pos!= NULL)
    		{
    			if(strlen(pos) == strlen(s2))
    			{
    				ret = true;
    				break;
    			}
    			else
    			{
    				pos++;
    			}
    		}
    	}while(pos != NULL);
    	return ret;
    }
    int main()
    {
    	char *parole[3]={"Antonio","Jasmine","Vincenzo"};
    	
    	int i;
    	for(i = 0; i < 3; i++)
    	{
    		if(trova(parole[i],"ine"))
    			printf("%s",parole[i]);
    	}
    	return 0;
    }
    
  • Re: Aiuto ricerca in una stringa

    Mi hai illuminato!!! Mi è venuto :O GRAZIE!

    Ho preso spunto dai tuoi codici ed ho ftt cosi
     printf("Inserisci altri tre caratteri: ");
         gets(finepar);
         for(i=0;i<n;i++)
         {
                         strcpy(testo,parole[i]);
                         m=strlen(testo);
                         if (testo[m-3]==finepar[0] && testo[m-2]==finepar[1] && testo[m-1]==finepar[2])
                         {
                                                    printf("%s ",parole[i]);
                                                    res++;
                         }
         }
         if(res==0)
                   printf("Nessun risultato\n");
    Ho copiato parola per parola in un altro array, ne ho calcolato la lunghezza volta per volta e se gli ultimi 3 erano uguali ai 3 inseriti la stampavo! Ogni volta che stampo incremento res di 1 e se alla fine res rimane a 0 vuol dire che non c'è nessun risultato

    Funziona

    CMQ GRAZIE! Piano piano mi hai fatto capire il ragionamento..
  • Re: Aiuto ricerca in una stringa

    E se il confronto lo dovessi fare con una chiave da n caratteri? che fai un if infinito?
    Se una parola del dizionario fosse più corta di 3 caratteri il tuo programma va in crash.
  • Re: Aiuto ricerca in una stringa

    In quel caso userei due variabili diverse invece dei numeri e con un do while incrementerei le due variabili passo per passo..
  • Re: Aiuto ricerca in una stringa

    Un if prima di tutto il procedimento che vanno ad escludere le parole con meno di tre caratteri..
  • Re: Aiuto ricerca in una stringa

    Guarda che sono tutte domande che ti può fare il prof quindi è meglio pensare ad una algoritmo generico.
  • Re: Aiuto ricerca in una stringa

    Infatti me le sto segnando tutte cosi domani lo perfeziono e mi preparo le risposte in caso di domande del genere

    comunque grazie! restando in questo forum credo di poter migliorare sempre di più! ci devo venire più spesso
  • Re: Aiuto ricerca in una stringa

    Ecco il codice completo che ho fatto

    Riconosce sia parole che cominciano in minuscolo che in maiuscolo.

    al secondo blocco se non vengono inseriti tre caratteri non va avanti e ripete il processo

    credo vada bene
    #include <stdio.h>
    #include <string.h>
    int ricerca_binaria(char chiave[], char *parole[], int n);
    void main()
    {
         char chiave[10];
    	 int n,indice,m,i,res=0;
    	 char *parole[]={"Abete","Abiosfera","Abisso","Antonio","Argilla","Bambu","Bomba","Buca","Buddismo","Buongiorno","Carne","Chioma","Cicca","Collare","Coppia"};
    	 char *parole2[]={"abete","abiosfera","abisso","antonio","argilla","bambu","bomba","buca","buddismo","buongiorno","carne","chioma","cicca","collare","coppia"};
    	 char *vocab[]={"Nome di alcuni alberi","Parte del nostro pianeta dove non e' possibile la vita","Luogo in cui la grande profondita' conferisce un aspetto buio e pauroso","Nome proprio di persona","Tipo di roccia sedimentaria","Nome comune di una pianta","Involucro contenente esplosivo","Cavita del terreno","Religione indiana","Forma di saluto","La parte dei tessuti molli del corpo","Folta capigliatura","Avanzo di sigaro o di sigaretta","Oggetto da mettere al collo degli animali","Abbinamento di due cose o persone"};
    	 char testo[20],finepar[3];
    	 printf("Inserisci la parola da cercare: ");
    	 gets(chiave);
    	 n=15;
    	 indice=ricerca_binaria(chiave,parole,n);
    	 if (indice<0)
    	 {
    		 indice=ricerca_binaria(chiave,parole2,n);
    	 }
    	 if(indice>=0)
    	 {
                      printf("%s: %s\n",chiave,vocab[indice]);
         }
         else
                      printf("Chiave non trovata\n");
                      
         do
    	 {
    	 printf("Inserisci altri tre caratteri: ");
         gets(finepar);
    	 } while(strlen(finepar)!=3);
    	 printf("Ecco le parole che terminano per %s\n",finepar);
         for(i=0;i<n;i++)
         {
                         strcpy(testo,parole[i]);
                         m=strlen(testo);
                         if (testo[m-3]==finepar[0] && testo[m-2]==finepar[1] && testo[m-1]==finepar[2])
                         {
                                                    printf("%s ",parole[i]);
                                                    res++;
                         }
         }
         if(res==0)
                   printf("Nessun risultato\n");
         getch();
    }
    
    
    int ricerca_binaria(char chiave[], char *parole[], int n)
    {
        int mediano, primo=0, ultimo=n-1;
        while (primo<=ultimo)
        {
              mediano=(primo+ultimo)/2;
              if(strcmp(chiave,parole[mediano])==0)
                 return mediano;
              else if(strcmp(chiave,parole[mediano])<0)
                 ultimo=mediano-1;
              else 
                 primo=mediano+1;
        }
        return -1;
    }
Devi accedere o registrarti per scrivere nel forum
18 risposte