Le strutture dati dinamiche
•
•
•
•
La gestione statica della memoria -o a pila quando si usa
la ricorsione- è molto efficiente ma non è priva di
inconvenienti:
Soprattutto è rigida rispetto a informazioni la cui
dimensione non è nota a priori o è destinata a variare
durante l’esecuzione
Caso tipico: tabella di elementi vari: può essere vuota, vi
si possono inserire o cancellare elementi, ecc.
Per gestirla mediante array occorre prevedere una
dimensione massima, con rischio di
– spreco
– overflow
•
Per questo motivo alcuni linguaggi permettono tipi di
dato dinamici:
– Una tabella -o lista- può essere vuota, oppure può essere il
risultato di aggiungere un elemento ad una lista esistente
– si noti la struttura ricorsiva della definizione del tipo di dato
– Un valore di un tipo di dato definito in questa maniera
occupa una quantità di memoria non nota a compile time
– Per questo motivo i linguaggi tradizionali non li permettono
– Permettono però una -parziale- gestione dinamica della
memoria ottenendo strutture dati -rigorosamente parlando,
non tipi di dati- dinamiche
– Il risultato è ottenuto sfruttando i puntatori, ma non è privo
di rischi: se ne raccomanda un uso molto disciplinato!!
•
Per arrivare al risultato finale -la “simulazione” di tipi
astratti dinamici- il cammino è un po’ lunghetto
• Le operazioni di allocazione e cancellazione di
memoria
•
La chiamata di funzione
•
malloc(sizeof(TipoDato));
•
crea in memoria una variabile di tipo TipoDato, e restituisce
come risultato l’indirizzo della variabile creata (più
precisamente, il valore restituito è l’indirizzo del primo byte
riservato alla variabile).
•
Se P è una variabile di tipo puntatore a TipoDato, l’istruzione
•
P = malloc(sizeof(TipoDato));
•
assegna l’indirizzo restituito dalla funzione malloc a P. Di
conseguenza, dopo l’esecuzione di questa istruzione P “punta”
alla nuova variabile perdendo il suo valore originario.
NB1: la memoria viene allocata per un dato di tipo TipoDato,
non per P, che invece è una variabile già esistente.
NB2: In C una variabile creata dinamicamente è
necessariamente “anonima”: a essa si può fare riferimento solo
tramite puntatore; una variabile dichiarata mediante un proprio
identificatore può invece essere indicata tramite l’identificatore
stesso ma può anche essere puntata.
Un puntatore si comporta come una normale variabile
identificata (esso può essere indicato mediante identificatore o
puntato da un altro puntatore).
•
•
•
•
•
•
•
•
Simmetricamente,
free(P)
rilascia lo spazio di memoria puntato da P; ciò significa che la
corrispondente memoria fisica è resa nuovamente disponibile
per qualsiasi altro uso.
NB: free deve ricevere un puntatore al quale era stato assegnato
come valore l’indirizzo restituito da una funzione di allocazione
dinamica di memoria (malloc, nel nostro caso).
L’uso delle funzioni malloc e free richiede l’inclusione del file
header <stdlib.h> tramite l’istruzione
•
#include <stdlib.h>
•
Siccome però malloc e free possono essere chiamate in
qualsiasi momento (non si segue più la disciplina LIFO tipica
della stack), la gestione della memoria si complica:
int
*Punt1;
int
**Punt2;
•
•
...
Punt1
Punt2
Record di
attivazione di
Proc
5
3
...
Stack
Heap
•
Rischi della gestione dinamica della memoria
• produzione di
garbage (“spazzatura”): la memoria allocata
dinamicamente risulta logicamente inaccessibile perché non
esiste più alcun riferimento a essa:
•
•
P = malloc(sizeof(TipoDato));
P = Q;
•
“riferimenti fluttuanti” (dangling references). (simmetrico
rispetto al precedente): riferimenti fasulli a zone di memoria
logicamente inesistenti:
•
•
P = Q;
free(Q);
•
Esempio: P puntatore a int e la cella potrebbe ricevere un
valore di tipo char.
Un riferimento a *P comporterebbe l’accesso all’indirizzo fisico
puntato da P e l’interpretazione del suo contenuto come un
valore intero con risultati imprevedibili ma non facilmente
individuabili come errati.
garbage e dangling references chiaramente simmetrici, ma la
seconda è più pericolosa.
In alcuni linguaggi si accetta la prima per evitare il rischio della
seconda: eliminazione dell’istruzione free.
Viene lasciato alla macchina astratta del linguaggio l’onere di
effettuare garbage collection
Morale: puntatori tecnica di programmazione di basso livello.
Se ne raccomanda l’uso esclusivamente finalizzato alla
costruzione di “pseudotipi astratti dinamici” come illustrato in
seguito
•
•
•
•
•
•
La costruzione e la gestione della struttura dinamica
(pseudotipo astratto) lista mediante puntatori
•
L’idea base:
Ultimo
elemento
Lista
e1
e2
en
•
Invece di dichiarare il tipo lista …
•
si dichiarano i suoi elementi:
•
•
•
•
struct EL
•
typedef
struct EL
ElemLista;
•
typedef
ElemLista
*ListaDiElem;
•
Sintassi un po’ nuova:
– la prima dichiarazione del tipo strutturato struct EL
definisce un primo campo, Info, del tipo TipoElemento e
permette di dichiarare il campo Prox come puntatore al tipo
strutturato che si sta definendo;
– la seconda dichiarazione utilizza typedef per rinominare
il tipo struct EL come ElemLista;
– la terza dichiarazione definisce il tipo ListaDiElem come
puntatore al tipo ElemLista.
{
TipoElemento
struct EL
};
Info;
*Prox;
•
A questo punto si può procedere come al solito per definire
variabili “di tipo lista”:
•
ListaDiElem
•
dichiarazioni abbreviate:
•
•
ElemLista
*Lista1;
se non interessa mettere in evidenza il tipo della lista.
•
•
struct EL
*Lista1
può sostituire entrambe le typedef se non è necessario
nominare esplicitamente né il tipo della lista né il tipo dei suoi
elementi.
•
•
Ricordiamo che:
un tipo di dato è individuato da un insieme di valori e da un
insieme di operazioni.
Vediamo dunque alcune fondamentali operazioni per la gestione
di liste così realizzate.
•
Lista1, Lista2, Lista3;
•
Inizializzazione
•
assegna il valore NULL alla variabile “testa della lista”:
l’operazione:
Inizializza (Lista)
produce perciò l’effetto indicato in figura:
•
Lista
•
•
Se però vogliamo eseguire l’operazione in maniera
parametrica su una lista generica occorre che il parametro
sia passato “per indirizzo”.
Avremo perciò a che fare con un doppio puntatore:
– il puntatore che realizza il parametro formale puntando alla
lista che costituisce il parametro attuale
– il puntatore che realizza la testa della lista
•
Applicando perciò la tipica tecnica di realizzazione del
passaggio parametri per indirizzo in C otteniamo il codice
seguente
•
#include <stdlib.h>
•
void Inizializza (ListaDiElem *Lista)
• /* Lista è la variabile locale che punta alla "testa di lista". La
funzione assegna alla “testa di lista" il valore NULL
corrispondente al valore di lista vuota */
• {
•
*Lista = NULL;
• }
•
•
•
La chiamata:
Inizializza(&Lista1);
produce l’esecuzione seguente:
Lista
Lista1
Al termine dell’esecuzione il parametro formale Lista viene
eliminato e rimane l’effetto voluto (inizializzazione
mediante il valore NULL sul parametro attuale Lista1)
•
NB: lo stesso effetto si sarebbe potuto ottenere dichiarando
l’header della procedura come segue:
•
void
•
La complicazione del passaggio per indirizzo in C -tramite
puntatori- ha indotto una cattiva prassi nel “gergo della
programmazione C” (anche nei libri!): evitare l’uso di parametri
-soprattutto se da passare per indirizzo- e sostituirlo con l’abuso
delle variabili globali
•
#include <stdlib.h>
•
ElemLista
•
•
•
•
void Inizializza(void)
{
Lista1 = NULL;
}
•
Si raccomanda di evitare questa prassi.
Inizializza(ElemLista **Lista)
*Lista1;
• Controllo di lista vuota
•
•
•
•
boolean
ListaVuota(ListaDiElem Lista)
• /* Produce il valore true se la lista passata come
parametro è vuota, false in caso contrario, a Lista viene
passato il valore contenuto nella variabile testa di lista.
Lista punta pertanto al primo elemento della lista
considerata */
{
if (Lista == NULL) return true; else return false;
}
•
•
chiamata:
ListaVuota(Lista1)
• Ricerca di un elemento in una lista
•
•
•
boolean Ricerca (ListaDiElem Lista,
TipoElemento ElemCercato)
{
ElemLista *Cursore;
•
•
•
•
•
•
•
•
•
•
•
if (Lista != NULL)
{
Cursore = Lista;
/* La lista non è vuota */
while (Cursore != NULL)
{
if (Cursore–>Info == ElemCercato) return true;
Cursore = Cursore–>Prox;
• /* In questa maniera Cursore viene fatto puntare
all'elemento successivo della lista */
}
}
return false;
}
• Versione ricorsiva della ricerca di un elemento in
una lista
•
•
•
•
•
•
•
•
•
•
boolean Ricerca (ListaDiElem Lista,
TipoElemento
ElemCercato)
{
if (Lista == NULL)
return false;
else
if (Lista–>Info == ElemCercato)
return true;
else
return Ricerca(Lista–>Prox, ElemCercato);
}
• Estrazione della testa o della coda da una lista
•

•
(senza codice).
TipoElemento
TestaLista(ListaDiElem Lista)
 /* È applicabile solo a liste non vuote. Se la lista è vuota
segnala l'errore in modo opportuno; in caso contrario
produce come risultato il valore del campo Info del primo
elemento della lista */
ListaDiElem
CodaLista(ListaDiElem Lista)
• /*Produce come risultato un puntatore alla sottolista
ottenuta da Lista cancellandone il primo elemento. Essa
non deve modificare il parametro originario. Anche questa
assume l'ipotesi che il parametro passatole sia una lista
non vuota */
CodaLista
Ultimo
elemento
Lista
e1
e2
en
•
•
Inserimento di un nuovo elemento in testa alla lista:
Si fa uso di un puntatore locale: Punt;
Punt
Lista
e1
e2
en
Si crea un nuovo elemento puntato da Punt e vi si inserisce il
valore desiderato
Punt = malloc(sizeof(ElemLista));
Punt–>Info = Elem;
Punt
Elem
Lista
e1
e2
en
Infine si collega il nuovo elemento al precedente primo
elemento della lista e la testa della lista viene fatta puntare al
nuovo elemento:
Punt
Elem
Lista
e1
e2
en
Come in precedenza dobbiamo però costruire un codice
parametrico rispetto alla lista in cui inserire il nuovo elemento
attraverso il passaggio parametri per indirizzo:
•
void
•
•
{
•
•
•
•
•
InsercisciInTesta(ListaDiElem *Lista,
TipoElemento Elem)
ElemLista *Punt;
• /* Allocazione dello spazio necessario per la
memorizzazione del nuovo elemento e inizializzazione del
puntatore */
Punt = malloc(sizeof(ElemLista));
Punt–>Info = Elem;
Punt–>Prox = *Lista;
*Lista = Punt;
}
Lista
Punt
e1
e2
en
Lista1
Punt
Lista
Elem
e1
e2
en
Lista1
Lista
Punt
Elem
e1
Lista1
e2
en
•
void
•
•
•
•
•
•
•
•
•
•
•
{
InserisciInCoda(ListaDiElem *Lista,
TipoElemento Elem);
ElemLista *Punt;
if (ListaVuota(*Lista))
{
Punt = malloc(sizeof(ElemLista));
Punt–>Prox = NULL;
Punt–>Info = Elem;
*Lista = Punt;
}
else InserisciIncoda(&((*Lista)–>Prox), Elem);
}
Esaminiamo con attenzione l’esecuzione delle varie chiamate
ricorsive della procedura applicata a un parametro attuale
Lista1 di n elementi
Lista*1
Lista*2
e1
Lista*3
e2
Lista*n
Lista*n+1
en-1
en
Lista*n+1
Punt
Lista1
Lista*1
Lista*2
e1
Lista*3
e2
en-1
Elem
en
Lista1
Lista*1
Lista*2
e1
Lista1
Lista*3
e2
Lista*n+1 Punt
en-1
en
Elem
• void InserisciInOrdine(ListaDiElem *Lista, TipoElemento Elem)
•{
• ElemLista *Punt, *PuntCorrente, *PuntPrecedente;
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•}
PuntPrecedente = NULL;
PuntCorrente = *Lista;
while (PuntCorrente != NULL && Elem > PuntCorrente–>Info)
{
PuntPrecedente = PuntCorrente;
PuntCorrente = PuntCorrente->Prox;
}
Punt = malloc(sizeof(ElemLista));
Punt–>Info = Elem;
Punt–>Prox = PuntCorrente;
if (PuntPrecedente) != NULL
PuntPrecedente–>Prox = Punt;
• /* Inserisci internamente alla lista */
else
*Lista = Punt;
• /* Inserisci in testa alla lista */
Punt
Lista
Elem
e1
ek
ek+1
en
Lista1
PuntPrecedente
PuntCorrente
Punt
Elem
Lista
e1
ek
ek+1
Lista1
PuntPrecedente
PuntCorrente
en
Cancellazione di un elemento da una lista
void
Cancella(ListaDiElem *Lista, TipoElemento Elem)
/* Cancella dalla lista passata "per indirizzo" l'elemento Elem, se
esiste, assumendo che nella lista non vi siano ripetizioni */
{
ElemLista *PuntTemp;
if (ListaVuota (*Lista) == false)
if ((*Lista)–>Info == Elem)
{
PuntTemp = *Lista;
*Lista = CodaLista(*Lista);
free(PuntTemp);
}
else Cancella(&((*Lista)–>Prox), Elem);
}
Riassumendo
•
•
•
•
•
•
•
•
Strutture dati dinamiche = “pseudotipi di dato astratti” dinamici
Realizzate mediante puntatori
Puntatori: struttura di basso livello ---> a rischio
(Puntatori: meccanismo tipico e “storico” del C: ponte tra
assembler e linguaggi di alto livello)
Raccomandazione: usare i puntatori solo all’interno delle
operazioni astratte associate alle relative strutture
Liste: primo e fondamentale -ma non unico!!- esempio di
struttura dinamica
Altri più complessi e potenti verranno visti in corsi successivi
Una prima valutazione -a spanne- dell’efficienza della struttura
dinamica lista rispetto all’array:
–
–
–
–
Si evita lo spreco di memoria/rischio di overflow (obiettivo iniziale)
A prezzo di un -lieve- aumento dovuto ai puntatori
Da un punto di vista del tempo necessario all’esecuzione degli
algoritmi: pro e contro (inserire in testa meglio, inserire in coda
peggio, … però la ricerca in una lista ordinata non si può fare con
algoritmi del tipo della ricerca in un vocabolario …
il seguito alle prossime puntate (corsi).
Introduzione alla programmazione modulare
•
•
•
•
•
Ormai costruire un “sistema informatico” è impresa ben più
complessa -meglio, diversa- che “inventare” un algoritmo e
codificarlo.
Il problema della progettazione -e gestione- del SW va ben oltre
gli scopi di un corso di base ---> l’ingegneria del SW
E’ però concetto di base il principio della modularizzazione:
Ogni volta che un manufatto si rivela di dimensioni e
complessità difficili da dominare la cosa migliore per
affrontarne la costruzione è modularizzarlo: scomporlo in
sottoproblemi, affrontare questi separatamente, indi ricomporre
le soluzioni parziali in una soluzione globale
Meccanismi di supporto alla modularizzazione sono già entrati
in gioco:
–
–
•
Essi non sono però totalmente adeguati alle esigenze sempre
maggiori di costruzione di sistemi sempre più complessi:
–
–
•
la tipizzazione
i sottoprogrammi
principalmente essi hanno senso solo nel contesto del programma
cui appartengono -anche se con sfumature diverse da linguaggio a
linguaggio
un sistema informatico invece è cosa ben più ampia rispetto al
concetto di programma
Occorre dunque almeno gettare le basi della programmazione
modulare -detta anche programmazione in grande, in
contrapposizione alla programmazione in piccolo.
•
•
•
Un sistema software è costituito da un insieme di moduli e da
relazioni intercorrenti tra i vari moduli.
Ogni modulo è costituito da una interfaccia e da un corpo.
– L’interfaccia di un modulo, detta anche definizione di un
modulo, è l’insieme di tutti e soli i suoi elementi che
devono essere conosciuti da chi usa il modulo per farne un
uso appropriato.Tali elementi vengono anche chiamati
risorse esportate dal modulo.
– L’implementazione di un modulo, detta anche corpo di un
modulo, è l’insieme dei meccanismi che permettono di
realizzare le funzionalità, ossia i compiti, che il modulo
stesso deve garantire al resto del sistema.
Due importanti relazioni tra moduli:
–
–
La relazione di importazione / esportazione. Diciamo che un
modulo M importa una risorsa dal modulo M’ quando esso la usa.
Un modulo M può importare da un altro modulo M’ solo risorse
appartenenti all’interfaccia di M’. Quando non vengono precisate le
risorse importate da parte di M da M’, si dice semplicemente che M
usa M’.
La relazione è_composto_da. Si dice che un modulo M
è_composto_da un insieme di moduli {M1, M2, ..., Mk} se tale
insieme permette di realizzare tutte le funzionalità di M. Di
conseguenza si dice anche M1, M2, ..., Mk sono componenti di M.
Un esempio di architettura modulare
Module W
A
Module Y
Module X
Module L Module
R
T
B
C
Module Z
•
Criteri di buona modularizzazione
•
Principio di information hiding (occultamento delle
informazioni)
– In generale, meno informazioni sono rese note
all’utilizzatore di un modulo, meno condizionamenti
vengono posti al suo implementatore e maggiore sicurezza
si ha nel suo uso.
– Ovviamente, al contrario, non bisogna dimenticare di
definire nell’interfaccia tutte le informazioni di rilievo,
evitando che l’utente del modulo sia costretto a esaminarne
l’implementazione.
Principio di low coupling and high cohesion (basso
accoppiamento e alta coesione)
E’ bene che variabili, procedure e altri elementi spesso utilizzati
congiuntamente siano raggruppati nello stesso modulo dando ad
ogni modulo un alto livello di coesione interna, mentre altri
elementi che raramente interagiscono tra loro possono essere
allocati nelle interfacce di moduli diversi, ottenendo così moduli
con un basso livello di accoppiamento.
•
•
•
Principio di design-for-change (progetto in funzione del
cambiamento)
•
Un esempio molto semplice ed efficace di design-for-change è
già stato visto nell’ambito della programmazione in piccolo:
l’uso delle costanti. La dichiarazione della costante PiGreco, ad
esempio, cosituisce la cornice che racchiude il possibile
cambiamento del suo valore dovuto a nuove assunzioni.
Un altro tipico esempio di cambiamento prevedibile è quello
dell’hardware destinato all’esecuzione di un certo software. E’
perciò utile,costruire un modulo DriverDiPeriferica.
•
•
•
•
•
Progettazione top-down e bottom-up
La modularizzazione si accoppia molto bene con il
metodo dei raffinamenti successivi (già visto fin dagli
inizi)
Questo metodo può “sposarsi” con criteri di buona
modularizzazione in varie maniere (i principi generali
hanno un’enormità di sfumature nella loro realizzazione per fortuna e purtroppo …)
Senza entrare in tecniche specifiche:
– Progettazione top-down (centrata sul problema):
– Si parte da una visione -modulo- globale e lo si raffina scompone- fino ad ottenere moduli elementari.
– Progettazione bottom-up (centrata sul riuso dell’esistente e
quindi più in auge in tempi moderni):
– si aggregano moduli -esistenti o nuovi- fino ad ottenere il
sistema voluto
•
•
Definizione e implementazione di moduli
(per il momento lasciamo perdere il C … o almeno
lasciamolo un po’ in disparte)
•
Un programma consiste in un gruppo di moduli: un modulo
principale detto modulo-programma (o modulo master) e
alcuni moduli detti moduli-asserviti (o moduli slave). Il
modulo-programma usa altri moduli, che, loro volta, possono
usarne altri ancora.
Per motivi che qui non intendiamo approfondire, sono vietate le
“circolarità” nella relazione usa.
Ogni modulo, che non sia un modulo-programma, è costituito
da, e deve chiaramente separare, le sue due parti:
•
•
–
–
l’interfaccia,
l’implementazione.
Program
module
(main
module)
Service
module
M1
Service
module
M3
Service
module
M2
Service
module
M4
•
•
Interfaccia del modulo
L’interfaccia di un modulo è composta dai seguenti
elementi:
– L’identificatore del modulo. Facciamo precedere
l’identificatore dalla ‘pseudo parola chiave’ module
interface.
–
•
•
•
•
•
•
•
•
•
•
La clausola import, che lista tutte le entità importate da altri
moduli e il rispettivo modulo sorgente:
import
A, B, ...
from
import
X, Y ...
from
import
Alpha, Beta, ...
from
import
Zed, W,...
from
M1;
M2;
M3;
M4;
La clausola export , che lista tutte le entità esportate dal
modulo.
Ad esempio, se l’interfaccia di un modulo MD dichiara un tipo T
e un altro modulo M1 importa T da MD, allora M1 può
dichiarare variabili di tipo T come se T fosse stato dichiarato in
M1 stesso.
– Il modulo principale è l’unico infatti che importa elementi
ma non ne esporta.
Importanza dei commenti nell’interfaccia di un modulo. Il
commento a un prototipo di una funzione, per esempio, può
indicare, nel modo più preciso possibile, l’effetto della funzione.
Nell’interfaccia di un modulo la dichiarazione di un tipo può
non precisare la struttura del tipo stesso. Il tipo così definito si
dice opaco e la sua struttura risulta nascosta:
Typedef [hidden] Type1;
• Un primo esempio: il tipo astratto numeri complessi
•
•
•
•
•
•
•
•
[module interface] ComplexNumbers
[import scanf, printf from stdio]
• /*segue la lista degli elementi esportati*/
{
typedef [hidden] Complex;
• /*E’ l’insieme dei numeri complessi, ben noto in
matematica. Si noti il fatto che questo tipo è opaco:
se ne riscontrerà l’importanza tra poco.*/
typedef enum {RPIP, MODARG} Representation;
• /*indica il modo di rappresentare all’esterno un
numero compless.: RPIP: “parte reale, parte
immaginaria”; MODARG: “modulo, argomento”. Ciò
permetterà all’utente di scegliere la scrittura di un
dato di tipo complesso nella forma preferita senza
per questo condizionare la rappresentazione interna
dei dati,.*/
Complex SumCompl(Complex Add1, Complex
Add2);
• /*esegue la somma tra i due parametri complessi
Add1 e Add2. Non produce side-effect.*/
Complex MultCompl(Complex Mult1, Complex
Mult2);
• /*esegue il prodotto tra i due parametri complessi
Mult1 e Mult2. Non produce side-effect.*/
...
• /*altre operazioni aritmetiche eseguibili su numeri
complessi.*/
•
•
•
void WriteCompl(Complex Par1, Representation
Rep);
• /*stampa sul file stdout il valore complesso
passatole come primo parametro. Il formato
di stampa varia al variare del valore del
secondo parametro.*/
void ReadCompl(Complex *Par, Representation
Rep);
/*legge dal file stdin un valore complesso,
memorizzandolo nella variabile indicata come primo
parametro – passato necessariamente per indirizzo.
La procedura interagisce con l’utente chiedendogli
di immettere i dati in forma diversa a seconda del
valore del secondo parametro.*/
•
Prima implementazione (parte reale e parte
immaginaria)
•
•
•
[module implementation] ComplexNumbers
[import scanf, printf
from stdio
import sin, cos, asin, acos, pow, sqrt from
math]
{
typedef struct {
float RealPart;
float ImaginaryPart;
} Complex;
•
•
•
•
•
•
•
•
•
•
•
Complex SumCompl(Complex Add1, Complex
Add2)
{
Complex Result;
Result.RealPart = Add1.RealPart +
Add2.RealPart;
Result.ImaginaryPart = Add1.ImaginaryPart +
Add2.ImaginaryPart;
return Result;
}
•
•
•
•
•
•
•
•
•
•
•
Complex MultCompl(Complex Mult1, Complex
Mult2)
{
Complex Result;
Result.RealPart =
Mult1.RealPart * Mult2.RealPart Mult1.ImaginaryPart *
Mult2.ImaginaryPart;
Result.ImaginaryPart =
Mult1.ImaginaryPart * Mult2.RealPart +
Mult2.ImaginaryPart * Mult1.RealPart;
return Result;
}
•
...
• /*implementazione delle altre operazioni aritmetiche sui
numeri complessi*/
•
•
•
•
•
•
•
•
•
•
•
•
•
void WriteCompl(Complex Par, Representation Rep)
{
float Mod, Arg;
if (Rep == RPIP)
printf(“Parte Reale: %f, Parte Immaginaria: %f\n”,
Par.RealPart, Par.ImaginaryPart);
else
{
Mod = sqrt(pow(Par.RealPart, 2) +
pow(Par.ImaginaryPart, 2));
Arg = acos(Par.ImaginaryPart/Mod);
printf(“Modulo: %f, Argomento: %f\n”, Mod, Arg);
}
}
•
•
•
•
void ReadCompl(Complex *Par, Representation Rep)
….
}
….
•
Seconda implementazione (modulo e argomento)
•
•
•
•
•
•
•
•
•
•
•
[module implementation]
ComplexNumbers
[import scanf, printf
from stdio
import sin, cos, asin, acos, sqrt
from math]
{
typedef struct { float Modulus;
float
Argument;
} Complex;
Complex SumCompl(Complex Add1, Complex Add2)
{
Complex Result;
float RealPar1, RealPar2, ImPar1, ImPar2, RealParRes,
ImParRes;
•
•
•
•
•
•
•
RealPar1 = Add1.Modulus * cos(Add1.Argument);
RealPar2 = Add2.Modulus * cos(Add2.Argument);
ImPar1 = Add1.Modulus * sin(Add1.Argument);
ImPar2 = Add2.Modulus * sin(Add2.Argument);
RealParRes = RealPar1 + RealPar2;
ImParRes = ImPar1 + ImPar2;
Result.Modulus = sqrt(RealParRes * RealParRes +
ImParRes * ImParRes);
Result.Argument = acos(RealParRes/Result.Modulus);
return Result;
}
•
•
•
•
•
•
•
•
•
•
•
•
Complex MultCompl(Complex Mult1, Complex Mult2)
{
Complex Result;
Result.Modulus = Mult1.Modulus * Mult2.Modulus;
Result.Argument = Mult1.Argument + Mult2.Argument;
return Result;
}
...
• /*implementazione delle altre operazioni aritmetiche sui numeri
complessi*/
•
•
void WriteCompl(Complex Par, Representation Rep)
...
•
•
void ReadCompl(Complex *Par, Representation Rep)
...
}
•
Esaminiamo l’impatto dell’astrazione così ottenuta. L’istruzione:
– if (x.RealPar > 0) ...
•
è vietata: sarebbe accettabile per un’implementazione ma non per
l’altra. Se si vuole accedere alla parte reale di un numero complesso
occorre definire un’opportuna operazione nell’interfaccia.
•
Dal tipo di dato astratto al dato astratto
•
•
•
[module interface] NameTableManagement
[import printf
from stdio
import strcmp
from string]
•
•
•
{
#define MaxLen 20
#define MaxElem 1000
•
typedef char Name[MaxLen];
•
void Insert(Name NewElem);
• /*inserisce il parametro nella prima posizione libera di
NameTable, che è l’unica variabile globale su cui vengono
eseguite le varie operazioni e che viene esportata. Gli elementi
da inserire sono invece passati alla funzione da altri moduli, dai
quali essa è chiamata. Se la tabella è piena o se l’elemento da
inserire è già presente in tabella, stampa un opportuno
messaggio sul file stdout.*/
•
boolean Exist(Nam Elem);
• /*la funzione accede alla variabile globale NameTable e ritorna
il valore true se il parametro passato esiste nella tabella, false
in caso contrario.*/
•
Name DeleteReturnLast(void);
• /*elimina l’ultimo valore della tabella e lo produce come valore
risultato dell’operazione.*/
•
void Print(void);
• /*stampa il contenuto della tabella, un nome per ogni riga.*/
…
}
•
•
•
•
•
•
•
•
[module implementation] NameTableManagement
[import printf
from stdio
import strcmp
from string]
{
#define MaxLen 20
#define MaxElem 1000
•
•
•
•
•
typedef char Name[MaxLen];
typedef Name ContentType[MaxElem];
typedef struct { int
NumElem = 0;
ContentType Contents;
} TableType;
•
TableType
NameTable;
•void Insert(Name NewElem)
•{
•int
Count;
•boolean Found;
•if (NameTable.NumElem == MaxElem)
•
printf(“La tabella è già piena”);
•else
/*si verifica se l’elemento da inserire esiste già*/
•{
•
Found = false;
•
for (Count = 0; Count < NumElem; Count++)
•
if (strcmp(NameTable.Contents[Count], NewElem) == 0)
•
Found = true;
•
if (Found == true)
•
printf(“L’elemento da inserire è già in tabella”);
•
else
•
{
•
strcpy(NameTable.Contents[NameTable.NumElem], NewElem);
•
NameTable.NumElem = NameTable.NumElem + 1;
•
}
•
}
• }
•boolean Exist(Name Elem)
•
...
•Name DeleteReturnLast (void)
•
...
•void Print (void)
•
...
•}
•
Dallo pseudo C al C
•
Il C -un po’ vecchiotto- non ha costrutti espliciti per la scrittura di
interfaccia e implementazione di moduli.
Contano però più i concetti che le peculiarità di un linguaggio:
Con un po’ di metodo si può ottenere una buona modularizzazione
anche in C adattando e “approssimando” i meccanismi ideali a quelli
offerti dal C
Un programma C è articolabile e distribuibile su più file. E’ possibile
quindi creare programmi C composti da un modulo-programma,
contenuto in un file, e da più moduli asserviti contenuti ciascuno in
uno o più file separati.
I moduli asserviti possono poi essere ulteriormente suddivisi in
interfaccia e implementazione. L’interfaccia può essere contenuta in
un file avente nome uguale al nome del modulo ed estensione .h
mentre l’implementazione potrà essere contenuta in un file avente
nome uguale al nome del modulo ed estensione .c.
La direttiva #include viene utilizzata per indicare la clausola di
importazione anche se il suo effetto non è esattamente lo stesso: non
consente di precisare quali elementi sono importati
Constatiamo quindi che in realtà abbiamo scritto programmi modulari
in C fin dal primo programma eseguibile (#include stdio.h)
modulo stack contiene la dichiarazione del tipo pila e le operazioni
su di esso definite. Il file stack.h contiene la dichiarazione del tipo e i
prototipi delle funzioni.
...
•
•
•
•
•
•
•
•
•
La realizzazione della gestione tabella nomi in C
•
•
•
**************************************************
Parti rilevanti del file gtab.h
******************************************************************
•
•
•
•
#include <stdio.h>
#include <string.h>
#define MaxLen 20
#define MaxElem 1000
•
typedef char Name[MaxLen];
•
void
•
boolean Exist(Name Elem);
•
•
void
...
Insert(Name NewElem);
Print(void);
•
•
•
•
•
•
•
•
•
******************************************************************
Parti rilevanti del file gtab.c
******************************************************************
#include <gtab.h>
typedef Name ContentType[MaxElem];
typedef struct { int
NumElem;
ContentType
Contents;
} TableType;
static TableType NameTable;
• /*Variabili dichiarate come static all’interno di un file possono
essere manipolate quindi solo da funzioni dichiarate in quel
file*/
• void Insert(Name NewElem)
•{
• int
Count;
• boolean
Found;
• if (NameTable.NumElem == MaxElem)
•
printf(“La tabella è già piena”);
• else
•/*si verifica se l’elemento da inserire esiste già*/
• {
•
Found = false;
•
for (Count = 0; Count < NameTable.NumElem;
Count++)
•
if (strcmp(NameTable.Contents[Count],
NewElem) == 0)
•
Found = true;
•
if (Found == true)
•
printf(“L’elemento da inserire è già in tabella”)
•
else
•
{
strcpy(NameTable.Contents[NameTable.NumElem],
NewElem);
NameTable.NumElem = NameTable.NumElem + 1;
•
}
• }
•}
• ...
•
•
•
******************************************************************
Parti rilevanti del file gtmain.c
******************************************************************
•
#include <gtab.h>
•
Name NewName;
•
•
•
•
•
•
•
•
main()
{
...
Insert(NewName);
...
printf(“Il contenuto della tabella è il seguente:”);
Print();
}
La gestione dei file in C
•
Ricapitoliamo alcune caratteristiche fondamentali dei file
– il file è un’astrazione molto ampia nella descrizione di un
sistema informatico:
• “nastro” di I/O
• supporto di comunicazione macchina/ambiente di ogni
tipo (sensori, attuatori, ….)
• zona di memoria di massa
• …
– è un supporto di memoria -in senso lato- ma profondamente
diverso dalla memoria centrale -non solo da un punto di
vista tecnologico
– è uno snodo fondamentale di flussi di informazione anche
tra applicazioni diverse
– ciò implica che un file sia “visto” necessariamente da
diversi elementi della macchina (astratta):
• i programmi
• il file system (sistema operativo)
– difficile applicare ai file i concetti di tipo di dato che sono
in genere specifici dei singoli linguaggi
– nel conflitto tra linguaggi e sistema operativo sulle
competenze sui file finisce di solito con prevalere il SO --->
– la tendenza moderna è di non definire la struttura dei file
nei linguaggi di programmazione, lasciandola ad apposite
librerie -spesso system dependent.
– Il C, in un certo senso è un’eccezione in positivo, grazie
alla standard library.
– I file sono strutture sostanzialmente sequenziali, anche se,
quando è possibile, permettono un accesso diretto ai vari
record.
Flussi, file e programmi C
Un programma C che desidera utilizzare un file per operazioni di
memorizzazione permanente o di ingresso/uscita deve aprire un flusso di
comunicazione indicando al sistema operativo la sua intenzione di aprire
un file esistente o la necessità di creare e aprire un nuovo file. Al termine
dell’insieme di operazioni che coinvolgono quel file il flusso di
comunicazione viene chiuso chiudendo il file utilizzato.
NB: operazioni di input/output sono sia le operazioni che
coinvolgono un dispositivo di ingresso/uscita sia le operazioni di
memorizzazione permanente.
Per aprire un flusso un programma C deve dichiarare una variabile di
tipo puntatore e chiedere l’apertura del flusso tramite una funzione di
libreria (fopen).
L’apertura del flusso di comunicazione provoca l’assegnamento della
variabile puntatore (che serve al programma per far riferimento al file
corrispondente). La chiusura del flusso (tramite fclose) impedisce
ulteriori riferimenti al file.
Un flusso di comunicazione può essere
binario
(sequenza di byte)
o
di tipo testo
(sequenza di caratteri )
La variabile puntatore locale al programma creata dalla fopen punta a un
oggetto di tipo FILE capace di registrare tutte le informazioni necessarie a
controllare un flusso. Esso contienediversi campi:
modalità di utilizzo del file (lettura, scrittura o lettura e scrittura);
posizione corrente sul file (punta al prossimo byte da leggere o
scrivere sul file);
indicatore di errore;
indicatore di end-of-file (eof).
Ogni variabile che punta a un file deve essere definita come segue:
FILE
*fp;
Una “tabella file aperti”:
FILE
TabellaFileAperti[MaxNumFileGestibili];
è gestita dal SO (file system) e costituisce il “ponte” tra il programma e la
macchina astratta gestita dal SO.
File
Variabili puntatore
Tabella dei file aperti
StandardInput
stdin
stdout
nomefile:
modouso:
poscorr:
….
nomefile:
modouso:
poscorr:
….
stderr
f1
nomefile:
modouso:
poscorr:
….
nomefile: FileTre
modouso:
poscorr:
….
f2
nomefile: FileUno
modouso:
poscorr:
….
f3
nomefile: FileDue
modouso:
poscorr:
….
StandardInput
StandardError
FileUno
FileDue
FileTre
Tre flussi standard vengono automaticamente aperti quando inizia
l’esecuzione di un programma: stdin, stdout e stderr.
Normalmente questi tre flussi “rappresentano” il video del terminale
(stdout e stderr) o la tastiera del terminale (stdin).
printf e scanf utilizzano questi flussi standard.
Queste operazioni sono una parte delle
Operazioni di gestione dei file (dalla standard library)
FILE
*fopen(nomefile, modalità)
apre un file, eventualmente creandolo, e vi associa un flusso; restituisce
l’indirizzo della struttura di tipo FILE che descrive il file aperto; richiede in
ingresso il nome del file da aprire e la modalità di apertura :
“r” (lettura in modalità testo, posizionamento all’inizio del file),
“w” (scrittura in modalità testo, posizionamento all’inizio del file),
“a” (scrittura in modalità testo a partire dalla fine del file), “rb”, “wb” e
“ab” (lettura, scrittura e scrittura a fine file con modalità binaria), “r+”,
“w+”, “a+”, “rb+”, “wb+”, “ab+” (lettura e scrittura su file con modalità
di testo o modalità binaria).
Int
fclose(FILE
*fp)
chiude il file cui fa riferimento il puntatore fp; la chiusura comporta il
rilascio del descrittore di tipo FILE. Se l’operazione di chiusura viene
eseguita correttamente restituisce valore uguale a 0, altrimenti viene
restituito il valore particolare EOF (EOF è una costante definita in
stdio.h).
Int
remove(nomefile)
cancella il file identificato da nomefile. Restituisce 0 se l’operazione è
stata eseguita correttamente, un valore diverso da zero in caso
contrario. Se si cerca di cancellare un file aperto il comportamento
della funzione dipende dall’implementazione.
Int
rename(vecchionome, nuovonome)
modifica il nome di un file da vecchionome a nuovonome.
Restituisce 0 se...
Operazioni di gestione degli errori
int
ferror(FILE
*fp)
controlla se è stato commesso un errore nella precedente operazione di
lettura o scrittura. Restituisce 0 se nessun errore è stato commesso, un
valore diverso da 0 in caso contrario.
Int
feof(FILE
*fp)
controlla se è stata raggiunta la fine del file nella precedente operazione
di lettura o scrittura. Restituisce 0 se la condizione di fine file non è
stata raggiunta, un valore diverso da 0 in caso contrario.
void
clearerr(FILE
*fp)
riporta al valore di default i campi eof ed error della struttura che
descrive lo stato del file cui fa riferimento il puntatore fp.
Operazioni di lettura e scrittura
Le operazioni di lettura e scrittura su file possono essere effettuate in
quattro modi diversi:
•precisando il formato dei dati in ingresso e in uscita,
•accedendo ai dati carattere per carattere,
•linea per linea
•blocco per blocco.
Generalmente si adotta l’accesso linea per linea nel caso di flussi di testo
e l’accesso carattere per carattere o blocco per blocco in presenza di flussi
binari.
Lettura e scrittura formattata
Le funzioni fprintf e fscanf consentono operazioni formattate analoghe a
quelle di scanf e printf ma coinvolgono il file precisato dall’utente
tramite il puntatore fp. Restituiscono il numero degli elementi
effettivamente letti o stampati o restituiscono un numero negativo in caso
di errore:
int fprintf(FILE *fp, stringa di controllo, elementi)
int fscanf(FILE *fp, stringa di controllo, indirizzo elementi)
Lettura e scrittura di caratteri
Sei funzioni della standard library consentono la lettura e la scrittura di
caratteri su file. getchar legge da Standard Input il prossimo carattere
restituendolo come intero. putchar scrive come prossimo carattere sul file
di Standard Output il carattere che riceve come parametro restituendo il
carattere scritto. getc e fgetc leggono il prossimo carattere del file
specificato tra i parametri di ingresso restituendolo come intero. putc e
fputc scrivono come prossimo carattere del file il carattere specificato tra
i parametri di ingresso restituendolo come intero. Tutte le funzioni
restituiscono EOF in caso di errore: per verificare se si tratta di un caso di
fine file o di altro errore bisogna utilizzare feof o ferror. Le funzioni getc
e putc sono normalmente implementate in modo da risultare più veloci in
esecuzione ma presentano il rischio di effetti collaterali.
Il seguente programma legge e mostra sul video il contenuto del file
di tipo testo filechar:
#include <stdio.h>
/* Contiene la definizione di EOF, del tipo FILE
e le testate delle funzioni che operano su file */
#include <stddef.h>
/* Contiene la definizione di NULL */
main()
{
FILE
char
*fp;
c;
if ((fp = fopen("filechar", "r")) != NULL)
/* Il file viene aperto in lettura con modalità testo */
{
while ((c = fgetc(fp)) != EOF)
/* Viene letto e stampato un carattere per volta sino a fine file */
putchar(c);
fclose(fp);
}
else
printf("Il file non può essere aperto\n");
}
Lettura e scrittura di stringhe (accesso per linee)
Quattro funzioni della standard library consentono la lettura e la
scrittura di stringhe di caratteri su file: gets e puts rispettivamente
leggono da Standard Input e scrivono su Standard Output, fgets e
fputs rispettivamente leggono o scrivono linee (stringhe di caratteri
terminate da un newline) dal o sul file specificato come parametro di
ingresso.
Per non farla troppo lunga … la seguente funzione riceve come
parametro di ingresso una stringa di riferimento, legge per linee il
contenuto del file di testo filein e scrive, nel file di testo fileout, solo
le linee che contengono la stringa di riferimento. La funzione
restituisce valore pari a 1 se l’operazione è stata correttamente
ultimata e valore 0 in caso contrario.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#define
OK
#define
ERROR
#define
MAXLINE
1
0
100
int copiaselettiva(char refstr[])
{
char line[MAXLINE];
FILE *fin, *fout;
If ((fin = fopen("filein", "r")) == NULL)
/* filein viene aperto in lettura con modalità testo */
return ERROR;
if ((fout = fopen("fileout", "w")) == NULL)
/* fileout viene aperto in scrittura con modalità testo */
{
fclose(fin);
return ERROR;
}
while (fgets(line,MAXLINE,fin) != NULL)
/* fgets legge da filein al più MAXLINE–1 caratteri e assegna al
vettore line i caratteri letti, incluso l'eventuale carattere di
newline, e termina la stringa con il carattere \0 */
if (strstr (line,refstr) != NULL)
/* La funzione strstr restituisce la posizione della prima
occorrenza della stringa puntata da refstr nella stringa puntata
da line; se la seconda stringa non è contenuta nella prima viene
restituito il valore NULL */
fputs(line,fout);
fclose(fin);
fclose(fout);
return OK;
}
Lettura e scrittura di strutture (accesso per blocchi)
int fread(void *ptr, dimelemento, numelementi, FILE *fp);
legge un blocco di dati binari o testuali dal file cui fa riferimento fp e
li memorizza nel vettore identificato da ptr. La funzione termina
correttamente
se legge il numero di byte richiesti
(dimelemento*numelementi); termina anche se incontra la fine del
file o se si verifica un errore di lettura. La funzione restituisce il
numero di elementi effettivamente letti: se tale numero è inferiore
rispetto al numero richiesto è necessario usare feof o ferror per capire
i motivi del (mal)funzionamento ottenuto.
int fwrite(void *ptr, dimelemento, numelementi, FILE *fp);
scrive un blocco …
La funzione termina correttamente se …
------------------------------------------Un file Persone è costituito da record di tipo Persona.
Ogni Persona contiene i campi nome, cognome, indirizzo.
Si vuole modificare il file aggiungendo a ogni persona il campo
CodiceFiscale.
Un file CodiciFiscali contiene i codici fiscali delle persone contenute
in persone, nello stesso ordine.
Si vuole costruire un file NuovePersone
I tre file sono binari.
Questa operazione è svolta, in maniera parametrica rispetto ai file
utilizzati, dalla seguente funzione, cui sono premesse le necessarie
dichiarazioni di tipo.
typedef struct { char
nome[20];
char
cognome[20];
char
indirizzo[50];
} Persona;
typedef char CodFisc[16];
typedef struct { char
nome[20];
char
cognome[20];
char
indirizzo[50];
CodFisc CodiceFiscale;
} NuovaPersona;
/* I file Persone, CodiciFiscali e Nuove Persone si suppongono aperti dal
main. pp, cf e np fanno riferimento ai tre file in questione */
void AggiornaPersone (FILE *pp, FILE *cf, FILE *np)
{
Persona
PersonaCorrente;
CodFisc
CodFiscCorrente;
NuovaPersona NuovaPersonaCorrente;
rewind(pp);
/* Rende possibile le seguenti operazioni di lettura e scrittura sul file
identificato da pp, iniziando dal primo byte del file.*/
rewind(cf);
rewind(np);
while (fread(&PersonaCorrente,sizeof(Persona),1,pp) != 0)
/* Finché non si è raggiunta la fine del file */
{
fread(CodFiscCorrente,sizeof(CodFisc),1,cf);
strcpy(NuovaPersonaCorrente.nome, PersonaCorrente.nome);
strcpy(NuovaPersonaCorrente.cognome,PersonaCorrente.cognome);
strcpy(NuovaPersonaCorrente.indirizzo, PersonaCorrente.indirizzo);
strcpy(NuovaPersonaCorrente.CodiceFiscale, CodFiscCorrente);
fwrite(&NuovaPersonaCorrente,sizeof(NuovaPersona),1,np);
}
}
Accesso diretto
int fseek(FILE *fp, long offset, int refpoint)
sposta l’indicatore di posizione per effettuare accessi diretti al file a cui fa
riferimento fp. Lo scostamento offset (può assumere valori positivi o
negativi ed è espresso in byte) si riferisce alla posizione fissa indicata da
refpoint; quest’ultimo può assumere tre diversi valori indicati in stdio.h:
SEEK_SET indica uno scostamento rispetto all’inizio del file,
SEEK_CUR indica uno scostamento rispetto alla posizione corrente,
SEEK_END indica uno scostamento rispetto alla fine del file. La funzione
fseek restituisce zero se la richiesta è corretta, un valore diverso da zero
altrimenti.
long
ftell(FILE
*fp)
restituisce il valore corrente dell’indicatore di posizione del file
specificato. Per file binari la posizione è il numero di byte rispetto
all’inizio del file, mentre per file testuali è un valore dipendente
dall’implementazione.
rewind(f)
equivale a
fseek (f, 0, SEEK_SET);
A differenza di fseek, rewind non restituisce alcun valore.
Inversione del contenuto di un file numint di interi:
...
main()
{
FILE
*f;
long int
inizio, fine;
int
tempi, tempf;
unsigned int
dim;
if ((f = fopen("numint", "rb+")) == NULL)
{
puts("Non è stato possibile aprire il file numint");
/* più efficiente della printf per la stampa di un messaggio dato che
non richiede la scansione e l’interpretazione della stringa di controllo
*/
exit(1);
/* La funzione exit provoca una conclusione non anomala del
programma e la restituzione del controllo al sistema operativo */
}
inizio = 0;
dim = sizeof(int);
fseek(f, –dim, SEEK_END);
/* SEEK_END è una costante definita nel file stdio.h. Ha valore 2 */
fine = ftell(f);
while (inizio < fine)
{
fseek(f, inizio, SEEK_SET);
/* SEEK_SET è una costante definita nel file stdio.h. Ha valore 0 */
fread(&tempi, dim, 1, f);
fseek (f, fine, SEEK_SET);
fread (&tempf, dim, 1, f);
/* È necessario riposizionarsi dato che la precedente istruzione
fread ha spostato la posizione corrente sul successivo elemento */
fseek (f, fine, SEEK_SET);
fwrite (&tempi, dim, 1, f);
fseek (f, inizio, SEEK_SET);
fwrite (&tempf, dim, 1, f);
inizio = inizio + dim;
fine = fine – dim;
}
}