[C] Ricerca binaria in un ABR

[Xfree]

Ciao a tutti.
Ho fatto un piccolo esercizio che carica da file delle informazioni riguardanti i generi dei libri in un ABR e poi ricerca il genere nell'albero stesso,
solo che quest'ultima non c'è verso di farla funzionare.:mbe:
Mi da sempre "Non trovato", quindi come se il puntatore fosse sempre NULL,
ma non sono riuscito a capire perché.

Codice del programma

/*
Creazione di un albero binario con lettura informazioni da file e visita in ordine anticipato
e ricerca binaria. L'etichetta dei nodi è una stringa.
*/

#include <stdio.h>
#include <malloc.h>
#define MAX 50

struct nodo {
char inf[MAX];
struct nodo *sx;
struct nodo *dx;
};

struct tlibro{
char autori[MAX];
char titolo[MAX];
char tipologia[MAX];
};

struct nodo *albBin(void);
struct nodo *creaNodo(struct nodo *, char val[]);
void anticipato(struct nodo *);
void ricBin(char val[],struct nodo *);

main()
{
char cerca[MAX];
struct nodo *radice; /* puntatore alla radice dell'albero */
radice = albBin(); /* invoca la funzione per la creazione
dell'albero binario */
printf("\nVISITA IN ORDINE ANTICIPATO\n");
anticipato(radice);
printf("\nRICERCA BINARIA\n");
printf("Inserisci la stringa da cercare: ");
scanf("%s",&cerca);
ricBin(cerca,radice);
system("pause");
}


/* Crea l'albero binario. Per ogni etichetta immessa
dall'utente, invoca la funzione creaNodo.
Ritorna al chiamante la radice dell'albero */

struct nodo *albBin(void)
{
struct nodo *p = NULL;
struct tlibro libro;
FILE *fp;

fp=fopen("libri.txt","r");
if(fp==NULL)
printf("Si e' verificato un'errore nell'apertura del file\n");
else{
while(!feof(fp)){
fgets(libro.autori,MAX,fp);
fgets(libro.titolo,MAX,fp);
fgets(libro.tipologia,MAX,fp);
p=creaNodo(p,libro.tipologia);
//printf("%s",libro.autori);
//printf("%s",libro.titolo);
//printf("%s",libro.tipologia);
}
fclose(fp);
}
return(p); /* ritorna la radice */
}


/* Visita ricorsivamente l'albero alla ricerca del punto di
inserimento. Quando trova la posizione, crea un nodo, vi
inserisce l'etichetta e ritorna il puntatore a tale nodo.
Parametri in ingresso:
p e' il puntatore alla radice
val e' l'etichetta da inserire nel nodo */


struct nodo *creaNodo(struct nodo *p, char val[])
{
if(p==NULL) { /* il punto di inserimento e' stato reperito */
/* Creazione del nodo */
p=(struct nodo *) malloc(sizeof(struct nodo));
strcpy(p->inf,val); /* inserimento di val in elemento */
p->sx = NULL; /* marca di albero sinistro vuoto */
p->dx = NULL; /* marca di albero destro vuoto */
}
else{ /* ricerca del punto di inserimento */
if(strcmp(val,p->inf)>0){
/* Visita il sottoalbero destro */
p->dx = creaNodo(p->dx, val);
}
else{
/* Visita il sottoalbero sinistro */
p->sx = creaNodo(p->sx, val);
}
}
return(p); /* ritorna il puntatore alla radice */
}


/* Visita l'albero binario in ordine anticipato */

void anticipato(struct nodo *p)
{
if(p!=NULL) {

printf("%s",p->inf); /* visita la radice */
anticipato(p->sx); /* visita il sottoalbero sinistro */
anticipato(p->dx); /* visita il sottoalbero destro */
}
}

void ricBin(char val[],struct nodo *p)
{
if(p==NULL)
printf("Non trovato");
else if(strcmp(val,p->inf)==0)
printf("Trovato");
else if(strcmp(val,p->inf)<0)
ricBin(val,p->sx);
else
ricBin(val,p->dx);
}


File libri.txt

DANTE
LA DIVINA COMMEDIA
COMMEDIA
DESCARTES
DISCORSO SUL METODO
SAGGISTICA
UMBERTO ECO
IL NOME DELLA ROSA
LETTERATURA
JULES VERNE
20000 LEGHE SOTTO I MARI
FANTASCIENZA
NICK HORNBY
ALTA FEDELTA
ROMANZO

[labrosan]

Devi stare attento a due cose:

1)"CASA" è diverso da "casa".
Il tuo file libri.txt è scritto in maiuscolo, mentre un operatore probabilmente inserirà un nome minuscolo. Per fare il confronto usa la stricmp()

2)La fgets include anche il carattere '\n'.
"casa\n" è diverso da "casa", quindi devi tenerne conto

[Xfree]

Ok, grazie per le osservazioni.
Per il primo punto lo sapevo e l'ho deliberatamente lasciato così perché facendo le prove io già facevo la ricerca in maiuscolo; quella funzione comunque non la conoscevo per cui grazie.
Per il secondo punto quindi i nodi dell'albero binario contengono il '\n' mentre la stringa che immetto io non lo contiene, il problema nasce quindi da qui?

[labrosan]

Ho provato al volo con questa modifica e funziona.

while(!feof(fp)){
fgets(libro.autori,MAX,fp);
if (libro.autori[strlen(libro.autori)-1]=='\n')
libro.autori[strlen(libro.autori)-1]='\0';
fgets(libro.titolo,MAX,fp);
if (libro.titolo[strlen(libro.titolo)-1]=='\n')
libro.titolo[strlen(libro.titolo)-1]='\0';
fgets(libro.tipologia,MAX,fp);
if (libro.tipologia[strlen(libro.tipologia)-1]=='\n')
libro.tipologia[strlen(libro.tipologia)-1]='\0';

Ancora una osservazione: quando fai scanf("%s",&cerca), l'operatore & non devi metterlo poichè la stringa è gia passata per riferimento

Ciao Ciao

[Xfree]

:muro: Fatto come dici tu e funziona. :sofico:
Quindi il problema non era dell'algoritmo della ricerca binaria ma nel carattere di fine stringa che non essendo uguale tra l'informazione contenuta nell'etichetta dell'albero e quella acquisita da tastiera dava il risultato di non trovare mai nulla.
Approfitto della tua presenza per chiederti un'altra cosa:
se io volessi modificare il programma facendo in modo tale che l'albero binario sia ordinato per tipologia (e qui già è fatto così) ma con il vincolo che ogni nodo dell'albero binario deve contenere le informazioni dei libri della stessa tipologia organizzati nel seguente modo:
tipologia
lista dei libri della stessa tipologia

e per ogni libro sono memorizzati
autori
titolo del libro.

Per lista io ho capito che si intende lista nel senso di struttura dati dinamica, quindi all'interno del nodo dell'albero ci dovrebbe essere puntatore ad una lista
del tipo

struct lista{
char autori[MAX];
char titolo[MAX];
struct lista *next;
}


e quindi poi gestire il tutto con le operazioni proprie delle liste, giusto?

[labrosan]

Ok