Definición de Tipos Abstractos de Datos (TAD)

El Tipo Abstracto de Datos (TAD) Lista_Ciclistas[T] define una colección de elementos de tipo T, donde cada elemento representa un ciclista con los siguientes atributos: Nombre, Equipo y Tiempo. Esta estructura permite la gestión de listas de ciclistas, facilitando operaciones de creación, inserción, eliminación y búsqueda.

TAD Lista_Ciclistas[T]

Descripción

  • Las Lista_Ciclistas[T] son colecciones de elementos que, una vez insertados, no modifican sus atributos internos (Nombre, Equipo, Tiempo). Sin embargo, la estructura de la lista en sí es dinámica y permite la adición o eliminación de elementos.

Operaciones

  • Operación CrearLista(salida S: Lista_Ciclistas[T])
    • Calcula: Crea una lista vacía de elementos de tipo T.
  • Operación Insertar_Final(entrada/salida S: Lista_Ciclistas[T], Ciclista: T)
    • Modifica: S
    • Calcula: Inserta un elemento Ciclista (con sus atributos Nombre, Equipo, Tiempo) en la última posición de la lista S.
  • Operación Comparar(entrada S: Lista_Ciclistas[T]; salida posicion: int)
    • Calcula: Devuelve la primera posición (1-indexada) en la que se encuentra un ciclista duplicado en la lista S. Si no hay duplicados, la salida puede ser un valor especial (ej. 0 o -1).
  • Operación Eliminar(entrada/salida S: Lista_Ciclistas[T], posicion: int)
    • Requiere: 1 ≤ posicion ≤ tamaño(Lista_Ciclistas[T])
    • Modifica: S
    • Calcula: Elimina el nodo en la posicion indicada de la lista S y reorganiza los nodos sucesores para mantener la continuidad.
  • Operación Insertar(entrada/salida S: Lista_Ciclistas[T], Ciclista: T, posicion: int)
    • Requiere: 1 ≤ posicion ≤ tamaño(Lista_Ciclistas[T]) + 1
    • Modifica: S
    • Calcula: Inserta un elemento Ciclista en la posicion indicada de la lista S, desplazando los elementos posteriores una posición hacia adelante.

Ejemplos de Trazas de Operaciones

Traza 1: Creación e Inserción

  1. S = CrearLista()
  2. Insertar_Final(S, Ciclista[Nombre, Equipo, Tiempo])
  3. Insertar_Final(S, Ciclista[Nombre, Equipo, Tiempo])
  4. Insertar_Final(S, Ciclista[Nombre, Equipo, Tiempo])

Traza 2: Eliminación e Inserción en Posición Específica

  1. Eliminar(S, 5)
  2. Insertar(S, Ciclista[Nombre, Equipo, Tiempo], 2)

Implementación de Estructuras de Datos en Python

A continuación, se presentan implementaciones en Python de dos estructuras de datos fundamentales: un Conjunto (utilizando una lista enlazada ordenada con centinelas) y una Lista Enlazada básica.

Clase Conjunto: Implementación con Lista Enlazada Ordenada

Esta implementación de un conjunto utiliza nodos enlazados para almacenar elementos de forma ordenada y sin duplicados, empleando nodos centinela para simplificar las operaciones de inserción, unión e intersección.

Definición de Nodo para Conjunto

class Nodo:
    def __init__(self, dato=None):
        self.dato = dato
        self.siguiente = None

Clase Conjunto

class Conjunto:
    def __init__(self):
        self.cabeza = Nodo()  # Nodo cabecera sin valor
        self.centinela = Nodo(float('inf'))  # Nodo centinela con valor máximo
        self.cabeza.siguiente = self.centinela  # La lista comienza apuntando al centinela

    def insertar(self, dato):
        """Inserta un elemento en orden si no está presente."""
        anterior = self.cabeza
        actual = self.cabeza.siguiente
        while actual.dato < dato:
            anterior, actual = actual, actual.siguiente
        if actual.dato == dato:
            return  # No insertar duplicados
        nuevo_nodo = Nodo(dato)
        anterior.siguiente = nuevo_nodo
        nuevo_nodo.siguiente = actual

    def union(self, otro):
        """Devuelve un nuevo conjunto que es la unión de este con otro."""
        C = Conjunto()
        c1, c2 = self.cabeza.siguiente, otro.cabeza.siguiente

        while c1 != self.centinela or c2 != otro.centinela:
            if c1 == self.centinela: # c1 agotado, añadir restantes de c2
                C.insertar(c2.dato)
                c2 = c2.siguiente
            elif c2 == otro.centinela: # c2 agotado, añadir restantes de c1
                C.insertar(c1.dato)
                c1 = c1.siguiente
            elif c1.dato < c2.dato:
                C.insertar(c1.dato)
                c1 = c1.siguiente
            elif c2.dato < c1.dato:
                C.insertar(c2.dato)
                c2 = c2.siguiente
            else:  # Son iguales
                C.insertar(c1.dato)
                c1 = c1.siguiente
                c2 = c2.siguiente
        return C

    def interseccion(self, otro):
        """Devuelve un nuevo conjunto que es la intersección de este con otro."""
        C = Conjunto()
        c1, c2 = self.cabeza.siguiente, otro.cabeza.siguiente

        while c1 != self.centinela and c2 != otro.centinela:
            if c1.dato < c2.dato:
                c1 = c1.siguiente
            elif c1.dato > c2.dato:
                c2 = c2.siguiente
            else:  # Elemento común
                C.insertar(c1.dato) # también valdría c2
                c1 = c1.siguiente
                c2 = c2.siguiente
        return C

    def mostrar(self):
        """Muestra el conjunto como una lista ordenada."""
        elementos = []
        actual = self.cabeza.siguiente
        while actual != self.centinela:
            elementos.append(actual.dato)
            actual = actual.siguiente
        print("{", ", ".join(map(str, elementos)), "}")

Ejemplo de Uso de Conjunto

A = Conjunto()
A.insertar(3)
A.insertar(6)
A.insertar(5)

print("A: ", end='')
A.mostrar() # Salida esperada: A: {3, 5, 6}

B = Conjunto()
B.insertar(6)
B.insertar(3)
B.insertar(2)
print("B: ", end='')
B.mostrar() # Salida esperada: B: {2, 3, 6}

C = A.union(B)
print("A union B: ", end='')
C.mostrar() # Salida esperada: {2, 3, 5, 6}

D = A.interseccion(B)
print("A interseccion B: ", end='')
D.mostrar() # Salida esperada: {3, 6}

Clase ListaEnlazada: Implementación Básica

Esta sección presenta una implementación fundamental de una lista enlazada simple, que permite operaciones básicas como agregar elementos al inicio o al final, eliminar, buscar y obtener el tamaño.

Definición de Nodo para ListaEnlazada

class Nodo:
    """
    Clase que representa un nodo de la lista enlazada.
    """
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None  # Puntero al siguiente nodo

Clase ListaEnlazada

class ListaEnlazada:
    """
    Clase que representa la lista enlazada dinámica.
    """
    def __init__(self):
        self.cabeza = None  # Puntero al primer nodo de la lista
        self.tamano = 0     # Número de elementos en la lista

    def esta_vacia(self):
        """
        Verifica si la lista está vacía.
        """
        return self.cabeza is None

    def agregar_al_final(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.esta_vacia():
            self.cabeza = nuevo_nodo
        else:
            actual = self.cabeza
            while actual.siguiente is not None:  # Avanzar hasta el último nodo
                actual = actual.siguiente
            actual.siguiente = nuevo_nodo
        self.tamano += 1

    def agregar_al_inicio(self, dato):
        """
        Agrega un nuevo elemento al inicio de la lista.
        """
        nuevo_nodo = Nodo(dato)
        nuevo_nodo.siguiente = self.cabeza
        self.cabeza = nuevo_nodo
        self.tamano += 1

    def eliminar(self, dato):
        """
        Elimina el primer nodo que contiene el dato especificado.
        """
        if self.esta_vacia():
            print("La lista está vacía.")
            return

        actual = self.cabeza
        anterior = None
        while actual is not None:
            if actual.dato == dato:
                if anterior is None:  # El nodo a eliminar es la cabeza
                    self.cabeza = actual.siguiente
                else:
                    anterior.siguiente = actual.siguiente
                self.tamano -= 1
                return
            anterior = actual
            actual = actual.siguiente
        print("El elemento no se encontró en la lista.")

    def mostrar(self):
        """
        Muestra todos los elementos de la lista.
        """
        elementos = []
        actual = self.cabeza
        while actual is not None:
            elementos.append(actual.dato)
            actual = actual.siguiente
        print("Lista:", " -> ".join(map(str, elementos)))

    def buscar(self, dato):
        """
        Busca un elemento en la lista y devuelve True si existe.
        """
        actual = self.cabeza
        while actual is not None:
            if actual.dato == dato:
                return True
            actual = actual.siguiente
        return False

    def obtener_tamano(self):
        """
        Devuelve el tamaño de la lista.
        """
        return self.tamano

Ejemplo de Uso de ListaEnlazada

# Ejemplo de uso
lista = ListaEnlazada()

lista.agregar_al_inicio(10)
lista.agregar_al_final(20)
lista.agregar_al_final(30)
lista.mostrar()  # Salida esperada: Lista: 10 -> 20 -> 30

lista.eliminar(20)
lista.mostrar()  # Salida esperada: Lista: 10 -> 30

print("Existe el 30:", lista.buscar(30))  # Salida esperada: Existe el 30: True
print("Tamaño de la lista:", lista.obtener_tamano())  # Salida esperada: Tamaño de la lista: 2