Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 14
  1. #1

    [AIUTO] alberi binari di ricarca

    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");


    }

  2. #2
    Moderatore di Programmazione L'avatar di alka
    Registrato dal
    Oct 2001
    residenza
    Reggio Emilia
    Messaggi
    24,288

    Moderazione

    Che linguaggio? Letto il Regolamento?
    MARCO BREVEGLIERI
    Software and Web Developer, Teacher and Consultant

    Home | Blog | Delphi Podcast | Twitch | Altro...

  3. #3
    ho utilizzato il C++
    se è possibile utilizzare altri comandi per allocare la struttura tipo malloc (ke io nn so utilizzare) e free
    aiutatemi please!!!!!

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

    codice:
     
    //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; 
    
                               }
    con un input di dimensine di 1.000.000 il mio programma occupa 232 MegaByte
    ho provato ha creare con l'operatore new la struttura nodo fuori dal ciclo for
    o vabene con il new all'interno del ciclo for o il new all'esterno
    mi serve una funzione ke dealloki la memoria . voi avete usato malloc ??? come funziona????


    codice:

    codice:
                                x=new nodo[dim];
                               T=new albero;
                               inizializza_root(T);
                              
                               
                               media=0;
                               cout<<"\n";
                               for(int h=0;h<10;h++){
                                  //Crea l'albero di dim elementi
                                  for (int i=0;i<dim;i++){
                                     
                                      
                                      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";
    GRazie

  5. #5

    Re: [AIUTO] alberi binari di ricarca

    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;


    }
    Ciao per motivi di tempo non ho letto tutto il tuo codice, mi sono solo soffermato sulla funzione inserimento dove pero non vedo l allocazione dinamica della memoria per un nuovo nodo....
    Codice PHP:
    void insertTree(tree ** Ptr,char buffer// Inserimento nell albero, funzione ricorsiva             
    {
     
     
    /* Caso base */
     
     
    if((*Ptr)==NULL)
      {
       
    CreateNode(Ptr);
       (*
    Ptr)->Comando=(char *)calloc(strlen(buffer)+1,sizeof(char));
       
    strcpy((*Ptr)->Comando,buffer);
        return;
       }
     
     
    /* Comando>buffer --> vado a sinistra*/
     
    if(strcmp((*Ptr)->Comando,buffer)>0)
      {
        
    insertTree(&((*Ptr)->left),buffer);
        return;
       }
      
     
    /* Comando<buffer --> vado a destra*/
     
    else
      {
      
    insertTree(&((*Ptr)->right),buffer);
       
      return;
       
      }
     
     
    }  
    /* FINE insertTree */

    /* Crea un nodo */
    void CreateNode(tree ** dp)
    {
     (*
    dp)=(tree*)malloc(sizeof(tree));
     (*
    dp)->left=NULL;
     (*
    dp)->right=NULL;
    /* FINE CreateNode*/ 
    Ti posto parzialmente quello su cui sto lavorando io, bada che cosi come è l albero sarà creato in maniera sbilanciata. In ogni caso spero che la traccia ti serva un po...



  6. #6
    GRazie
    l'allocazione la faccio nel main il mio problema è dato dalla deallocazione

    ho provato due modi divesi per allocare(stanno scritti sopra) però essendo un suer princiapiante della rpog nn sn sicuro
    potreste consigliarmi
    HElp!!!

  7. #7
    Ciao
    sn riuscito a scrivare una funzione per la deallo cazione
    adesso il mio problema e il test di cmplessità si ricerca in tutti i casi mi restitisce sempre zero come valore

    Codice:

    codice:
    cout<<"\n TEST SEARCH_min";
                               cout<<"\n test di complessita' ";
                               cout<<"\n inserisci la dimensione dell'input ->";
                               cin>>dim;
                               
                              inizializza_root(T);
                                  //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++){ 
                                      clk1=clock();
                                      found=RicercaMin(x);
                                      clk2 = clock();
                                                
                                  cout<<"tempo della "<<h+1<<" prova: ";
                                  
                                  double tempo_trascorso = ( double)(clk2-clk1)/CLOCKS_PER_SEC;
                                  
                                  cout<<tempo_trascorso;
                                  cout<<"\n";
                                  media=media+tempo_trascorso;
                                                            
                               }
                               
                               cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
                               cout<<"tempo per deallocare la memoria...\n\n";
                                
                               dealloca_nodo( T->root);
                               cout<<"\n\n";
                               break;

    cm mai ???
    forse creo un albero sbilanciato e il lminimo sta nella radice????
    devo scrivere una funzione ke mi ordini l'albero????


  8. #8
    Originariamente inviato da P_il_musicante
    Ciao
    sn riuscito a scrivare una funzione per la deallo cazione
    adesso il mio problema e il test di cmplessità si ricerca in tutti i casi mi restitisce sempre zero come valore

    Codice:

    codice:
    cout<<"\n TEST SEARCH_min";
                               cout<<"\n test di complessita' ";
                               cout<<"\n inserisci la dimensione dell'input ->";
                               cin>>dim;
                               
                              inizializza_root(T);
                                  //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++){ 
                                      clk1=clock();
                                      found=RicercaMin(x);
                                      clk2 = clock();
                                                
                                  cout<<"tempo della "<<h+1<<" prova: ";
                                  
                                  double tempo_trascorso = ( double)(clk2-clk1)/CLOCKS_PER_SEC;
                                  
                                  cout<<tempo_trascorso;
                                  cout<<"\n";
                                  media=media+tempo_trascorso;
                                                            
                               }
                               
                               cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
                               cout<<"tempo per deallocare la memoria...\n\n";
                                
                               dealloca_nodo( T->root);
                               cout<<"\n\n";
                               break;

    cm mai ???
    forse creo un albero sbilanciato e il lminimo sta nella radice????
    devo scrivere una funzione ke mi ordini l'albero????

    Uhm bhe,

    se crei un BST semplice è probabile che risulti sbilanciato. Se ti interessa avere l albero bilanciato proca con gli alberi AVL che sono bilanciati tramite rotazioni. Io ci sto sbattendo la testa da 2-3 giorni, le rotazioni fanno un po impazzire...

  9. #9
    Originariamente inviato da P_il_musicante
    Ciao
    sn riuscito a scrivare una funzione per la deallo cazione
    adesso il mio problema e il test di cmplessità si ricerca in tutti i casi mi restitisce sempre zero come valore

    Codice:

    codice:
    cout<<"\n TEST SEARCH_min";
                               cout<<"\n test di complessita' ";
                               cout<<"\n inserisci la dimensione dell'input ->";
                               cin>>dim;
                               
                              inizializza_root(T);
                                  //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++){ 
                                      clk1=clock();
                                      found=RicercaMin(x);
                                      clk2 = clock();
                                                
                                  cout<<"tempo della "<<h+1<<" prova: ";
                                  
                                  double tempo_trascorso = ( double)(clk2-clk1)/CLOCKS_PER_SEC;
                                  
                                  cout<<tempo_trascorso;
                                  cout<<"\n";
                                  media=media+tempo_trascorso;
                                                            
                               }
                               
                               cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
                               cout<<"tempo per deallocare la memoria...\n\n";
                                
                               dealloca_nodo( T->root);
                               cout<<"\n\n";
                               break;

    cm mai ???
    forse creo un albero sbilanciato e il lminimo sta nella radice????
    devo scrivere una funzione ke mi ordini l'albero????

    Ciao potresti postare il codice per la deallocazione per piacere???te ne sarei molto grata!!!
    Ciao

  10. #10
    Ciao
    postami tutto il tuo codice del proggetto!!!
    ma anke tu devi fare l'esame di asd????

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.