4-Strutture Dati: Gli algoritmi spesso operano su strutture dati come array, liste, code, pile, alberi, grafi e tabelle hash per organizzare e gestire i dati in modi specifici.
4.1-Array e liste
Le strutture dati sono elementi essenziali in programmazione e rappresentano modi per organizzare e memorizzare dati. Due delle strutture dati più comuni sono gli array e le liste:
Liste: Le liste sono strutture dati dinamiche che possono contenere elementi di diversi tipi. Le liste sono più flessibili rispetto agli array statici, poiché possono espandersi o contrarsi dinamicamente mentre vengono utilizzate.
Le liste sono una struttura dati versatile e flessibile che può contenere una sequenza di elementi di diversi tipi. In molti linguaggi di programmazione, le liste sono strutture dati dinamiche che possono crescere o diminuire di dimensione durante l'esecuzione del programma. In Python, ad esempio, le liste sono definite utilizzando parentesi quadre [].
Esempio di liste in Python:
python
Copy code
# Creazione di una lista in Python
lista = [1, 2, 3, 4, 5]
Principali caratteristiche delle liste:
Le liste possono contenere elementi di diversi tipi (numeri, stringhe, booleani, liste nidificate, ecc.).
Le liste possono essere modificate (aggiunta, rimozione, modifica di elementi).
Gli elementi di una lista sono indicizzati, cioè possono essere accessibili tramite il loro indice (indice inizia da 0).
Ecco un esempio di algoritmo che opera su una struttura dati lista (linked list). In questo caso, l'algoritmo inserisce un elemento in testa alla lista:
Input: Una lista collegata lista, un valore elemento da inserire
Output: La lista aggiornata con l'inserimento di elemento in testa
Inizializza un nuovo nodo nodo con il valore elemento
Se lista è vuota allora
Assegna nodo come il primo nodo di lista
Altrimenti
Collega il nuovo nodo nodo al primo nodo esistente in lista
Assegna nodo come il nuovo primo nodo di lista
Fine
In questo esempio:
L'algoritmo riceve una lista collegata e un valore elemento da inserire all'inizio della lista.
Inizializza un nuovo nodo nodo con il valore elemento.
Se la lista è vuota, assegna il nuovo nodo nodo come il primo nodo della lista. In caso contrario, collega il nuovo nodo nodo al primo nodo esistente in lista, rendendolo il nuovo primo nodo della lista.
Questo esempio rappresenta un'operazione di inserimento in testa a una lista collegata. È importante notare che le liste collegate sono strutture dati dinamiche e flessibili, il che significa che possono essere facilmente modificate per aggiungere o rimuovere elementi.
Ecco un esempio di come funzionerebbe l'algoritmo:
Esecuzione:
Input: lista è inizialmente vuota, elemento = 5
Calcolo: Un nuovo nodo con valore 5 viene creato e assegnato come il primo nodo di lista
Output: lista ora contiene il nodo con valore 5
L'algoritmo ha inserito con successo il valore 5 in testa alla lista collegata.
Array: Un array è una struttura dati che può contenere un insieme di elementi dello stesso tipo. Gli elementi sono indicizzati da numeri interi, consentendo un accesso rapido e diretto agli elementi. Gli array possono avere dimensioni fisse (array statici) o dimensioni dinamiche (array dinamici o liste).
Gli array sono una struttura dati simile alle liste in quanto possono contenere una sequenza di elementi. Tuttavia, negli array, tutti gli elementi devono essere dello stesso tipo di dato e l'array ha una dimensione fissa una volta creato. In molti linguaggi di programmazione, gli array richiedono una dimensione specifica al momento della dichiarazione.
Esempio di array in alcuni linguaggi (come C, Java):
java
Copy code
// Creazione di un array in Java
int[] array = new int[5]; // Array di interi con dimensione 5
Principali caratteristiche degli array:
Gli array hanno dimensione fissa dopo la loro creazione.
Gli elementi di un array sono accessibili tramite indice.
Gli elementi di un array devono essere dello stesso tipo di dato.
Ecco un esempio di algoritmo che utilizza un array come struttura dati per memorizzare una lista di numeri e calcolare la loro somma:
Input: Un array di numeri interi numeri
Output: La somma dei numeri nell'array, somma
Leggi la dimensione dell'array n dallo standard input
Inizializza un array vuoto numeri
Per i da 1 a n fai
Leggi un numero intero num dallo standard input
Aggiungi num all'array numeri
Inizializza la variabile somma a zero
Per i da 1 a n fai
Aggiungi il valore di numeri[i] a somma
Stampa somma sullo standard output
Fine
In questo esempio:
L'algoritmo legge la dimensione dell'array n e successivamente legge n numeri interi dall'input, memorizzandoli nell'array numeri.
Utilizza un ciclo "for" per attraversare l'array e calcolare la somma dei numeri memorizzati nella variabile somma.
Alla fine, stampa il valore di somma sull'output.
Ad esempio, se forniamo la dimensione n = 5 e i numeri 3, 7, 2, 8, e 5 come input:
Esecuzione:
Input: n = 5, numeri = [3, 7, 2, 8, 5]
Calcolo: somma = 3 + 7 + 2 + 8 + 5 = 25
Output: 25
Questo esempio dimostra come un array possa essere utilizzato come struttura dati per memorizzare e manipolare una lista di dati in un algoritmo.
Differenze chiave:
Le liste (come in Python) possono contenere elementi di diversi tipi e la loro dimensione può variare dinamicamente.
Gli array (in molti linguaggi come C, Java) hanno una dimensione fissa e tutti gli elementi devono essere dello stesso tipo di dato.
In alcuni linguaggi di programmazione, il termine "array" può essere usato in modo più generale per riferirsi a strutture dati che possono essere sia dinamiche che a dimensione fissa. Tuttavia, è importante considerare le differenze specifiche tra liste e array in base al linguaggio di programmazione che si sta utilizzando, poiché le implementazioni e le caratteristiche possono variare considerevolmente da un linguaggio all'altro.
Altri esempi
Ecco un esempio in Python che mostra la creazione di un array e una lista:
python
Copy code
# Array in Python
array = [1, 2, 3, 4, 5]
# Lista in Python
lista = [1, "due", 3.0, [4, 5]]
Gli array e le liste sono ampiamente utilizzati per memorizzare e gestire collezioni di dati, facilitando l'accesso, la modifica e l'organizzazione degli elementi. La scelta tra array e liste dipende dalle esigenze specifiche del tuo programma.
4.2-Stack e coda.
Lo stack e la coda sono due tipi di strutture dati utilizzate per la gestione di dati in modo particolare.
Stack e coda sono strutture dati fondamentali utilizzate nell'informatica per organizzare e gestire dati in un programma. Entrambi sono tipi di strutture dati che memorizzano una collezione di elementi, ma hanno diverse caratteristiche e regole per l'inserimento e l'estrazione degli elementi.
Stack (pila): Uno stack è una struttura dati basata sul principio LIFO (Last In, First Out). Ciò significa che l'ultimo elemento inserito è il primo a essere rimosso. È simile a un pila di oggetti fisici, in cui puoi aggiungere o rimuovere oggetti solo dalla cima. Gli stack sono spesso utilizzati per gestire chiamate di funzioni, per invertire stringhe o per risolvere problemi ricorsivi.
Uno stack è una struttura dati LIFO (Last-In, First-Out), dove l'ultimo elemento inserito è il primo a essere estratto. Questa struttura dati funziona seguendo il principio "push" (inserimento) e "pop" (rimozione). Gli elementi vengono aggiunti (push) o rimossi (pop) solo dall'estremità superiore dello stack.
Esempio di stack:
yaml
Copy code
Inserimento: 5 -> 3 -> 9
Top
9
---
3
---
5
Bottom
Principali operazioni su uno stack:
push(item): Aggiunge un elemento in cima allo stack.
Ecco un esempio di una funzione push(item) che aggiunge un elemento in cima allo stack in Python utilizzando una lista come struttura dati per rappresentare lo stack:
python
Copy code
class Stack:
def __init__(self):
self.items = [] # Inizializzazione dello stack come una lista vuota
def push(self, item):
self.items.append(item) # Aggiunge l'elemento in cima allo stack
def print_stack(self):
print("Stack attuale:", self.items)
# Creazione di uno stack e utilizzo della funzione push()
stack = Stack()
stack.push(5) # Aggiunge 5 in cima allo stack
stack.print_stack() # Stampa: Stack attuale: [5]
stack.push(10) # Aggiunge 10 in cima allo stack
stack.print_stack() # Stampa: Stack attuale: [5, 10]
stack.push('ciao') # Aggiunge 'ciao' in cima allo stack
stack.print_stack() # Stampa: Stack attuale: [5, 10, 'ciao']
In questo esempio, la funzione push(item) della classe Stack utilizza il metodo append() della lista in Python per aggiungere l'elemento item in cima allo stack rappresentato dalla lista self.items. Successivamente, la funzione print_stack() viene utilizzata per stampare il contenuto attuale dello stack dopo ogni operazione di push().
pop(): Rimuove e restituisce l'elemento in cima allo stack.
Ecco un esempio di come implementare la funzione pop() che rimuove e restituisce l'elemento in cima allo stack utilizzando una lista come struttura dati per rappresentare lo stack in Python:
python
Copy code
class Stack:
def __init__(self):
self.items = [] # Inizializzazione dello stack come una lista vuota
def push(self, item):
self.items.append(item) # Aggiunge l'elemento in cima allo stack
def pop(self):
if not self.is_empty(): # Verifica se lo stack non è vuoto
return self.items.pop() # Rimuove e restituisce l'elemento in cima allo stack
else:
return "Lo stack è vuoto, impossibile fare pop"
def is_empty(self):
return len(self.items) == 0 # Verifica se lo stack è vuoto
def print_stack(self):
print("Stack attuale:", self.items)
# Creazione di uno stack e utilizzo della funzione pop()
stack = Stack()
stack.push(5)
stack.push(10)
stack.push('ciao')
stack.print_stack() # Stampa: Stack attuale: [5, 10, 'ciao']
popped_item = stack.pop() # Rimuove e restituisce l'elemento in cima allo stack
print("Elemento rimosso:", popped_item) # Stampa: Elemento rimosso: ciao
stack.print_stack() # Stampa: Stack attuale: [5, 10]
In questo esempio, la funzione pop() della classe Stack utilizza il metodo pop() della lista in Python per rimuovere e restituire l'elemento in cima allo stack rappresentato dalla lista self.items. La funzione is_empty() è utilizzata per verificare se lo stack è vuoto prima di eseguire l'operazione pop(), altrimenti restituirà un messaggio indicando che lo stack è vuoto.
top() o peek(): Restituisce l'elemento in cima allo stack senza rimuoverlo.
Ecco un esempio di come implementare la funzione top() (o peek()) che restituisce l'elemento in cima allo stack senza rimuoverlo. Si userà una lista come struttura dati per rappresentare lo stack in Python:
python
Copy code
class Stack:
def __init__(self):
self.items = [] # Inizializzazione dello stack come una lista vuota
def push(self, item):
self.items.append(item) # Aggiunge l'elemento in cima allo stack
def pop(self):
if not self.is_empty(): # Verifica se lo stack non è vuoto
return self.items.pop() # Rimuove e restituisce l'elemento in cima allo stack
else:
return "Lo stack è vuoto, impossibile fare pop"
def top(self):
if not self.is_empty(): # Verifica se lo stack non è vuoto
return self.items[-1] # Restituisce l'elemento in cima allo stack
else:
return "Lo stack è vuoto, impossibile fare top"
def is_empty(self):
return len(self.items) == 0 # Verifica se lo stack è vuoto
def print_stack(self):
print("Stack attuale:", self.items)
# Creazione di uno stack e utilizzo della funzione top() (o peek())
stack = Stack()
stack.push(5)
stack.push(10)
stack.push('ciao')
stack.print_stack() # Stampa: Stack attuale: [5, 10, 'ciao']
top_item = stack.top() # Restituisce l'elemento in cima allo stack
print("Elemento in cima allo stack:", top_item) # Stampa: Elemento in cima allo stack: ciao
stack.print_stack() # Stampa: Stack attuale: [5, 10, 'ciao']
In questo esempio, la funzione top() della classe Stack restituisce l'elemento in cima allo stack rappresentato dalla lista self.items utilizzando l'indice -1 che rappresenta l'ultimo elemento della lista senza rimuoverlo dallo stack. La funzione is_empty() è utilizzata per verificare se lo stack è vuoto prima di restituire l'elemento in cima allo stack, altrimenti restituirà un messaggio indicando che lo stack è vuoto.
isEmpty(): Verifica se lo stack è vuoto.
Ecco un esempio di implementazione della funzione isEmpty() in una classe Stack che verifica se lo stack è vuoto:
python
Copy code
class Stack:
def __init__(self):
self.items = [] # Inizializzazione dello stack come una lista vuota
def push(self, item):
self.items.append(item) # Aggiunge l'elemento in cima allo stack
def pop(self):
if not self.is_empty(): # Verifica se lo stack non è vuoto
return self.items.pop() # Rimuove e restituisce l'elemento in cima allo stack
else:
return "Lo stack è vuoto, impossibile fare pop"
def top(self):
if not self.is_empty(): # Verifica se lo stack non è vuoto
return self.items[-1] # Restituisce l'elemento in cima allo stack
else:
return "Lo stack è vuoto, impossibile fare top"
def is_empty(self):
return len(self.items) == 0 # Verifica se lo stack è vuoto
def print_stack(self):
print("Stack attuale:", self.items)
# Creazione di uno stack e utilizzo della funzione isEmpty()
stack = Stack()
print(stack.is_empty()) # Stampa: True, perché lo stack è vuoto
stack.push(5)
print(stack.is_empty()) # Stampa: False, perché lo stack non è più vuoto dopo l'inserimento di un elemento
In questo esempio, la funzione isEmpty() della classe Stack verifica se lo stack rappresentato dalla lista self.items è vuoto controllando la lunghezza della lista. Restituisce True se lo stack è vuoto (lunghezza zero) e False altrimenti. Sono inclusi esempi di come utilizzare questa funzione per verificare se lo stack è vuoto o meno in diverse fasi dell'esecuzione del codice.
Esempio di Algoritmo con Struttura dati Pila (Stack): Calcolo di una Espressione Postfissa
Input: Una stringa rappresentante un'espressione postfissa (ad esempio, "34+5*").
Output: Il risultato dell'espressione.
Descrizione: Questo algoritmo utilizza una pila per calcolare il risultato di un'espressione matematica in notazione postfissa. Esso analizza i caratteri uno alla volta e, se incontra un operando, lo inserisce nella pila. Se incontra un operatore, estrae gli operandi dalla pila, esegue l'operazione e riinserisce il risultato nella pila.
Ecco un esempio di algoritmo che calcola il risultato di un'espressione postfissa utilizzando una pila:
ALGORITMO CalcoloEspressionePostfissa
Input: Una stringa rappresentante un'espressione postfissa (ad esempio, "34+5*").
Output: Il risultato dell'espressione.
Descrizione: Questo algoritmo utilizza una pila per calcolare il risultato di un'espressione matematica in notazione postfissa.
Inizializza una pila vuota.
Per ogni carattere car nella stringa di input fai
Se car è un operando (ad esempio, un numero) allora
Converti car in un numero e inseriscilo nella pila.
Altrimenti, se car è un operatore (ad esempio, +, -, *, /) allora
Estrai due operandi, op2 e op1, dalla pila.
Esegui l'operazione tra op1 e op2 in base all'operatore car.
Inserisci il risultato nellapila.
Il risultato dell'espressione si trova ora nella pila.
Estrai il risultato dalla pila e restituiscilo come output.
Fine
Esempio di esecuzione con input "34+5*":
Esecuzione:
Input: "34+5*"
Inizializzazione della pila: [ ]
Passaggio 1: Leggiamo "3", è un operando, quindi inseriamo 3 nella pila: [3]
Passaggio 2: Leggiamo "4", è un altro operando, inseriamo 4 nella pila: [3, 4]
Passaggio 3: Leggiamo "+", è un operatore, estraiamo 4 e 3 dalla pila, eseguiamo 3 + 4 e inseriamo 7 nella pila: [7]
Passaggio 4: Leggiamo "5", è un operando, inseriamo 5 nella pila: [7, 5]
Passaggio 5: Leggiamo "*", è un operatore, estraiamo 5 e 7 dalla pila, eseguiamo 7 * 5 e inseriamo 35 nella pila: [35]
Alla fine, il risultato dell'espressione è 35.
Output: 35
Questo algoritmo dimostra come una pila può essere utilizzata per valutare espressioni matematiche in notazione postfissa in modo efficiente. Ogni volta che viene letto un operatore, vengono estratti gli operandi dalla pila, eseguita l'operazione e il risultato viene reinserito nella pila. Alla fine, il risultato finale si trova nella cima della pila.
Coda: Una coda è una struttura dati basata sul principio FIFO (First In, First Out). In una coda, l'elemento inserito per primo è il primo a essere rimosso. Le code sono comunemente utilizzate per gestire operazioni di tipo "prima arrivato, prima servito", come le code nei supermercati o la gestione delle richieste in un server web.
Una coda è una struttura dati FIFO (First-In, First-Out), dove il primo elemento inserito è il primo a essere estratto. Gli elementi vengono aggiunti (enqueue) alla fine della coda e rimossi (dequeue) dall'inizio della coda.
Esempio di coda:
yaml
Copy code
Inserimento: 5 -> 3 -> 9
Front
5
---
3
---
9
Rear
Principali operazioni su una coda:
enqueue(item): Aggiunge un elemento alla fine della coda.
Ecco un esempio di come implementare la funzione enqueue(item) che aggiunge un elemento in coda a una coda (queue) utilizzando una lista come struttura dati per rappresentare la coda in Python:
python
Copy code
class Queue:
def __init__(self):
self.items = [] # Inizializzazione della coda come una lista vuota
def enqueue(self, item):
self.items.append(item) # Aggiunge l'elemento in coda alla coda
def print_queue(self):
print("Coda attuale:", self.items)
# Creazione di una coda e utilizzo della funzione enqueue()
queue = Queue()
queue.enqueue(5) # Aggiunge 5 in coda alla coda
queue.print_queue() # Stampa: Coda attuale: [5]
queue.enqueue(10) # Aggiunge 10 in coda alla coda
queue.print_queue() # Stampa: Coda attuale: [5, 10]
queue.enqueue('ciao') # Aggiunge 'ciao' in coda alla coda
queue.print_queue() # Stampa: Coda attuale: [5, 10, 'ciao']
In questo esempio, la funzione enqueue(item) della classe Queue utilizza il metodo append() della lista in Python per aggiungere l'elemento item in coda alla coda rappresentata dalla lista self.items. La funzione print_queue() è utilizzata per stampare il contenuto attuale della coda dopo ogni operazione di enqueue().
dequeue(): Rimuove e restituisce l'elemento all'inizio della coda.
Ecco un esempio di come implementare la funzione dequeue() che rimuove e restituisce l'elemento in testa a una coda (queue) utilizzando una lista come struttura dati per rappresentare la coda in Python:
python
Copy code
class Queue:
def __init__(self):
self.items = [] # Inizializzazione della coda come una lista vuota
def enqueue(self, item):
self.items.append(item) # Aggiunge l'elemento in coda alla coda
def dequeue(self):
if not self.is_empty(): # Verifica se la coda non è vuota
return self.items.pop(0) # Rimuove e restituisce l'elemento in testa alla coda
else:
return "La coda è vuota, impossibile fare dequeue"
def is_empty(self):
return len(self.items) == 0 # Verifica se la coda è vuota
def print_queue(self):
print("Coda attuale:", self.items)
# Creazione di una coda e utilizzo della funzione dequeue()
queue = Queue()
queue.enqueue(5)
queue.enqueue(10)
queue.enqueue('ciao')
queue.print_queue() # Stampa: Coda attuale: [5, 10, 'ciao']
dequeued_item = queue.dequeue() # Rimuove e restituisce l'elemento in testa alla coda
print("Elemento rimosso:", dequeued_item) # Stampa: Elemento rimosso: 5
queue.print_queue() # Stampa: Coda attuale: [10, 'ciao']
In questo esempio, la funzione dequeue() della classe Queue verifica se la coda rappresentata dalla lista self.items non è vuota, quindi utilizza il metodo pop(0) della lista per rimuovere e restituire l'elemento in testa alla coda. La funzione is_empty() è utilizzata per verificare se la coda è vuota prima di eseguire l'operazione dequeue(), altrimenti restituirà un messaggio indicando che la coda è vuota. La funzione print_queue() viene utilizzata per stampare il contenuto attuale della coda dopo ogni operazione.
Ecco un esempio di algoritmo che opera su una struttura dati coda (queue). In questo caso, l'algoritmo esegue un'operazione di inserimento (enqueue) e un'operazione di estrazione (dequeue) dalla coda:
Input: Una coda coda, un valore elementoDaInserire
Output: La coda aggiornata dopo l'inserimento e l'estrazione
Inserisci elementoDaInserire nella coda (enqueue).
Estrai il primo elemento dalla coda (dequeue).
Fine
In questo esempio:
L'algoritmo riceve una coda coda e un valore elementoDaInserire da inserire nella coda.
Utilizza l'operazione di inserimento (enqueue) per aggiungere elementoDaInserire alla coda.
Quindi, utilizza l'operazione di estrazione (dequeue) per rimuovere il primo elemento dalla coda.
Ecco un esempio di come funzionerebbe l'algoritmo:
Esecuzione:
Input: coda è inizialmente vuota, elementoDaInserire = 10
Calcolo:
Inserisce 10 nella coda.
Estrae il primo elemento dalla coda (che è ora 10).
Output: La coda è vuota.
Questo esempio dimostra come le operazioni di inserimento e estrazione possano essere eseguite su una struttura dati coda. Le code sono spesso utilizzate per gestire dati in modo FIFO (First-In-First-Out), dove il primo elemento inserito è anche il primo a essere estratto.
front() o peek(): Restituisce l'elemento all'inizio della coda senza rimuoverlo.
Ecco un esempio di come implementare la funzione front() (o peek()) che restituisce l'elemento in testa alla coda (queue) senza rimuoverlo, utilizzando una lista come struttura dati per rappresentare la coda in Python:
python
Copy code
class Queue:
def __init__(self):
self.items = [] # Inizializzazione della coda come una lista vuota
def enqueue(self, item):
self.items.append(item) # Aggiunge l'elemento in coda alla coda
def dequeue(self):
if not self.is_empty(): # Verifica se la coda non è vuota
return self.items.pop(0) # Rimuove e restituisce l'elemento in testa alla coda
else:
return "La coda è vuota, impossibile fare dequeue"
def front(self):
if not self.is_empty(): # Verifica se la coda non è vuota
return self.items[0] # Restituisce l'elemento in testa alla coda
else:
return "La coda è vuota, impossibile fare front"
def is_empty(self):
return len(self.items) == 0 # Verifica se la coda è vuota
def print_queue(self):
print("Coda attuale:", self.items)
# Creazione di una coda e utilizzo della funzione front() (o peek())
queue = Queue()
queue.enqueue(5)
queue.enqueue(10)
queue.enqueue('ciao')
queue.print_queue() # Stampa: Coda attuale: [5, 10, 'ciao']
front_item = queue.front() # Restituisce l'elemento in testa alla coda
print("Elemento in testa alla coda:", front_item) # Stampa: Elemento in testa alla coda: 5
queue.print_queue() # Stampa: Coda attuale: [5, 10, 'ciao']
In questo esempio, la funzione front() della classe Queue verifica se la coda rappresentata dalla lista self.items non è vuota e restituisce l'elemento in testa alla coda senza rimuoverlo, utilizzando l'indice 0 per accedere all'elemento. La funzione is_empty() è utilizzata per verificare se la coda è vuota prima di restituire l'elemento in testa, altrimenti restituirà un messaggio indicando che la coda è vuota. La funzione print_queue() viene utilizzata per stampare il contenuto attuale della coda dopo ogni operazione.
isEmpty(): Verifica se la coda è vuota.
Ecco un esempio di come implementare la funzione isEmpty() in una classe Queue che verifica se la coda è vuota:
python
Copy code
class Queue:
def __init__(self):
self.items = [] # Inizializzazione della coda come una lista vuota
def enqueue(self, item):
self.items.append(item) # Aggiunge l'elemento in coda alla coda
def dequeue(self):
if not self.is_empty(): # Verifica se la coda non è vuota
return self.items.pop(0) # Rimuove e restituisce l'elemento in testa alla coda
else:
return "La coda è vuota, impossibile fare dequeue"
def front(self):
if not self.is_empty(): # Verifica se la coda non è vuota
return self.items[0] # Restituisce l'elemento in testa alla coda
else:
return "La coda è vuota, impossibile fare front"
def is_empty(self):
return len(self.items) == 0 # Verifica se la coda è vuota
def print_queue(self):
print("Coda attuale:", self.items)
# Creazione di una coda e utilizzo della funzione isEmpty()
queue = Queue()
print(queue.is_empty()) # Stampa: True, perché la coda è vuota
queue.enqueue(5)
print(queue.is_empty()) # Stampa: False, perché la coda non è più vuota dopo l'inserimento di un elemento
Nell'esempio sopra, la funzione isEmpty() della classe Queue verifica se la coda rappresentata dalla lista self.items è vuota controllando la lunghezza della lista. Restituisce True se la coda è vuota (lunghezza zero) e False altrimenti. Sono inclusi esempi di come utilizzare questa funzione per verificare se la coda è vuota o meno in diverse fasi dell'esecuzione del codice.
Differenze chiave:
Stack: Segue il principio LIFO (Last-In, First-Out), l'ultimo elemento inserito è il primo a essere estratto.
Coda: Segue il principio FIFO (First-In, First-Out), il primo elemento inserito è il primo a essere estratto.
Entrambi gli stack e le code sono utilizzati per la gestione di dati in diversi contesti. Ad esempio, gli stack possono essere utilizzati per la gestione delle chiamate di funzioni (stack di chiamate), l'undo/redo in editor di testo, l'implementazione di algoritmi come DFS (Depth-First Search). Le code sono spesso utilizzate per gestire i processi in attesa (ad es. in un sistema di gestione di processi) o nella gestione delle richieste in un sistema di rete.
4.3-Alberi e Grafi
Gli alberi e i grafi sono strutture dati complesse utilizzate per rappresentare relazioni e gerarchie tra dati:
Alberi: Un albero è una struttura dati gerarchica composta da nodi collegati tra loro. Ogni albero ha un nodo radice, da cui si diramano i sottoalberi. Gli alberi sono utilizzati per rappresentare strutture ad albero come le directory del file system, le gerarchie di organizzazioni o le strutturazioni dei dati in database.
Un albero è una struttura dati gerarchica che consiste in nodi collegati in modo gerarchico. È costituito da un insieme di nodi, in cui uno di essi è designato come "radice", e ogni altro nodo è collegato a essa attraverso un percorso univoco. Ogni nodo può avere zero o più nodi figlio, ma può avere solo un nodo genitore (ad eccezione della radice che non ha genitore).
Esempio di struttura di un albero:
mathematica
Copy code
A
/ \
B C
/ \ / \
D E F G
Principali termini associati agli alberi:
Radice: Il nodo principale dell'albero, dal quale tutti gli altri nodi si dipartono.
Un esempio comune di radice è nel contesto degli alberi binari.
Supponiamo di avere una struttura di dati per un albero binario in cui ogni nodo può avere al massimo due figli: un nodo padre (o radice) e due nodi figli, uno a sinistra e uno a destra.
Ecco un esempio di implementazione di un nodo per un albero binario in un linguaggio come Python:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
In questo esempio, la classe NodoAlbero rappresenta un nodo dell'albero binario. La proprietà valore contiene il valore del nodo, mentre sinistro e destro sono puntatori ai nodi figli sinistro e destro rispettivamente.
La radice dell'albero sarebbe il nodo principale dal quale tutti gli altri nodi si dipartono. Ad esempio, se vogliamo creare un albero binario con una radice il cui valore è 10 e aggiungere alcuni nodi figli, possiamo farlo in questo modo:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
# Aggiunta di ulteriori nodi figli per il nodo a sinistra
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
Nell'esempio sopra, il nodo con valore 10 è la radice dell'albero. Tutti gli altri nodi, come quelli con valori 5, 15, 3, e 7, si dipartono da questa radice tramite i puntatori ai nodi figli sinistro e destro. La radice è il punto di partenza e il nodo principale dell'albero, dal quale la struttura dell'albero si sviluppa.
Nodo: Elemento individuale dell'albero che può contenere un valore e puntatori ai nodi figlio.
Un esempio di un nodo in un albero potrebbe essere rappresentato in Python come segue:
Supponiamo di avere una struttura di dati per un albero binario simile a quanto descritto nell'esempio precedente. Qui di seguito è mostrata un'implementazione semplificata di un nodo per un albero binario:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
In questo esempio, la classe NodoAlbero rappresenta un nodo dell'albero binario. Ogni nodo contiene una variabile valore che può contenere qualsiasi valore desiderato e due puntatori, sinistro e destro, che puntano ai nodi figli sinistro e destro rispettivamente.
Per esempio, possiamo creare un nodo e aggiungere dei nodi figli in questo modo:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
Nell'esempio sopra, radice rappresenta la radice dell'albero e contiene un nodo con valore 10. Successivamente, vengono aggiunti due nodi figli: uno con valore 5 e l'altro con valore 15. Ogni nodo può a sua volta contenere valori e puntatori ai suoi nodi figli, formando così una struttura ad albero. Ogni singolo nodo in questo scenario rappresenta un elemento individuale dell'albero e può contenere un valore insieme a puntatori ai nodi figlio.
Foglia: Nodo senza figli.
Una foglia in un albero è un nodo che non ha nodi figlio. Nella rappresentazione di un albero binario, una foglia è un nodo terminale che non ha alcun nodo figlio. Ecco un esempio in Python:
Supponiamo di avere la stessa struttura di nodo per un albero binario:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
Ora creiamo un esempio di un albero binario che contiene delle foglie:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
# Aggiunta di foglie
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
radice.destro.sinistro = NodoAlbero(12)
radice.destro.destro = NodoAlbero(20)
Nell'esempio sopra, radice rappresenta la radice dell'albero e contiene un nodo con valore 10. Successivamente, vengono aggiunti nodi figli e foglie. Le foglie sono i nodi terminali dell'albero che non hanno ulteriori nodi figlio. Ad esempio, i nodi con valori 3, 7, 12 e 20 sono foglie perché non hanno alcun nodo figlio associato (sinistro e destro sono entrambi impostati a None).
Le foglie in un albero sono nodi senza alcun nodo figlio e rappresentano gli estremi delle ramificazioni dell'albero.
Percorso: Una sequenza di nodi connessi da archi.
Un percorso in un albero è una sequenza di nodi che sono connessi da archi seguendo un percorso specifico all'interno della struttura ad albero. Ogni nodo nel percorso è collegato al successivo tramite un arco o un collegamento.
Prendiamo ad esempio l'albero binario che abbiamo creato precedentemente:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
e l'albero binario stesso:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
# Aggiunta di foglie
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
radice.destro.sinistro = NodoAlbero(12)
radice.destro.destro = NodoAlbero(20)
Ora, supponiamo di voler trovare un percorso specifico all'interno di questo albero, ad esempio, dal nodo radice 10 a una foglia, diciamo il nodo con valore 7.
Un percorso da 10 a 7 potrebbe essere rappresentato come una lista di valori dei nodi che vengono attraversati:
python
Copy code
percorso_da_10_a_7 = [10, 5, 7]
Questo percorso rappresenta la sequenza di nodi che devono essere attraversati partendo dal nodo radice 10, passando per il nodo 5, e arrivando infine al nodo 7. Questi nodi sono connessi attraverso archi che definiscono il percorso specifico all'interno dell'albero. Un percorso può essere definito come una sequenza di nodi connessi che va da un nodo di partenza a un nodo di destinazione all'interno della struttura dell'albero.
Livello: La generazione di un nodo rispetto alla radice (la radice è al livello 0).
Il livello di un nodo in un albero rappresenta la generazione del nodo rispetto alla radice, dove la radice stessa è al livello 0 e i suoi figli immediati sono al livello 1, i figli dei nodi di livello 1 sono al livello 2, e così via.
Utilizziamo ancora una volta la struttura di un albero binario in Python:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
E l'albero binario:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
# Aggiunta di foglie
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
radice.destro.sinistro = NodoAlbero(12)
radice.destro.destro = NodoAlbero(20)
Ora, se vogliamo determinare il livello di ciascun nodo all'interno dell'albero, possiamo farlo utilizzando una funzione ricorsiva:
python
Copy code
def calcola_livelli(nodo, livello):
if nodo is None:
return
print(f"Il nodo {nodo.valore} è al livello {livello}")
calcola_livelli(nodo.sinistro, livello + 1)
calcola_livelli(nodo.destro, livello + 1)
# Chiamata alla funzione per calcolare i livelli di ogni nodo partendo dalla radice
calcola_livelli(radice, 0)
L'output mostrerà il livello di ciascun nodo rispetto alla radice dell'albero. Ad esempio, per l'albero sopra descritto, l'output sarà:
Copy code
Il nodo 10 è al livello 0
Il nodo 5 è al livello 1
Il nodo 15 è al livello 1
Il nodo 3 è al livello 2
Il nodo 7 è al livello 2
Il nodo 12 è al livello 2
Il nodo 20 è al livello 2
Ciò indica che la radice 10 si trova al livello 0, i nodi 5 e 15 si trovano al livello 1, e così via. Ogni generazione di nodi aggiuntiva dalla radice corrisponde a un incremento del livello di quei nodi nell'albero.
Altezza: Il numero di livelli dell'albero.
L'altezza di un albero rappresenta il numero massimo di livelli presenti nell'albero stesso. In altre parole, l'altezza di un albero è il numero massimo di generazioni di nodi da qualsiasi nodo foglia fino alla radice dell'albero.
Consideriamo ancora una volta l'esempio dell'albero binario:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
E l'albero binario:
python
Copy code
# Creazione del nodo radice
radice = NodoAlbero(10)
# Aggiunta di nodi figli
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
# Aggiunta di foglie
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
radice.destro.sinistro = NodoAlbero(12)
radice.destro.destro = NodoAlbero(20)
Per calcolare l'altezza dell'albero, possiamo utilizzare una funzione ricorsiva per individuare l'altezza massima partendo dalla radice:
python
Copy code
def altezza_albero(nodo):
if nodo is None:
return -1 # Altezza di un albero vuoto è -1
else:
altezza_sinistra = altezza_albero(nodo.sinistro)
altezza_destra = altezza_albero(nodo.destro)
# L'altezza è il massimo tra l'altezza del sottoalbero sinistro e destro + 1 (per includere il nodo corrente)
return max(altezza_sinistra, altezza_destra) + 1
# Calcolo dell'altezza dell'albero partendo dalla radice
altezza = altezza_albero(radice)
print(f"L'altezza dell'albero è {altezza}")
Per l'albero sopra descritto, l'altezza sarà:
rust
Copy code
L'altezza dell'albero è 2
Questo perché il percorso più lungo dalla radice a una delle foglie richiede 2 livelli (radice -> nodo a livello 1 -> foglie a livello 2). Quindi, l'altezza dell'albero in questo caso specifico è 2, dato che è il numero massimo di livelli presenti nell'albero stesso.
Sottoalbero: Un albero derivato da un nodo e tutti i suoi discendenti.
Un sottoalbero è una struttura di albero che deriva da un nodo specifico e include quel nodo e tutti i suoi discendenti (figli, figli dei figli e così via). In altre parole, è un albero completo formato da un nodo principale e tutti i suoi sotto-nodi.
Utilizziamo ancora la struttura di un albero binario in Python e consideriamo l'implementazione di una funzione che restituisce il sottoalbero radicato in un determinato nodo:
python
Copy code
class NodoAlbero:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
def sottoalbero(nodo):
if nodo is None:
return None
nuovo_sottoalbero = NodoAlbero(nodo.valore)
nuovo_sottoalbero.sinistro = sottoalbero(nodo.sinistro)
nuovo_sottoalbero.destro = sottoalbero(nodo.destro)
return nuovo_sottoalbero
# Utilizzo della funzione per ottenere il sottoalbero radicato in un certo nodo
radice = NodoAlbero(10)
radice.sinistro = NodoAlbero(5)
radice.destro = NodoAlbero(15)
radice.sinistro.sinistro = NodoAlbero(3)
radice.sinistro.destro = NodoAlbero(7)
radice.destro.sinistro = NodoAlbero(12)
radice.destro.destro = NodoAlbero(20)
# Nodo da cui si desidera ottenere il sottoalbero
nodo_sottoalbero = radice.sinistro
# Ottenere il sottoalbero radicato nel nodo specifico
sottoalbero_radicato_nodo = sottoalbero(nodo_sottoalbero)
# Funzione per visualizzare il sottoalbero
def visualizza_albero(nodo):
if nodo is None:
return
print(nodo.valore)
visualizza_albero(nodo.sinistro)
visualizza_albero(nodo.destro)
# Visualizzazione del sottoalbero
print("Sottoalbero radicato nel nodo", nodo_sottoalbero.valore)
visualizza_albero(sottoalbero_radicato_nodo)
Nell'esempio sopra, viene definita la classe NodoAlbero per creare nodi dell'albero. La funzione sottoalbero prende un nodo come argomento e restituisce un sottoalbero radicato in quel nodo. Infine, viene mostrato un esempio di come visualizzare il sottoalbero radicato in un nodo specifico attraverso la funzione visualizza_albero.
Esempio di Algoritmo con Struttura dati Albero (Tree): Attraversamento In-Order
Input: Un albero binario.
Output: L'attraversamento in ordine dei nodi dell'albero.
Descrizione: Questo algoritmo esegue un attraversamento in ordine (in-order traversal) di un albero binario. Inizia dalla radice e visita prima il sottoalbero sinistro, poi il nodo corrente e infine il sottoalbero destro. Questo è utile per ottenere i nodi dell'albero in ordine crescente.
Ecco un esempio di algoritmo che esegue un attraversamento in ordine (in-order traversal) di un albero binario:
ALGORITMO AttraversamentoInOrdine
Input: Un nodo radice di un albero binario.
Output: La lista dei nodi dell'albero visitati nell'ordine corretto.
Descrizione: Questo algoritmo esegue un attraversamento in ordine di un albero binario. Inizia dalla radice e visita prima il sottoalbero sinistro, poi il nodo corrente e infine il sottoalbero destro.
python
Copy code
class Nodo:
def __init__(self, valore):
self.valore = valore
self.sinistro = None
self.destro = None
def attraversamento_in_ordine(nodo):
risultato = []
if nodo:
# Visita il sottoalbero sinistro
risultato += attraversamento_in_ordine(nodo.sinistro)
# Visita il nodo corrente
risultato.append(nodo.valore)
# Visita il sottoalbero destro
risultato += attraversamento_in_ordine(nodo.destro)
return risultato
# Esempio di utilizzo:
# Creiamo un albero binario
radice = Nodo(4)
radice.sinistro = Nodo(2)
radice.destro = Nodo(6)
radice.sinistro.sinistro = Nodo(1)
radice.sinistro.destro = Nodo(3)
# Eseguiamo l'attraversamento in ordine
risultato = attraversamento_in_ordine(radice)
print(risultato) # Output: [1, 2, 3, 4, 6]
In questo esempio, l'algoritmo attraversa l'albero in ordine crescente e restituisce una lista dei nodi visitati. L'attraversamento in ordine è utile per ottenere una sequenza ordinata dei valori contenuti nell'albero binario.
Grafi: Un grafo è una struttura dati composta da nodi collegati da archi. I grafi possono essere diretti (ogni arco ha una direzione) o indiretti (gli archi non hanno direzione). I grafi sono utilizzati per rappresentare reti, relazioni complesse, mappe e molte altre situazioni in cui le connessioni tra i dati sono importanti.
Un grafo è una struttura dati che rappresenta un insieme di vertici (nodi) collegati da archi. A differenza degli alberi, i grafi non hanno una struttura gerarchica predefinita. I grafi possono essere diretti (in cui gli archi hanno una direzione) o non diretti (senza direzione). Possono essere rappresentati in diverse forme, come matrici di adiacenza o liste di adiacenza.
Esempio di struttura di un grafo non diretto:
mathematica
Copy code
A -- B
| | \
| | D
| |
C -- E
Principali termini associati ai grafi:
Vertice: Punto di dati o nodo all'interno del grafo.
Nel contesto dei grafi, un vertice (o nodo) rappresenta un singolo punto di dati all'interno della struttura del grafo. Ogni vertice in un grafo può essere considerato come un'entità discreta che può essere collegata ad altri vertici tramite archi o spigoli.
Ad esempio, consideriamo un'implementazione semplificata di un grafo non diretto utilizzando una rappresentazione mediante dizionario in Python:
python
Copy code
class Grafo:
def __init__(self):
self.vertici = {}
def aggiungi_vertice(self, vertice):
if vertice not in self.vertici:
self.vertici[vertice] = []
def aggiungi_arco(self, vertice1, vertice2):
if vertice1 in self.vertici and vertice2 in self.vertici:
self.vertici[vertice1].append(vertice2)
self.vertici[vertice2].append(vertice1)
def mostra_vertici(self):
return list(self.vertici.keys())
# Creazione di un grafo
grafo = Grafo()
# Aggiunta di vertici al grafo
grafo.aggiungi_vertice('A')
grafo.aggiungi_vertice('B')
grafo.aggiungi_vertice('C')
grafo.aggiungi_vertice('D')
# Aggiunta di archi tra i vertici
grafo.aggiungi_arco('A', 'B')
grafo.aggiungi_arco('B', 'C')
grafo.aggiungi_arco('C', 'D')
grafo.aggiungi_arco('D', 'A')
# Mostra i vertici del grafo
print("Vertici del grafo:", grafo.mostra_vertici())
In questo esempio, la classe Grafo contiene metodi per aggiungere vertici e archi al grafo. I vertici sono memorizzati in un dizionario dove ogni vertice è una chiave e il suo valore è una lista di vertici adiacenti ad esso.
I vertici del grafo rappresentano i punti di dati o le entità all'interno della struttura del grafo. Ad esempio, 'A', 'B', 'C', e 'D' sono i vertici di questo grafo e gli archi connettono questi vertici. Ogni vertice può avere relazioni con altri vertici all'interno del grafo attraverso gli archi.
Arco o Edge: Connessione tra due vertici.
In un grafo, un arco (o edge in inglese) rappresenta la connessione tra due vertici. Gli archi sono gli elementi che collegano coppie di vertici all'interno della struttura del grafo, indicando l'esistenza di una relazione o di un percorso tra i vertici stessi.
Utilizzando ancora l'implementazione semplificata di un grafo non diretto in Python come esempio:
python
Copy code
class Grafo:
def __init__(self):
self.vertici = {}
def aggiungi_vertice(self, vertice):
if vertice not in self.vertici:
self.vertici[vertice] = []
def aggiungi_arco(self, vertice1, vertice2):
if vertice1 in self.vertici and vertice2 in self.vertici:
self.vertici[vertice1].append(vertice2)
self.vertici[vertice2].append(vertice1)
def mostra_archi(self):
archi = []
for vertice in self.vertici:
for adiacente in self.vertici[vertice]:
if (adiacente, vertice) not in archi:
archi.append((vertice, adiacente))
return archi
# Creazione di un grafo
grafo = Grafo()
# Aggiunta di vertici al grafo
grafo.aggiungi_vertice('A')
grafo.aggiungi_vertice('B')
grafo.aggiungi_vertice('C')
grafo.aggiungi_vertice('D')
# Aggiunta di archi tra i vertici
grafo.aggiungi_arco('A', 'B')
grafo.aggiungi_arco('B', 'C')
grafo.aggiungi_arco('C', 'D')
grafo.aggiungi_arco('D', 'A')
# Mostra gli archi del grafo
print("Archi del grafo:", grafo.mostra_archi())
In questo esempio, la funzione aggiungi_arco aggiunge un arco tra due vertici. Gli archi nel grafo sono rappresentati come coppie di vertici collegati tra loro. Nell'output, gli archi del grafo vengono mostrati come coppie di vertici collegati, ad esempio ('A', 'B'), ('B', 'C'), ('C', 'D'), e ('D', 'A').
Gli archi definiscono le connessioni tra coppie di vertici all'interno della struttura del grafo e rappresentano le relazioni o i percorsi tra questi vertici.
Grafo diretto: Grafo in cui gli archi hanno una direzione.
Un grafo diretto è una struttura di dati grafica in cui gli archi hanno una direzione specifica, il che significa che il collegamento tra due vertici ha una direzione univoca da un vertice di partenza a un vertice di destinazione. In un grafo diretto, gli archi vengono spesso definiti come "archi diretti" o "spigoli".
Differisce da un grafo non diretto, in cui gli archi non hanno direzione e la connessione tra due vertici è bidirezionale.
Esempio di implementazione di un grafo diretto utilizzando la programmazione orientata agli oggetti in Python:
python
Copy code
class GrafoDiretto:
def __init__(self):
self.vertici = {}
def aggiungi_vertice(self, vertice):
if vertice not in self.vertici:
self.vertici[vertice] = []
def aggiungi_arco(self, vertice_partenza, vertice_destinazione):
if vertice_partenza in self.vertici and vertice_destinazione in self.vertici:
self.vertici[vertice_partenza].append(vertice_destinazione)
def mostra_archi(self):
archi = []
for vertice in self.vertici:
for adiacente in self.vertici[vertice]:
archi.append((vertice, adiacente))
return archi
# Creazione di un grafo diretto
grafo_diretto = GrafoDiretto()
# Aggiunta di vertici al grafo
grafo_diretto.aggiungi_vertice('A')
grafo_diretto.aggiungi_vertice('B')
grafo_diretto.aggiungi_vertice('C')
grafo_diretto.aggiungi_vertice('D')
# Aggiunta di archi diretti tra i vertici
grafo_diretto.aggiungi_arco('A', 'B')
grafo_diretto.aggiungi_arco('B', 'C')
grafo_diretto.aggiungi_arco('C', 'D')
grafo_diretto.aggiungi_arco('D', 'A')
# Mostra gli archi del grafo diretto
print("Archi del grafo diretto:", grafo_diretto.mostra_archi())
In questo esempio, la classe GrafoDiretto rappresenta un grafo diretto. La funzione aggiungi_arco aggiunge un arco diretto tra due vertici specificando la direzione da un vertice di partenza a un vertice di destinazione.
L'output mostrerà gli archi del grafo diretto con la direzione specificata, come ad esempio ('A', 'B'), ('B', 'C'), ('C', 'D'), e ('D', 'A'). In un grafo diretto, questi archi indicano la direzione del collegamento da un vertice all'altro.
Grafo non diretto: Grafo in cui gli archi non hanno una direzione.
Un grafo non diretto è una struttura di dati grafica in cui gli archi non hanno una direzione specifica, il che significa che la connessione tra due vertici è bidirezionale. In altre parole, gli archi in un grafo non diretto non hanno una direzione definita e consentono il movimento in entrambe le direzioni tra i vertici collegati.
Di seguito c'è un esempio di implementazione di un grafo non diretto utilizzando la programmazione orientata agli oggetti in Python:
python
Copy code
class GrafoNonDiretto:
def __init__(self):
self.vertici = {}
def aggiungi_vertice(self, vertice):
if vertice not in self.vertici:
self.vertici[vertice] = []
def aggiungi_arco(self, vertice1, vertice2):
if vertice1 in self.vertici and vertice2 in self.vertici:
self.vertici[vertice1].append(vertice2)
self.vertici[vertice2].append(vertice1)
def mostra_archi(self):
archi = []
for vertice in self.vertici:
for adiacente in self.vertici[vertice]:
if (adiacente, vertice) not in archi:
archi.append((vertice, adiacente))
return archi
# Creazione di un grafo non diretto
grafo_non_diretto = GrafoNonDiretto()
# Aggiunta di vertici al grafo
grafo_non_diretto.aggiungi_vertice('A')
grafo_non_diretto.aggiungi_vertice('B')
grafo_non_diretto.aggiungi_vertice('C')
grafo_non_diretto.aggiungi_vertice('D')
# Aggiunta di archi non diretti tra i vertici
grafo_non_diretto.aggiungi_arco('A', 'B')
grafo_non_diretto.aggiungi_arco('B', 'C')
grafo_non_diretto.aggiungi_arco('C', 'D')
grafo_non_diretto.aggiungi_arco('D', 'A')
# Mostra gli archi del grafo non diretto
print("Archi del grafo non diretto:", grafo_non_diretto.mostra_archi())
In questo esempio, la classe GrafoNonDiretto rappresenta un grafo non diretto. La funzione aggiungi_arco aggiunge un arco tra due vertici specificando la connessione bidirezionale tra di essi.
L'output mostrerà gli archi del grafo non diretto senza specificare una direzione specifica, come ad esempio ('A', 'B'), ('B', 'C'), ('C', 'D'), e ('D', 'A'). In un grafo non diretto, questi archi indicano la connessione bidirezionale tra i vertici senza una direzione definita.
Grado di un vertice: Numero di archi collegati a un vertice.
Il grado di un vertice in un grafo rappresenta il numero di archi che sono collegati a quel particolare vertice. Nel caso di un grafo non diretto, il grado di un vertice indica quante connessioni (archi) ha quel vertice con gli altri vertici nel grafo.
Ecco un esempio di come calcolare il grado di un vertice in un grafo non diretto utilizzando Python:
python
Copy code
class GrafoNonDiretto:
def __init__(self):
self.vertici = {}
def aggiungi_vertice(self, vertice):
if vertice not in self.vertici:
self.vertici[vertice] = []
def aggiungi_arco(self, vertice1, vertice2):
if vertice1 in self.vertici and vertice2 in self.vertici:
self.vertici[vertice1].append(vertice2)
self.vertici[vertice2].append(vertice1)
def grado_vertice(self, vertice):
if vertice in self.vertici:
return len(self.vertici[vertice])
return None
# Creazione di un grafo non diretto
grafo_non_diretto = GrafoNonDiretto()
# Aggiunta di vertici al grafo
grafo_non_diretto.aggiungi_vertice('A')
grafo_non_diretto.aggiungi_vertice('B')
grafo_non_diretto.aggiungi_vertice('C')
grafo_non_diretto.aggiungi_vertice('D')
# Aggiunta di archi non diretti tra i vertici
grafo_non_diretto.aggiungi_arco('A', 'B')
grafo_non_diretto.aggiungi_arco('B', 'C')
grafo_non_diretto.aggiungi_arco('C', 'D')
grafo_non_diretto.aggiungi_arco('D', 'A')
# Calcolo del grado di un vertice specifico
vertice_selezionato = 'A'
grado_vertice_selezionato = grafo_non_diretto.grado_vertice(vertice_selezionato)
# Mostra il grado del vertice selezionato
print(f"Il grado del vertice {vertice_selezionato} è {grado_vertice_selezionato}")
In questo esempio, la funzione grado_vertice all'interno della classe GrafoNonDiretto calcola il grado di un vertice specifico. La funzione restituisce il numero di archi (connessioni) che partono o arrivano a quel vertice. Nell'output verrà mostrato il grado del vertice selezionato.
Ad esempio, se eseguiamo questo codice, otterremo il grado del vertice 'A' nel grafo non diretto. Il risultato dipenderà dal numero di archi che partono o arrivano al vertice 'A'.
Differenze chiave:
Struttura: Gli alberi hanno una struttura gerarchica con una radice, mentre i grafi non hanno una struttura gerarchica definita.
Connessioni: Gli alberi hanno un'unica strada tra ogni coppia di nodi, mentre i grafi possono avere molteplici percorsi tra due nodi.
Orientazione degli archi: Nei grafi diretti, gli archi hanno una direzione, mentre nei grafi non diretti non c'è direzione negli archi.
Entrambi gli alberi e i grafi trovano applicazioni in vari campi, come l'informatica, la teoria dei grafi, l'ingegneria delle reti, la modellazione dei database e molti altri. Sono strutture dati fondamentali utilizzate per risolvere problemi di routing, rappresentare relazioni e connessioni, e per implementare algoritmi di ricerca e ottimizzazione.
Esempio Algoritmo con Struttura dati Grafo (Graph): Ricerca in Profondità (DFS)
Input: Un grafo non diretto.
Output: L'ordine in cui i nodi vengono visitati durante la ricerca in profondità.
Descrizione: Questo algoritmo esegue una ricerca in profondità (Depth-First Search, DFS) su un grafo. Inizia da un nodo di partenza e visita ricorsivamente tutti i nodi adiacenti prima di tornare indietro. Questo è utilizzato per esplorare grafi e trovare percorsi tra i nodi.
Ecco un esempio di algoritmo che esegue una ricerca in profondità (DFS) su un grafo non diretto:
ALGORITMO RicercaInProfondità
Input: Un grafo non diretto rappresentato come lista di adiacenza, un nodo di partenza.
Output: L'ordine in cui i nodi vengono visitati durante la ricerca in profondità.
Descrizione: Questo algoritmo esegue una ricerca in profondità su un grafo, partendo da un nodo di partenza. Visita ricorsivamente tutti i nodi adiacenti prima di tornare indietro.
python
Copy code
def ricerca_in_profondità(grafo, nodo):
visitati = set() # Inizializziamo un insieme per tenere traccia dei nodi visitati
risultato = [] # Inizializziamo una lista per registrare l'ordine di visita dei nodi
def dfs(nodo):
visitati.add(nodo) # Segnala il nodo come visitato
risultato.append(nodo) # Aggiunge il nodo all'ordine di visita
for vicino in grafo[nodo]:
if vicino not in visitati:
dfs(vicino) # Richiama la ricerca in profondità per i nodi adiacenti non visitati
dfs(nodo) # Avvia la ricerca in profondità dal nodo di partenza
return risultato
# Esempio di utilizzo:
# Creiamo un grafo come lista di adiacenza
grafo = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1, 6],
5: [2],
6: [4]
}
nodo_partenza = 0
ordine_visita = ricerca_in_profondità(grafo, nodo_partenza)
print(ordine_visita) # Output: [0, 1, 3, 4, 6, 5, 2]
In questo esempio, l'algoritmo parte dal nodo di partenza (in questo caso, il nodo 0) e visita ricorsivamente tutti i nodi adiacenti seguendo un percorso in profondità. L'ordine in cui i nodi vengono visitati viene registrato nella lista ordine_visita. La ricerca in profondità è utilizzata per esplorare grafi e trovare percorsi tra i nodi, ed è ampiamente utilizzata in applicazioni di ricerca, come la risoluzione di labirinti o la determinazione della connettività in una rete.
4.4-Tabelle hash e Dizionari
Le tabelle hash e i dizionari sono strutture dati utilizzate per associare chiavi a valori.
Le tabelle hash e i dizionari sono strutture dati utilizzate per memorizzare elementi in base a una chiave associata. Entrambe consentono un accesso efficiente ai dati utilizzando una chiave univoca, ma hanno alcune differenze nel modo in cui sono implementate e utilizzate.
Tabelle hash: Una tabella hash è una struttura dati che consente di cercare, inserire o eliminare valori in modo efficiente. Funziona associando una chiave univoca a un valore tramite una funzione di hash. Le tabelle hash sono utilizzate per l'implementazione di strutture dati come insiemi, mappe e cache.
Una tabella hash è una struttura dati che utilizza una funzione di hash per mappare le chiavi agli indirizzi di memoria (posizioni) dove vengono memorizzati i dati. Questa funzione di hash prende una chiave e la trasforma in un indice (o posizione) all'interno di una tabella. Una buona funzione di hash cerca di distribuire uniformemente le chiavi all'interno della tabella per minimizzare le collisioni (quando due chiavi producono lo stesso indice).
Principali caratteristiche delle tabelle hash:
Struttura basata su array associativi.
Accesso rapido ai dati tramite una chiave.
Le collisioni possono verificarsi quando due chiavi producono lo stesso indice.
Esempio di Algoritmo con Struttura dati Tabella Hash (Hash Table): Ricerca rapida
Input: Una tabella hash e una chiave da cercare.
Output: Il valore associato alla chiave se presente, altrimenti un valore nullo.
Descrizione: Questo algoritmo utilizza una tabella hash per eseguire una ricerca rapida. Calcola l'hash della chiave, accede alla posizione corrispondente nella tabella e restituisce il valore associato, se presente. Le tabelle hash sono ampiamente utilizzate per l'accesso efficiente ai dati.
Ecco un esempio di algoritmo che esegue una ricerca rapida utilizzando una tabella hash:
ALGORITMO RicercaRapidaInTabellaHash
Input: Una tabella hash tabella_hash e una chiave chiave da cercare.
Output: Il valore associato alla chiave se presente, altrimenti un valore nullo.
Descrizione: Questo algoritmo utilizza una tabella hash per eseguire una ricerca rapida. Calcola l'hash della chiave, accede alla posizione corrispondente nella tabella e restituisce il valore associato, se presente.
python
Copy code
class TabellaHash:
def __init__(self, dimensione):
self.dimensione = dimensione
self.tabella = [None] * dimensione
def inserisci(self, chiave, valore):
indice = hash(chiave) % self.dimensione
self.tabella[indice] = valore
def cerca(self, chiave):
indice = hash(chiave) % self.dimensione
valore = self.tabella[indice]
return valore
# Esempio di utilizzo:
tabella = TabellaHash(10)
tabella.inserisci("chiave1", 42)
tabella.inserisci("chiave2", 18)
valore1 = tabella.cerca("chiave1")
valore2 = tabella.cerca("chiave2")
valore3 = tabella.cerca("chiave3")
print(valore1) # Output: 42
print(valore2) # Output: 18
print(valore3) # Output: None (chiave non presente)
In questo esempio, l'algoritmo utilizza una tabella hash per eseguire una ricerca rapida dei valori associati alle chiavi. La chiave viene convertita in un indice tramite una funzione di hash, quindi l'algoritmo accede direttamente alla posizione corrispondente nella tabella per recuperare il valore associato. Questo permette una ricerca molto efficiente, specialmente quando la tabella è dimensionata correttamente e non vi sono collisioni di hash.
Dizionari: Un dizionario è una struttura dati simile a una tabella hash che associa chiavi a valori. È ampiamente utilizzato in molti linguaggi di programmazione, come il dizionario in Python o la mappa in Java. I dizionari consentono di accedere rapidamente ai valori tramite chiavi univoche e sono utili per archiviare dati strutturati.
I dizionari sono una struttura dati in cui i dati sono memorizzati come coppie chiave-valore. In molte lingue di programmazione (come Python), i dizionari sono implementati utilizzando le tabelle hash. Consentono di accedere ai dati tramite una chiave anziché un indice numerico.
Principali caratteristiche dei dizionari:
Contengono coppie chiave-valore.
Le chiavi sono univoche e utilizzate per accedere ai valori.
Consentono un accesso efficiente ai dati tramite la chiave.
Esempio di utilizzo di un dizionario in Python:
python
Copy code
# Creazione di un dizionario in Python
studenti = {
'123': 'Alice',
'456': 'Bob',
'789': 'Charlie'
}
# Accesso ai dati tramite la chiave
print(studenti['123']) # Stampa: Alice
Un dizionario in Python è una struttura dati che associa chiavi ad elementi. Gli algoritmi che operano con i dizionari sfruttano spesso questa struttura dati per la memorizzazione, il recupero e la gestione dei dati.
Ecco un semplice esempio di algoritmo che utilizza un dizionario:
Supponiamo di avere una lista di numeri e vogliamo contare quante volte ciascun numero compare nella lista. Utilizzeremo un dizionario per tenere traccia di queste occorrenze:
python
Copy code
def conta_occorrenze(lista):
conteggio = {}
for numero in lista:
if numero in conteggio:
conteggio[numero] += 1
else:
conteggio[numero] = 1
return conteggio
# Esempio di lista di numeri
numeri = [1, 2, 3, 2, 1, 3, 4, 2, 5, 1, 5]
# Utilizzo della funzione per contare le occorrenze dei numeri nella lista
occorrenze_numeri = conta_occorrenze(numeri)
# Visualizzazione delle occorrenze
print("Occorrenze dei numeri:")
for numero, conteggio in occorrenze_numeri.items():
print(f"Il numero {numero} compare {conteggio} volte")
In questo esempio, la funzione conta_occorrenze riceve una lista di numeri. Utilizza un dizionario chiamato conteggio per tenere traccia delle occorrenze dei numeri nella lista. Il dizionario associa ciascun numero incontrato come chiave e incrementa il valore corrispondente ogni volta che il numero viene ritrovato.
Successivamente, il programma visualizza il conteggio delle occorrenze di ciascun numero all'interno della lista utilizzando il dizionario.
L'algoritmo qui sopra è un esempio semplice di come si può utilizzare un dizionario per implementare un algoritmo di conteggio delle occorrenze di elementi in una lista, ma ci sono molte altre applicazioni e algoritmi che possono fare uso dei dizionari per organizzare e gestire i dati in vari modi.
Differenze chiave:
Implementazione: Le tabelle hash si riferiscono a una struttura dati che utilizza una funzione di hash per memorizzare e recuperare dati, mentre i dizionari possono essere implementati utilizzando le tabelle hash o altre strutture dati.
Struttura dei dati: Le tabelle hash sono strutture più generali utilizzate per diverse applicazioni di memorizzazione e recupero dei dati, mentre i dizionari sono specifici e contengono coppie chiave-valore.
Entrambi sono strumenti importanti nella programmazione per la gestione efficiente di dati in memoria e sono utilizzati in vari contesti per accedere rapidamente ai dati tramite una chiave univoca. Ad esempio, nei linguaggi di programmazione, i dizionari sono ampiamente utilizzati per gestire associazioni chiave-valore come in Python, mentre le tabelle hash sono utilizzate per implementare varie strutture dati come le mappe in Java.
Nessun commento:
Posta un commento