Laberinto con arboles en C
1.0.-OBJETIVOS
El principal objetivo nuestro a través del desarrollo de esta aplicación es ampliar nuestros conocimientos sobre estructuras de datos dinámicos como lo son las listas y los árboles.
Aprender sobre el uso de grafos y como trabajar con el modo grafico interactuando con el modo texto.
Conocer más a fondo el lenguaje de programación C.
Poder hacernos acreedores de una nota y así poder aprobar la materia.
1.1.-JUSTIFICACIÓN
Hemos decidido realizar este proyecto por que nos pareció bastante interesante el uso que le podemos dar a las estructuras llamadas árboles y su diversa aplicación en muchos campos; además nos pareció interesante la forma como combinar varias estructuras en el mismo proyecto en nuestro caso listas doblemente enlazadas y árboles; a mas de eso nos percatamos que era un reto no tan fácil y fue una razón mas para inclinarnos por este proyecto.
1.2.-UTILIDAD INMEDIATA
La utilidad inmediata Constituye la de estudiar a profundidad el lenguaje de programación C y las estructuras de datos que podemos utilizar en este complejo lenguaje; además que nos sirve de modelo para la realización de otros trabajos de la misma naturaleza en el difícil camino hacia la obtención de nuestro titulo.
1.3.-AGRADECIMIENTOS
Este trabajo no hubiese sido posible sin la ayuda de nuestro profesor el ING. Víctor Poma quien con mucha paciencia nos supo guiar con sus conocimientos; nos nuestros sinceros agradecimientos.
2.0.-ANALISIS
2.1.-DEFINICIÓN FORMAL DEL PROBLEMA
Los árboles son estructuras de datos muy importantes en informática y en ciencias de la computación, son usados para representar formulas algebraicas como un método eficiente para la búsquedas grandes y complejas y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado.
A nuestra aplicación la hemos denominado laberinto, la misma que consiste en construir dinámicamente un laberinto utilizando grafos para luego realizar búsquedas sobre el mismo.
Para lo cual el usuario deberá ingresar los nodos; por ejemplo:
Ingrese los nodos: A,B,C,D,E,F,G,H,I,J,K
Posteriormente deberá ingresar las rutas o sea como estarán unidos los nodos; por ejemplo:
Ingrese los nodos a unir: A C , AB, AF, BH, BG, CD, CE, EB, EI, IJ, JK
Por ultimo nuestra aplicación deberá realizar una tarea de búsqueda estableciendo una posición de partida a la que podemos llamar partida y una posición de llegada a la que llamaremos meta. Asumiendo que un individuo se encuentra en la partida deberá recorrer el grafo hasta encontrar la meta, en caso de que después de haber recorrido el árbol, la meta no ha sido encontrada se tiene que presentar un mensaje en el cual se informe que la meta no ha sido encontrada.
2.3-DESCRIPCION DEL PROYECTO
Nuestra aplicación ha sido desarrollada en Turbo C, por que nos brinda un poco mas de facilidades al trabajar con el modo grafico; el programa ha sido construido usando listas doblemente enlazadas pero pudimos haberlo hecho con listas simples sin ningún problema.
cuando ejecutamos este trabajo nos pide que ingresemos el numero de nodos a graficar; solo podemos ingresar un numero máximo de 10, estos deberán ser letras; luego nos pedirá que ingresemos el nombre de los nodos; a continuación los nodos se graficaran en posiciones que el programa genera aleatoriamente cuidando que entre cada nodo haya una distancia considerable por efectos de visualización; posteriormente nos solicitara que ingresemos los pares ordenados, los que deseamos que se unan con una línea y el programa graficara una línea de color amarillo uniendo ambos nodos que ingreso el usuario, para seguir uniendo nodos la aplicación nos pedirá una opción podemos ingresar cualquier numero excepto el numero 2 ya que con ese numero salimos de aplicación; por ultimo si deseamos encontrar las rutas de un nodo partida a un nodo llegada el programa nos pedirá que ingresemos el nodo de partida y el nodo de llegada recorre el árbol y si lo encuentra las líneas cambian de color; en caso contrario presenta un mensaje que el nodo no ha sido encontrado.
3.0.-DISEÑO
3.1.-DEFINICIÓN DE ESTRUCTURAS
En nuestra aplicación hemos construido 1 estructura llamada Nodo:
struct Nodo{
char dato[1];
struct Nodo *conect[5];
struct Nodo *sig;
struct Nodo *ant;
int x;
int y;
};
El campo dato es una variable de tipo char que va a almacenar el nombre del nodo.
El campo *conect es un arreglo de cinco apuntadores.
El campo *sig es un apuntador que va a puntar al siguiente nodo de la lista doblemente enlazada.
El campo *ant es un apuntador que va a puntar al nodo anterior de la lista doblemente enlazada.
Las variables X y Y nos sirven para almacenar los valores que va a tener en la pantalla cada nodo para poderlos dibujar posteriormente.
3.2.-DEFINICIÓN DE CLASES (RELACIONES)
En la presente aplicación tenemos la clase NodosBusqueda la cual contendrá todos los métodos públicos y privados que se utilizaran para desarrollar el grafo de búsqueda con nodos.
3.3.-DISEÑO DE LA INTERFAZ
La interfaz grafica consta de dos espacios, en el primer espacio se realizaran las peticiones por parte del usuario; y en la otra parte se verán reflejadas los cambios que el usuario realice de modo grafico.
Ingrese el numero de nodos del grafo
->3
Ingrese los nodos
Nodo [1] ->a
Nodo [2] ->b
Nodo [3] ->c
Esta es lo que tenemos en pantalla antes de que los nodos sean graficados.
4.0.- IMPLEMENTACIÓN
4.1.- IMPLEMENTACIÓN DE LA CLASE
Hemos implementado una clase en nuestra aplicación llamada NodosBusqueda.
class NodosBusqueda{
private:
struct Nodo *cab, *col;
public:
NodosBusqueda();
void Presentacion(void);
void Insertar(char dat[1], int posx,int posy);
void DibujarNodos();
void DibujarLineasNodos();
void LlenarIndice();
void UnirNodos(char nod[3]);
};
La clase NodosBusqueda contendrá todos los métodos que se implementaran en la aplicación para su desarrollo.
Struct Nodo *cab: Es una estructura que nos permite obtener la dirección del primer elemento de la lista para poder realizar operaciones en ella.
Struct Nodo *col: Es una estructura que nos permite obtener la dirección del último elemento de la lista.
NodosBusqueda(): es el constructor que inicializa la cabeza y la cola de la lista.
Todas las operaciones a realizar son de tipo público; para su utilización dentro y fuera de la clase.
4.2.-DOCUMENTACION DE CADA UNO DE LOS METODOS
En nuestra clase NodosBusqueda hemos implementado los siguientes métodos:
void Presentacion(void) :Este método nos sirve para presentar una introducción del proyecto antes de la utilización del proyecto.
void Insertar(char dat[1], int posx,int posy) :Método que nos sirve para insertar elementos en una lista doblemente enlazada recibe la información del nodo y las coordenadas del nodo tanto en x como en y respectivamente para poder dibujarlo.
void DibujarNodos(): Método que utilizamos para poder recorrer la lista doblemente enlazada y por cada nodo recorrido dibujarlo en la pantalla de a cuerdo con sus coordenadas; la función utilizada para dibujar el circulo es circle(x,y,r) x, y son las coordenadas y r es el radio del circulo; outtextxy(x,y,str) x y son las coordenadas para que el string se dibuje en las coordenadas respectivas .
void DibujarLineasNodos(): Método que nos permite dibujar las líneas que unen los nodos para cual utilizamos la función line(x,y,x,y) son pares ordenados el primer par nos sirve para el punto de partida y el segundo par para el punto de llegada de la línea.
void LlenarIndice(): Método que utilizamos para llenar dos arreglo de tipo entero de forma aleatoria, cada elemento del arreglo será único; los enteros que se llenaran serán con valores menores a 12 y 9 respectivamente que sirven como índices para ubicar a cada nodo en una posición especifica en la pantalla.
void UnirNodos(char nod[3]): Método que usamos para enlazar los nodos de acuerdo a lo que el usuario haya ingresado utilizando el arreglo de apuntadores que tiene cada estructura en este caso conect, y recibimos los nodos a ingresar dependiendo del criterio del usuario.
5.0.-PRUEBAS
5.1.-PROBAR CON TODOS LOS POSIBLE CASOS
El programa funciona para todos los casos posibles; pudiendo insertar un número de 10 nodos; si deseamos unir dos nodos por ejemplo AB y luego unimos AB la línea se rescribe.
Si intentamos graficar más de 10 nodos no podremos ya que solo graficar un número máximo de 10.
Si deseamos unir un nodo que si existe con otro que no existe el programa presenta nodo no encontrado.
Si por ejemplo unimos el nodo AB y luego queremos unir el nodo BA no nos permite pues nos confundiríamos con el número de arista de cada nodo.
Cada nodo solo podrá tener un número máximo de 5 aristas o conexiones si excedemos ese número nos dará un error.
6.0.-CONCLUCIONES
Como conclusiones podemos decir que la aplicación de estructuras de datos es muy importante en nuestra carrera y por eso debemos tener un amplio conocimiento sobre esta materia, pues nos sirven de mucho a lo largo de nuestra carrera e inclusive cuando ejerzamos nuestra profesión nos podemos topar con estas estructuras.
Podemos concluir que este proyecto nos ha sido de mucha ayuda ya que nos ha permitido aprender muchas cosas nuevas e interesantes, además nos ha servido de gran ayuda para entender un poco mas a fondo el lenguaje, pues no se trata de un lenguaje de fácil entendimiento.
7.0 BIBLIOGRAFIA
Luís Joyanes Aguilar. Algoritmos y estructura de datos. Editorial McGraw Hill.
Evelio Granizo Montalvo. Programación Estructurada en pseudos códigos.
Lipshutz Clifford. Estructura de datos. Editorial McGraw Hill.
Internet. HYPERLINK "http://www.google.com" www.google.com , HYPERLINK "http://www.wikipedia.org" www.wikipedia.org
