Struttura dati
Da Wikipedia, l'enciclopedia libera.
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, a tal proposito, solitamente si utilizza il concetto unificato di Algoritmi e Strutture Dati. La scelta della struttura dati influirà inevitabilmente sull'efficienza degli algoritmi da utilizzare.
La struttura dati è un metodo di organizzazione dei dati, quindi prescinde dai dati effettivamente contenuti. 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 dato elementari, e le strutture dati sono strumenti per costruire tipi di dati aggregati più complessi.
L'operazione di costruire una variabile di un tipo di dato 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 creare un'astrazione dall'implementazione, dando vita al concetto di Struttura dati astratta o Abstract Data Structure (ADS).
Indice |
[modifica] Costruttori di strutture dati
[modifica] Array o vettore
Un array è una struttura dati omogenea, che contiene un numero finito di elementi 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.
[modifica] 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.
[modifica] Classe
Una classe è un costrutto tipico dei linguaggi orientati agli oggetti, e consiste in un record a cui sono associate anche delle operazioni.
[modifica] Composizione di costruttori
Questi costruttori possono essere liberamente combinati per dare luogo a cose come: "un array di 500 elementi. gli elementi dell'array sono record con quattro stringhe e due vettori, ciascun vettore contiene quattro vettori di 3 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à sempre 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.
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.
[modifica] 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 illustrate le tipologie più comuni.
[modifica] 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.
[modifica] Lista bidirezionale o doppiamente concatenata
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. liste
[modifica] 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.
[modifica] Alberi ordinati
Gli alberi binari si prestano anche a rappresentare insiemi dotati di ordinamento: un nodo contiene un elemento dell'insieme da ordinare; tutti gli elementi collegati al primo figlio sono precedenti; quelli collegati al secondo sono successivi. Questi alberi vengono anche definiti Binary Search Tree (BST) ovvero alberi di ricerca binaria.
In questo modo, la ricerca di un elemento in un albero ordinato equilibrato richiede un tempo proporzionale al logaritmo del numero di elementi. L'inserimento di un elemento in un albero ordinato richiede di rispettare l'ordinamento precedentemente descritto. Inoltre, siccome l'equilibrio dell'albero è affidato unicamente alla casualità dei successivi inserimenti, sarà necessario un periodico riequilibrio, per fare in modo che tutti i rami abbiano più o meno la stessa lunghezza e le prestazioni di ricerca non degenerino. Questa operazione può essere onerosa in termini computazionali.
[modifica] Grafo
Il grafo è una generalizzazione dell'albero. Ogni nodo ha un numero arbitrario di nodi "vicini", può contenere cicli. In generale, può essere associato un carico utile sia ai nodi che ai collegamenti tra di loro.
[modifica] 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 della 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.
[modifica] Contenitori
Le strutture dati sopra esposti possono essere utilizzate per realizzare alcuni tipi di contenitori di utilizzo frequente, che possono forzare una particolare modalità di accesso ai dati.
[modifica] Pila o stack
Una pila è una struttura dati di tipo LIFO (Last In First Out). Viene tipicamente realizzata con array o liste.
[modifica] Coda
Una coda è una struttura dati di tipo FIFO (First In First Out). Viene tipicamente realizzata con array o liste.
[modifica] 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.
[modifica] 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.
[modifica] 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à (informatica) 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.
[modifica] Altri progetti
Wikimedia Commons contiene file multimediali su Struttura dati
