Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

2. Listas, pilas y colas mediante listas enlazadas

Horas de clases presenciales: 8 (4 teoría + 4 prácticas)
Horas de trabajo no presencial: 8
Ratio: 2 horas no presenciales por cada clase de 2 horas

Recursos

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:

  1. 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:

    • 3.1 Abstract Data Types (ADTs)
    • 3.2 The List ADT
      • 3.2.1 Simple Array Implementation of Lists
      • 3.2.2 Simple Linked Lists
    • 3.6 The Stack ADT
      • 3.6.1 Stack Model
      • 3.6.2 Implementation of Stacks
    • 3.7 The Queue ADT
      • 3.7.1 Queue Model
      • 3.7.2 Array Implementation of Queues
  2. 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):

    • 6. Listas
      • 6.4 Introducción a las listas enlazadas
      • 6.5 Una implementación de listas enlazadas basada en punteros en C++
    • 7. Pilas
      • 7.3 Pilas enlazadas
    • 8. Colas
      • 8.3 Colas enlazadas

    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 las clases de teoría del 21-23/09 introduciremos también el concepto de coste amortizado, 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 temas posteriores.

Recursos opcionales

Si buscas un buen libro para aprender C++ más allá de lo que vamos a ver en esta asignatura, mira "Big C++" (2009) de Cay Horstmann y Timothy Budd. Aunque es anterior a la estandarización del C++11, en el capítulo 21 avanza algunas de sus principales novedades. Por lo demás, es un libro muy recomendable.

Opcionalmente también, las siguientes referencias proporcionan más información sobre el coste amortizado de duplicar la capacidad de un vector introducido en clase:

Ejercicios

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.

  1. Clase de teoría TE2 14/09, TE1 16/09

    Descarga 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. 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.

    Recuerda que, si en tu ordenador tienes una versión de g++ más antigua que la que tenemos este curso en las aulas, es posible que tengas que informarle de que usas C++11 añadiendo -std=c++11.

    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í.

    Estudia la 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.

  2. Clase de prácticas LA2 y LA4 21/09, LA1 y LA3 23/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.

    1. 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;
      		

      Solución

    2. Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.

      Solución

      Busca errores

    3. 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;
      		

      Solución

    4. Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.

      Solución

      Busca errores

    5. 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;
      		

      Solución

      Busca errores

    6. Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.

      Solución

      Busca errores

    7. 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.

      Solución

      Busca errores

    8. Resuelve el problema anterior utilizando recursión, sin utilizar ningún bucle.

      Solución (incluye un ejemplo de puntero pasado por referencia)

      Busca errores (solución alternativa)

  3. Clase de prácticas LA2 y LA4 28/09, LA1 y LA3 30/09

    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.

    1. 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).

      Solución

    2. 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.

      Solución

    3. 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.

      Solución

      Busca errores

    4. 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.

      Solución

      Busca errores

    5. 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.

      Solución completa

      Busca errores

    6. 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?

      Solución

    7. 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.

      Solución

    8. 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.

      Ayuda

      Solución

      Busca errores

      Código de prueba

  4. Clase de teoría TE2 14/09

    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.

    Solución

    Busca errores

    Código de prueba

    Opcionalmente, aquí puedes encontrar una implementación más completa en un curso de "Programación Avanzada" con C++, anterior a C++11.

  5. 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 (ilustra el uso de un puntero pasado por referencia)

    Busca errores

    Código de prueba

  6. Clase de teoría TE2 14/09

    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?

    1. vector no ordenado
    2. vector ordenado
    3. lista enlazada no ordenada
    4. lista enlazada ordenada

    En los apartados (i) y (ii) supón que la talla máxima del vector es conocida a priori y no se redimensiona.

    Solución

    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.

  7. 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.

    1. vector no ordenado
    2. vector ordenado
    3. lista enlazada no ordenada
    4. lista enlazada ordenada

    En los apartados (i) y (ii) supón que la talla máxima del vector es conocida a priori y no se redimensiona.

    Solución

    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.

  8. 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 y espacial, en el mejor y el peor caso, de cada solución.

    1. 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.

      Solución

    2. Resuelve el problema anterior de forma recursiva.

      Solución

    3. 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).

      Solución

    4. Resuelve el problema anterior de forma recursiva.

      Solución

    Código de prueba