💻 Ejercicios prácticos – Estructuras dinámicas

[GabrielEValenzuela]

⏱️ Duración estimada: 1 hora

Objetivo: Reforzar conocimientos de listas, pilas y colas aplicadas a situaciones concretas dentro del universo Refugio 33.

---

🧠 Ejercicio 1 – Búsqueda de suministros en la lista

En el sistema de gestión del Refugio 33, los recursos se almacenan en una lista dinámica (lista simplemente enlazada) ordenada por nombre. Cada nodo representa un Supply, con su nombre (clave) y cantidad.

Implementá la función SEARCH(S, k) que devuelva el puntero al suministro con nombre k, o nullptr si no existe.

Extendé la funcionalidad implementando:

• MINIMUM(S) – devuelve el suministro alfabéticamente menor.
• MAXIMUM(S) – idem, pero el mayor.
• SUCCESSOR(S, x) – dado un suministro, devolvé el siguiente en orden alfabético.

Tip: Podés usar clases simples como struct Supply { std::string name; int quantity; };

---

🔁 Ejercicio 2 – Unión de listas de comerciantes

Dos caravanas aliadas llegan al refugio, cada una con una lista ordenada de comerciantes que desean intercambiar bienes. Necesitamos fusionar ambas listas en una sola sin duplicados.

Implementá:

• intersect(L1, L2) – devuelve una nueva lista con los comerciantes en común.
• merge(L1, L2) – devuelve la unión ordenada de las dos listas.

Usá solo operaciones básicas de listas: acceso, inserción, avance de punteros.

---

💣 Ejercicio 3 – Heaps fusionables con listas

En Refugio 33, los conflictos se manejan con un heap de amenazas. Cada amenaza tiene una prioridad (más baja = más urgente). Queremos representar este heap usando listas enlazadas.

Implementá una estructura ThreatHeap que permita:

• INSERT
• MINIMUM
• EXTRACT-MIN
• UNION(Heap1, Heap2)

Analizá la complejidad de cada operación en estos tres escenarios:

1. Si las listas están ordenadas.
2. Si las listas están desordenadas.
3. Si las listas están desordenadas y disjuntas.

Consejo: Usá punteros a nodos Threat { int priority; std::string name; };.

---

👻 Ejercicio 4 – Eliminación perezosa en listas

Algunos registros de eventos del refugio ya no son válidos, pero por motivos de auditoría, no los eliminamos físicamente. Usamos lazy deletion: marcamos como borrado y solo limpiamos cuando hay tantos borrados como activos.

Implementá:

• lazyDelete(x) – marca el nodo como eliminado.
• realDeleteIfThresholdReached() – si hay tantos borrados como activos, limpia la lista.

Describí:

• Ventajas y desventajas de esta técnica.
• Compará memoria y performance con eliminación inmediata.

---

🔍 Ejercicio 5 – Implementá tu propio find

A veces, el sistema necesita encontrar un recurso o personaje rápidamente dentro de un rango. Implementá tu propia versión del algoritmo STL std::find.

template <typename Iterator, typename Object>
Iterator find(Iterator start, Iterator end, const Object& x);

Debe retornar el primer iterador donde *it == x, o end si no lo encuentra.

Probalo con una lista de nombres, una lista de enteros, o incluso un vector de NPCs.

---

🔭 Ejercicio 6 – Quién puede ver a quién en el refugio

Dentro del pasillo principal del Refugio, los habitantes están parados en fila según su altura. Un habitante puede ver a otro si nadie entre medio es más alto que ambos.

Implementá una función que reciba un std::vector<int> alturas y devuelva cuántas personas puede ver cada una hacia la derecha.

std::vector<int> cuantasPuedeVer(const std::vector<int>& alturas);

Este ejercicio evalúa comprensión de pilas y recorrido de vectores.

[EnzoFernandezz11]

#include <vector>

template <typename TData>
struct Nodo
{
    TData data;
    Nodo* next;
    explicit Nodo(const TData& value) : data(value),next(nullptr){}
};

template <typename TData>
class Lista
{
    private:
        Nodo<TData>* head;
    public:
        Lista() : head(nullptr) {}

        ~Lista()
        {
            while(head != nullptr)
            {
                auto temp = head;
                head = head->next;
                delete temp;
            };
        }

        void add(TData& value)
        {
            auto new_node = new Nodo<TData>(value);
            new_node->next = head;
            head = new_node;
        }

        Nodo<TData>* getHead() const
        {
            return head;
        }
        
};



//Ejercicio 1
struct Supply { std::string name; int quantity; }; 
Nodo<Supply>* search(Lista<Supply>& S, const std::string& k)
{
    auto temp = S.getHead(); 
    while (temp != nullptr) 
    {
        if (temp->data.name == k) 
        {
            return temp; 
        }
        temp = temp->next; 
    }
    return nullptr; 

}

std::string minimun(Lista<Supply>& S)
{
    return ((S.getHead())->data.name);

}

std::string maximun(Lista<Supply>& S)
{
    auto temp = S.getHead(); 
    while (temp != nullptr) 
    {
        if (temp->next == nullptr) 
        {
            return temp->data.name; 
        }
        temp = temp->next; 
    }

}

std::string succesor(Lista<Supply>& S, std::string x)
{
    auto x_search = search(S,x);
    while (x_search != nullptr) 
    {
        if (x_search->next->data.name[0] > x_search->data.name[0]) 
        {
            return x_search->data.name; 
        }
    }

}

//Ejercicio 2

Lista<std::string> intersect(Lista<std::string>& l1,Lista<std::string>& l2 )
{
    Lista<std::string> L_comb;
    auto temp_l1 = l1.getHead();
    auto temp_l2 = l2.getHead();
    while(temp_l1 != nullptr) //Asumo que l1 y l2 son del mismo tamaño
    {
        if(temp_l1->data == temp_l2->data)
        {
            L_comb.add(temp_l1->data); // simplifico el caso suponiendo que en una misma lista no hay nombre repetidos
        }
        temp_l1 = temp_l1->next;
        temp_l2 = temp_l2->next;
    }

}

Lista<std::string> merge(Lista<std::string>& l1,Lista<std::string>& l2 )
{
    //complejidad alta ya que tendria que ir como "intercalando" para crear una lista ordeanda de mayor a menor
}

//Ejercicio 3

struct Threat { int priority; std::string name; };


class ThreatHeap 
{
    private:
        Lista<Threat> threats;
    public:
        //implentacion de insert para una lista desordenada
        void insert(int p, std::string name)
        {
            Threat newThreat{p, name}; 
            threats.add(newThreat);    
        }
        //si fuera una lista ordenada, tendria que buscar el lugar adecuado para insetar el nodo con respecto a p
        
        //implentacion para una lista ordenada de menor a mayor
        std::string minum()
        {
            return threats.getHead()->data.name;
        }
        // si fuera una lista desordenada tendria que buscar el minimo entre toda la listas que hay

        //idem anterior
        Nodo<Threat>* extract_min()
        {
            return threats.getHead();
        }

        //implementacion si la listas fueran desordenadas
        Lista<Threat> union_heap(Lista<Threat>& Heap1, Lista<Threat>& Heap2)
        {
            Lista<Threat> union_h;
            auto temp_heap1 = Heap1.getHead();
            auto temp_heap2 = Heap2.getHead();
            while (temp_heap1 != nullptr && temp_heap1 != nullptr) 
            {
                union_h.add(temp_heap1->data);
                union_h.add(temp_heap2->data);
    
                temp_heap1 = temp_heap1->next;
                temp_heap2 = temp_heap1->next;
            }
            return union_h;
            //si fuera una lista ordenada tendria que ir verificando las proridades e ir agregando
        }   

//Ejercicio 4
struct Register{bool state; int id_register;}; //state 0 ->borrado , estate 1 -> activo

void leazydelete(Lista<Register>& r,int& x)
{
    auto temp = r.getHead();
    while(temp != nullptr)
    {
        if(temp->data.id_register == x)
        {
            temp->data.state = 0;
        }
        temp = temp->next;
    }
}

void realDeleteIfThresholdReached(Lista<Register>& r,int& x)
{
    auto temp = r.getHead();
    int borrado = 0;
    int activo = 0;
    while(temp != nullptr)
    {
        if(temp->data.state == 0)
        {
            borrado++;
        }else{ activo++; }
        temp = temp->next;
    }
    if(borrado == activo)
    {
        r.~Lista();
    }
}
// La desventaja qeu tiene es que no se ahorra memoria eliminando el nodo, pero al mismo tiempo se gana ya que tenemos un backup de la informacion

//Ejercicio 5
//suponiendo que es sobre una lista
template <typename Iterator, typename Object>
Iterator find(Iterator start, Iterator end, const Object& x)
{
    while(start != nullptr)
    {
        if(*start == x)
        {
            return start;
        }
        if(start == end)
        {
            return end;
        }
        start = start->next;
    }
}

//Ejercicio 6
std::vector<int> cuantasPuedeVer(const std::vector<int>& alturas)
{
    std::vector<int> vistas(alturas.size(), 0);
    for(int i = 0; i < alturas.size() ; i++ )
    {
        int maxAltura = 0; 
        for (int j = i + 1; j < alturas.size(); j++)
        {
            if (alturas[j] > maxAltura)
            {
                vistas[i]++;
                maxAltura = alturas[j];
            }
            if (alturas[j] >= alturas[i])
            {
                break; 
            }
        }
    }
    return vistas;
}

};> ```

[Danteps-4]

Resolución de ejercicio 1,2 y 4

#include <iostream>
#include <ostream>
#include <string>

template <typename TData>
struct ListNode
{
    TData data;
    ListNode* next;

    explicit ListNode(const TData& value)
        : data(value)
        , next(nullptr)
    {
    }
};

template <typename TData>
class List {
private:
    ListNode<TData>* head;

public:
    List()
        : head(nullptr)
    {
    }

    ~List()
    {
        while(head != nullptr)
        {
            auto temporalNode = head;
            head = head->next;
            delete temporalNode;
        }
    }
    void push_front(const TData& value)
    {
        auto nuevo = new ListNode<TData>(value);
        nuevo->next = head;
        head = nuevo;
    }

    ListNode<TData>* get_head() const
    {
        return head;
    }

    bool search(const TData& value) {
        if (head == nullptr) {
            return false;
        }
        auto temporal = head;
        while (temporal != nullptr) {
            if (temporal->data.name == value.name) {
                return true;
            }
            temporal = temporal->next;
        }

        return false;
    }
};


// Ejercicio 1 – Búsqueda de suministros en la lista
struct Supply {
    std::string name;
    int quantity;

    Supply(std::string name, int quantity):name(std::move(name)), quantity(quantity) {}
};

ListNode<Supply>* search(List<Supply>& s, const std::string& k) {
    if (s.get_head() == nullptr) {
        return nullptr;
    }

    auto temporal = s.get_head();
    while (temporal != nullptr) {
        if (k == temporal->data.name) {
            return temporal;
        }
        temporal = temporal->next;
    }
    return nullptr;
}

// Ejercicio 2 – Unión de listas de comerciantes
struct Comerciante {
    std::string name;

    explicit Comerciante(std::string  name) : name(std::move(name)) {}
};

List<Comerciante>* intersect(List<Comerciante>& l1, List<Comerciante>& l2) {
    if (l1.get_head() == nullptr) {
        return &l2;
    }
    if (l2.get_head() == nullptr) {
        return &l1;
    }

    auto listaIntersect = new List<Comerciante>();
    auto temporal1 = l1.get_head();
    while (temporal1 != nullptr) {
        auto temporal2 = l2.get_head();
        while (temporal2 != nullptr) {
            if (temporal2->data.name == temporal1->data.name) {
                auto repetido = listaIntersect->search(temporal2->data);
                if (!repetido) {
                    listaIntersect->push_front(temporal2->data);
                }
            }
            temporal2 = temporal2->next;
        }
        temporal1 = temporal1->next;
    }
    return listaIntersect;
}

List<Comerciante>* merge(List<Comerciante>& l1, List<Comerciante>& l2) {
    if (l1.get_head() == nullptr) {
        return &l2;
    }
    if (l2.get_head() == nullptr) {
        return &l1;
    }
    auto listaMerge = new List<Comerciante>();
    auto temporal1 = l1.get_head();
    auto temporal2 = l2.get_head();
    while (temporal1 != nullptr && temporal2 != nullptr) {
        if (temporal2->data.name == temporal1->data.name) {
            if (!listaMerge->search(temporal1->data)) {
                listaMerge->push_front(temporal2->data);
            }
        }
        if (!listaMerge->search(temporal1->data)) {
            listaMerge->push_front(temporal1->data);
        }
        if (!listaMerge->search(temporal2->data)) {
            listaMerge->push_front(temporal2->data);
        }
        temporal1 = temporal1->next;
        temporal2 = temporal2->next;
    }

    while (temporal1 != nullptr) {
        if (!listaMerge->search(temporal1->data))
            listaMerge->push_front(temporal1->data);
        temporal1 = temporal1->next;
    }

    while (temporal2 != nullptr) {
        if (!listaMerge->search(temporal2->data))
            listaMerge->push_front(temporal2->data);
        temporal2 = temporal2->next;
    }

    return listaMerge;
}

// Ejercicio 4 – Eliminación perezosa en listas

struct Evento {
    bool state;
    std::string name;

    Evento(bool state, std::string name) : state(state), name(std::move(name)) {}
};

void lazyDelete(List<Evento>& l, const std::string& name) {
    auto temporal = l.get_head();
    while (temporal != nullptr) {
        if (temporal->data.name == name) {
            temporal->data.state = false;
        }
        temporal = temporal->next;
    }
}

void realDeleteIfThresholdReached(List<Evento>& l) {
    auto temporal = l.get_head();
    int activos = 0;
    int desactivos = 0;
    while (temporal != nullptr) {
        if (temporal->data.state == true) {
            activos++;
        } else {
            desactivos++;
        }
        temporal = temporal->next;
    }
    if (desactivos >= activos) {
        l.~List();
    }
}

[LeoI3assi]

//
// Created by leand on 19/4/2025.
//
#include "Supply.h"
#include "Comerciantes.h"
#include "Nodo.h"
#include "Lista.h"
#include "ThreatHeap.h"
#include "Registro.h"
#include <vector>

//Ejercicio 1:

Nodo<Supply>* search(Lista<Supply>& S, const std::string& n) {
  if (S.get_Head()== nullptr) {
    return nullptr;
  }
  auto head = S.get_Head();
  while (head != nullptr) {
    if (head->data.name == n) {
      return head;
    }
    head = head->next;
  }
  return nullptr;
}

std::string minimun(Lista<Supply>& S) {
  return S.get_Head()->data.name;
}

std::string maximun(Lista<Supply>& S) {
return S.get_Tail()->data.name;
}

std::string successor(Lista<Supply>& S, const std::string& x) {
  Nodo<Supply>* current = S.get_Head();
  std::string succ = "";

  while (current != nullptr) {
    const std::string& name = current->data.name;

    if (name > x && (succ == "" || name < succ)) {
      succ = name;
    }

    current = current->next;
  }

  if (succ == "") {
    return "NO HAY SUCESOR";
  }

  return succ;
}


//Ejercicio 2:

//Implementación de Intersect:

Lista<Comerciantes> intersect(Lista<Comerciantes>& l1, Lista<Comerciantes>& l2) {
  Lista<Comerciantes> l3;
  Nodo<Comerciantes>* p1 = l1.get_Head();
  Nodo<Comerciantes>* p2 = l2.get_Head();

  while (p1 != nullptr && p2 != nullptr) {
    if (p1->data.name == p2->data.name) {
      l3.add(p1->data);
      p1 = p1->next;
      p2 = p2->next;
    }
    else if (p1->data.name < p2->data.name) {
      p1 = p1->next;
    }
    else {
      p2 = p2->next;
    }
  }

  return l3;
}

//Implementación de Merge:

Lista<Comerciantes> merge(Lista<Comerciantes> l1, Lista<Comerciantes> l2) {
  Lista<Comerciantes> l3;
  Nodo<Comerciantes>* p1 = l1.get_Head();
  Nodo<Comerciantes>* p2 = l2.get_Head();

  while (p1 != nullptr && p2 != nullptr) {

    if (p1->data.name == p2->data.name) {
      l3.add(p1->data);
      p1 = p1->next;
    }
    else if (p1->data.name < p2->data.name) {
      l3.add(p1->data);
      p1 = p1->next;
    }
    else {
      l3.add(p2->data);
      p2 = p2->next;
    }
  }
  while (p1 != nullptr) {
    l3.add(p1->data);
    p1 = p1->next;
  }
  while (p2 != nullptr) {
    l3.add(p2->data);
    p2 = p2->next;
  }
  return l3;
}

//Ejercicio 3:

class Threat {
private:
  Lista<ThreatHeap> threats;
public:
  //Implementación de Insert(Lista Desordenada):
  void insert(int priority, const std::string& name) {
    ThreatHeap new_th = {priority, name};
    threats.add(new_th);
  }
  /* OBSERVACIÓN: Si la Lista<ThreatHeap> estuviera ordenada tendría que ir recorriendo la misma e ir comparando
   * las diferentes prioridades de cada amenaza hasta asignarle el lugar correspondiente a mi new_th. Si se presentara
   * el caso en donde 2 o más amenazas tuvieran la misma prioridad debería tener un criterio extra para su correcto
   * ordenamiento.
  */

  //Implementación de Minimum(Lista ORDENADA):
  std::string minimum() {
    return threats.get_Head()->data.name;
  }
  /* OBSERVACIÓN: Si la lista estuviera DESORDENADA tendría que recorrerla Nodo a Nodo, comparando los distintos niveles
   * de amenaza y retornar la más prioritaria.
  */


  //Implementacion de Extract-Min(Lista ORDENADA):
  Nodo<ThreatHeap>* extract_min() {
    return threats.get_Head();
  }
  /* OBSERVACIÓN: Si la lista estuviera DESORDENADA tendría que recorrerla Nodo a Nodo, comparando los distintos niveles
   * de amenaza y retornar la más prioritaria.
  */

  //Implementación de Union(Lista DESORDENADA):
  static Lista<ThreatHeap> union_lists(Lista<ThreatHeap>& h1, Lista<ThreatHeap>& h2)
  {
    Lista<ThreatHeap> union_list;
    auto temp1 = h1.get_Head();
    auto temp2 = h2.get_Head();

    while (temp1 != nullptr || temp2 != nullptr)
    {
      if (temp1 != nullptr) {
        union_list.add(temp1->data);
        temp1 = temp1->next;
      }
      if (temp2 != nullptr) {
        union_list.add(temp2->data);
        temp2 = temp2->next;
      }
    }
    return union_list;
  }
  /* OBSERVACION: Si la lista estuviera ordenada debería implementar otro código para comparar los niveles de amenaza de
   * los diferentes elementos de cada lista y ordenarlos desde el mas urgente (menor nivel de amenaza) al menos urgente
   * (mayor nivel de amenaza) en una tercer lista
  */
};

//Ejercicio 4:
void lazydelete(Lista<Registro>& reg, const int& n ) {

  auto temp = reg.get_Head();
  while (temp != nullptr) {
    if (temp->data.direc == n) {
      temp->data.estado = false;
    }
    temp = temp->next;
  }
}

void realDeleteIfThresholdReached(Lista<Registro>& reg) {
  auto temp = reg.get_Head();
  int n_active = 0;
  int n_removed = 0;
  while (temp != nullptr) {
    if (temp->data.estado == true) {
      n_active++;
      temp = temp->next;
    }
    else {
      n_removed++;
      temp = temp->next;
    }
  }
  if (n_active == n_removed) {
      reg.~Lista();
  }
}

/* OBSERVACIONES:
 *
 * VENTAJAS:
 * -Simplicidad en la Eliminación (No hace falta reordenar nada, simplemente marcamos un elemento como "false" o "true").
 * -Mejor rendimiento en tiempo de eliminación.
 * -Perserva el Historial (Los elementos siguen estando en memoria).
 * -Evitamos operaciones costosas.
 *
 * DESVENTAJAS:
 * -Uso adicional de Memoria.
 * -Complejidad en Operaciones de Búsqueda.
 * -Mantenimiento de Contadores.
 *
*/

// Ejercicio 5:
template <typename Iterator, typename Object>
Iterator find(Iterator start, Iterator end, const Object& x)
{
  while (start != end) {
    if (*start == x) {
      return start;
    }
    ++start;
  }
  return end;
}

// Ejercicio 6:
std::vector<int> cuantasPuedeVer(const std::vector<int>& alturas)
{
  std::vector<int> personas(alturas.size(), 0);
  for(int i = 0; i < alturas.size() ; i++ )
  {
    int maxAltura = 0;
    for (int j = i + 1; j < alturas.size(); j++)
    {
      if (alturas[j] > maxAltura)
      {
        personas[i]++;
        maxAltura = alturas[j];
      }
      if (alturas[j] >= alturas[i])
      {
        break;
      }
    }
  }
  return personas;
}