El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Estructures de Dades Avançades

Següent ►
►

En aquest tema, explorarem algunes estructures de dades avançades que són útils per a la resolució de problemes complexos i l'optimització del rendiment en Python. Aquestes estructures de dades inclouen piles, cues, deques, heaps i grafos. Aprendrem com utilitzar-les, les seves aplicacions i implementacions pràctiques.

Continguts

  1. Piles (Stacks)
  2. Cues (Queues)
  3. Deques (Double-ended Queues)
  4. Heaps
  5. Grafos (Graphs)

Piles (Stacks)

Què és una Pila?

Una pila és una estructura de dades que segueix el principi LIFO (Last In, First Out), és a dir, l'últim element que s'afegeix és el primer que es treu.

Operacions Bàsiques

  • push(x): Afegeix l'element x a la pila.
  • pop(): Treu i retorna l'element del cim de la pila.
  • peek(): Retorna l'element del cim sense treure'l.
  • is_empty(): Retorna True si la pila està buida, False en cas contrari.

Implementació en Python

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from empty stack")

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

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

# Exemple d'ús
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # Sortida: 2
print(stack.peek())  # Sortida: 1

Cues (Queues)

Què és una Cua?

Una cua és una estructura de dades que segueix el principi FIFO (First In, First Out), és a dir, el primer element que s'afegeix és el primer que es treu.

Operacions Bàsiques

  • enqueue(x): Afegeix l'element x a la cua.
  • dequeue(): Treu i retorna l'element del front de la cua.
  • front(): Retorna l'element del front sense treure'l.
  • is_empty(): Retorna True si la cua està buida, False en cas contrari.

Implementació en Python

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

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("dequeue from empty queue")

    def front(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("front from empty queue")

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

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

# Exemple d'ús
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue())  # Sortida: 1
print(queue.front())  # Sortida: 2

Deques (Double-ended Queues)

Què és una Deque?

Una deque (Double-ended Queue) és una estructura de dades que permet l'addició i eliminació d'elements tant pel front com pel final.

Operacions Bàsiques

  • append(x): Afegeix l'element x al final de la deque.
  • appendleft(x): Afegeix l'element x al front de la deque.
  • pop(): Treu i retorna l'element del final de la deque.
  • popleft(): Treu i retorna l'element del front de la deque.
  • is_empty(): Retorna True si la deque està buida, False en cas contrari.

Implementació en Python

from collections import deque

# Creació d'una deque
d = deque()

# Afegeix elements
d.append(1)
d.appendleft(2)

# Treu elements
print(d.pop())  # Sortida: 1
print(d.popleft())  # Sortida: 2

Heaps

Què és un Heap?

Un heap és una estructura de dades especialitzada que satisfà la propietat de heap. En un min-heap, el valor del node pare és sempre menor o igual que els valors dels seus fills. En un max-heap, el valor del node pare és sempre major o igual que els valors dels seus fills.

Operacions Bàsiques

  • heappush(heap, x): Afegeix l'element x al heap.
  • heappop(heap): Treu i retorna l'element més petit del heap.
  • heapify(x): Converteix la llista x en un heap.

Implementació en Python

import heapq

# Creació d'un min-heap
heap = []

# Afegeix elements
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# Treu l'element més petit
print(heapq.heappop(heap))  # Sortida: 1

Grafos (Graphs)

Què és un Grafo?

Un grafo és una estructura de dades que consisteix en un conjunt de nodes (o vèrtexs) i un conjunt d'arestes que connecten parells de nodes.

Representació d'un Grafo

Els grafos es poden representar de diverses maneres, incloent llistes d'adjacència i matrius d'adjacència.

Implementació en Python

Llista d'Adjacència

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

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def get_neighbors(self, u):
        return self.graph.get(u, [])

# Exemple d'ús
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
print(g.get_neighbors(1))  # Sortida: [2, 3]

Matriu d'Adjacència

import numpy as np

class GraphMatrix:
    def __init__(self, num_nodes):
        self.matrix = np.zeros((num_nodes, num_nodes))

    def add_edge(self, u, v):
        self.matrix[u][v] = 1

    def get_neighbors(self, u):
        return np.where(self.matrix[u] == 1)[0]

# Exemple d'ús
gm = GraphMatrix(5)
gm.add_edge(1, 2)
gm.add_edge(1, 3)
gm.add_edge(2, 4)
print(gm.get_neighbors(1))  # Sortida: [2 3]

Exercicis Pràctics

Exercici 1: Implementació d'una Pila

Implementa una pila utilitzant una llista en Python i prova les operacions bàsiques.

Exercici 2: Implementació d'una Cua

Implementa una cua utilitzant una llista en Python i prova les operacions bàsiques.

Exercici 3: Utilització de Deques

Utilitza la classe deque de la biblioteca collections per implementar una cua de doble extrem i prova les operacions bàsiques.

Exercici 4: Treballant amb Heaps

Utilitza la biblioteca heapq per crear un min-heap i realitza operacions d'inserció i eliminació.

Exercici 5: Representació de Grafos

Implementa un grafo utilitzant una llista d'adjacència i una matriu d'adjacència. Afegeix algunes arestes i mostra els veïns d'un node donat.

Resum

En aquesta secció, hem explorat diverses estructures de dades avançades com piles, cues, deques, heaps i grafos. Hem après les seves operacions bàsiques i com implementar-les en Python. Aquestes estructures de dades són fonamentals per a la resolució de problemes complexos i l'optimització del rendiment en aplicacions reals.

◄ Anterior
◄
Següent ►
►

Curs de Programació en Python

Mòdul 1: Introducció a Python

Mòdul 2: Estructures de Control

Mòdul 3: Funcions i Mòduls

Mòdul 4: Estructures de Dades

Mòdul 5: Programació Orientada a Objectes

Mòdul 6: Gestió de Fitxers

Mòdul 7: Gestió d'Errors i Excepcions

Mòdul 8: Temes Avançats

Mòdul 9: Proves i Depuració

Mòdul 10: Desenvolupament Web amb Python

Mòdul 11: Ciència de Dades amb Python

Mòdul 12: Projecte Final

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats