Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: matrod en 29 Abril 2016, 06:56 am


Título: buscar camino en un arbol AYUDAAAAA!!!
Publicado por: matrod en 29 Abril 2016, 06:56 am
Hola! tengo una entrega en facultad y hay una función que me está matando...

me piden hacer una función que dado un arbol binario de busqueda y una lista, me devuelva el "camino" que hace esa lista si es que existe dentro del arbol... el encabezado es este:

camino_t buscar_camino(const lista l, const binario b);

y el tipo camino es asi:

Código
  1. struct camino_t {
  2. bool existe ;
  3. array_rama ramas ;
  4. nat cantidad_ramas ;
  5. };
  6.  
PD: existe una función que creo que es util:
Código
  1. texto_t camino_a_texto(const camino_t c) {
  2.   texto_t res;
  3.   // espacio suficiente para "No existe" o para cada rama y la coma y la
  4.   // cantidad, el guión y los paréntesis.
  5.   char cadena[c.cantidad_ramas * 2 + 10];
  6.   if (!c.existe) {
  7.     strcpy(cadena, "No existe");
  8.   } else {
  9.     sprintf(cadena, "%d", c.cantidad_ramas);
  10.     strcat(cadena, "-(");
  11.     if (c.cantidad_ramas > 0) {
  12.       agregar_rama(cadena, c.ramas[0]);
  13.       for (nat i = 1; i < c.cantidad_ramas; i++) {
  14.         strcat(cadena, ",");
  15.         agregar_rama(cadena, c.ramas[i]);
  16.       }
  17.     }
  18.     strcat(cadena, ")");
  19.   }
  20.   res = cadena_a_texto(cadena);
  21.   return res;
  22. }
  23.  
al menos creo que de ahi se puede sacar algo...eso intenté pero no sale...se cuelga todo

AYUDAAAA

(http://imageshack.com/a/img922/685/L2w40e.jpg)

MOD EDIT: No hacer doble post.

Título: Re: buscar camino en un arbol AYUDAAAAA!!!
Publicado por: MAFUS en 29 Abril 2016, 17:56 pm
¿Qué es...
texto_t
array_rama
nat
?

Título: Re: buscar camino en un arbol AYUDAAAAA!!!
Publicado por: _TTFH_3500 en 29 Abril 2016, 18:19 pm
UY que mal, en 7 horas te respondo...

Cita de: MAFUS en 29 Abril 2016, 17:56 pm
¿Qué es...
texto_t
array_rama
nat
?

texto_t es un puntero a una estructura (registro) que tiene un campo que es otro puntero a un o varios carácter/es.

array_rama es un puntero a un enumerado que puede ser izq o der

typedef unsigned int nat;

me pregunto cómo se esto?... en fin.


Si lo que quieres es ver si una lista esta en un árbol binario de búsqueda.

Código
  1. #include <assert.h>
  2.  
  3. bool existe_camino(const lista l, const binario b) {
  4.   bool existe = true;
  5.   nodo* loc = inicio_lista(l); // loc es un puntero a un elemento de la lista
  6.   binario aux = b; // puntero auxiliar a arbol binario
  7.   assert(!es_vacia_lista(l) && !es_vacio_binario(b));
  8.   if (!es_igual_dato(loc, l, aux))
  9.     existe = false;
  10.   while (existe && loc != final_lista(l)) {
  11.     loc = siguiente(loc, l);
  12.     if (!es_vacio_binario(derecho(aux)) && es_igual_dato(loc, l, derecho(aux)))
  13.       aux = derecho(aux);
  14.     else if (!es_vacio_binario(izquierdo(aux)) && es_igual_dato(loc, l, izquierdo(aux)))
  15.       aux = izquierdo(aux);
  16.     else existe = false;
  17.   }
  18.   if (!es_vacio_binario(izquierdo(aux)) || !es_vacio_binario(derecho(aux)))
  19.     existe = false;
  20.   return existe;
  21. }

luego tu ves como llenar la estructura camino_t.

Título: Re: buscar camino en un arbol AYUDAAAAA!!!
Publicado por: matrod en 30 Abril 2016, 04:55 am
solo para cerrar el tema...lo terminé resolviendo asi:

Citar
camino_t buscar_camino(const lista l, const binario b){
   binario baux=b;
   camino_t caux;
   caux.existe=false;
   caux.cantidad_ramas=0;
   caux.ramas= new rama_t[largo_lista(l)];
   bool bandera=true;
   int i=0;
   localizador loc=inicio_lista(l);
   while (es_localizador_lista(loc) && bandera)
   { if (!es_vacio_binario(baux))
   {bandera=comparar_texto(texto_info(raiz_binario(baux)),texto_info(info_lista(loc,l)))==igual;   }
   else {bandera=false;}
   if (bandera)
   {if (es_localizador_lista(siguiente(loc,l)))
   {   
      texto_t texto_sig=texto_info(info_lista(siguiente(loc,l),l));
      texto_t texto_actual=texto_info(info_lista(loc,l));
      if (comparar_texto(texto_sig,texto_actual)==mayor)
      {baux=baux->der; caux.ramas=der; i++;}
      else
      {baux=baux->izq; caux.ramas=izq; i++;}
   }   
   }
   
   loc=siguiente(loc,l);
   }
   if (!es_localizador_lista(loc) && altura_binario(baux)==1){caux.existe=bandera; caux.cantidad_ramas=i;}
   else {delete[] caux.ramas;}
   return caux;
}


(localizador es un puntero a un nodo de la lista)

De todas formas otras funciones tenian error y me quedé sin pasar todos los test que le hacen...mañana me dan el resultado pero creo que perdí el curso...  :-\


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines