C Albero binario con chiave stringa...come?

[TorpedoBlu]

ciao ragazzi, ho trovato il codice per l'albero binario in cui la chiave è un Int, sembra banale ma come faccio a modificare le funzioni in modo che tutto funzioni con chiave stringa (con ordine lessicografico)?

ecco il codice:


/***************************
* searchtree.h *
***************************/

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

typedef int key;

struct searchtree {
key v;
struct searchtree *left, *right, *up;
};

typedef struct searchtree searchtree;

searchtree *createsearchtree(void);

void inorder(searchtree *p, void (*op)(searchtree *));

searchtree *search(searchtree *p, key k);

searchtree *search2ndvers(searchtree *p, key k);

searchtree *search3rdvers(searchtree *p, key k);

searchtree *itsearch(searchtree *p, key k);

searchtree *treemin(searchtree *p);

searchtree *treemax(searchtree *p);

searchtree *treesucc(searchtree *q);

searchtree *treepred(searchtree *q);

searchtree *insert(searchtree *p, key k);

searchtree *delete(searchtree *p, searchtree *q);

void destroysearchtree(searchtree *p);

/* End of file searchtree.h */


/*****************************
* searchtree.c *
*****************************/

#include "searchtree.h"

searchtree *createsearchtree(void)
{
return NULL;
}

void inorder(searchtree *p, void (*op)(searchtree *))
{
if(p) {
inorder(p->left,op);
(*op)(p);
inorder(p->right,op);
}
}

searchtree *search(searchtree *p, key k)
{
if(!p || k == p->v)
return p;
return search(k < p->v ? p->left : p->right, k);
}

searchtree *search2ndvers(searchtree *p, key k)
{
if(!p || k == p->v)
return p;
return k < p->v ? search2ndvers(p->left,k) : search2ndvers(p->right,k);
}

searchtree *search3rdvers(searchtree *p, key k)
{
if(!p || k == p->v)
return p;
if(k < p->v)
return search3rdvers(p->left,k);
else
return search3rdvers(p->right,k);
}

searchtree *itsearch(searchtree *p, key k)
{
while(p && k != p->v)
p = k < p->v ? p->left : p->right;
return p;
}

searchtree *treemin(searchtree *p)
{
for(;p->left;p = p->left);
return p;
}

searchtree *treemax(searchtree *p)
{
for(;p->right;p = p->right);
return p;
}

searchtree *treesucc(searchtree *q)
{
searchtree *qq;

if(q->right)
return treemin(q->right);
qq = q->up;
while(qq && q == qq->right) {
q = qq;
qq = qq->up;
}
return qq;
}

searchtree *treepred(searchtree *q)
{
searchtree *qq;

if(q->left)
return treemax(q->left);
qq = q->up;
while(qq && q == qq->left) {
q = qq;
qq = qq->up;
}
return qq;
}

searchtree *insert(searchtree *p, key k)
{
searchtree *q = malloc(sizeof(searchtree));
searchtree *r = p;
searchtree *s = NULL;

if(!q) {
fprintf(stderr,"Errore di allocazione\n");
exit(-1);
}
q->v = k;
q->left = q->right = NULL;
while(r) {
s = r;
r = k < r->v ? r->left : r->right;
}
q->up = s;
if(!s)
return q;
if(k < s->v)
s->left = q;
else
s->right = q;
return p;
}

searchtree *delete(searchtree *p, searchtree *q)
{
searchtree *r, *s, *t = NULL;

if(!q->left || !q->right)
r = q;
else
r = treesucc(q);
s = r->left ? r->left : r->right;
if(s)
s->up = r->up;
if(!r->up)
t = s;
else
if(r == r->up->left)
r->up->left = s;
else
r->up->right = s;
if(r != q)
q->v = r->v;
free(r);
return t ? t : (p != r ? p : NULL);
}

void destroysearchtree(searchtree *p)
{
while(p = delete(p,p));
}

[TorpedoBlu]

io ci ho provato, ma non va, ho usato al posto di < e > la funzione strcmp()



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


typedef char key;

struct searchtree {
key *v;
struct searchtree *left, *right, *up;
};

typedef struct searchtree searchtree;

searchtree *createsearchtree(void);

void inorder(searchtree *p, void (*op)(searchtree *));

searchtree *search(searchtree *p, key *k);

searchtree *search2ndvers(searchtree *p, key *k);

searchtree *search3rdvers(searchtree *p, key *k);

searchtree *itsearch(searchtree *p, key *k);

searchtree *treemin(searchtree *p);

searchtree *treemax(searchtree *p);

searchtree *treesucc(searchtree *q);

searchtree *treepred(searchtree *q);

searchtree *insert(searchtree *p, key *k);

searchtree *delete(searchtree *p, searchtree *q);

void destroysearchtree(searchtree *p);






searchtree *createsearchtree(void)
{
return NULL;
}

void inorder(searchtree *p, void (*op)(searchtree *))
{
if(p) {
inorder(p->left,op);
(*op)(p);
inorder(p->right,op);
}
}

searchtree *search(searchtree *p, key *k)
{
if(!p || strcmp(k,p->v)==0)
return p;
return search(strcmp(k, p->v)? p->left : p->right, k);
}


searchtree *treemin(searchtree *p)
{
for(;p->left;p = p->left);
return p;
}

searchtree *treemax(searchtree *p)
{
for(;p->right;p = p->right);
return p;
}

searchtree *treesucc(searchtree *q)
{
searchtree *qq;

if(q->right)
return treemin(q->right);
qq = q->up;
while(qq && q == qq->right) {
q = qq;
qq = qq->up;
}
return qq;
}

searchtree *treepred(searchtree *q)
{
searchtree *qq;

if(q->left)
return treemax(q->left);
qq = q->up;
while(qq && q == qq->left) {
q = qq;
qq = qq->up;
}
return qq;
}

searchtree *insert(searchtree *p, key *k)
{
searchtree *q = malloc(sizeof(searchtree));
searchtree *r = p;
searchtree *s = NULL;

if(!q) {
fprintf(stderr,"Errore di allocazione\n");
exit(-1);
}
q->v = k;
q->left = q->right = NULL;
while(r) {
s = r;
r = strcmp(k,r->v) ? r->left : r->right;
}
q->up = s;
if(!s)
return q;
if(strcmp(k,s->v))
s->left = q;
else
s->right = q;
return p;
}

searchtree *delete(searchtree *p, searchtree *q)
{
searchtree *r, *s, *t = NULL;

if(!q->left || !q->right)
r = q;
else
r = treesucc(q);
s = r->left ? r->left : r->right;
if(s)
s->up = r->up;
if(!r->up)
t = s;
else
if(r == r->up->left)
r->up->left = s;
else
r->up->right = s;
if(r != q)
q->v = r->v;
free(r);
return t ? t : (p != r ? p : NULL);
}

void destroysearchtree(searchtree *p)
{
while(p = delete(p,p));
}



int main(void){
searchtree *pippo;
searchtree *A =createsearchtree();
/*inserisco e contestualmente controllo*/
if(insert(A, "pippo")) printf("inserito");
else printf("errore");
/*cerco il nodo inserito*/
pippo=search(A,"pippo");
/*stampo il nome della chiave del nodo trovato*/
printf("\n\n\n trovato: %s",pippo->v);
return 0;
}

[mr_hyde]

Attento: strcmp restituisce
- un intero < 0
- oppure 0
- oppure un intero > 0

Quindi, la funzione

searchtree *search(searchtree *p, key *k)
{
if(!p || strcmp(k,p->v)==0)
return p;
return search(strcmp(k, p->v)? p->left : p->right, k);
}

_PROBABILMENTE_ dovrebbe essere qualcosa del tipo:

searchtree *search(searchtree *p, key *k)
{
if(!p || strcmp(k,p->v)==0)
return p;
return search((strcmp(k, p->v) < 0) ? p->left : p->right, k);
}

(infatti ricorda che:
- (numero diverso da zero) equivale a TRUE
- 0 equivale a FALSE

Quindi la tua search sarebbe sempre andata a sinistra (meno male che non siamo piu' in periodo elettorale :-) )

Ciao,
Mr Hyde

[TorpedoBlu]

giusto! ho modificato sia search che insert e funziona! che cachiata!

[TorpedoBlu]

ecco siccome mi serve anche tenere i nodi ordinati in base alla X ho bisogno di una struttura di appoggio (una lista bidirezionale) ma come ordinare in base alla X?

io ho provato



#include "progetto.h"

/* crea una lista vuota e ne restituisce il puntatore radice */
intlist *createlist(void)
{
intlist *q = malloc(sizeof(intlist));

if(!q) {
fprintf(stderr,"Errore di allocazione nella creazione della lista\n");
exit(-1);
};
q->next = q->prev = q;
return q;
}




/* ritorna il numero di elementi nella lista */
int countlist(intlist *p)
{
int i;
intlist *q;

if(!p || p == p->next)
return 0;
for(i = 1, q = p->next; q->next != p; q = q->next, i++);
return i;
}

/* inserisce un elemento in testa alla lista */
void insertL(intlist *p, int elem, searchtree *nodo)
{
intlist *q = malloc(sizeof(intlist));

if(!q) {
fprintf(stderr,"Errore nell'allocazione del nuovo elemento\n");
exit(-1);
};
q->dato = elem;
q->nodo=nodo;
q->next = p->next;
p->next->prev = q;
p->next = q;
q->prev = p;
}


/* inserisce un elemento in ordine alla lista */
intlist *insertOrderL(intlist *p, int elem, searchtree *nodo)
{
intlist *q = malloc(sizeof(intlist));
intlist *s = p;
if(!q) {
fprintf(stderr,"Errore nell'allocazione del nuovo elemento\n");
exit(-1);
};

/*ATTENZIONE NON CICLA BENE NON FUNZIONA, CONTINUA A CICLARE!!!!*/
if(p!=NULL){
while((p->next)&&(p->next->dato>elem)){
p=p->next;
printf(".");
}
}


q->dato = elem;
q->nodo = nodo;
q->next = p->next;
p->next->prev = q;
p->next = q;
q->prev = p;

return s;
}


/* inserisce un elemento in coda alla lista */
void insertatend(intlist *p, int elem, searchtree *nodo)
{
intlist *q = malloc(sizeof(intlist));

if(!q) {
fprintf(stderr,"Errore nell'allocazione del nuovo elemento\n");
exit(-1);
};
q->dato = elem;
q->nodo=nodo;
q->prev = p->prev;
p->prev->next = q;
p->prev = q;
q->next = p;
}


/* cancella l'elemento puntato da q dalla lista */
void deleteL(intlist *q)
{
q->prev->next = q->next;
q->next->prev = q->prev;
free(q);
}

/* distrugge la lista */
void destroylist(intlist *p)
{
while(p->next != p)
deleteL(p->next);
free(p);
}






insertOrderL() dovrebbe inserire dopo aver percorso la lista e trovato la posizione giusta.. dite che è meglio implementare una funziona che ordina la lista separatamente? (in caso io modifichi la X di un nodo devo cambiare la sua posizione in lista quindi non mi basta inserirli in ordine)

[mr_hyde]

Scusa ma, vista la mia immensa ignoranza, visto che non conosco neppure un milionesimo di niente e visto che fatto non fui a viver come bruto ma per seguir virtute e canoscenza mi manca un'informazione basilare: cosa e' la X di un nodo?

Ciao,
Mr Hyde

[TorpedoBlu]

Scusa ma, vista la mia immensa ignoranza, visto che non conosco neppure un milionesimo di niente e visto che fatto non fui a viver come bruto ma per seguir virtute e canoscenza mi manca un'informazione basilare: cosa e' la X di un nodo?

Ciao,
Mr Hyde


è un intero che mi serve per ordinare i nodi in base alle ascisse.

ho usato un alberoper immagazzinare i dati in base al nome, ma devo avere ordinato anche in base alla x (avendo ogni nodo delle coordinate x,y ed un nome)