Struttura dati

Strutture dati di base

Array

Il tipo più semplice di struttura dati è un array lineare. Conosciuto anche come array unidimensionale. Un array contiene diversi valori dello stesso tipo (Integer, Floats, String, ecc.). L'accesso agli elementi all'interno dell'array è molto veloce. Una matrice è normalmente di dimensione fissa. Dopo che la dimensione dell'array è definita all'inizio, potrebbe non essere possibile aumentare la dimensione dell'array senza creare un nuovo array più grande e copiare tutti i valori nel nuovo array. In informatica, una struttura di dati array o semplicemente un array è una struttura di dati che consiste in una collezione di elementi (valori o variabili), ognuno identificato da almeno un indice di array o chiave. Un array è memorizzato in modo che la posizione di ogni elemento possa essere calcolata dalla sua tupla di indice tramite una formula matematica.

Per esempio, un array di 10 variabili intere, con indici da 0 a 9, può essere memorizzato come 10 parole agli indirizzi di memoria 2000, 2004, 2008, 2036, in modo che l'elemento con indice i abbia l'indirizzo 2000 + 4 × i.

Poiché il concetto matematico di una matrice può essere rappresentato come una griglia bidimensionale, gli array bidimensionali sono anche chiamati a volte matrici. In alcuni casi il termine "vettore" è usato in informatica per riferirsi ad un array, anche se tuple piuttosto che vettori sono l'equivalente matematico più corretto. Gli array sono spesso usati per implementare le tabelle, specialmente le tabelle di ricerca; la parola tabella è talvolta usata come sinonimo di array.

Gli array sono tra le strutture di dati più antiche e importanti, e sono usati da quasi tutti i programmi. Possono anche essere usati per implementare molte altre strutture di dati, come liste e stringhe. Sfruttano efficacemente la logica di indirizzamento dei computer. Nella maggior parte dei computer moderni e in molti dispositivi di memorizzazione esterni, la memoria è un array unidimensionale di parole, i cui indici sono i loro indirizzi. I processori, specialmente quelli vettoriali, sono spesso ottimizzati per le operazioni di array.

Gli array sono utili perché gli indici degli elementi possono essere calcolati a tempo di esecuzione. Tra le altre cose, questa caratteristica permette ad una singola istruzione iterativa di elaborare arbitrariamente molti elementi di un array. Per questo motivo, gli elementi di una struttura dati di un array devono avere la stessa dimensione e devono utilizzare la stessa rappresentazione dei dati. L'insieme delle tuple indice valide e gli indirizzi degli elementi (e quindi la formula di indirizzamento degli elementi) sono di solito, ma non sempre, fissati mentre l'array è in uso.

Il termine array è spesso usato per indicare il tipo di dati array, un tipo di dati fornito dalla maggior parte dei linguaggi di programmazione di alto livello che consiste in una collezione di valori o variabili che possono essere selezionati da uno o più indici calcolati a run-time. I tipi di array sono spesso implementati da strutture di array; tuttavia, in alcuni linguaggi possono essere implementati da tabelle hash, liste collegate, alberi di ricerca o altre strutture di dati.

Elenco collegato

Una struttura di dati collegati è un insieme di informazioni/dati collegati insieme da riferimenti. I dati sono spesso chiamati nodi. I riferimenti sono spesso chiamati link o puntatori. Da qui in poi, le parole nodo e puntatore saranno usate per questi concetti.

Nelle strutture di dati collegate, i puntatori sono solo dereferenziati o confrontati per l'uguaglianza. Quindi, le strutture di dati collegate sono diverse dagli array, che richiedono l'aggiunta e la sottrazione di puntatori.

Le liste collegate, gli alberi di ricerca e gli alberi di espressione sono tutte strutture di dati collegate. Sono anche importanti in algoritmi come l'ordinamento topologico e il set union-find.

Stack

Una pila è una struttura dati di base che può essere logicamente pensata come una struttura lineare rappresentata da una pila fisica reale, una struttura in cui l'inserimento e l'eliminazione di elementi avviene ad un'estremità chiamata cima della pila. Il concetto di base può essere illustrato pensando al vostro set di dati come una pila di piatti o di libri dove potete prendere solo l'elemento in cima alla pila per rimuovere le cose da essa. Questa struttura è usata in tutta la programmazione.

L'implementazione di base di uno stack è anche chiamata struttura "Last In First Out"; tuttavia ci sono diverse varianti di implementazioni di stack.

Ci sono fondamentalmente tre operazioni che possono essere eseguite sulle pile. Esse sono:

• inserire ("spingere") un elemento in una pila
• cancellare ("popping") un elemento dalla pila
• visualizzare il contenuto dell'elemento superiore della pila ("peeking")

Coda

Una coda è un tipo di dati astratto o una struttura di dati lineare, in cui il primo elemento viene inserito da un'estremità (la "coda"), e la cancellazione di un elemento esistente avviene dall'altra estremità (la "testa"). Una coda è una struttura "First In First Out". "First In First Out" significa che gli elementi messi in coda per primi usciranno per primi, e gli elementi messi in coda per ultimi usciranno per ultimi. Un esempio di coda sono le file di persone in attesa. La prima persona della fila va per prima, e l'ultima persona della fila va per ultima.

Il processo di aggiunta di un elemento a una coda è chiamato "enqueuing" e il processo di rimozione di un elemento da una coda è chiamato "dequeuing".

Grafico

Un grafo è un tipo di dati astratto che ha lo scopo di implementare i concetti di grafo e ipergrafo della matematica.

Una struttura di dati a grafo consiste in un insieme finito (e possibilmente mutevole) di coppie ordinate, chiamate bordi o archi, di certe entità chiamate nodi o vertici. Come in matematica, si dice che un bordo (x,y) punta o va da x a y. I nodi possono essere parte della struttura del grafico, o possono essere entità esterne rappresentate da indici o riferimenti interi. Una struttura di dati a grafo può anche associare ad ogni bordo qualche valore, come un'etichetta simbolica o un attributo numerico.

Albero

L'albero è una delle strutture dati avanzate più potenti. Appare spesso in materie avanzate come l'intelligenza artificiale (AI) e il design. Sorprendentemente, l'albero è importante in un'applicazione molto più elementare - la tenuta di un indice efficiente.

Quando si usa un albero c'è un'alta probabilità che venga usato un indice. Il tipo più semplice di indice è una lista ordinata di campi chiave. Un albero ha normalmente una struttura definita. Nel caso di un albero binario, è possibile utilizzare una ricerca binaria per individuare qualsiasi elemento senza dover guardare ogni elemento.

Il tipo di dati albero è un tipo di grafico che significa che molti algoritmi fatti per attraversare un grafico funzionano anche con un albero, tuttavia, gli algoritmi possono essere molto simili e devono avere un nodo iniziale dedicato, cioè il nodo senza altri nodi che lo collegano.

Il problema con una semplice lista ordinata si presenta quando iniziate ad aggiungere nuovi elementi e dovete mantenere la lista ordinata - può essere fatto in modo ragionevolmente efficiente ma richiede alcune modifiche. Inoltre, un indice lineare non è facile da condividere perché l'intero indice deve essere "bloccato" quando un utente lo modifica, mentre un "ramo" di un albero può essere bloccato, lasciando gli altri rami modificabili dagli altri utenti (poiché non possono essere influenzati).

Tabella Hash

Una tabella hash è un array in cui ogni indice punta a una lista collegata basata su un valore hash. Un valore di hash è un valore determinato da una funzione di hash. Una funzione di hash determina un valore unico basato sui dati che sta memorizzando. Questo permette l'accesso ai dati in tempo costante perché il computer sa sempre dove guardare.

Ogni nodo punta ad un altro nodo.