Strutture dati

* STRUTTURE DATI ASTRATTE E CONCRETE Strutture dati STRUTTURE DATI ASTRATTE E CONCRETE Una struttura di dati è un insieme di valori identificabili con un solo nome, dotato di una funzione di accesso, cioè di un metodo che permette di individuare ciascun singolo valore all'interno dell'insieme. Per definire una struttura dati bisogna 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 - la funzione di accesso che permette di individuare un singolo dato. Per facilitare la memorizzazione delle struggere di dati astratte, la memoria può essere vista con organizzazioni gestite da appositi programmi, dette strutture concrete di memoria. Le strutture concrete usate più comunemente sono la struttura sequenziale, la struttura concatenata e la struttura a plesso. STRUTTURE CONCRETE 1) STRUTTURA SEQUENZIALE : è la più semplice struttura concreta di memoria; è costituita da un insieme di elementi, ognuno occupante un certo numero di byte, che si susseguono in memoria in locazioni successive e contigue. Gli elementi di solito sono della stessa lunghezza. In questo caso non bisogna esaminare in modo sequenziale tutta la struttura concreta per individuare un elemento; l'indirizzo di un elemento può essere determinato con un semplice calcolo conoscendo il numero d'ordine dell'elemento all'interno della struttura (cioè il numero di elementi che lo precedono) e l'indirizzo iniziale della struttura. Se gli elementi hanno lunghezza variabile deve essere definito un criterio per stabilire dove inizia e finisce ciascun elemento e la struttura può venire esaminata soltanto in modo sequenziale. Per individuare ciascun elemento si può porre tra un elemento e l'altro un carattere particolare, usato come separatore; la lettura in questo caso però deve procedere carattere per carattere. Oppure si può far procedere ogni elemento da una indicazione di lunghezza costante del numero di byte occupati dall'elemento stesso. Per leggere un elemento si legge la sua lunghezza e poi i byte indicati che contengono il valore. Per arrivare ad un elemento intermedio si devono leggere tutte le indicazioni di lunghezza degli elementi che lo precedono. 2) STRUTTURA CONCATENATA : permette di gestire in modo dinamico l'occupazione della memoria, cioè di inserire o eliminare elementi durante l'elaborazione (anche al centro della catena). La forma più semplice di struttura concatenata è composta da elementi (celle o nodi) di lunghezza costante, ognuno diviso in due parti: il dato e il puntatore al nodo successivo. Deve anche essere noto l'indirizzo del primo elemento della struttura. OPERAZIONI SULLA CATENA: devono essere compiute rispettando rigorosamente l'ordine per non perdere il valore dei puntatori modificati. RICERCA: si scorrono gli elementi della lista usando i puntatori fino a quando si trova l'elemento cercato o finché si arriva alla fine