Story Transcript
Autorizada la entrega del proyecto del alumno: Jorge Barca Orden
EL DIRECTOR DEL PROYECTO Eduardo Alcalde Lancharro
Fdo.:…………………………. Fecha: …… /…… /……
Vº Bº del Coordinador de Proyectos Eduardo Alcalde Lancharro
Fdo.:…………………………. Fecha: …… /…… /……
UNIVERSIDAD PONTIFICIA COMILLAS ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI) INGENIERO TECNICO EN INFORMÁTICA DE SISTEMAS
PROYECTO FIN DE CARRERA
TUTORIAL GRÁFICO DE ESTRUCTURAS DINÁMICAS DE DATOS (ÁRBOLES)
AUTOR: JORGE BARCA ORDEN MADRID, JUNIO DE 2007
A mis padres y a Isabel por estar ahí durante el desarrollo del proyecto y animarme en los momentos más difíciles.
A mis amigos por ayudarme en todo lo que han podido, en especial a Paz, Loic e Isabel por ayudarme con las traducciones del y al inglés.
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Resumen La finalidad de este proyecto es crear un tutorial sobre el uso de las estructuras dinámicas de datos, en concreto los árboles. Este tutorial debe ayudar a entender el funcionamiento de dichas estructuras de una manera gráfica y sencilla para que, de este modo, el usuario siente unas bases sólidas sobre el tema y pueda profundizar más en él sin muchas complicaciones.
Los objetivos fundamentales de esta aplicación son:
a. Conseguir un aprendizaje del uso de los árboles desde un nivel sencillo, aumentando la complejidad a medida que el usuario vaya ampliando sus conocimientos. Llegando a un nivel intermedio.
b. Enseñar las operaciones básicas para el uso de los árboles, como pueden ser inserciones, modificaciones, eliminaciones, búsquedas y recorrido.
c. Mostrar el uso de los árboles en un lenguaje en concreto, como puede ser el C, y extrapolarlo a cualquier lenguaje mostrando al usuario un pseudocódigo de las operaciones antes mencionadas
d. Conseguir la mayor interactividad posible con el usuario mostrándole, de manera gráfica, qué es lo que está ocurriendo exactamente con la estructura dinámica, el árbol, mediante ejemplos propuestos.
I
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
e. Hacer ver al usuario las ventajas del uso de estructuras dinámicas frente a las estáticas.
El proyecto se desarrollará en un entorno visual y para ello se programará con Visual Basic. El entorno de desarrollo escogido para este lenguaje es el Microsoft Visual Studio 6.0.
La aplicación podrá ser ejecutada tanto de manera local como de manera remota. Para la ejecución remota se contará con un servidor de aplicaciones y una página Web.
La implementación del proyecto se hará sólo de la parte local, dejando proyectada la parte remota para una futura programación.
II
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Abstract The purpose of this project is to create a tutorial of the use of a kind of dynamic data structures, the trees. This tutorial must help to understand the way this kind of structures works in a graphic and simple way, so that the user can build the solid basics in this area and therefore can go further into it without too many difficulties.
The main objectives of this application are:
a. To learn about the use of trees, starting from a simple level and increasing the complexity of the knowledge in this area as the user goes further into it, until an intermediate level is reached. b. To teach the basic operations for the use of trees, such as: additions, modifications, deletions, searching, and tracking. c. To show the use of the trees in a specific programming language, as can be C language, so that the users can generalize back to any other language once they know the pseudocode of the operations mentioned before. d. To obtain as much interactivity as possible with the users by showing them graphically what is happening exactly, with that dynamic structure using the proposed examples. e. To make the user see the advantages of the use of dynamic structures over the static ones.
III
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
The project will be developed in a visual environment. Therefore it will be programmed using Visual Basic. The developing environment chosen for this task is the Microsoft Visual Studio 6.0.
The application can be run locally as well as remotely. For the running of the remote way there will be an application server and a web page.
In this version of the application the local part will be the only one developed. The remote part will be left aside for future versions.
IV
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Índice RESUMEN .......................................................................................................... I ABSTRACT....................................................................................................... III ÍNDICE ...............................................................................................................V FIGURAS ........................................................................................................VIII 1
INTRODUCCIÓN ........................................................................................ 1 1.1
RESUMEN DE LA APLICACIÓN ................................................................... 1
1.2
INTRODUCCIÓN AL OBJETO DEL TUTORIAL: LOS ÁRBOLES ............................ 3
1.2.1 Definición de árbol............................................................................ 4 1.2.2 Tipos de árboles ............................................................................... 5
2
3
1.2.2.1
Árboles Genéricos............................................................................... 5
1.2.2.2
Árboles binarios .................................................................................. 6
1.2.2.3
Árboles Binarios de Búsqueda (ABB) ................................................. 6
1.2.2.4
Árboles de Adelson-Velskii y Landis (AVL) ......................................... 7
IDENTIFICACIÓN DE NECESIDADES ...................................................... 8 2.1
OBJETIVOS DE LA APLICACIÓN.................................................................. 8
2.2
ALCANCE DEL SISTEMA.......................................................................... 10
2.3
TIPOLOGÍA DE USUARIOS FINALES .......................................................... 10
2.4
RESTRICCIONES ................................................................................... 11
2.5
ANTECEDENTES ................................................................................... 11
ANÁLISIS DE REQUISITOS .................................................................... 13 3.1
RECONOCIMIENTO DEL PROBLEMA ......................................................... 13
3.1.1 Ámbito del proyecto........................................................................ 13 V
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3.1.2 Contexto general del sistema ......................................................... 14 3.1.3 Matriz de funciones ........................................................................ 15 3.2 4
LISTA DE REQUISITOS ............................................................................ 16
DISEÑO INTERNO ................................................................................... 22 4.1
DISEÑO DEL SISTEMA ACTUAL ................................................................ 22
4.2
DISEÑO DEL NUEVO SISTEMA ................................................................. 24
4.2.1 Nivel contextual .............................................................................. 24 4.2.2 Nivel conceptual ............................................................................. 25
5
4.2.2.1
Primer nivel ....................................................................................... 25
4.2.2.2
Segundo nivel: Explotación de Buscar práctica ................................ 32
4.2.2.3
Segundo Nivel: Explotación de Buscar Teoría.................................. 37
4.2.2.4
Tercer nivel: Explotación de Actualizar AVL ..................................... 41
4.2.2.5
Tercer nivel: Explotación de Actualizar ABB ..................................... 51
DISEÑO EXTERNO .................................................................................. 60 5.1
DISEÑO DE ENTRADAS Y SALIDAS. INTERFAZ DE USUARIO. ........................ 60
5.1.1 Formulario de teoría ....................................................................... 62 5.1.2 Formulario de práctica.................................................................... 64 6
PROGRAMACIÓN .................................................................................... 69 6.1
LISTA DE FUNCIONES ............................................................................ 69
6.1.1 Formulario principal ........................................................................ 69 6.1.2 Formulario de teoría ....................................................................... 69 6.1.3 Formulario de práctica.................................................................... 70 6.1.3.1
Funciones generales ......................................................................... 70
6.1.3.2
Funciones propias de los AVL .......................................................... 71
6.1.4 Formulario de Complementos ........................................................ 71 VI
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6.1.5 Módulo Externo .............................................................................. 71 6.1.6 Objeto Nodo ................................................................................... 72 6.2
MANUAL DE USUARIO ............................................................................ 73
Figuras ...................................................................................................... 76 1.
Introducción a la aplicación................................................................ 77
2.
Requisitos mínimos............................................................................ 78
3.
Instalación.......................................................................................... 79
4.
Utilización........................................................................................... 81 a.
Ejecución................................................................................................... 81
b.
Teoría........................................................................................................ 81
c.
Práctica ..................................................................................................... 83
d.
Complementos .......................................................................................... 85
5.
6. 7
Posibles errores ................................................................................. 86 a.
Teoría........................................................................................................ 86
b.
Práctica ..................................................................................................... 86
c.
Complementos .......................................................................................... 88
Desinstalación.................................................................................... 88
PRUEBAS................................................................................................. 89 7.1
PRUEBAS EN EL FORMULARIO PRINCIPAL ................................................. 89
7.2
PRUEBAS EN EL FORMULARIO DE TEORÍA ................................................ 90
7.3
PRUEBAS EN EL FORMULARIO DE PRÁCTICA............................................. 91
8
VALORACIÓN ECONÓMICA Y PLANIFICACIÓN .................................. 94
9
CONCLUSIONES ..................................................................................... 97
10 BIBLIOGRAFÍA ........................................................................................ 98
VII
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Figuras Figura 1 Nodo con 3 punteros. .......................................................................... 4 Figura 2 Árbol binario. ....................................................................................... 5 Figura 3 Diagrama de presentación ................................................................ 14 Figura 4 DFD del sistema actual. .................................................................... 23 Figura 5 DFD del nivel contextual del TGED-A. .............................................. 24 Figura 6 DFD del primer nivel.......................................................................... 25 Figura 7 DFD de la explotación de Buscar práctica......................................... 32 Figura 8 DFD de explotación del proceso Buscar teoría. ................................ 37 Figura 9 DFD de la explotación de Actualizar AVL.......................................... 41 Figura 10 DFD de la explotación de Actualizar ABB. ...................................... 51 Figura 11 Formulario principal ......................................................................... 60 Figura 12 Formulario de Teoría. ...................................................................... 62 Figura 13 Formulario de Práctica. ................................................................... 64 Figura 14 Menú Complementos ...................................................................... 66 Figura 15 Ejemplo 1 de Formulario de Complementos. .................................. 68 Figura 16 Ejemplo 2 de Formulario de Complementos. .................................. 68 Figura 17 Etiquetas de título............................................................................ 90 Figura 18 Botones “Anterior” y “Siguiente” deshabilitados. ............................. 90 Figura 19 Botones “Buscar” e “Insertar” deshabilitados. ................................. 91 Figura 20 Error producido si el usuario no introduce un número. .................... 91 Figura 21 Error producido si el usuario introduce un número fuera de rango.. 91 Figura 22 Error producido cuando el usuario intenta insertar un nodo que ya existe. ............................................................................................................... 92
VIII
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Figura 23 Error producido cuando el usuario intenta buscar o eliminar un nodo que no existe. ................................................................................................... 92 Figura 24 Error producido si el usuario intenta insertar un nodo que hace que el árbol supere la altura máxima. ......................................................................... 93 Figura 25 Error producido si el usuario intenta insertar un nodo que hace que el árbol supere la altura máxima. ......................................................................... 93 Figura 26 Planificación temporal. .................................................................... 94 Figura 27 Tabla de tarifas................................................................................ 94 Figura 28 Tabla de licencias............................................................................ 95
IX
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
1 Introducción 1.1 Resumen de la aplicación La finalidad de este proyecto es crear un tutorial sobre el uso de las estructuras dinámicas de datos, en concreto los árboles. Este tutorial debe ayudar a entender el funcionamiento de dichas estructuras de una manera gráfica y sencilla para que, de este modo, el usuario siente unas bases sólidas sobre el tema y pueda profundizar más en él sin muchas complicaciones.
Los objetivos fundamentales de esta aplicación son:
f. Conseguir un aprendizaje del uso de los árboles desde un nivel sencillo, aumentando la complejidad a medida que el usuario vaya ampliando sus conocimientos. Llegando a un nivel intermedio.
g. Enseñar las operaciones básicas para el uso de los árboles, como pueden
ser
inserciones,
modificaciones,
eliminaciones,
búsquedas y recorrido.
h. Mostrar el uso de los árboles en un lenguaje en concreto, como puede ser el C, y extrapolarlo a cualquier lenguaje mostrando al usuario un pseudocódigo de las operaciones antes mencionadas
i. 1
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
j.
Conseguir la mayor interactividad posible con el usuario mostrándole, de manera gráfica, qué es lo que está ocurriendo exactamente con la estructura dinámica, el árbol, mediante ejemplos propuestos.
k. Hacer ver al usuario las ventajas del uso de estructuras dinámicas frente a las estáticas.
El proyecto se desarrollará en un entorno visual y para ello se programará con Visual Basic. El entorno de desarrollo escogido para este lenguaje es el Microsoft Visual Studio 6.0.
La aplicación podrá ser ejecutada tanto de manera local como de manera remota. Para la ejecución remota se contará con un servidor de aplicaciones y una página Web.
La implementación del proyecto se hará sólo de la parte local, dejando proyectada la parte remota para una futura programación.
2
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
1.2 Introducción al objeto del tutorial: los árboles Para entender el concepto de árbol hay que entender primero el concepto de Estructura dinámica de datos.
La mayoría de lenguajes de programación proporcionan al desarrollador estructuras capaces de almacenar conjuntos de elementos pero tienen una importante limitación: no pueden cambiar su tamaño durante la ejecución. Las tablas, por ejemplo, pueden ser declaradas dinámicas pero una vez creadas no se pueden aumentar o reducir, en caso de querer ampliar su capacidad se deben rehacer desde cero.
Las estructuras dinámicas nos permiten ajustar el tamaño a la necesidad real en cada momento puesto que están compuestas por unidades independientes entre sí y enlazadas mediante punteros 1 . Otra ventaja que se extrae de esto es que se puede tratar cada elemento como único, sin tener en cuenta el resto del conjunto.
1
Puntero: Variable que almacena una dirección de memoria. Normalmente, cuando una
variable contiene la dirección de memoria de otra, se dice que la primera apunta a la segunda.
3
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Las estructuras dinámicas de datos están presentes en la mayoría de aplicaciones informáticas. Sin ir más lejos, en los sistemas operativos, los recursos de la máquina se gestionan mediante pilas y colas. Los árboles binarios proporcionan una gran velocidad y eficiencia a la hora de realizar búsquedas y ordenaciones. En UNIX, por ejemplo, toda la gestión del, nunca mejor llamado, árbol de directorios, se realiza mediante árboles de diferentes niveles facilitando así la búsqueda de un fichero.
1.2.1 Definición de árbol Las estructuras dinámicas de datos están compuestas por elementos individuales llamados nodos.
Nodo: Elemento mínimo de una estructura de datos compuesto por información y uno o varios punteros.
Figura 1 Nodo con 3 punteros.
4
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Árbol: Estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
Figura 2 Árbol binario.
1.2.2 Tipos de árboles Existen varios tipos de árboles. Éstos se diferencian o por el número de punteros o bien por cómo estén distribuidos los datos dentro del árbol. 1. Árboles genéricos. 2. Árboles binarios. 3. Árboles Binarios de Búsqueda (ABB). 4. Árboles AVL.
1.2.2.1 Árboles Genéricos Esta categoría engloba a todos los árboles. Éstos pueden ser desde orden 2 (si fuese de orden 1 sería una lista) hasta orden N. No presentan ninguna restricción. 5
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
1.2.2.2 Árboles binarios Estos árboles son un subconjunto de los árboles genéricos formado por todos los árboles de orden 2. Se caracterizan por tener sólo dos punteros, normalmente designados por izquierda y derecha. No presentan ningún tipo de restricción más y su uso es simple (Véase Figura 2).
1.2.2.3 Árboles Binarios de Búsqueda (ABB) Es una especificación de los árboles binarios. Su estructura es idéntica a éstos pero deben estar ordenados de forma que para cada nodo se cumple que, todos los elementos de su subárbol izquierdo son menores que él y todos los elementos del subárbol derecho son mayores.
Esta restricción conllevará que, al insertar un elemento, no puede hacerse en cualquier parte si se quiere que el árbol siga estando ordenado. Deberá hacerse donde corresponda. Esto lo se conseguirá entrando en el nodo raíz y de ahí se comprueba si es mayor o menor que el que se está tratando, si es mayor se seguirá por la derecha y si es menor por la izquierda. Este proceso se repetirá hasta que se encuentre el hueco donde debería ir.
6
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
1.2.2.4 Árboles de Adelson-Velskii y Landis (AVL) Los Árboles de Adelson-Velskii y Landis son un subconjunto de los Árboles Binarios de Búsqueda tal que para cada nodo, la altura de su subárbol derecho y la altura de su subárbol izquierdo no puede diferir en más de una unidad.
Esta restricción conlleva que al insertar o eliminar un nodo, se debe calcular, y recolocar el árbol siempre que se incumpla, para que siga siendo un Árbol de Adelson-Velskii y Landis.
7
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
2 Identificación de necesidades En esta parte del proyecto se define el problema concreto a resolver y se acota en universo de discurso del mismo. Con esto se obtiene el conjunto de requisitos básicos que la aplicación debe cumplir.
2.1 Objetivos de la aplicación El objetivo principal es desarrollar una aplicación para la ayuda al aprendizaje del uso de las estructuras dinámicas de datos, en concreto los árboles. Se ayudará al alumno a entender cómo funcionan los diferentes tipos de árboles y para que se usa cada uno de ellos.
Al tratarse de una aplicación orientada a la enseñanza deberá incluir referencias teóricas sobre los árboles, así como la implementación en pseudocódigo de las diferentes rutinas (adición, modificación, eliminación, búsqueda y ordenación) y ejemplos reales en diferentes lenguajes de programación. El programa deberá contener también un apartado donde el alumno pueda observar gráficamente qué pasa en un árbol cuando insertamos, modificamos o eliminamos un nodo del mismo.
8
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Esta aplicación debe servir de herramienta de apoyo visual a los estudiantes que tratan por primera vez con árboles. Éste es el caso de los estudiantes de la asignatura de Estructura de datos que podrán buscar ayuda gráfica y sencilla en este tutorial para:
1. Aprender los conceptos fundamentales de los árboles y diferenciar los subtipos y sus aplicaciones prácticas. 2. Conocer en todo momento cómo está funcionando la estructura en cuestión y poder así manejarla con mayor soltura. 3. Conseguir abstraer la percepción del árbol a algo más que unas cuantas líneas de código. 4. Saber implementar un árbol en un lenguaje de programación concreto y poder realizar funciones básicas como añadir, buscar, o eliminar un nodo. 5. Valorar la eficacia de los árboles frente a otras formas de almacenar la información y comprender su uso en determinados programas.
9
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
2.2 Alcance del sistema Dada la existencia de gran variedad de estructuras dinámicas, este tutorial se centrará en los árboles como objeto de estudio. Para las estructuras de datos más simples, como las listas, pilas y colas, ya existe material didáctico similar a éste.
Este programa se ejecutará, de manera local, bajo el sistema operativo Microsoft Windows, preferiblemente en su versión XP. Y de manera remota mediante un navegador Web que soporte Visual Basic Script, preferiblemente Microsoft Internet Explorer. Esta limitación es debida a que se programará en Microsoft Visual Basic 6.0, lenguaje con una portabilidad prácticamente nula pero muy potente para la programación de aplicaciones Windows.
2.3 Tipología de usuarios finales La aplicación está dirigida principalmente a alumnos que cursen alguna asignatura en relación con las estructuras dinámicas de datos. Está hecha para que, de forma visual, entiendan como funcionan los árboles y asienten los conocimientos básicos sobre los mismos.
Por otro lado también podría ser utilizada por profesores que impartan materia relacionada con los árboles a modo de material de apoyo en clase.
10
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
2.4 Restricciones Este proyecto no presenta restricciones económicas ni temporales pero, al ser un proyecto desarrollado en Visual Basic, su instalación y uso se ven reducidos a equipos que funcionen con Windows o algún emulador de este sistema operativo para la ejecución local. Este problema viene dado por la prácticamente nula posibilidad de portar un sistema de Visual Basic a otro sistema operativo.
Para una ejecución online se necesitará un navegador que soporte Visual Basic Script, preferiblemente Microsoft Internet Explorer.
2.5 Antecedentes Puesto que no existen aplicaciones de este tipo no había forma de apreciar, visualmente, cómo funcionan los árboles y qué pasa con ellos cuando se produce un alta, una baja o una modificación.
Este problema puede llevar a que el alumno no sea capaz de imaginarse, a la hora de programar, qué está ocurriendo en el árbol cuando, por ejemplo, se elimina un nodo. Para un programador es importante tener en mente una idea “gráfica” de qué está pasando con las variables y estructuras para no perder así el hilo del programa.
11
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Por otro lado, si en algún momento se necesitase documentar gráficamente lo que está ocurriendo con un árbol cuando se realiza cualquiera de las operaciones básicas 1 se podría hacer con esta aplicación.
1
Cuando se habla de operaciones básicas se refiere a: altas, bajas, modificaciones, búsquedas
y ordenaciones.
12
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3 Análisis de requisitos El objetivo de esta fase es especificar qué requisitos debe cumplir la aplicación, así como sus funciones y procedimientos.
3.1 Reconocimiento del problema 3.1.1 Ámbito del proyecto A partir de los objetivos expuestos en la fase de identificación de necesidades, se obtendrán las entidades principales del proyecto:
1.
USUARIO: Es quien ejecuta la aplicación. Éste puede ser un usuario que quiere aprender cómo funcionan los árboles o un profesor que imparta dicha materia. La ejecución puede ser local u online.
2.
SERVIDOR DE APLICACIONES: Es la entidad que ejecuta la aplicación cuando ésta se solicita de manera online. Antes de proceder a ejecutar la aplicación, el servidor de aplicaciones realizará una validación del usuario.
3.
PÁGINA WEB: Es la entidad que, cuando se trate de una ejecución online, mostrará lo que ejecuta el servidor de aplicaciones. Es decir, primero mostrará lo necesario para la validación del usuario y, una vez validado, mostrará la ejecución de la aplicación.
4.
EQUIPO LOCAL: Esta entidad es la que ejecuta la aplicación en caso de una ejecución de manera local.
13
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3.1.2 Contexto general del sistema El contexto general del sistema se representará mediante un diagrama de presentación donde se muestra la interacción de las entidades antes descritas:
Figura 3 Diagrama de presentación
En el diagrama de presentación no se ha tenido en cuenta el tipo de usuario ni la validación del mismo. Esto es debido a que la interrelación de las entidades es independiente del tipo de usuario.
14
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3.1.3 Matriz de funciones En ese apartado se enumerará de forma esquematizada las funciones que realiza cada entidad anteriormente expuesta.
ENTIDAD
USUARIO
FUNCIONES •
Introduce usuario y clave.
•
Realiza una petición de ejecución al servidor de aplicaciones.
SERVIDOR DE APLICACIONES
•
Ejecuta la aplicación de manera local.
•
Recibe la petición de ejecución.
•
Recibe usuario y clave.
•
Valida al usuario.
•
Envía a la página Web la información necesaria para mostrar la aplicación.
•
Realiza una petición de ejecución al servidor de aplicaciones
PÁGINA WEB
•
Muestra la aplicación
EQUIPO LOCAL
•
Ejecuta la aplicación
15
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3.2 Lista de requisitos A continuación se expondrán los requisitos que debe cumplir la aplicación.
Los requisitos tendrán un código que lo identificará unívocamente del resto. Cada requisito contará con un título y una descripción.
LRQ01. Inserción de un nodo en un árbol binario de búsqueda. •
El usuario deberá poder insertar un nodo en un Árbol Binario de Búsqueda. Cuando se alcance el número máximo de nodos a insertar, se mostrará un aviso,
•
El nodo se insertará en el lugar que le corresponda para que la estructura no deje de ser un árbol binario de búsqueda.
•
El tiempo de inserción de un nodo en un árbol no ha de ser superior a 2 segundos.
LRQ02. Eliminación de un nodo en un árbol binario de búsqueda. •
El usuario podrá eliminar el nodo que desee del árbol binario de búsqueda. Si el nodo no existe se mostrará un mensaje de aviso.
•
El tiempo de eliminación de un nodo de un Árbol Binario de Búsqueda no será superior a 2 segundos.
16
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
LRQ03. Búsqueda de un nodo en un Árbol Binario de Búsqueda. •
El usuario podrá buscar un nodo en un Árbol Binario de Búsqueda. Si el nodo no existe se mostrará un mensaje de aviso.
•
El tiempo de búsqueda de un nodo en un Árbol Binario de Búsqueda no será superior a 2 segundos.
LRQ04. Recorrido en Preorden de un Árbol Binario de Búsqueda. •
El usuario podrá consultar el recorrido en preorden de un Árbol Binario de Búsqueda en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
LRQ05. Recorrido en Inorden de un Árbol Binario de Búsqueda. •
El usuario podrá consultar el recorrido en inorden de un Árbol Binario de Búsqueda en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
LRQ06. Recorrido en Postorden de un Árbol Binario de Búsqueda. •
El usuario podrá consultar el recorrido en postorden de un Árbol Binario de Búsqueda en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
17
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
LRQ07. Inserción de un nodo en un Árbol de Adelson-Velskii y Landis. •
El
usuario deberá poder insertar un nodo en un Árbol de
Adelson-Velskii y Landis. Cuando se alcance el número máximo de nodos a insertar, se mostrará un aviso, •
El nodo se insertará en el lugar que le corresponda para que la estructura no deje de ser un Árbol de Adelson-Velskii y Landis. La aplicación reordenará el árbol si fuese necesario.
•
El tiempo de inserción de un nodo en un árbol no ha de ser superior a 3 segundos.
LRQ08. Eliminación de un nodo en un árbol binario de búsqueda. •
El usuario podrá eliminar el nodo que desee del Árbol de AdelsonVelskii y Landis. Si el nodo no existe se mostrará un mensaje de aviso.
•
Si para mantener la condición de Árbol de Adelson-Velskii y Landis es necesaria una recolocación del árbol, la aplicación la llevará a cabo.
•
El tiempo de eliminación de un nodo de un Árbol de AdelsonVelskii y Landis no será superior a 3 segundos.
18
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
LRQ09. Búsqueda de un nodo en un Árbol de Adelson-Velskii y Landis. •
El usuario podrá buscar un nodo en un Árbol de Adelson-Velskii y Landis. Si el nodo no existe se mostrará un mensaje de aviso.
•
El tiempo de búsqueda de un nodo en un Árbol de Adelson-Velskii y Landis no será superior a 2 segundos.
LRQ10. Recorrido en Preorden de un Árbol de Adelson-Velskii y Landis. •
El usuario podrá consultar el recorrido en preorden de un Árbol de Adelson-Velskii y Landis en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
LRQ11. Recorrido en Inorden de un Árbol de Adelson-Velskii y Landis. •
El usuario podrá consultar el recorrido en inorden de un Árbol de Adelson-Velskii y Landis en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
LRQ12. Recorrido en Postorden de un Árbol de Adelson-Velskii y Landis. •
El usuario podrá consultar el recorrido en postorden de un Árbol de Adelson-Velskii y Landis en cualquier momento.
•
El tiempo de espera para esta consulta no será superior a 2 segundos. 19
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
LRQ13. Consulta de la teoría general de Árboles. •
El usuario podrá consultar la teoría general de árboles mediante un formulario aparte.
•
Esta teoría contendrá explicaciones sobre el funcionamiento de los árboles.
•
El tiempo de espera para esta consulta no deberá ser superior a 2 segundos.
LRQ14. Consulta de la teoría sobre Árboles Binarios de Búsqueda. •
El usuario podrá consultar la teoría específica sobre Árboles Binarios de Búsqueda mediante un formulario aparte.
•
Esta teoría contendrá explicaciones sobre el funcionamiento específico de este tipo de árboles.
•
El tiempo de espera para esta consulta no deberá ser superior a 2 segundos.
LRQ15. Consulta de la teoría sobre Árboles de Adelson-Velskii y Landis. •
El usuario podrá consultar la teoría específica sobre Árboles de Adelson-Velskii y Landis mediante un formulario aparte.
•
Esta teoría contendrá explicaciones sobre el funcionamiento específico de los Árboles de Adelson-Velskii y Landis.
20
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
LRQ16. Consulta de explicaciones puntuales. •
El usuario podrá consultar la explicación de una función en concreto en un formulario aparte.
•
Este formulario contendrá una explicación en castellano de la función deseada.
•
El tiempo de espera para esta consulta no será superior a 2 segundos.
LRQ17. Consulta de Pseudocódigos. •
El usuario podrá consultar el pseudocódigo de una función en concreto en un formulario aparte.
•
Este formulario contendrá el pseudocódigo en castellano de la función deseada.
•
El tiempo de espera para la consulta no será superior a 2 segundos.
LRQ18. Consulta de Códigos. •
El usuario podrá consultar el código de una función en concreto en un formulario aparte.
•
Este formulario contendrá el código de la función en el lenguaje de programación C.
•
El tiempo de espera para la consulta no será superior a 2 segundos.
21
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4 Diseño Interno 4.1 Diseño del sistema actual Al no existir ningún antecedente que resuelva el problema planteado se podría decir que la única herramienta con la que se contaba para ver, en tiempo real, como está funcionando un árbol, es la imaginación.
En lo referente a la teoría de árboles, podía ser consultada en libros o páginas Web. Esto conlleva un trabajo tedioso para el alumno puesto que ha de recopilar información de diferentes sitios. Este trabajo puede incluso llevar a equívocos puesto que, aunque la teoría de árboles siempre sea la misma, no todo el mundo la explica igual.
22
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Se puede representar todo este proceso mediante el siguiente DFD 1 :
Figura 4 DFD del sistema actual.
Como se puede apreciar en la Figura 4, hasta este momento, todo dependía de la imaginación del alumno, lo que no quiere decir que en el nuevo sistema sea obviada, simplemente se ayudará a agilizar el proceso de entendimiento de los conceptos.
1
DFD: Diagrama de Flujo de Datos.
23
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2 Diseño del nuevo sistema Una vez visto que es necesaria una herramienta que englobe todos los conocimientos que requiere el alumno sobre teoría de árboles así como una explicación gráfica del funcionamiento de los mismos, se procederá a explicar como funciona el nuevo sistema.
4.2.1 Nivel contextual El diagrama inicial, a nivel contextual, será el siguiente:
Figura 5 DFD del nivel contextual del TGED-A1.
Como se puede apreciar en la imagen el alumno sólo consultará información de una fuente, lo que facilita considerablemente el entendimiento de la misma. Además la información que recibirá el alumno está muy procesada y mostrada de una manera fácil y sencilla.
1
TGED-A: Tutorial Gráfico de Estructuras Dinámicas: Árboles
24
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2.2 Nivel conceptual En este apartado se procederá a explotar el proceso propuesto en el nivel contextual.
4.2.2.1 Primer nivel ► Diagrama El diagrama de flujo de datos del TGED-A quedaría de la siguiente forma:
Figura 6 DFD del primer nivel.
Como se puede apreciar en la Figura 6, el proceso tiene dos grandes partes, la parte teórica y la parte práctica.
25
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
► Definición de los procesos El diagrama consta de 5 burbujas 1 : Identificador
1. Proceso de solicitud
Explotación de
0.TGED-A
Diagrama
Esta burbuja representa la función de procesar la petición del usuario. Como se puede observar, le entran 2 tipos de datos, o bien una petición de información, que, como seve Descripción
en la Figura 5, viene del alumno, o bien una actualización de teoría por parte del profesor. En función de ese dato, mandará
la
información
necesaria
al
proceso
que
corresponda.
1
Burbuja: Palabra usada comúnmente, entre los informáticos, para hacer referencia a los
diferentes subprocesos en los que se divide la explotación de un proceso. Este nombre viene dado por su forma en los diagramas de flujo de datos.
26
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Teoría a actualizar: Dato introducido por el profesor que contiene la teoría a almacenar en el almacén de datos. Recibe
Solicitud de información: Dato introducido por el alumno que contiene la información de la función que desea realizar. Solicitud de práctica: Dato ya moldeado que contiene la información necesaria para acceder a la parte práctica del sistema. Solicitud de teoría: Dato ya moldeado que contiene la
Devuelve
información necesaria para acceder a la parte teórica del sistema. Teoría a actualizar: Dato ya moldeado que contiene la teoría que se quiere introducir en el almacén de información.
Observaciones
Ninguna.
27
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2. Buscar práctica
Explotación de
0.TGED-A
Diagrama
Este proceso es el encargado de buscar y generar la práctica que ha solicitado el usuario que, como se ve en la Descripción
Figura 6 viene desde la burbuja de Proceso de solicitud. Una vez haya procesado la información, la mandará al proceso encargado de mostrarla. Solicitud de práctica: Dato ya moldeado que contiene la
Recibe
información necesaria para acceder a la parte teórica del sistema. Práctica a mostrar: Dato concreto, de la parte práctica,
Devuelve requerido por el usuario. Observaciones
Ninguna.
28
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
3. Buscar teoría
Explotación de
0.TGED-A
Diagrama
Esta burbuja es la encargada de buscar la teoría pedida por el usuario, que viene dada por la burbuja Proceso de Descripción
solicitud, en el almacén de información Teoría. Cuando la obtenga, la mandará al proceso que le corresponda mostrarla. Solicitud de teoría: Dato ya moldeado que contiene la información necesaria para acceder a la parte teórica del
Recibe sistema. Teoría: Dato puro que se lee del almacén de información. Teoría a mostrar: Dato concreto, de la parte teórica, Devuelve requerido por el usuario. Observaciones
Ninguna.
29
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
4. Muestra información
Explotación de
0. TGED-A
Diagrama
Este proceso se encarga de mostrar la información, ya sea teoría o práctica, que ha recibido de los procesos Descripción
anteriores. Este proceso mandará la información hacia fuera del sistema y, como se puede apreciar en la Figura 5, la recibirá el usuario. Práctica a mostrar: Dato concreto de la parte práctica requerido por el usuario.
Recibe Teoría a mostrar: Dato concreto de la parte teórica requerido por el usuario. Devuelve
Información solicitada: Dato requerido por el usuario.
Observaciones
Ninguna.
30
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
5. Actualizar teoría
Explotación de
0. TGED-A
Diagrama
Esta burbuja es la encargada de actualizar la teoría Descripción
recibida, que como se ve en la Figura 5 proviene del profesor, en el almacén de información Teoría. Teoría a actualizar: Dato ya moldeado que contiene la
Recibe
teoría que se quiere introducir en el almacén de información. Teoría: Dato puro que se guarda en el almacén de
Devuelve información. Este proceso queda proyectado pero no será implementado Observaciones
en esta versión. La función de este proceso se realizará de forma manual.
31
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2.2.2 Segundo nivel: Explotación de Buscar práctica En esta sección se procede a explotar la burbuja Buscar práctica. ► Diagrama
Figura 7 DFD de la explotación de Buscar práctica.
Como se aprecia en la imagen se distingue dos tipos de información: la referente a los Árboles de Adelson-Velskii y Landis y la referente a los Árboles Binarios de Búsqueda.
32
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
► Definición de los procesos Como puede verse en la imagen, la explotación cuenta con 4 procesos: Identificador
2.1. Comprobar tipo
Explotación de
0. TGED-A Æ 2. Buscar Práctica
Diagrama
Proceso encargado de discernir si la información pertenece a una petición de un Árbol Binario de Búsqueda o de un Descripción
Árbol de Adelson-Velskii y Landis. Dependiendo del que sea, se mandará la petición al proceso encargado de gestionar el árbol en cuestión. Solicitud de práctica: Dato ya moldeado que contiene la
Recibe
información necesaria para acceder a la parte teórica del sistema. Tipo AVL: Dato que indica que la función a realizar pertenece a un Árbol de Adelson-Velskii y Landis.
Devuelve Tipo ABB: Dato que indica que la función a realizar pertenece a un Árbol Binario de Búsqueda. Observaciones
Ninguna.
33
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2. Actualizar AVL
Explotación de
0. TGED-A Æ 2. Buscar Práctica
Diagrama
Proceso encargado de gestionar las peticiones referentes a los Árboles de Adelson-Velskii y Landis. Esta petición puede ser un alta de un nodo, una baja, una eliminación, Descripción etc. Cuando haya hecho los cambios necesarios para esta actualización, enviará la información al proceso que corresponda. Tipo AVL: Dato que indica que la función a realizar Recibe pertenece a un Árbol de Adelson-Velskii y Landis. Información actualizada: Función requerida por el usuario. Devuelve Ya sea la actualización del árbol como un recorrido. Observaciones
Ninguna.
34
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3. Actualizar ABB
Explotación de
0. TGED-A Æ 2. Buscar Práctica
Diagrama
Proceso encargado de gestionar las peticiones referentes a los Árboles Binarios de Búsqueda. Esta petición puede ser Descripción
un alta de un nodo, una baja, una eliminación, etc. Cuando haya hecho los cambios necesarios para esta actualización, enviará la información al proceso que corresponda. Tipo ABB: Dato que indica que la función a realizar
Recibe pertenece a un Árbol Binario de Búsqueda. Información actualizada: Función requerida por el usuario. Devuelve Ya sea la actualización del árbol como un recorrido. Observaciones
Ninguna.
35
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.4. Devuelve información
Explotación de
0. TGED-A Æ 2. Buscar Práctica
Diagrama
Este proceso se encarga de devolver la información actualizada al proceso que corresponda, que, como puede Descripción verse en la Figura 6, será al proceso de Mostrar información. Información actualizada: Función requerida por el usuario. Recibe Ya sea la actualización del árbol como un recorrido. Práctica a mostrar: Devuelve el dato moldeado y Devuelve prácticamente listo para mostrarse al usuario. Observaciones
Ninguna.
36
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2.2.3 Segundo Nivel: Explotación de Buscar Teoría En esta sección se procede a explotar la burbuja Buscar teoría. ► Diagrama
Figura 8 DFD de explotación del proceso Buscar teoría.
Como se puede apreciar en la imagen, el proceso Buscar teoría se compone básicamente de un subproceso que recibe, uno que lee y otro que devuelve la información.
37
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
► Definición de los procesos. Como puede verse en el diagrama la explotación de este proceso se compone de 3 subprocesos: Identificador
3.1. Comprobar tipo
Explotación de
0. TGED-A Æ 3. Buscar Teoría
Diagrama
Proceso que se encarga de comprobar de qué tipo es la teoría que ha solicitado el usuario. Ésta puede ser de árboles generales, de Árboles de Adelson-Velskii y Landis o Descripción de Árboles Binarios de Búsqueda. Una vez sepa el tipo del que se trata, mandará la información al proceso encargado de leer del almacén de información. Solicitud de teoría: Dato ya moldeado que contiene la Recibe
información necesaria para acceder a la parte teórica del sistema.
Devuelve
Tipo: Dato que indica qué tipo de teoría requiere el usuario.
Observaciones
Ninguna.
38
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
3.2. Leer Teoría
Explotación de
0. TGED-A Æ 3. Buscar Teoría
Diagrama
Proceso que se encarga de leer la teoría del tipo que recibe del almacén de información. En esta versión del programa Descripción el almacén de información serán unos archivos de textos almacenados en el directorio de la aplicación. Tipo: Dato que indica qué tipo de teoría requiere el usuario. Recibe Teoría: Dato puro que se lee del almacén de información. Devuelve
Teoría: Dato tratado obtenido del almacén de información.
Observaciones
Ninguna.
39
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
3.3. Devuelve información:
Explotación de
0. TGED-A Æ 3. Buscar Teoría
Diagrama
Este proceso es el que se encarga de formatear la información que desea recibir el usuario para que el Descripción
entendimiento de la misma sea claro y conciso. Una vez la tenga formateada la pasará al proceso que la muestra al usuario.
Recibe
Teoría: Dato tratado obtenido del almacén de información. Teoría a mostrar: Dato concreto, de la parte teórica,
Devuelve requerido por el usuario. Observaciones
Ninguna.
40
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2.2.4 Tercer nivel: Explotación de Actualizar AVL En esta sección se procede a explotar la burbuja Actualizar AVL. ► Diagrama
Figura 9 DFD de la explotación de Actualizar AVL.
Como se puede observar en la Figura 9 aparece un subproceso que discrimina el tipo de operación a realizar, siete más que se encargan de realizar la operación y uno que devuelve los datos.
41
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
► Definición de los procesos Como puede observarse en el diagrama, esta explotación se compone de nueve subprocesos: Identificador
2.2.1 Determina tipo
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de determinar de qué tipo de Descripción
instrucción se trata. En función de eso, mandará lo necesario al proceso que le corresponda. Operación del Tipo AVL: Dato que indica que la función a
Recibe realizar pertenece a un Árbol de Adelson-Velskii y Landis. Todas las funciones que se pueden realizar: Inserción, Devuelve
Eliminación, Búsqueda, Recorrido en Preorden, Recorrido en Inorden y Recorrido en Postorden.
Observaciones
Ninguna.
42
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.2. Insertar nodo
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de insertar un nodo en el Árbol de Adelson-Velskii y Landis. Este proceso se encargará también Descripción
de que el árbol no pierda, por lo menos, la condición de Árbol Binario de Búsqueda. Cuando haya terminado, mandará el árbol con el nodo insertado al proceso que corresponda.
Recibe
Inserción: Dato del nuevo nodo a insertar. Árbol con nuevo nodo: Árbol con el nodo que el usuario
Devuelve quería insertar. Observaciones Ninguna.
43
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.3. Eliminar nodo
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de eliminar un nodo del Árbol de Adelson-Velskii y Landis. Este proceso se encargará también Descripción
de que el árbol no pierda, por lo menos, la condición de Árbol Binario de Búsqueda. Cuando termine con la eliminación enviará el árbol actualizado al proceso que corresponda.
Recibe
Eliminación: Dato con el nodo a eliminar.
Devuelve
Árbol sin el nodo: Árbol actualizado sin el nodo eliminado.
Observaciones Ninguna.
44
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.4. Buscar nodo
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Este proceso se encargará de encontrar un nodo, si existe, en Descripción
un Árbol de Adelson-Velskii y Landis. Cuando lo encuentre se lo mandará al proceso que corresponda.
Recibe
Búsqueda: Dato con el nodo a buscar.
Devuelve
Nodo deseado: Nodo requerido por el usuario.
Observaciones
45
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.5. Recorrer Preorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de calcular el recorrido en preorden de Descripción
un Árbol de Adelson-Velskii y Landis. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. Preorden: Dato que le indica que debe recorrer el árbol
Recibe en preorden. Devuelve
Recorrido: Dato que contiene el recorrido en preorden.
Observaciones Ninguna.
46
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.6. Recorrer Inorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de calcular el recorrido en inorden de Descripción
un Árbol de Adelson-Velskii y Landis. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. Inorden: Dato que le indica que debe recorrer el árbol en
Recibe inorden. Devuelve
Recorrido: Dato que contiene el recorrido en inorden.
Observaciones Ninguna.
47
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.7 Recorrer Postorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de calcular el recorrido en postorden Descripción
de un Árbol de Adelson-Velskii y Landis. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. postorden: Dato que le indica que debe recorrer el árbol
Recibe en postorden. Devuelve
Recorrido: Dato que contiene el recorrido en postorden.
Observaciones Ninguna.
48
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.8. Equilibrar
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Este proceso se encargará de recolocar el árbol para que no pierda la condición de Árbol de Adelson-Velskii y Landis. Descripción Cuando lo haya calculado lo mandará al proceso que corresponda. Árbol con nuevo nodo: Árbol con el nodo que el usuario Recibe
quería insertar. Árbol sin el nodo: Árbol actualizado sin el nodo eliminado. Árbol equilibrado: Árbol que cumple las condiciones de un
Devuelve Árbol de Adelson-Velskii y Landis. Observaciones
Ninguna.
49
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.9. Devolver solución
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de recibir de los demás procesos Descripción
la información requerida por el usuario, moldearla y mandarla al proceso que corresponda. Recorrido: Dato que contiene el recorrido calculado en cualquiera de los procesos anteriores.
Recibe
Nodo deseado: Nodo requerido por el usuario. Árbol equilibrado: Árbol que cumple las condiciones de un Árbol de Adelson-Velskii y Landis. Información actualizada: Dato que contiene la información
Devuelve requerida por el usuario prácticamente lista para mostrar. Observaciones
Ninguna.
50
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4.2.2.5 Tercer nivel: Explotación de Actualizar ABB En esta sección se procede a explotar la burbuja Actualizar ABB. ► Diagrama
Figura 10 DFD de la explotación de Actualizar ABB.
Como se puede observar en la Figura 10, hay un subproceso que discrimina el tipo de operación a realizar, seis más que se encargan de realizar la operación y uno que devuelve los datos.
51
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
► Definición de los procesos Como se observa en el diagrama, esta explotación se compone de 8 subprocesos: Identificador
2.2.1 Determina tipo
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de determinar de qué tipo de Descripción
instrucción se trata. En función de eso, mandará lo necesario al proceso que le corresponda. Operación del Tipo ABB: Dato que indica que la función a
Recibe realizar pertenece a un Árbol Binario de Búsqueda. Todas las funciones que se pueden realizar: Inserción, Devuelve
Eliminación, Búsqueda, Recorrido en Preorden, Recorrido en Inorden y Recorrido en Postorden.
Observaciones
Ninguna. 52
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3.2. Insertar nodo
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 2. Actualizar AVL
Diagrama
Proceso que se encarga de insertar un nodo en el Árbol Binario de Búsqueda. Este proceso se encargará también Descripción
de que el árbol no pierda su condición de Árbol Binario de Búsqueda. Cuando haya terminado, mandará el árbol con el nodo insertado al proceso que corresponda.
Recibe
Inserción: Dato del nuevo nodo a insertar. Árbol con nuevo nodo: Árbol con el nodo que el usuario
Devuelve quería insertar. Observaciones
Ninguna.
53
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3.3. Eliminar nodo
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de eliminar un nodo del Árbol Binario de Búsqueda. Este proceso se encargará también de que el Descripción
árbol no pierda su condición de Árbol Binario de Búsqueda. Cuando termine con la eliminación enviará el árbol actualizado al proceso que corresponda.
Recibe
Eliminación: Dato con el nodo a eliminar.
Devuelve
Árbol sin el nodo: Árbol actualizado sin el nodo eliminado.
Observaciones Ninguna.
54
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3.4. Buscar nodo
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Este proceso se encargará de encontrar un nodo, si existe, en Descripción
un Árbol Binario de Búsqueda. Cuando lo encuentre se lo mandará al proceso que corresponda.
Recibe
Búsqueda: Dato con el nodo a buscar.
Devuelve
Nodo deseado: Nodo requerido por el usuario.
Observaciones Ninguna
55
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3.5. Recorrer Preorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de calcular el recorrido en preorden Descripción
de un Árbol Binario de Búsqueda. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. Preorden: Dato que le indica que debe recorrer el árbol
Recibe en preorden. Devuelve
Recorrido: Dato que contiene el recorrido en preorden.
Observaciones Ninguna.
56
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
Recorrer Inorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de calcular el recorrido en inorden de Descripción
un Árbol Binario de Búsqueda. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. Inorden: Dato que le indica que debe recorrer el árbol en
Recibe inorden. Devuelve
Recorrido: Dato que contiene el recorrido en inorden.
Observaciones Ninguna.
57
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.3.7 Recorrer Postorden
Explotación de 0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de calcular el recorrido en postorden Descripción
de un Árbol Binario de Búsqueda. Cuando lo tenga calculado lo mandará al proceso que corresponda. Rec. postorden: Dato que le indica que debe recorrer el árbol
Recibe en postorden. Devuelve
Recorrido: Dato que contiene el recorrido en postorden.
Observaciones Ninguna.
58
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Identificador
2.2.8. Devolver solución
Explotación de
0. TGED-A Æ 2. Buscar Práctica Æ 3. Actualizar ABB
Diagrama
Proceso que se encarga de recibir de los demás procesos Descripción
la información requerida por el usuario, moldearla y mandarla al proceso que corresponda. Recorrido: Dato que contiene el recorrido calculado en cualquiera de los procesos anteriores. Nodo deseado: Nodo requerido por el usuario.
Recibe Árbol con nuevo nodo: Árbol con el nodo que el usuario quería insertar. Árbol sin el nodo: Árbol actualizado sin el nodo eliminado. Información actualizada: Dato que contiene la información Devuelve requerida por el usuario prácticamente lista para mostrar. Observaciones
Ninguna.
59
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
5 Diseño Externo 5.1 Diseño de entradas y salidas. Interfaz de usuario. En este apartado se mostrarán el diseño de las ventanas y controles con los que el usuario interactuará con la aplicación.
Figura 11 Formulario principal
El formulario principal será el que tenga los menús necesarios para la utilización de la aplicación. Asimismo será el contenedor de los demás formularios.
60
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Los menús que se pueden encontrar son: 1) Teoría. a) Árboles (General). -
Este menú abrirá el formulario que contiene la teoría general de árboles.
b) ABB. -
Este menú abrirá el formulario que contiene la teoría sobre Árboles Binarios de Búsqueda.
c) AVL. -
Este menú abrirá el formulario que contiene la teoría sobre Árboles de Adelson-Velskii y Landis.
2) Práctica a) ABB. -
Este menú abrirá el formulario con el que se interactuará con un Árbol Binario de Búsqueda.
b) AVL. -
Este menú abrirá el formulario con el que se interactuará con un Árbol de Adelson-Velskii y Landis
61
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Ahora se van a explicar cada uno de los formularios abierto por cada uno de los menús.
5.1.1 Formulario de teoría
Figura 12 Formulario de Teoría.
62
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
El formulario de teoría es igual para las 3 opciones posibles. Este formulario está formado por los siguientes elementos: •
Título: Se encuentra situado en la barra de título y corresponde al título de la teoría que contiene el formulario. En el caso de la imagen puede verse que contiene el texto: “Teoría general de árboles”.
•
Título de la página: Etiqueta situada en la parte superior del formulario que contiene el título de la página que se está mostrando. En el caso de la imagen se ve que contiene el texto: “Introducción”.
•
Cuadro de texto de teoría: Este cuadro de texto contendrá la teoría de la página que se está cargando. En el caso de que la teoría ocupe más que el tamaño del cuadro de texto, aparecerá la barra de desplazamiento (Scroll). En la imagen puede verse que contiene la Introducción de la Teoría general de árboles.
•
Botón “Anterior”: Botón que lleva a la página anterior. Se encontrará deshabilitado en caso de no existir página anterior.
•
Botón “Siguiente”: Botón que lleva a la página siguiente. Se encontrará deshabilitado en caso de no existir página siguiente.
•
Número de página: Etiqueta que contiene el número de la página actual así como el número total de páginas de la teoría en cuestión.
63
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
5.1.2 Formulario de práctica
Figura 13 Formulario de Práctica.
El formulario de práctica será el mismo para las dos opciones posibles. Este formulario está compuesto por los siguientes controles: •
Título: Se encuentra situado en la barra de título y corresponde al título de la práctica que contiene el formulario. En el caso de la imagen puede verse que contiene el texto: “Árboles de Adelson-Velskii y Landis (AVL)”.
64
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
•
Conjunto de funciones: Cuadro situado en la parte superior izquierda que contiene los siguientes botones: o Botón “Insertar”: Botón que inserta un nodo en el árbol. Cuando se pulse este botón se mostrará un cuadro de diálogo pidiéndole al usuario que introduzca un número. Una vez introducido, y de acuerdo con los requisitos, si el nodo no existe aún, la aplicación lo insertará y, si fuese necesario, reestructurará el árbol haciendo que éste mantenga su condición. o Botón “Buscar”: Botón que busca un nodo en el árbol. Cuando se pulse este botón se mostrará un cuadro de diálogo pidiéndole al usuario que introduzca un número. Una vez introducido, y de acuerdo con los requisitos, si el nodo existe, la aplicación lo señalará haciéndolo parpadear. o Botón “Eliminar”: Botón que elimina un nodo del árbol. Cuando se pulse este botón se mostrará un cuadro de diálogo pidiéndole al usuario que introduzca un número. Una vez introducido, y de acuerdo con los requisitos, si el nodo existe, la aplicación lo eliminará y reestructurará el árbol, si fuese necesario, haciendo que éste mantenga su condición •
Conjunto de Propiedades: Cuadro, situado a la derecha del cuadro de funciones, que contiene la altura del árbol.
65
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
•
Botón “Volver a empezar”: Botón que reinicia el formulario eliminando todos los nodos.
•
Zona de árbol: Región, situada en el centro del formulario, que contiene el árbol sobre el que se está trabajando. Esta zona tiene básicamente: o Nodos: Cuadrado que representa un nodo del árbol y está formado por un dato y dos punteros. o Flechas: Líneas que representa hacia donde apuntan los punteros de los nodos.
•
Conjunto de recorridos: Cuadro, situado en la parte inferior
del
formulario,
que
contiene
los
diferentes
recorridos del árbol sobre el que se está trabajando.
En la Figura 13 podemos apreciar que al entrar en la zona de práctica, se ha habilitado un nuevo menú.
Figura 14 Menú Complementos
66
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Este menú contiene las siguientes opciones: •
Explicaciones. o Inserción. o Eliminación. o Búsqueda. o Recorrido Preorden. o Recorrido Inorden. o Recorrido Postorden.
•
Pseudocódigos. o Inserción. o Eliminación. o Búsqueda. o Recorrido Preorden. o Recorrido Inorden. o Recorrido Postorden. o Auxiliares.
•
Código en C. o Inserción. o Eliminación. o Búsqueda. o Recorrido Preorden. o Recorrido Inorden. o Recorrido Postorden. o Auxiliares. 67
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Cada una de estas opciones abre un formulario como el de la Figura 15 y el de la Figura 16, conteniendo el texto deseado.
Figura 15 Ejemplo 1 de Formulario de Complementos.
Figura 16 Ejemplo 2 de Formulario de Complementos.
68
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6 Programación 6.1 Lista de funciones En este apartado se presentan las cabeceras de las funciones de cada formulario para hacerse una idea de cómo funciona cada uno.
6.1.1 Formulario principal mnuExp_Click(Index As Integer) mnuPrABB_Click() mnuPrAVL_Click() mnuPse_Click(Index As Integer) mnuCodC_Click(Index As Integer) mnuTeo_Click(Index As Integer)
6.1.2 Formulario de teoría Form_Load() btnAnterior_Click() btnSiguiente_Click() CargaInicial(teo As Integer) CargaPagina(Optional numero As Integer = 1) CargaTitulos(teo As Integer) Form_Unload(Cancel As Integer)
69
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6.1.3 Formulario de práctica 6.1.3.1 Funciones generales Form_Load() btnInsertar_Click() btnBuscar_Click() btnEliminar_Click() btnVolver_Click() Iniciar(avl As Boolean) CalculaPropiedades() CalculaRecorridos() Refrescar() CreaHijo(padre As Integer, lado As Integer, Optional Dato As Integer = 0) CreaRaiz(Dato As Integer) NodoMas() RecorridoPreorden(indice As Integer, contenido As String) RecorridoInorden(indice As Integer, contenido As String) RecorridoPostorden(indice As Integer, contenido As String) Insercion(Dato As Integer) As Integer InsertaNodo(Dato As Integer, Optional padre As Integer = 0, Optional indice As Integer = 0) As Integer BuscarMasIzquierdo(ByVal padre As Integer) As Integer BuscarMasDerecho(ByVal padre As Integer) As Integer BuscarLado(padre As Integer, Hijo As Integer) As Integer Eliminar(clave As Integer) As Integer Buscar(clave As Integer) As Integer Recolocar(i As Integer, Optional lado As Integer = 0) As Integer AsignaPropiedades(i As Integer, padre As Integer, lado As Integer) As Integer CalculaAltura() As Integer Form_Unload(Cancel As Integer) 70
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6.1.3.2 Funciones propias de los AVL InsercionAVL(Dato As Integer) As Integer EliminarAVL(clave As Integer) As Integer Equilibrar(indice As Integer, ByRef lado As Integer, operacion As Integer) RotSimpleDerecha(ByVal n As Integer) RotSimpleIzquierda(ByVal n As Integer) RotDobleDerecha(ByVal n As Integer) RotDobleIzquierda(ByVal n As Integer) RecalcularFE(ByVal i As Integer)
6.1.4 Formulario de Complementos Public Sub CargaForm(doc As String, Optional top As Integer = 0, Optional left As Integer = 0) Private Sub CargaArchivo(doc As String) Redimensionar(top As Integer, left As Integer)
6.1.5 Módulo Externo PedirNumero() CuentaLineas(ByRef rtf As RichTextBox) As Long TrataError(e As Integer) RellenarMatriz() CargaAyuda(avl As Boolean, op As Integer, subOp As Integer) EsHoja(Nodo As cNodo) As Boolean CargaTeoria(op As Integer)
71
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6.1.6 Objeto Nodo Private Sub UserControl_Initialize() Private Sub tmEspera_Timer() OcultaCruz(lado As Integer) MuestraCruz(lado As Integer) Parpadear() Property Get Dato() As Integer Property Let Dato(ByVal vNewValue As Integer) Property Get Hijo(lado As Integer) As Integer Property Let Hijo(lado As Integer, indice As Integer) Property Get Linea(lado As Integer) As Integer Property Let Linea(lado As Integer, indice As Integer) Property Get PosArriba(Coord As Integer) As Integer Property Get PosAbajo(Coord As Integer, lado As Integer) As Integer Property Get miIndex() As Integer Property Let miIndex(ByVal vNewValue As Integer) Property Get nivel() As Integer Property Let nivel(ByVal vNewValue As Integer) Property Get padre() As Integer Property Let padre(ByVal vNewValue As Integer) Property Get FE() As Integer Property Let FE(ByVal vNewValue As Integer) Property Get NumEnFila() As Integer Property Let NumEnFila(ByVal vNewValue As Integer) Property Get miTop() As Integer Property Let miTop(ByVal vNewValue As Integer) Property Get miLeft() As Integer Property Let miLeft(ByVal vNewValue As Integer) Property Get Altura() As Integer Property Let Altura(ByVal vNewValue As Integer)
72
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
6.2 Manual de usuario El manual de usuario se ha desarrollado siguiendo la siguiente estructura: 1. Introducción a la aplicación. 2. Requisitos mínimos. 3. Instalación. 4. Uso a. Ejecución. b. Teoría. c. Práctica. d. Complementos. 5. Posibles errores. a. Instalación. b. Teoría. c. Práctica. d. Complementos. 6. Desinstalación.
A continuación se muestra el manual de usuario completo.
73
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
TUTORIAL GRÁFICO DE ESTRUCTURAS DINÁMICAS DE DATOS (ÁRBOLES)
MANUAL DE USUARIO
74
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
FIGURAS ......................................................................................................... 76 1.
INTRODUCCIÓN A LA APLICACIÓN...................................................... 77
2.
REQUISITOS MÍNIMOS ........................................................................... 78
3.
INSTALACIÓN.......................................................................................... 79
4.
UTILIZACIÓN ........................................................................................... 81 A.
EJECUCIÓN .............................................................................................. 81
B.
TEORÍA ................................................................................................... 81
C.
PRÁCTICA ................................................................................................ 83
D.
COMPLEMENTOS ...................................................................................... 85
5.
6.
POSIBLES ERRORES ............................................................................. 86 A.
TEORÍA ................................................................................................... 86
B.
PRÁCTICA ................................................................................................ 86
C.
COMPLEMENTOS ...................................................................................... 88 DESINSTALACIÓN .................................................................................. 88
75
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Figuras Figura 1 Inicio de la instalación. ...................................................................... 79 Figura 2 Elección de directorio de instalación. ................................................ 80 Figura 3 Ruta del acceso directo en el Menú Inicio. ........................................ 81 Figura 4 Menú Teoría ...................................................................................... 81 Figura 5 Formulario de teoría. ......................................................................... 82 Figura 6 Menú Práctica. .................................................................................. 83 Figura 7 Formulario de teoría .......................................................................... 83 Figura 8 Inserción de un número..................................................................... 84 Figura 9 Búsqueda de un nodo. ...................................................................... 84 Figura 10 Pegunta sobre si realmente se quiere cambiar de tipo de práctica. 85 Figura 11 Menú complementos. ...................................................................... 85 Figura 12 Ejemplo de error de falta de archivo de teoría................................. 86 Figura 13 Error producido si el usuario no introduce un número. .................... 86 Figura 14 Error producido si el usuario introduce un número fuera de rango.. 87 Figura 15 Error producido cuando el usuario intenta insertar un nodo que ya existe. ............................................................................................................... 87 Figura 16 Error producido cuando el usuario intenta buscar o eliminar un nodo que no existe. ................................................................................................... 87 Figura 17 Error en la carga de un archivo de complementos. ......................... 88 Figura 18 Ruta del programa de desinstalación. ............................................. 88
76
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
1. Introducción a la aplicación La finalidad de esta aplicación es enseñar cómo funcionan los árboles. Para esta tarea se dispone de una parte teórica y una parte práctica.
En la parte teórica se mostrará qué son los árboles, para qué se usan y cómo utilizarlos de manera óptima.
En la parte práctica se podrá experimentar de manera gráfica con un árbol y realizar sobre él las operaciones de inserción, búsqueda, eliminación y recorrido.
Se contará con explicaciones sobre operaciones concretas así como de pseudocódigos y códigos en C de las mismas. Esto ayudará al alumno a entender mejor el funcionamiento de los árboles.
Después de interactuar con esta aplicación el usuario debería tener muy claros los conceptos de Árbol, Árbol Binario de Búsqueda y Árbol de AdelsonVelskii y Landis así como su funcionamiento y utilización.
77
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
2. Requisitos mínimos La instalación y ejecución de la aplicación requiere lo siguiente: •
Microprocesador Pentium 75 MHz o superior.
•
64 MB de memoria RAM.
•
30 MB de espacio en el disco duro.
•
Sistema operativo Windows 95 o superior.
•
Unidad de CD-ROM.
•
Teclado y ratón.
•
Tarjeta gráfica soportadora de Windows 95.
Los componentes, necesarios para la instalación y ejecución del programa, que no son estándar, vienen incluidos en el paquete de instalación.
78
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
3. Instalación Al introducir el CD en el lector aparecerá la ventana de instalación.
Figura 1 Inicio de la instalación.
Hacer clic en Siguiente para continuar la instalación.
79
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
A continuación el programa de instalación dará a elegir el directorio donde se quiere instalar la aplicación.
Figura 2 Elección de directorio de instalación.
Por defecto la aplicación se instalará en el directorio “c:\Archivos de programa\TGED-A”. Si se desea cambiar el directorio, se podrá escribir manualmente o bien pulsar sobre el icono con los puntos suspensivos para seleccionar un directorio.
Una vez se haya seleccionado un directorio hacer clic en Siguiente.
La siguiente ventana que se mostrará será la de confirmación. Si se está de acuerdo con la información mostrada hacer clic en Empezar y comenzará la instalación. 80
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
4. Utilización a. Ejecución Para ejecutar el programa hacer clic en Inicio/Programas 1 /Tutorial Gráfico sobre Árboles/ Tutorial Gráfico sobre Árboles.
Figura 3 Ruta del acceso directo en el Menú Inicio.
b. Teoría Para hacer uso de la teoría sobre árboles que proporciona el tutorial se deberá desplegar el menú teoría situado en la parte superior del formulario. Después se deberá seleccionar el tema que se desea ver.
Figura 4 Menú Teoría
1
En algunas versiones de Windows XP y Vista este menú se llama Todos los programas.
81
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Una vez que se encuentre en el formulario de la teoría que se quiere mostrar se podrá consultar las diferentes páginas de la misma mediante los botones Anterior y Siguiente. Los números que se encuentran entre estos dos botones representan el número de página en la que se está y el número total de páginas de la teoría en cuestión.
Figura 5 Formulario de teoría.
82
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
c. Práctica Para acceder a los formularios de práctica se deberá desplegar el menú Práctica situado en la parte superior del formulario principal.
Figura 6 Menú Práctica.
Una vez seleccionada la práctica a realizar se encontrará un formulario como el de la Figura 7. Este formulario está divido en tres zonas denominadas Zona de Funciones, Zona del Árbol y Zona de Recorridos, enumerándose de la más cercana al borde superior hacia abajo.
Figura 7 Formulario de teoría
83
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
En la Zona de Funciones se tienen los botones Insertar, Buscar y Eliminar y el cuadro de propiedades. El cuadro de propiedades muestra la altura del árbol en todo momento.
Cada uno de estos botones realiza la función que indica su nombre. Haciendo clic en cualquiera de ellos se mostrará un cuadro de diálogo pidiéndo el dato del nodo que se quiere insertar, buscar o eliminar. Este número ha de ser un número entero positivo menor que 32767.
Figura 8 Inserción de un número.
Se introduce el número deseado y se hace clic en aceptar. A continuación puede verse que, si era una inserción o una eliminación, el nodo deseado se ha insertado o eliminado respectivamente, y, si era una búsqueda, el nodo deseado está rodeado de un círculo rojo.
Figura 9 Búsqueda de un nodo.
84
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Se puede cambiar de tipo de práctica desplegando el menú práctica (véase Figura 6) y seleccionando la opción deseada. Si se tiene algún árbol creado en el momento que intenta cambiar de práctica, la aplicación preguntará si realmente se desea cambiar puesto que este cambio producirá la eliminación del mismo.
Figura 10 Pegunta sobre si realmente se quiere cambiar de tipo de práctica.
d. Complementos Para hacer uso de los complementos ofrecidos por la aplicación deberá desplegar el menú complementos 1 , situado en la parte superior, y elegir el complemento a mostrar.
Figura 11 Menú complementos.
Una vez seleccionado el complemento se mostrará el texto deseado. 1
El menú complementos sólo se mostrará cuando se esté realizando una práctica.
85
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
5. Posibles errores a. Teoría En el caso de que se haya dañado la instalación del programa y faltase algún archivo necesario para mostrar la teoría, se presentará un error diciendo qué archivo falta o está dañado.
Figura 12 Ejemplo de error de falta de archivo de teoría.
b. Práctica Los errores posibles son los siguientes: •
A la hora de introducir el número para realizar una función, es decir, insertar, buscar o eliminar un nodo, se han introducido caracteres no numéricos.
Figura 13 Error producido si el usuario no introduce un número.
86
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
•
A la hora de introducir el número para realizar una función, es decir, insertar, buscar o eliminar un nodo, ha introducido un número demasiado grande.
Figura 14 Error producido si el usuario introduce un número fuera de rango.
•
El nodo que desea insertar ya existe.
Figura 15 Error producido cuando el usuario intenta insertar un nodo que ya existe.
•
El nodo que desea eliminar o buscar no existe.
Figura 16 Error producido cuando el usuario intenta buscar o eliminar un nodo que no existe.
87
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
c. Complementos Si se hubiese dañado la instalación y la aplicación no pudiese acceder al archivo necesario para cargar el complemento deseado, ya fuese porque éste estuviese dañado o porque no existiera, se mostrará un mensaje de error diciendo qué archivo no se ha podido cargar.
Figura 17 Error en la carga de un archivo de complementos.
6. Desinstalación Para una correcta desinstalación hacer clic en Inicio/Programas 1 /Tutorial Gráfico sobre Árboles/Unistall Tutorial Gráfico sobre Árboles y seguir las instrucciones del desinstalador.
Figura 18 Ruta del programa de desinstalación.
1
En algunas versiones de Windows XP y Vista este menú se llama Todos los programas.
88
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
7 Pruebas En esta sección se enumerarán las diferentes pruebas realizadas a la aplicación.
7.1 Pruebas en el formulario principal •
Archivo Æ Salir: La aplicación se cierra sin ningún problema parando el proceso “TGEDVB.exe”.
•
Teoría: Las tres posibles opciones abren sus respectivos formularios. Cuando uno se encuentra abierto el menú muestra una marca al lado derecho del nombre del mismo.
•
Práctica: Permite elegir el tipo de práctica a realizar. Sólo permite una de ellas. La que está abierta se muestra marcada en el menú. Si se hace clic encima de la contraria a la que está abierta el programa pregunta si realmente se desea cambiar y en caso afirmativo cambia sin ninguna complicación.
•
Complementos: Cada una de las opciones posibles abre un formulario con el contenido deseado.
89
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
7.2 Pruebas en el formulario de teoría •
Las etiquetas de título se cargan correctamente correspondiendo con el tema y la sección de la parte de teoría seleccionada.
Figura 17 Etiquetas de título.
•
Cuando se está mostrando la primera página el botón “Anterior” se encuentra deshabilitado. Así como cuando se está mostrando la última, el que está deshabilitado es el botón “Siguiente”.
Figura 18 Botones “Anterior” y “Siguiente” deshabilitados.
90
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
7.3 Pruebas en el formulario de práctica •
El título del formulario se actualiza correctamente en función del tipo de práctica que se esté mostrando.
•
Cuando no hay ningún nodo, los botones de las funciones “Buscar” y “Eliminar” se encuentran deshabilitados.
Figura 19 Botones “Buscar” e “Insertar” deshabilitados.
•
Cuando se hace clic en alguno de los botones de “Funciones” se muestra un formulario para que el usuario introduzca el dato del nodo que desea insertar, buscar o eliminar. Éste formulario sólo acepta números enteros comprendidos entre -32766 y +32766. Si el dato introducido no está dentro de lo permitido se mostrará un error.
Figura 20 Error producido si el usuario no introduce un número.
Figura 21 Error producido si el usuario introduce un número fuera de rango.
91
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
•
Si el usuario intenta insertar un nodo que ya existe se presentará un mensaje de error.
Figura 22 Error producido cuando el usuario intenta insertar un nodo que ya existe.
•
Si el usuario intenta buscar o eliminar un nodo que no existe se presentará un mensaje de error.
Figura 23 Error producido cuando el usuario intenta buscar o eliminar un nodo que no existe.
92
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
•
La altura del árbol que se muestra no puede ser mayor que 5. Esta restricción existe por tener limitado el espacio de la pantalla. Cuando se intenta añadir un nodo que haga superar esta altura se mostrará un mensaje de error.
Figura 24 Error producido si el usuario intenta insertar un nodo que hace que el árbol supere la altura máxima.
•
Para no producir un desbordamiento 1 no se pueden crear infinitos nodos en una misma ejecución del formulario de práctica. Si se llegase a este número se mostraría un error y se deshabilitaría el botón “Insertar”.
Figura 25 Error producido si el usuario intenta insertar un nodo que hace que el árbol supere la altura máxima.
1
Desbordamiento: Sobrepasar el valor máximo de una variable. Por cuestiones de
programación cada nodo tiene un índice cuyo valor máximo es 32766.
93
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
8 Valoración económica y planificación El siguiente diagrama muestra los procesos realizados a lo largo del tiempo. IDN ARQ EAQ DEX DIN PRO PRU Octubre
Noviembre
Diciembre
Enero
Abril
Mayo
Junio
Figura 26 Planificación temporal.
Como se puede observar en la figura, el proceso que más tiempo ha llevado ha sido el de programación. También se observa que hubo una pausa en el desarrollo que duró desde finales de enero hasta principios de abril.
A la hora de valorar el coste de cada proceso se divide el desarrollo en dos grandes etapas: análisis y programación. La etapa de programación engloba la programación y las pruebas y la de análisis el resto de procesos.
Los dos tipos de tarifa, la de analista y la de programador, son los siguientes: Puesto
Precio/hora
Tiempo
Sueldo
Programador Junior
40€ / hora
180 horas
7.200 €
Analista Junior
65€ / hora
60 horas
3.900 €
Figura 27 Tabla de tarifas.
94
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
Para el desarrollo del proyecto se ha utilizado el siguiente software: Software
Precio licencia
Microsoft Visual Studio 2003
477,05 €
Microsoft Office 2003
744 €
Microsoft Windows XP SP2
154,80 €
Figura 28 Tabla de licencias.
Los precios del software enumerado en la Figura 28 corresponden con el precio total de cada licencia. La licencia del Microsoft Visual Studio 2003 ha sido amortizada por completo por el proyecto por lo que el coste imputable al mismo es equivalente a su precio (477,05 €). Por otro lado, para las licencias del Office 2003 y del Windows XP habrá que calcular la parte proporcional de su precio que ha de imputarse al proyecto.
La duración operativa media del MS Office es de 24 meses. Teniendo en cuenta que el desarrollo del proyecto ha llevado 7 meses, se tiene que el coste de la licencia imputable al proyecto es de 217 €. De la misma manera, desde que se adquirió el Windows XP hasta que ha salido la última versión, Windows Vista, han transcurrido 5 años y medio (66 meses), por lo que el coste imputable al proyecto es de 16,42 €.
El coste total de software asciende a 710,47 €.
95
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
El equipo utilizado para el desarrollo de la aplicación ha sido un equipo con un procesador AMD 2600 XP y con una memoria RAM de 1 GB. La amortización de este equipo aplicable al proyecto asciende a 400 €.
Por último hay que tener en cuenta los gastos en consumibles informáticos así como de papel para la entrega de informes y documentos sobre el desarrollo del proyecto. Este tipo de gastos han ascendido en su totalidad a 100 €.
Sumando todos los gastos generados por el proyecto se tiene que el coste total del mismo asciende a 12.310,47 €.
96
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
9 Conclusiones Con la realización de este proyecto se ha podido poner en práctica lo aprendido durante la carrera. A priori, se tiene la sensación de que todo lo que se estudia en la carrera está muy disgregado pero durante el desarrollo de la aplicación se va uniendo lo aprendido en cada una de las asignaturas para poder configurar un proyecto detallado y estructurado.
Dentro del peso que han tenido todos, o casi todos, los conocimientos adquiridos durante la carrera en el desarrollo del proyecto, hay que decir que la asignaturas que más han aportado a este efecto han sido: Ingeniería del software en cuanto a la metodología se refiere, Estructuras de datos en lo referente al objeto del proyecto, los árboles, y Programación en Visual Basic en la programación de la aplicación.
Tras el estudio exhaustivo de los árboles durante el desarrollo de la aplicación se ha ido viendo que las estructuras dinámicas de datos no son una herramienta fácil de entender con una simple explicación teórica. Por esta razón se puede afirmar que este tutorial cumplirá casi a la perfección su principal objetivo: ayudar a entender, de una manera visual, cómo funcionan los árboles.
97
Tutorial Gráfico de Estructuras Dinámicas de datos: Árboles
10 Bibliografía [BARR01] Barranco de Areba, Jesús, “Metodología del análisis estructurado de sistemas”. Universidad Pontificia de Comillas, Madrid 2001.
[DURA04] Durán Parra, Luís, “Apuntes de estructura de datos”. Universidad Pontificia de Comillas, Madrid 2001.
[LAZA05] Lázaro-Cañedo Argüelles, Eugenio, “Apuntes de Visual Basic”. Universidad Pontificia de Comillas, Madrid 2005.
[PETR99] Petroutsos, Evangelos, “La biblia de Visual Basic”. Anaya Multimedia-Anaya Interactiva, Madrid 1999.
[HEIL97] Heileman, Gregory L., “Estructura de Datos. Algoritmos, Abstracción y Objetos”. McGraw-Hill / Interamericana de España, S.A., Madrid 1997.
Páginas Web http://c.conclase.net
Página de programación en C.
http://msdn.microsoft.com
Ayuda de Microsoft.
http://es.wikipedia.org
Wikipedia en castellano.
http://ca.wikipedia.org
Wikipedia en catalán.
http://en.wikipedia.org
Wikipedia en inglés
http://www.elguille.info/vb
Manual de Visual Basic.
98