L’induzione permette di dimostrare delle proprietà attraverso degli esempi.

Noi l’abbiamo utilizzata per:

• Definire, insiemi e funzioni;
• Dimostrare, le proprietà.

La stessa tecnica di applicazione, può essere utilizzata per dimostrare/definire:

• Liste di elementi
• Alberi binari
• Alberi binari etichettati

Per ciascuna di queste strutture dati, daremo una definizione induttiva e il principio di induzione.

Con il principio di induzione strutturale, infine potremmo generalizzare tutte le strutture come una sola, così da avere un’unica definizione di struttura dati.

Gli elementi contenuti in una struttura dati, possono essere di due tipi:

• omogenee: i dati sono tutti dello stesso tipo;
• eterogenee: possono esserci tipi diversi di dati.

<aside> 💡 Le strutture posso avere una dimensione fissa oppure variabile.

</aside>

Liste

Struttura dati che permette di memorizzare sequenze omogenee di dati aventi lunghezza variabile

Permette di aggregare elementi dello stesso tipo in una stessa struttura, operabile come unica.

Possono essere differenziate tra:

• sequenza lineare
• sequenza non lineare
• struttura più complessa

Una lista contenente una sequenza, è rappresentata attraverso le parentesi [ ]