PDA

Visualizza la versione completa : [C] alberi binari..problemi con funzione ricerca minimo e massimo


SSSS90
20-05-2014, 21:53
Il seguente codice permette di fare quanto segue:

Inserendo da tastiera uno alla volta dei valori interi:
Inserisci numero:1
Inserisci numero:0
Inserisci numero:2
a)Ordina la sequenza:
0 1 2
b)Ricerca un valore:
Inserire un numero: 4
Valore non presente!(Dopo aver stampato questo messaggio il programma mi si blocca)
c)Ricerca Min max della sequenza(Le funzioni non partono proprio,in quanto il programma si blocca)

Qualche consiglio?



#include<stdio.h>
#include<stdlib.h>
struct TInfo{
int num;
};
struct Nodo{
TInfo info;
struct Nodo *destro;
struct Nodo *sinistro;
};
typedef struct Nodo TNodo;
typedef struct Nodo* Albero;
Albero Crea_Albero();
void Distruggi_Nodo(TNodo *nodo);//??//
Albero Inserisci_Elemento(Albero bt,TInfo info);
TInfo Leggi_Info();
Albero Distruggi_Albero(Albero bt);
TNodo *Ricerca(Albero bt,TInfo info);
TNodo *Cerca_Minimo(Albero bt);
TNodo *Cerca_Massimo(Albero bt);
void Stampa_Info(TInfo info);
void Stampa_Albero(Albero bt);

int main(){
Albero bt;/*Rappresenta l'albero binario*/
TInfo info;/*Serve per leggere gli elementi*/
int i,dim;/*Serve per chiedere più elementi*/
TNodo *search,*min,*max;
bt=Crea_Albero();
printf("Quanti elementi vuoi inserire?");
scanf("%d",&dim);
for(i=0;i<dim;i++){
info=Leggi_Info();
bt=Inserisci_Elemento(bt,info);
}
/*STAMPA DELL'ALBERO*/
printf("Elementi dell'albero:");
Stampa_Albero(bt);
/*RICERCA ELEMENTO*/
printf("\n\nRicerca elemento\n");
info=Leggi_Info();
search=Ricerca(bt,info);
if(search==NULL)
printf("Elemento non presente!\n");
else
printf("Elemento presente!\n");
/*RICERCA MINIMO*/
min=Cerca_Minimo(bt);
/*RICERCA MASSIMO*/
max=Cerca_Massimo(bt);

printf("\n\nMinimo:\n");
Stampa_Info(min->info);
printf("\nMassimo:\n");
Stampa_Info(max->info);
printf("\n\n");




system("pause");
return 0;
}










Albero Crea_Albero(){/*Crea un albero vuoto*/
return NULL;
}

void Distruggi_Nodo(TNodo *nodo){
free(nodo);/*Deallocazione dimanica nodo*/
}
TInfo Leggi_Info(){
TInfo info;/*creazione di un tipo TInfo*/
printf("Inserisci numero:");
scanf("%d",&info.num);
return info;
}
Albero Inserisci_Elemento(Albero bt,TInfo info){
if(bt==NULL){/*opzioni che si verificano se il nodo 3è vuoto*/
TNodo *nuovo_nodo;
nuovo_nodo=(TNodo*)malloc(sizeof(TNodo));
nuovo_nodo->info=info;
nuovo_nodo->destro=NULL;/*pongo a null perchè l'albero al momento è vuoto*/
nuovo_nodo->sinistro=NULL;
if(nuovo_nodo==NULL){
printf("Errore di allocazione in memoria!\n");
exit(1);
}
return nuovo_nodo;}
/* se il nodo non e' vuoto*/
else if(info.num<bt->info.num){ /* se l'informazione contenuta nel primo nodo radice bt
è maggiore del numero che voglio inserire...quindi i confronti
vengo fatti due per volta,i valori non sono contenuti già tutt
nella struttura come pensavo.
/*se è vero l'else if devo lavorare nel sottoalbero sinistro,perchè
è sottinteso che l'albero sia in ordine e a sinistra della radice ci sono gli elementi più piccoli*/
bt->sinistro=Inserisci_Elemento(bt->sinistro,info);
return bt;
}
else{
bt->destro=Inserisci_Elemento(bt->destro,info);
return bt;
}
}

void Stampa_Info(TInfo info){
printf("%d ",info.num);
}
void Stampa_Albero(Albero bt){
if(bt!=NULL){
Stampa_Albero(bt->sinistro);
Stampa_Info(bt->info);
Stampa_Albero(bt->destro);
}
}
Albero Distruggi_Albero(Albero bt){
/*Caso base:Albero vuoto o con un solo elemento*/
if(bt==NULL)
return NULL;

else if((bt->sinistro==NULL)&&(bt->destro==NULL)){
free(bt);
return NULL;
}else{
/*Divide et impera*/
bt->sinistro=Distruggi_Albero(bt->sinistro);
/*Divide et impera*/
bt->destro=Distruggi_Albero(bt->destro);
/*Combina*/
Distruggi_Albero(bt);
return NULL;
}
}


TNodo *Ricerca(Albero bt,TInfo info){
/*Caso base:albero vuoto o la radice coincide
con l'elemento che cerchiamo*/
if((bt==NULL) || (bt->info.num==info.num))/*caso banale:albero vuoto oppure l'informazione
contenuta nell'elemento radice bt->info e' uguale
all'elemento che stiamo cercando(che culo)*/
return bt;
else{
/*Dobbiamo verificare se l'elemento che stiamo cercando è meaggiore o minore
dell'elemento contenuto nel nodo che stiamo visitando*/
if(info.num >bt->info.num)/*Se il valore dell'elemento che vogliamo cercare info.num
e' maggiore della radice che stiamo cercando bt->info.num*/

return Ricerca(bt->destro,info);
else
return Ricerca(bt->sinistro,info);
}
}
TNodo *Cerca_Minimo(Albero bt){
/*Caso base:Albero vuoto*/
if(bt=NULL)
return NULL;
else if(bt->sinistro==NULL)
return bt;
else{
Albero min=Cerca_Minimo(bt->destro);
return min;
}
}
TNodo *Cerca_Massimo(Albero bt){
/*Caso base:Albero vuoto*/
if(bt=NULL)
return NULL;
else if(bt->destro==NULL)
return bt;
else{
Albero max=Cerca_Massimo(bt->destro);
return max;
}
}

shodan
20-05-2014, 22:00
Occhio a:


if(bt=NULL)

sia in Cerca_Minimo() sia in Cerca_Massimo();

SSSS90
20-05-2014, 22:17
grz

if(bt==NULL).

inoltre nelle funzione minimo:

Albero min=Cerca_Minimo(bt->sinistro);:unz::unz::unz::unz:

SSSS90
21-05-2014, 09:29
Salve ho un'altra perplessità sulla funzione ricerca minimo,l'istruzione:

Albero min=Cerca_Minimo(bt->destro);è una chiamata ricorsiva che restituisce:

Albero min..non saarebbe più corretto scrivere:

min=Cerca_Minimo(bt->destro)?
in più non capisco perchè la funzione necessita del simbolo di puntatore,

TNodo *Cerca_Minimo(Albero bt);...
perdonatemi per la profonda ignoranza ma è la prima volta che mi trovo di fronte a questi casi..:confused:

SSSS90
22-05-2014, 17:19
Salve ho risolto da solo i dubbi precedenti..ma ora studiando più da vicino la funzione cerca minimo mi è sorta qualche perplessità:
quando invoco nel main:

min=Cerca_Minimo(bt); passo alla funzione l'albero binario:ora supporniamo che il nostro albero binario sia formato da 2 3 4 7..passando alla definizione della funziione:
saltando il caso di albero vuoto bt=NULL
nel codice
else if(bt->sinistro==NULL) chi è bt->sinistro tra i nodi 2 3 4 7?L'abero viene analizzato dal primo valore,o come riportato su vari testi dalla radice..se si qual è la radice?:dhò::dhò::dhò::dhò:

SSSS90
22-05-2014, 21:02
qualche idea?

Loading