Introduzione al linguaggio C

(1)

Introduzione al linguaggio C

Violetta Lonati

Dipartimento di Informatica Universit`a degli studi di Milano

Violetta Lonati Introduzione al linguaggio C 1

(2)

Ultimo aggiornamento

October 7, 2021

(3)

Argomenti I

Intro

Uso del compilatore gcc Struttura di un programma C Tipi di base

Definizione di tipi Input e output formattati

Lettura e scrittura di caratteri

Dati aggregati: array, stringhe, strutture, enumerazioni Array

Stringhe Strutture Enumerazioni Funzioni

Definizione di funzioni Chiamata di funzioni Dichiarazione di funzioni

(4)

Argomenti II

Parametri, argomenti e variabili locali L’istruzione return

Organizzazione dei programmi Alcune osservazioni sulle funzioni Funzioni ricorsive

Alcuni algoritmi di ordinamento ricorsivi Selectionsort

Mergesort Puntatori

Operatori & e *

Puntatori come argomento di funzione Puntatori come valori restituiti

Puntatori a strutture Aritmetica dei puntatori Puntatori e array Stringhe e puntatori

(5)

Argomenti III

Array frastagliati Array di stringhe

Argomenti da linea di comando

Allocazione dinamica della memoria Puntatore nullo

Funzioni per l’allocazione dinamica della memoria Deallocare memoria

Errori tipici Esempi

(6)

Uso del compilatore gcc

I Si usa da linea di comando: gcc file da compilare.c I Per default produce il file eseguibile a.out

I Per eseguire il file basta digitare ./a.out I Opzioni utili:

I -o file di output per salvare l’output nel file specificato, I -c per arrestare la compilazione prima della fase dilink, I -s per arrestare la compilazione prima della fase diassemble, I -E per arrestare la compilazione dopo la fase dipreprocessing, I -W, con parametro all, per la segnalazione di avvertimenti

(warning),

I -l, con parametro m, per linkare le librerie matematiche

Esempio

$ gcc -Wall -o cerchio cerchio.c -lm

$ ./cerchio

(7)

Forma generale di un programma C

Esempio di programma

# i n c l u d e < s t d i o . h >

int m a i n ( v o i d ) { p r i n t f ( " C i a o !\ n " );

r e t u r n 0;

}

Struttura generale di un programma

D I R E T T I V E

int m a i n ( v o i d ) { I S T R U Z I O N I

}

(8)

Tipi numerici in C

In C esistono duetipi numerici built-in (di base):

I numeri interi int

I numeri decimali in virgola mobile float

La dimensione dei tipi varia a seconda della macchina. L’operatore sizeofconsente di determinare quanta memoria occupa una variabile di un determinato tipo:

I sizeof ( int ) rappresenta il numero di byte necessari a memorizzare una variabile di tipo int,

I sizeof ( a ) rappresenta il numero di byte necessari a memorizzare la variabile a.

(9)

Tipo int

I Possono avere segno oppure no:

I signed int: il bit più a sinistra vale 0 se il numero è ≥ 0 e 1 se è < 0

I unsigned int: bisogna specificarlo nella dichiarazione I Possono avere diverse dimensioni:

I short int: nelle dichiarazioni si può abbreviare inshort I long int: nelle dichiarazioni si può abbreviare inlong I Il range di variabilità non è fissato nel C standard ma cambia

a seconda della macchina, gli unici vincoli sono i seguenti:

short int ≤ int ≤ long int

I Il file di intestazionelimits.h fornisce alcune macro che definiscono i valori limite, per l’architettura corrente, dei tipi interi.

Dichiarazioni per i tipi interi:

short si;

int i;

long li;

unsigned short usi;

unsigned int ui;

unsigned long uli;

(10)

Tipo float

I In C ci sono tre tipi di numeri in virgola mobile:

I float: single-precision I double: double-precisione I long double: extended-precision

I Anche per i float il range di variabilit`a non `e fissato I Il file di intestazionefloat.h fornisce alcune macro che

definiscono, per l’architettura corrente, la precisione dei tipi float.

I Le costanti possono essere scritte in molti modi, purch`e contengano un decimale e/o un’esponente. Ad esempio:

5 7 . 0 57. 5 7 . 0 e0 57 E0

5.7 e1 5.7 e +1 .57 e +2 5 7 0 . e -1 Per default le costanti sono memorizzate come double. Se basta la singola precisione, basta usare la letterafoF alla fine della costante (es: 57.0f).

(11)

Tipo char

L’ultimo tipo built-in del C `e il tipochar (carattere) c h a r ch ;

ch = ’ a ’; /∗ a minuscola ∗/

ch = ’ A ’; /∗ A maiuscola ∗/

ch = ’ 0 ’; /∗ zero ∗/

ch = ’ ’; /∗ spazio ∗/

I Il valore di un char pu`o cambiare a seconda dellacharacter set della macchina.

I Si pu`o generalmente assumere che le lettere minuscole siano contigue nell’ordine alfabetico, idem per le maiuscole, idem per le cifre.

I I char sono usati dal C come tipi interi: le variabili char possono essere incrementate o confrontate come interi (l’esito del confronto dipende dall’ordinamento del character set).

I Il file di intestazionectype.h fornisce alcune funzioni per l’elaborazione di caratteri e la conversione di lettere da maiuscole a minuscole e viceversa.

(12)

Tipo char - esempi

Assumendo che il character set sia ASCII:

c h a r ch ; int i ;

i = ’ a ’; /∗ ora i vale 97 ∗/

ch = 65; /∗ ora ch vale ’A’ ∗/

ch ++; /∗ ora ch vale ’B’ ∗/

Per convertire lettere minuscole in maiuscole:

if ( ’ a ’ <= ch && ch <= ’ z ’) ch = ch - ’ a ’ + ’ A ’;

Oppure:

# i n c l u d e < c t y p e . h >

...

if ( i s l o w e r ( ch ) ) ch = t o u p p e r ( ch );

(13)

Definizione di tipi

La parola chiavetypedef consente di definire nuovi tipi a partire da quelli built-in o dai tipi precedentemente definiti

Esempio

Definiamo un nuovo tipo Bool. Bool potr`a essere usato nelle dichiarazioni di variabili esattamente come gli altri tipi built-in.

# d e f i n e V E R O 1

# d e f i n e F A L S O 0

t y p e d e f int B o o l ; /∗ Def . del tipo Bool ∗/

int m a i n ( v o i d ) {

B o o l f l a g ; /∗ Dich . della var flag ∗/

f l a g = V E R O ; /∗ Assegno a flag valore VERO ∗/

...

}

(14)

Input e output formattati

I printf e scanfdanno la possibilit`a di stampare output e leggere input formattati.

I Il primo argomento `e dato dallastringa di formatoche pu`o contenere

I sequenze di escape(es \n) I specifiche di formato:

I %dper gli interi;

I %fper i float in notazione decimale;

I %eper i float in notazione esponenziale;

I %cper i char;

I `e possibile specificare anche il numero di decimali, di 0 iniziali, l’allineamento...

I Funzionamento di scanfin presenza di spazi bianchi:

I gli spazi bianchi iniziali vengono ignorati nella lettura di int e float, ma non di char;

I uno spazio bianco nella stringa di formato significa “salta uno o pi`u caratteri bianchi”; ad esempioscanf( " %c", &ch ) salta gli spazi bianchi e poi memorizza ch.

(15)

Lettura e scrittura di caratteri

getchare putcharpermettono di leggere e stampare un carattere alla volta.

I ch = getchar();

memorizza in ch il prossimo carattere da standard input;

I putchar( ch );

stampa il carattere ch su standard output.

/∗ Trasforma la riga da minuscole a maiuscole ∗/

c h a r ch ;

w h i l e ( ( ch = g e t c h a r () ) != ’ \ n ’ ) { if ( i s l o w e r ( ch ) )

p u t c h a r ( t o u p p e r ( ch ) );

e l s e

p u t c h a r ( ch );

}

/∗ Salta gli spazi bianchi ∗/

w h i l e ( ( ch = g e t c h a r () ) == ’ ’ )

;

(16)

Array unidimensionali

Dichiarazione

# d e f i n e N 100 int a [ N + 2];

Indicizzazione

a[i]indica l’i-esimo elemento dell’array a. Al posto di isi pu`o mettere una qualsiasi espressione intera.

Attenzione agli effetti collaterali ina[i] = b[i++];

Inizializzazione

int a [4] = {1 , 2 , 0 , 0};

int b [] = {1 , 2 , 0 , 0};

int c [4] = {1 , 2};

Eventuali elementi mancanti sono inizializzati a 0.

(17)

Array unidimensionali - continua

Lunghezza di un array

sizeof( a ) / sizeof( a[0] )

Array costanti

const int MESI[12] = {31,28,31,30,31,30,31,31,30,31,30,31}

Il qualificatoreconst rende ogni elemento immodificabile.

Esempi

for ( i = 0; i < N ; i ++ ) a [ i ] = 0

/∗ azzero l’array a ∗/

for ( i = 0; i < N ; i ++ ) s c a n f ( " % d ", & a [ i ] );

/∗ leggo e mem . in a ∗/

for ( i = 0; i < N ; i ++ )

p r i n t f ( " % d ", a [ i ] ); /∗ stampo ∗/

(18)

Array unidimensionali - errori tipici

Dimensione degli array

Secondo lo standard del C90, la dimensione dell’array va fissata in fase di compilazione (non di esecuzione) usando un espressione costante. La seguente dichiarazione produce errore di compilazione in C90, ma `e previsto in C99 (VLA: variable-length arrays) in cui comunque la dimensione di un array non pu`o variare nel corso del programma. Nello standard C11 i VLA sono opzionali.

int n = 10;

int a [ n ];

Non c’`e controllo dei limiti

int a [ N ] , i ;

for ( i = 0; i <= N ; i ++ ) p r i n t f ( " % d \ n ", a [ i ] );

/∗ accede ad a[N] che non e’ definito !! ∗/

(19)

Array unidimensionali - esercizi

I Rovescia: scrivete un programma che legga una sequenza di numeri interi terminata da 0 e li stampi dall’ultimo (0 escluso) al primo. Potete assumere che la sequenza contenga al pi`u 100 numeri non nulli.

I Cifre ripetute: scrivete un programma che legga in input un numero intero n usando scanf( "%d", &n ) e stabilisca se n contiene qualche cifra ripetuta e in caso affermativo quali.

I Da base 10 a base b: scrivere un programma che data una coppia di numeri interi b e n (separati da spazio e in base 10) stampi la rappresentazione di n in base b. Potete assumere che il numero di cifre in base b sia sempre minore di 100.

I Da base b a base 10: scrivere un programma che dato un numero b (in base 10) e una sequenza s di cifre in

{0, . . . b − 1} terminata da un punto, stampi il numero la cui rappresentazione in base b `e data da s. Potete assumere che il numero di cifre di s sia sempre minore di 100.

(20)

Array bidimensionali

int mat [ R ][ C ] , r , c ; /∗ inizializzo a 0 ∗/

for ( r = 0; r < R ; r ++ ) for ( c = 0; c < C ; c ++ )

mat [ r ][ c ] = 0;

Mappa di memorizzazione

Un array di R righe e C colonne viene memorizzato come array di R ∗ C elementi. In altre paroleM[i][j] si trova i ∗ C + j posizioni dopoM[0][0].

Inizializzazione

int a [ 3 ] [ 2 ] = { {1 , 2} , {3 , 4} , {0 , 0} };

int b [ ] [ 2 ] = { {1 , 2} , {3 , 4} , {0 , 0} };

/∗ non si puo ’ omettere la seconda dimensione ! ∗/

int c [ 3 ] [ 2 ] = {1 , 2 , 3 , 4 , 0 , 0};

int d [ 3 ] [ 2 ] = {1 , 2 , 3 , 4};

/∗ eventuali el. mancanti sono inizializzati a 0 ∗/

(21)

Array bidimensionali - esercizi

I Esami e studenti: scrivete un programma che permetta di inserire gli esiti di 5 esami per 5 studenti e calcoli la media di ciascuno studente e la media dei voti ottenuti in ciascun esame.

I Quadrato magico: scrivete un programma che legga un intero n e stampi un quadrato magico di dimensione n.

(22)

Stringhe

Le stringhe in C sono array di char, terminati dal carattere difine stringa. Il carattere di fine stringa ha valore 0 (i char sono trattati come interi!), ma `e opportuno indicarlo come carattere’\0’. La lunghezza di una stringa `e data dal numero dei suoi caratteri + 1 (per il simbolo di fine stringa).

Inizializzazione

c h a r p a r o l a 1 [5] = " c i a o ";

c h a r p a r o l a 2 [] = " c i a o ";

c h a r p a r o l a 3 [] = { ’ c ’, ’ i ’, ’ a ’, ’ o ’, ’ \0 ’ };

Lettura e scrittura di stringhe

s c a n f ( " % s ", p a r o l a ); /∗ senza & !!! ∗/

p r i n t f ( " % s \ n ", p a r o l a );

Funzioni per elaborare stringhe

<string.h>contiene le dichiarazioni di alcune funzioni utili:

strcpy,strcmp,strcat,strlen,...

(23)

Stringhe - esempio

/∗ copia parola in bis ∗/

c h a r p a r o l a [] = " c i a o ", bis [ 4 + 1 ] ; int i = 0;

w h i l e ( p a r o l a [ i ] != ’ \0 ’ ) { bis [ i ] = p a r o l a [ i ];

i ++;

}

bis [ i ] = ’ \0 ’;

p r i n t f ( " % s \ n ", bis );

(24)

Stringhe - esercizio

Una stringa si dice palindroma se `e uguale quando viene letta da destra a sinistra e da sinistra a destra. Quindi"enne"`e

palindroma, ma"papa" non lo è. Scrivete un programma che legga una stringa terminata da’.’e stabilisca se è palindroma. Potete assumere che la stringa sia al più di 100 caratteri.

(25)

Strutture

I Si tratta di tipi di dati aggregati. Ogni variabile strutturata `e composta da membri, ciascuno dei quali `e individuato da un nome.

I Ogni struttura ha un namespacedistinto, quindi i nomi dei membri possono essere usati anche per altre cose!

I In altri linguaggi, le strutture sono chiamate recorde i membri campi.

/∗ Dichiarazione della var . strutturata studente ∗/

/∗ avente 3 membri : cognome , nome , anno . ∗/

s t r u c t {

c h a r c o g n o m e [ 1 0 ] ; c h a r n o m e [ 1 0 ] ; int a n n o ; } s t u d e n t e ;

(26)

Strutture - continua

Inizializzazione

s t r u c t {

c h a r c o g n o m e [ 1 0 ] ; c h a r n o m e [ 1 0 ] ; int a n n o ;

} s t u d e n t e 1 = { " F e r r a r i ", " M a r i o ", 1 9 8 8 } , s t u d e n t e 2 = { " R o s s i ", " M a r i a ", 1 9 8 8 };

Accesso ai membri

s t u d e n t e . a n n o = 1 9 8 7 ;

p r i n t f ( " % s \ n ", s t u d e n t e . n o m e );

Assegnamento

E’ possibile farlo tra due variabili strutturate dello stesso tipo: tutti i membri vengonocopiati(con gli array questo non si pu`o fare!!).

s t u d e n t e 1 = s t u d e n t e 2 ;

(27)

Definizione di tipi strutturati

Ci sono due modi per definire tipi strutturati:

/∗ usando un tag ∗/

s t r u c t s t u d e n t e { c h a r n o m e [ 1 0 ] ; c h a r c o g n o m e [ 1 0 ] ; int a n n o ;

};

...

s t r u c t s t u d e n t e stud1 , s t u d 2 ; /∗ usando typedef ∗/

t y p e d e f s t r u c t { c h a r n o m e [ 1 0 ] ; c h a r c o g n o m e [ 1 0 ] ; int a n n o ;

} S t u d e n t e ; ...

S t u d e n t e stud1 , s t u d 2 ;

(28)

Strutture nidificate

t y p e d e f s t r u c t { f l o a t x , y ; } P u n t o ;

t y p e d e f s t r u c t { P u n t o p1 , p2 ; } R e t t a n g o l o ; ...

R e t t a n g o l o r ; r . p1 . x = 0;

r . p1 . y = 1;

r . p2 . x = 5;

r . p2 . y = 3;

Esercizio: Scrivete un programma che calcoli l’area e il perimetro di rettangoli e cerchi.

(29)

Array di strutture

# d e f i n e L U N G 20 /∗ lungh . massima per le stringhe ∗/

# d e f i n e N 100 /∗ numero massimo di voci ∗/

t y p e d e f c h a r S t r i n g a [ L U N G + 1];

t y p e d e f s t r u c t { S t r i n g a n o m i n a t i v o ; S t r i n g a tel ;

} V o c e ; ...

/∗ dichiaro rubrica come array di N voci ∗/

V o c e r u b r i c a [ N ];

Esercizio: Scrivete un programma per la gestione di una semplice rubrica. Attraverso un menu l’utente deve poter visualizzare la rubrica e inserire nuovi numeri.

(30)

Enumerazioni

I Si tratta di tipi di dati i cui valori sono enumerati dal programmatore.

e n u m { CUORI , QUADRI , FIORI , P I C C H E } seme1 , s e m e 2 ;

I Ad ogni possibile valore si associa una costante di

enumerazione intera. Per default i valori associati alle costanti sono 0, 1, 2, ..., in questo ordine. E’ possibile scegliere altri valori.

e n u m { V E N D I T E = 10 , R I C E R C A = 21 ,

P R O D O T T I = 17 } s e t t o r e ;

I Si possono definire tipi enumerativi usando sia typedef che tag.

t y p e d e f e n u m { FALSO , V E R O } B o o l ;

(31)

Funzioni

I Le funzioni sono costituite da una sequenze di istruzioni raccolte sotto un solo nome.

I Le funzioni possono avere argomentie possono calcolare e restituire dei valori, ma anche no! (a differenza delle funzioni matematiche)

I I programmi visti sin qui erano costituiti da una sola funzione, il main.

I A cosa servono le funzioni?

I permettono di evitare la duplicazioni di codice;

I sono riutilizzabili.

(32)

Esempio: calcolare la media

# i n c l u d e < s t d i o . h >

f l o a t m e d i a (f l o a t x , f l o a t y ) { r e t u r n ( x + y ) / 2;

}

int m a i n ( v o i d ) { f l o a t a , b , c , m ;

s c a n f ( " % f % f % f ", & a , & b , & c );

m = m e d i a ( a , b );

p r i n t f ( " La m e d i a tra % f e % f e ’ % f \ n ", a , b , m );

p r i n t f ( " La m e d i a tra % f e % f e ’ % f \ n ", a , c , m e d i a ( a , c ) );

r e t u r n 0;

}

(33)

Esempio: conto alla rovescia

# i n c l u d e < s t d i o . h >

v o i d s t a m p a _ c o n t e g g i o ( int n ) { p r i n t f ( " m e n o % d . . . \ n ", n );

}

int m a i n ( v o i d ) { int i ;

for ( i = 10; i > 0; - - i ) s t a m p a _ c o n t e g g i o ( i );

r e t u r n 0;

}

(34)

Definizione di funzioni

La forma generale di una funzione `e la seguente:

T I P O _ R E S T I T U I T O N O M E _ F U N Z I O N E ( P A R A M E T R I ) { D I C H I A R A Z I O N I

I S T R U Z I O N I }

TIPO RESTITUITO

E’ il tipo del valore che la funzione restituisce mediante ilreturn:

I le funzioni non possono restituire array, ma non ci sono restrizioni sugli altri tipi;

I seTIPO_RESTITUITO`e void, la funzione non restituisce alcun valore;

I se il TIPO_RESTITUITOè omesso, per default è int; è comunque meglio indicarlo sempre!

NOME FUNZIONE

E’ il nome della funzione, si usa perchiamarela funzione stessa.

(35)

Definizione di funzioni - continua

PARAMETRI

E’ una lista di parametri separati da virgole.

I ciascun parametro deve essere preceduto dal suo tipo (il tipo va ripetuto anche se ci sono pi`u parametri dello stesso tipo) f l o a t m e d i a ( f l o a t x , y ) /∗ SBAGLIATO ! ∗/

Corpo della funzione

Il corpo della funzione pu`o contenere dichiarazioni e istruzioni; le variabili dichiarate nel corpo di una funzione si chiamanolocali.

f l o a t m e d i a (f l o a t x , f l o a t y ) {

f l o a t sum ; /∗ dichiarazione ∗/

sum = x + y ; /∗ istruzione ∗/

r e t u r n sum / 2; /∗ istruzione ∗/

}

(36)

Chiamata di funzioni

I Una chiamata di funzione consiste nel nome della funzione seguito da una lista di argomentitra parentesi.

m e d i a ( 3 , 6 ) m e d i a ( a , b * b ) s t a m p a _ c o n t e g g i o ( 9 ) g e t c h a r ( )

I La chiamata di una funzione coinvolge sempre due funzioni (che possono anche coincidere, nella ricorsione):

I una funzionechiamante I e una funzionechiamata.

Nei primi esempi, la funzione chiamante `e il main.

I Quando una funzione viene chiamata, il controllo passa dalla funzione chiamante alla funzione chiamata. Quando questa termina (alla fine delle istruzioni oppure in presenza

dell’istruzione return), restituisce il controllo alla funzione chiamante.

(37)

Chiamata di funzioni - continua

I Se mancano le parentesi, la funzione non verrà chiamata. Se una funzione è di tipo void, bisognerà chiamarla cos`ı:

g e t c h a r ( );

I Una chiamata di funzione di tipo void `e una istruzione, quindi deve concludersi con punto-e-virgola;

s t a m p a _ c o n t e g g i o ( 9 );

I Una chiamata di funzione di tipo non void `e un’espressione e produce un valore che pu`o essere assegnato ad una variabile, testato, stampato, ecc

m = m e d i a ( 3 , 6 );

if ( m e d i a ( a , b * b ) > c ) p r i n t f ( " ... " );

I Il valore restituito da una funzione pu`o essere scartato:

p r i n t f ( " C i a o m o n d o !\ n " );

c h a r s = p r i n t f ( " C i a o m o n d o !\ n " );

(38)

Dichiarazione di funzioni

I La definizione di una funzione non deve necessariamente precedere il punto in cui viene chiamata. Ad esempio, le definizioni di funzioni possono seguire il main.

I Se il compilatore trova una chiamata prima della definizione, non sa quanti e di che tipo siano i parametri, quindi fa delle assunzioni e effettua dei casting. Non `e detto che le queste assunzioni siano corrette!

I Per evitare questo problema, `e possibiledichiarare le funzioni prima che vengano chiamate.

T I P O _ R E S T I T U I T O N O M E _ F U N Z I O N E ( P A R A M E T R I );

Una dichiarazione di questo tipo si chiama prototipoo segnatura.

I Attenzione: ci deve essere coerenza tra dichiarazione e definizione!!

(39)

Esempio: media rivisitata

# i n c l u d e < s t d i o . h >

/∗ prototipo della funzione media ∗/

f l o a t m e d i a (f l o a t x , f l o a t y );

/∗ main ∗/

int m a i n ( v o i d ) { f l o a t a , b , c , m ;

s c a n f ( " % f % f % f ", & a , & b , & c );

p r i n t f ( " La m e d i a tra % f e % f e ’ % f \ n ", a , b , m e d i a ( a , b ) );

r e t u r n 0;

}

/∗ definizione della funzione media ∗/

f l o a t m e d i a (f l o a t x , f l o a t y ) { r e t u r n ( x + y ) / 2;

}

(40)

Parametri e argomenti

I Iparametri di una funzione compaiono nella sua definizione:

sono nomi che rappresentano i valori da fornire alla funzione al momento della chiamata.

I Gliargomenti sono invece leespressioni che compaiono nella chiamata di funzione tra parentesi.

I A volte i parametri sono chiamati parametri formali mentre gli argomenti sono chiamati parametri attuali.

I Se il tipo di un argomento non corrisponde al tipo del parametro, viene eseguita una conversione coerente con il prototipo della funzione oppure una conversione di default.

I Gli argomenti sonopassati per valore: al momento della chiamata, ogni argomento `e valutato e il valore `e assegnato al corrispondente parametro; eventuali cambiamenti di valore dei parametri durante l’esecuzione della funzione noninfluenzano il valore dell’argomento!

(41)

Parametri e variabili locali

Levariabili locali hanno le seguenti propriet`a:

I sono utilizzabili solo dal punto in cui sono dichiarate fino alla fine della stessa funzione (block scope);

I non possono essere usate o modificate da altre funzioni;

I sono automaticaticamente allocate al momento della chiamata della funzione e deallocate al return (automatic storage duration);

I alla fine dell’esecuzione della funzionenon conservanoil loro valore.

Iparametrihanno le stesse propriet`a (block scope e automatico storage duration) delle variabili locali. Di fatto, la sola differenza tra variabili locali e parametri `e che i parametri vengono

inizializzati al momento della chiamata (con il valore degli argomenti della chiamata).

(42)

Conversione di tipi

I In C sono consentiti assegnamenti ed espressioni che mescolano i tipi, ma alcuni operandi verranno convertiti automaticamente (implicitamente) in modo da rendere possibile la valutazione dell’espressione.

I Nelle chiamate di funzione `e consentito passare argomenti di tipo diverso da quelli dei parametri; anche in questo caso si avranno delle conversioni implicite.

I Le regole di conversione implicita sono complicate! In sintesi:

I nelle espressioni aritmetiche gli operandi vengonopromossi;

I negli assegnamenti il lato destro viene convertito al tipo del lato sinistro;

I se la funzione `e dichiarata/definita prima della chiamata, ogni argomento `e convertito implicitamente al tipo del parametro corrispondente;

I se la funzione non `e dichiarata/definita prima della chiamata, il compliatore esegue delle promozioni di default

I E’ possibile anche effettuare conversioni esplicite con ilcast.

(43)

Array come argomenti

I Se il vettore `e unidimensionale, la dimensione pu`o essere omessa.

int f ( int a [] ) { ... }

I Se il vettore `e multidimensionale, solo la prima dimensione pu`o essere omessa.

int f ( int a [][ LUN ] ) { ... }

I la funzione non ha modo di sapere quanto è lungo il vettore (l’operatore sizeofnon può essere usato...) quindi può essere utile passare la lunghezza come parametro aggiuntivo:

int s o m m a _ a r r a y ( int a [] , int n ) { int i , sum = 0;

for ( i = 0; i < n ; i ++ ) sum += a [ i ];

r e t u r n sum ; }

(44)

L’istruzione return

I Ogni funzione non void contiene l’istruzione return per specificare quale valore deve essere restituito alla funzione chiamante.

r e t u r n E S P R E S S I O N E ;

I L’espressione pu`o essere una semplice costante o variabile, oppure un’espressione pi`u complicata (del tipo giusto!)

r e t u r n i > j ? i : j ;

I L’esecuzione dell’istruzione return ha per effetto la restituzione del controllo alla funzione chiamante. La restituzione del controllo alla funzione chiamante avviene comunque al termine dell’esecuzione della funzione.

I Il valore restituito dal main `e uncodice di stato: il codice 0 indica la terminazione senza errori.

(45)

Organizzazione dei programmi

Quando un programma è costituito da più di una funzione, è importante organizzarlo bene!

I Ricordare che variabili locali e parametri hanno block scope e automatic storage duration;

I Le funzioni comunicano fra loro attraverso i parametri, oppure attraverso variabili esterneo globali, che hanno queste

propriet`a:

I sono definite fuori dal corpo di ogni funzione;

I hanno static storage duration, cio`e permangono e mantengono il loro valore indefinitamente;

I sono visibili dal punto in cui sono definite per tutto il file.

(46)

Organizzazione dei programmi - continua

In generale, un programma pu`o essere organizzato come segue:

I direttive#include I direttive#define

I definizione di tipi contypedef I dichiarazione di variabili esterne I prototipi delle funzioni diverse dalmain I definizione del main

I definizione delle altre funzioni

(47)

Esercizi

I Scrivete una funzione avente due parametri interi b ed e che calcoli la potenza b^e.

I Scrivete una funzione con parametro un intero n che stabilisca se n `e un numero primo.

I Scrivete un programma che generi a caso un array di interi e calcoli la somma dei suoi elementi: strutturate il programma usando una funzione per generare l’array e una per sommare i suoi elementi.

I Scrivete una variante dell’esercizio precedente per un array bidimensionale.

(48)

Esercizi - continua

I Scrivete un programma che legga un carattere, uno spazio e quindi una sequenza di caratteri minuscoli terminati da ’.’e che stampi quanto ha letto dopo il primo spazio, ma

sostituendo tutte le vocali con il primo carattere letto. Per farlo, usate una funzione che, dati due caratteri, restituisca il primo carattere se il secondo `e una vocale minuscola,

altrimenti restituisca il secondo carattere.

I Rivedete gli esercizi svolti nelle esercitazioni precedenti e provate a strutturarli usando delle funzioni. Ad esempio, modificate l’esercizio sulla rubrica usando una funzione per stampare la rubrica, una per leggere una nuova voce, una per inserire la nuova voce nell’ordine corretto.

(49)

Overloading

A differenza di Java, in C non `e possibile fare overloading, ovvero, non si possono definire due funzioni con lo stesso nome e

propotipo diverso!

int m e d i a _ i n t ( int x , int y ) { r e t u r n ( x + y ) / 2

}

f l o a t m e d i a _ f l o a t ( f l o a t x , f l o a t y ) { r e t u r n ( x + y ) / 2.0

}

(50)

Lista di parametri a lunghezza variabile

I Esistono funzioni con numero di parametri variabile (es:

printf);

I Il file di intestazionestdarg.h fornisce gli strumenti per poterle gestire (qui non le vediamo, si veda il capitolo 26 del libro).

I Attenzione: chiamare una funzione di questo tipo `e un’operazione sempre rischiosa!

(51)

Funzioni ricorsive

Una funzione si dicericorsivaquando chiama se stessa.

int f a c t ( int n ) { if ( n <= 1 )

r e t u r n 1;

e l s e

r e t u r n n * f a c t ( n - 1 );

}

Le chiamate ricorsive siimpilano.

Ad esempio, tracciamo l’esecuzione della chiamatafact(3): fact(3)chiama

fact(2) che chiama

fact(1)che restituisce 1, quindi fact(2) restituisce 2 × 1 = 2, quindi fact(3)restituisce 3 × 2 = 6.

(52)

Esempio

La potenza può essere definita ricorsivamente, osservando che b⁰ = 1 e bê= b ∗ bê−1 per ogni e > 0.

int p o w e r ( int b , int e ) { if ( e = = 0 )

r e t u r n 1;

e l s e

r e t u r n b * p o w e r ( b , e - 1 );

}

La chiamatapower(5, 3) sar`a eseguita come segue:

power(5, 3) chiama power(5, 2) che chiama

power(5, 1)che chiama

power(5, 0) che restituisce 1, quindi power(5, 1)restituisce 5 × 1 = 5, quindi power(5, 2) restituisce 5 × 5 = 25, quindi power(5, 3) restituisce 5 × 25 = 125.

(53)

Algoritmi di ordinamento

I Abbiamo gi`a implementato l’ordinamento per inserimento, utile per riempire un array mantenendolo ordinato ad ogni passo.

I Ora vediamo alcuni algoritmi di ordinamento classici, usati per ordinare un array gi`a riempito ma in disordine.

I selection sort (in italiano ordinamento per selezione);

I mergesort(in italiano ordinamento per immersione);

I Tutti e due gli algoritmi sono basati suiconfronti tra elementi e sono ricorsivi: la base della ricorsione `e data dagli array di lunghezza 0 o 1, che sono sempre ordinati.

I Per semplicit`a faremo riferimento soltanto ad array di interi.

(54)

selectionsort ( int a[ ], int n )

Ordina i primi n elementi del vettore a, procedendo come segue:

1. cerca in a l’elemento massimo e lo scambia con l’elemento nell’ultima posizione dell’array;

2. richiama ricorsivamente se stessa per ordinare i primi n − 1 elementi dell’array.

Esempio su input a = 15, 29, 11, 7

selectionsort( a, 4 ) 15 29 11 7

15 7 11 29

11 7 15 29 selectionsort( a, 2 ) 11 7 15 29 7 11 15 29 selectionsort( a, 1 ) 7 11 15 29

7 11 15 29

(55)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(56)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(57)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(58)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(59)

selectionsort ( int a[ ], int n )

15 7 11 29

11 7 15 29

selectionsort( a, 2 ) 11 7 15 29 7 11 15 29 selectionsort( a, 1 ) 7 11 15 29

7 11 15 29

(60)

selectionsort ( int a[ ], int n )

15 7 11 29

11 7 15 29 selectionsort( a, 2 ) 11 7 15 29

7 11 15 29 selectionsort( a, 1 ) 7 11 15 29

7 11 15 29

(61)

selectionsort ( int a[ ], int n )

15 7 11 29

11 7 15 29 selectionsort( a, 2 ) 11 7 15 29 7 11 15 29

7 11 15 29

(62)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(63)

selectionsort ( int a[ ], int n )

15 7 11 29

7 11 15 29

(64)

mergesort ( int a[ ], int sx, int dx )

Ordina la parte dell’array a compresa tra gli indici sx e dx , come segue:

1. divide l’array in due sotto-array di dimensione circa uguale;

2. ordina il sotto-array di sinistra richiamando se stessa;

3. ordina il sotto-array di destra richiamando se stessa;

4. integra (merge) i due sotto-array in un unico array ordinato.

La base della ricorsione `e data dagli array di lunghezza 0 o 1, che sono sempre ordinati.

(65)

merging

La parte di integrazione (merge) di due array ordinatia1ea2funziona con un vettore di supportob:

I si scorrono entrambi gli array da sinistra a destra usando due indicatorii1ei2rispettivamente;

I ad ogni passo si confronta a1[i1]cona2[i2]e si sceglie l’elemento pi`u piccolo, lo si copia nell’array di supportob(nella prima posizione libera) e si incrementa l’indicatore relativo ad esso;

I quandoi1esce daa1oppurei2esce daa2, la parte rimanente dell’altro array viene copiata inb;

I alla fine si copia il contenuto dell’arraybnell’array originale.

a1 a2

· · · 3 5 11 1 12 13 · · ·

b

· · · · · ·

(66)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · · · ·

k

(67)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 · · ·

k

(68)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 · · ·

k

(69)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 3 · · ·

k

(70)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 3 · · ·

k

(71)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 3 5 · · ·

k

(72)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 3 5 · · ·

k

(73)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2

b

· · · 1 3 5 11 · · ·

k

(74)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

i1 i2 b

· · · 1 3 5 11 · · ·

k

(75)

merging

a1 a2

· · · 3 5 11 1 12 13 · · ·

b

· · · 1 3 5 11 12 13 · · ·

(76)

mergesort ( int a[ ], int sx, int dx )

Ordina la parte dell’array a compresa tra gli indici sx e dx , come segue:

1. divide l’array in due sotto-array di dimensione circa uguale;

2. ordina il sotto-array di sinistra richiamando se stessa;

3. ordina il sotto-array di destra richiamando se stessa;

4. integra (merge) i due sotto-array in un unico array ordinato.

La base della ricorsione `e data dagli array di lunghezza 0 o 1, che sono sempre ordinati.