IALweb Homepage
Forum Home Forum Home > Programmazione > Programmazione > C/C++ - VISUAL C++
  New Posts New Posts RSS Feed - [AIUTO] Alberi binari di ricerca
  FAQ FAQ  Forum Search   Events   Register Register  Login Login


REGISTRATEVI su IALWeb forum!

Topic Closed[AIUTO] Alberi binari di ricerca

 Post Reply Post Reply
Author
Message
P_il_musicante View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 05/Giu/2007
Status: Offline
Points: 4
Direct Link To This Post Topic: [AIUTO] Alberi binari di ricerca
    Posted: 05/Giu/2007 at 18:22

Salve a tutti!!
devo testare la complessità dell'insert search tree_minimum e tree maximum
il mio problema
per imput di dimesione elevata la memoria virtuale viene allocata tutta tipo p per imput di dimensione pari a 9*10^6
lascio il codice:
albero.h


//Predichiarazione della struct
struct nodo;
struct albero;


//Dichiarazione del tipo puntatore a nodo
typedef struct nodo* tree;
//Dichiarazione del tipo puntatore ad albero
typedef struct albero* ABR;


//Dichiarazione del tipo strutturato nodo
struct nodo {
int key;
tree genitore;
tree sinistro;
tree destro;

};
//Dichiarazine del tipo strutturato albero
struct albero{
tree root;
};


//PROTOTIPI delle funzioni utilizzate

void inizializza_nodo(tree n);
void inizializza_root(ABR T);
void set_ABR_root(ABR T, tree n);

void Inorder(tree x);
void Preorder(tree x);
void Postorder(tree x);
tree Tree_successor(tree x);



tree RicercaBin(tree x,int x);
tree RicercaIterativaBin(tree x,int k);
tree RicercaMin(tree x);
tree RicercaMax(tree x);
void Inserimento(ABR T,tree z);
tree Tree_delete(ABR T, tree z);








albero.cpp

#include "albero.h"
#include <stdlib.h>
#include <iostream>

using namespace std;


void inizializza_nodo(tree n){
n->key=0;
n->genitore=NULL;
n->sinistro=NULL;
n->destro=NULL;
}
void inizializza_root(ABR T){
T->root=NULL;

}



void Inorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
Inorder(x->sinistro);
cout<<x->key<<" ";
Inorder(x->destro);
}
}

void Preorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
cout<<x->key<<" ";
Preorder(x->sinistro);
Preorder(x->destro);
}
}

void Postorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
Postorder(x->sinistro);
Postorder(x->destro);
cout<<x->key<<" ";
}
}

/*
trova {succ,prede}cessore del nodo x
output: puntatore {succ,prede}cessore
*/
tree Tree_successor(tree x){
if(x->destro!=NULL)
return RicercaMin(x->destro);

tree y=x->genitore;
while( y!=NULL && x==y->sinistro){
x=y;
y=y->genitore;
}
return y;
}

tree Tree_predecessor(tree x){
if(x->sinistro!=NULL)
return RicercaMax(x->sinistro);

tree y=x->genitore;
while( y!=NULL && x==y->destro){
x=y;
y=y->genitore;
}
return y;
}


tree RicercaBin(tree x,int k)
// Ricerca per alberi binari di ricerca
{
if ((x==NULL)||(k==x->key))
return x;
else {
if (k < x->key)
return RicercaBin(x->sinistro,k) ;
else
return RicercaBin(x->destro,k) ;
}
}

tree RicercaIterativaBin(tree x,int k)
// Ricerca iterativa per alberi binari di ricerca
{
while ((x!=NULL)&&(k!=x->key))
{
if (k < x->key)
x=x->sinistro;
else
x=x->destro;
}
return x;
}

tree RicercaMin(tree x)
// Ricerca del minimo per alberi binari di ricerca
{
while (x->sinistro!=NULL)
{
x=x->sinistro;
return x;
}
}

tree RicercaMax(tree x)
// Ricerca del massimo per alberi binari di ricerca
{
while (x->destro!=NULL)
{
x=x->destro;
return x;
}
}

void Inserimento(ABR T,tree z)
// Costruisce un albero binario di ricerca
{
//Puntatore al padre
tree Y=NULL;

tree X=T->root;
//tree X=T;
while (X!=NULL)
{
Y=X;
if ( z->key < X->key)
X=X->sinistro;
else
X=X->destro;
}
z->genitore=Y;

if (Y==NULL)
T->root=z;

else
if (z->key < Y->key)
Y->sinistro=z;
else
Y->destro=z;
z->sinistro=NULL;
z->destro=NULL;


}


/*
cancella un nodo dall'albero

*/
tree Tree_delete(ABR T, tree z){
tree x=NULL;
tree y=NULL;



if( z->sinistro==NULL || z->destro==NULL){
y=z;
}else{
y=Tree_successor(z);
}

if(y->sinistro!=NULL){
x=y->sinistro;
}else{
x=y->destro;
}

if(x!=NULL)
x->genitore=y->genitore;

if(y->genitore ==NULL){
T->root=x;
}else{
if( y==(y->genitore)->sinistro){
(y->genitore)->sinistro=x;
}else{
(y->genitore)->destro=x;
}
}

if (y!=z){
z->key=y->key;
z->genitore=y->genitore;
z->sinistro=y->sinistro;
z->destro=y->destro;
}


return y;
}











main.cpp

#include "albero.h"
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cstdlib>



using namespace std;


int main()
{

ABR T=new albero;
inizializza_root(T);
tree x=NULL;
tree found=NULL;
time_t t1,t2;
double media=0;
int dim;
int scelta;


do{
cout<<"\n SCEGLI LA FUNZIONE DI CUI VUOI TESTARE LA COMPLESSITA'";
cout<<"\n digita 1 per INSERT";
cout<<"\n digita 2 per SEARCH (ricorsiva)";
cout<<"\n digita 3 per SEARCH (iterativa)";
cout<<"\n digita 4 per uscire dal programma";
cout<<"\n ->";
cin>>scelta;
switch(scelta){
case 1:
cout<<"\n TEST INSERT";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;

media=0;
cout<<"\n";
for(int h=0;h<10;h++){
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);

x->key=rand();

if(i==0)
t1=time(NULL);
Inserimento(T,x);

//Inorder(x);
}
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<difftime(t2,t1);
cout<<"\n";
// devo inserire una funzione per liberare la memoria
cout<<"tempo per deallocare la memoria...\n\n";

media=media+difftime(t2,t1);
}

cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
cout<<"\n\n";

break;


case 2:
cout<<"\n TEST SEARCH";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;



cout<<"\n --------caso ricorsivo---------> \n";
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);

x->key=rand();

Inserimento(T,x);

}
//Inserisce l'elemento 1234567890
x=new nodo;
inizializza_nodo(x);
x->key=1234567890;
Inserimento(T,x);

media=0;
for(int h=0;h<10;h++){
t1=time(NULL);
found=RicercaBin(x,1234567890);
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<(long double)difftime(t2,t1);
cout<<"\n";
media=difftime(t2,t1)+media;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";

cout<<"\n\n";
break;


case 3:
cout<<"\n TEST SEARCH";
cout<<"\n test di complessita'";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;


cout<<"\n --------caso iterativo----------> \n";
x=new nodo;
inizializza_nodo(x);
x->key=1234567890;

Inserimento(T,x);
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);
x->key=rand();
Inserimento(T,x);
}
media=0;
for(int h=0;h<10;h++){
t1=time(NULL);
found=RicercaIterativaBin(x,1234567890);
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<(long double)difftime(t2,t1);
cout<<"\n";
media=difftime(t2,t1)+media;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";

cout<<"\n\n";
break;


case 4:

exit(0);
break;

}
}while((scelta>0)&&(scelta<5));

cout<<"\n Errore di digitazione \n";

cout<<"\n\n\n\n\n";





system("PAUSE");


}

ho utilizzato il C++
se è possibile utilizzare altri comandi per allocare la struttura tipo malloc (ke io nn so utilizzare) e free
aiutatemi please!!!!!
potreste consigliarmi come fare
GRAzie



Edited by MrHyde
Back to Top
Sponsored Links


Back to Top
MrHyde View Drop Down
Veterano
Veterano
Avatar

Joined: 03/Lug/2003
Location: ITALIA
Status: Offline
Points: 1197
Direct Link To This Post Posted: 05/Giu/2007 at 18:29

Ehm...

Innanzitutto formatta il codice utilizzando gli appositi tag CODE.

Proseguendo...

Quote

se è possibile utilizzare altri comandi per allocare la struttura tipo malloc (ke io nn so utilizzare) e free
aiutatemi please!!!!!

E' giusto l'utilizzo di new per allocare e di delete per deallocare dato che stai scrivendo in C++. (l'Operatore new non è altro che un malloc mascherato...)

In conclusione..

Qual'è l'esatta richiesta del post?

 

http://www.mrhyde.altervista.org/myblog.html
http://www.mrhyde.altervista.org
Back to Top
P_il_musicante View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 05/Giu/2007
Status: Offline
Points: 4
Direct Link To This Post Posted: 05/Giu/2007 at 18:34

mi servirebbe una funzione ke mi dealloki la memori poichè qnd mando in esecuzione il mio programma e inserisco una dimensione dell'imput superiore a 10^6 mi da errore della memoria virtuale (memory leak)

se pio darmi una mano ha scrivere il main per testare  la complessità delle funzioni di insert search e search min penso che il doppio new sia fato bene ???

puoi darmi qlke consiglio

 

GRAZIE

Back to Top
P_il_musicante View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 05/Giu/2007
Status: Offline
Points: 4
Direct Link To This Post Posted: 06/Giu/2007 at 15:29

Ho provato con queste funzioni ma nn ho risolto nulla aiutatemi!!!!!!

<CODE>
//Funzione ausiliaria: dealloca l'albero
void dealloca_nodo(ABR T,tree& x){
                             tree q;
                               q=x;
                             while(x!=NULL){
                                         x=Tree_delete(T,x);
                                         delete q;
                                        
                                         q=x;
                                            }
                                 
                            }

void dealloca_albero(ABR& T,tree x){
                             tree q;
                               q=T->root;
                             while(T!=NULL){
                                             dealloca_nodo( T, x);
                                          
                                             /*
                                         T->root=Tree_delete(T,x);
                                         delete q;                                         
                                         q=T->root;
                                         */
                                            }
                                            T->root=Tree_delete(T,x);
                                         delete q;                                         
                                         q=T->root;
                                 
                            }
</CODE>

Back to Top
MrHyde View Drop Down
Veterano
Veterano
Avatar

Joined: 03/Lug/2003
Location: ITALIA
Status: Offline
Points: 1197
Direct Link To This Post Posted: 06/Giu/2007 at 15:39

Scusa musicante, ma in questi giorni sono impegnatissimo e nonho tempo di debuggare il tuo codice.

Il discorso è che 1.000.000 di oggetti x 2 sono decisamente tantini. L'Heap che il tuo processo può sfruttare è strettamente legato alla macchina che utilizzi ed al sistema operativo.

La deallocazione di un nodo (o più nodi) non influisce al momento della creazione della struttura, e da quello che capisco,è proprio in quel momento che hai il problema.

Quanto occupa di memoria il tuo programma caricando un albero delle massime dimensioni che riesci ad ottenere?



Edited by MrHyde
http://www.mrhyde.altervista.org/myblog.html
http://www.mrhyde.altervista.org
Back to Top
P_il_musicante View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 05/Giu/2007
Status: Offline
Points: 4
Direct Link To This Post Posted: 06/Giu/2007 at 15:54
Ti kiedo io scusa e ti ringrazio per la tua disponibilità

MA Vorrei  riuscire a terminare questo elaborato il più presto possibile
se tu puoi consigliarmi una soluzione alternativa per il main basta ke riesca a testare la complessità delle suddette funzioni
GRAZIE

con un imput di dimensine di 1.000.000 il  mio programma occupa 232 MegaByte


Back to Top
MrHyde View Drop Down
Veterano
Veterano
Avatar

Joined: 03/Lug/2003
Location: ITALIA
Status: Offline
Points: 1197
Direct Link To This Post Posted: 06/Giu/2007 at 15:59

Quote

con un imput di dimensine di 1.000.000 il  mio programma occupa 232 MegaByte

E ci credo che la memoria virtuale si esaurisce, qui non è questione di delete!!!

Io credo che a partire da una certa quota dovresti fare delle stime, in base al tipo di complessità dell'algoritmo, senza obbligatoriamente allocare tutti gli oggetti.

Ovvero, tu sai il risultato per n valori. Una piccola proporzione e puoi rapportare il risultato ad un valore di input maggiore.

 

http://www.mrhyde.altervista.org/myblog.html
http://www.mrhyde.altervista.org
Back to Top
 Post Reply Post Reply
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 10.17
Copyright ©2001-2013 Web Wiz Ltd.

This page was generated in 0,063 seconds.