<aside> ℹ️

Struttura dati astratta

Organizzazione di un insieme di oggetti tale da poter essere rappresentata con strutture dati a sostegno delle operazioni che permettono la gestione degli oggetti in modo efficiente

</aside>

Una struttura dati astratta può essere un dizionario

Dati: un insieme $S$ di coppie $(elem, chiave)$

Operazioni:

Insert(elem e, chiave k)

Aggiunge ad S una nuova coppia (e,k)

Delete(elem e, chiave k)

Cancella da S la coppia con chiave k

Search(chiave k)

Se la chiave k è presente in S restituisce l’elemento e ad esso associato altrimenti restituisce null

Una struttura dati astratta definisce cosa vogliamo

Una struttura dati definisce come viene implementato ciò

Tabelle

<aside> ℹ️

Una tabella è una sequenza di elementi $E_i$ ciascuno dei quali è costituito da due parti:

• una chiave $K_i$, costituita da un gruppo di caratteri (o più generalmente di bit), che distingue un elemento dagli altri
• L’informazione $I_i$, associata alla chiave

Scopo della tabella è la memorizzazione delle informazioni $I_i$

Scopo della chiave è l’individualizzazione delle $I_i$ dall’esterno

</aside>

Le operazioni in una tabella sono:

• Ricerca di un elemento $E_i$ con chiave $K_i$
• Eliminazione di un elemento con chiave $K_i$, se presente
• Inserimento di un elemento $E_i$ la cui chiave $K_i$ non risulti associata ad alcun elemento presente in tabella

L’operazione fondamentale che si esegue su una tabella è la ricerca di un elemento nota la sua chiave

Per ogni elemento $E_i$ della tabella si può definire la lunghezza della ricerca - denotata con $S_i$ - come il numero di prove necessarie per raggiungere $E_i$ - numero di chiavi lette fino a trovare $K_i$.

La lunghezza media di ricerca $S$ è la media delle $S_i$ per tutti gli elementi della tabella.