Struttura dati

Un array monodimensionale, una delle strutture dati più semplici

In informatica, una struttura dati è un'entità usata per organizzare un insieme di dati all'interno della memoria del computer, ed eventualmente per memorizzarli in una memoria di massa. La scelta delle strutture dati da utilizzare è strettamente legata a quella degli algoritmi; per questo, spesso essi vengono considerati insieme. Infatti, la scelta della struttura dati influisce inevitabilmente sull'efficienza computazionale degli algoritmi che la manipolano.

Descrizione

La struttura dati è un metodo di organizzazione dati, quindi prescinde da ciò che è effettivamente contenuto. Ciascun linguaggio di programmazione offre strumenti, più o meno sofisticati, per definire strutture dati, ovvero aggregare dati di tipo omogeneo o eterogeneo. Questi strumenti sono tipicamente componibili.

Più formalmente, i linguaggi forniscono un insieme predefinito di tipi di dati elementari, e le strutture dati sono strumenti per costruire tipi di dati aggregati più complessi.

L'operazione di costruzione di una variabile di un tipo di dati complesso è detta "istanziazione", e può avvenire sia durante la compilazione del programma (compile time) sia durante la sua esecuzione (runtime).

Le strutture di dati si differenziano prima di tutto in base alle operazioni che si possono effettuare su di esse e alle prestazioni offerte. Questo permette di studiare un'astrazione dall'implementazione.

Strutture dati astratte

Si parla di strutture dati astratte quando si vuole distinguere le strutture stesse dalle loro implementazioni; una struttura dati astratta può essere implementata in modi diversi in diversi linguaggi di programmazione, o addirittura nello stesso linguaggio.

Costruttori di strutture dati

Array o vettore

Un array è una struttura dati omogenea, che contiene un numero finito di elementi tutti dello stesso tipo, ad esempio un vettore di 10 interi. Questi elementi sono individuati attraverso un indice numerico, che tipicamente va da 0 al numero massimo di elementi meno uno. La dimensione del vettore deve essere dichiarata al momento della sua creazione. Vettori di dimensione diversa costituiscono tipi di dati diversi. L'accesso ad un elemento di un array ha un costo computazionale costante, mentre l'aggiunta o la rimozione di elementi in posizione casuale possono essere piuttosto onerose, tipicamente appannaggio degli array dinamici.

Record o struttura

Un record è una struttura dati che può essere eterogenea o omogenea. Nel primo caso contiene una combinazione di elementi che possono essere di diverso tipo, ad esempio un intero, un numero in virgola mobile e un carattere testuale. Gli elementi che lo compongono sono detti anche campi, e sono identificati da un nome.

Classe

Una classe è un costrutto tipico dei linguaggi orientati agli oggetti, e consiste in un record a cui sono associate anche delle operazioni o metodi.

Composizione di costruttori

Questi costruttori possono essere liberamente combinati per dare luogo a strutture più complesse. Per esempio, è possibile rappresentare una matrice bidimensionale di taglia $n\times m$ come un vettore di dimensione $n$ avente come elementi dei vettori di lunghezza $m$. Ancora, si può definire un array di cinquecento elementi, ognuno dei quali è un record composto da quattro stringhe e due vettori, ciascuno contenente quattro vettori di tre caratteri.

Le strutture dati ottenute mediante la composizione di questi costruttori sono dette anche "statiche", in quanto la loro occupazione di memoria è definita al momento della compilazione, o al più al momento dell'istanziazione. Ad esempio: il programma decide che ha bisogno di un array di 100 elementi per processare i suoi dati, e lo alloca, ovvero impegna la memoria necessaria. Da questo momento, l'array avrà dimensione fissa cioè sarà sempre composto di 100 elementi, e terrà impegnata la memoria necessaria fino alla terminazione del programma o a quando non sarà distrutto. Cambiare la lunghezza dell'array è possibile, ma molto costoso in termini di risorse di calcolo ed è quindi un'operazione evitata per quanto possibile (vedi array dinamici).

Il limite delle strutture dati statiche è che mal si adattano a problemi in cui la numerosità dei dati da trattare non è nota a priori e/o varia sensibilmente durante l'esecuzione del programma.

Strutture dati dinamiche

Le strutture dati dinamiche sono basate sull'uso di dati di tipo puntatore, e sull'allocazione dinamica della memoria. Gli elementi possono essere allocati (e deallocati) man mano che servono, collegati tra loro in modi diversi, e questi collegamenti possono a loro volta mutare durante l'esecuzione del programma. Lo spazio di memoria necessario per allocare i puntatori, e le operazioni necessarie alla loro manutenzione costituiscono il costo aggiuntivo delle strutture dati dinamiche.

In assenza dei puntatori, è anche possibile costruire strutture dati dinamiche utilizzando gli array, rinunciando però alla flessibilità nell'uso della memoria: viene allocato un array di dimensioni sufficienti a contenere tutti gli elementi che si pensa di dover gestire, e al posto dei puntatori si usano indici nell'array.

Le strutture dati dinamiche possono adattarsi a rappresentare qualsiasi situazione. Qui vengono illustrati i tipi più comuni.

Lista

Esempio di lista

Una lista è un insieme di "nodi" collegati linearmente. I nodi sono dei record che contengono un "carico utile" di dati, ed un puntatore all'elemento successivo della lista. L'ordine con cui sono collegati i nodi definisce un ordinamento tra di loro. Un nodo funge da testa della lista, e da questo è possibile accedere a tutti i nodi della lista. Conoscendo un nodo interno alla lista, è possibile accedere ai nodi successivi, ma non a quelli precedenti.

Il costo di accesso ad un nodo della lista cresce con la dimensione della lista. Conoscendo il nodo precedente ad un nodo N, è possibile rimuovere N dalla lista, o inserire un elemento prima di lui, in un tempo costante.

Lista bidirezionale o doppiamente concatenata

Lista bidirezionale

In questo caso i nodi contengono un puntatore sia al nodo precedente che al successivo. Usando la sintassi del linguaggio C, dato un nodo N il suo successore è N->succ, e il suo precedente è N->prec. Deve sempre essere vero che N->succ->prec == N. Ogni nodo permette di accedere a tutti gli elementi della lista. Gli elementi "strutturali" di questa struttura dati, ovvero i due puntatori contenuti in ogni nodo, sono ridondanti.

Albero

Esempio di albero

Un albero è una rappresentazione dell'albero in teoria dei grafi.

Ogni nodo contiene due (o più) puntatori ad altri nodi che sono detti suoi "figli". Continuando nella metafora, dato un nodo, è possibile accedere a tutti i suoi discendenti. Un albero deve essere privo di cicli, ovvero un nodo non può essere discendente di sé stesso, ovvero non deve essere possibile partire da un nodo, seguire i puntatori ai figli e ritornare al nodo di partenza. Inoltre ciascun nodo deve essere figlio di un solo padre.

In alcune implementazioni, ogni nodo contiene anche un collegamento al suo "padre", chiaramente distinto da quelli ai suoi figli.

Tra i figli di un nodo esiste normalmente una relazione d'ordine, definita dall'ordine dei puntatori nel padre.

In molte implementazioni, ogni nodo ha un numero fissato di figli, ad esempio due o tre. Si parla in questo caso di alberi binari o ternari. In altri casi, il numero di figli di un nodo è arbitrario; questo può essere gestito memorizzando i figli di un nodo in una lista di uno dei tipi descritti sopra.

Ciascun nodo, oltre ai puntatori ai nodi figli, ha normalmente un "carico utile", ovvero un dato associato al nodo, utile per il problema applicativo da risolvere.

Gli alberi si prestano molto bene a rappresentare le formule matematiche.

Alberi binari ordinati

Quando i dati sono dotati di una relazione d'ordine totale, essa stessa può essere rappresentata in maniera conveniente nella struttura di alberi binari.

Ad esempio, si può adottare la convenzione secondo la quale un nodo N è nel sotto-albero sinistro M se e solo se N < M, altrimenti N è nel sottoalbero destro di M. Un albero dotato di questa proprietà è chiamato albero binario di ricerca (o binary search tree, BST). In questo modo, la ricerca di un elemento in un albero ordinato equilibrato richiede un tempo proporzionale all'altezza dell'albero, che nel caso migliore è a sua volta proporzionale al logaritmo del numero di elementi, mentre l'inserimento di un elemento in un albero ordinato richiede inoltre che la proprietà di ordinamento precedentemente descritta sia rispettata. A seconda dell'ordine degli inserimenti l'albero potrebbe sbilanciarsi ed avere cioè foglie a profondità molto diverse le une dalle altre, causando inefficienze nella ricerca. Talvolta è quindi necessario che la struttura dati sia dotata e sia oggetto di un'operazione di equilibratura forzata che minimizzi l'altezza dell'albero.

Grafo

Il grafo è una generalizzazione dell'albero. Ogni nodo ha un numero arbitrario di nodi "vicini", e può contenere cicli. In generale, può essere associato un carico utile sia ai nodi che ai collegamenti tra di loro.

Tabella hash

Una tabella hash è una struttura dati utile per cercare velocemente un elemento all'interno di un insieme sulla base di una chiave, ovvero di un sottoinsieme dalle caratteristiche dell'elemento. Di ciascun elemento da memorizzare viene calcolato un hash della chiave. Viene poi costruito un array, che ha come indice il valore dell'hash, come elementi puntatori a liste di nodi che corrispondono a quel valore dell'hash. Se la funzione di hash è ben scelta, statisticamente le liste avranno lunghezze equilibrate.

Per cercare un elemento, si calcola il suo valore di hash, si seleziona l'elemento dell'array corrispondente e si percorre la lista fino a quando non lo si trova.

Contenitori

Le strutture dati sopra esposte possono essere utilizzate per realizzare alcuni tipi di contenitori di utilizzo frequente, che possono forzare una particolare modalità di accesso ai dati.

Pila o stack

Una pila è una struttura dati di tipo LIFO (Last In First Out). Viene tipicamente realizzata con array o liste.

Coda

Una coda è una struttura dati di tipo FIFO (First In First Out). Viene tipicamente realizzata con array o liste.

Array associativo

È una struttura dati presente in molti linguaggi di scripting. Consiste in un array, i cui elementi sono però identificati da una chiave di tipo arbitrario invece che da un indice numerico. Per accedere ad un elemento, si mette tipicamente la sua chiave tra parentesi quadre, al posto dell'indice. Se non esiste un elemento con quella chiave, si ottiene un errore oppure un valore convenzionale.

Template di strutture dati

L'implementazione manuale di strutture dati dinamiche è un compito ripetitivo, a rischio di errori. Per questa ragione, sono stati usati vari metodi per separare la definizione delle strutture dati dal loro utilizzo in algoritmi.

Alcuni linguaggi mettono a disposizione lo strumento dei template, che permette di scrivere funzioni o classi parametriche rispetto al tipo degli argomenti o di alcuni membri della classe che può essere utilizzata normalmente.

Un template viene istanziato specificando il tipo degli argomenti di funzione o dei membri di classe non specificati nella definizione, costruendo una funzione o una classe.

In questo modo, è possibile scrivere una classe lista generica rispetto al contenuto, con i metodi necessari a manipolare una lista, e poi usarla sia per gestire liste di interi che liste di oggetti complessi.

STL e Generics

Un importante sforzo per costruire una libreria di strutture dati generiche rispetto al tipo dei dati immagazzinati è la Standard Template Library (vedi STL su sito SGI), basata sul concetto di fornire uno strumento per comporre in modo ortogonale dati, contenitori (strutture dati) ed algoritmi. In STL, un importante strumento per collegare in modo generico strutture dati ed algoritmi sono gli iteratori, una generalizzazione dei puntatori.

STL è una libreria di classi in linguaggio C++.

Il linguaggio Java presenta, invece, due modalità per gestire le strutture dati fondamentali presenti nel linguaggio. Fino alla versione 1.4 la gestione dei contenitori è stata realizzata con l'ereditarietà invece che con i template. I contenitori contengono quindi oggetti di tipo "Object", un tipo da cui discendono tutte le classi definite in Java; di conseguenza, in Java non è altrettanto facile assicurarsi che tutti gli oggetti inseriti in un contenitore appartengano ad un dato tipo. Dalla versione 1.5 sono stati introdotti i generics, che si comportano in modo molto simile ai template C++ e risolvono molti dei problemi relativi all'upper casting dei "vecchi" contenitori.

Voci correlate

• Array
• Database
• Lista di strutture dati
• Modello dei dati
• Record (tipo di dato)
• Tipo di dato
• Struttura dati persistente

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «data structure»
• Wikimedia Commons contiene immagini o altri file sulle strutture dati

Collegamenti esterni

• dati, struttura di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) data structure, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Data structures (Computer science), su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Data Structure, su MathWorld, Wolfram Research.
• (EN) Denis Howe, data structure, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (EN) Dizionario degli algoritmi e delle strutture dati, su nist.gov.