Facultad de Ingeniería Eléctrica.

Universidad Michoacana de San

Nicolás de Hidalgo

Software Didáctico de

Estructuras de Datos

Dr. Félix Calderón Solorio

Contenido General

1 Descripción General....................................................................................................... 3

2 Listas Ligadas................................................................................................................ 3

2.1.1 Conjuntos.................................................................................................................. 4

2.1.2 Expresiones en Postfijo.............................................................................................. 5

2.1.3 Operaciones.............................................................................................................. 6

3 Árboles.......................................................................................................................... 8

3.1.1 Árboles Binarios......................................................................................................... 9

3.1.2 Árbol AVL.................................................................................................................. 9

3.1.3 Árbol de expresión.................................................................................................... 10

4 Tablas Hash................................................................................................................. 11

5 Relaciones................................................................................................................... 12

6 Menús......................................................................................................................... 12

7 Gráfica......................................................................................................................... 12

8 Bibliografía................................................................................................................... 14

Software Didáctico de

Estructuras de Datos

1 Descripción General

Este programa muestra las operaciones que se pueden realizar con listas, conjuntos, árboles y Grafos, en general Estructuras de datos, las cuales son analizadas en la materia correspondiente (ver programa). El programa principal que debe ejecutarse es principal.jar dando la siguiente línea de comando

java –jar principal.jar

Al realizar la ejecución aparece una pantalla como se muestra en la Figura 1. En dicha figura se muestra, sobre la barra de menú, las estructuras de datos que el programa maneja. Para llevar a cabo la ejecución del programa se requiere una computadora pentium 4 o similar con sistema operativo Windows, Linux, MacOS, etc. La versatilidad de los programas en Java permite que puedan ser corridos en cualquier plataforma y el código fuente se encuentra disponible en la página http://lc.fie.umich.mx/~calderon/ . El proyecto completo con todos los códigos fuentes puede ser descargado aquí y la documentación necesaria explicando cada una de las clases con sus métodos esta disponible en doc.

Figura 1. Pantalla del programa principal

Las opciones que de el menú de la Figura 1, son Archivo, Listas Ligadas, Árboles, Tablas Hash, Relaciones, Menús y Graficas. Cada uno a su vez despliega submenús de operaciones implementadas para cada caso y estas son descritas con más detalle a continuación.

1 Listas Ligadas

Al entrar a la opción de Listas ligadas se muestran las opciones que se tienen implementadas, estas son las opciones de Conjuntos, Manejo de Expresiones en Postfijo y Operaciones básicas con listas, este submenú se muestra en Figura 2 . En la siguiente sección se detallan cada una de las operaciones implementadas con listas.

Figura 2. Submenú de Listas Ligadas

1.1.1 Conjuntos

El código fuente para la implementación de conjuntos se encuentra disponible en Conjunto.java, esta clase tiene implementadas las operaciones básicas con conjuntos y este marco (Figura 3), solamente muestra la ejecución de estas de una manera didáctica. Al ejecutar del la Figura 2, la opción de conjuntos se despliega el marco que se muestra en la Figura 3 donde se muestra un ejemplo de la evaluación de una expresión dada con de tres conjuntos. Esta opción cuenta con un menú de archivo y Ejemplos dados con conjuntos.

Figura 3. Opción de Conjuntos

La opción de archivo despliega un submenú como se muestra en la Figura 4. Estas opciones permiten crear un conjunto nuevo, dar datos para los tres conjuntos desde un archivo, guardar la información de los conjuntos en archivo y salir.

Figura 4. Submenú archivo de la opción de conjuntos

1.1.2 Expresiones en Postfijo

Esta opción permite manejar expresiones en postfijo o notación polaca. La opción evalua la expresión dada en la casilla de texto o corre dos ejemplos que se muestran en la opción de ejemplos. La Figura 5, muestra el marco para la opción de expresiones en postfijo.

Figura 5. Opción de Expresiones en Postfijo

1.1.3 Operaciones

En esta opción se manejan las operaciones que se pueden realizar con Listas ligadas. Se implemento una lista, una pila y una cola. Al ejecutar la opción Operaciones del menú de la Figura 2, se despliega el menú presentado en la Figura 6. En la opción de archivo se despliegan tres tipos de estructuras implementadas a partir del modelo de listas ligas, estas operaciones son la Lista, la Pila y la Cola. Cada una de estas tiene la opción de crear una lista nueva vacía o leer la información de un archivo. En las Figura 7, Figura 8 y Figura 9 se muestran las opciones implementadas.

En el caso de una lista (Figura 7) se tienen implementadas las operaciones de Insertar, Borrar, Buscar, Imprimir y Ordenar, y los métodos de ordenamiento implementados son Burbuja y MergeSort. Para una pila se implemento las opciones de sacar información de la pila Pop, meter información a la pila Push e Imprimir el contenido de la pila con Imprime tal como lo muestra la Figura 8. Finalmente en la Figura 9, se muestra la operaciones de Encolar, Desencolar e Imprimir el contenido de una Cola.

Los códigos fuentes con esta operaciones se encuentran en Cola.java Lista.java y Stack.java

Figura 6. Opción de Operaciones con Listas Ligadas.

Figura 7. Lista

Figura 8. Pila

Figura 9. Cola

2 Árboles

Dentro de las estructuras de datos existen los árboles. Estas estructuras a diferencia de las listas ligadas, permite tener mas de una referencia a otro nodo, por lo tanto si utilizamos solamente la referencia a dos de ellos estaremos creando un árbol binario. Los árboles binarios pueden ser utilizados para almacenar información y a su vez derivar otras aplicaciones como son los árboles de expresiones que pueden ser utilizados para evaluar expresiones matemáticas o crearlas. Los árboles AVL son una mejora de los Binarios en el cual el árbol siempre esta balanceado. En las siguientes subsecciones siguientes, se detallan mas la funciones implementadas en esta opción. Los códigos fuentes se encuentran disponibles en las clases Arbol_Binario.java, Arbol_AVL.java y Arbol_Expresion.java

2.1.1 Árboles Binarios

Para los árboles binarios, se tienen implementadas las operaciones de Insertar, Buscar, Borrar e Imprimir. El nombre de cada una de ellas describe la operación que realizar. La opción de imprimir puede hacerla en preorden, orden y postorden. Una opción mas implementada, es la del cálculo de la Altura Máxima como se ve en la Figura 10.

Figura 10. Árbol Binario

2.1.2 Árbol AVL

Los árboles AVL son árboles Binarios que tienen una restricción de balaceo. Esto quiere decir que en el árbol AVL siempre satisface el criterio 2^k-1, donde k es la profundidad del árbol. Así por ejemplo si el número de elementos en el árbol es de 15 la profundidad máxima k = 3 y para un árbol binario en el peor de los casos k = 15. Esto significa que en el primero con 3 comparaciones encontramos un elemento mientras que en segundo se requieren de 15 en el peor de los casos. En la Figura 11, se muestran las opciones implementadas, estas son, Buscar en un árbol, Ejemplos implementados, Insertar, Imprimir, Nuevo y Salir.

Figura 11. Árbol AVL

2.1.3 Árbol de expresión

Los árboles de expresión son árboles Binarios donde siempre, para un subárbol dado, su nodo raíz es una operación aritmética y los subárboles hijos son dos números reales o el resultado de una operación. Estos árboles son utilizados para cambiar una expresión dada en notación polaca a su notación en infijo que es como estamos acostumbrados a manejar las expresiones aritméticas. El menú implementado para esta opción se presenta en la Figura 12, donde podemos ver que las opciones implementadas son ejemplos, Imprimir (en forma de árbol o expresión) y salir. La expresión dada en el área de texto es evaluada al momento de finalizar su captura y el resultado es presentado en el área de texto de abajo.

Figura 12. Árbol de Expresión

3 Tablas Hash

Al presionar la opción Tabla Hash de la Figura 1, se despliega el menú de la Figura 13, este es el menú de inicio donde se dan las opciones de crea una nueva Tabla Hash o mostrar los ejemplos implementados. Al ejecutar alguna de estas opciones se muestra el menú de la Figura 14, las operaciones implementadas son Insertar, Borrar, Imprimir, Calcular la función Hash y Buscar.

Figura 13. Menú principal de la tabla Hash.

Figura 14. Operaciones con Tablas Hash.

4 Relaciones

Esta opción esta bajo construcción y al presionar el botón izquierdo del Mouse no realiza acción alguna.

5 Menús

Despliega dos ejemplos de menús implementados. Estas no pueden ser consideradas estructuras de datos sin embargo estos menús se dan como ejemplo para que los alumnos tenga referencia de opciones para proyectos relacionados con la materia. En la figura

Figura 15. Ejemplo de Menú 1

6 Gráfica

Al presionar la opción de Gráfocas de la Figura 1, se despliega el menú de la Figura 16, este es el menú de inicio donde se dan las opciones de crea una nueva Grafica la cual puede ser dirigida o no o simplemente, se lee desde un archivo de datos. Al ejecutar alguna de estas opciones se muestra el menú de la Figura 17. En esta figura podemos calcular el Árbol de expansión mínima, Buscar, Borrar, Insertar, Búsqueda en profundidad y Distancia a todos los nodos.

Figura 16. Menú principal para la ejecutar una gráfica.

Figura 17. Operaciones implementadas con Gráficas.

7 Bibliografía.

1. Alfred V. Aho. y Jeffrey D. Ullman. Foundations of Computer Science, C Edition. W.H. Freeman, 1995
2. Mark Allen Weiss. Data Structures & Algorithm Analysis in JAVA. Addison Wesley. 1999.