Si vuole costruire un programma che legga tre numeri
dall’ingresso, quindi verifichi che questi possano essere la
lunghezza dei tre lati di un triangolo (la lunghezza di ogni lato
deve essere minore della somma degli altri due) e infine
determini se il triangolo avente lati con le lunghezze indicate è
scaleno, isoscele oppure equilatero.
/*Programma per la valutazione di un triangolo */
main()
{
/*Lettura dei dati di ingresso */
scanf(X); scanf(Y); scanf(Z);
/* Verifica che i dati possano essere le lunghezze
dei lati di un triangolo */
if ((X < Y + Z) && (Y < X + Z) && (Z < X + Y))
/*Distinzione tra i vari tipi di triangolo */
if (X == Y && Y == Z)
printf("I dati letti corrispondono a un triangolo equilatero");
else
if (X == Y || Y == Z || X == Z)
printf("I dati letti corrispondono a un triangolo isoscele");
else
printf("I dati letti corrispondono a un triangolo scaleno");
else
printf("I dati letti non corrispondono ad alcun triangolo");
}
NB
L’uso delle istruzioni condizionali annidate causa rischio di
ambiguità quando qualcuna di loro manca del ramo else:
if (C1) if (C2) S1; else S2;
if (C1)
if (C2) S1;
else S2;
oppure
if (C1)
if (C2) S1;
else S2;
?
Convenzione:
il primo ramo else viene attribuito all’ultimo if. Nell’esempio
precedente, questo significa scegliere la seconda alternativa.
Altrimenti, scriviamo esplicitamente:
if (C1) {if (C2) S1;} else S2;
Analogamente con a + b * c intendiamo a + (b * c);
altrimenti (a + b) * c.
Torniamo al problema di leggere una
sequenza di dati e riscriverli in ordine inverso
• Il problema richiede la memorizzazione di tutti i dati in celle diverse- prima di cominciare a scriverli
• Nel linguaggio assembler (di von Neumann) avevamo
risolto il problema mediante l’indirizzamento
indiretto (si poteva fare anche in maniera più …
basilare, ma più complessa)
• I linguaggi di alto livello invece introducono il
concetto di dato strutturato, ossia informazione che a
sua volta è composta di informazioni più elementari.
• Il primo tipo di dato strutturato che affrontiamo è
l’array: sequenza lineare di celle omogenee e
consecutive che di per sé costituiscono una variabile.
Rivediamo la struttura della macchina astratta
C, includendo il nuovo tipo di variabili
• Un array viene identificato come qualsiasi altra
variabile
• Però anche i suoi elementi sono variabili
• Ad essi si accede mediante un indice:
• Ad esempio:
• scanf(s[2]);
• per leggere un dato e memorizzarlo nella terza cella
dell’array s: in C il primo elemento di ogni array è
sempre lo 0-esimo ---> se un array ha 10 elementi il
suo indice può assumere i valori interi tra 0 e 9 (per
il momento però non ci preoccupiamo del numero di
elementi di un array);
• a[3] = s[1] + x;
• if (a[4] > s[1] + 3) s[2] = a[2] + a[1];
• … ma anche
• x = a[i];
• a[i] = a[i+1];
a[i*x] = s[a[j+1]–3]*(y – a[y]);
Torniamo al problema di partenza: leggere
una sequenza -di caratteri, terminata da un
‘%’- e riscriverla in ordine inverso
• /* Programma InvertiSequenza */
• main()
• {
•
indice = 0;
•
scanf(x);
•
while (x != '%')
•
{
•
sequenza[indice] = x;
•
indice = indice + 1;
•
scanf(x);
•
}
•
while (indice > 0)
•
{
•
indice = indice - 1;
•
printf(sequenza[indice]);
•
}
• }
A poco a poco cominciamo ad affrontare
problemi, e a scrivere programmi, un po’
meno banali
•
•
Supponiamo di avere sullo Standard Input una serie di
dati relativi a delle fatture: per ogni fattura una cella dello
Standard Input ne contiene l’importo e le tre successive la
data di emissione, nella forma “giorno” (un numero
compreso tra 1 e 31), “mese”, “anno”. Il solito % di
terminazione è posto dopo l’anno dell’ultima fattura.
Si vogliono stampare, nell’ordine, sullo Standard Output:
– la dicitura: IMPORTI FATTURE EMESSE;
– la sequenza di tutti gli importi, nello stesso ordine di
ingresso, preceduti dal carattere $;
– la dicitura: TOTALE FATTURE EMESSE;
– il totale delle fatture stesse, precedute dal carattere $;
– la dicitura: DATE DI EMISSIONE;
– la sequenza delle date di emissione, nello stesso
ordine di ingresso. I tre elementi di ogni data devono
essere separati da una /; alla fine di ogni data va
scritto il carattere #.
Quando i problemi si complicano -poco per ora- è
difficile scrivere d’acchito un programma che li risolva:
conviene andare per gradi.
Cominciamo con lo scrivere l’algoritmo, poi lo
codificheremo
– Un primo ciclo esegue la lettura dei vari dati, quattro
per volta (infatti ogni fattura è descritta da quattro
elementi). Ognuno dei quattro dati letti viene
memorizzato, rispettivamente, in una cella di quattro
diversi array, denominati fatture, giorno, mese e
anno. L’indice di ognuno di questi array viene
incrementato di 1 a ogni iterazione del ciclo. Durante
questo ciclo viene anche calcolato l’importo totale
delle varie fatture.
– Viene stampata la dicitura IMPORTI FATTURE
EMESSE mediante un’unica istruzione printf.
– Un primo ciclo di scrittura stampa nell’ordine tutti
gli elementi dell’array fatture intercalandoli con il
simbolo $.
– Viene stampata la dicitura TOTALE FATTURE
EMESSE seguita da $ e dal valore del totale
precedentemente calcolato.
– Viene stampata la dicitura DATE DI EMISSIONE.
– Un secondo ciclo di scrittura stampa le varie terne di
valori “giorno, mese, anno”, prelevandole nell’ordine
dai corrispondenti array e introducendo il carattere /
tra giorno e mese e tra mese e anno, e il carattere #
tra l’anno della data corrente e il giorno della terna
successiva.
Dall’algoritmo al programma:
•
/* Programma Fatture */
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
main()
{
contatore = 0; totale = 0; scanf(dato);
while (dato != '%')
{
fatture[contatore] = dato; totale = totale + dato;
scanf(dato); giorno[contatore] = dato;
scanf(dato); mese[contatore] = dato;
scanf(dato); anno[contatore] = dato;
scanf(dato); contatore = contatore + 1;
}
printf("IMPORTI FATTURE EMESSE");
NumFatture = contatore; contatore = 0;
while
(contatore < NumFatture)
{
printf('$'); printf(fatture[contatore]); contatore = contatore + 1;
}
printf("TOTALE FATTURE EMESSE"); printf('$'); printf(totale);
printf("DATE DI EMISSIONE"); contatore = 0;
while (contatore < NumFatture)
{
printf(giorno[contatore]); printf('/');
printf(mese[contatore]); printf('/');
printf(anno[contatore]); printf('#');
contatore = contatore + 1;
}
•
}
La costruzione incrementale dei programmi mediante
pseudocodice
•
•
•
•
•
Si vuole costruire un analizzatore di testo che sostituisca
sistematicamente una parola con un’altra. Precisamente, si
supponga che lo Standard Input della macchina abbia il
contenuto seguente.
In primo luogo è scritta (carattere per carattere) una parola (per
“parola” intendiamo qui una sequenza di caratteri alfabetici);
segue il carattere $; poi un’altra parola seguita dal carattere #;
successivamente vi è una sequenza di parole separate tra di
loro da uno spazio e chiusa da un % (cioè, dopo l’ultima parola
c’è uno spazio seguito dal terminatore finale %).
Il programma deve riscrivere su Standard Output il testo
costituito dalla sequenza di parole dopo il #, sostituendo a ogni
occorrenza della prima parola dello Standard Input la seconda.
Se per caso la prima parola mancasse, il programma deve
stampare un messaggio che avverte l’utente dell’errore e
sospendere l’esecuzione. Al contrario, può essere mancante la
seconda parola: in tal caso si ottiene l’effetto di cancellare ogni
occorrenza della prima parola; è ammesso il caso particolare
che l’intero testo da riscrivere sia assente.
Osservazione
Per la prima volta ci preoccupiamo della possibilità di dati
errati o, più in generale ancora, di condizioni eccezionali.
Per costruire il programma -non banalissimoprocediamo per gradi
•
Prima specifichiamo a grandi linee e informalmente -in
italiano- l’algoritmo:
1
Verifica se prima del carattere $ esiste una parola. In caso
negativo stampa il messaggio MANCA LA PAROLA DA
SOSTITUIRE. In caso positivo procedi come segue.
Memorizza la prima parola del testo in un array di caratteri.
Memorizza la seconda parola in un altro array.
A questo punto fai la scansione dell’intero testo parola per
parola (fino all’individuazione del carattere %).
4.1 Memorizza ogni parola in un array.
4.2 Confronta la parola letta con la prima parola. Se le due
parole coincidono, scrivi nello Standard Output la
seconda parola, altrimenti scrivi la parola appena letta.
2
3
4
Non tutti i termini utilizzati, pur chiari, (ad esempio:
memorizza parola) corrispondono a operazioni
elementari del C: occorre analizzarli separatamente
come sottoproblemi. Per non fare tutta la fatica in un
colpo solo, codifichiamo “in parte” l’algoritmo:
/* Programma SostituzioneParole */
main()
{
scanf(carattere);
if (carattere == '$')
printf("MANCA LA PAROLA DA SOSTITUIRE");
else
{
[memorizza nell'array PrimaParola la sequenza di
caratteri fino a '$'];
[memorizza nell'array SecondaParola la sequenza di
caratteri seguenti '$' fino a '#'];
scanf(carattere);
while (carattere != '%')
{
[memorizza nell'array ParolaCorrente la
sequenza di caratteri fino al prossimo spazio];
[confronta PrimaParola con ParolaCorrente];
if
([PrimaParola == ParolaCorrente])
[printf(SecondaParola)];
else
[printf(ParolaCorrente)];
printf(' ');
/* Sia nel caso che si sia scritta la parola appena letta
(ParolaCorrente), sia nel caso che si sia scritta la seconda parola
al posto della prima, si scrive uno spazio per separarla dalla
parola successiva */
scanf(carattere);
/* Inizia la lettura della prossima ParolaCorrente,
a meno che il carattere letto non sia % */
}
}
}
• Esaminiamo ora i sottoproblemi:
– memorizzazione di una parola in un array,
– scrittura di una parola
– confronto tra due parole.
•
Ognuna di queste operazioni richiede a sua volta un
“sottoalgoritmo” per la sua realizzazione.
•
Concentriamo
confronto.
•
decidere se due parole memorizzate rispettivamente nei
due array PrimaParola e ParolaCorrente coincidono :
l’attenzione
sulla
meno
banale:
il
– se le lunghezze delle due parole sono diverse, allora
le parole sono senz’altro diverse. In caso contrario:
– fai la scansione dei due array carattere per carattere
fino a quando o non trovi due caratteri diversi o
l’indice dell’array ha superato la lunghezza della
parola; nel primo dei due casi precedenti concludi
che le due parole sono diverse; nel secondo caso
concludi che le due parole coincidono.
Ora codifichiamo l’algoritmo precedente
separatamente ...
• if (LunghPrimaPar == LunghParCorr)
• {
•
contatore = 0;
– while ((contatore < LunghPrimaPar) &&
•
PrimaParola[contatore] ==
•
ParolaCorrente[contatore]))
contatore = contatore + 1;
– if (contatore >= LunghPrimaPar)
•
printf("Le due parole coincidono");
– else
•
printf("Le due parole sono diverse");
• }
• else
•
printf("Le due parole sono diverse");
… e alla fine mettiamo tutto assieme
•
/* Programma SostituzioneParole */
main()
{
scanf(carattere);
if
(carattere == '$')
printf ("MANCA LA PAROLA DA SOSTITUIRE");
else
{
contatore = 0;
while (carattere != '$')
/* Memorizzazione della prima parola */
{
PrimaParola[contatore] = carattere;
contatore = contatore + 1;
scanf(carattere);
}
LunghPrimaPar = contatore;
scanf(carattere); contatore = 0;
while (carattere != '#')
/* Memorizzazione della seconda parola */
{
SecondaParola[contatore] = carattere;
contatore = contatore + 1;
scanf(carattere);
}
LungSecPar = contatore;
/* Si entra ora nella fase di scansione del testo */
scanf(carattere);
while (carattere != '%')
{
contatore = 0;
while (carattere != ' ' )
/* Memorizzazione della parola corrente */
{
ParolaCorrente[contatore] = carattere;
contatore = contatore + 1;
scanf(carattere);
}
LungParCorr = contatore;
/* Si confronta la prima parola con la parola corrente */
if (LunghPrimaPar == LunghParCorr)
{
contatore = 0;
while (contatore < LunghPrimaPar &&
PrimaParola[contatore] ==
ParolaCorrente[contatore])
contatore = contatore + 1;
if (contatore >= LunghPrimaPar
/* Si ricopia la seconda parola */
{
contatore = 0;
while (contatore < LungSecPar)
{
printf(SecondaParola[contatore]);
contatore = contatore + 1;
}
}
else
/* Si ricopia la parola corrente */
{
contatore = 0;
while (contatore < LungParCorr)
{
printf(ParolaCorrente[contatore]);
contatore = contatore + 1;
}
}
}
else
/* Si copia la Parola corrente: in questo caso le due parole sono
differenti perché le lunghezze sono differenti */
{
contatore = 0;
while (contatore < LungParCorr)
{
printf(ParolaCorrente[contatore]);
contatore = contatore + 1;
}
}
printf(' ');
/*Sia nel caso che si sia scritta la parola appena letta
(ParolaCorrente), sia nel caso che si sia scritta la seconda parola
al posto della prima, si scrive uno spazio per separarla dalla
parola successiva*/
scanf(carattere);
/* Inizia la lettura della prossima ParolaCorrente, a meno che il
carattere letto non sia % */
}
}
}
• I programmi visti finora non sono ancora “puro codice
C” compilabile
• Anche se un compilatore per quello “pseudo-C”
sarebbe possibile
• Che cosa manca per arrivare al “puro codice C”
compilabile?
• Ricominciamo da capo (quasi):
/* Programma SommaSequenza */
#include <stdio.h>
void main()
{
int numero, somma;
somma = 0;
scanf("%d", &numero);
while (numero != 0)
{
somma = somma + numero;
scanf("%d", &numero);
}
printf("La somma dei numeri digitati è: %d\n", somma);
}
• ed esaminiamo le novità (non proprio in ordine di
apparizione):
La struttura dei programmi C
• Un programma C deve contenere, nell’ordine:
 una parte contenente direttive per il
compilatore. Per il momento trascuriamo questa
parte.
 l’identificatore predefinito main seguito dalle
parentesi () (già visto in precedenza) (e
preceduto “spesso” dalla parola chiave void)
 due parti, sintatticamente racchiuse dalle
parentesi {}:
– la parte dichiarativa;
– la parte esecutiva.
• La parte dichiarativa di un programma costituisce la
principale novità.
• Essa elenca tutti gli elementi che fanno parte del
programma, con le loro principali caratteristiche.
• La parte esecutiva consiste in una successione di
istruzioni come già descritto in pseudo-C.
La parte dichiarativa
• Tutto ciò che viene usato va dichiarato
• In prima istanza -altri elementi seguiranno-:

dichiarazione delle costanti;
• dichiarazione delle variabili.
• Perché obbligare il programmatore a questa fatica
… inutile?
– Aiuta la diagnostica (ovvero segnalazione di
errori):
– x = alfa;
– alba = alfa + 1;
– Senza dichiarazione alba è una nuova variabile
• Principio importante: meglio un po’ più di fatica
nello scrivere un programma che nel leggerlo -e
capirlo!
Esaminiamo più in dettaglio la dichiarazione
delle variabili (posponendo quella delle
costanti)
• Una dichiarazione di variabile consiste in uno
specificatore di tipo, seguito da una lista di uno o
più identificatori di variabili separati da una virgola.
Ogni dichiarazione termina con ‘;’
• Il concetto di tipo (di dato, o informazione) è un
concetto fondamentale della programmazione
• La stessa stringa di bit può rappresentare un intero,
un carattere, …
• Il tipo di dato è il “ponte” tra la visione astratta
dell’informazione e la sua rappresentazione
concreta: strumento fondamentale di astrazione.
Infatti parleremo spesso di tipo di dato astratto.
• Abbiamo già fatto uso del concetto di tipo (di una
variabile): abbiamo infatti parlato di interi, caratteri,
… tipi strutturati. A poco a poco saremo vieppiù
sistematici nell’esposizione del sistema di tipi (del
C e, in generale, nella programmazione)
• Cominciamo con tre specificatori di tipi già noti:
• le parole chiave int, float, char specificano,
rispettivamente i tipi intero, reale, carattere:
•
float
int
char
•
equivalenti a:
•
float
int
char
float
•
Se un identificatore di variabile x è dichiarato di tipo int,
esso potrà essere usato nella parte esecutiva solo come
tale. Di conseguenza, x non assumerà mai un valore
reale, come per esempio 3.14.
x,y;
i,j;
simb;
x;
i,j;
simb;
y;
La dichiarazione di costanti e il loro uso
Una dichiarazione di costante associa permanentemente un
valore a un identificatore. Come nel caso della dichiarazione
di variabili, la sezione della dichiarazione di costanti consiste
in una lista di dichiarazioni. Ogni dichiarazione, a sua volta,
consiste in:
la parola chiave const;
lo specificatore di tipo;
l’identificatore della costante;
il simbolo =;
il valore della costante. Esso può essere, fra le altre
cose, un numero intero, con o senza segno, un numero
reale o un carattere;
il solito “terminatore” ‘;’
Esempi di dichiarazioni di costanti:
const
const
const
const
float
float
int
char
PiGreco = 3.14;
PiGreco = 3.1415, e = 2.718;
N = 100, M = 1000;
CAR1 = 'A', CAR2 = 'B';
Un eventuale assegnamento a una costante sarebbe segnalato
come errore dal compilatore.
Perché dichiarare le costanti? (potremmo anche farne a
meno)
L’istruzione
AreaCerchio =
PiGreco*RaggioCerchio*RaggioCerchio;
è equivalente a:
AreaCerchio = 3.14*RaggioCerchio*RaggioCerchio;
(se si fa riferimento alla prima dichiarazione di PiGreco)
1.
Maggior astrazione:
“l’area del cerchio è il prodotto del quadrato del raggio per ”, e
non “per 3.14”, né “3.1415”, né “3.14159” ecc.
2.
Maggior astrazione ===> parametricità ==> generalità ==>
modificabilità …:
Se non mi accontento più di 2 cifre decimali per
approssimare , mi basta modificare la sua dichiarazione,
non tutte le istruzioni in cui ne faccio uso.
Altri esempi di parametricità ottenuta attraverso la
dichiarazione di costanti saranno illustrati in seguito -anche
attraverso un nuovo modo di dichiararle.
• Torniamo ora alla parte esecutiva di un programma
• L’unica differenza tra il codice “pseudo-C” e il codice “C
reale” dell’esempio precedente sta nelle istruzioni di I/O.
• Il punto è che le “istruzioni” di I/O non sono vere e
proprie istruzioni del linguaggio ma sottoprogrammi di
libreria, concetto che verrà illustrato più avanti. Al
momento, però … facciamo finta che siano istruzioni.
• printf richiede una stringa di controllo e un insieme di
elementi da stampare:
• printf(stringa di controllo, elementi da stampare);
•
La stringa di controllo è una stringa che viene stampata in
uscita e può contenere caratteri detti di conversione o di
formato preceduti dal simbolo % e altri simboli particolari.
– I caratteri di formato %d, %f, %c, %s provocano la stampa sullo
Standard Output rispettivamente:
– di un numero intero decimale, di un numero reale (floating point),
di un carattere, di una stringa di caratteri.
– Il simbolo \n nella stringa di controllo provoca un salto a nuova
riga per la successiva scrittura.
•
L’insieme degli elementi da stampare è una lista di variabili, di
costanti o di espressioni composte con variabili e costanti.
printf ("Lo stipendio annuo dei dipendenti di categoria %d è pari a
E. %f", cat_dipend, stip_medio);
Se cat_dipend è una variabile di tipo int che rappresenta la
categoria dei dipendenti considerati, l’istruzione printf viene
eseguita usando il suo valore corrente, per esempio 6.
Se stip_medio è una variabile di tipo float che rappresenta lo
stipendio medio calcolato per il gruppo di dipendenti considerato,
l’istruzione printf viene eseguita usando il suo valore corrente, per
esempio 1570580.0.
L’esecuzione dell’istruzione printf provocherà la stampa sullo schermo
della frase
Lo stipendio annuo dei dipendenti di categoria 6 è pari a E. 1570580.0
printf("%s\n%c%c\n\n%s\n", "Questo programma è
stato scritto da", iniz_nome, iniz_cognome, "Buon
lavoro!");
Se iniz_nome è una variabile di tipo char che
rappresenta l’iniziale del nome del programmatore,
l’istruzione printf viene eseguita usando il suo valore
corrente, per esempio G.
Se iniz_cognome è una variabile di tipo char che
rappresenta l’iniziale del cognome del programmatore,
l’istruzione printf viene eseguita usando il suo valore
corrente, per esempio M.
L’esecuzione
dell’istruzione
printf
visualizzazione delle seguenti frasi:
Questo programma è stato scritto da
GM
Buon lavoro!
Si noti l’effetto dei simboli \n
produce
la
• Anche scanf è del tipo
• scanf(stringa di controllo,
elementi da leggere);
• ma
• i nomi delle variabili sono preceduti dall’operatore
unario &
•
scanf("%c%c%c%d%f", &c1, &c2, &c3, &i, &x);
•
Se al momento dell’esecuzione dell’istruzione scanf
l’utente inserisce i seguenti dati:
•
ABC 3 7.345
 la variabile c1 (di tipo char) assume il valore A.
(&c1 va letto come indirizzo della variabile c1);
 la variabile c2 (di tipo char) assume valore B;
 la variabile c3 (di tipo char) assume valore C;
 la variabile i (di tipo int) assume valore 3;
 la variabile x (di tipo float) assume valore 7.345.
Resta da spiegare la direttiva #include
ogni programma che utilizza al suo interno le funzioni
printf e scanf deve dichiarare l’uso di tali funzioni nella
parte direttiva che precede il programma principale.
#include <stdio.h>
E’ una direttiva data a una parte del compilatore, chiamata
preprocessore, che include una copia del contenuto del file
stdio.h. Essa provoca l’inclusione (una copia) del contenuto
del file stdio.h. Tra le dichiarazioni di funzione contenute in
stdio.h sono presenti quelle di printf e scanf. Questo consente
una esatta compilazione del programma che utilizza nella sua
parte eseguibile printf e scanf e una produzione corretta del
codice eseguibile grazie all’utilizzo del codice che il sistema C
mette a disposizione per printf e scanf.
E finalmente ...
/* PrimoProgrammaC */
#include <stdio.h>
main()
{
printf("Questo è il mio primo programma in C\n");
}
NB: niente dichiarazioni!
------------------------------------------------------------/* Programma SommaDueInteri */
#include <stdio.h>
main()
{
int a, b, somma;
printf (“inserisci come valore dei due addendi due numeri
interi\n”);
scanf("%d%d", &a, &b);
somma = a + b;
printf("La somma di a+b è:\n%d \nArrivederci!\n",
somma);
}
Se vengono inseriti i dati 3 e 5 l’effetto dell’esecuzione del
programma sullo Standard Output è il seguente:
La somma di a+b è:
8
Arrivederci!
Se invece fossero stati omessi i primi due simboli \n nella stringa
di controllo?
Il programma SommaDueInteri è anche un primo esempio di
programma interattivo
• Intraprendiamo ora lo studio sistematico degli
elementi essenziali del linguaggio C
• Lo scopo non è tanto diventare esperti del
linguaggio, quanto impossessarsi di alcuni concetti
fondamentali della programmazione che dovranno
essere applicati in vari contesti e usando diversi
strumenti/linguaggi
• C sarà perciò soltanto un punto di riferimento ma
dovremo presto imparare a “giostrare tra vari
linguaggi”.
• Alcuni di essi -i più tradizionali (Ada, Pascal,
Modula-2, C++, Java, ….)- hanno molto in comune
con C e ad essi soprattutto faremo riferimento. Altri
sono basati su principi meno convenzionali - che
verranno illustrati in corsi successivi.
Cominciamo con il concetto di tipo di dato
• Ci siamo già imbattuti in questo concetto:
–
–
–
–
–
•
•
•
•
•
•
tipo di dato = tipo di informazione
alcuni tipi: interi, reali, caratteri, array, …
ma anche: fatture, conti correnti, pagine web, …
Quanti tipi? Infiniti!
E allora?
Occorre un po’ di sistematicità
Definizione generale di tipo di dato:
Insieme di valori e di operazioni ad esso applicabili
(riscontrare con i tipi già noti)
Tipo astratto:
conta la visione esterna, non la rappresentazione
interna, ovvero il punto di vista di chi usa il tipo,
non di chi lo realizza:
– Gli interi -e tutti gli altri tipi- all’interno di un
calcolatore sono stringhe -sequenze- di bit. Ma l’HW
ci permette di astrarre da questa conoscenza: ci
permette di scrivere 23, 555, .. e 74 + 223 senza
conoscere quale algoritmo viene applicato per
calcolare la somma.
– Immaginiamo di dover trattare direttamente come
stringhe di bit la divina commedia, una pagina web,
…
– Inoltre potremo talvolta usare diverse
rappresentazioni concrete per la stessa astrazione
Classificazione dei tipi di dato
• 1
• Tipi semplici (interi, caratteri, reali, …)
• Tipi strutturati (per ora: array)
– Attenzione: non sempre
– tipo semplice = valori del tipo contenuti in una cella
di memoria
– tipo strutturato = valori del tipo contenuti in diverse
celle di memoria
– Esistono vari controesempi (e.g. i reali …)
– Tipo semplice: i valori vengono gestiti dalle varie
operazioni in modo unitario
– Tipo strutturato: i valori possono essere scomposti in
elementi più semplici trattabili separatamente.
• 2
• Tipi predefiniti (nel linguaggio) (interi, caratteri, …)
• Tipi definiti dall’utente (per soddisfare le infinite e
imprevedibili esigenze)
– in C: età, data, conto_corrente non sono predefiniti:
devono essere costruiti dal programmatore
– in altri linguaggi “special purpose” potrebbero esserlo
(e.g. data nei fogli elettronici)
• Il concetto è generale: l’attuazione varia a seconda
del linguaggio (con molta parte comune a quasi tutti)
Cominciamo da:
Tipi semplici predefiniti
Quattro tipi di base: char (caratteri), int (interi), float (reali),
double (reali in precisione doppia).
I “qualificatori di tipo” signed o unsigned possono essere
applicati a char e a int,
i qualificatori short o long a int
il qualificatore long a double..
Tipi semplici predefiniti del C
(da non imparare a memoria)
Tipo predefinito
char
signed char
unsigned char
signed short int
signed int
signed long int
unsigned short int
unsigned int
unsigned long int
float
double
long double
Denominazioni alternative
signed short, short
signed, int
long int, signed long, long
unsigned short
unsigned
unsigned long
short e long condiziona(va)no lo spazio allocato dal compilatore
per la memorizzazione delle variabili tipizzate
signed e unsigned, short e long condizionano l’insieme dei
valori nonché il valore massimo e minimo
Non è necessario dichiarare tipi built-in
Il tipo int
• il tipo “interi” non è l’insieme {..., _1, 0, 1, 2, ...}, bensì quello
stesso insieme “corredato” di somma, sottrazione,
moltiplicazione ecc.
• il tipo “interi” della matematica ha infiniti valori, e anche
infinite operazioni.
• Non così in C: int è un’approssimazione finita del
corrispondente tipo matematico, legata alla finitezza della
memoria reale del calcolatore
• I valori di int in C
• spazio allocato (short int)  spazio allocato (int)  spazio
allocato(long int)
• Un signed int usa un bit per la rappresentazione del segno
• Un unsigned int utilizza tutti gli n bit (16 ---> 32 ---> 64) per
rappresentare il valore intero supposto positivo.
• INT_MIN e INT_MAX: identificatori di costante predefiniti,
però int è predefinito dalla definizione del linguaggio,
INT_MIN e INT_MAX lo sono dall’implementazione del
linguaggio, non dalla definizione dello stesso.
Su qualunque macchina venga eseguito un programma vale
comunque la proprietà seguente:
spazio allocato (signed int) = spazio allocato (unsigned int)
Operazioni built-in per dati di tipo int
=
Assegnamento di un valore int a una variabile int
+
*
/
Somma (tra int ha come risultato un int)
Sottrazione (tra int ha come risultato un int)
Moltiplicazione (tra int ha come risultato un int)
Divisione con troncamento della parte non intera
(risultato int)
Resto della divisione intera
Relazione di uguaglianza
Relazione di diversità
Relazione “minore di”
Relazione “maggiore di”
Relazione “minore o uguale a”
Relazione “maggiore o uguale a”
%
==
!=
<
>
<=
>=
Se alcune operazioni fornissero un risultato non appartenente
all’insieme dei valori consentito (per esempio se il risultato di una
moltiplicazione fosse maggiore di INT_MAX) il risultato
effettivamente prodotto sarebbe una segnalazione di errore
(Integer Overflow) : in questo caso il risultato concreto non
corrisponde al valore astratto.
Operazioni built-in per dati di tipo int
=
Assegnamento di un valore int a una variabile int
+
*
/
Somma (tra int ha come risultato un int)
Sottrazione (tra int ha come risultato un int)
Moltiplicazione (tra int ha come risultato un int)
Divisione con troncamento della parte non intera
(risultato int)
Resto della divisione intera
Relazione di uguaglianza
Relazione di diversità
Relazione “minore di”
Relazione “maggiore di”
Relazione “minore o uguale a”
Relazione “maggiore o uguale a”
%
==
!=
<
>
<=
>=
Se alcune operazioni fornissero un risultato non appartenente
all’insieme dei valori consentito (per esempio se il risultato di una
moltiplicazione fosse maggiore di INT_MAX) il risultato
effettivamente prodotto sarebbe una segnalazione di errore
(Integer Overflow) : in questo caso il risultato concreto non
corrisponde al valore astratto.
I tipi float e double
• float e double: approssimazione dei numeri reali, non solo dal
punto di vista del loro limite, ma anche della precisione di
rappresentazione
• Due diverse rappresentazioni:
1. la normale rappresentazione decimale, o in virgola fissa:
3.14
1 234.543 328
543.
0.000 076
rappresentare 10900 o 10–900 in questa maniera
richiederebbe un enorme spreco di cifre, e quindi di
celle di memoria.
2. la rappresentazione in virgola mobile (floating point)
mantissa ed esponente (della base 10), separate dal
carattere “E”. Se un numero n ha mantissa m ed
esponente e, il suo valore è n = m  10e.
1 780 000.000 0023 può essere rappresentato in virgola mobile
nei modi seguenti:
178 000.000 000 23E1
17 800 000 000 023E-7
1.780 000 000 0023E+6, ….
Le notazioni sono interscambiabili e la macchina provvede
automaticamente alle necessarie conversioni
spazio allocato (float)  spazio allocato (double)
 spazio allocato (long double) (di solito useremo double)
Operazioni built-in per dati di tipo float e double
=
+
*
/
==
!=
<
>
<=
>=
Assegnamento
Somma
Sottrazione
Moltiplicazione
Divisione (a risultato reale; il simbolo è identico a quello
usato per la divisione intera)
Relazione di uguaglianza
Relazione di diversità
Relazione “minore di”
Relazione “maggiore di”
Relazione “minore o uguale a”
Relazione “maggiore o uguale a”
NB:
• Sia internamente (in base 2) che esternamente (in base 10) le
due rappresentazioni in virgola fissa e virgola mobile sono
interscambiabili  algoritmi interni di conversione.
• Un’operazione di relazione su due valori di tipo float (double o
long) produce come risultato un valore intero pari a zero se la
relazione non è verificata, e un valore intero diverso da zero se
la relazione è verificata.
• La standard library fornisce anche diverse funzioni
matematiche predefinite (sqrt, pow, exp, sin, cos, tan...) (per
double ).
• Per ora trattiamole come operazioni normali built-in (però
occorre includere l’opportuno file)
• Attenzione agli arrotondamenti:
(x/y) * y == x
potrebbe risultare falsa !
Invece di scrivere
if (x == y) ...
è meglio scrivere
if (x <= y + .000001 && y <= x + .000001) ...
Il tipo char
L’insieme dei dati di tipo char, è l’insieme dei caratteri ASCII, e
contiene tutte le lettere, le cifre e i simboli disponibili sulle
normali tastiere.
La codifica ASCII consente la rappresentazione di ciascun
carattere attraverso un opportuno valore intero.
definisce inoltre l’ordinamento dei valori: per qualsiasi coppia di
caratteri x e y, x < y se e solo se x precede y nell’elenco dei
caratteri.
Alcuni caratteri sono caratteri di controllo: la loro scrittura non
consiste in una vera e propria stampa di un simbolo sulla carta o
sul video, ma nell’esecuzione di un’operazione correlata alla
visualizzazione dei dati:
\n che provoca un a capo, \b = “backspace”, \t = “horizontal
tab”, \r = “carriage return”, ETX, EOF, ....
Il compilatore ANSI C alloca per una variabile di tipo char 1
byte e lo stesso avviene per una variabile di tipo signed char
o unsigned char. Un byte può contenere la codifica binaria di
256 valori differenti. Per un signed char l’insieme dei valori
va da –128 a +127, per un unsigned char l’insieme dei valori
va da 0 a 255 (ASCII esteso e problemi di standardizzazione
…).
Sono definite le operazioni di assegnamento (=), le operazioni
aritmetiche (+, –, *, /, %) e quelle relazionali (==, !=, < ecc.)
La comunanza di operazioni tra char e int è una naturale
conseguenza della rappresentazione dei caratteri tramite
numero intero.
…
Non proprio identico al normale concetto di carattere ...
Un tipico esempio di sfruttamento - e aberrazioni- delle
caratteristiche del C
Leggere una sequenza di caratteri (terminata da #); per ciascun
carattere letto viene stampato il relativo codice ASCII e, nel caso sia
una lettera dell’alfabeto minuscola, viene operata la trasformazione in
lettera maiuscola.
/* Programma ManipolazioneCaratteri*/
#include <stdio.h>
main()
{
char C, CM;
printf("Inserire un carattere – # per terminare il
programma\n");
scanf(“ %c", &C);
/*NB lo spazio prima di %*/
while (C != '#')
{
printf("Il codice ASCII del carattere %c è %d\n", C, C);
/* Se il carattere è una lettera minuscola */
if (C >= 'a' && C <= 'z')
{
/* La differenza 'a' – 'A' è lo scarto fra la rappresentazione
ASCII delle lettere maiuscole e minuscole dell'alfabeto */
CM = C – ('a' –'A');
printf("La lettera maiuscola per %c è %c e il suo
codice ASCII è %d\n", C, CM, CM);
}
printf("Inserire un carattere – # per terminare
il programma\n");
scanf(“ %c", &C);
}
}
Riassumendo
Tipi integral:
char
short
unsigned short
Tipi floating:
float
signed char
int
unsigned
double
unsigned char
long
unsigned long
long double
Tipi arithmetic: tipi integral + tipi floating
Tutti i tipi arithmetic del C condividono alcune importanti
caratteristiche:
sono totalmente ordinati
sono limitati
I tipi integral sono insiemi discreti.
I tipi floating sono insieme densi (in astratto)
La costruzione di nuovi tipi in C
Regole sintattiche
Una dichiarazione di tipo (type declaration) consiste nella
parola chiave typedef seguita dalla rappresentazione o
costruzione del nuovo tipo dall’identificatore del nuovo tipo, e
dal simbolo “;” che chiude la dichiarazione.
typedef int
anno;
Una volta definito e identificato un nuovo tipo ogni variabile
può essere dichiarata di quel tipo come di ogni altro tipo già
esistente.
char x;
anno y;
NB: typedef non consente di costruire veri e propri nuovi tipi
astratti (mancano le operazioni … colmeremo poi questa
lacuna)
Presentiamo ora in maniera sistematica le varie modalità per
costruire la rappresentazione di un nuovo tipo, cominciando dai
tipi semplici.
Ridefinizione
typedef
TipoEsistente
NuovoTipo;
TipoEsistente può essere sia un tipo built-in (predefinito), per
esempio int, sia un tipo user-defined precedentemente definito:
typedef
typedef
typedef
typedef
int
char
tipo1
tipo2
tipo1;
tipo2;
tipo3;
tipo4;
Constateremo tra breve l’estrema utilità e generalità di questa
caratteristica.
Enumerazione esplicita dei valori
Un nuovo tipo può essere costruito anche elencando, all’interno
di una coppia di parentesi graffe e separati tra loro da una
virgola, tutti i suoi valori:
typedef
typedef
typedef
typedef
enum
{lun, mar, mer, gio, ven, sab, dom}
GiornoDellaSettimana;
enum
{rosso, verde, giallo, arancio, violetto,
marrone, nero, ocra}
colore;
enum
{Giovanni, Claudia, Carla, Simone,
Serafino}
persone;
enum
{gen, feb, mar, apr, mag, giu, lug, ago, set,
ott, nov, dic}
mese;
Data la seguente dichiarazione di variabili:
persone
individuo, individuo1, individuo2;
è possibile scrivere istruzioni del tipo
individuo = Giovanni;
if (individuo1 == individuo2) individuo = Claudia;
senza includere i valori Giovanni e Claudia tra virgolette (non
sono dei valori di tipo stringa!).
Alcune osservazioni
• Spesso i valori del nuovo tipo sono rappresentati da nomi; però
il compilatore associa a tali nomi un progressivo valore intero
• Per esempio, una variabile x dichiarata di tipo mese che
assume durante l’esecuzione del programma valore gen assume
in realtà valore 0, 3 per apr, ecc.
• Nuova mancanza di astrazione del C: consente l’uso della
rappresentazione interna del valore di gen.
• non abusare di questa possibilità!
• Operazioni applicabili: le stesse degli interi:
• operazioni aritmetiche (+, –, *, /, %), assegnamento (=),
confronto per uguaglianza (==), diversità (!=), precedenza
stretta e debole (<, <=, >, >=).
• In particolare, la relazione di precedenza è definita dall’ordine
in cui vengono elencati i valori del tipo.
apr < giu
rosso < arancio
•producono un risultato un intero diverso da 0 (valore logico
“true”):
dom < lun
Simone < Giovanni
producono 0 (corrispondente al valore “false”):
===> un tipo costruito mediante enumerazione è, analogamente
ai tipi integral, un tipo totalmente ordinato, limitato ed
enumerabile.
Un importante caso particolare
In linguaggi come il Pascal il tipo boolean è predefinito e
contiene i due soli valori logici false e true. Su essi sono
definite le classiche operazioni logiche AND, OR, NOT.
In C la definizione di variabili che possano assumere valore false
o true richiede la dichiarazione di un tipo tramite il costruttore
di tipo enum:
typedef
boolean
enum
{false, true} boolean;
flag, ok;
flag e ok possono così essere definite come variabili in grado di
assumere valore vero (true) o falso (false) durante l’esecuzione
di un programma che le usi.
Raccomandiamo di usare il tipo boolean “a’ la Pascal”, anche se
in C è diverso.
I tipi strutturati
• Anche se in passato abbiamo introdotto le variabili
di “tipo strutturato” array,
• Ad essere rigorosi, in C -come in molti linguaggi
classici-, tipi predefiniti strutturati non esistono.
• Questa affermazione può sembrare in contrasto con
la seguente tipica dichiarazione di array in C:
• int lista[20];
• che dichiara un array di nome lista costituito da 20
interi (quindi il suo indice assume i valori da 0 a 19)
• Esaminiamo allora dalla radice il concetto di tipo
strutturato.
• In primis, i tipi strutturati sono solo ottenuti
mediante costruttori di tipo, ossia sono tutti costruiti
dal programmatore attraverso alcuni meccanismi
fondamentali.
• Cominciamo con il costruttore ...
… array
•
Costruzione del tipo:
•
typedef
•
dichiazione di variabili di tipo anArray:
•
anArray
•
•
•
•
•
la dichiarazione
int lista[20];
va perciò interpretata come un’abbreviazione per
typedef
int
arrayAnonimo[20];
arrayAnonimo
lista
int
anArray[20];
lista1, lista2;
• Alcuni commenti e precisazioni
– La variabile che verrà usata come indice per indicare
l’elemento dell’array deve essere un tipo integral
– l’array è un costruttore di tipo, non un tipo:
– typedef
– typedef
int
double
anArray [20];
NuovaLista[30];
– danno luogo a due tipi diversi
e
• Quando esplicitare il nome del tipo e quando no?
• typedef double VettoreDiReali[20];
• VettoreDiReali
v1, v2, v3;
• invece della più semplice e altrettanto chiara:
• double
v1[20], v2[20], v3[20];
• Al contrario:
•
•
•
•
typedef
typedef
PioggeMensili
IndiciBorsa
double
PioggeMensili[12];
double
IndiciBorsa[12];
Piogge01, Piogge02, Piogge03;
Indici01, Indici02, Indici03;
• preferibile a:
• double
Piogge01[12], Piogge02[12], Piogge03[12],
Indici01[12], Indici02[12], Indici03[12];
• Gli elementi degli array possono essere di tipo
arbitrario (built-in, user-defined, semplice o
strutturato).
• È quindi possibile avere anche “array di array”:
• typedef
• typedef
int
Vettore[20];
Vettore MatriceIntera20Per20[20];
• MatriceIntera20Per20
matrice1;
• Oppure:
• typedef
int
• int
matrice1[20][20];
• int
matricetrid1[10][20][30];
Matrice20Per20[20][20];
• Per accedere agli elementi di matricetrid1
potremmo poi scrivere:
• matricetrid1[2][8][15]
• colore
ListaColori[10];
• Dall’array multidimensionale del C
• All’array monodimensionale della
macchina di von Neumann:
i 0
j
0
1
2
23 12 3
1
16 2
2
…
3
55
45 18
Cella
23
12
3
55
16
2
45
18
…
Indirizzo
1000
1001
1002
1003
1004
…
1000+4*j +i
….
Un brutto inconveniente
•
•
un array ha dimensioni fisse ===>
gli estremi di variabilità degli indici di un array non
possono cambiare durante l’esecuzione del programma.
•
Ciò certamente riduce la flessibilità del linguaggio: ad
esempio, consideriamo le stringhe di caratteri (parole):
siamo costretti a meccanismi del tipo:
•
typedef
•
String
•
Parole corte memorizzate in tali variabili lascerebbero una
notevole quantità di memoria (fisica) inutilizzata; d’altro
canto, prima della lettura di un nuovo carattere,
dovremmo anche prevedere istruzioni del tipo:
if
(LunghezzaParola == 30)
printf("Parola troppo lunga");
•
•
•
•
char
string[30];
Nome, Cognome;
Perché?
Perché il C e altri linguaggi sono basati sul principio
dell’allocazione statica della memoria: (per motivi di
efficienza) è il compilatore che decide quanta memoria è
necessaria e dove va allocata -tranne alcune eccezioni ...
Un parziale rimedio
•
•
#include <stdio.h>
•
•
•
•
main()
{
int
int
•
•
•
•
•
•
•
•
•
•
•
•
•
•
/* Programma InvertiSequenza */
Contatore;
Memorizzazione[100];
Contatore = 0;
while (Contatore < 100)
• /* si ricordi che il valore dell'indice di un array di 100
elementi varia da 0 a 99 */
{
scanf("%d", &Memorizzazione[Contatore]);
Contatore = Contatore + 1;
}
Contatore = Contatore – 1;
while (Contatore >= 0)
{
printf("%d\n", Memorizzazione[Contatore]);
Contatore = Contatore – 1;
}
}
E se invece di 100 la sequenza fosse lunga 1000?
La direttiva #define
•
/* Program InvertiSequenza */
•
•
#include <stdio.h>
#define LunghezzaSequenza 100
•
•
•
•
main()
{
int
int
•
•
•
•
•
•
•
•
•
•
•
•
Contatore;
Memorizzazione[LunghezzaSequenza];
Contatore = 0;
while (Contatore < LunghezzaSequenza)
{
scanf("%d", &Memorizzazione[Contatore]);
Contatore = Contatore + 1;
}
Contatore = Contatore – 1;
while (Contatore >= 0)
{
printf("%d\n", Memorizzazione[Contatore]);
Contatore = Contatore – 1;
}
•
}
•
NB: la stessa cosa non si poteva fare con la dichiarazione
const
Attenzione!
•
Se Array1 e Array2 sono variabili definite nel modo
seguente:
•
typedef
•
anArray
•
è scorretta l’istruzione:
•
Array2 = Array1;
•
Sarà necessaria un’istruzione ciclica che “scorra” i singoli
elementi dell’array
Capiremo a fondo il perché in seguito
•
int
anArray[10];
Array1, Array2;
Il seguente programma legge due stringhe composte da
esattamente 50 caratteri ciascuna e costruisce una terza stringa che
concatena le prime due in ordine alfabetico. Il programma stampa
poi la stringa così creata.
/* Programma ConcatenazioneStringhe */
#include <stdio.h>
#define LunghezzaArray 50
main()
{
int
i, j, k;
char TempCar;
char Array1[LunghezzaArray], Array2[LunghezzaArray];
/* Nella seguente dichiarazione il valore LunghezzaArray]*2 è un
valore costante calcolato a tempo di compilazione */
char ArrayConc[LunghezzaArray*2];
/* Legge la prima stringa assicurandosi che essa non superi la
dimensione dell'array, 50 caratteri /*
i = 0;
while (i < LunghezzaArray)
/* Si ricordi che il valore dell'indice di un array di LunghezzaArray
elementi è compreso fra 0 e LunghezzaArray–1 */
{
scanf(“ %c", &TempCar);
Array1[i] = TempCar;
i = i + 1;
}
/* Legge la seconda stringa assicurandosi che essa non superi la
dimensione dell'array, 50 caratteri /*
i = 0;
while (i < LunghezzaArray)
{
scanf(“ %c%, &TempCar);
Array2[i] = TempCar;
i = i + 1;
}
/* Confronta le due stringhe per capire quale precede l'altra in
ordine alfabetico */
i = 0;
while (i < LunghezzaArray && Array1[i] == Array2[i])
i = i+1;
if
(i == LunghezzaArray || Array1[i] < Array2[i])
/* Le due stringhe sono uguali o la prima precede la seconda in
ordine alfabetico */
{
k = 0; j = 0;
while (j < LunghezzaArray)
{
ArrayConc[k] = Array1[j];
k = k + 1;
j = j + 1;
}
j = 0;
while (j < LunghezzaArray)
{
ArrayConc[k] = Array2[j];
k = k + 1;
j = j + 1;
}
}
else
/* Se la seconda stringa precede la prima in ordine alfabetico, ossia
se (Array2[i] < Array1[i]) */
{
k = 0; j = 0;
while (j < LunghezzaArray)
{
ArrayConc[k] = Array2[j];
k = k + 1;
j = j + 1;
}
j = 0;
while (j < LunghezzaArray)
{
ArrayConc[k] = Array1[j];
k = k + 1;
j = j + 1;
}
}
/* Stampa la stringa ottenuta dalla concatenazione */
k = 0;
while (k < (LunghezzaArray*2)) {printf("%c", ArrayConc[k]);
k = k + 1;}
}
Un po’ noiosetto?
Si potrà far di meglio -in seguito- ma ricorrendo alle
“funzioni di libreria”.
Dati strutturati eterogenei
•
•
•
•
•
typedef
int
data [3];
???
impiegato: il nome, il cognome, il codice fiscale,
l’indirizzo, il numero di telefono, eventuali stipendio e
data di assunzione e via di seguito.
famiglia è costituita da un certo insieme di persone, da un
patrimonio, costituito a sua volta da un insieme di beni,
ognuno con un suo valore, da un reddito annuo, da spese
varie, …
Queste strutture informative sono eterogenee:
l’array non si presta a questo tipo di aggregazione.
• Il costruttore record (parola chiave struct in C) è la
risposta a questo tipo di esigenze
•
typedef struct
•
{
}
int Giorno;
int Mese;
int Anno;
Data;
•
•
•
•
typedef struct
•
Ovviamente si assume che i tipi String e Data siano già
stati precedentemente definiti.
•
typedef struct
{
}
{
•
•
•
}
String
Destinatario;
double
Importo;
Data
DataEmissione;
DescrizioneFatture;
int
Canale;
AccType Accensione;
double
CursoreLuminosita,
CursoreColore,
CursoreVolume;
CanaliTV;
•
dove :
•
typedef enum {On, Off}
AccType;
• Dal punto di vista del compilatore
Cella
Pinco Pallino
20,000.00
6
Luglio
2008
Indirizzo
P
1000
i
1001
n
1002
…
o
…
1029
20,000
1030
00
1031
6
1032
Luglio
1033
2008
1034
•
•
•
•
•
typedef struct {
•
}
String
String
int
char
Data
CatType
Dipendenti;
Nome;
Cognome;
Stipendio;
CodiceFiscale[16];
DataAssunzione;
Categoria;
•
dove CatType :
•
typedef enum {Dirigente, Impiegato, Operaio}
CatType;
• La dichiarazione di variabili procede poi come al
solito:
•
Dipendenti
Dip1, Dip2;
• oppure
•
•
•
•
•
•
•
•
struct
{
}
….
String Nome;
String Cognome;
int
Stipendio;
char CodiceFiscale[16];
Data DataAssunzione;
CatType
Categoria;
Dip1, Dip2;
•
•
•
L’accesso alle singole componenti del record
Così come l’accesso a un elemento di un array avviene mediante una
notazione funzionale
L’accesso al campo di un record avviene mediante la dot notation.
•
Dip1.Stipendio = Dip1.Stipendio + (Dip1.Stipendio*10) / 100;
•
I meccanismi di accesso a elementi di variabili strutturate si possono
combinare tra loro esattamente come si possono combinare i
costruttori di tipi:
•
•
•
Dip1.DataAssunzione.Giorno = 3;
Dip1.DataAssunzione.Mese = 1;
Dip1.DataAssunzione.Anno = 1993;
•
•
Se si vuole sapere se la prima lettera del cognome di Dip1 è A:
if (Dip1.Cognome[0] == 'A') …
•
DichiarazioneFatture
•
Si vuole sapere se la fattura numero 500 è stata emessa entro il 1991
o no, e in caso affermativo, qual è il suo importo:
if (ArchivioFatture[500].DataEmissione.Anno <= 1991)
printf("%d", ArchivioFatture[500].Importo);
else
printf("La fattura in questione è stata emessa dopo il
1991\n");
•
•
•
•
ArchivioFatture[1000];
• Una stranezza del C:
•
•
Mentre non è permesso scrivere un assegnamento globale tra
array (a = b) [meglio, non è ciò che ci si aspetterebbe]
l’istruzione
•
Dip2 = Dip1;
•
è lecita e fa esattamente ciò che ci si aspetta: copia l’intera
struttura Dip1 in Dip2, comprese le sue componenti che sono
costituite da array!
•
Il perché di questa stranezza risiede nel modo in cui in C sono
realizzati gli array e potrà essere capito tra breve
Il costruttore puntatore
• Ritorniamo sul problema dell’accesso alle variabili
• Nel linguaggio di von Neumann attraverso il loro
indirizzo (numero d’ordine di cella di memoria)
• Nei linguaggi di alto livello attraverso il loro nome:
più astratto -e più mnemonico• Però in taluni casi si vuol fare riferimento a celle
diverse mediante lo stesso simbolo:
• a[i] denota una cella diversa a seconda del valore di i
• Introduciamo ora un nuovo meccanismo di accesso
simbolico legato all’indirizzo delle variabili
(potente e indispensabile in C -non così in altri
linguaggi- ma pericoloso e spesso difficile!)
• typedef
TipoDato
*TipoPuntatore;
P
Valore di tipo
TipoDato
Dereferenziazione: *P indica la cella di memoria il cui
indirizzo è contenuto in P. Essa può essere utilizzata
esattamente come una qualsiasi altra variabile di tipo
TipoDato.
typedef TipoDato
TipoPuntatore
TipoDato
*TipoPuntatore;
P;
x;
le seguenti istruzioni sono ammissibili:
*P = x;
x = *P;
P
14
x
23
(a)
P
23
x
23
(b)
P
14
x
14
(c)
Il compito del compilatore …
• … è facilissimo:
• infatti:
• accedere a una variabile mediante
puntatore, altro non è che accedere al
contenuto di una cella in modo indiretto
attraverso il suo indirizzo:
Identificatore
indirizzo
contenuto
P
1034
2435
…
…
x
2132
…
???
2435
10000
x = *P
LOAD@ 1034; STORE 2132
*P = x
LOAD
2132; STORE@ 1034
L’operatore unario & significa “indirizzo di” ed è il duale
dell’operatore ‘*’.
(Coincidenza non casuale con l’utilizzo della scanf)
Date le seguenti dichiarazioni di tipo e di variabili:
typedef TipoDato
*TipoPuntatore;
TipoPuntatore
P, Q;
TipoDato
y, z;
è possibile [NB: non in Pascal, Modula-2, Ada, …!] assegnare
al puntatore P e al puntatore Q l’indirizzo delle variabili y e z,
rispettivamente, tramite le seguenti istruzioni:
P = &y;
Q = &z;
(y e z sono di tipo TipoDato mentre P e Q sono puntatori a
variabili di tipo TipoDato.)
E’ possibile eseguire anche il seguente assegnamento:
P = Q;
y
P
14
Q
z
23
(a)
P
y
14
Q
z
23
(b)
(a) Stato della memoria della macchina dopo l’esecuzione
delle istruzioni P = &y; Q = &z. (b) Effetto dell’esecuzione
dell’istruzione P = Q (iniziando dallo stato di parte (a))
Si noti la differenza tra le istruzioni P = Q e *P = *Q
Il costrutto denotato dal simbolo * è a tutti gli effetti un
costruttore di tipo:
Alcune dichiarazioni lecite:
typedef TipoDato
*TipoPuntatore;
typedef AltroTipoDato
*AltroTipoPuntatore;
TipoDato
*Puntatore;
/* forma abbreviata: unifica una dichiarazione di tipo e una
dichiarazione di variabile.*/
TipoDato
**DoppioPuntatore;
TipoPuntatore
P, Q;
AltroTipoPuntatore
P1, Q1;
TipoDato
x, y;
AltroTipoDato
z, w;
istruzioni corrette:
Puntatore = &y;
DoppioPuntatore = &P;
Q1 = &z;
P = &x;
P = Q;
*P = *Q;
*Puntatore = x;
P = *DoppioPuntatore;
z = *P1;
Puntatore = P;
istruzioni scorrette:
P1 = P;
(warning)
w = *P;
(error)
*DoppioPuntatore = y;
(warning)
Puntatore = DoppioPuntatore; (warning)
*P1 = *Q;
(error)
Una tipica abbreviazione del C ...
Sia:
typedef struct
{
}
int
PrimoCampo;
char
SecondoCampo;
TipoDato;
Accesso normale alla componente PrimoCampo della
variabile cui P punta:
(*P).PrimoCampo
accesso abbreviato:
P–>PrimoCampo = 12;
Riassumendo e completando
Le operazioni applicabili a variabili puntatori sono le seguenti:
• l’assegnamento dell’indirizzo di una variabile tramite
l’operatore unario & seguito dal nome della variabile;
• l’assegnamento del valore di un altro puntatore;
• l’assegnamento del valore speciale NULL. Se una
variabile puntatore ha valore NULL, *P è indefinito: P
non punta ad alcuna informazione significativa.
• l’operazione di dereferenziazione, indicata
dall’operatore *;
• il confronto basato sulle relazioni ==, !=, >, <, <=, >=;
• operazioni aritmetiche ( da altri linguaggi!)
• l’assegnamento di indirizzi di memoria a seguito di
operazioni di allocazione esplicita di memoria (gli ultimi
due casi verranno trattati in seguito);
E’ sempre meglio fare esplicitamente l’assegnamento per ogni
puntatore (possibilmente inizializzandolo con lo speciale valore
NULL), benché alcune implementazioni del linguaggio C possano
implicitamente assegnare il valore NULL a ciascun nuovo puntatore.
Ciò garantisce che il programma venga eseguito correttamente sotto
qualsiasi implementazione del linguaggio.
Anche se l’importanza -e la criticità- dell’uso dei puntatori in
C si chiarirà strada facendo … vediamone una prima
applicazione
Il programma che segue tratta informazioni riguardanti i lavoratori di
una fabbrica usando dati contenuti in due variabili: la prima,
denominata DatiLavoratori, contiene informazioni su diversi
lavoratori (dirigenti, impiegati, operai); la seconda, chiamata
Management, permette di accedere rapidamente ai dati relativi ai
dirigenti contenuti nella prima struttura dati. Si supponga di voler
stampare i cognomi e gli stipendi di tutti i dirigenti che guadagnano
più di 5 milioni: anziché selezionare tutti gli elementi dell’intero array
DatiLavoratori sulla base della categoria del lavoratore,
immagazziniamo nell’array Management (verosimilmente molto più
corto) i puntatori a tutti gli elementi di DatiLavoratori che sono
dirigenti (ciò, naturalmente, renderà l’aggiornamento dei due array
più complicato, per esempio quando viene assunta una nuova
persona).
Il frammento di codice di questo esempio presuppone che i dati
contenuti nelle variabili DatiLavoratori e Management siano già
disponibili, e restituisce il cognome e lo stipendio dei dirigenti che
guadagnano più di 5 milioni.
/* Programma Dirigenti */
#include <stdio.h>
main()
{
typedef enum
typedef struct
{
{
}
Lavoratore
Lavoratore
dirigente, impiegato, operaio CatLav;
char
Nome[30];
char
Cognome[30];
CatLav Categoria;
int
Stipendio;
char
CodiceFiscale[16];
Lavoratore;
DatiLavoratori[300];
*Management[10];
...
i = 0;
while (i < 10)
{
if (Management[i]–>Stipendio > 5000000)
{
j = 0;
while (j < 30)
{
printf("%c", Management[i]–>Cognome[j]);
j = j + 1;
}
printf("%d \n", Management[i]–>Stipendio);
}
}
i = i + 1;
}
Attenzione ai “rischi” dei puntatori
Effetti collaterali (side effects) (non facilmente
completamente prevedibili durante la programmazione):
e
*P = 3;
*Q = 5;
P = Q;
/* a questo punto *P = 5 */
*Q = 7;
A questo punto *Q = 7, ma anche, in modo più “subdolo”, *P =
7. Comportamento diverso rispetto a:
x = 3;
y = 5;
x = y;
y = 7;
Effetto collaterale perché un assegnamento esplicito alla
variabile puntata da Q determina un assegnamento nascosto
(quindi con il rischio di non essere voluto) alla variabile
puntata da P.
In realtà questo è un caso particolare di aliasing, ovvero
del fatto che uno stesso oggetto viene identificato in due
modi diversi.
Ulteriori rischi, verranno alla luce in seguito (i puntatori sono
una “palestra di trucchi C”, ricca di usi … ed abusi)
Siamo ora in grado di capire certe (apparenti?) stranezze del C:
in C esiste una parentela molto stretta tra array e puntatori. Anzi, gli
array sono di fatto realizzati mediante puntatori. Vediamo meglio
•
•
•
•
•
•
•
•
•
•
L’operatore sizeof produce il numero di byte occupati da
ciascun elemento di un array o da un array nel suo complesso.
Supponendo di lavorare su un calcolatore che riserva quattro
byte per la memorizzazione di un valore int e ipotizzando di
aver dichiarato
int
a[5];
allora
sizeof(a[2])
restituisce il valore 4 e
sizeof(a)
restituisce il valore 20.
Il nome di una variabile di tipo array viene considerato in C
come l’indirizzo della prima parola di memoria che contiene il
primo elemento della variabile di tipo array (lo 0-esimo …).
Se ne deduce:
 a “punta” a una parola di memoria esattamente come fa una
variabile dichiarata di tipo puntatore;
 a punta sempre al primo elemento della variabile di tipo
array (è un puntatore “fisso” al quale non è possibile
assegnare l’indirizzo di un’altra parola di memoria).
•
•
C consente di eseguire operazioni di somma e sottrazione su
puntatori.
Se una variabile p punta a un particolare tipo di dato,
l’espressione p+1 fornisce l’indirizzo in memoria per l’accesso o
per la corretta memorizzazione della prossima variabile di quel
tipo.
Se p e a forniscono l’indirizzo di memoria di elementi di tipo
opportuno, p+i e a+i forniscono l’indirizzo di memoria dell’iesimo elemento successivo di quel tipo (riflette una tipica
struttura HW che vedremo nel corso successivo).
Riprendendo in considerazione l’array a dichiarato in precedenza:
 se i è una variabile intera, la notazione a[i] è equivalente a
*(a+i).
Analogamente, se p è dichiarato come puntatore a una variabile di
tipo int:
 supposta i come variabile intera, la notazione p[i] è
equivalente a *(p+i).
Ne segue che:
•
•
p=a
p = a+1
•
•
•
mentre non sono ammessi assegnamenti ad a del tipo:
a = p;
a = a +1;
•
•
•
•
è equivalente a
è equivalente a
p = &a[0];
p = &a[1];
•
Infine
•
•
Se p e q puntano a due diversi elementi di un array,
p–q restituisce un valore intero pari al numero di elementi
esistenti tra l’elemento cui punta p e l’elemento cui punta q.
non la differenza tra il valore dei puntatori.
Supponendo infatti che il risultato di p–q sia pari a 3 e
supponendo che ogni elemento dell’array risulti memorizzato in 4
byte, la differenza tra l’indirizzo contenuto in p e l’indirizzo
contenuto in q darebbe 12.
•
•
•
•
Abbiamo cominciato ad “assaggiare” alcune di quelle
peculiarità del C tanto amate dagli “specialisti” e tanto
pericolose:
Cave C, ossia non lasciarsi attrarre dai vari trucchetti e
abbreviazioni (che costano gravi errori anche agli …
esperti)
Un ultimo importante concetto sui tipi di dato (nella
programmazione):
compatibilità e verifica di compatibilità tra tipi
•
•
•
Il concetto di tipo è un importante strumento di
astrazione: separa la visione esterna di un’informazione
dalla rappresentazione interna.
Come “mettere insieme” informazioni di tipo diverso?
In prima istanza vale il principio del “non sommare le
pere con le mele”:
– Ha senso sommare un nome ad un conto corrente?
– Assegnare il valore 10 a un indirizzo?
•
Ad un’analisi più attenta, però, nascono interrogativi un
po’ meno banali:
– Se ridefinisco età come intero e temperatura come intero
non dovrei assegnare un’età a una temperatura
– Ma un intero a un reale?
– Un reale a un intero?
– …
•
•
•
Non è possibile dare regole di compatibilità tra tipi che
si adattino in maniera naturale a tutte le situazioni
immaginabili (coperta corta).
Però è almeno raccomandabile dare regole precise -non
tutti i linguaggi lo fanno- per evitare rischi di
interpretazioni ed errori diversi da diversi “attori” -uomini
o macchine.
Vediamo allora le principali regole del C (precise ma
anche molto “liberali”)
•
Espressioni che coinvolgono elementi eterogenei in
tipo
•
Un’espressione aritmetica come x + y è caratterizzata dal valore
e dal tipo del risultato.
Il tipo degli operandi condiziona l’operazione che deve essere
eseguita. (A operandi di tipo int si applica l’operazione di
somma propria di tale tipo, diversa è l’operazione di somma che
si applica a operandi di tipo float ecc.)
Se x è di tipo short e y di tipo int è necessario convertire una
delle due variabili per rendere omogenea l’espressione e
applicare la corretta operazione. x viene temporaneamente
convertita in int e la somma tra interi restituisce un risultato
intero.
In generale sia x op y.
Regole di conversione implicita:
– ogni variabile di tipo char o short (incluse le rispettive
versioni signed o unsigned) viene convertita in variabile
di tipo int;
– se dopo l’esecuzione del passo 1 l’espressione risulta ancora
eterogenea rispetto al tipo degli operandi coinvolti, rispetto
alla seguente gerarchia
int < long < unsigned < unsigned long < float < double
< long double
•
•
•
•
•
–
–
si converte temporaneamente l’operando di tipo inferiore facendolo
divenire di tipo superiore;
Il risultato dell’espressione avrà tipo uguale a quello di più alto
livello gerarchico.
– NB: in C è dunque possibile sommare un carattere - o un
tipo enumerato- ad un intero: prevale la visione “concreta”
che interpreta tutte le sequenze di bit come numeri
– Non così in altri linguaggi (facciamo finta che …)
•
Assegnamenti che coinvolgono elementi eterogenei in
tipo
•
Le regole di conversione implicita esposte vengono utilizzate
anche per la valutazione di assegnamenti tra variabili eterogenee
in tipo:
double
d;
int
i;
L’istruzione
d = i;
provoca una temporanea conversione del valore dell’intero i a
double e successivamente l’assegnamento di tale valore
double a d.
L’esecuzione dell’istruzione
i = d;
comporta invece, normalmente, una perdita di informazione. Il
valore di d subisce infatti un troncamento alla parte intera con
perdita della parte decimale.
•
•
•
•
•
•
•
•
•
Puntatori e tipizzazione delle variabili puntate
•
Viene segnalato dal compilatore il tentativo di utilizzo congiunto
di puntatori dichiarati come puntanti a dati di tipo differente - e
spesso il programmatore se ne ....
•
Un’ultima importante osservazione
•
Le regole di uso dei tipi del C sono tutte verificabili dal
compilatore -si dice “a compile-time”Questa caratteristica viene anche indicata come tipizzazione
forte; non tutti i linguaggi ne sono dotati
•
•
Generalizzando questa osservazione
•
Molti linguaggi preferiscono, laddove possibile, eseguire
operazioni (verifiche di errori, allocazione di memoria) a
compile time piuttosto che a run-time:
Maggiore efficienza ma soprattutto maggiore sicurezza
•
•
•
•
•
La verifica -dell’assenza- di un errore a compile time, ne
garantisce effettivamente l’assenza:
Errori di sintassi, di tipo (in C) sono errori verificabili a compiletime.
Non tutti gli errori però hanno questa -piacevole- caratteristica:
Alcuni tipici errori a run-time
– La divisione per '0'. Infatti l'operazione di divisione, sia
intera che reale, è definita - cioè applicabile - solo al
caso in cui il divisore sia diverso da '0'. Ma ciò, in
generale, non è prevedibile prima dell'esecuzione.
– L'uso di un indice di un array con valore al di fuori del
suo campo di variabilità:
–
int
V1[100];
–
permette al compilatore di segnalare che l'istruzione:
–
V1[132] = 190
–
è un errore, ma il caso più generale:
–
scanf (&i); V1[i] = 190
–
non è verificabile durante la compilazione perché
dipende dalla lettura del dato i.
•
Se eseguo il programma 1, 2, n volte e non viene
segnalato un errore a run-time ciò non è garanzia di
immunità dall’errore!
•
Quale tempo per
» x = z / (y - y)
» ?
I sottoprogrammi
• I meccanismi di astrazione sui dati visti finora non
corrispondono in pieno al concetto di tipo di dato
astratto:
• mancano le operazioni:
•
•
•
•
•
•
•
•
typedef struct {
int
NumFatture;
DescrizioneFatture
Sequenza[MaxNumFatture];
} ElencoFatture;
typedef struct {
int
… come sopra
} ElencoCosti;
MaxNumFatture e MaxNumCosti costanti
DescrizioneFatture e DescrizioneCosti tipi definiti (in
precedenza):
•
Consideriamo operazioni come “Calcolo del fatturato
complessivo”, “Fatturato relativo al periodo x”, “Calcolo della
somma dei costi complessivi” ecc.
•
•
Un codice del tipo
RisultatoDiGestione = FatturatoTotale (ArchivioFatture) –
SommaCosti (ArchivioCosti);
•
dove ArchivioFatture e ArchivioCosti sono di tipo
ElencoFatture ed ElencoCosti
•
è certo meglio (+ astratto, + …) di
•
•
FatturatoTotale = 0;
for (Cont = 0; Cont < ArchivioFatture.NumFatture;
Cont++)
{
FatturatoTotale = FatturatoTotale +
ArchivioFatture.Sequenza[Cont].Importo;
}
SommaCosti= 0;
for (Cont = 0; Cont < ArchivioCosti.NumCosti; Cont++)
{
SommaCosti = SommaCosti +
•
•
•
•
•
•
•
•
ArchivioCosti.Sequenza[Cont].Importo;
•
•
}
RisultatoDiGestione = FatturatoTotale – SommaCosti;
•
•
•
•
•
•
•
Però la macchina C non sa fare operazioni del genere
(così come non sa a priori che cosa significa fattura):
occorre “insegnarglielo”, così come le si insegna che
cos’è una fattura
I sottoprogrammi sono lo strumento per realizzare
astrazioni sulle operazioni (concettualmente sono di due
tipi)
Vediamone le caratteristiche principali
Cominciamo con l’arricchire la struttura di un
programma completo C:
Alle già note parti
 direttive;
 main, a sua volta è costituito da una parte dichiarativa e
una esecutiva.
Aggiungiamo ora:
 una parte dichiarativa globale compresa fra la parte
direttive e il programma principale.
 contiene la dichiarazione di tutti gli elementi che sono
condivisi, ossia usati in comune, dal programma principale e
dai sottoprogrammi. Tali elementi possono essere costanti, tipi,
variabili e altro ancora che verrà introdotto più avanti.
 una successione di definizioni di sottoprogrammi  funzioni o
procedure , a seguire il programma principale. Il main risulta
un -particolare- sottoprogramma tra gli altri
 il programma principale e ciascun sottoprogramma possono
usare tutti e soli gli elementi che sono stati dichiarati nella
loro propria parte dichiarativa, nonché quelli che sono stati
dichiarati nella parte dichiarativa globale
•
Le funzioni (definizione e uso)
•
Le operazioni astratte considerate finora sono funzioni nel senso
matematico del termine: hanno un dominio e un codominio
Analogo -non identico! Concetto ritroviamo in C.
•
•
Definizione delle funzioni
(attenzione: In C spesso si usa il termine funzione come
sinonimo di sottoprogramma)
•
la sua definizione (semplificata) consiste in:
 una testata (header);
 due parti, sintatticamente racchiuse fra parentesi graffe:
– la parte dichiarativa (detta parte dichiarativa locale);
–
•
•
•
•
•
•
•
la parte esecutiva (detta corpo della funzione).
La testata contiene le informazioni più rilevanti per l’uso
corretto del sottoprogramma:
tipo del risultato,
identificatore del sottoprogramma,
lista dei parametri - formali- cui la funzione viene applicata
con il relativo tipo;
(dominio e codominio della funzione)
Ogni parametro formale è un identificatore di tipo seguito da un
identificatore.
Una funzione non può restituire array o funzioni ma può
restituire un puntatore a qualsiasi tipo.
•
Alcuni esempi di testate di funzioni :
•
•
int
boolean
•
•
•
•
•
FatturatoTotale (ElencoFatture
par)
Precede (StringaCaratteri
par1,
StringaCaratteri
par2)
boolean
Esiste (int par1, SequenzaInteri par2)
• /* Stabilisce se il primo parametro, di tipo intero, appartiene
all'insieme di interi contenuti nel secondo parametro: una
sequenza di interi */
MatriceReali10Per10
*MatriceInversa
(MatriceReali10Per10 *par)
Dopo la testata seguono le dichiarazioni locali.
ci limiteremo inizialmente alle variabili locali
Infine si trova il corpo della funzione costruito con le medesime regole
sintattiche del programma principale. Al suo interno però si trova
normalmente un’istruzione di return ( parola chiave return seguita
da una espressione.
•
Un paio di esempi
•
•
•
int
{
int
•
•
•
•
•
}
•
•
•
int
{
int
•
•
•
•
•
FatturatoTotale (ElencoFatture
parametro)
Totale, Cont;
Totale = 0;
for (Cont = 0; Cont < parametro.NumFatture; Cont++)
Totale = Totale + parametro.Sequenza[Cont].Importo;
return
Totale;
RadiceIntera (int
cont;
cont = 0;
while (cont*cont <= par)
cont = cont + 1;
return (cont–1);
}
par)
• Chiamata delle funzioni
•
•
•
Identificatore della funzione seguito dalla lista dei parametri attuali.
Ogni parametro può essere un’espressione qualsiasi, eventualmente
contenente un’altra chiamata di funzione. La corrispondenza tra
parametri segue l’ordine della dichiarazione
Inoltre il tipo dei parametri attuali deve essere compatibile con il tipo
dei corrispondenti parametri formali.
La stessa funzione può essere chiamata in diversi punti dello stesso
programma con diversi parametri attuali.
•
•
•
•
•
•
x = sin(y) – cos(PiGreco – alfa);
x = cos(atan(y) – beta);
x = sin(alfa);
y = cos(alfa) – sin(beta);
z = sin(PiGreco) + sin(gamma);
RisultatoDiGestione = FatturatoTotale (ArchivioFatture) SommaCosti (ArchivioCosti);
•
•
Det1 = Determinante (Matrice1);
Det2 = Determinante (MatriceInversa (Matrice2));
•
•
•
TotaleAssoluto = Sommatoria (Lista1) + Sommatoria (Lista2);
ElencoOrdinato = Ordinamento (Elenco);
OrdinatiAlfabeticamente = Precede (nome1, nome2);
• Prototipo delle funzioni
•
•
•
•
•
•
All’interno di un programma C una funzione può essere chiamata
purché risulti definita oppure dichiarata.
definizione e dichiarazione non sono termini equivalenti
la dichiarazione di una funzione (prototipo) si limita a richiamarne la
testata.
Utile quando la chiamata di una funzione precede, nel codice, la
definizione della funzione, oppure le funzioni utilizzate da un
programma sono definite in file propri del sistema C (e.g., le funzioni
di libreria).
Aiuta il compilatore ed è buono stile di programmazione
Riassumendo, la parte dichiarativa del programma principale e quella
dichiarativa di una funzione contengono i seguenti elementi:




dichiarazioni di costanti;
dichiarazioni di tipo;
dichiarazioni di variabili;
prototipi delle funzioni.
•
Esaminiamo ora in dettaglio come avviene la:
•
Esecuzione delle funzioni e passaggio dei parametri
•
•
•
#include <stdio.h>
#define MaxNumFatture
1000
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
typedef char
typedef struct
typedef struct
main()
{
ElencoFatture
int
int
/* Parte dichiarativa globale */
String [30];
{
String
Indirizzo;
int
ammontare;
Data
DataFattura;
}
DescrizioneFatture;
{
int
NumFatture;
DescrizioneFatture
Sequenza[MaxNumFatture];
}
ElencoFatture;
ArchivioFatture1, ArchivioFatture2;
Fatt1, Fatt2, Fatt;
FatturatoTotale (ElencoFatture parametro);
•
/* Prototipo della funzione FatturatoTotale */
....
Fatt1 = FatturatoTotale(ArchivioFatture1);
Fatt2 = FatturatoTotale(ArchivioFatture2);
Fatt = Fatt1 + Fatt2;
....
}
•
•
•
•
•
•
•
•
/* Programma Contabilità */
•
/* Parte direttiva */
int
{
FatturatoTotale (ElencoFatture
int
....
return
...
}
/* Fine del main del programma Contabilità */
Totale, Cont;
Totale;
parametro)
Ambienti di esecuzione, macchine astratte master e slave
ArchivioFatture1
Parametro
ArchivioFatture2
Totale
Fatt1
Fatt2
Cont
FatturatoTotale
Se poi, per valutare un parametro attuale, fosse necessario
calcolare (chiamare) un’ulteriore funzione (ad esempio):
x = sin (atan (y) – acos (z));
La macchina esegue qualcosa del genere:
temp1 = atan (y); temp2 = acos (z);
x = sin (temp1 – temp2);
Le procedure
Non tutte le operazioni astratte sono formalizzabili come funzioni nel
senso matematico del termine:
• Inserimento di una fattura in un archivio
typedef enum
typedef struct
TipoSemaforo
{VerdeSinistra, VerdeDestra} TipoStato;
{
TipoStato
Stato;
int
CodaSinistra;
int
CodaDestra;
} TipoSemaforo;
Semaforo;
AggiornaSemaforo :
•
diminuisce di un valore costante il campo CodaSinistra o
CodaDestra a seconda che lo stato del semaforo sia VerdeSinistra o
VerdeDestra;
•
legge dal terminale i valori NuoviArriviSinistri e
NuoviArriviDestri e li somma, rispettivamente, a CodaSinistra e
CodaDestra;
•
dà al campo Stato il valore VerdeSinistra se
CodaSinistra > Coda Destra e viceversa.
Vogliamo ordinare un archivio di fatture, ad esempio in ordine
crescente di data. L’effetto di una chiamata
Ordina (archivio),
con archivio del tipo ElencoFatture non deve essere il valore di
tipo ElencoFatture ottenuto ordinando gli elementi contenuti in
archivio. Si vuole invece che proprio il contenuto della variabile
archivio venga ordinato dall’operazione ordina (archivio). In
altre parole, se CostruisciValoreOrdinato(archivio) fosse una
funzione che produce come risultato un valore di tipo
ElencoFatture il cui campo Sequenza è una permutazione del
campo Sequenza di archivio e i cui elementi sono ordinati per
data crescente, l’effetto desiderato di Ordina(archivio) sarebbe
quello dell’istruzione
archivio = CostruisciValoreOrdinato (archivio).
Per casi del genere il tipo di sottoprogramma adatto è la
procedura
Da un punto di vista sintattico le procedure si distinguono dalle
funzioni per:
• Il “tipo speciale” void del risultato
• La chiamata che è un’istruzione e non produce un valore -e
non si trova quindi all’interno di un’espressione
/*Programma Contabilità */
#include<stdio.h>
#define
MaxNumFatture 1000
...
typedef struct
{
String
indirizzo;
int
ammontare;
Data
DataFattura;
} DescrizioneFatture;
typedef struct
{
int
NumFatture;
DescrizioneFatture Sequenza[MaxNumFatture];
} ElencoFatture;
ElencoFatture
ArchivioFatture;
main()
{
Data
DataOdierna;
DescrizioneFatture
Fattura1, Fattura2;
void
InserisciFattura (DescrizioneFatture
Fattura);
boolean
Precede (Data Num1, Data Num2);
…
/* Sequenza di istruzioni che leggono i datidi una fattura in Fattura1 */
InserisciFattura(Fattura1);
...
/* Sequenza di istruzioni che leggono i dati di una fattura in
Fattura2 */
if (Precede(Fattura2.DataEmissione, DataOdierna))
InserisciFattura (Fattura2);
...
}
void
InserisciFattura (DescrizioneFatture Fattura)
{
if (ArchivioFatture.NumFatture == MaxNumFatture)
printf("L'archivio è pieno.\n");
else
{
ArchivioFatture.NumFatture = ArchivioFatture.NumFatture + 1;
ArchivioFatture.Sequenza[ArchivioFatture.NumFatture–1] = Fattura;
}
}
•
La differenza fondamentale tra procedure e funzioni la si
afferra osservando la gestione della memoria durante
l’esecuzione
ArchivioFatture
Ambiente globale
DataOdierna
Fattura
...
Fattura1
Fattura2
Ambiente locale di
InserisciFattura
Ambiente di main di
Programma Contabilità
L’esecuzione di una procedura non produce un risultato ma
cambia lo stato del programma -agendo sull’ambiente
globale:
le varie procedure e funzioni -main compreso- non possono
accedere agli ambienti locali altrui: la “comunicazione”
avviene o passandosi parametri e risultati o attraverso
l’ambiente globale/comune
(… + un altro modo che viene esposto ora)
Supponiamo ora di voler eseguire diversi inserimenti di nuove fatture in
diversi archivi.
A prima vista basterebbe:
void InserisciFattura(
DescrizioneFatture Fattura,
ElencoFatture
ArchivioFatture)
/*In questa versione della procedura, sia la fattura da inserire sia
l'archivio in cui inserirla sono dei parametri */
{
if
(ArchivioFatture.NumFatture == MaxNumFatture)
printf("L'archivio è pieno.");
else
{
ArchivioFatture.NumFatture =
ArchivioFatture.NumFatture + 1;
ArchivioFatture.Sequenza[ArchivioFatture.NumFatture–1] =
Fattura;
}
}
/*Fine della procedura InserisciFattura */
Esaminiamo però l’effetto della chiamata:
InserisciFattura (Fattura1, ArchivioFatture5);
L’esecuzione della procedura produce l’effetto di inserire il valore di
Fattura in ArchivioFatture, ma non in ArchivioFatture5, che è invece
rimasto esattamente come prima!
Infatti l’operazione astratta della procedura viene eseguita sul parametro
formale, non sul corrispondente parametro attuale.
Per ottenere l’effetto di modificare il valore dei parametri attuali, alcuni
linguaggi, come il Pascal, offrono al programmatore un diverso modo
di passare i parametri tra chiamante e chiamato: il passaggio parametri
per indirizzo. Esso si contrappone al modo usato finora, detto passaggio
per valore.
Quando un parametro è passato per indirizzo, al momento della chiamata
del sottoprogramma, invece di copiare il valore del parametro attuale nella
corrispondente cella del parametro formale, si copia semplicemente
l’indirizzo della cella contenente il parametro attuale in un’opportuna cella
attribuita al parametro formale.
Parametri attuali
x
Ind(x) = 2034
Ind(y) = 1004
243
Parametri formali
A
Passaggio
243
per valore
y
A
413
1004
Passaggio per
indirizzo
Quando, durante l’esecuzione, la macchina asservita trova un
riferimento al parametro formale, essa accede alla cella del parametro
attuale (non a quella del parametro formale!) tramite l’indirizzo che le
era stato precedentemente passato: meccanismo dell’indirizzamento
indiretto.
In C la modalità di passaggio dei parametri a un
sottoprogramma è sempre quella di passaggio per
valore.
Dobbiamo arrangiarci facendo noi in qualche modo ciò
che in altri linguaggi fa la macchina astratta
automaticamente.
• utilizzando il costruttore di tipo puntatore per
la definizione dei parametri formali della
funzione;
• usando l’operatore di dereferenziazione di
puntatore (operatore * o –>) all’interno del
corpo della funzione;
• passando al momento della chiamata della
funzione come parametro attuale un indirizzo
di variabile (usando eventualmente l’operatore
& - e così scopriamo finalmente il perché di &
nella scanf)).
/*Programma Contabilità */
...
main()
{
ElencoFatture
ArchivioFatture5;
/* Si noti che ArchivioFatture5 è in questo caso una variabile locale
del main. Appartiene all'ambiente del programma chiamante */
Data
DataOdierna;
DescrizioneFatture
Fattura1, Fattura2;
void InserisciFattura (
DescrizioneFatture Fattura,
ElencoFatture
*PointToArchivioFatture);
/* Prototipo della procedura InserisciFattura */
boolean
Precede (Data
Num1, Data Num2);
/* Prototipo della funzione Precede */
...
/* Sequenza di istruzioni che leggono i dati di una
fattura in Fattura1 */
InserisciFattura (Fattura1, &ArchivioFatture5);
/* Chiamata della procedura InserisciFattura: alla procedura viene
passato il valore di Fattura1 e l'indirizzo di ArchivioFatture5 */
...
/* Sequenza di istruzioni che leggono i dati di una
fattura in Fattura2 */
if
(Precede (Fattura2.DataEmissione, DataOdierna)
InserisciFattura (Fattura2, &ArchivioFatture5);
/* Nuova chiamata della procedura InserisciFattura: alla procedura
viene passato il valore di Fattura2 e -nuovamente- l'indirizzo di
Archivio Fatture5 (ma potrebbe essere un altro) */
...
}
/* Definizione della procedura InserisciFattura */
void InserisciFattura (DescrizioneFatture
Fattura,
ElencoFatture
*PointToArchivioFatture)
/* In questa versione della procedura, la fattura da inserire e l'indirizzo
dell'archivio in cui inserirla sono dei parametri */
{
if (PointToArchivioFatture–>NumFatture == MaxNumFatture)
/* PointToArchivioFatture è una variabile che punta a una struttura avente
un campo di nome NumFatture.
La notazione PointToArchivioFatture–> NumFatture si riferisce al campo
NumFatture della variabile strutturata cui punta PointTo ArchivioFatture */
printf ("L'archivio è pieno.\n");
else
{
PointToArchivioFatture–>NumFatture =
PointToArchivioFatture–>NumFatture + 1;
PointToArchivioFatture–>
Sequenza[PointToArchivioFatture–>NumFatture – 1] = Fattura;
}
}
• Dopo aver appreso gli aspetti fondamentali dei
sottoprogrammi,
• esaminiamo ora qualche dettaglio,
approfondimento, precisazione.
•
Riepiloghiamo, in primis, la struttura generale di un
programma C :
 una parte direttiva;
 una parte dichiarativa globale che comprende:
–
–
–
–
dichiarazioni di costanti;
dichiarazioni di tipi;
dichiarazioni di variabili;
prototipi di procedure e funzioni;
 un programma principale;
 definizioni di funzioni o procedure.
•
Un programma C è un insieme di funzioni e variabili proprie
dell’ambiente globale del programma. Una delle funzioni deve
essere identificata come main.
 le procedure e il main possono essere considerati casi
particolari di funzioni (infatti nel gergo C, funzione è
spesso sinonimo di sottoprogramma generale).
 main può avere parametri di ingresso come ogni altra
funzione: però noi non trattiamo questo aspetto
 Un main deve esistere: l’esecuzione del programma globale
inizia con la prima istruzione della parte esecutiva del
main.
Il concetto di blocco in C (non dissimile da Pascal e altri)
Con la raccomandazione di non abusarne ...
• Un blocco è composto da due parti sintatticamente
racchiuse tra parentesi graffe:
 una parte dichiarativa (facoltativa);
 una sequenza di istruzioni.
• Diversi blocchi possono comparire internamente al
main o alle funzioni che compongono un
programma C. I blocchi possono risultare paralleli
o annidati
•
•
/* Programma ComplessoInStruttura */
#include <stdio.h>
•
•
•
•
•
•
•
•
int
char
int
main ()
{
int
int
/* Parte dichiarativa globale */
g1, g2;
g3;
f1 (int par1, int
par2); ...
a, b;
f2 (int par3, int
par1); ...
•
•
•
•
{
char
...
a, c;
•
•
•
•
•
/* blocco2 annidato nel blocco1 */
{
float
...
a;
}
/* Fine blocco2 */
•
}
/* Fine blocco1 */
•
/* blocco1 */
}
/* Fine main */
•
•
•
•
int
{
•
•
•
f1(int
par1, int
int
...
d;
par2)
•
/* blocco3 */
•
/* Fine blocco3 */
/* blocco4 */
{
int
...
•
e;
}
•
•
•
{
int
...
•
d;
}
/* Fine blocco4 */
•
}
/* Fine f1 */
•
•
•
•
•
int
{
f2 (int par3, int
int
...
•
/* Definizione della funzione f2 */
par4)
f;
}
/* Fine f2 */
•
Il modello a contorni della struttura di un programma
•
Le regole di visibilità
 il main può accedere alle variabili globali g1, g2 e g3 e a
quelle locali a e b. Il main può inoltre chiamare sia la
funzione f1 sia la funzione f2;
 il blocco blocco1 può accedere alle variabili globali g1,
g2, g3, alla variabile locale al main b e alle variabili a e c
del proprio ambiente (a è stata ridefinita da blocco1). Il
blocco blocco1 può inoltre richiamare sia f1 sia f2;
 il blocco blocco2 può accedere alle variabili globali g1,
g2, g3, alla variabile locale al main b, alla variabile del
blocco blocco1 c e alla variabile a del proprio ambiente (a
è stata ridefinita da blocco2). Il blocco blocco2 può inoltre
richiamare sia f1 sia f2;
 la funzione f1 può accedere alle variabili globali g1, g2 e
g3 e a quella locale d. La funzione f1 può inoltre chiamare
la funzione f2 o richiamare se stessa ma non può accedere
alle variabili a, b, c, f;
 il blocco blocco3 può accedere alle variabili globali g1,
g2, g3, alla variabile d, locale a f1, e alla variabile e del
proprio ambiente. Il blocco blocco3 può inoltre richiamare
sia f1 sia f2;
 il blocco blocco4 può accedere alle variabili globali g1,
g2, g3, e alla variabile d del proprio ambiente (d è stata
ridefinita da blocco4) il blocco blocco4 non può invece
accedere alla variabile e propria del blocco blocco3. Il
blocco blocco4 può inoltre richiamare sia f1 sia f2;
 la funzione f2 può accedere alle variabili globali g1, g2 e
g3 e a quella locale f. La funzione f2 può chiamare la
funzione f1 o richiamare se stessa e non può accedere alle
variabili a, b, c, d, e.
La durata delle variabili
variabili fisse o statiche (static): i loro valori vengono mantenuti anche
all’esterno del loro ambito di visibilità.
variabili automatiche (auto): i loro valori non vengono mantenuti
all’esterno del proprio ambito di visibilità.
Sono variabili fisse le variabili globali del programma
Sono, in generale, variabili automatiche quelle dichiarate a livello di
funzione (inclusi i parametri di ingresso e la variabile risultato) e quelle
dichiarate a livello di blocco.
Quando il controllo passa a una particolare funzione -o blocco- viene
allocato in memoria lo spazio per le variabili locali e tale spazio viene
rilasciato quando il controllo ritorna all’ambiente chiamante.
possono venire occupate in memoria, di volta in volta, celle
differenti per la rappresentazione della stessa variabile;
non vengono conservati i valori prodotti dalla precedente
esecuzione della funzione o del blocco.
Però:
int
{
f1(int
/* Definizione della funzione f1 */
par1, int par2)
static int d;
/* blocco3 */
{
int
e;
...
}
/* Fine blocco3
*/
/* blocco4 */
{
int
d;
...
}
/* Fine blocco4
*/
}
/* Fine f1 */
è possibile usare la variabile d (a durata fissa) ad esempio per contare il
numero di chiamate effettuate alla funzione f1 durante l’esecuzione del
programma globale.
La variabile d è allocata in memoria quando f1 viene chiamata per la
prima volta ma non viene distrutta al termine dell’esecuzione della
funzione.
Raccomandazione finale:
Usare i meccanismi e le regole di visibilità e di vita delle variabili
in modo semplice: pochi o niente annidamenti, poche o nessuna
variabile statica.
Il caso dei parametri di tipo array
Quando un array viene passato a una funzione come
parametro formale, l’indirizzo di base dell’array viene
passato “per valore” alla funzione.
Di fatto si realizza quindi un passaggio di parametro “per
indirizzo”: il parametro formale dichiarato nella testata
della funzione viene trattato come puntatore.
Esempi
typedef
double TipoArray[MaxNumElem]
le tre testate di funzione riportate di seguito sono in C di
fatto equivalenti:
double
double
double
sum (TipoArray a, int n)
/* n è la dimensione dell'array passato */
sum (double *a, int n)
sum (double a[ ], int n)
double
mul (double
a[ ], int n)
/* n è la dimensione dell'array passato */
{
int
double
i;
ris;
ris = 1.0;
for (i=0; i < n; i=i+1)
ris = ris * a[i];
return ris;
}
Supponiamo che nel main sia stata dichiarata una variabile v di tipo
array di 50 elementi:
Chiamata
Valore calcolato e restituito
mul (v, 50)
mul (v, 30)
mul (&v[5], 7)
mul (v+5, 7)
v[0]*v[1]* ... *v[49]
v[0]*v[1]* ... *v[29]
v[5]*v[6]* ... *v[11]
v[5]*v[6]* ... *v[11]
Infine, notiamo che una funzione C non può mai restituire un array, ma
soltanto un puntatore all’array.
In conclusione: gli array in C sono un “vestito cucito addosso ai
puntatori”. Opinione personale: talvolta questo vestito “butta male”.
In ogni caso: molta attenzione e rigore: evitare le tentazioni alle
scorciatorie offerte dal C
I parametri di tipo struttura invece ...
Una struttura può essere passata per valore anche quando
contiene un componente di tipo array.
In tal caso, viene copiato nel parametro formale, l’intero
valore del parametro attuale, contenuto dell’array, incluso.
Una funzione C può anche restituire per valore o per
indirizzo una struttura (anche quando contiene un
componente di tipo array).
NB: possibilità “disomogenee” nei confronti di due tipi
strutturati di grande utilizzo.
Effetti collaterali
Finora abbiamo distinto in maniera molto netta l’uso delle procedure da
quello delle funzioni, utilizzando queste ultime nel senso rigorosamente
matematico del termine.
In realtà i(l) linguaggi(o) permette(ono) diversi “incroci” -sconsigliati
nei casi normaliint
{
PrimoEsempio (int par)
return
(par + x)
}
Nel corso del seguente frammento di programma:
x = 1;
x = PrimoEsempio (1);
x = PrimoEsempio (1);
la sua chiamata produce, la prima volta, il risultato “2”, la seconda volta
“3”.
int
{
SecondoEsempio (int
*par)
*par = *par + 1;
return
*par;
}
y = SecondoEsempio (&z)
assegna alla variabile y il valore di z+1, ma anche z assume lo stesso
valore.
effetto collaterale (side effect)
int TerzoEsempio (int par)
{
x = par + 2;
return
(par + 1);
}
Altro effetto collaterale:
z = TerzoEsempio (4)
assegna a z il valore “5”, ma anche il valore “6” a x.
A
Si supponga di voler esaminare l’ultima fattura inserita nella variabile
ArchivioFatture già più volte utilizzata, e di volerla eliminare se il
giorno di emissione corrisponde a quello desiderato.
DescrizioneFatture
{
DescrizioneFatture
EsaminaElimina (Giorno ParGiorno)
FatturaLocale;
FatturaLocale =
ArchivioFatture.Sequenza[ArchivioFatture.NumFatture–1];
if (FatturaLocale.DataEmissione.Giorno == ParGiorno)
ArchivioFatture.NumFatture =
ArchivioFatture.NumFatture–1;
return FatturaLocale;
}
Uso interscambiabile di procedure e funzioni
int
{
f(int
par1)
...
return risultato;
}
Essa può essere trasformata nella procedura seguente:
void
{
f(int
par1, int
*par2)
...
*par2 = risultato;
}
Successivamente, una chiamata come
y = f (x)
verrà trasformata in
f(x, &y)
Procedure e funzioni predefinite
La standard library del C
•
Sono chiari il bisogno e la comodità di sottoprogrammi di
largo uso predefiniti:
– matematica
– I/O
– Grafica,
•
Ciò ha dato luogo alle librerie di sottoprogrammi:
– predefinite
– costruite dai programmatori applicativi
•
•
•
Però l’uso di librerie diminuisce la portabilità
A meno che anche le librerie (almeno le fondamentali)
non siano standardizzate
La grande forza del C: la libreria standard:
 Operazioni di ingresso/uscita.

operazioni su file

operazioni per la gestione dell’I/O di stringhe e caratteri
 operazioni di I/O formattato, operazioni di I/O non formattato,
operazioni per la gestione degli errori
 Operazioni matematiche e aritmetiche: operazioni
trigonometriche, operazioni esponenziali e logaritmiche e
l’operazione per il calcolo del valore assoluto.
 Operazioni di gestione della memoria.
 Operazioni di gestione di caratteri e di gestione di stringhe
 Operazioni di ricerca e ordinamento applicabili ad array,
operazioni di gestione di date e tempo, operazioni di utilità
generale quali la generazione di numeri casuali.
 Operazioni di comunicazione con l’ambiente del sistema
operativo e una operazione per la gestione degli errori che hanno
provocato un fallimento nell’esecuzione di una funzione.
Esempio: uso di funzioni della standard library del C per leggere due stringhe
e costruirne una terza mediante la concatenazione delle prime due in ordine
alfabetico. (si confronti con la soluzione senza procedure di libreria!)
Le stringhe sono array di caratteri terminati dal carattere di fine stringa \0
(il carattere null).
Gli argomenti delle funzioni sono puntatori a caratteri. --> Le funzioni
possono essere chiamate passando il nome degli array
/* Programma Concatenazione di stringhe */
#include <stdio.h>
#include <string.h>
#define LunghezzaArray 50
main()
{
char
PrimaStringa[LunghezzaArray],
SecondaStringa[LunghezzaArray],
StringaConc[2 * LunghezzaArray];
unsigned
LunghezzaConc;
scanf (“%s”, PrimaStringa);
scanf (“%s”, SecondaStringa);
if (strcmp (PrimaStringa, SecondaStringa) <= 0
{
strcpy (StringaConc, PrimaStringa);
strcat (StringaConc, SecondaStringa);
}
else
{
strcpy (StringaConc, SecondaStringa);
strcat (StringaConc, PrimaStringa);
}
LunghezzaConc = strlen (StringaConc);
printf(“La stringa ottenuta concatenando le due stringhe lette è %s.
Essa è lunga %d caratteri\n”, StringaConc, LunghezzaConc);
}
I file header
Le funzioni della libreria sono disponibili in C come file di codice
compilato, non leggibili direttamente dal programmatore.
È comunque compito del programmatore inserire nel programma i
prototipi delle funzioni che verranno usate
Per facilitare questo compito, la libreria C comprende alcuni file,
chiamati header file, che contengono i prototipi di un insieme di
funzioni di libreria.
Ciò spiega finalmente la
#include <stdio.h>
e le altre #include <xxx.h>
Il preprocessore copia il contenuto del file stdio.h nel programma,
inserendo i prototipi delle funzioni che appartengono al gruppo di cui
xxx.h è il file testata.
Abbiamo infine anche capito il senso del ‘&’ nel parametro della scanf
e…
il cerchio si è finalmente chiuso!
La ricorsione
•
•
•
•
Solo un breve cenno
(approfondimenti nei corsi successivi)
Che cos’è
A che cosa serve e come si usa
(da approfondire in Principi e Algoritmi dell’Informatica)
Come viene realizzata (da approfondire in INFO2)
La ricorsione: che cos’è
•
•
•
•
•
•
•
Un sottoprogramma P può chiamarne -durante la sua
esecuzione- un altro Q
Il quale a sua volta ne può chiamare un terzo R, …
e se R chiamasse nuovamente P (ricorsione indiretta)?
Oppure P chiamasse se stesso durante la propria
esecuzione (ricorsione diretta)?
NB: ricorsione non significa chiamare un
sottoprogramma più volte (scontato), ma richiamarlo -da
se stesso o altri sottoprogrammi- prima della
terminazione della sua esecuzione.
Ha un senso ciò?
Se sottoprogramma significa “parte di programma per
risolvere un sottoproblema”, richiamare P durante la sua
esecuzione significa cercare di usare la soluzione del
sottoproblema PR che si intende risolvere con P per …
risolvere PR: cane che si morde la coda?
•
•
•
•
•
In realtà, a ben pensarci, non è poi così strano usare la soluzione
di un problema PR per risolvere PR!
Il punto sta nel distinguere il concetto di istanza di un problema
dal problema nella sua generalità:
Assai spesso, per trovare la soluzione di un problema in un caso
complicato possiamo usare la soluzione dello stesso problema in
un caso più semplice.
Un esempio classico:
individuare, in un gruppo di palline l’unica pallina di peso
maggiore delle altre facendo uso di una bilancia “a basculla”
(Per semplicità: il numero di palline sia una potenza di 3)
•
Algoritmo Pesate
•
– Dividi il gruppo di palline in tre sottogruppi di egual
numero e confronta due di questi sottogruppi.
– Se i due gruppi risultano di peso uguale scartali entrambi.
Altrimenti scarta il gruppo non pesato e quello risultato di
peso minore.
– Ridividi il gruppo rimasto in tre e ripeti il procedimento
precedente finché i sottogruppi non siano ridotti a una
pallina per uno. In tal caso l’ultima pesata individuerà la
pallina cercata.
Nuova versione dell’algoritmo Pesate
– Se il gruppo di palline consiste in una sola pallina, allora
essa è banalmente la pallina cercata, altrimenti procedi
come segue.
– dividi il gruppo di palline in tre e confronta due dei tre
sottogruppi.
– se i due gruppi risultano di peso uguale scarta entrambi,
altrimenti scarta il gruppo non pesato e quello risultato di
peso minore.
– Applica l’algoritmo Pesate al gruppo rimanente.
•
La ricorsione è un potentissimo strumento concettuale
“nascosto” sotto svariati ragionamenti -sia di tipo
matematico che non-:
•
•
•
•
•
•
•
x + 0 = x;
x + y = x + Successore(y–1) = Successore (x + (y–1))
:
1+3 = Successore (1+2) = Successore(Successore(1+1))
=
Successore(Successore(Successore(1+0))) =
Successore(Successore(Successore(1))) =
Successore(Successore(2)) = Successore(3) = 4
•
I numeri di Fibonacci, F = {f0, ..., fn}:
– f0 = 0
– f1 = 1
– Per n > 1, fn = f n–1 + fn–2
•
:
– f0 = 0
– f1 = 1
– f2 = f1 + f0 = 1 + 0 = 1
– f3 = f2 + f1 = 1 + 1 = 2
– f4 = f3 + f2 = 2 + 1 = 3
•
La sommatoria di una sequenza di numeri è:
0
a
i
i 1
n 1
a
i
i 1
0
n
 an 1   ai
i 1
Per esempio, la sommatoria di 2,5,7,9 è:
3
2
1
1
9 +  ai = 9 + (7 +  ai )
1
= 9 + (7 + (5 +  ai ))
1
0
ai )))
= 9 + (7 + (5 + (2 + 
1
= 9 + 7 + (5 + (2 + 0)))
= 9 + (7 + (5 + 2))
= 9 + (7 + 7) = 9 + 14 = 23
•
La lista inversa L–1 di una lista di elementi L = {a1, ..., an}
è così definita:
•
se n = 1, L–1 = L, altrimenti L–1 = {an, (Ln–1)–1}
•
dove Ln–1 indica la lista ottenuta da L cancellando l’ultimo
•
elemento an.
Per esempio, la lista inversa di L = 2,7,5,4 è ottenibile come
segue:
– 2,7,5,4–1 = 4, 2,7,5–1
–
= 4,5, 2,7–1
–
= 4,5,7, 2–1
–
= 4,5,7,2
Il determinante D di una matrice quadrata A di
ordine n è così definito:
Se n = 1, allora D(A) = a11;
altrimenti D(A) = (-1)i+1 . a1i. D(A1i),
dove A1i indica la matrice ottenuta da A eliminando
la prima riga e la i-esima colonna.
La ricorsione come strumento di programmazione
•
Passare da una formulazione ricorsiva di tipo astrattomatematico a una scrittura di codice è estremamente semplice e
naturale: A
•
Calcolo del fattoriale (versione iterativa):
•
•
•
•
•
•
•
•
int
{
•
Se sfruttiamo la proprietà per cui n! = n (n–1)!, con 0! = 1 per
convenzione: ---> calcolo del fattoriale di un numero  0 versione ricorsiva:
•
•
•
•
•
•
•
int FattRic(int n)
{
int ris;
if (n == 0) ris = 1;
else
ris = n * FattRic(n–1);
return
ris;
}
fatt(int n)
int i, ris;
ris = 1;
for (i = 1; i <=n; i= i+1)
ris = ris * i;
return ris;
}
•
Programma Fibonacci
•
•
•
int fibonacci(int n)
{
int ris;
•
•
•
•
•
if (n == 0) ris = 0;
else if (n == 1) ris = 1;
else
ris = fibonacci(n–1) + fibonacci(n–2);
return
ris;
}
•
Apparentemente dunque, è immediato trasferire alla
programmazione la “mentalità ricorsiva” nella formulazione
astratta di algoritmi
•
Eppure i primi linguaggi di programmazione (FORTRAN,
COBOL) non permettevano la ricorsione:
– Non era conosciuta?
• Il concetto è ben più vecchio (Peano, …)
– Era esclusivamente di interesse matematico?
• Il FORTRAN era dedicato proprio ad applicazioni numeriche
– ???
•
Pensiamo all’esecuzione di un sottoprogramma ricorsivo (ad
esempio, il fattoriale di 3):
– 3 = 0? No. Quindi occorre calcolare il fattoriale di 2, e, una
volta ottenutolo, moltiplicarlo per 3.
– .2 = 0? No. Quindi occorre calcolare il fattoriale di 1, e, una
volta ottenutolo, moltiplicarlo per 2.
– .1 = 0? No. Quindi occorre calcolare il fattoriale di 0, e, una
volta ottenutolo, moltiplicarlo per 1.
– .0 = 0? Sì. Quindi il fattoriale di 0 è 1.
– .Sulla base di quanto stabilito al punto 3, il fattoriale di 1 è
1 moltiplicato per il fattoriale di 0, cioè 1  1 = 1.
– .Sulla base di quanto stabilito al punto 2, il fattoriale di 2 è
2 moltiplicato per il fattoriale di 1, cioè 2  1 = 2.
•
Sulla base di quanto stabilito al punto 1, il fattoriale di 3 è 3
moltiplicato per il fattoriale di 2, cioè 3  2 = 6.
•
Ovvio? Mettiamoci però nei panni della macchina:
•
In primo luogo, il valore del parametro attuale, 3, viene copiato
nel parametro formale, n
Ha inizio l’esecuzione di FattRic. Essa giunge a n*FattRic(2), il
cui risultato dovrebbe essere assegnato alla cella FattRic per poi
essere passato al chiamante. A questo punto avviene dunque la
nuova chiamata di FattRic: essa è ricorsiva poiché avviene
durante l’esecuzione di FattRic stessa.
Il nuovo valore del parametro attuale, 2, viene copiato nella
•
•
cella n, cancellando il precedente valore 3!
•
•
L’introduzione della ricorsione come strumento programmativo
richiede una piccola rivoluzione nel meccanismo di gestione
della memoria -area dati attribuita ai vari sottoprogrammi:
Invece che assegnare un area dati -staticamente- a ogni
sottoprogramma, se ne assegna una -record di attivazione- a
ogni chiamata di sottoprogramma:
n
FattRic
3
3*2 = 6
Prima
attivazione
2
2*1 = 2
Seconda
attivazione
1
0
1*1 = 1
1
Terza
attivazione
Quarta
attivazione
Abbiamo fatto una prima importante violazione al
principio dell’allocazione statica della memoria: il
compilatore non può allocare tutta e sola la memoria
necessaria prima dell’esecuzione
•
Un altro esempio (con passaggio -anche- per indirizzo)
•
•
•
•
•
•
•
•
void incrementa(int *n, int m)
{
if (m != 0)
{
*n = *n + 1;
incrementa(n, m–1);
}
}
x
y
2,3,4,5,5
3
n
m
Area dati della
funzione
chiamante
3
Prima
attivazione
2
Seconda
attivazione
Terza
attivazione
1
0
Quarta
attivazione
Un modo particolarmente efficace di gestire la memoria per
l’esecuzione di programmi ricorsivi:
la gestione a pila o stack
M
P1
P2'
P3
P2''
P2'
P3
P4
M
P1
Legend
:
P2'
A rightwards arrow denotes a call
A leftwards arrow denotes the return to the calling subprogram
The different activations of P2 are marked by apexes
activation
record
of P2'
activation
record
of P3
activation
record
of P2''
activation
record
of P3
activation
record
of P2'
activation
record
of P2'
activation
record
of P1
activation
record
of P1
activation
record
of P1
activation
record
of P1
activation
record
of
M
activation
record
of M
activation
record
of M
activation
record
of M
activation
record
of M
global
variables
global
variables
global
variables
global
variables
global
variables
(a)
(b)
(c)
(d)
(e)
activation
record
of P4
activation
record
of P3
activation
record
of P2'
activation
record
of P2'
activation
record
ofP2'
activation
record
of P1
activation
record
of P1
activation
record
of P1
activation
record
of P1
activation
record
of P1
activation
record
of M
activation
record
of M
activation
record
of M
activation
record
of M
activation
record
of M
global
variables
global
variables
global
variables
activation
record
of P2'
(f)
(h)
(g)
ac tivation
rec ord
of M
global
variables
(m)
global
variables
(i)
global
variables
(l)
Qualche ulteriore dettaglio sulla
gestione a stack della memoria
(non tutti!)
• Il record di attivazione:
• Oltre a:
– Parametri attuali
– Variabili locali
• Indirizzo di ritorno (RetAdd)
• (Valore precedente dello) Stack pointer (SP)
Record di
attivazione della
funzione in
esecuzione
Record di
attivazione del
chiamante
crescita della stack
Il record di attivazione
Attuale valore dello SP
Variabili locali
…
e qualcos’altro
Link dinamico
Indirizzo di ritorno
Parametro n
…
Parametro 2
Risultato/parametro 1
Record di attivazione
precedente
Indirizzo di base del record
di attivazione corrente =
Precedente valore dello SP
La chiamata
•
Codice del chiamante
– Riserva memoria per il
risultato (se previsto)
– Assegna valore ai
parametri attuali
– Assegna l’indirizzo di
ritorno
– Assegna il link dinamico
(valore attuale
dell’indirizzo di base del
RA)
– Assegna il nuovo valore
dell’indirizzo di base
(valore attuale dello SP)
– Assegna il nuovo valore
allo SP (valore attuale
dell’indirizzo di base +
dimensioni del nuovo
RA, comprendente spazio
per le variabili locali)
– Salta alla prima
istruzione del chiamato
– [Indirizzo di ritorno]
•
Codice del chiamato
Il ritorno
•
Codice del chiamato
– Riporta il valore di SP al
valore precedente (il valore
dell’indirizzo di base
dell’attuale RA)
– Riporta il valore dell’indirizzo
di base al valore precedente (il
valore dell’attuale link
dinamico)
– Salta (con BRANCH@)
all’indirizzo di ritorno
•
Codice del chiamante
– Codice della chiamata
– [Indirizzo di ritorno]
– Recupera eventuale
risultato
/* Programma RicPalindr*/
#include
#include
<stdio.h>
<string.h>
typedef
enum {false, true} boolean;
void main ()
{
…
}
boolean
{
if
Palindrome (char, *PC, char *UC)
(PC >= UC)
/* Se la stringa è vuota o è costituita da un solo carattere */
return true;
elseif (*PC != *UC)
/* Se il primo e l'ultimo carattere sono diversi */
return false;
else
/* Chiama se stessa ricorsivamente escludendo il primo e l'ultimo carattere */
return Palindrome (PC+1, UC–1);
}
/* Programma RicPalindr*/
…
void main ()
{
#define LunghMaxStringa
char
boolean
unsigned
100
Stringa1[LunghMaxStringa];
OK;
LunghStringa;
boolean
Palindrome (char *PC, char *UC);
/* L’istruzione seguente assume che i caratteri componenti
la stringa non siano spazi */
scanf ("%s", Stringa1);
LunghStringa = strlung (Stringa1);
if (LunghStringa == 0)
printf ("La stringa è palindroma");
else
{
/* Viene chiamata la funzione Palindrome passando per indirizzo il primo e l'ultimo
carattere della stringa da analizzare */
OK = Palindrome (&Stringa1[0], &Stringa1[LunghStringa–1];
if (OK == true)
printf ("La stringa è palindroma”);
else
printf ("La stringa non è palindroma");
}
}
boolean
{
…
}
Palindrome (char, *PC, char *UC)
Operazioni su una lista di elementi
typedef struct {
}
ListaDiInteri
int
lungh;
int
cont[MaxLungh];
ListaDiInteri;
coda (ListaDiInteri
l1)
/* l1 è una variabile di tipo strutturato contenente una copia della lista (passata
per valore). La funzione trasforma l1 nella lista costituita dagli ultimi n–1
elementi, dove n è la lunghezza della lista al momento della chiamata. La
funzione restituisce quindi la lista così trasformata */
boolean RicercaElem (int el, ListaDiInteri l1)
/* La funzione cerca l'elemento el in l1; restituisce vero quando l'elemento
viene trovato, falso altrimenti */
{
if
(l1.lungh > 0)
if (l1.cont[0] == el)
return true;
else
return RicercaElem (el, coda(l1));
else
return false;
}
Calcolo del determinante di una matrice quadrata
(con una piccola “digressione linguistica”)
CONST MaxOrdine= 100;
TYPE MatQuad = RECORD
Ordine : [1 .. OrdMax];
Elementi : ARRAY [1 .. OrdMax] [1 .. OrdMax] OF REAL;
END (* RECORD *);
Una possibile formulazione della funzione è la seguente:
PROCEDURE Determinante (Mat: MatQuad): REAL;
VAR risultato : REAL;
j : INTEGER;
BEGIN
IF n = 1 THEN
risultato := Mat.Elementi[1, 1];
ELSE
risultato := 0;
FOR j := 1 TO n DO
risultato := risultato + Espon((–1), j + 1) *
Mat.Elementi [1, j] * Determinante ( SubMat(Mat, 1, j) );
END (* FOR *);
END (*IF*);
RETURN risultato;
END det;