Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Horas de clases presenciales: 8 (4 teoría + 4 prácticas)
Horas de trabajo no presencial: 8
El tema 2 de la asignatura VJ1215 es un complemento del Módulo 3 "Estructuras de datos básicas con memoria dinámica: listas enlazadas, pilas, colas, diccionarios" de la asignatura Programación II. Supondremos, aunque lo repasaremos, que conoces el contenido de esa asignatura, cuyos resultados de aprendizaje incluyen "implementar las siguientes estructuras de datos cumpliendo ciertas especificaciones: pila, cola, lista enlazada" y "utilizar implementaciones estándar de las siguientes estructuras de datos: pila, cola, lista enlazada, diccionario". Quienes no aprendieron eso en primer curso, deberán dedicar tiempo extra a la asignatura para aprenderlo ahora.
En este tema utilizaremos dos referencias:
Para presentar los conceptos teóricos, nos basaremos en los siguientes apartados del capítulo 3 "Lists, Stacks and Queues" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss. En ese libro el énfasis se pone en la eficiencia, comparando diferentes formas de implementar cada uno de los tres Tipos Abstractos de Datos con el fin de aprender a elegir soluciones de coste O(1) y descartar soluciones de coste O(n) cuando es posible:
Además de aprender a elegir soluciones eficientes dependiendo de las operaciones que se quieran realizar, en los ejercicios de este tema veremos con detalle cómo trabajar con listas enlazadas para implementar Tipos Abstractos de Datos con C++.
Los siguientes capítulos del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff te pueden ayudar a entender eso, en estos subapartados dedicados a las implementaciones con listas enlazadas (no veremos sus implementaciones con vectores):
Las explicaciones de este libro sobre cómo implementar constructor de copia, operador de asignación y destructor pueden ser interesantes para quien quiera aprender a programar en C++ pero no forman parte del temario de la asignatura VJ1215 y no se exigirán.
Ten en cuenta que en este libro, por ser anterior a
C++11, se utiliza 0 donde nosotros
utilizaremos nullptr para representar el
valor nulo de un puntero. También cambió con C++11 la
notación de las listas de inicialización en los
constructores (antes se utilizaban paréntesis donde
ahora utilizaremos llaves).
En la última clase de teoría del curso finalizaremos el tema 1 introduciendo el concepto de coste amortizado y aplicándolo a analizar el coste de duplicar el tamaño de la memoria reservada cuando se llena en las implementaciones con vectores. Esto se complementará con otros ejemplos de coste amortizado en algoritmos que veremos en temas posteriores.
En este tema contamos con 8 horas de trabajo no presencial, a repartir como creas conveniente para completar tanto los ejercicios de prácticas que no puedas completar en clase como el resto de ejercicios. Esa estimación de tiempo no es válida si no conoces el contenido propio de la asignatura Programación II, completo, hasta el último módulo inclusive.
Vamos a hacer, entre otros, varios ejercicios de implementación de Tipos Abstractos de Datos en C++ empleando internamente listas enlazadas (unas simplemente enlazadas, otras doblemente enlazadas; unas con acceso directo al primer nodo y al último, otras con acceso directo a uno de ellos; etc.). Ello servirá no solo para poner en práctica los conceptos del Tema 2 sino también para adquirir una base para entender y realizar implementaciones más complejas en temas posteriores.
Como estamos aprendiendo C++ gradualmente y éste no es un curso completo de C++, no implementaremos clases con genericidad, sobrecarga de operadores, constructores de copia, etc., aunque con ello nuestros ejemplos y soluciones sean mejorables. Quien esté interesado puede consultar los libros recomendados para profundizar en esos temas y consultar al profesor.
Opcionalmente, en los ejercicios de refuerzo sobre recursión propuestos al principio del curso puedes encontrar más problemas con vectores que puedes resolver ahora con listas enlazadas si quieres seguir practicando recursión, y en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de implementación de Tipos Abstractos de Datos con listas enlazadas.
Clase de teoría TE1 22/09
Los ficheros que puedes encontrar en esta
carpeta Pila
contienen una implementación del TAD Pila
en la que se emplea una lista simplemente
enlazada para representar internamente los datos.
Estudia esa implementación de la clase Pila, con ayuda
de las explicaciones que se darán en clase y de cualquier otro
recurso que consideres adecuado.
Clase de prácticas LA2 27/09, LA1 y LA3 29/09
Descarga los tres ficheros que contiene la
carpeta Pila. Compílalos y
prueba el test como se indica a continuación:
g++ Pila.cpp -c
g++ Pila.o TestPila.cpp -o TestPila
./TestPila
Con la opción -c le decimos
a g++ que no tenemos
función main y el resultado no será un
ejecutable. En la primera compilación
obtenemos Pila.o. En la segunda
compilación lo unimos con el resultado de
compilar TestPila.cpp. Con la
opción -o podemos elegir el nombre del
ejecutable si no nos gusta a.out.
Aunque es recomendable compilar así cada parte por separado, también lo podríamos compilar y unir todo a la vez:
g++ Pila.cpp TestPila.cpp -o TestPila
./TestPila
También puedes probarlo con OnlineGDB: para ello, crea una pestaña por cada fichero de código fuente, como puedes ver aquí.
Clase de prácticas LA2 27/09, LA1 y LA3 29/09
Piensa cómo utilizar una lista enlazada
para realizar una implementación del
TAD Cola de modo que los
métodos encolar, desencolar
y consultarPrimero tengan coste O(1). ¿Es
necesario que sea doblemente enlazada?
Después de haberlo pensado, estudia la implementación
que puedes encontrar en esta
carpeta: Cola.
Observa lo que tiene en común y en qué se diferencia de
la implementación anterior del
TAD Pila. Es importante que entiendas
lo que se ha hecho para conseguir los costes O(1),
y en qué se diferencia de lo que se hizo
en Pila.
Compíla y prueba el test que se proporciona. Lo puedes hacer con OnlineGDB así.
La implementación anterior proporciona las operaciones básicas del TAD Cola, que son las que permiten encolar y desencolar elementos, y algunas más. En este ejercicio vas a enriquecerla con otras utilidades.
Una vez entendida, añade a esa implementación métodos que resuelvan los siguientes problemas. Si lo deseas, puedes partir del código en OnlineGDB que se da en el enlace anterior y pulsar el botón "Fork this" para obtener una copia editable en la que puedes escribir tus soluciones.
Con el objetivo de practicar mejor el uso de punteros en
C++, que es probablemente lo más novedoso para ti,
resuelve todos los apartados teniendo en cuenta que la
clase Cola no dispone de ningún atributo
que contenga la talla y suponiendo que no puedes añadírselo.
En cada apartado, piensa cuál es el coste temporal en el peor caso y en el mejor caso de tu solución.
Sin utilizar recursión, averiguar si un elemento aparece en la cola.
En el caso particular de que
la cola esté vacía, devuelve false.
bool buscar(int) const;
Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.
Sin utilizar recursión, averiguar la posición de la primera aparición de un elemento en la cola (contando desde cero; -1 indicará que no aparece).
int buscarPosicion(int) const;
Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.
Sin utilizar recursión, comprobar si dos colas son iguales, es decir, contienen los mismos elementos en las mismas posiciones. En el caso particular de que las dos colas estén vacías, considera que son iguales.
bool colasIguales(const Cola &) const;
Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.
Sin utilizar recursión, eliminar un elemento de la cola (si aparece más de una vez, hay que eliminar solamente la primera aparición; si no aparece, la cola no debe modificarse).
void eliminar(int);
Esto puede tener utilidad, por ejemplo, para eliminar de una cola de personas a una que decide abandonar antes de que le toque su turno.
Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.
Clase de prácticas LA2 04/10, LA1 y LA3 06/10
En este ejercicio vas a realizar una implementación del TAD Cola de Prioridad de Doble Fin (Double-ended Priority Queue) que soporte las operaciones del siguiente recuadro con los costes temporales que se indican, utilizando una lista enlazada para almacenar los datos.
ColaDePrioridadDeDobleFin(); // O(1) void insertar(int); // O(n) void eliminar(int); // O(n) void eliminarMinimo(); // O(1) int consultarMinimo() const; // O(1) void eliminarMaximo(); // O(1) int consultarMaximo() const; // O(1) int talla() const; // O(1) void mostrar() const; // O(n)
Una cola de prioridad de doble fin permite realizar las siguientes operaciones básicas: insertar un elemento que tiene una cierta prioridad, extraer un elemento de mínima prioridad y extraer un elemento de máxima prioridad. A eso vas a añadir en este ejercicio la posibilidad de eliminar de la cola de prioridad de doble fin el elemento que nos indiquen y otras utilidades. Por simplificar el problema y centrarnos en lo esencial, suponemos que la única información que se guarda de cada elemento es su prioridad, de tipo entero. En caso de empate entre varios elementos con la misma prioridad, las tres operaciones de eliminación pueden elegir uno cualquiera de ellos.
Antes de empezar a programar los métodos, empieza decidiendo qué tipo de lista enlazada utilizar para conseguir los costes del recuadro anterior: ¿necesitas que sea doblemente enlazada o basta con una lista simplemente enlazada? ¿Los datos deben estar ordenados de menor a mayor? ¿Cómo se puede consultar el mínimo en tiempo O(1)? ¿Cómo se puede eliminar el mínimo en tiempo O(1)? Etc.
Una vez tengas claro eso, escribe la declaración
de la clase
en ColaDePrioridadDeDobleFin.h (a
falta de añadir más adelante otros métodos
privados si hace falta).
Implementa el método mostrar. Tenerlo
disponible ya te ayudará a comprobar que tus
implementaciones de los restantes métodos
funcionan correctamente. Elige el formato que
prefieras para ver el contenido de la cola de
prioridad de doble fin.
Implementa el método insertar. Puedes
elegir hacerlo de forma recursiva o no recursiva:
debes aprender a escribir ambas soluciones.
Implementa a continuación los constructores que
hacen las inicializaciones necesarias para que tu
implementación de insertar funcione
correctamente.
Comprueba que por ahora todo funciona correctamente antes de seguir implementando otros métodos.
Implementa el método eliminar. Puedes
elegir hacerlo de forma recursiva o no recursiva:
debes aprender a escribir ambas soluciones.
Si se intenta eliminar un dato que no está en la cola de prioridad, lanza una excepción de tipo string.
Comprueba que funciona correctamente antes de seguir.
Completa la implementación de los restantes métodos públicos del recuadro anterior.
Lanza también una excepción de tipo string si se intenta eliminar o consultar el mínimo o el máximo en una cola de prioridad vacía.
Imagina ahora que en la solución anterior,
haciendo uso
de cualquiera
de estas dos implementaciones
de eliminar, sustituyésemos el
código del método eliminarMinimo por
una llamada
a eliminar(consultarMinimo()) y
análogamente sustituyésemos el código del
método eliminarMaximo por una llamada
a eliminar(consultarMaximo()). ¿Serían
buenos esos cambios, teniendo en cuenta el coste temporal?
Añade a tu implementación un método que permita eliminar todos los elementos de la cola.
void vaciar();
Tu solución debe ser eficiente. Analiza su coste temporal.
Añade a tu implementación un método que permita obtener una nueva cola de prioridad de doble fin que contenga la unión de dos colas de prioridad de doble fin dadas.
void unir(const ColaDePrioridadDeDobleFin &, const ColaDePrioridadDeDobleFin &);
Debes conseguir que c3.unir(c1, c2)
deje en c3 el resultado de
unir c1 y c2 y elimine
lo que hubiera previamente en c3, sin
que c1 y c2 se vean
modificadas. Si un dato inicialmente
aparece a veces en
c1 y b veces
en c2, aparecerá a + b
veces en
c3. Puede suceder
que c1, c2
y/o c3 estén inicialmente vacías.
Para que tu solución sea válida debe ser eficiente. Analiza su coste temporal.
Resuelve este apartado suponiendo que la clase no dispone de ningún atributo que contenga la talla ni puedes añadírselo.
Utilizando una lista enlazada para contener los datos, realiza una implementación del TAD Cola de Prioridad (Priority Queue) que soporte las siguientes operaciones con los costes temporales que se indican:
void insertar(int); // O(1) void eliminarMinimo(); // O(n) int consultarMinimo() const; // O(1)
Al igual que en el ejercicio 3, por simplificar el problema, suponemos que la única información que se guarda de cada elemento es su prioridad, de tipo entero.
Empieza de nuevo decidiendo qué tipo de lista enlazada utilizar en este caso y qué atributos poner en cada nodo y en cada cola de prioridad: ¿necesitas que la lista sea doblemente enlazada o basta con una lista simplemente enlazada? Etc.
Opcionalmente, aquí puedes encontrar una implementación más completa en un curso de "Programación Avanzada" con C++, anterior a C++11.
Para
implementar el TAD Cola de Prioridad
queremos utilizar una lista simplemente
enlazada con datos de tipo real, posiblemente
repetidos, que hacen el papel de prioridades. En cada
cola de prioridad tendremos un único atributo,
primero, para acceder al primer nodo de la
lista. En cada nodo tendremos dos
atributos: prioridad
y siguiente. Con esa representación
queremos soportar las siguientes operaciones, de modo
que las dos últimas se ejecuten en tiempo O(1) en el
peor caso:
void insertar(float); void eliminarMinimo(); // O(1) float consultarMinimo() const; // O(1)
Realiza esa implementación, completa. Implementa dos
versiones de insertar: una no recursiva y
otra recursiva. No puedes utilizar más atributos y tu
solución debe ser compatible con el coste temporal de
las dos operaciones que se ha indicado. ¿Cuál es el
coste temporal de la operación de inserción?
Solución (la versión 1 recursiva ilustra el uso de un puntero pasado por referencia; en el tema 3 volveremos a ver eso)
Considerando de nuevo el TAD Cola de Prioridad de los ejercicios anteriores, ¿cuál sería el coste temporal de cada una de las tres operaciones insertar, eliminarMínimo y consultarMínimo con cada una de las siguientes estructuras de datos?
En los apartados (i) y (ii) supón que la talla máxima del vector es conocida a priori y no se redimensiona.
En los temas 3 y 4 veremos cómo implementar esas operaciones eficientemente empleando árboles binarios de búsqueda auto-balanceables (equilibrados) y empleando montículos.
Clase de teoría TE1 06/10
Consideremos que el TAD Conjunto (Set) y el TAD Multiconjunto (Multiset) se caracterizan por las siguientes operaciones básicas, diferenciándose en que el primero no admite elementos duplicados y el segundo sí:
void insertar(float); // Inserta en el conjunto el dato que se le pasa void eliminar(float); // Elimina del conjunto el dato que se le pasa bool buscar(float) const; // Dice si se encuentra en el conjunto el dato que se le pasa
Para cada uno de los dos TADs, ¿cuál sería el coste temporal de cada una de esas tres operaciones con cada una de las siguientes estructuras de datos? Considera que al insertar un dato en un conjunto hay que comprobar que no estaba previamente.
En los apartados (i) y (ii) supón que la talla máxima del vector es conocida a priori y no se redimensiona.
En el tema 3 compararemos esos costes temporales con los que se obtienen empleando internamente un árbol binario de búsqueda o un árbol AVL.
Estamos utilizando una lista doblemente enlazada para
realizar una implementación del
TAD Lista con datos de tipo real. En
cada lista tenemos tres atributos:
talla, primero y ultimo. En cada nodo
tenemos tres atributos: dato, siguiente y
anterior. Todos los atributos tienen el significado habitual.
Implementa los métodos que se piden en los siguientes apartados. Analiza el coste temporal, en el mejor y el peor caso, de cada solución.
Realiza una implementación no recursiva del método
void insertar(float dato, int i);
que inserta el dato en la posición i-ésima de la lista, sabiendo que 0 ≤ i ≤ n, siendo n la talla de la lista antes de la inserción (si i vale 0, el dato se situará en la primera posición; si i vale n, el dato se situará en la última posición).
Si necesitas algún constructor, impleméntalo también.
Resuelve el problema anterior de forma recursiva.
Realiza una implementación no recursiva del método
void eliminar(int i);
que elimina el dato en la posición i-ésima de la lista, sabiendo que 0 ≤ i < n, siendo n la talla de la lista antes de la eliminación (si i vale 0, se eliminará el dato de la primera posición; si i vale n - 1, se eliminará el dato de la última posición).
Resuelve el problema anterior de forma recursiva.