Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

Liste - Argomenti, Le liste come astrazioni di dato

informatica




Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a WhatsApp - corso di

Liste

Argomenti

Progetto e realizzazione di astrazioni di dato

Le liste come astrazioni di dato

Operazioni primitive e non
Il legame tra strutture e operazioni

Operazioni sulle liste



Classificazione dei dati

Una possibile classificazione

Indipendenza dalla rappresentazione

Indipendenza dalla rappresentazione

Problemi di typing

Il problema della genericita'

Organizzazione modulare dei programmi:
Interfacce e implementazione

Files come moduli
Il file listInt.h
Il file listInt.c
Il file main.c

Approcci generativi: vantaggi e limiti
Structure sharing vs structure copying

Analisi della soluzione

Strutture di dati generiche

Verso liste generiche

Operazioni

inserzione ordinata

listInt ordInsert ( listInt l1, int el )

prima posizione di un elemento

int posElInList( listInt l1, int el )

eliminazione di un elemento

listInt removeEldaList( listInt l1, int el )


void removeFromList( listInt* l1, int el )


lettura di una lista

void readList( listInt* l1 )


listInt readBuildList()


void writeListInFile( listInt l1, FILE* fp)

stampa di una lista

void showList( listInt l1)


void writeList( listInt l1)


listInt readListFromFile( FILE* fp)

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

Costruttori

cons: elType,lista -> lista

Dato un elemento el e una lista l1, restituisce la lista che ha come primo elemento el e come resto la lista l1

Selettori

car: lista -> elType     oppure: head: lista -> elType

Data una lista l1, restituisce il primo elemento. Se la lista data e' vuota, provoca un errore a tempo di esecuzione.

cdr: lista->list             oppure: tail: lista-> list

Data una lista l1, restituisce la lista ottenuta escludendo da l1 il primo elemento. Se la lista data e' vuota, provoca un errore a tempo di esecuzione.

Predicati

isNull: lista->boolean  oppure: null: lista->boolean

Restituisce true se la lista data e' vuota, false altrimenti.

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:

isAtom: dato-> boolean

restituisce false nel caso l'argomento di ingresso sia una lista

isList: dato->boolean

restituisce true nel caso l'argomento di ingresso sia una lista

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:

cons

pone a 1 il countRef del nuovo blocco creato ed incrementa di uno il countRef del primo blocco della lista che costituisc ela coda (tail).

assgnamento

l1 = l2

incrementa di uno il countRef del primo blocco (se esiste) della lista l2
decrementa di 1 il countRef del primo blocco (se esiste) della lista
l1

assgnamento

l1 = tail(l2)       



incrementa di uno il countRef del secondo blocco (se esiste) della lista l2
decrementa di 1 il countRef del primo blocco (se esiste) della lista
l1

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.







Privacy




Articolo informazione


Hits: 1219
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2021