PDA

Visualizza la versione completa : [C]Albero Binario di stringhe


canino88
23-05-2010, 19:38
ciao a tutti, ho appena letto un post su un albero binario di interi su questo forum e ho preso il codice e lo ho adattato per lavorare su chiavi stringhe.
il mio problema Ŕ il seguente:
-leggo in un ciclo un certo numero di stringhe(nel mio esempio 7)
-se la stringa non Ŕ presente la inserisco nell albero
-uscito dal ciclo stampo le stringhe del mio albero
vi posto il codice sperando che mi possiate dare una mano


#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>

//FUNZIONA
struct Nodo{

char * key;
struct Nodo* left;
struct Nodo* right;

};

typedef struct Nodo* Tree;

void insert(Tree *t, char * k){

// crea il nodo foglia da inserire contenente la chiave
struct Nodo* e = malloc(sizeof(struct Nodo));
e->key = k;
e->left = e->right = NULL;

struct Nodo* p;
struct Nodo* x = *t;

// se l'albero Ŕ vuoto imposta e come radice dell'albero
if (x == NULL) {
*t = e;
return;
}

// altrimenti cerca la posizione della foglia nell'albero
while (x != NULL){

p = x;
if (strcmp(x->key,k) < 0) x = x->right;
else x = x->left;
}

// ora p punta al padre del nuovo elemento da inserire in t
// quindi si procede a linkare p ed e

if (strcmp(p->key,k) < 0) p->right = e;
else p->left = e;

}


// cerca una chiave k nell'albero t e restituisce la profonditÓ alla quale si trova
// oppure 0 se la chiave non Ŕ presente in t

int search(Tree t, char* k){

struct Nodo* n= t;
int depth = 0;

while (n != NULL){
depth++;
if (strcmp(n->key,k) >0) n = n->left;
else if (strcmp(n->key,k) == 0) return depth;
else n = n->right;
}

return 0;
}

int stampaa(Tree T) {

struct Nodo* n = T;

if (n == NULL)
return -1;
//caso ricorsivo (albero non vuoto)
else {
// esamina radice
printf("%s\n", n->key);
// visita sottoalbero sinistro
stampaa(n->left);
// visita sottoalbero destro
stampaa(n->right);
}
return 1;

}
int main() {

int a;
int k,i;
Tree t= NULL;
char *buf1, *buf2;
buf1 = malloc(30 * sizeof(char));
printf("inserisci chiave\n");
scanf("%s", buf1);
for(i=0;i<5;i++)
{insert(&t,buf1);
scanf("%s", buf1);
}
printf("stampa\n");
stampaa(t);

}






baci giulia

oregon
23-05-2010, 19:43
Ma il problema qual e'?

canino88
23-05-2010, 19:47
non funziona come dovrebbe esempio di input
-----
inserisci chiave
ciao
o
come
ciao
stai
io
OUTPUT:
stampa
io
io
io
io
io

oregon
23-05-2010, 20:01
Nella insert non puoi fare semplicemente

e->key = k;

ma devi allocare lo spazio per la stringa.

Devi sostituire quella riga con

e->key = (char *)malloc(strlen(k)+1);
e->key = strcpy(e->key, k);

canino88
23-05-2010, 20:09
ho modificato come mi hai detto te ma continua a darmi degli output scorretti :-(
scusatemi ma sono alle prime armi e devo consegnare l esercizio entro breve XD

oregon
23-05-2010, 20:46
Originariamente inviato da canino88
ho modificato come mi hai detto te ma continua a darmi degli output scorretti :-(

Quella modifica era necessaria. Cio' non vuol dire che sarebbe stata sufficiente ad eliminare tutti i problemi del codice.

Che intendi adesso con "output scorretti"?

Loading