PDF de programación - Animaciones de tipos abstractos de datos

Sistemas Informáticos

Curso 2006-07



Animaciones de tipos abstractos
de datos



Ana Colinas Lorenzo
Alejandro García Asenjo
Aída Mengual Castro


Dirigido por:
Isabel Pita Andreu
Dpto. Sistemas Informáticos y Programación



Facultad de Informática

Universidad Complutense de Madrid

ANIMACIONES DE TIPOS ABSTRACTOS DE DATOS



2.1.
2.2.

2.2.1.
2.2.2.
2.2.3.

Índice

Resumen............................................................................................................ 3
Summary............................................................................................................ 3

1.
Introducción................................................................................................. 4
2. Animaciones................................................................................................ 7
Evaluación de expresiones en forma postfija ................................... 7
Comprobación de expresiones palíndromas .................................. 16
Algoritmo utilizando dos pilas .................................................. 16
Algoritmo utilizando una pila y una cola .................................. 23
Algoritmo utilizando una cola doble......................................... 28
Arboles 2-3-4.................................................................................. 33
Inserción.................................................................................. 33
Búsqueda ................................................................................ 38
Implementación en Flash ........................................................ 41
3. Aplicación web .......................................................................................... 51
4. Tutorial de ActionScript ............................................................................. 52
Manual flash: .................................................................................. 52
Por qué utilizar Flash para realizar animaciones de TADs...... 52
Tutorial ActionScript: ...................................................................... 62
Cómo obtener interactividad y movimiento con Action Script.. 62
5. Conclusiones............................................................................................. 86
6. Bibliografía ................................................................................................ 87


2.3.1.
2.3.2.
2.3.3.

2.3.

4.1.

4.2.

4.1.1.

4.2.1.



2

ANIMACIONES DE TIPOS ABSTRACTOS DE DATOS



Resumen

El objetivo principal de este trabajo es la realización de animaciones dinámicas
e interactivas de tipos abstractos de datos mediante el uso de la herramienta
de Macromedia Flash. Está dirigido principalmente a los alumnos que estén
cursando asignaturas en las que se estudian tipos abstractos de datos.

En el trabajo se han realizado animaciones sobre un algoritmo de evaluación
de expresiones postfijas, tres algoritmos de comprobación de cadenas
palíndromas utilizando distintas estructuras de datos y por último una
animación sobre la inserción y búsqueda de elementos en árboles 2-3-4.

El primer algoritmo completa el trabajo realizado el curso anterior sobre
transformación de expresiones en forma infija a forma postfija. Los árboles 2-3-
4 se suman a las animaciones de árboles de búsqueda y árboles equilibrados
(rojo-negros) realizadas también el curso pasado.

A diferencia de los algoritmos desarrollados el curso anterior, las animaciones
son completamente interactivas, permitiendo al usuario introducir los datos,
esto se ha conseguido utilizando la herramienta ActionScript.

Adicionalmente se ha desarrollado un tutorial sobre cómo implementar
animaciones en Flash utilizando ActionScript. Este manual será de gran
utilidad para la continuidad del proyecto.

Summary

The main purpose of this project is to do dynamic and interactive abstract data
type animations using Macromedia Flash. It is directed to those who are
studying subjects in which abstract data types are being taught.

The animations that have been done are based on evaluating postfix
expression algorithms, three algorithms about testing palindromes using
different abstract data types and, finally, an animation about inserting and
searching elements in 2-3-4 trees.

The first algorithm completes the work done last year about changing infix
expressions into postfix expressions. The 2-3-4 trees are added to searching
trees and balanced trees (red-black), made last year too.

The difference between the algorithms made last year and the ones done now
is that animations are completely interactive allowing the user to insert data; this
has been achieved thanks to Action Script.

An additional tutorial about how to implement animations in Flash using Action
Script is been made. This manual ensures the continuity of the project.



3

ANIMACIONES DE TIPOS ABSTRACTOS DE DATOS



1. Introducción

Los tipos abstractos de datos (TADs) son un elemento fundamental en la
programación actual. Un TAD define un conjunto de valores junto con las
operaciones que manejan dichos valores. Son por tanto piezas básicas de la
programación modular, que permiten separar de forma estricta la
implementación del TAD del uso que se hace de él en las aplicaciones. Para
ello al definir un TAD se definen los valores del tipo y las operaciones con los
respectivos interfaces. Normalmente se utiliza la técnica de la especificación
algebraica para definir el comportamiento del tipo. Un tipo de datos suele
permitir varias implementaciones, variando el coste de las operaciones de unas
a otras. La implementación concreta seleccionada al utilizar un TAD en una
aplicación debe ser transparente, esto es, se debe poder cambiar una
implementación por otra sin modificar la aplicación.

El objetivo de este proyecto es realizar animaciones de algunos tipos
abstractos de datos para facilitar su estudio a los alumnos. La animación puede
referirse al comportamiento de la estructura, a una implementación concreta de
ella, o al uso de la estructura en una aplicación. El trabajo continúa el realizado
el año pasado por los alumnos R. Carrasco, J. Crespo y A. López en el
proyecto de Sistemas Informáticos [1].

La principal aportación de este proyecto es la realización de animaciones
dinámicas permitiendo a los usuarios introducir los datos que consideren
oportunos para estudiar el comportamiento de las distintas funciones
implementadas para los tipos de datos y estudiar el funcionamiento de éstos
con todo el nivel de detalle que se quiera.

El proyecto está dirigido principalmente a los alumnos que están cursando
asignaturas en las que se estudian tipos abstractos de datos y por ello, las
animaciones han sido diseñadas teniendo en cuenta que pueden ser
proyectadas en aulas para su visualización siendo éstas así ricas en
contenidos visuales y de manejo muy intuitivo. Las animaciones también están
pensadas para ser utilizadas por los alumnos para estudiar individualmente los
TADs, para ello en cada animación se muestra los pasos detallados que va
dando el algoritmo o la función además de la correspondiente animación.

En este proyecto se han realizado las siguientes animaciones:

- Evaluación de una expresión en forma postfija. La animación comprueba

si la expresión dada está en forma postfija e informa del error si no lo
está.

- Comprobación de si una cadena es o no palíndroma. Para ello se han

empleado tres algoritmos distintos que emplean distintas estructuras de
datos: dos pilas, una pila y una cola y una cola doble. Para cada
algoritmo se ha producido una animación diferente lo que facilita la
comparación de los algoritmos.

- Tipo de datos de los árboles 2-3-4, con las operaciones de inserción de

nuevos elementos y búsqueda de elementos.



4

ANIMACIONES DE TIPOS ABSTRACTOS DE DATOS



Para cada animación vemos, a la derecha de la pantalla la animación y a la
izquierda los pasos del algoritmo que ésta va siguiendo.

Para el desarrollo de las animaciones hemos utilizado la herramienta
Macromedia Flash utilizando la interfaz de programación Action Script, para
poder ejecutar los algoritmos y dotar a las animaciones de un alto grado de
interactividad con el usuario. El uso de ActionScript hace el desarrollo de las
animaciones más estructurado y sencillo de comprender.

Todas las animaciones pueden ser visualizadas desde cualquier navegador
que disponga del plugin Macromedia Flash Player, disponible en la siguiente
dirección web: www.macromedia.org.


Punto de Partida

Este proyecto es la continuación del proyecto Sistema multiusuario para la
gestión universitaria vía Web, incluyendo el desarrollo de un interfaz para el
diseño de aplicación de datos visuales de R. Carrasco, A. J. López, J. J.
Crespo [1].

Las animaciones del proyecto anterior tenían un interfaz atractivo pero un grave
problema: la falta de interactividad con el usuario.
Esto es debido a que las animaciones estaban realizadas exclusivamente en
Flash con interpolaciones de movimiento, sin la utilización de ActionScript.

Las nuevas animaciones deberían tener una apariencia lo mas parecida posible
a la del proyecto anterior para mantener un estándar en estas aplicaciones de
estudio para los alumnos. Sin embargo debíamos dotar a la herramienta de
cierta interactividad con el usuario.


Objetivos y evolución

El proyecto ha tenido dos objetivos que se han desarrollado en paralelo por un
lado el desarrollo de aplicaciones para la asignatura de Estructuras de Datos
de la Información; y por otro lado el estudio del lenguaje ActionScript y sus
posibilidades para resolver los problemas principales detectados el año
anterior. Estos problemas son la falta de interactividad con el usuario y el coste
de mantener aplicaciones realizad