SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Rombus en Viernes 24 de Octubre de 2008, 05:18

Título: Asignacion de punteros
Publicado por: 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
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <assert.h>
  4.  
  5. typedef int (*_funCmp_t)(void *a, void *b);
  6. typedef void (*_funPrint_t)(void *a);
  7.  
  8. ///Arbol
  9. typedef struct _nodo{
  10.     void *valor;
  11.     struct _nodo *iz;
  12.     struct _nodo *der;
  13. }nodo_t;
  14.  
  15. ///Estructura administrativa
  16. typedef struct {
  17.     int sizeTipo;           //Tamaño del dato a almacenar
  18.     nodo_t *raiz;
  19.     _funCmp_t funCmp;       //Funcion de comparacion
  20.     _funPrint_t funPrint;   //Funcion de impresion
  21. }arbol_t;
  22.  
  23. int comparaEnteros(void *a, void *b){
  24.     return *((int *)a) - *((int *)b);
  25. }
  26. void imprimeEnteros(void *a){
  27.     printf("lol: %d",*(int *)a);
  28. }
  29.  
  30. arbol_t *arbolCreate(int sizeTipo, _funCmp_t funCmp, _funPrint_t funPrint){
  31.     arbol_t *arbol = (arbol_t *)malloc(sizeof(arbol_t));
  32.     assert(arbol);
  33.  
  34.     arbol->sizeTipo = sizeTipo;
  35.     arbol->funCmp = funCmp;
  36.     arbol->funPrint = funPrint;
  37.     arbol->raiz = NULL;
  38.     return arbol;
  39. }
  40.  
  41. nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz){
  42.     nodo_t *nodo = (nodo_t *)malloc(sizeof(nodo_t));
  43.     assert(nodo);
  44.  
  45.     nodo->valor = valor;
  46.     nodo->der = der;
  47.     nodo->iz = iz;
  48.    
  49.     return nodo;
  50. }
  51. nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
  52.     if(!nodo)
  53.         return creaNodo(arbol, aIngresar, NULL, NULL);
  54.    
  55.     if(arbol->funCmp(nodo->valor, aIngresar) > 0)
  56.         nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
  57.     else if(arbol->funCmp(nodo->valor, aIngresar) < 0)
  58.         nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
  59.     return nodo;
  60. }
  61. void printArbol(arbol_t *arbol, nodo_t *nodo){  //Preorden
  62.     if(nodo)
  63.         arbol->funPrint(nodo->valor);
  64.  
  65.     if(nodo->iz)
  66.         printArbol(arbol, nodo->iz);
  67.     if(nodo->der)
  68.         printArbol(arbol, nodo->der);
  69. }
  70.  
  71. int main(void){
  72.     arbol_t *arbol = arbolCreate(sizeof(int),comparaEnteros, imprimeEnteros);
  73.     int i = 5;
  74.  
  75.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  76.     i =4;
  77.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  78.     i =3;
  79.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  80.     i = 7;
  81.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  82.    
  83.    
  84.     printArbol(arbol, arbol->raiz);
  85.     return 0;
  86. }
  87.  

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!
Título: Re: Asignacion de punteros
Publicado por: m0skit0 en Viernes 24 de Octubre de 2008, 12:22
Personalmente creo que complicas las cosas sencillas, pero bueno...

Código: C
  1. typedef struct {
  2.     int sizeTipo;           //Tamaño del dato a almacenar
  3.     nodo_t *raiz;
  4.     _funCmp_t funCmp;       //Funcion de comparacion
  5.     _funPrint_t funPrint;   //Funcion de impresion
  6. }arbol_t;
  7.  

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

Código: C
  1.  
  2.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  3.     i =4;
  4.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  5.     i =3;
  6.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  7.     i = 7;
  8.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)&i);
  9. }
  10.  

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
  1.     int *i;
  2.  
  3.     i = (int *) malloc(sizeof(int));
  4.     *i = 5;
  5.     arbol->raiz = arbolInsert(arbol, arbol->raiz, (void *)i);
  6.  

Espero haberme explicado, un saludo.
Título: Re: Asignacion de punteros
Publicado por: Rombus en Viernes 24 de Octubre de 2008, 14:57
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  :wacko:

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

Código: C
  1. nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz){
  2.     nodo_t *nodo = (nodo_t *)malloc(sizeof(nodo_t));
  3.     void *dato = malloc(sizeof(void*));
  4.     assert(dato);
  5.     assert(nodo);
  6.  
  7.     nodo->valor = dato; //para que nodo->valor apunte a una dir valida antes de hacer el memcpy
  8.     memcpy((char *)(nodo->valor), (char *)valor, sizeof(nodo_t));
  9.     nodo->der = der;
  10.     nodo->iz = iz;
  11.    
  12.     return nodo;
  13. }
  14.  

asi con el memcpy copio el contenido y no la direccion  :beer:


gracias!
Título: Re: Asignacion de punteros
Publicado por: m0skit0 en Viernes 24 de Octubre de 2008, 15:05
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
  1. nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz)
  2.  

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 :P ). En fin, encantado de guiarte, un saludo.
Título: Re: Asignacion de punteros
Publicado por: Rombus en Viernes 24 de Octubre de 2008, 15:12
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  :comp:
Título: Re: Asignacion de punteros
Publicado por: eternity en Viernes 24 de Octubre de 2008, 16:04
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
  1. void printArbol(arbol_t *arbol, nodo_t *nodo){  //Preorden
  2.     if(nodo!=NULL){
  3.         arbol->funPrint(nodo->valor);
  4.         printArbol(arbol, nodo->iz);
  5.         printArbol(arbol, nodo->der);
  6.     }
  7. }
  8.  

 :beer:

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
  1. nodo_t *creaNodo(arbol_t *arbol, void *valor, nodo_t *der, nodo_t *iz)
  2.  

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

Código: C
  1. nodo_t *creaNodo(void *valor, nodo_t *der, nodo_t *iz)
  2.  

y despues cambiar en arbolInsert esta linea:

Cita de: "Rombus"
Código: C
  1. return creaNodo(arbol, aIngresar, NULL, NULL);
  2.  

por esta otra:

return creaNodo( aIngresar, NULL, NULL);

Nos vemos Rombus!
Título: Re: Asignacion de punteros
Publicado por: Rombus en Viernes 24 de Octubre de 2008, 16:13
:O


un par de datos bastante interesantes tiraste  ahi  :beer:

gracias ternitys!
Título: Re: Asignacion de punteros
Publicado por: eternity en Viernes 24 de Octubre de 2008, 17:03
otra sugerencia!

esta es para el la funcción arbolInsert!

Cita de: "Rombus"
Código: C
  1. nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
  2.     if(!nodo)
  3.         return creaNodo(arbol, aIngresar, NULL, NULL);
  4.    
  5.     if(arbol->funCmp(nodo->valor, aIngresar) > 0)
  6.         nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
  7.     else if(arbol->funCmp(nodo->valor, aIngresar) < 0)
  8.         nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
  9.     return nodo;
  10. }
  11.  

fijate en esto:

Código: C
  1. nodo_t *arbolInsert(arbol_t *arbol, nodo_t *nodo, void *aIngresar){
  2.     if(nodo == NULL)
  3.         return creaNodo( aIngresar, NULL, NULL);
  4.     else
  5.         if(arbol->funCmp(nodo->valor, aIngresar) <= 0)
  6.             nodo->iz = arbolInsert(arbol, nodo->iz, aIngresar);
  7.         else
  8.             nodo->der = arbolInsert(arbol, nodo->der, aIngresar);
  9.  
  10.     return nodo;
  11. }
  12.  

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

 :good:
Título: Re: Asignacion de punteros
Publicado por: Rombus en Viernes 24 de Octubre de 2008, 17:09
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

 :good:
Título: Re: Asignacion de punteros
Publicado por: eternity en Viernes 24 de Octubre de 2008, 17:38
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!

 :beer:  :good:
Título: Re: Asignacion de punteros
Publicado por: Rombus en Viernes 24 de Octubre de 2008, 17:47
pero es un arbol binario de busqueda.. no nesesito tener valores repetidos
Título: Re: Asignacion de punteros
Publicado por: m0skit0 en Viernes 24 de Octubre de 2008, 17:54
Cita de: "eternity"
como tu codigo no contempla valores repetidos

A lo mejor es lo que quiere  :P

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!  :P
Título: Re: Asignacion de punteros
Publicado por: Eternal Idol en Viernes 24 de Octubre de 2008, 18:22
NULL es 0, no hay duda, cualquier otro valor seria una aberracion sin ningun sentido.
Título: Re: Asignacion de punteros
Publicado por: m0skit0 en Viernes 24 de Octubre de 2008, 21:13
Cita de: "Eternal Idol"
cualquier otro valor seria una aberracion sin ningun sentido.

Peores cosas se han visto...  :D