INFORMATICA - LE STRUTTURE DI DATI: RICERCHE COMPLEMENTARI

LE STRUTTURE DI DATI NEI PROGRAMMI

Le strutture di dati che abbiamo esaminato sono molto flessibili e si prestano a svariati usi; hanno però un difetto: sono realizzate nella memoria di lavoro del computer (la memoria RAM) e quindi esistono soltanto all'interno del programma che le utilizza; una volta terminato il programma (ancora prima di spegnere il computer) tutti i dati inseriti nella struttura non sono più utilizzabili; non è possibile così conservare dati in queste strutture, né comunicare dati tra un programma e un altro. Per poter conservare delle informazioni in modo permanente bisogna memorizzarle in file.

LINGUAGGI DI PROGRAMMAZIONE E STRUTTURE DI DATI

Perché sia possibile utilizzare una struttura di dati in un programma bisogna che il linguaggio di programmazione con cui viene codificato offra le istruzioni necessarie alla gestione della struttura stessa. Ogni linguaggio permette di usare solo alcune delle strutture di dati; più strutture di dati offre e più è flessibile. In genere tutti i linguaggi permettono di definire vettori e matrici a più dimensioni; la situazione è più varia per gli altri tipi di strutture. Alcuni linguaggi permettono di definire dei puntatori e offrono istruzioni per utilizzarli, consentendo così di gestire liste concatenate (e di realizzare alberi e grafi memorizzati come liste a più puntatori). Se un linguaggio non offre un metodo per memorizzare una struttura di dati, ma offre vettori e matrici, si può sempre simulare l'uso della struttura attraverso il vettore; si possono cioè usare gli elementi del vettore come se si trattasse degli elementi della struttura che servirebbe, definendo le procedure, per inserire o estrarre elementi, o per compiere qualsiasi altra operazione necessaria. Per esempio, se fosse necessario utilizzare una lista concatenata e si avessero a disposizione soltanto i vettori, si potrebbero considerare due vettori, uno per i dati e uno per i puntatori; gli elementi corrispondenti dei due vettori costituirebbero le due parti (dato e puntatore) di un elemento della lista. Le operazioni sulla lista verrebbero effettuate sui vettori, aggiornando la parte che contiene il dato e la parte che contiene il puntatore.

ESEMPI DI UTILIZZO DI STRUTTURE DATI

USO DI UNA PILA PER LA GESTIONE DELLE CHIAMATE A PROCEDURE

Quando un programma richiama una procedura si sospende l'esecuzione sul programma e si passa ad eseguire le istruzioni della procedura; quando la procedura termina si deve riprendere l'esecuzione del programma chiamante, dall'istruzione successiva a quella di richiamo della procedura (rientro dalla procedura). Una procedura può a sua volta richiamarne altre e così via (si parla in questo caso di procedure nidificate); l'esecuzione viene sospesa e prosegue sulla procedura richiamata; quando la procedura termina bisogna riprendere dal modulo chiamante, e precisamente dall'istruzione successiva a quella di richiamo. La situazione è piuttosto complessa e può essere gestita soltanto utilizzando una pila: ogni volta che viene chiamata una procedura si inserisce nella pila l'indirizzo dell'istruzione successiva a quella di richiamo; quando termina una procedura si estrae dalla pila un valore; tale valore rappresenta l'indirizzo di rientro della procedura appena terminata. Memorizzando gli indirizzi di rientro in una pila si possono gestire i rientri nell'ordine corretto.

USO DEI GRAFI PER LA SOLUZIONE DI PROBLEMI DI LOCALIZZAZIONE DI SERVIZI DI UNTERRITORIO

Nella programmazione territoriale si presenta spesso la necessità di dover localizzare il luogo più conveniente dove collocare un servizio (un ospedale, una scuola ecc.) in funzione di un certo obiettivo che tiene conto dei costi per la realizzazione e per l'utilizzo del servizio, delle distanze che dovranno essere percorse dagli utenti per accedere al servizio ecc. I servizi sono fondamentalmente di due tipi: - di routine, se utilizzati in modo regolare (scuole, uffici postali, depositi di merce ecc.); - di emergenza, se richiesti in modo irregolare e non frequentemente (ospedali, stazioni dei pompieri ecc.). La regione in cui devono essere localizzati i servizi può essere rappresentata con un grafo in cui ogni possibile utente coincide con un nodo e le vie di comunicazione con gli archi; agli archi sono associati dei valori che rappresentano le distanze. I servizi possono essere localizzati sia nei nodi che lungo gli archi. Nei servizi di emergenza il punto ottimale viene detto "centro" e il problema di ricerca "min-max" (perché si deve cercare la soluzione che rende più breve possibile la distanza dall'utente più lontano); nei servizi di routine il punto ottimale viene detto "mediano" e il problema "min-sum" (perché si deve cercare di rendere più piccola possibile la somma delle distanze tra gli utenti e il luogo in cui è posto il servizio).

USO DEI GRAFI PER LA SOLUZIONE DEL PROBLEMA DEL COMMESSO VIAGGIATORE

Il problema, noto come problema del commesso viaggiatore, consiste nel cercare un percorso che sia il più breve o più economico possibile tra quelli che toccano un certo numero di località. Può essere rappresentato con un grafo in cui i nodi rappresentano le località e gli archi le vie di comunicazione con le relative distanze o i costi (o tempi) di percorrenza.

USO DI ALBERI PER LA RAPPRESENTAZIONE DI CLASSIFICAZIONI GERARCHICHE

Gli alberi si prestano a essere utilizzati in schemi di classificazione e rappresentazione di dati tra i quali c'è un ordinamento gerarchico.