5.4 Strutture astratte

Gli array, le prime e fondamentali strutture astratte, sono già state introdotte e si è inoltre parlato della loro implementazione in linguaggio C, così come sono state trattate le tabelle. Altre due strutture di cui si vedranno in seguito le implementazioni e le operazioni più comuni sono le pile e le code. Di grafi e alberi si accennerà solo alle definizioni fondamentali.

La pila o stack è una lista di elementi (insieme di elementi ordinati) in cui tutti gli inserimenti o le estrazioni di nuovi elementi avvengono ad un estremo della lista (la cima). La pila viene anche spesso indicata, a causa della gestione degli elementi, come lista LIFO (Last In First Out cioè l’ultimo inserito sarà il primo estratto). In pratica in una pila sono definite due operazioni: l’inserimento in cima di un nuovo elemento (push) e l’estrazione sempre dalla cima di un elemento (pop).

La coda è una lista di elementi in cui gli inserimenti avvengono dopo l’ultimo elemento (fondo della coda) e le estrazioni avvengono dall’estremo opposto (testa della coda). La coda viene anche indicata come lista FIFO (First In First Out cioè il primo inserito sarà anche il primo estratto).

Il grafo è costituito da un insieme di nodi (le informazioni) e archi (collegamenti fra le informazioni). Ogni nodo può essere collegato a più altri nodi stabilendo così più modi di collegare logicamente i dati rappresentati nella struttura. Per esempio se in ogni nodo sono rappresentati i dati riguardanti un alunno di un istituto scolastico, un arco potrebbe portare al prossimo alunno della stessa classe frequentata e un altro arco potrebbe portare al prossimo alunno che risiede nella stessa città dell’alunno preso in esame. In questo modo un cammino (successione di nodi collegati) porta alla conoscenza di tutti gli alunni di una stessa classe e un secondo cammino porta all’elenco degli alunni residenti in un determinato paese. Se gli archi sono orientati (cioè se, essendo collegati i nodi n_i ed n_i+1, si può andare da n_i ad n_i+1 ma non viceversa), il grafo si dice orientato.

L’albero è un grafo orientato che presenta le seguenti caratteristiche: esiste un nodo a cui non arrivano ma da cui si dipartono archi (radice), ogni nodo ha un solo arco che arriva ad esso ma può avere più archi che partono da esso, esistono nodi (foglie o nodi terminali) a cui porta un arco ma da cui non partono archi. Gli alberi vengono utilizzati per rappresentare strutture gerarchiche; nella pratica, anche al di fuori delle applicazioni informatiche, si trovano spesso applicazioni di tale struttura (alberi genealogici, famiglie zoologiche).