INFORMATICA - LE STRUTTURE DI DATI

DATI SEMPLICI E DATI STRUTTURATI

I dati semplici sono quelli (numerici, alfanumerici ecc.) che si possono considerare soltanto singolarmente, uno ad uno. Una struttura di dati è un raggruppamento, con una certa organizzazione, che si può considerare come un unico oggetto o come composto dai singoli dati; è possibile quindi riferirsi all'intera struttura o operare su ciascun singolo dato; le modalità per accedere a uno solo dipendono dal tipo di struttura considerato. Esempi di strutture di dati sono vettori, matrici, liste, ecc. Per definire una struttura di dati è necessario stabilire: - il metodo di aggregazione, cioè le regole per comporre la struttura, - il tipo di elementi che vengono aggregati, - le operazioni consentite, che dipendono ovviamente dal tipo di elementi, - il metodo che permette di individuare un singolo dato. Una struttura di dati viene definita così dal punto di vista logico, indicando cioè il collegamento e le relazioni logiche che intercorrono tra i dati.

STRUTTURE DI DATI ASTRATTE E CONCRETE

Una struttura definita da un punto di vista logico, descrivendo cioè soltanto le associazioni logiche tra i dati e i metodi per utilizzare la struttura, si dice informativa o astratta. Per poter utilizzare una struttura di dati in un programma, però, si deve poter memorizzare e gestire la struttura nella memoria del computer. Si dice struttura di dati concreta la rappresentazione nella memoria del computer di una struttura astratta. Ogni dato occupa precise posizioni nella memoria e ogni volta che si fa riferimento a un dato si fa in effetti riferimento alla posizione di memoria che lo contiene (il nome di una variabile corrisponde ad un indirizzo di memoria, stabilito in modo automatico dal computer proprio grazie all'utilizzo dei linguaggi di programmazione). Anche per i dati che fanno parte di una struttura deve essere possibile individuare quali sono le posizioni di memoria occupate e come trovare il singolo dato che interessa all'interno dell'insieme.

I VETTORI

Un vettore è un insieme di valori (di qualsiasi tipo, ma tutti dello stesso tipo) a ciascuno dei quali è associato un numero naturale che ne indica la posizione; questo numero viene chiamato indice e permette di accedere direttamente all'elemento che si vuole utilizzare. I vettori permettono di risolvere problemi in cui bisogna operare ripetutamente su dati dello stesso tipo, o effettuare ricerche o ordinamenti su gruppi di dati.

LE MATRICI

Il vettore è un caso particolare di una struttura più generale, chiamata matrice. Una matrice è un insieme di valori a ciascuno dei quali sono associati più indici. Anche in questo caso, gli elementi devono essere tutti omogenei tra loro, cioè tutti dello stesso tipo. Per una matrice ad N dimensioni, a ogni elemento sono associati N indici; ogni indice indica la posizione del valore lungo una dimensione. In particolare per una matrice a due dimensioni, pensabile come formata da righe e colonne, a ogni valore sono associati due indici, uno dei quali indica la posizione sulla colonna (cioè la riga cui il valore appartiene), l'altro la posizione sulla riga (cioè la colonna a cui il valore appartiene). A ciascun elemento della matrice si può accedere direttamente conoscendo gli indici che identificano l'elemento stesso. [Figura: Vettore di 6 elementi e matrice di 4 righe e 6 colonne. Ogni elemento del vettore è individuato dall'indice (indicato sotto l'elemento) e ogni elemento della matrice è individuato dalla coppia di indici che identificano la riga e la colonna.] Schema di vettore e di matrice

LE LISTE

Una lista è un insieme di valori omogenei per cui è stabilito un ordine nella posizione. Non è possibile accedere direttamente a un elemento. L'accesso ai valori è consentito soltanto seguendo l'ordine degli elementi; in altre parole per esaminare un elemento all'interno della lista bisogna scorrere tutti gli elementi che lo precedono (accesso sequenziale). Una lista si dice a lunghezza fissa se il numero di elementi che compongono la lista non varia nel tempo; si dice invece a lunghezza variabile se il numero di elementi varia nel tempo per effetto di inserimenti o cancellazioni di elementi.

LISTE LINEARI E CONCATENATE

Si dicono liste lineari quelle in cui si possono inserire o estrarre elementi soltanto all'inizio o alla fine della lista; casi particolari di liste lineari sono code e pile. Le liste concatenate invece permettono di inserire o estrarre elementi anche da posizioni intermedie della lista.

LE CODE

La coda è un caso particolare di lista lineare in cui gli elementi vengono inseriti da un estremo ed estratti dall'altro. Il criterio utilizzato per la gestione di una coda è il criterio FIFO (First In First Out, il primo che entra è il primo che esce), cioè viene estratto per primo l'elemento che è stato inserito per primo. Si può pensare a una coda di persone, davanti ad uno sportello, che vengono servite nell'ordine in cui sono arrivate o alle macchine in coda a un semaforo che passano nell'ordine in cui sono arrivate.

LE PILE

La pila, chiamata anche stack, è un caso particolare di lista lineare in cui gli elementi si possono inserire o estrarre da un solo estremo. Il criterio utilizzato per la gestione di una pila si dice LIFO (Last In First Out, l'ultimo che entra è il primo che esce), cioè viene estratto per primo l'ultimo valore che è stato inserito. Si può pensare ad una pila di piatti appoggiati sul tavolo; ogni piatto lavato viene appoggiato sopra la pila di piatti e ogni volta che serve un piatto si prende il primo disponibile. Gestione di una coda e di una pila

LE LISTE CONCATENATE

In una lista concatenata gli elementi sono composti ciascuno da due parti: il dato e un puntatore, cioS un valore che permette un collegamento con il dato successivo; il puntatore dell'ultimo elemento S un segnale che indica la fine della catena. L'accesso alla lista è sequenziale, cioè per accedere a un elemento qualsiasi bisogna esaminare tutti quelli che lo precedono; si passa da un elemento all'altro utilizzando le informazioni date dai puntatori (bisogna quindi conoscere il primo elemento della catena). E' possibile però inserire ed eliminare elementi in qualsiasi posizione, soltanto modificando i puntatori. La forma più semplice di lista concatenata è la catena unidirezionale, in cui ogni elemento ha un solo puntatore all'elemento successivo e l'ultimo elemento contiene nel puntatore un segnale di fine catena. Altri tipi di liste concatenate sono la catena circolare e la catena bidirezionale. Quella circolare è una catena unidirezionale in cui l'ultimo elemento contiene un puntatore al primo elemento (creando quindi un percorso circolare). La catena bidirezionale è composta da elementi che oltre al dato stesso contengono due puntatori, uno all'elemento precedente e uno al successivo. L'ultimo elementoontiene nel puntatore al successivo un segnale di fine catena; il primo elemento contiene nel puntatore al precedente un segnale di fine catena. Anche la catena bidirezionale può essere circolare. Più in generale, in una catena il dato di ogni elemento può essere sostituito da un puntatore a un dato o a un'altra lista. Ci possono anche essere famiglie di catene in cui un elemento appartiene a due o più catene. Ogni elemento di una catena può avere più di un puntatore; il numero dei puntatori deve comunque essere fisso, uguale per tutti gli elementi della catena. [Figura: Esempio di lista concatenata. Ogni elemento è formato da due parti: il dato e il puntatore all'elemento successivo; l'ultimo elemento contiene nel puntatore un segnale di fine lista.] Esempio di lista concatenata

OPERAZIONI SULLE LISTE CONCATENATE

Tutte le operazioni di ricerca, inserimento o cancellazione di elementi in una lista concatenata vengono svolte sfruttando i puntatori. Per cercare un dato in una lista si devono scorrere tutti gli elementi; per ognuno di questi si confronta la parte contenente il dato con il dato cercato e, se non corrisponde, si passa all'elemento successivo attraverso il puntatore. Si continua finché non si trova il dato voluto oppure finché si incontra il puntatore che contiene il segnale di fine catena. Per l'inserimento di un nuovo dato si devono considerare dei casi diversi, secondo la posizione in cui si vuole inserire l'elemento: all'inizio della lista, al centro o alla fine. L'inserimento di un dato come primo elemento della lista è piuttosto semplice: si conosce l'indirizzo del primo elemento della lista, che viene inserito nel puntatore del nuovo elemento; l'indirizzo del nuovo elemento inserito diventerà quello del primo elemento. Per inserire un dato al centro della lista (per esempio per creare una lista i cui i dati sono ordinati) bisogna scorrerla interamente fino a trovare l'elemento che deve precedere quello nuovo; il puntatore di questo elemento deve essere copiato nel puntatore di quello che si vuole inserire e poi modificato in modo che punti al nuovo elemento. Il procedimento per inserire un dato in fondo alla lista è analogo a quello per l'inserimento al centro della lista, soltanto che il puntatore copiato nel nuovo elemento è in realtà il segnale di fine catena. Per cancellare un elemento è sufficiente fare in modo che non faccia più parte della catena, in altre parole scorrendo i puntatori, deve essere saltato; bisogna che il puntatore dell'elemento che precede quello da cancellare lo salti, puntando invece all'elemento successivo.

I GRAFI

Un grafo è un insieme di elementi detti nodi e di archi che congiungono coppie di nodi. Una successione di archi che congiunge due nodi in un grafo si dice cammino. Si chiama cammino semplice un cammino che non passa due volte per uno stesso nodo; un cammino semplice che inizia e finisce sullo stesso nodo si dice ciclo. Un ciclo Hamiltoniano è un ciclo che passa per tutti i nodi del grafo una sola volta. Un grafo si dice orientato se per ogni arco è definito un senso in cui l'arco è percorribile; in caso contrario si dice non orientato. [Figura: Esempio di grafo orientato: nel grafo è presente un ciclo (tra i nodi A, B e C).] Esempio di grafo orientato

GLI ALBERI

Un albero è un particolare tipo di grafo; per potersi chiamare albero un grafo deve essere connesso e aciclico. Un grafo si dice connesso se, presa una coppia qualsiasi di nodi, esiste sempre un cammino che li congiunge. Un grafo si dice aciclico se non esistono cicli, cioè se non ci sono cammini che partono da un nodo e terminano sullo stesso. Se un grafo gode di queste proprietà si può disegnare in un modo particolare: un nodo rappresenta la radice e tutti gli altri nodi vengono rappresentati lungo dei rami, proprio come un albero rovesciato, dato che la radice viene rappresentata in alto e i rami sono orientati verso il basso. I nodi terminali dei rami vengono chiamati foglie. Si chiama numero di livello di un nodo il numero di archi che è necessario percorrere per raggiungere la radice. Per i nodi di un albero si usa anche un'altra terminologia: si dice che un nodo è padre dei nodi di livello inferiore e si dice anche che questi sono suoi figli; ogni nodo può avere più figli ma ogni figlio può avere soltanto un padre. Un caso particolare di albero è quello binario in cui ogni nodo ha sempre al massimo due figli. Gli alberi binari sono particolarmente importanti; su essi sono definiti dei metodi per esaminare ordinatamente tutti gli elementi (visita dell'albero). Qualsiasi albero può essere ridisegnato come albero binario seguendo delle particolari regole.

VISITA DI UN ALBERO BINARIO

La visita di un albero binario è un metodo per esaminare i nodi dell'albero. Ci sono diversi metodi per eseguirla: in ordine anticipato, cominciando dalla radice oppure posticipato, cominciando dalle foglie, o simmetrico. La descrizione dei metodi di visita viene fatta di solito in modo ricorsivo (il metodo cioè viene spiegato facendo ancora riferimento a se stesso); l'insieme di dati a cui si applica la procedura diventa ogni volta più piccolo, limitandosi sempre a un sottoalbero dell'albero considerato, finché si arriva alla radice, che permette di terminare la descrizione ricorsiva. La visita in ordine anticipato viene definita come: visita la radice visita il sottoalbero sinistro in ordine anticipato visita il sottoalbero destro in ordine anticipato. Per esempio, dato l'albero illustrato in figura Schema dell'albero binario citato nell'esempio in cui ogni nodo è indicato da una lettera, seguendo il procedimento descritto si ottiene: - esame della radice: si incontra A; - esame del sottoalbero sinistro in ordine anticipato; riprendendo la definizione si ha: - esame della radice di questo sottoalbero: si incontra B; - esame del sottoalbero sinistro in ordine anticipato; riprendendo la definzione si ha: - esame della radice: si incontra D; non ci sono sottoalberi quindi si riprende dal punto in cui si era rimasti e si trova - esame del sottoalbero destro; in questo momento si sta considerando il sottoalbero illustrato in figura Schema del sottoalbero sinistro e quindi si incontra E. Tutto il sottoalbero sinistro dell'albero principale è stato esaminato; si passa al sottoalbero destro illustrato in figura Schema del sottoalbero destro da esaminare in ordine anticipato; si ha allora: - esame della radice e si incontra C, - esame del sottoalbero sinistro, formato solo dalla radice, quindi si incontra F, - esame del sottoalbero destro, formato solo dalla radice, quindi si incontra G. Perciò l'ordine con cui si esaminano gli elementi è A B D E C F G. Allo stesso modo vengono definiti gli altri tipi di visita; per la visita in ordine posticipato: visita il sottoalbero sinistro in ordine posticipato visita il sottoalbero destro in ordine posticipato visita la radice Gli elementi dell'albero vengono in questo caso esaminati nell'ordine D E B F G C A. per la visita in ordine simmetrico: visita il sottoalbero sinistro in ordine simmetrico visita la radice visita il sottoalbero destro in ordine simmetrico Gli elementi dell'albero vengono esaminati nell'ordine D B E A F C G.