Autor Tema: Asignacion de punteros (Leído 3752 veces)

Rombus · « **en:** Viernes 24 de Octubre de 2008, 05:18 »

Hola gente!

estoy realizando un arbol generico y me encuentro con el problema (despues de depurar bastante) que no estoy asignando bien los hijos de los nodos.

mi codigo es el siguiente, como siempre, listo para compilar:

Código: C

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
 
typedef int (*_funCmp_t)(void *a, void *b);
typedef void (*_funPrint_t)(void *a);
 
///Arbol
typedef struct _nodo{
    void *valor;
    struct _nodo *iz;
    struct _nodo *der;
}nodo_t;
 
///Estructura administrativa
typedef struct {
    int sizeTipo;           //Tamaño del dato a almacenar
    nodo_t *raiz;
    _funCmp_t funCmp;       //Funcion de comparacion
    _funPrint_t funPrint;   //Funcion de impresion
}arbol_t;
 
int comparaEnteros(void *a, void *b){
    return *((int *)a) - *((int *)b);
}
void imprimeEnteros(void *a){
    printf("lol: %d",*(int *)a);
}
 
arbol_t *arbolCreate(int sizeTipo, _funCmp_t funCmp, _funPrint_t funPrint){
    arbol_t *arbol = (arbol_t *)malloc(sizeof(arbol_t));
    assert(arbol);
 
    arbol->sizeTipo = sizeTipo;
    arbol->funCmp = funCmp;
    arbol->funPrint = funPrint;
    arbol->raiz = NULL;
    return arbol;
}
 
nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz){
    nodo_t *nodo = (nodo_t *)malloc(sizeof(nodo_t));
    assert(nodo);
 
    nodo->valor = valor;
    nodo->der = der;
    nodo->iz = iz;
    
    return nodo;
}
nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
    if(!nodo)
        return creaNodo(arbol, aIngresar, NULL, NULL);
    
    if(arbol->funCmp(nodo->valor, aIngresar) > 0)
        nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
    else if(arbol->funCmp(nodo->valor, aIngresar) < 0)
        nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
    return nodo;
}
void printArbol(arbol_t *arbol, nodo_t *nodo){  //Preorden
    if(nodo)
        arbol->funPrint(nodo->valor);
 
    if(nodo->iz)
        printArbol(arbol, nodo->iz);
    if(nodo->der)
        printArbol(arbol, nodo->der);
}
 
int main(void){
    arbol_t *arbol = arbolCreate(sizeof(int),comparaEnteros, imprimeEnteros);
    int i = 5;
 
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i =4;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i =3;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i = 7;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    
    
    printArbol(arbol, arbol->raiz); 
    return 0;
}
 

el problema creo q esta en la funcion arbolInsert(); ya que nunca entra ni en el IF ni el ELSE IF de dicha funcion, siempre termina devolviendo el return creaNodo(); lo que genera que no se forme un arbol.. siempre se inserta en la cabeza y lo que habia antes se pierde.

esto se debe a que la comparacion que contemplan los if's: arbol->funCmp(nodo->valor, aIngresar) , siempre da 0, y es porque tanto el valor que recibe como parametro nodo_t *nodo y void *aIngresar es el mismo :O!, imprimo las direcciones de memoria y los valores y siepmre compara (por ejemplo) A con A, B con B, y en la funcion de comparacion cuando las cadenas son iguales devuelve 0.

entiendo que es lo que pasa... lo que no me sale es como arreglarlo :S

alguien sabe como evitar esto?

gracias de antemano!

m0skit0

Personalmente creo que complicas las cosas sencillas, pero bueno...

Código: C

typedef struct {
    int sizeTipo;           //Tamaño del dato a almacenar
    nodo_t *raiz;
    _funCmp_t funCmp;       //Funcion de comparacion
    _funPrint_t funPrint;   //Funcion de impresion
}arbol_t;
 

Si vas a meter punteros a funciones en una estructura, mejor usa C++ y objetos.

Código: C

 
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i =4;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i =3;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
    i = 7;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
}
 

Tienes un error de concepto en estas líneas. Tú lo que estas insertando en el árbol no son los valores de i, sino el puntero a i, por lo tanto es lógico que nodo_t *nodo y void *aIngresar sean el mismo, puesto que es &i (que siempre es el mismo, aunque cambies el valor de i). Al hacer en main() i =4; y luego i = 7; cambias el valor apuntado por &i, no &i. Por tanto, en el árbol, sólo has insertado un nodo con el puntero, al que vas cambiando el valor al que apunta, pero no creas un nuevo valor. Vas a tener que reservar memoria por cada elemento que desees insertar, porque sino simplemente lo sobreescribes. Algo como:

Código: C

    int *i;
 
    i = (int *) malloc(sizeof(int));
    *i = 5;
    arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)i);
 

Espero haberme explicado, un saludo.

Rombus

Cita de: "m0skit0"

Tú lo que estas insertando en el árbol no son los valores de i, sino el puntero a i, por lo tanto es lógico que nodo_t *nodo y void *aIngresar sean el mismo

gracias moskito!!

es verdad

lo soluicione modificando la funcion creaNodo(); de esta manera:

Código: C

nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz){
    nodo_t *nodo = (nodo_t *)malloc(sizeof(nodo_t));
    void *dato = malloc(sizeof(void*));
    assert(dato);
    assert(nodo);
 
    nodo->valor = dato; //para que nodo->valor apunte a una dir valida antes de hacer el memcpy
    memcpy((char *)(nodo->valor), (char *)valor, sizeof(nodo_t));
    nodo->der = der;
    nodo->iz = iz;
    
    return nodo;
}
 

asi con el memcpy copio el contenido y no la direccion

gracias!

m0skit0

Cita de: "Rombus"

asi con el memcpy copio el contenido y no la direccion

Pero no olvides hacer un free() de los malloc() que hayas hecho. Sigo pensando que con POO quedaría mucho más bonito, puesto que tienes destructores que se encargan de esto.

Código: C

nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz)
 

Además, ya no necesitas el parámetro arbol (de hecho, no lo necesitas, salvo por la llamada al puntero de función ese, que no me gusta nada

). En fin, encantado de guiarte, un saludo.

Rombus

Citar

Pero no olvides hacer un free() de los malloc() que hayas hecho.

si, ya tengo la destructora.

Citar

Sigo pensando que con POO quedaría mucho más bonito, puesto que tienes destructores que se encargan de esto.

seguramente.. pero un gran problema para mi es que no se C++ XD!

y es verdad lo del arbol por parametro solo lo necesito para usar esas funciones

gracias moskito!

un saludo

eternity

fijate que tu algoritmo para mostrar el recorrido en pre Orden es mas facil que el que estas usando!
tendría que ser asi!

Código: C

void printArbol(arbol_t *arbol, nodo_t *nodo){  //Preorden
    if(nodo!=NULL){
        arbol->funPrint(nodo->valor);
        printArbol(arbol, nodo->iz);
        printArbol(arbol, nodo->der);
    }
}
 

y que cuando llamas a la función Crea nodo le estás pasando un argumento de más (arbol_t *arbol) que no usas para nada

Cita de: "Rombus"

Código: C
nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz)

fijate que creaNodo, solo depende de la raiz del árbol, y no te toda la estructura administrativa!
tendrias que hacer:

Código: C

nodo_t *creaNodo(void *valor, nodo_t *der, nodo_t *iz)
 

y despues cambiar en arbolInsert esta linea:

Cita de: "Rombus"

Código: C
return creaNodo(arbol, aIngresar, NULL, NULL);

por esta otra:

return creaNodo( aIngresar, NULL, NULL);

Nos vemos Rombus!

Rombus

:O

un par de datos bastante interesantes tiraste ahi

gracias ternitys!

eternity

otra sugerencia!

esta es para el la funcción arbolInsert!

Cita de: "Rombus"

Código: C
nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
if(!nodo)
return creaNodo(arbol, aIngresar, NULL, NULL);

if(arbol->funCmp(nodo->valor, aIngresar) > 0)
nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
else if(arbol->funCmp(nodo->valor, aIngresar) < 0)
nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
return nodo;
}

fijate en esto:

Código: C

nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
    if(nodo == NULL) 
        return creaNodo( aIngresar, NULL, NULL);
    else
        if(arbol->funCmp(nodo->valor, aIngresar) <= 0)
            nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
        else 
            nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
 
    return nodo;
}
 

puede que funciones pero no estoy seguro de si if(!nodo) es lo mismo que prguntar if (nodo == NULL), esto es mucho mas decifrable cuando se labura con punteros jeje

viste ahi cambie lo que te dije en el post anterior

otra, en tu codigo no conteplabas en los casos que arbol->funCmp(nodo->valor, aIngresar) eran iguales a cero, en ese caso nunca harias nada yo lo solucione con un <= 0 eso me garantiza que todos los valores seran insertados;
y de vuelta vos llamaste dos veces a arbol->funCmp(nodo->valor, aIngresar) cuando por defecto en un IF, sabes la contrapartida colocando un ELSE

Saludos Rombus

Rombus

Citar

puede que funciones pero no estoy seguro de si if(!nodo) es lo mismo que prguntar if (nodo == NULL), esto es mucho mas decifrable cuando se labura con punteros jeje

si if (!nodo) seria preguntar por si nodo == NULL

Citar

otra, en tu codigo no conteplabas en los casos que arbol->funCmp(nodo->valor, aIngresar) eran iguales a cero, en ese caso nunca harias nada yo lo solucione con un <= 0 eso me garantiza que todos los valores seran insertados;
y de vuelta vos llamaste dos veces a arbol->funCmp(nodo->valor, aIngresar) cuando por defecto en un IF, sabes la contrapartida colocando un ELSE

claro, justamente no quiero q haga nada cuando sea 0, pq significa q ese valor ya esta ingresado, y no hace falta volverlo a ingresar.

por eso en vez de poner un else pongo un else if, para dejar fuera cuando me de 0

eternity

las mismas dos cosas, empiezo por la segunda, si la entrada del programa fuera:

5, 4, 3, 7, 7, 3, la salida esperada en preorden seria: 5, 7, 7, 4, 3, 3,
pero como tu codigo no contempla valores repetidos, tu salida es 5, 7, 4, 3

dos opciones o contemplas un campo de node que sea cantidad de apariciones de un dato, o contemplas que pueda haber datos repetidos y en nodos distintos.

y despues, la solucion "trivial" para insertar un nodo en un arbol binario, es que llegues a un nodo==NULL, no a un !nodo o como lo quieras llamar!

Rombus

pero es un arbol binario de busqueda.. no nesesito tener valores repetidos

m0skit0

Cita de: "eternity"

como tu codigo no contempla valores repetidos

A lo mejor es lo que quiere

Cita de: "Rombus"

si if (!nodo) seria preguntar por si nodo == NULL

No necesariamente. Ten en cuenta que NULL está definido por el SO y puede ser cualquier valor, aunque en todos los SOs que conozco es 0. Sin embargo, si en un determinado SO no fuera así, poniendo if(!nodo) incurres en un error y habría que cambiarlo, cosa que no ocurriría si pusieses la alternativa. Es mejor ésta puesto que es más portable (de hecho, para eso se inventó una constante NULL). Un saludo y ¡acabemos ya este post!

Eternal Idol

NULL es 0, no hay duda, cualquier otro valor seria una aberracion sin ningun sentido.

m0skit0

Cita de: "Eternal Idol"

cualquier otro valor seria una aberracion sin ningun sentido.

Peores cosas se han visto...

SoloCodigo

Autor Tema: Asignacion de punteros (Leído 3752 veces)

Rombus

Asignacion de punteros

m0skit0

Re: Asignacion de punteros

Rombus

Re: Asignacion de punteros

m0skit0

Re: Asignacion de punteros

Rombus

Re: Asignacion de punteros

eternity

Re: Asignacion de punteros

Rombus

Re: Asignacion de punteros

eternity

Re: Asignacion de punteros

Rombus

Re: Asignacion de punteros

eternity

Re: Asignacion de punteros

Rombus

Re: Asignacion de punteros

m0skit0

Re: Asignacion de punteros

Eternal Idol

Re: Asignacion de punteros

m0skit0

Re: Asignacion de punteros