Programma per la valutazione di un triangolo / main() { /Lettura dei dati di ingresso /...

/*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 lunghezzedei 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");elseprintf("I dati letti corrispondono a un triangolo

scaleno");else

printf("I dati letti non corrispondono ad alcun triangolo");}

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.

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 banalissimo- procediamo 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.

2 Memorizza la prima parola del testo in un array di caratteri.

3 Memorizza la seconda parola in un altro array.

4 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.

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 l’attenzione sulla meno banale: il confronto.

• decidere se due parole memorizzate rispettivamente nei due array PrimaParola e ParolaCorrente coincidono :

– 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 x,y;int i,j; char simb;

• equivalenti a:

• float x; int i,j; char simb;float y;

• 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.

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 float PiGreco = 3.14;const float PiGreco = 3.1415, e = 2.718;const int N = 100, M = 1000;const char 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 produce la visualizzazione delle seguenti frasi:

Questo programma è stato scritto da GM

Buon lavoro!

Si noti l’effetto dei simboli \n

• 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 predefinitiQuattro 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 intil qualificatore long a double..

Tipi semplici predefiniti del C (da non imparare a memoria)

Tipo predefinito Denominazioni alternativecharsigned charunsigned charsigned short int signed short, shortsigned int signed, intsigned long int long int, signed long, long

unsigned short int unsigned shortunsigned int unsignedunsigned long int unsigned longfloatdoublelong double

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 minimoNon è 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.

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.141 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 23E117 800 000 000 023E-71.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 == xpotrebbe risultare falsa !Invece di scrivereif (x == y) ...è meglio scrivereif (x <= y + .000001 && y <= x + .000001) ...

Il tipo charL’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 signed char unsigned char

short int longunsigned short unsigned unsigned

long

Tipi floating:float double long double

Tipi arithmetic: tipi integral + tipi floating

Tutti i tipi arithmetic del C condividono alcune importanti caratteristiche:

sono totalmente ordinatisono 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 int tipo1;typedef char tipo2;typedef tipo1 tipo3;typedef tipo2 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 enum {lun, mar, mer, gio, ven, sab, dom} GiornoDellaSettimana;

typedef enum {rosso, verde, giallo, arancio, violetto, marrone, nero, ocra}

colore;typedef enum {Giovanni, Claudia, Carla, Simone,

Serafino} persone;

typedef 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 < giurosso < arancio•producono un risultato un intero diverso da 0 (valore logico “true”):

dom < lunSimone < Giovanniproducono 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 enum {false, true} boolean;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 int anArray[20];

• dichiazione di variabili di tipo anArray:

• anArraylista1, lista2;

• la dichiarazione

• int lista[20];• va perciò interpretata come un’abbreviazione per

• typedef intarrayAnonimo[20];

• arrayAnonimo lista

• 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 int anArray [20]; e– typedefdouble NuovaLista[30];

– danno luogo a due tipi diversi

• 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 double PioggeMensili[12]; • typedef double IndiciBorsa[12]; • PioggeMensiliPiogge01, Piogge02, Piogge03; • IndiciBorsa 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 int Vettore[20]; • typedef Vettore

MatriceIntera20Per20[20];

• MatriceIntera20Per20matrice1;

• Oppure:

• typedef int Matrice20Per20[20][20];

• int matrice1[20][20];

• int matricetrid1[10][20][30];

• 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 1 2 3

j

0 23 12 3 55

1 16 2 45 18

2 …

Cella Indirizzo

23 1000

12 1001

3 1002

55 1003

16 1004

2 …

45 1000+4*j +i

18 ….

…

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 char string[30];

• String Nome, Cognome;

• 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");

• 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

• /* Programma InvertiSequenza */• #include <stdio.h>

• main()• {• int Contatore;• int 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 Contatore; • int 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 int anArray[10];

• anArray Array1, Array2;

• è scorretta l’istruzione:

• Array2 = Array1;

• Sarà necessaria un’istruzione ciclica che “scorra” i singoli elementi dell’array

• Capiremo a fondo il perché in seguito

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){


}}else

/* Se la seconda stringa precede la prima in ordine alfabetico, ossia se (Array2[i] < Array1[i]) */

{k = 0; j = 0;while (j < LunghezzaArray){


}j = 0;while (j < LunghezzaArray){


}}/* 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 { String Destinatario;• double Importo;• Data

DataEmissione;• } DescrizioneFatture;

• Ovviamente si assume che i tipi String e Data siano già stati precedentemente definiti.

• typedef struct { int Canale;AccType Accensione;

• doubleCursoreLuminosita,

CursoreColore,• CursoreVolume;• } CanaliTV;

• dove :

• typedef enum {On, Off} AccType;

• Dal punto di vista del compilatore

Cella Indirizzo

P 1000

i 1001

n 1002

… …

o 1029

20,000 1030

00 1031

6 1032

Luglio 1033

2008 1034

Pinco Pallino20,000.006Luglio2008

• typedef struct { String Nome;• String

Cognome;• int Stipendio;• char

CodiceFiscale[16];• Data

DataAssunzione; CatTypeCategoria;

• } Dipendenti;

• 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 ArchivioFatture[1000];

• 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");

• 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; TipoPuntatore P; TipoDato x;

x

P

P

14

23

(a)

(b)

(c)

14

14

x

x

23

23

P

*P = x; x = *P;

le seguenti istruzioni sono ammissibili:

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

14

14

z

y

z

P

P

Q

Q

23

23

(a)

(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 { intPrimoCampo; charSecondoCampo;

} 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 { dirigente, impiegato, operaio CatLav;

typedef struct { char Nome[30];char Cognome[30];CatLav Categoria;int Stipendio;char CodiceFiscale[16];

} Lavoratore;Lavoratore DatiLavoratori[300];Lavoratore *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 e completamente prevedibili durante la programmazione):

*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’i-esimo 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 è equivalente a p = &a[0];• p = a+1 è equivalente a p = &a[1];

• mentre non sono ammessi assegnamenti ad a del tipo:

• a = p; • a = 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 compile-time.

• 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 { intNumFatture;

• 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 FatturatoTotale (ElencoFatture par)• boolean 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 FatturatoTotale (ElencoFatture parametro)

• {• int Totale, Cont;

• Totale = 0;• for (Cont = 0; Cont < parametro.NumFatture;

Cont++)• Totale = Totale +

parametro.Sequenza[Cont].Importo;• return Totale;• }

• int RadiceIntera (int par)• {• int cont;

• cont = 0;• while (cont*cont <= par)• cont = cont + 1;• return (cont–1);• }

• 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

• /* Programma Contabilità */• /* Parte direttiva */

• #include <stdio.h>• #define MaxNumFatture 1000

• /* Parte dichiarativa globale */• typedef char String [30];• typedef struct { String Indirizzo;• int ammontare;• Data DataFattura;• } DescrizioneFatture;• typedef struct { int NumFatture;• DescrizioneFatture

Sequenza[MaxNumFatture];• } ElencoFatture;• main() • {• ElencoFatture ArchivioFatture1, ArchivioFatture2;• int Fatt1, Fatt2, Fatt;• int FatturatoTotale (ElencoFatture

parametro);• /* Prototipo della funzione FatturatoTotale */

• ....• Fatt1 = FatturatoTotale(ArchivioFatture1);• Fatt2 = FatturatoTotale(ArchivioFatture2);• Fatt = Fatt1 + Fatt2;• ....• }

• /* Fine del main del programma Contabilità */

• int FatturatoTotale (ElencoFatture parametro)• {• int Totale, Cont;• ....• return Totale;• ...• }

Ambienti di esecuzione, macchine astratte master e slave

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);

ArchivioFatture1

ArchivioFatture2

Fatt1

Fatt2

Parametro

Totale

Cont

FatturatoTotale

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 {VerdeSinistra, VerdeDestra} TipoStato;typedef struct { TipoStato Stato;

int CodaSinistra;int CodaDestra;

} TipoSemaforo;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;

DescrizioneFattureSequenza[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

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)

Ambiente globale

ArchivioFatture

Ambiente locale di InserisciFattura

Ambiente di main di Programma Contabilità

DataOdierna Fattura

Fattura1

Fattura2

...

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.

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.

Ind(x) = 2034

Parametri attuali Parametri formali

Passaggio per valore

x A

243 243

Ind(y) = 1004Passaggio per indirizzo

y A

413 1004

• 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>

• /* Parte dichiarativa globale */• int g1, g2;• char g3;• int f1 (int par1, int par2); ...• main ()• {• int a, b;• int f2 (int par3, int par1); ...

• /* blocco1 */• {• char a, c;• ...

• /* blocco2 annidato nel blocco1 */• {• float a;• ...• }

/* Fine blocco2 */• }

/* Fine blocco1 */• }

/* Fine main */

• int f1(int par1, int par2)• {• int d;• ...

• /* blocco3 */• {• int e;• ...

• } /* Fine blocco3 */

• /* blocco4 */• {• int d;• ...

• } /* Fine blocco4 */

• }/* Fine f1 */

• /* Definizione della funzione f2 */• int f2 (int par3, int par4)• {• int 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ò:

/* Definizione della funzione f1 */int f1(int par1, intpar2){

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 doubleTipoArray[MaxNumElem]

le tre testate di funzione riportate di seguito sono in C di fatto equivalenti:

double sum (TipoArray a, int n)

/* n è la dimensione dell'array passato */double sum (double *a, int

n)double sum (double a[ ], int

n)

double mul (double a[ ], int n)/* n è la dimensione dell'array passato */

{int i;double 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) v[0]*v[1]* ... *v[49]mul (v, 30) v[0]*v[1]* ... *v[29]mul (&v[5], 7) v[5]*v[6]* ... *v[11]mul (v+5, 7) 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 normali-

int 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)

intTerzoEsempio (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 EsaminaElimina (Giorno ParGiorno){

DescrizioneFattureFatturaLocale;

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 50main(){

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 è:

00

1

i

ia

n

iin

n

ii aaa

11

1

1

Per esempio, la sommatoria di 2,5,7,9 è:

9 + = 9 + (7 +

= 9 + (7 + (5 +

= 9 + (7 + (5 + (2 +

= 9 + 7 + (5 + (2 + 0)))

= 9 + (7 + (5 + 2))

= 9 + (7 + 7) = 9 + 14 = 23

3

1ia )

2

1 ia

))1

1 ia

)))0

1 ia

• 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 astratto-matematico a una scrittura di codice è estremamente semplice e naturale: A

• Calcolo del fattoriale (versione iterativa):

• int fatt(int n)• {• int i, ris;• ris = 1;• for (i = 1; i <=n; i= i+1)• ris = ris * i;• return ris;• }

• 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;• }

• 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:

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

Prima attivazione

Seconda attivazione

Terza attivazione

Quarta attivazione

n FattRic

3

2

1

0 1

1*1 = 1

2*1 = 2

3*2 = 6

• Un altro esempio (con passaggio -anche- per indirizzo)

• void incrementa(int *n, int m)• {• if (m != 0)• {• *n = *n + 1; • incrementa(n, m–1); • }• }

Prima attivazione

Seconda attivazione

Terza attivazione

Quarta attivazione

n m

0

1

2

3

y

3

Area dati della funzione chiamante

x

2,3,4,5,5

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''

P4

M P1 P2'

P2' P3

Legend:

A rightwards arrow denotes a callA leftwards arrow denotes the return to the calling subprogram

The different activations of P2 are marked by apexes

M

activationrecordof

(a)

M

activationrecordof

(b)

activationrecordof P1

M

activationrecordof

(c)


activationrecordof P2'

M

activationrecordof

(d)




M

activationrecordof

(e)




activationrecordof P2''

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

globalvariables

M

activationrecordof

(f)




M

activationrecordof

(g)



M

activationrecordof

(h)


activationrecordofP2'


M

activationrecordof

(i)



M

activationrecordof

(l)


globalvariables

M

activationrecordof

(m)

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)

crescita della stack

Record di attivazione della funzione in esecuzione

Record di attivazione del chiamante

Il record di attivazione

Indirizzo di base del record di attivazione corrente =Precedente valore dello SP

Risultato/parametro 1

Parametro 2

…

Parametro n

Indirizzo di ritorno

Link dinamico

Variabili locali…

e qualcos’altro

Attuale valore dello SP

Record di attivazione precedente

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 <stdio.h>#include <string.h> typedef enum {false, true} boolean; void main (){

…} boolean Palindrome (char, *PC, char *UC){

if (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 100

char Stringa1[LunghMaxStringa];boolean OK;unsigned 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 { int lungh;

int cont[MaxLungh]; } ListaDiInteri;

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 THENrisultato := Mat.Elementi[1, 1];

ELSErisultato := 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;

Programma per la valutazione di un triangolo / main() { /Lettura dei dati di ingresso /...

Documents

Transcript of Programma per la valutazione di un triangolo / main() { /Lettura dei dati di ingresso /...

*Programma per la valutazione di un triangolo */ main() { /*Lettura dei dati di ingresso */...

Documents

Transcript of *Programma per la valutazione di un triangolo */ main() { /*Lettura dei dati di ingresso */...

Programma per la valutazione di un triangolo / main() { /Lettura dei dati di ingresso /...

Transcript of Programma per la valutazione di un triangolo / main() { /Lettura dei dati di ingresso /...