5.3 Strutture dei dati: generalità

Negli esempi che si sono esaminati si sono incontrati, oltre che dati elementari come, per esempio, quelli di tipo int, float o char, si sono esaminati due tipi di aggregati di dati: i vettori, le strutture e le tabelle.

In questa sede ci si propone di esporre altri tipi di aggregati o, come si dice più correttamente altri tipi di strutture di dati. Una trattazione completa delle strutture dei dati va oltre gli scopi dei presenti appunti: qui si vogliono fornire i concetti generali, le operazioni fondamentali e le prime strutture dati.

Per prima cosa occorre distinguere tra:

• Struttura astratta: identifica il modo come i dati sono collegati logicamente fra di loro. Con questo termine si fa riferimento alle leggi che definiscono le relazioni fra i dati.

• Struttura interna: identifica il modo come i dati sono rappresentati nella memoria di un elaboratore. Per rappresentare una struttura astratta in memoria si dovrà tenere conto delle leggi che raggruppano i dati e del modo come è possibile tradurre tale struttura astratta in una struttura interna senza stravolgere le proprietà di aggregazione dei dati: cioè adattare la struttura astratta alle esigenze di conservazione in memoria dei dati (allocazione in memoria della struttura astratta).

Le strutture interne sono sostanzialmente riconducibili a due tipi:

1. Struttura sequenziale: è costituita da un insieme definito di elementi, ognuno costituito da una o più celle di memoria, che sono fisicamente adiacenti in memoria. La caratteristica di essere la struttura composta da un numero definito di elementi, la rende adatta a conservare strutture astratte di tipo statico. Strutture cioè che restano più o meno uguali nel tempo: se si alloca spazio per n elementi, la quantità degli elementi effettivamente presenti in memoria sarà uguale o quasi uguale a tale numero. Il fatto poi che la lunghezza degli elementi sia la stessa per tutti porta ad una facilità di accesso ad un elemento qualsiasi della struttura. Se infatti si vuole conoscere l’indirizzo dell’i-esimo elemento basta calcolare: IND(x_i)=IND_b+(i-1)l dove con IND(x_i) si è indicato l’indirizzo da trovare (l’elemento è x_i), IND_b è l’indirizzo base (l’indirizzo del primo elemento della struttura), i è la posizione relativa dell’elemento cercato ed l è la lunghezza comune. Il modo come è organizzata tale struttura se da una parte permette di rintracciare facilmente e in maniera rapida, qualsiasi elemento, dall’altra si presenta in maniera rigida: non solo il numero degli elementi non può essere variato (essendo gli elementi adiacenti è necessario predisporre una serie di locazioni di memoria consecutive nelle quali conservare la struttura), ma anche l’inserimento o l’eliminazione di un nuovo elemento fra due già esistenti risultano operazioni se non impossibili, quanto meno estremamente dispendiose (occorre infatti per esempio nel caso di inserimento fra l’elemento x_i e l’elemento x_i+1, se è possibile se cioè la struttura non è interamente occupata, spostare gli elementi dalla posizione i+1 in poi in modo da creare lo spazio per l’elemento da inserire e quindi procedere con l’inserimento).

2. Struttura concatenata: è costituita da un insieme di elementi disposti in posizioni qualsiasi della memoria. Ogni elemento è costituito da una parte nella quale è contenuta l’informazione da conservare e un indicatore (puntatore) che fornisce l’indirizzo dell’elemento che deve intendersi successivo logicamente al corrente. L’ultimo elemento contiene, nel puntatore, un valore particolare (puntatore nullo) che permette di riconoscere l’elemento come l’ultimo della catena. Poiché non è possibile calcolare direttamente l’indirizzo di un elemento generico della struttura, per accedere ad esso è necessario, conoscendo l’indirizzo del primo elemento, percorrere sequenzialmente la catena finché non si trova l’elemento cercato. In questa struttura non è necessario conoscere in anticipo la quantità degli elementi che ne dovranno far parte: quando occorre inserire un nuovo elemento basta avere a disposizione una quantità di memoria tale da poter conservare l’elemento. L’aggancio dell’elemento alla struttura è facilitato dall’uso dei puntatori: il prossimo elemento non è quello che si trova conservato nelle locazioni successive rispetto all’elemento considerato (come nella struttura sequenziale), ma quello che segue logicamente cioè quello indicato dal puntatore. L’inserimento dell’elemento E_k fra l’elemento E_i e l’elemento E_i+1, per esempio, è una operazione che può essere compiuta in modo semplice tenendo presente che ogni elemento, per esempio E_k, è formato dall’informazione I_k e dal puntatore P_k. Per effettuare l’inserimento basta sistemare E_k in una zona di memoria disponibile, per esempio all’indirizzo IND(E_k), mettere nel puntatore P_k dell’elemento E_k il valore attualmente contenuto in P_i (in modo che E_i+1 segua E_k), mettere nel puntatore E_i il valore IND(E_k) in modo che E_k risulti il successivo di E_i. La struttura si presta, per le sue caratteristiche, a rappresentare strutture astratte di tipo dinamico; strutture cioè che cambiano frequentemente nel tempo. Un elemento della struttura potrà avere anche un puntatore al precedente e, in questo caso, si parlerà di catena bidirezionale, così come si potrà avere l’ultimo elemento che punta al primo e, in questo caso, si parlerà di catena circolare.

Per riassumere brevemente si può dire che la struttura sequenziale presenta il vantaggio di fornire accesso immediato a qualsiasi elemento della struttura a costo di una rigidità della struttura (numero elementi da conoscere all’atto dell’allocazione, difficoltà di aggiornamento della struttura). La struttura concatenata, al contrario, può conservare elementi finché c’è spazio in memoria, le operazioni di inserimento o cancellazione di elementi vengono svolte in maniera agevole, ma risulta impossibile l’accesso diretto ad un elemento qualunque della struttura.