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

Exercicis amb Llistes

Següent ►
►

En aquesta secció, posarem en pràctica els conceptes apresos sobre les llistes. Els exercicis estan dissenyats per reforçar la comprensió de les llistes enllaçades, les llistes dobles enllaçades i les llistes circulars. Cada exercici inclou una descripció del problema, un exemple de codi i una solució detallada.

Exercici 1: Implementació d'una Llista Enllaçada

Descripció

Implementa una llista enllaçada simple en Python. La llista ha de permetre les operacions bàsiques següents:

  • Inserir un element al final de la llista.
  • Eliminar un element de la llista.
  • Cercar un element a la llista.
  • Imprimir tots els elements de la llista.

Exemple de Codi

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

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

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next

    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None

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

# Exemple d'ús
llista = LinkedList()
llista.insert(1)
llista.insert(2)
llista.insert(3)
llista.print_list()  # Output: 1 -> 2 -> 3 -> None
print(llista.search(2))  # Output: True
llista.delete(2)
llista.print_list()  # Output: 1 -> 3 -> None

Solució Detallada

  1. Node Class: La classe Node representa un node de la llista enllaçada. Cada node conté dades (data) i un punter al següent node (next).
  2. LinkedList Class: La classe LinkedList gestiona les operacions de la llista enllaçada.
    • insert: Afegeix un nou node al final de la llista.
    • delete: Elimina el primer node que conté el valor especificat.
    • search: Cerca un node amb el valor especificat.
    • print_list: Imprimeix tots els elements de la llista.

Exercici 2: Implementació d'una Llista Doblement Enllaçada

Descripció

Implementa una llista dobles enllaçada en Python. La llista ha de permetre les operacions bàsiques següents:

  • Inserir un element al final de la llista.
  • Eliminar un element de la llista.
  • Cercar un element a la llista.
  • Imprimir tots els elements de la llista.

Exemple de Codi

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

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

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def delete(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        if current is None:
            return
        if current.prev is None:
            self.head = current.next
        else:
            current.prev.next = current.next
        if current.next:
            current.next.prev = current.prev

    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None

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

# Exemple d'ús
llista = DoublyLinkedList()
llista.insert(1)
llista.insert(2)
llista.insert(3)
llista.print_list()  # Output: 1 <-> 2 <-> 3 <-> None
print(llista.search(2))  # Output: True
llista.delete(2)
llista.print_list()  # Output: 1 <-> 3 <-> None

Solució Detallada

  1. Node Class: La classe Node representa un node de la llista dobles enllaçada. Cada node conté dades (data), un punter al següent node (next) i un punter al node anterior (prev).
  2. DoublyLinkedList Class: La classe DoublyLinkedList gestiona les operacions de la llista dobles enllaçada.
    • insert: Afegeix un nou node al final de la llista.
    • delete: Elimina el primer node que conté el valor especificat.
    • search: Cerca un node amb el valor especificat.
    • print_list: Imprimeix tots els elements de la llista.

Exercici 3: Implementació d'una Llista Circular

Descripció

Implementa una llista circular enllaçada en Python. La llista ha de permetre les operacions bàsiques següents:

  • Inserir un element al final de la llista.
  • Eliminar un element de la llista.
  • Cercar un element a la llista.
  • Imprimir tots els elements de la llista.

Exemple de Codi

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

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

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def delete(self, key):
        if self.head is None:
            return
        if self.head.data == key:
            if self.head.next == self.head:
                self.head = None
            else:
                current = self.head
                while current.next != self.head:
                    current = current.next
                current.next = self.head.next
                self.head = self.head.next
            return
        current = self.head
        previous = None
        while current.next != self.head and current.data != key:
            previous = current
            current = current.next
        if current.data == key:
            previous.next = current.next

    def search(self, key):
        if self.head is None:
            return False
        current = self.head
        while True:
            if current.data == key:
                return True
            current = current.next
            if current == self.head:
                break
        return False

    def print_list(self):
        if self.head is None:
            print("None")
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("HEAD")

# Exemple d'ús
llista = CircularLinkedList()
llista.insert(1)
llista.insert(2)
llista.insert(3)
llista.print_list()  # Output: 1 -> 2 -> 3 -> HEAD
print(llista.search(2))  # Output: True
llista.delete(2)
llista.print_list()  # Output: 1 -> 3 -> HEAD

Solució Detallada

  1. Node Class: La classe Node representa un node de la llista circular enllaçada. Cada node conté dades (data) i un punter al següent node (next).
  2. CircularLinkedList Class: La classe CircularLinkedList gestiona les operacions de la llista circular enllaçada.
    • insert: Afegeix un nou node al final de la llista.
    • delete: Elimina el primer node que conté el valor especificat.
    • search: Cerca un node amb el valor especificat.
    • print_list: Imprimeix tots els elements de la llista.

Resum

En aquesta secció, hem treballat amb diferents tipus de llistes: llistes enllaçades, llistes dobles enllaçades i llistes circulars. Hem implementat operacions bàsiques com la inserció, l'eliminació, la cerca i la impressió d'elements. Aquests exercicis són fonamentals per entendre com funcionen les estructures de dades bàsiques i com es poden manipular en programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats