Termini e definizioni principali

3.1 Operazioni sui dati: inserimento, eliminazione, ricerca

Inserimento (Insert):

Operazione di aggiunta di un nuovo elemento in una struttura dati. L'inserimento può avvenire all'inizio, alla fine o in una posizione arbitraria della struttura dati.

Eliminazione (Delete):

Operazione di rimozione di un elemento da una struttura dati. L'eliminazione può avvenire in base al valore dell'elemento, all'indice o alla posizione dell'elemento nella struttura dati.

Ricerca (Search):

Operazione di individuazione di un elemento in una struttura dati. La ricerca può avvenire in base al valore o ad altri criteri.

Esempi di operazioni:

• Array: L'inserimento e l'eliminazione richiedono uno spostamento degli elementi, il che può essere costoso in termini di tempo — O(n).
• Liste concatenate: L'inserimento e l'eliminazione possono avvenire in O(1) se la posizione del nodo è conosciuta.
• Hash Table: Ricerca, inserimento ed eliminazione di solito avvengono in O(1) nel caso medio.
• Alberi: Le operazioni di ricerca, inserimento ed eliminazione possono essere eseguite in O(log n) in alberi bilanciati.

3.2 Concetti di base: array, lista, stack, coda

Array

Array — una sequenza di elementi di un unico tipo, accessibili tramite indice.

Complessità delle operazioni: Accesso tramite indice — O(1), inserimento ed eliminazione — O(n).

Esempio: Creazione di un array, modifica di un elemento e stampa del risultato

# Creiamo un array di numeri
arr = [1, 2, 3, 4, 5]

# Modifichiamo l'elemento con indice 2 (terzo elemento, poiché l'indicizzazione inizia da 0)
arr[2] = 10

# Stampiamo l'array modificato
print(arr)  # Output: [1, 2, 10, 4, 5]

# Aggiungiamo un nuovo elemento alla fine dell'array
arr.append(6)
print(arr)  # Output: [1, 2, 10, 4, 5, 6]

# Rimuoviamo l'elemento per indice
del arr[1]
print(arr)  # Output: [1, 10, 4, 5, 6]

Lista

Lista — una collezione di elementi dove ogni elemento contiene un riferimento al successivo (lista semplicemente concatenata) o al successivo e al precedente (lista doppiamente concatenata) elemento.

Complessità delle operazioni: Inserimento ed eliminazione — O(1) se la posizione è conosciuta, ricerca — O(n).

Esempio: Creazione di una semplice lista concatenata e sua iterazione

# Definiamo la struttura del nodo di una lista
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Creiamo una lista semplicemente concatenata
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Colleghiamo i nodi
node1.next = node2
node2.next = node3

# Impostiamo l'inizio della lista
list_head = node1

# Attraversiamo la lista e stampiamo i dati
current = list_head
while current:
    print(current.data)
    current = current.next

# Output:
# 101
# 102
# 103

Stack

Stack — una collezione di elementi secondo il principio LIFO (Last In, First Out): l'ultimo aggiunto è il primo ad uscire.

Complessità delle operazioni: Inserimento (push) ed eliminazione (pop) — O(1).

Esempio: Implementazione e utilizzo di uno stack per verificare l'equilibrio delle parentesi

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Verifichiamo varie espressioni
print(is_balanced("({[]})"))  # Output: True
print(is_balanced("([)]"))    # Output: False
print(is_balanced("(("))      # Output: False

Coda (Queue)

Coda — una collezione di elementi secondo il principio FIFO (First In, First Out): il primo aggiunto è il primo ad uscire.

Complessità delle operazioni: Inserimento (enqueue) ed eliminazione (dequeue) — O(1).

Esempio: Implementazione e utilizzo di una coda per simulare l'elaborazione di compiti

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Compito '{task}' aggiunto alla coda")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Processamento compito: '{task}'")
        else:
            print("La coda è vuota")

    def display_queue(self):
        print("Coda compiti attuale:", list(self.queue))

# Creiamo e utilizziamo una coda di compiti
task_queue = TaskQueue()

task_queue.add_task("Inviare email")
task_queue.add_task("Aggiornare database")
task_queue.add_task("Creare report")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Output:
# Compito 'Inviare email' aggiunto alla coda
# Compito 'Aggiornare database' aggiunto alla coda
# Compito 'Creare report' aggiunto alla coda
# Coda compiti attuale: ['Inviare email', 'Aggiornare database', 'Creare report']
# Processamento compito: 'Inviare email'
# Processamento compito: 'Aggiornare database'
# Coda compiti attuale: ['Creare report']

3.3 Differenze tra vari tipi di strutture dati

Ecco le differenze chiave tra diversi tipi di strutture dati:

Array:

• Accesso: Accesso rapido tramite indice — O(1).
• Modifica della dimensione: Dimensione fissa, l'aumento richiede la copia di tutti gli elementi — O(n).
• Adatto per: Accesso casuale agli elementi quando la dimensione dei dati è nota in anticipo.

Liste concatenate:

• Accesso: Accesso lento tramite indice — O(n).
• Modifica della dimensione: Dimensione facilmente modificabile, inserimento e eliminazione richiedono O(1).
• Adatto per: Aggiunta e rimozione frequente di elementi.

Stack:

• Principio di funzionamento: LIFO.
• Operazioni: Inserimento ed eliminazione solo ad un'estremità — O(1).
• Adatto per: Gestione delle attività in ordine inverso, gestione delle chiamate a funzioni.

Coda:

• Principio di funzionamento: FIFO.
• Operazioni: Inserimento ed eliminazione alle estremità opposte — O(1).
• Adatto per: Gestione delle attività nell'ordine di arrivo.

3.4 Applicazione di diverse strutture dati

Esempi di applicazione di diverse strutture dati nella pratica:

Array

Archiviazione di dati di lunghezza fissa, come i giorni della settimana o i mesi dell'anno.

Esempio: Uso di un array per lavorare con i giorni della settimana

# Creiamo un array con i giorni della settimana
days = ["Lunedì", "Martedì", "Mercoledì", "Giovedì", "Venerdì", "Sabato", "Domenica"]

# Otteniamo il giorno della settimana tramite indice (ad esempio, il terzo giorno)
print(days[2])  # Output: Mercoledì

# Modifichiamo il nome del giorno
days[0] = "Lunedì (inizio settimana)"
print(days[0])  # Output: Lunedì (inizio settimana)

# Iteriamo su tutti i giorni della settimana
for day in days:
    print(day)

# Output:
# Lunedì (inizio settimana)
# Martedì
# Mercoledì
# Giovedì
# Venerdì
# Sabato
# Domenica

Liste concatenate

Implementazione di collezioni dinamiche in cui gli elementi possono essere aggiunti e rimossi al centro della collezione.

Esempio: Implementazione e utilizzo di una lista concatenata per archiviare una lista di cose da fare

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

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

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("Lista di cose da fare vuota")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Creiamo e utilizziamo una lista di cose da fare
todo = TodoList()
todo.add_task("Comprare la spesa")
todo.add_task("Chiamare la mamma")
todo.add_task("Preparare la presentazione")

print("La mia lista di cose da fare:")
todo.display_tasks()

# Output:
# La mia lista di cose da fare:
# - Comprare la spesa
# - Chiamare la mamma
# - Preparare la presentazione

Stack

Ordine inverso di esecuzione delle attività, ad esempio, gestione delle chiamate a funzioni nella ricorsione, annullamento delle operazioni (undo).

Esempio: Uso di uno stack per invertire una stringa

def reverse_string(s):
    stack = []
    # Mettiamo ogni carattere della stringa nello stack
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Estrarre i caratteri dallo stack formando la stringa inversa
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Esempio di utilizzo
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Stringa originale: {original}")
print(f"Stringa invertita: {reversed_str}")

# Output:
# Stringa originale: Hello, World!
# Stringa invertita: !dlroW ,olleH

Coda

Gestione delle attività nell'ordine di arrivo, ad esempio, lavori su una stampante, code nel servizio clienti.

Esempio: Simulazione di una coda di stampa documenti

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Documento '{document}' aggiunto alla coda di stampa")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Stampa del documento: '{document}'")
        else:
            print("La coda di stampa è vuota")

    def display_queue(self):
        print("Coda di stampa attuale:", list(self.queue))

# Creiamo e utilizziamo una coda di stampa
printer = PrinterQueue()
printer.add_document("Report")
printer.add_document("Presentazione")
printer.add_document("Contratto")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Output:
# Documento 'Report' aggiunto alla coda di stampa
# Documento 'Presentazione' aggiunto alla coda di stampa
# Documento 'Contratto' aggiunto alla coda di stampa
# Coda di stampa attuale: ['Report', 'Presentazione', 'Contratto']
# Stampa del documento: 'Report'
# Stampa del documento: 'Presentazione'
# Coda di stampa attuale: ['Contratto']

In questo esempio abbiamo creato una semplice simulazione di una coda di stampa. I documenti vengono aggiunti alla fine della coda e stampati nell'ordine in cui sono stati inseriti, dimostrando il principio FIFO (First In, First Out).