PDA

Visualizza la versione completa : [C++] albero di void


bako
07-04-2005, 19:54
volevo fare un albero di puntatori a void. ora, l'inserimento va, cioè nn da errori, ma secondo me nn salva nulla, la stampa invece nn so come implementarla..



tree.h

#ifndef TREE_H
#define TREE_H
struct nodo;

typedef nodo * tree;
typedef void * elemento ;

struct nodo{
elemento item;
tree left;
tree right;
};

void init(tree & );
int inserisci(tree &,elemento );
void stampa(tree );

#endif




tree.cpp
using namespace std;
#include <iostream>
#include "tree.h"

void init(tree & t){
t = NULL;
}

int inserisci(tree & t,elemento it){
elemento e;
if (t==NULL){
t=new nodo;
if (t==NULL) return 0;
}
else {
if (t->item==NULL) {
e = new elemento;
if (e==NULL) return 0;
e=it;
t->item=e;
t->left=NULL;
t->right=NULL;
}
else if (it>t->item) return inserisci (t->right,it);
else return inserisci (t->left,it);
}
}

void stampa(tree t){
if (t!=NULL){
stampa(t->left);
cout << (int)t->item << endl;

stampa(t->right);
}
}




main.cpp
using namespace std;
#include <iostream>
#include "tree.h"


int main(){
tree t;
int ele;
init(t);
ele=100;
inserisci(t,&ele);
stampa(t);
return 1;
}

MMarzia
07-04-2005, 22:50
nel titolo della discussione bisogna indicare il linguaggio utilizzato, come da regolamento (http://forum.html.it/forum/showthread.php?threadid=762409)

bako
07-04-2005, 22:55
a si lo sapevo bem ma mi son dimenticato .. se puoi (e vuoi) cambialo tu!

anx721
08-04-2005, 13:47
Questa dovrebbe essere corretta:



int inserisci(tree & t, elemento it){
if (t == NULL){
t = new nodo;
t -> item = it;
return 1;
}
if(it > t -> item)
return inserisci(t -> right,it);
if(it < t -> item)
return inserisci(t -> left,it);
return 1;
}


Nota che poichè gli elementi sono di tipo void *, facendo i confronti stai semplicemente confrontatno di puntatori, non i valori puntati, il che non ha molto senso. Per fare queste funzioni generiche hai bisogno di passare tra gli argomenti anche una funzione di confronto che fa il confronto vero e proprio e che sarà implementata diversamente di volta in volta in base al tipo effettivo degli elementi. Lo stesso vale per la stampa. La funzione dovrebbe allora essere:



int inserisci(tree & t, elemento it, int (*confronta)(void *, void *)){
if (t == NULL){
t = new nodo;
t -> item = it;
return 1;
}
if(confronta(it, t -> item) == 1)
return inserisci(t -> right,it);
if(confronta(it, t -> item) == -1)
return inserisci(t -> left,it);
return 1;
}


il paramentro "confronta" è un puntatore ad una funzione che prende due void* e restituisce 1, -1 o zero rispettivamente se il primo è maggiore, minore o uguale al secondo. Cosi ad esempio, se fai un albero di interi puoi definire una funzione



int confronta_interi(void * a, void * b){
if(*a > *b)
return 1;
if(*a < *b)
return -1;
return 0;
}


e poi chiamare la funzione di inserimento cosi:

inserisci(t, it, confronta_interi);

se invece fai un albero di puntatori ad un altro tipo di oggetti, ad esempio delle stringhe che vanno confrontate lessicograficamente, devi definire una funzione confronta_stringhe da passare ad inserisci. Analogamente devi creare delle funzioni diverse per la stampa di un singolo elemento, ad esempio stampa_intero o stampa_stringhe, e che saranno passate come parametro alla funzione di stampa dell'albero.

bako
08-04-2005, 14:51
dopo c provo e t faccio sapere.. grazie per ora!

Loading