[c] Function ricerca binaria ricorsiva [Archivio]

View Full Version : [c] Function ricerca binaria ricorsiva

mariano89

24-02-2010, 23:00

Salve, ho bisogno di un piccolissimo aiuto. Di questo programma in c mi è stato chiesto di eseguire una function che permetta la ricerca di un numero di telefono tra un elenco di numeri e informazioni di persone da me inserite in input. In caso affermativo, il programma dovrebbe stamparmi le informazioni (nome, cognome, indirizzo) del soggetto.
Il problema è che quando vado ad eseguire la function per la ricerca di un numero tel. mi da sempre esito negativo.
Sapreste trovarmi l'errore e dirmi come modificare??
è per un progetto da consegnare domani:doh: :(

#include <stdio.h>
#include<string.h>
#include<conio.h>
#define SIZE 100
#define SIZEV 3

/*STRUCT PERSONA*/
typedef struct
{
char nome[SIZE];
char cognome[SIZE];
char indirizzo[SIZE];
char telefono[SIZE];
} Persona;

void caricaPersona ( Persona *p);
void caricaVettore(Persona *p,int n);
void ordinaVettore(Persona *p,int n);
void stampaPersona (Persona p);
void stampaVettore(Persona *p,int n);

void caricaPersona(Persona *p)
{
printf ("********************\n");
char invio;
printf("Nome:");
gets(p->nome);
printf("Cognome:");
gets(p->cognome);
printf("Indirizzo:");
gets(p->indirizzo);
printf("Telefono: 081\\");
gets(p->telefono);
}

/*Questa procedura carica il vettore*/
void caricaVettore(Persona *p,int n)
{
int i;
for(i=0;i<n;i++)
{
caricaPersona(&p[i]);
}
}

/*Questa procedura ordina il vettore*/
void ordinaVettore(Persona *p,int n)
{
int i,j;
char buffer[SIZE];
for(i=0; i<n-1; i++)
{
for(j=i+1; j<n; j++)
{

/*La strcmp prende come parametri due char* e restituisce 0 se le due stringhe sono uguali,
>0 se la prima è maggiore della seconda,
<0 se la prima è minore della seconda
(lavorando con le stringhe parlando di maggiore e minore si intende
il normale ordine lessicografico).*/

if (strcmp(p[i].cognome,p[j].cognome)>= 1)
{
strcpy(buffer,p[i].cognome);
strcpy(p[i].cognome,p[j].cognome);
strcpy(p[j].cognome,buffer);
strcpy(buffer,p[j].nome);
strcpy(p[j].nome,p[i].nome);
strcpy(p[i].nome,buffer);
strcpy(buffer,p[j].indirizzo);
strcpy(p[j].indirizzo,p[i].indirizzo);
strcpy(p[i].indirizzo,buffer);
strcpy(buffer,p[j].telefono);
strcpy(p[j].telefono,p[i].telefono);
strcpy(p[i].telefono,buffer);

}
}
}
}

/*Questa procedura stampa il vettore in output*/
void stampaPersona(Persona p)
{
printf("\nCognome:%s \nNome:%s \nIndirizzo: %s\nTelefono':%s\n",p.cognome,p.nome,p.indirizzo,p .telefono);
}
void stampaVettore(Persona *p,int n)
{
int i;
for (i=0;i<n;i++)
stampaPersona(p[i]);
}

/*Procedura ricerca binaria ricorsiva*/
int ricerca_bin(Persona gente[],int first,int last,char tel[]){
int med;
if(first > last) /* caso in cui il vettore è terminato, ritorno il valore -1 ad indicare che l'elemento non esiste */
return -1;
else
{
med = (first + last)/2;
if(tel==gente[med].telefono)
return med;
else
if (strcmp(tel,gente[med].telefono)>0) /* nel caso in cui tel sia più grande di gente[med] */
return ricerca_bin(gente,med+1,last,tel);
else
return ricerca_bin(gente,first,med-1,tel);
}
}

//*CORPO DEL PROGRAMMA*//
int main(void)
{
char ch;
int i,j,eta;
Persona p[SIZEV],buffer[SIZEV];
printf ("\n****INSERISCI CONTATTI NELLE RUBRICA*****\n");
caricaVettore(p,SIZEV);
printf ("\n************RUBRICA ORDINATA*************\n");
ordinaVettore(p,SIZEV);
stampaVettore(p,SIZEV);

/* ricerca binaria ricorsiva */
int idx;
char tel[50];
printf ("\n \n");
printf("Inserire il num da cercare:");
scanf("%c",tel);
idx = ricerca_bin(p,0,SIZEV,tel);
if(idx == -1)
printf("Siamo spiacente, ma il numero selezionato non e' stato trovato \n");
else{
printf ("numero selezionato trovato: \b");
printf("\nNome:%s \n Cognome:%s \n Indirizzo: %s\n Telefono':%d\n",p[idx].nome,p[idx].cognome,p[idx].indirizzo,p[idx].telefono);
}

system("PAUSE");
return 0;

}

bobbytre

24-02-2010, 23:27

sei sicuro che questo scanf("%c",tel); nel main sia corretto ?

il confronto tra stringhe lo gestisci in modo corretto nella funzione ricerca_bin ?

mariano89

24-02-2010, 23:37

sei sicuro che questo scanf("%c",tel); nel main sia corretto ?

meglio gets(tel)?:confused:

per l'altro punto, non saprei.. puoi suggerirmi qualcosa?:(

bobbytre

24-02-2010, 23:44

Bisognava leggere tra le righe il mio post precedente , ti avevo indicato dove erano gli errori .

Lo scanf nel main , che si aspetta di ricevere un carattere mentre tu vuoi che sia inserita una stringa, quindi o usi scanf("%s", tel); oppure va bene la funzione gets.

nella funzione ricerca_bin il confronto tra le stringhe si effettua cosi

if (strcmp(tel, gente[med].telefono) == 0)

e non cosi

if(tel==gente[med].telefono)

mariano89

24-02-2010, 23:57

grazie 1000, ora funziona però così va bene solo nel caso il num. di telefono sia composto da una cifra, come mai??
grazie ancora per un milione di volte:)

bobbytre

25-02-2010, 00:09

dovrebbe funzionare anche se il num di telefono sia una stringa qualsiasi e non per forza un numero.

come lo hai modificato ?

mariano89

25-02-2010, 00:13

cosi

#include <stdio.h>
#include<string.h>
#include<conio.h>
#define SIZE 50
#define SIZEV 3

/*STRUCT PERSONA*/
typedef struct
{
char nome[SIZE];
char cognome[SIZE];
char indirizzo[SIZE];
char telefono[SIZE];
} Persona;

void caricaPersona ( Persona *p);
void caricaVettore(Persona *p,int n);
void ordinaVettore(Persona *p,int n);
void stampaPersona (Persona p);
void stampaVettore(Persona *p,int n);

void caricaPersona(Persona *p)
{
printf ("********************\n");
char invio;
printf("Nome:");
gets(p->nome);
printf("Cognome:");
gets(p->cognome);
printf("Indirizzo:");
gets(p->indirizzo);
printf("Telefono: 081\\");
gets(p->telefono);
}

/*Questa procedura carica il vettore*/
void caricaVettore(Persona *p,int n)
{
int i;
for(i=0;i<n;i++)
{
caricaPersona(&p[i]);
}
}

/*Questa procedura ordina il vettore*/
void ordinaVettore(Persona *p,int n)
{
int i,j;
char buffer[SIZE];
for(i=0; i<n-1; i++)
{
for(j=i+1; j<n; j++)
{

/*La strcmp prende come parametri due char* e restituisce 0 se le due stringhe sono uguali,
>0 se la prima è maggiore della seconda,
<0 se la prima è minore della seconda
(lavorando con le stringhe parlando di maggiore e minore si intende
il normale ordine lessicografico).*/

if (strcmp(p[i].cognome,p[j].cognome)>= 1)
{
strcpy(buffer,p[i].cognome);
strcpy(p[i].cognome,p[j].cognome);
strcpy(p[j].cognome,buffer);
strcpy(buffer,p[j].nome);
strcpy(p[j].nome,p[i].nome);
strcpy(p[i].nome,buffer);
strcpy(buffer,p[j].indirizzo);
strcpy(p[j].indirizzo,p[i].indirizzo);
strcpy(p[i].indirizzo,buffer);
strcpy(buffer,p[j].telefono);
strcpy(p[j].telefono,p[i].telefono);
strcpy(p[i].telefono,buffer);

}
}
}
}

/*Questa procedura stampa il vettore in output*/
void stampaPersona(Persona p)
{
printf("\nCognome:%s \nNome:%s \nIndirizzo: %s\nTelefono':%s\n",p.cognome,p.nome,p.indirizzo,p.telefono);
}
void stampaVettore(Persona *p,int n)
{
int i;
for (i=0;i<n;i++)
stampaPersona(p[i]);
}

/*Procedura ricerca binaria ricorsiva*/
int ricerca_bin(Persona gente[],int first,int last,char tel[]){
int med;
if(first > last) /* caso in cui il vettore è terminato, ritorno il valore -1 ad indicare che l'elemento non esiste */
return -1;
else
{
med = (first + last)/2;
if (strcmp(tel, gente[med].telefono) == 0)
return med;
else
if (strcmp(tel,gente[med].telefono)>0) /* nel caso in cui tel sia più grande di gente[med] */
return ricerca_bin(gente,med+1,last,tel);
else
return ricerca_bin(gente,first,med-1,tel);
}
}

//*CORPO DEL PROGRAMMA*//
int main(void)
{
char ch;
int i,j,eta;
Persona p[SIZEV],buffer[SIZEV];
printf ("\n****INSERISCI CONTATTI NELLE RUBRICA*****\n");
caricaVettore(p,SIZEV);
printf ("\n************RUBRICA ORDINATA*************\n");
ordinaVettore(p,SIZEV);
stampaVettore(p,SIZEV);

/* ricerca binaria ricorsiva */
int idx;
char tel[50];
printf ("\n \n");
printf("Inserire il numero da cercare:");
scanf("%s", tel);
idx = ricerca_bin(p,0,SIZEV,tel);
if(idx == -1)
printf("Siamo spiacente, ma il numero selezionato non e' stato trovato \n");
else{
printf ("numero selezionato trovato: \b");
printf("\nNome:%s \nCognome:%s \nIndirizzo: %s\nTelefono':%s\n",p[idx].nome,p[idx].cognome,p[idx].indirizzo,p[idx].telefono);
}

system("PAUSE");
return 0;

}

con una normale stringa di caratteri funziona bene

bobbytre

25-02-2010, 00:18

a me sembra che va bene, che dati hai inserito quando lo hai provato e non ti ha funzionato ?

mariano89

25-02-2010, 00:22

il mio numero di casa, o anche 990 e 775.
Se inserisco ad esempio un num. 7 o una stringa tipo alba funziona invece:help:

bobbytre

25-02-2010, 00:24

posta un output del programma di quando ti da l'errore.

mariano89

25-02-2010, 00:29

non da un errore ma da semplicemente l'output
Siamo spiacente, ma il numero selezionato non e' stato trovato

bobbytre

25-02-2010, 00:32

è ovvio che se il numero della persona è 123456

devi cercare esattamente 123456 senza spazi ne altro

mariano89

25-02-2010, 00:33

infatti o provato così:boh:

bobbytre

25-02-2010, 00:41

scrivi esattamente quali dati hai inserito perchè cosi a occhio non vedo il problema

mariano89

25-02-2010, 00:46

Risolto, facendo svariati tentativi alla fine è andato. Sarà il dev non all'altezza. Ti ringrazio per la pazienza e la gentilezza offertami!!! :)
e scusami x il disturbo

bobbytre

25-02-2010, 00:50

figurati nessun disturbo :)

subpaco

25-02-2010, 12:00

Se vuoi un consiglio (che direi che potrai applicare nei prossimi programmi oramai :p) anche se il programma fa' cio' che deve fare io eviterei di usare strcpy senza i check sulla lunghezza delle stringhe ma SOPRATTUTTO eviterei di usare gets!!

Il programma incorrerebbe molto facilmente in segfault che non ti farebbero fare bella figura agli occhi del docente..Quindi direi meglio evitare :)

Ciao.