Liste - Argomenti, Le liste come astrazioni di dato

informatica

Liste

Argomenti

Operazioni

Le liste come astrazioni di dato

Una lista puo' essere definita in vari modi, tra cui i due modi che seguono:

Una lista e' una sequenza, anche vuota, di elementi

una lista e' un oggetto di una di queste due categorie:

una lista vuota

una struttura composta da un elemento seguito da una lista

La seconda definizione, di tipo ricorsivo, suggerisce sia un criterio per costruire una lista sia un criterio per scomporre una lista nei suoi elementi costituitivi. Un possibile insieme di operazioni primitive sulle liste, ispirate al linguaggio Lisp, puo' essere definito come segue:

Operazioni primitive sulle liste

Nelle definizioni che seguono, elType rappresenta il tipo degli elementi della lista

Una possibile classificazione

lista //astrazione

listaVuota

listaNonVuota

La lista e' una astrazione di dato che puo' avere due specializzazioni concrete: la lista vuota e la lista non vuota.

Le liste si possono considerare casi speciali di ulteriori astrazioni di dato, come ad esempio le sequenze. La classificazione puo' cioe' essere estesa come segue:

sequenza //astrazione

sequenzaLimitata

array

sequenzaNonLimitata

lista //astrazione

listaVuota

listaNonVuota

Le sequenza possono a loro volta essere casi speciali di astrazioni di dato ancora piu' generali:

dato //astrazione

atomico

numerico

logico

carattere

...

strutturato

sequenza

....

In Java il concetto che viene posto alla base di ogni possibile gerarchia di dati e' quello di "oggetto" (Object

All'idea di lista possono dunque essere associati due insiemi di operazioni:

l'insieme di operazioni specifiche definite in precedenza;

l'insieme di operazioni definito per la categoria di dati piu' generali cui la lista appartiene

in Java al tipo Object e' associata, tra le altre, l'operazione toString() che restituisce una rappresentazione in forma di stringa dell'oggetto

Ulteriori operazioni collegate alle liste possono ad esempio essere predicati che determinano se un oggetto di una classe piu' ampia delle liste e' una lista o meno:

Il problema della genericita'

Il concetto di lista e l'insieme delle operazioni primitive sulle liste non sono in alcun modo correlate con il tipo degli elementi della lista. Purtroppo pero', molti linguaggi di programmazione, tra cui il C, costringono a specificare nella definizione del tipo lista la categoria (unica) di enti che la costituiscono.

In C e' dunque impossibile realizzare il concetto di lista astraendo completamente dal tipo di elementi che la compongono. Per questo motivo sostituiremo nel seguito al tipo lista il tipo listInt, nella ipotesi di fare riferimento ad una lista di interi.

In tal caso, se in uno stesso programma risultasse necessario manipolare liste di altri tipi di dato, come ad esempio persone, studenti, veicoli, etc, il progettista software si troverebbe costretto a duplicare il codice che realizza le liste soltanto per modificare il tipo degli elementi memorizzati.

Indipendenza dalla rappresentazione

L'information hinding costituisce un concetto complementare all'astrazione.

Mentre l'astrazione si focalizza sul funzionamento osservabile di un oggetto e su cosa fa un oggetto, l'incapsulamento si focalizza sull'implementazione e permette di modificare un sistema software con uno sforzo limitato. Qualunque sia l'implementazione scelta per una nuova categoria di dati, essa e' inessenziale agli occhi dei clienti, una volta che assicuri il rispetto del contratto tra il cliente e un oggetto di quella categoria stabilito dall'interfaccia.

L'indipendenza dalla rappresentazione e' la proprieta' per cui la rappresentazione concreta di un dato puo' essere modificata senza che vi siano ripercussioni sul resto del programma.

L'insieme delle primitive sulle liste permette di definire ogni altra operazione in modo indipendente dalla rappresentazione:

Files come moduli

Il modulo e' un costrutto linguistico che permette di raggruppare dati, funzioni e procedure in una singola unita' sintattica e che permette l'incapsulamento dell'informazione.

Attraverso l'uso di un modulo e' possibile costruire una barriera di astrazione intorno alla rappresentazione concreta di una struttura di dati. Se ben definito, un modulo ha la possibilita' di:

garantire l'uso consistente e corretto di una nuova astrazione di dato, cioe' il soddisfacimento di invarianti di dato;

ottenere indipendenza dalla rappresentazione.

Non disponendo di alcun costrutto linguistico per organizzare i programmi in moduli, i programmatori C sfruttano i files e alcune direttive al compilatore per ripartire il codice sorgente in contenitori separati, al fine di agevolare il riuso del software.

Il file list.h

I file di estensione .h (file header) sono usati per conenere dichiarazioni di tipi e di operazioni.

/* file list.h */

#ifndef LIST_H

#define LIST_H

typedef enum boolean;

/* Liste: rappresentazione */

typedef struct listItemlistItem;   //nome del tipo

#define emptyList NULL

typedef listItem* listInt;

/* Liste: prototipi delle operazioni primitive */

listInt cons( int el, listInt l1); //---->

int head( listInt l1); //---->

listInt tail( listInt l1); //---->

boolean null( listInt l1); //---->

/* Liste: prototipi delle operazioni utili     */

void writeListInFile( listInt l1, FILE* fp);

/* scrive la lista l1 sul file fp */

listInt readListFromFile( FILE* fp);

/* restituisce una lista leggendone i valori dal file fp */

listInt ordInsert ( listInt l1, int el );

/* data una lista ordinata l1 restituisce una lista odinata che contiene gli elementi di l1 piu' el */

int posElInList( listInt l1, int el );

/* restituisce la prima posizione dell'elemento el nella lista data se el non compare nella lista restituisce 0 */

void removeFromList( listInt* l1, int el );

/* data una lista l1, restituisce una lista ottenuta rimuovendo da l1 tutte le occorrenze di el */

#endif

Il file list.c

Questo file e' destinato a contenere l'implementazione delle primitive.

/* file list.c */

#include <stdio.h>

#include <stdlib.h>     //per malloc

/* Liste:   implementqazione delle operazioni primitive */

boolean null( listInt l1)

listInt cons( int el, listInt l1)

t-> next = l1;

t-> val = el;

return t;

int head( listInt l1)

return l1-> val;

listInt tail( listInt l1)

return l1-> next;

/* Liste: operazioni di alto livello   */

void writeListInFile( listInt l1, FILE* fp)

fclose( fp );

listInt readListFromFile( FILE* fp)

listInt ordInsert ( listInt l1, int el );

int posElInList( listInt l1, int el );

if (head(l1) == el ) return k; else return 0;

void removeFromList( listInt* l1, int el )

Analisi della soluzione

Questa realizzazione delle liste, traendo ispirazione dal Lisp, non prevede alcuna operazione per modificare una lista. Le "mosse" disponibili permettono solo di utilizzare una lista o i componenti di una lista per costruirne altre.

Inoltre, mentre ogni invocazione alla operazione cons provoca l'allocazione (via malloc) di un blocco di memoria nell'heap, non vi e' alcuna operazione che restituisce all'heap blocchi non piu' utilizzati.

D'altra parte, il modo in cui e' realizzata l'operazione cons provoca la nascita di strutture condivise che rendono problematico e delicato l'uso dell'operazione free per liberare memoria. Infatti la lista tarsferita a cons come secondo argomento viene collegata direttamente (senza farne copia) alla nuova struttura creata.

La soluzione prospettata sarebbe pienamente soddisfacente solo in presenza di un garbage collector, cioe' di una componente software che determina in modo autonomo le strutture dati non piu' utilizzate da un programma, restituendo alla memoria i blocchi da loro occupati. Poiche' il linguaggio C non supporta garbage collector, la liberazione della memoria deve essere effettuata dal programma. Una possibile tecnica e' quella di dotare ciascun listItem di un campo countRef (contatore di riferimenti) che andrebbe cosi' gestito:

Il trasferimento di una lista l1 al parametro formale di una funzione implica l'incremento di uno il countRef del primo blocco (se esiste) della lista l1 e il suo decremento al termine della funzione.

Quando il countRef di un dato listItem assume il valore 0, quel listItem puo' essere deallocato.

Qui di seguito si riporta la definizione di altre operazioni: per renderle disponibili occorre inserirne le signature nel file list.h.

/* Liste: operazioni utili   */

int lenList( listInt l1 );

return k;

void shiftList( listInt* l1, int pos);

while( (i < pos) )

/* l1 punta all'item di posizione pos */

if( null(pred) ) (*l1) = t-> next;

else pred->next = t->next;

void readList( listInt* l1 )while( x != 0 );

listInt readBuildList()while( x != 0 );

return l1;

void showList( listInt l1)

printf(" | \n");

void writeList( listInt l1)

listInt removeEldaList( listInt l1, int el )

else return l1;

Il file main.c

/* chiamate */

void testOp()

void testRicerca()while( x != 0 );

readln();

void testOrdInsert()while( x != 0 );

readln();

showList( l1 );

void testRemove() ");

while( !null( l1 ) )

void testShift()while( x != 0 );

readln();

void testRWSuFile()

if( (fp = fopen("listInt.dat","rb")) == NULL )

puts("errore in apertura del file");

else

}//testRWSuFile

void effettiCollaterali()

void execute( char v )

void messaggi();

void main()while( !eof );

puts("fine del procedimento");

Verso liste generiche

Se in uno stesso programma risultasse necessario manipolare liste di vari tipi di dato, come ad esempio interi, persone, studenti, veicoli, etc, il progettista software si troverebbe costretto a duplicare il codice che realizza le liste soltanto per modificare il tipo degli elementi memorizzati.