El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Estructuras de Datos Avanzadas

Siguiente ►
►

En este módulo, exploraremos estructuras de datos avanzadas en Python que son esenciales para resolver problemas complejos de manera eficiente. Estas estructuras de datos incluyen listas enlazadas, pilas, colas, árboles y grafos. Aprenderemos cómo implementarlas y utilizarlas en Python.

Contenido

  1. Listas Enlazadas
  2. Pilas
  3. Colas
  4. Árboles
  5. Grafos

  1. Listas Enlazadas

Concepto

Una lista enlazada es una colección de nodos donde cada nodo contiene un valor y una referencia al siguiente nodo en la secuencia. A diferencia de las listas en Python, las listas enlazadas no almacenan sus elementos en ubicaciones contiguas en memoria.

Implementación en Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

# Ejemplo de uso
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()

Explicación

  • Node: Clase que representa un nodo en la lista enlazada.
  • LinkedList: Clase que maneja la lista enlazada.
  • append: Método para agregar un nodo al final de la lista.
  • print_list: Método para imprimir los elementos de la lista.

Ejercicio

Implementa un método insert_at_position en la clase LinkedList que inserte un nodo en una posición específica.

def insert_at_position(self, data, position):
    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return
    current_node = self.head
    for _ in range(position - 1):
        if not current_node:
            raise IndexError("Position out of bounds")
        current_node = current_node.next
    new_node.next = current_node.next
    current_node.next = new_node

  1. Pilas

Concepto

Una pila es una estructura de datos que sigue el principio LIFO (Last In, First Out). Los elementos se agregan y se eliminan desde el mismo extremo, conocido como el "tope" de la pila.

Implementación en Python

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

# Ejemplo de uso
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())  # 3
print(s.peek())  # 2

Explicación

  • Stack: Clase que representa una pila.
  • push: Método para agregar un elemento a la pila.
  • pop: Método para eliminar y devolver el elemento del tope de la pila.
  • peek: Método para devolver el elemento del tope sin eliminarlo.
  • is_empty: Método para verificar si la pila está vacía.

Ejercicio

Implementa un método size en la clase Stack que devuelva el número de elementos en la pila.

def size(self):
    return len(self.stack)

  1. Colas

Concepto

Una cola es una estructura de datos que sigue el principio FIFO (First In, First Out). Los elementos se agregan en un extremo (final) y se eliminan desde el otro extremo (frente).

Implementación en Python

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        return "Queue is empty"

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

# Ejemplo de uso
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.peek())  # 2

Explicación

  • Queue: Clase que representa una cola.
  • enqueue: Método para agregar un elemento al final de la cola.
  • dequeue: Método para eliminar y devolver el elemento del frente de la cola.
  • peek: Método para devolver el elemento del frente sin eliminarlo.
  • is_empty: Método para verificar si la cola está vacía.

Ejercicio

Implementa un método size en la clase Queue que devuelva el número de elementos en la cola.

def size(self):
    return len(self.queue)

  1. Árboles

Concepto

Un árbol es una estructura de datos jerárquica que consiste en nodos, donde cada nodo tiene un valor y referencias a sus nodos hijos. El nodo superior se llama raíz.

Implementación en Python

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level += 1
            p = p.parent
        return level

    def print_tree(self):
        spaces = ' ' * self.get_level() * 3
        prefix = spaces + "|__" if self.parent else ""
        print(prefix + self.data)
        if self.children:
            for child in self.children:
                child.print_tree()

# Ejemplo de uso
root = TreeNode("Electronics")
laptop = TreeNode("Laptop")
laptop.add_child(TreeNode("Mac"))
laptop.add_child(TreeNode("Surface"))
laptop.add_child(TreeNode("Thinkpad"))

root.add_child(laptop)
root.print_tree()

Explicación

  • TreeNode: Clase que representa un nodo en el árbol.
  • add_child: Método para agregar un nodo hijo.
  • get_level: Método para obtener el nivel del nodo en el árbol.
  • print_tree: Método para imprimir el árbol.

Ejercicio

Implementa un método find en la clase TreeNode que busque un nodo por su valor y devuelva el nodo si se encuentra.

def find(self, data):
    if self.data == data:
        return self
    for child in self.children:
        result = child.find(data)
        if result:
            return result
    return None

  1. Grafos

Concepto

Un grafo es una estructura de datos que consiste en un conjunto de nodos (o vértices) y un conjunto de aristas que conectan pares de nodos. Los grafos pueden ser dirigidos o no dirigidos.

Implementación en Python

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)  # Para grafos no dirigidos

    def print_graph(self):
        for vertex in self.graph:
            print(f"{vertex} -> {', '.join(self.graph[vertex])}")

# Ejemplo de uso
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_edge("A", "B")
g.add_edge("A", "C")
g.print_graph()

Explicación

  • Graph: Clase que representa un grafo.
  • add_vertex: Método para agregar un vértice al grafo.
  • add_edge: Método para agregar una arista entre dos vértices.
  • print_graph: Método para imprimir el grafo.

Ejercicio

Implementa un método find_path en la clase Graph que encuentre un camino entre dos vértices utilizando búsqueda en profundidad (DFS).

def find_path(self, start_vertex, end_vertex, path=[]):
    path = path + [start_vertex]
    if start_vertex == end_vertex:
        return path
    if start_vertex not in self.graph:
        return None
    for vertex in self.graph[start_vertex]:
        if vertex not in path:
            extended_path = self.find_path(vertex, end_vertex, path)
            if extended_path:
                return extended_path
    return None

Conclusión

En esta sección, hemos cubierto varias estructuras de datos avanzadas, incluyendo listas enlazadas, pilas, colas, árboles y grafos. Estas estructuras son fundamentales para resolver problemas complejos de manera eficiente. Asegúrate de practicar implementando y utilizando estas estructuras para fortalecer tu comprensión y habilidades en programación.

◄ Anterior
◄
Siguiente ►
►

Curso de Programación en Python

Módulo 1: Introducción a Python

Módulo 2: Estructuras de Control

Módulo 3: Funciones y Módulos

Módulo 4: Estructuras de Datos

Módulo 5: Programación Orientada a Objetos

Módulo 6: Manejo de Archivos

Módulo 7: Manejo de Errores y Excepciones

Módulo 8: Temas Avanzados

Módulo 9: Pruebas y Depuración

Módulo 10: Desarrollo Web con Python

Módulo 11: Ciencia de Datos con Python

Módulo 12: Proyecto Final

El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados