Vettore

Article

August 17, 2022

In informatica, una struttura dati array (inglese: array data structure), abbreviata come array (inglese: Array), è una struttura dati composta da una raccolta di elementi dello stesso tipo e una memoria contigua è allocata per l'archiviazione. L'indice dell'elemento può essere utilizzato per calcolare l'indirizzo di archiviazione corrispondente all'elemento. Il tipo più semplice di struttura dati è un array unidimensionale. Ad esempio, un array intero a 32 bit con indice da 0 a 9 può essere utilizzato come indirizzo di memoria 2000, 2004, 2008, ... 2036, memorizzando 10 variabili, quindi l'elemento con indice i è 2000 in memoria +4×i indirizzo . L'indirizzo di memoria del primo elemento dell'array è chiamato primo indirizzo o indirizzo di base. Un array bidimensionale, che corrisponde al concetto di matrice in matematica, può essere espresso come una griglia rettangolare bidimensionale. Per esempio: un [ 3 6 2 0 1 − 4 2 − 1 0 ] {\displaystyle a{\begin{bmatrix}3&6&2\\0&1&-4\\2&-1&0\end{bmatrix}}} È espresso in linguaggio C come int a[3][3] {{3, 6, 2}, {0, 1, -4}, {2, -1, 0}};. In alcuni casi, il termine "vettore" può anche riferirsi a un array bidimensionale, sebbene sia chiamato più accuratamente una tupla in senso matematico, piuttosto che un vettore. Ma va notato che: in alcuni campi dell'informatica, come Matlab, le tuple si riferiscono al tipo di struttura del linguaggio C, con strutture dati fisse che sono spesso diversi tipi di membri di dati. Gli array vengono spesso utilizzati per implementare le tabelle di database, in particolare le tabelle di ricerca; le tabelle vengono talvolta utilizzate come sinonimi per gli array. L'array è una delle strutture dati più antiche e importanti e molti programmi utilizzano gli array. Sono anche usati per implementare molte altre strutture di dati, come elenchi e stringhe. Hanno sviluppato efficacemente la logica di indirizzamento del computer. Nella maggior parte dei computer moderni e in molti dispositivi di archiviazione esterni, la memoria è come un array unidimensionale e l'indice è il suo indirizzo. I compilatori e le unità di elaborazione (in particolare i processori vettoriali) sono spesso ottimizzati per le operazioni sugli array. Poiché l'indice dell'elemento può essere calcolato mentre il programma è in esecuzione, l'array è molto utile. Inoltre, molti elementi dell'array possono essere elaborati con una singola istruzione iterativa. Per questo motivo gli elementi della struttura dati dell'array devono avere la stessa dimensione e devono essere rappresentati dallo stesso tipo di dati. Il termine array viene solitamente utilizzato per indicare il tipo di dati array, un tipo di dati integrato nella maggior parte dei linguaggi di programmazione di alto livello. I tipi di array sono generalmente implementati da strutture array; tuttavia, in alcuni linguaggi, possono essere implementati da tabelle hash, elenchi concatenati, alberi di ricerca o altre strutture dati. Nella descrizione degli algoritmi, il termine "array" ha un significato particolarmente enfatico di array associativo o "array astratto", un modello informatico teorico (tipo di dati astratto o ADT) che si concentra sulle proprietà di base degli array.

Storia

Il primo computer digitale utilizzava la programmazione in linguaggio macchina per impostare e accedere a tabelle di dati, strutture di array per calcoli vettoriali e matriciali e molti altri scopi. Nel 1945, quando costruì il primo computer con architettura di tipo Van Neumann, John von Neumann scrisse il primo programma di ordinamento di array (merge sort). L'indicizzazione dell'array è stata inizialmente completata dal codice automodificante e successivamente utilizzando il registro indice e l'indirizzamento indiretto. Alcuni host progettati negli anni '60, come Burroughs B5000 e i suoi successori, utilizzano la segmentazione della memoria per eseguire controlli dei limiti dell'indice nell'hardware. Fatta eccezione per l'hardware della macchina stesso, il linguaggio macchina non supporta in modo specifico gli array. I primi linguaggi di programmazione di alto livello includono FORTRAN (1957), Lisp (1958), COBOL (1960) e ALGOL 60.