PDA

Visualizza la versione completa : [C] alberi binari di ricerca


thesalien
21-01-2005, 14:11
Salve a tutti, ho costruito un programma che implementa un albero binario di ricerca. Ho provato e riprovato a implementare questo programma e alla fine sono arivato a questa versione che quella che diciamo, quella che funziona meglio. Tuttavia non funziona bene lo stesso, perch non riesce a memorizzare tutti gli elementi. Essa memorizza gli elementi sovrascrivendoli con gli ultimi (praticamente per 3 elementi, mi memorizza 3 elementi uguali all'ultimo). Io penso che il problema sta nella funzione ricerca_modificata ma non riesco a trovarlo (ho provato moltissime volte a modificarla ma questa quella che funziona di pi).
Qualcuno mi sa aiutare?


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
typedef char* elemento;
typedef struct nodo *tree_pointer;
typedef struct nodo {
elemento key;
tree_pointer figlio_sinistro;
tree_pointer figlio_destro;
} albero;
tree_pointer radice = NULL;
void preorder(tree_pointer ptr);
void inorder(tree_pointer ptr);
void postorder(tree_pointer ptr);
tree_pointer ric_ric(tree_pointer, char*);
tree_pointer ric_iter(tree_pointer, char* );


int menu(void);

void insert_nodo(tree_pointer *nodo,elemento num);

tree_pointer ric_modificata(tree_pointer , elemento );




main(){
printf("\nEsercitazione numero 14");
char *nome_chiave;
int scelta=100;
do{scelta=menu();
if(scelta==1){
printf("\nscrivi la chiave");
scanf("%s",nome_chiave);
insert_nodo(&radice,nome_chiave);
}

if(scelta==2){ printf("\nElemento da ricercare: ");
scanf("%s",nome_chiave);
if(ric_ric(radice,nome_chiave))
printf("\nTrovato!");
else printf("\nNon stato trovato!");
}


if(scelta==6)inorder(radice);

if(scelta==7)preorder(radice);

if(scelta==postorder(radice);

} while(scelta!=0);

fflush(stdin);
getchar();
}


int menu(void)
{
int buf;
printf("\n\nIndica l'operazione da eseguire:\n\n");
printf("inserisci elemento --> 1\n");
printf("ricerca elemento (ric.) --> 2\n");
printf("ricerca elemento (iter.) --> 3\n");
printf("cancella elemento per fusione --> 4\n");
printf("cancella elemento per copiatura --> 5\n");
printf("visita inorder --> 6\n");
printf("visita preorder --> 7\n");
printf("visita postorder --> 8\n");
printf("termina --> 0\n");
scanf("%d",&buf);
fflush;
return buf;
}



void insert_nodo(tree_pointer *nodo,elemento num)
{
tree_pointer ptr, temp;
temp = ric_modificata(*nodo, num);
if(temp || !(*nodo)) {
ptr = (tree_pointer)malloc(sizeof(nodo));
if (ptr == NULL) {
printf("\la memoria piena");
exit(1);
}
strcpy(ptr->key,num);
ptr->figlio_sinistro = NULL;
ptr->figlio_destro = NULL;
if(*nodo) if(strcmp(num,temp->key)<0) temp->figlio_sinistro = ptr;
else temp->figlio_destro = ptr;
else *nodo = ptr;
}
}



tree_pointer ric_modificata(tree_pointer tree, elemento chiave)
{
/* fornisce un puntatore al nodo che contiene item
se tale nodo non esiste fornisce NULL */
if(!tree) return NULL;

while(tree) {
if (strcmp(chiave,tree->key)==0) return NULL;
if (strcmp(chiave,tree->key)<0) {if (tree->figlio_sinistro) tree=tree->figlio_sinistro; else break;}
else {if (tree->figlio_destro) tree=tree->figlio_destro; else break;}
}
return tree;
}



/*algoritmo preorder*/
void preorder(tree_pointer ptr){
if(ptr){
printf("%4s",ptr->key);
preorder(ptr->figlio_sinistro);
preorder(ptr->figlio_destro);
}
}


/*algoritmo inorder*/
void inorder(tree_pointer ptr){
if(ptr){

inorder(ptr->figlio_sinistro);
printf("%4s",ptr->key);
inorder(ptr->figlio_destro);
}
}


/*algoritmo postorder*/
void postorder(tree_pointer ptr){
if(ptr){

postorder(ptr->figlio_sinistro);
postorder(ptr->figlio_destro);
printf("%4s",ptr->key);

}
}

tree_pointer ric_ric(tree_pointer radice, char* str)
{
if (!radice) return (NULL);
if (strcmp(str,radice->key) < 0)
return (ric_ric(radice->figlio_sinistro, str));
return (ric_ric(radice->figlio_destro, str));
}

tree_pointer ric_iter(tree_pointer tree, char* str)
{
while(tree)
{
if (strcmp(str,tree->key) == 0)
return(tree);
if (strcmp(str,tree->key) < 0)
return (ric_iter(tree->figlio_sinistro, str));
else tree = tree->figlio_destro;
}
return (NULL);
}

perzem
21-01-2005, 14:45
ti passo questa funzione di ricerca iterativa in pseudocodice, provala...

k= chiave nodo
x=valore da ricercare
ritorna un puntatore al nodo con chiave k oppura nil se k non presente nell'albero. Da invocare con x=bst-serarch(T,k)



bst-serarch(x,k)
{
while x!=nil and k!=key[x]
do if k<key[x]
then x=left[x];
else x=right[x];
return x;
}

MMarzia
21-01-2005, 15:36
ti consiglio di rileggere il nostro regolamento, nello specifico la parte relativa ai titoli delle discussioni...



per rendere il codice i leggibile ricorda di includerlo nel tag [*code] ... [*/code] (senza asterischi)

thesalien
22-01-2005, 02:21
Ciao perzem, grazie per quel codice ora provo a vedermelo.
X MMarzia, si hai ragione, chiedo scusa, sono nuovo e purtroppo non avevo letto il regolamento prima che tu mel avessi suggerito, ciao.

thesalien
23-01-2005, 15:48
Ho riscritto in C quello che mi hai suggerito ma non succede nulla, anzi ho fatto dei passi indietro perch memorizza ora solo un elemento :((

tree_pointer ric_modificata(tree_pointer tree, char* chiave)
{
/* fornisce un puntatore al nodo che contiene item
se tale nodo non esiste fornisce NULL */
while(tree!=NULL && chiave!=tree->key)
{
if(chiave<tree->key) tree=tree->figlio_sinistro;
else tree=tree->figlio_destro;
}

return tree;
}


Sto impazzendo :dh: dovrebbe funzionare ma non funziona e basta :master:

bako
23-01-2005, 16:57
falla ricorsiva..


item cerca(tree albero,bho key){
if (tree==NULL) return Null;
else if (tree->item->val==key) return tree->item;
else if (tree->item->val>key)
return cerca(albero->tree->sinistra,key)
else return cerca(albero->tree->destra,key)
}


le tue sono stringhe .. quindi nel controllo fai strcmp(tre..,key)==0 >0 <0 ..

infinitejustice
23-01-2005, 17:00
se magari vuoi darci un'okkiata... questo quello che scrissi al tempo dell'esame di Algoritmi.



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node{
int value;
struct node *leftChild;
struct node *rightChild;
}*root = NULL;


struct node *findMin(struct node *);
struct node *findMax(struct node *);
struct node *leftRotation(struct node *);
struct node *rightRotation(struct node *);
struct node *search(struct node *, int);
struct node *searchRicorsivo(struct node *, int);
void add(struct node **, int);
void addPathfinder (struct node *, int);
void delete(struct node **, struct node *, int);
void newNode(struct node **, int);
void traverse(struct node *);
void visit(struct node *);


void main(){

int i, array[] = {5, 3, 7, 2, 4, 8};

/* 5
/ \
3 7
/ \ \
2 4 8*/

srand(time(NULL));
for(i = 0; i < 6; i++){
add(&root, array[i]);
}

traverse(root);
}


void traverse(struct node *node){

if(node == NULL)
return;

traverse(node->leftChild);
traverse(node->rightChild);
visit(node);
}


void visit(struct node *node){

printf("%d\n", node->value);
}


//Ritorna un puntatore all'elemento piu piccolo (il child piu a sinistra senza child sinistro)
struct node *findMin(struct node *node){

if(node == NULL)
return NULL;
else
return((node->leftChild != NULL) ? findMin(node->leftChild) : node);
}


//Ritorna un puntatore all'elemento piu grande (il child piu a destra senza child destro)
struct node *findMax(struct node *node){

if(node == NULL)
return NULL;
else
return((node->rightChild != NULL) ? findMax(node->rightChild) : node);
}


//Ricerca iterativa: in caso positivo ritorna un puntatore all'elemento cercato
struct node *search(struct node *node, int x){

if(node == NULL)
return(NULL);

else if(node->value == x)
return(node);

else if (node->value > x)
return (search(node->leftChild, x));

else
return(search(node->rightChild, x));
}


//Ricerca ricorsiva
struct node *searchRicorsivo(struct node *node, int x){

while((node != NULL) && (node->value != x)){
if(node->value > x)
node = node->leftChild;
else
node = node->rightChild;
}

return(node);
}



void add(struct node **node, int x) {

if((*node) == NULL)
newNode(node, x);
else
addPathfinder(*node, x);
}


void newNode(struct node **node, int x){

if(!((*node) = malloc(sizeof(struct node))))
abort();
(*node)->leftChild = NULL;
(*node)->rightChild = NULL;
(*node)->value = x;
}


void addPathfinder (struct node *node, int x) {

if(x < node->value){
if(node->leftChild != NULL)
addPathfinder(node->leftChild, x);
else
newNode(&(node->leftChild), x);
}
else{
if(node->rightChild != NULL)
addPathfinder(node->rightChild, x);
else
newNode(&(node->rightChild), x);
}
}


void delete(struct node **father, struct node *tree, int x){

if(tree->value != x){
if(x < tree->value)
delete(&(tree->leftChild), tree->leftChild, x);
else
delete(&(tree->rightChild), tree->rightChild, x);
}

else{
if((tree->leftChild == NULL) && (tree->rightChild == NULL)){ // il nodo e' una foglia
*father = NULL;
free(tree);
}
else if(tree->leftChild == NULL){ // il nodo ha solo il figlio di destra
*father = tree->rightChild;
free(tree);
}
else if(tree->rightChild == NULL){ // il nodo ha solo il figlio di sinistra
*father = tree->leftChild;
free(tree);
}
else{ // il nodo ha due figli
tree->value = (findMax(tree->leftChild))->value;
delete(&(tree->leftChild),
tree->leftChild,
tree->value);
}
}
}


struct node *rightRotation(struct node *node){

struct node *temp = node->leftChild;
node->leftChild = temp->rightChild;
temp->rightChild = node;

return temp;
}


struct node *leftRotation(struct node *node){

struct node *temp = node->rightChild;
node->rightChild = temp->leftChild;
temp->leftChild = node;

return temp;
}



:ciauz:

edit: il disegno dell'albero fa un po skifo :D

thesalien
23-01-2005, 17:22
Si, mi sono dimenticato che erano stringhe ma la sostanza non cambia:

tree_pointer ric_modificata(tree_pointer tree, char* chiave)
{
/* fornisce un puntatore al nodo che contiene item
se tale nodo non esiste fornisce NULL */
while(tree!=NULL && strcmp(chiave,tree->key)!=0)
{
if(strcmp(chiave,tree->key)<0) tree=tree->figlio_sinistro;
else tree=tree->figlio_destro;
}

return tree;
}
Non fa lo stesso :(


infinitejustice: Ora provo a vedermi la tua funzione..

N.B. grazie a tutti per l'aiuto

bako
23-01-2005, 17:35
prova con un > nel if.. cmq la ricorsiva pi comoda..

thesalien
23-01-2005, 17:55
Niente :cry: , neanche cos! e neanche con la funz ricorsiva:

tree_pointer ric_modificata(tree_pointer tree, char* chiave)
{
/* fornisce un puntatore al nodo che contiene item
se tale nodo non esiste fornisce NULL */
if (tree==NULL) return NULL;
else if (strcmp(tree->key,chiave)==0) return tree;
else if (strcmp(tree->key,chiave)>0) return ric_modificata(tree->figlio_sinistro,chiave);
else return ric_modificata(tree->figlio_destro,chiave);

}

Loading