Semana 1 - Introducción a los tipos abstractos de datos
-
Conocer la definición de Tipo Abstracto de Datos.
-
Utilizar los mecanismos de encapsulación de C++ para la implementación de Tipos Abstractos de Datos.
-
Conocer la terminología básica de TADs: modelo, representación, e invariantes.
-
Vídeos: 1h 4min
-
Total (incluyendo vídeos, cuestionarios y actividades de autoevaluación, pero no los problemas de la sección 1.4): 2h 10min
En la última clase de teoría hemos hecho un ejercicio de planificación de horarios. Aquí tienes el ejercicio junto con las soluciones.
📝 Planificación de horarios A (con solución)
📝 Planificación de horarios B (con solución)
Este ejercicio es similar al siguiente problema de Acepta el Reto: ACR 278: El baile de Cenicienta.
1.1. Motivación
En el ejercicio de planificación de horarios, tenemos dos maneras de
representar las duraciones: (1) mediante un struct que almacene los
distintos campos de una duración por separado, y (2) mediante un único número
entero que denote una cantidad de segundos. Cada una de estas
representaciones tiene sus ventajas e inconvenientes, y no existe una opción
que sea mejor que la otra en todos los casos. No obstante, lo que sí
resultaría claramente perjudicial sería que tu código dependiese, en gran
medida, de la opción escogida. ¿Qué pasaría si, pasado un tiempo tras haber
escogido una representación, tienes que rectificar y escoger la otra?
En el primer video que se enlaza a continuación vamos a presentar un ejemplo parecido:
▶️ Tipos Abstractos de Datos (TADs) - Motivación (8:32)
Antes de que en el siguiente video arreglemos nuestra implementación, puedes acceder en el siguiente enlace a una sesión de Compiler Explorer con el código que tenemos hasta ahora.
💻 Implementación inicial del juego
¿Puedes arreglarlo tú mismo? El objetivo es que modifiques la función main, añadiendo las funciones auxiliares que necesites, para que puedas cambiar entre las dos implementaciones de ConjuntoChar sin tener que realizar cambios en la función main resultante.
¿No sabes utilizar Compiler Explorer? Aquí tienes un mini-manual: Cómo usar Compiler Explorer
En el siguiente video veremos cómo se puede realizar esta encapsulación:
▶️ Definición de TAD (11:56)
📄 Código fuente (versión que utiliza un array de elementos)
📄 Código fuente (versión que utiliza un array de valores booleanos)
En la siguiente sesión de Compiler Explorer se encuentra el nuevo método main.
Observa que se hace un #include sobre la implementación que utiliza arrays
de caracteres (ConjuntoCharArray.h). Vamos a demostrar que esta
implementación es intercambiable con la que utiliza un array de booleanos
(ConjuntoCharBool.h). Para ello sustituye el #include anterior por uno que
haga referencia a este último fichero. El programa debería funcionar
perfectamente, ¡sin modificar una línea del método main!
1.2. Clases en C++
El último vídeo de la sección anterior nos deja un interrogante. ¿No sería mejor que el compilador nos impidiese acceder a las representaciones internas de los tipos de datos? Pues bien, esto es posible mediante clases en C++. A continuación se presentan tres vídeos sobre esto. Los dos primeros presentan conceptos que ya conocéis de la asignatura de Tecnología de la Programación: clases, métodos, constructores, etc. Aun así, prestad atención porque la sintaxis difiere bastante de lo que habéis visto en Java. El último vídeo introduce los métodos constantes; una característica propia de C++ que no se encuentra en Java.
▶️ C++ - Atributos y métodos (8:04)
▶️ C++ - Constructores y Listas de inicialización (11:14)
▶️ C++ - Métodos const (7:42)
💻 Transformar ConjuntoChar en una clase
Sustituye el struct por una clase de C++, y modifica las funciones definidas sobre conjuntos para queden integradas como métodos dentro de la clase.
La solución está en el siguiente video, en el que introducimos las clases de C++ en nuestro juego.
▶️ Encapsulación en TADs (7:58)
1.3. Conceptos básicos en Tipos Abstractos de Datos
En este último vídeo vamos a introducir de manera informal los conceptos que aparecen en el estudio de las estructuras de datos y los TADs: modelos, representaciones e invariantes de representación. También se introduce la importante distinción entre operaciones constructoras, observadoras y mutadoras.
▶️ Modelo vs representación en TADs (13:31)