[C] Ricerca binaria

di il
3 risposte

[C] Ricerca binaria

Salve, sono un ragazzo di terza superiore. Potreste aiutarmi, sto trovando qualche problema nella funzione cerca.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 120

typedef struct{
	int gg; int mm; int aa;
	char nome[30];
	char cognome[30];
	int matricola;
}TDati;

//PROTOTIPO
void legge(TDati v[],int *n);
int conta(TDati v[],int n);
void cerca(TDati v[],int n);
void ordina(TDati v[],int n);
void visualizza(TDati v[],int n);
void menu();

//MAIN
int main() {
	TDati v[NMAX];
	int n=0,a;
	
	do{
		do{
			menu();
			printf("\nQuale scegli? ");
			scanf("%d",&a);
			printf("\n-------------------\n");
			switch(a) {
				case 1: legge(v,&n); break;
				case 2: 
						if(n==0) {
						    printf("\nCarica i dati!\n");
					    }else{
					    	conta(v,n);
					    }
					   
					    break;
				case 3: 
						if(n==0) {
						    printf("\nCarica i dati!\n");
					    }else{
					    	cerca(v,n);
					    }
					   
					    break;
				case 4: 
				     	if(n==0) {
						    printf("\nCarica i dati!\n");
					     }else{
					    	visualizza(v,n);
					     }
					   
					    break;
			}
		}while(a<1 || a>5);
	}while(a!=5);
	
	return 0;
}

//IMPLEMENTAZIONE DELLE FUNZIONI
//LEGGE
void legge(TDati v[],int *n) {
	 int i;
	 char r[100]; 
 	 char da[11], no[31], co[31], ma[7];
 	 char gg[3], mm[3], aa[5];
 	 FILE *fp;
 	 
     fp=fopen("prenotazioni.txt","r");
     i=0;
     while(!feof(fp)){
     	fgets(r,100,fp);
		sscanf(r,"%[^';'];%[^';'];%[^';'];%[^'\n']",da,no,co,ma);
		strcpy(v[i].cognome,co);
		strcpy(v[i].nome,no);
		v[i].matricola=atoi(ma);
		sscanf(da,"%[^'/']/%[^'/']/%[^'\0']",gg,mm,aa);
		v[i].gg=atoi(gg);
		v[i].mm=atoi(mm);
		v[i].aa=atoi(aa);
		i++;
 	}
 	fclose(fp);
 	*n=i;
}

//CONTA
int conta(TDati v[],int n) {
	int i,cnt=0,grn,mes,ann;
	
	printf("\nQuale giorno? ");
	scanf("%d",&grn);
	printf("Quale mese? ");
	scanf("%d",&mes);
	printf("Quale anno? ");
	scanf("%d",&ann);
	
	for(i=0;i<n;i++) {
		if((grn==v[i].gg) && (mes==v[i].mm) && (ann==v[i].aa)) 
			cnt++;
	}
	
	if(cnt!=0) {
		printf("\nNumero studenti prenotati: %d\n",cnt);
    }else{
    	printf("\nNessuno studente prenotato\n");
    }
}

//ORDINA
void ordina(TDati v[],int n) {
	TDati t; 
	int i,j;
	
	 for(i=0;i<n-1;i++)
 		for(j=i+1;j<n;j++)
			 if(v[i].matricola>v[j].matricola) {
 				t=v[i];
			    v[i]=v[j];
			    v[j]=t;
             }	
}

//CERCA
void cerca(TDati v[],int n) {
	int j,ctr=0,cmd;
	int pf=n-1, pi=0, pm;
	
	ordina(v,n);
	
	printf("\nInserisci codice matricola: ");
	scanf("%d",&cmd);
	
	pm=(pf-pi)/2;
	do{
		if(cmd==v[pi].matricola) {
			j=pi;
		}
		if(cmd==v[pf].matricola) {
			j=pf;
		}
		if(cmd==v[pm].matricola) {
			j=pm;
		}
		if(cmd>v[pm].matricola) {
			pi=pm+1;
			pm=pi+(pf-pi)/2;
			j=pm;
		}			 
		if(cmd<v[pm].matricola) {
			pf=pm-1;
			pm=pi+(pf-pi)/2;
			j=pm;
		}	
	}while(pf>pi);
	
    printf("\nNome: %s\n",v[j].nome);
    printf("Cognome: %s\n",v[j].cognome);
    printf("Prenotazione: %d/%d/%d\n",v[j].gg,v[j].mm,v[j].aa);

}

//MENU
 void menu() {
 	printf("\n-------------------\n");
	printf("1- Legge\n");
	printf("2- Conta\n");
	printf("3- Cerca\n");
	printf("4- Visualizza\n");
	printf("5- FINE");
	printf("\n-------------------\n");
}

//VISUALIZZA
void visualizza(TDati v[],int n) {
	int i;
	
	for(i=0;i<n;i++) {
	printf("\n---------------------------\n");
	printf("\nNome: %s\n",v[i].nome);
	printf("Cognome: %s\n",v[i].cognome);
    printf("Codice matricola: %d\n",v[i].matricola);
    printf("Prenotazione: %d/%d/%d\n",v[i].gg,v[i].mm,v[i].aa);
    printf("\n---------------------------\n");
	}
	
}

Allegati:
21383_7d1bc31765ddbc90fc19a9dc4e618db0.pdf
21383_7d1bc31765ddbc90fc19a9dc4e618db0.pdf

3 Risposte

  • Re: [C] Ricerca binaria

    wrugg25 ha scritto:


    Sempre lo stesso discorso, ad ogni richiesta:

    1 - Qual è il tuo problema?
    2 - Quali sono i risultati del debug?
    3 - Cosa dovresti ottenere? Cos'hai ottenuto invece?
    4 - Dov'è il file su cui far lavorare il programma? Tu non lo hai linkato.

    Se non fornite le informazioni, occorre più tempo (e volontà) per aiutarvi... io lo dico per voi


    Comunque...

    Il codice è scritto malissimo:

    1 - Quando hai più condizioni mutuamente esclusive da verificare (vedesi la funzione CERCA), si usa il costrutto ELSE IF, non si mettono cinque-sei if di fila in quel modo.
    2 - La funzione CONTA è dichiarata di tipo int, ma non ritorna un valore.
    3 - I nomi delle variabili sono osceni: DA, NO, CO, MA? Che c***o sono? Come si legge un codice del genere?
    4 - Quella roba che hai usato come format delle sscanf è formattata malissimo: qualche spaziatura non avrebbe fatto male... inoltre, puoi tranquillamente sostituire il %[^'\n'] finale con un normalissimo %s.
    5 - Perchè usare variabili stringa e convertirle con atoi, quando si potrebbero usare variabili intere?
    6 - La condizione del while di ricerca è sbagliata: se lo studente cercato non è nè il primo nè l'ultimo, il ciclo continua all'infinito. Occorre aggiungere un else if (vedi punto 1) che faccia verificare la condizione nel caso in cui lo studente viene trovato con l'indice pm (o, più opportunamente, occorre modificare la condizione).
    7 - Il codice non è adeguatamente commentato.


    Questo è il tuo codice scritto in maniera almeno decente (commenti a parte: ti ho commentato solo le parti che ho modificato):
    
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define NMAX 120
    
    typedef struct {
    	int gg; int mm; int aa;
    	char nome[30];
    	char cognome[30];
    	int matricola;
    }TDati;
    
    //PROTOTIPO
    void legge(TDati v[], int *n);
    int conta(TDati v[], int n);
    void cerca(TDati v[], int n);
    void ordina(TDati v[], int n);
    void visualizza(TDati v[], int n);
    void menu();
    
    //MAIN
    int main() {
    	TDati v[NMAX];
    	int n = 0, a, cnt;
    
    	do {
    		do {
    			menu();
    			printf("\nQuale scegli? ");
    			scanf("%d", &a);
    			printf("\n-------------------\n");
    			switch (a) {
    			case 1: legge(v, &n); break;
    			case 2:
    				if (n == 0) {
    					printf("\nCarica i dati!\n");
    				}
    				else {
    					cnt = conta(v, n);        /*FINALMENTE VIENE RICEVUTO UN VALORE DA CONTA*/
    					if (cnt != 0) {
    						printf("\nNumero studenti prenotati: %d\n", cnt);
    					}
    					else {
    						printf("\nNessuno studente prenotato\n");
    					}
    				}
    
    				break;
    			case 3:
    				if (n == 0) {
    					printf("\nCarica i dati!\n");
    				}
    				else {
    					cerca(v, n);
    				}
    
    				break;
    			case 4:
    				if (n == 0) {
    					printf("\nCarica i dati!\n");
    				}
    				else {
    					visualizza(v, n);
    				}
    
    				break;
    			}
    		} while (a<1 || a>5);
    	} while (a != 5);
    
    	return 0;
    }
    
    //IMPLEMENTAZIONE DELLE FUNZIONI
    //LEGGE
    void legge(TDati v[], int *n) {
    	/*QUI HO MIGLIORATO LA LEGGIBILITÀ DI QUELLO SCHIFO CHE AVEVI SCRITTO E DATO AD OGNI VARIABILE IL GIUSTO TIPO*/
    
    	int i, matricola, gg, mm, aa;
    	char str[100];
    	char data[11], nome[31], cognome[31];
    	FILE *fp;
    
    	fp = fopen("prenotazioni.txt", "r");
    	i = 0;
    	while (!feof(fp)) {
    		fgets(str, 100, fp);
    		sscanf(str, "%[^';'] ; %[^';'] ; %[^';'] ; %d", data, nome, cognome, &matricola);
    		strcpy(v[i].cognome, cognome);
    		strcpy(v[i].nome, nome);
    		v[i].matricola = matricola;
    		sscanf(data, "%d / %d / %d", &gg, &mm, &aa);
    		v[i].gg = gg;
    		v[i].mm = mm;
    		v[i].aa = aa;
    		i++;
    	}
    	fclose(fp);
    	*n = i;
    }
    
    //CONTA
    int conta(TDati v[], int n) {
    	int i, cnt = 0, grn, mes, ann;
    
    	printf("\nQuale giorno? ");
    	scanf("%d", &grn);
    	printf("Quale mese? ");
    	scanf("%d", &mes);
    	printf("Quale anno? ");
    	scanf("%d", &ann);
    
    	for (i = 0; i<n; i++) {
    		if ((grn == v[i].gg) && (mes == v[i].mm) && (ann == v[i].aa))
    			cnt++;
    	}
    	return cnt; /*ORA FINALMENTE LA FUNZIONE RITORNA UN VALORE*/
    }
    
    //ORDINA
    void ordina(TDati v[], int n) {
    	TDati t;
    	int i, j;
    
    	for (i = 0; i<n - 1; i++)
    		for (j = i + 1; j<n; j++)
    			if (v[i].matricola>v[j].matricola) {
    				t = v[i];
    				v[i] = v[j];
    				v[j] = t;
    			}
    }
    
    //CERCA
    void cerca(TDati v[], int n) {
    	/*ORA IL CICLO SI INTERROMPE SE PF<=PI, OVVERO A FINE SCANSIONE, O SE J>0, OVVERO SE LA SOLUZIONE VIENE TROVATA*/
    	int j = -1, ctr = 0, cmd; 
    	int pf = n - 1, pi = 0, pm;
    
    	ordina(v, n);
    
    	printf("\nInserisci codice matricola: ");
    	scanf("%d", &cmd);
    
    	pm = (pf - pi) / 2;
    	do {
    		/*TI HO CORRETTO I COSTRUTTI CONDIZIONALI.*/
    		if (cmd == v[pi].matricola) {
    			j = pi;
    		}
    		else if (cmd == v[pf].matricola) {
    			j = pf;
    		}
    		else if (cmd == v[pm].matricola) {
    			j = pm;
    		}
    		else if (cmd>v[pm].matricola) {
    			pi = pm + 1;
    			pm = pi + (pf - pi) / 2;
    			j = pm;
    		}
    		else if (cmd<v[pm].matricola) {
    			pf = pm - 1;
    			pm = pi + (pf - pi) / 2;
    			j = pm;
    		}
    	} while (pf>pi && j < 0);
    
    	printf("\nNome: %s\n", v[j].nome);
    	printf("Cognome: %s\n", v[j].cognome);
    	printf("Prenotazione: %d/%d/%d\n", v[j].gg, v[j].mm, v[j].aa);
    
    }
    
    //MENU
    void menu() {
    	printf("\n-------------------\n");
    	printf("1- Legge\n");
    	printf("2- Conta\n");
    	printf("3- Cerca\n");
    	printf("4- Visualizza\n");
    	printf("5- FINE");
    	printf("\n-------------------\n");
    }
    
    //VISUALIZZA
    void visualizza(TDati v[], int n) {
    	int i;
    
    	for (i = 0; i<n; i++) {
    		printf("\n---------------------------\n");
    		printf("\nNome: %s\n", v[i].nome);
    		printf("Cognome: %s\n", v[i].cognome);
    		printf("Codice matricola: %d\n", v[i].matricola);
    		printf("Prenotazione: %d/%d/%d\n", v[i].gg, v[i].mm, v[i].aa);
    		printf("\n---------------------------\n");
    	}
    
    }
    

    STUDIALO.


    A proposito, che libro usate per studiare 'ste cose? Per provare a capire se i tuoi problemi nella scrittura del codice derivano dal libro, dal docente o da te stesso.

    Ok, grazie mille per l'aiuto. Ho adottato i tuoi suggerimenti, e sicuramente funziona meglio di prima, ma purtroppo mi da ancora qualche errore. Quando inserisco i codici matricola centrali mi da il nome della matricola finale (Mario Rossini). Forse è il problema è nel j<0, poichè viene assegnato un valore ma non ripete la ricerca dicotomica perché j!=0. Sottolineo il forse.

    Il nostro libro è PAOLO CAMAGNI, RICCARDO NIKOLASSY - Informatica in C e C++ - Per il terzo anno degli Istituti Tecnici settore Tecnologico articolazione INFORMATICA.
    Allegati:
    21383_57543bdb839f36d6b41855bd4510f371.pdf
    21383_57543bdb839f36d6b41855bd4510f371.pdf
  • Re: [C] Ricerca binaria

    Ho tolto j=pm negli ultimi due else if, ma continua a darmi lo stesso errore. Mi spiego meglio. Se nella cerca inserisco il codice matricola 127756 (Antonio Luigi Verdi) o 132588 (Margherita Gialli) mi da come risultato Mario Rossi (123456). Da cosa potrebbe esser dovuto?

    P.S. Grazie per i numerosi consigli. Comunque il debug, purtroppo, è soltanto qualcosa sentito nominare. Vorra' dire che rimedierò con le guide che mi hai fornito.

    Ah, come compilatore utilizziamo Dev-C
  • Re: [C] Ricerca binaria

    Funziona, tutto perfetto. Grazie mille
Devi accedere o registrarti per scrivere nel forum
3 risposte