Resumen
El presente trabajo se desarrolló en dos fases. En la primera, se realizó una investigación sobre la forma en que Borland C++ 5.0, a través del concepto de Template y Clase, permite implementar las estructuras de datos como Tipos Abstractos de Datos. La segunda fase consistió en desarrollar aplicaciones, en su mayoría complejas, que requieren de las implementaciones de TAD’s de la primera fase, aplicando en todo momento los principios de Programación Orientada a Objetos. Los ocho capítulos basados en la investigación realizada, fueron desarrollados de tal forma que correspondieran con los contenidos de los actuales programas de las asignaturas de Estructuras de Datos que se dictan en las carreras de Análisis de Sistemas e Ingeniería en Informática. En el Capítulo 1, se trata todo lo relacionado a los conceptos, propiedades y ventajas de utilizar Programación Orientada a Objetos (POO) como técnica de programación. Además se tratan los conceptos que constituyen el núcleo de la Programación Orientada a Objetos, como son los de abstracción de datos, herencia y polimorfismo, así como las bondades que nos ofrece la versión utilizada de Borland C++, el Template, sobre la cual se basa principalmente este trabajo. En cada concepto se muestran ejemplos sencillos de aplicación de los mismos. El Capítulo 2 se dedica al estudio de las Estructuras de Datos en general, conceptos, características y niveles de visualización de las mismas como Tipos Abstractos de Datos, aplicando el concepto de Template y Clase en C++. Al final se muestra la implementación de un TAD llamada Bolsa, donde se aplica todos los conceptos desarrollados en este capítulo, así como una aplicación sencilla que utiliza la TAD. En el Capítulo 3 se introduce una estructura de datos conocida como Stack, Pila, o de almacenamiento pushdown, en todos sus niveles de visualización. La representación utilizada en la implementación de la TAD Pila es la secuencial. Para demostrar el funcionamiento de dicha TAD, se presenta una aplicación sencilla y luego la clásica aplicación de dos Pilas como es la de Evaluación de Expresiones Aritméticas. El Capítulo 4 trata de técnicas de desarrollo, verificación y seguimiento de problemas Recursivos en C++. Se muestran diferentes problemas resueltos en forma recursiva, retornando o no valores. Este capítulo es necesario, ya que en el capítulo 8 sobre Arboles, la mayoría de sus operaciones serán desarrolladas en forma recursiva. El Capítulo 5 trata, en todos los niveles de visualización, una nueva estructura de datos conocida como Queue, Cola, o de almacenamiento “espere su turno”. Aquí se implementan dos tipos de Cola Circular, ambas con representación secuencial. Para el primer enfoque se presenta una sencilla aplicación. Para demostrar el uso de la TAD Cola Circular, se desarrolló una aplicación más compleja como es la Simulación de un Autocine. El Capítulo 6 trata del concepto de Memoria Dinámica en C++. Se muestra como crear y utilizar variables dinámicas y apuntadoras, los operadores especiales NEW. DELETE, NULL y el apuntador THIS. Para cada concepto se dan ejemplos sencillos de aplicación de los mismos y al final del capítulo se desarrolla una nueva implementación de la TAD Bolsa, soportada por un arreglo dinámico, así como una aplicación que utiliza esa implementación. El Capítulo 7 trata de una de las más importantes estructuras de datos como es la Lista Encadenada. Lista Encadenada tiene múltiples aplicaciones. Donde más se evidencia su importancia, es en el caso de su utilización como representación interna en la implementación de la TAD’s. En este caso se realiza una nueva implementación de la Pila, pero utilizando como representación, la TAD Lista Encadenada. Se desarrollan diferentes implementaciones de Listas Encadenadas, con memoria Estática y Dinámica y Simple y Doblemente Encadenadas. La aplicación más importante en importante en este capítulo, utiliza la implementación de la TAD de Lista Dinámica Simplemente Encadenada, y consiste en la Simulación de un Banco. El capítulo 8 trata de la estructura de datos no lineal llamada Arbol o Tree. Se contempla principalmente las estructura datos Arboles Binarios y Arboles Binarios de Búsqueda, como una subclase descendiente de Arbol Binario. La TAD Arbol Binario será considerado en su totalidad, dado que es uno de los tipos de árboles más utilizados, y donde la aplicación que se muestra corresponde a como representar una Expresión Aritmética utilizando un Arbol Binario. En el caso de la TAD Arbol Binario de Búsqueda, la aplicación consiste en la Creación de un Indice de un Libro, la cual requiere de dos Arboles Binarios de Búsqueda.