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

Codice PHP:

#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]

Originariamente inviato da 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

è 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)