Quarta parte degli appunti delle lezioni del corso di Programmazione I con laboratorio (A.A. 2011/12)

Parte 4

Efficienza e precisione

contro immediatezza e semplicità

● Il linguaggio Python è molto semplice e

consente di scrivere rapidamente un codice eseguibile

● Ma in molte situazioni l'efficienza è un requisito

indispensabile e il Python è troppo lento per certi tipi di applicazione

● Una maggiore efficienza si ottiene usando

linguaggi compilati, come il linguaggio C, anziché interpretati

Differenze tra Python e C

● Tra C e Python esistono varie differenze a vari

livelli

● Modalità di esecuzione: interattiva, a linea di

comando per Python, solo batch per C

● Python è interpretato, C è compilato

● Tipizzazione statica per C, dinamica per Python ● Utilizzo di puntatori e operazioni esplicite di

gestione della memoria per C, uso di riferimenti e gestione trasparente della memoria in Python

Differenze tra Python e C

● Obbligo di dichiarazione delle variabili in C,

mancanza del costrutto in Python

● Una maggiore richezza di strutture di controllo

in C (do-while, switch, goto) rispetto a Python

● Istruzioni di I/O molto diverse tra C e Python

● Possibilità di gestione avanzata di sequenze e

stringhe in Python contro una gestione "spartana" in C

Compilazione

● I programmi in C devono essere compilati

prima di essere eseguiti

● La traduzione è suddivisa in varie fasi che sono

svolte tutte prima dell'esecuzione

● Il risultato finale della compilazione è di solito

un programma "eseguibile", la traduzione in

linguaggio macchina del programma originale, detto "sorgente"

Esecuzione

● L'esecuzione di un programma C è a carico del

sistema operativo e del processore: non c'è

nessun ambiente di esecuzione come invece è presente in Python

● Perciò un programma C deve provvedere

anche a ricevere i dati (tramite operazioni di input) e a visualizzare i risultati (tramite

operazioni di output), mentre in Python in genere non ve ne è bisogno

Esempio di programma

● Il primo programma C #include <stdio.h> int main( ) { printf("Hello world\n"); }

Elementi di sintassi del C

● come il Python, è case sensitive

● si può andare a capo e indentare liberamente ● le istruzioni sono concluse dal punto e virgola ● Le istruzioni sono raggruppate tra parentesi

graffe

main

● L'esecuzione di un programma C parte dalla

funzione main

● Perciò main deve contenere tutte le istruzioni

che devono essere eseguite “subito”

● Le altre funzioni saranno eseguite solo se

Tipizzazione

● Ogni dato trattato da un programma appartiene

ad un tipo di dato

● Il computer ha bisogno di sapere in ogni

operazione i tipi di dato coinvolti

● L'operazione potrebbe essere impossibile o non

definita (in Python la divisione tra due booleani)

● L'operazione potrebbe essere svolta in modi diversi

(l'addizione tra numeri interi si esegue in modo diverso dall'addizione tra numeri reali)

Tipizzazione dinamica

● Il linguaggio Python controlla i tipi solo

immediatamente prima dell'esecuzione delle istruzioni: la tipizzazione è dinamica

● Ad esempio l'istruzione

a=b+c

potrebbe essere

● La somma di due numeri interi ● La somma di due numeri reali

● La concatenazione di due sequenze o due stringhe ● (in tutti gli altri casi) Un'operazione non valida

Tipizzazione dinamica

● Non è possibile dire a priori se a=b+c è valida e

a che cosa corrisponde

● Fino all'ultimo b e c potrebbe cambiare tipo

● Il controllo dei tipi in Python può essere quindi

Tipizzazione statica

● Il linguaggio C invece è in grado di controllare i

tipi al momento della compilazione: la tipizzazione è statica

● E' in grado di fare il controllo in anticipo perché

in C le variabili e le funzioni sono dichiarate esplicitamente

● Per cui analizzando il programma (e non

aspettando la sua esecuzione) si sa già con certezza se l'istruzione può essere eseguita e in che modo

Confronto tra le due tipizzazioni

● La tipizzazione statica rende l'esecuzione più

veloce, in quanto il C, durante l'esecuzione di un programma, non deve controllare nulla

● In Python ogni volta che un'istruzione viene

eseguita, deve essere controllato il tipo degli operandi (si pensi ad istruzioni ripetute tante volte...)

● D'altro canto, la tipizzazione dinamica consente

Confronto tra le due tipizzazioni

● Ad esempio in Python è possibile scrivere una

funzione "massimo" generica def massimo(x,y):

if x>y:

return x else:

return y

● Può calcolare il massimo tra due numeri interi,

due numeri reali, due stringhe, ecc.

Tipi di dato presenti in C

● Tipi elementari

● Numeri interi: int, long, short, char e versioni

unsigned

● Numeri reali: float, double, long double ● puntatori ● enum ● Tipi strutturati ● array ● struct ● union

Dichiarazione delle variabili

● In C è obbligatorio dichiarare le variabili, ovvero

indicare il nome, il tipo di dato e l'eventuale valore iniziale

● Il tentativo di utilizzo di una variabile non

dichiarata genera un errore in compilazione

● Si possono dichiarare le variabili in due

modalità:

● Locali ● Globali

Variabili locali e globali

● Le variabili locali sono dichiarate all'inizio di una

funzione (o di un blocco) e sono utilizzabili solo all'interno della funzione (o del blocco)

● Le variabili globali sono dichiarate all'inizio del

programma, fuori di ogni funzione, e sono utilizzabili in tutto il programma

Dichiarazione delle variabili

● La dichiarazione delle variabili si fa come

nell'esempio seguente int main( ) { int x,y,z; double r=1.1, s, t=0; int i; char sep=',';

● Cioè prima il tipo, poi i nomi delle variabili e per

Istruzioni elementari

● In C come in Python l'istruzione di base è

l'assegnamento

● La sintassi è analoga a quella del Python

variabile = espressione

● Il vincolo è che non si può assegnare ad una

variabile un valore che non appartiene al tipo di dato della variabile

● Ad esempio

double x; x=”ciao”;

Operatori alternativi di

assegnamento

● In C, come in Python, è possibile usare

operatori composti di assegnamento del tipo +=

● a+=b corrisponde all'istruzione a=a+b ● In maniera analoga si ha -=, *=, /=, ecc. ● Altri operatori particolari sono ++ e –

● a++ corrisponde all'istruzione a=a+1 ● a-- corrisponde all'istruzione a=a-1

● E' leggermente diverso scrivere ++a e --a

(consultare un manuale per vedere la differenza)

Istruzione printf

● Serve a scrivere dei dati sullo schermo, in

modo simile alla print di Python

● Il primo argomento di printf è il "formato" ed è

una stringa che contiene caratteri normali (che vengono scritti sullo schermo così come sono), caratteri di controllo (\n va a capo, ecc.) e codici di formato

● Quest'ultimi iniziano con % e indicano che al

loro posto deve essere scritto l'argomento successivo (il secondo, il terzo, ecc.)

Codici di formato

● I principali codici di formato sono ● %d numero intero in base 10

● %X numero intero in base 16 ● %f numero reale float

● %lf numero reale double

● %c singolo carattere (char) ● %s stringa

Esempio di printf

● Ad esempio con

int a=3;

double x=8.1;

printf("a vale %d e x vale %lf\n",a,x);

scriverà

Istruzione scanf

● Serve a leggere dei dati da tastiera, in modo

simile a quello che fa input in Python

● Il primo argomento di scanf è il formato che

contiene, normalmente, solo i codici di controllo dei dati da leggere

● Ogni codice corrisponde ad uno degli

argomenti successivi, che devono essere variabili precedute dall'operatore &

● Ogni dato letto sarà memorizzato nella variabile

Esempio di scanf

● Ad esempio

int k; double x;

printf(“Introduci un numero intero e un numero reale “);

scanf(“%d %lf”,&k,&x);

● Se l'utente scrive

4 -1.3

ad k sarà assegnato il valore 4 e a x il valore -1.3

Blocchi

● I blocchi sono gruppi di istruzioni racchiuse tra

una parentesi graffa aperta e una chiusa

● Un blocco è eseguito in modo sequenziale:

un'istruzione dopo l'altra

● Un blocco conta come una singola istruzione e

quindi si può usare un blocco ogni volta che in un contesto si deve usare una istruzione

● Se in un blocco è presente una sola istruzione,

allora le graffe sono inutili

● Quando si definisce una funzione, si deve

Blocco

In un blocco si possono dichiarare variabili, che saranno locali al blocco

{ int a,b; double vx=c,vy=2*d; a=5; z=z+a; printf(“%lf\n”, vx-vy); }

Operatori logici

● In C non esiste il tipo di dato bool, si usano gli

int al loro posto, con la convenzione True è 1 e False è 0

● Gli operatori di confronto

< > <= >= == !=

sono identici in C e in Python

● Gli operatori booleani sono diversi

Python C

and &&

or ||

Istruzione if-else

● L'istruzione if funziona nello stesso modo che in

Python e ha anche una sintassi simile

Python C if condizione: if(condizione) { istruzione istruzione ... ... istruzione istruzione } else: else { istruzione istruzione ... ... istruzione istruzione }

Istruzione if-else

● Si noti che la condizione dell'if deve essere

racchiusa tra parentesi tonde

● Inoltre le parentesi graffe che racchiudono i due

gruppi di istruzioni sono facoltative se all'interno c'è una sola istruzione

Esempio di if-else

if(x>y) { massimo=x; minimo=y; } else { massimo=y; minimo=x; }

If-else

● La parte else è facoltativa, come in Python ● Ad esempio

min=a; if(a>b) {

min=b; }

● Invece la clausola “elif “ non esiste in C, al suo

posto si usano degli if-else nidificati

● Tale costrutto, presente anche in altri linguaggi,

If-else if

Python if a>10: b=1 elif a>5: b=2 elif a>3: b=3 else: b=4 C If (a>10) { b=1; } else if (a>5) { b=2; } else if (a>3) { b=3; } else { b=4; }

Istruzione switch/case

● In C esiste anche l'istruzione switch/case che

consente di operare una scelta tra un numero finito di alternative secondo il valore di

un'espressione

● Ha una sintassi particolare e può essere usata

solo su numeri interi o caratteri singoli (non con numeri reali o stringhe)

● Ogni clausola case corrisponde al confronto tra

Esempio di switch/case

C Python switch(mese) { if mese==4 or case 4: mese==6 or case 6: mese==9 or case 9: mese==11: case 11: giorni=30

giorni=30; elif mese==2:

break; giorni=28 case 2: else: giorni=28; giorni=31 break; default: giorni=31;

Istruzione while

● L'istruzione while funziona nello stesso modo

che in Python e ha anche una sintassi simile

Python C

while condizione: while(condizione) { istruzione istruzione

... ...

Esempio di while

while(a>0 && b>0) { a=a-c;

b=b-d; }

Istruzione do-while

● Il C ha una seconda istruzione iterativa,

speculare rispetto al while do {

istruzione …

istruzione

} while(condizione);

in cui la condizione è valutata alla fine di ogni iterazione (e non all'inizio come nel ciclo while)

Istruzione do-while

● Il ciclo do-while corrisponde al seguente

Esempio di do-while

do {

printf(“inserisci un numero positivo “); scanf(“%d”,&num);

} while(num<=0);

● Ripete il ciclo fintantoché l'utente inserisce

numeri non positivi

● Fa almeno la prima iterazione (cioè legge il

Confronto tra while e do-while

● Il ciclo do-while si usa in tutti quei casi in cui il

ciclo deve necessariamente svolgere almeno un'iterazione

● Invece nel while, se la condizione è subito

falsa, il ciclo termina immediatamente senza che le istruzioni associate siano eseguite

Istruzione for

● I cicli for in Python e in C assumono varie forme

e sono sostanzialmente diversi

● Il ciclo for su intervallo

Python C

for J in range(A,B): for(J=A;J<B;J++) {

istruzione istruzione

… ...

istruzione istruzione }

● J deve essere una variabile int, A e B possono

essere espressioni int, è meglio se B è una costante o una variabile

Esempio di ciclo for

Al posto di J<B, si può anche usare J<=B, in tal caso è come se fosse un range da A a B

incluso

● Ad esempio per andare da 1 a n incluso

fattoriale=1;

for(i=1; i<=n; i++) {

fattoriale=fattoriale*i; }

Ciclo for all'indietro

for(i=10;i>=1;i--) {

printf(“meno %d\n”,i); }

● Svolge un ciclo da 10 a 1 (incluso) con passo

-1

● Il passo può essere diverso da 1 e da -1, in tal

caso l'aggiornamento non è i++ o i--, ma i += passo

Ciclo for generico

● Il ciclo for visto in precedenza si può scrivere

anche con un ciclo while J=A;

while(J<=B) { istruzioni J++;

}

● Quando un ciclo while assume questa forma

(inizializzazione, condizione e aggiornamento) lo si può scrivere con un ciclo for generico

inizializzazione condizione

Ciclo for generico

● In C il ciclo for generico può assumere la forma

for(inizializzazione ; condizione ; aggiornamento) {

istruzione ...

istruzione }

in cui inizializzazione ed aggiornamento sono di solito istruzioni di assegnamento, mentre

condizione è una qualsiasi condizione di

Ciclo for generico

● La forma di ciclo for

for(e1; e2; e3) { S

}

equivale al ciclo while

e1;

while(e2) { S

e3;

Ciclo for generico

● Il ciclo for generico corrisponde al seguente

Istruzioni di "salto"

● Le istruzioni break e continue ci sono anche in

C e funzionano allo stesso modo

● break interrompe un ciclo (si usa anche nello

switch)

● continue passa all'iterazione successiva

● In C è presente anche l'istruzione goto, il cui

Definizione di funzione

● In C è possibile definire funzioni in modo simile

a quanto visto in Python

Python C

def fattoriale(n): int fattoriale(int n) {

p=1 int p=1,i;

for i in range(1,n): for(i=1;i<=n;i++) {

p=p*i p=p*i; }

return p return p;

Prototipo della funzione

● Nella prima riga della definizione di una

funzione si indica

● Il tipo restituito dalla funzione ● Il nome della funzione

● I parametri (tipo e nome per ognuno)

● L'istruzione return funziona come in Python

● Termina l'esecuzione della funzione ● Indica il risultato da restituire

Definizione di funzioni

● Le funzioni devono essere definite prima del

loro utilizzo

● Il modo più semplice è definire tutte le funzioni

prima del main, del tipo

int funzione1(int a,int b) { .... } double funzione2(double x) { ... } int main( ) { ... }

Definizione e dichiarazione

● In realtà si può usare una funzione anche dopo

che è stata solamente dichiarata (cioè dopo che è stato scritto il prototipo)

● La funzione però deve essere successivamente

definita, oppure deve essere già stata compilata

Esempio

#include <stdio.h> int fattoriale(int n); int main( ) { printf("5!=%d\n",fattoriale(5)); } int fattoriale(int n) { int p=1,i; ... Dichiarazione (prototipo) Definizione

Tipi restituiti

● Una funzione può restituire solo un risultato e

solo di tipo elementare (intero, reale o puntatore)

● Una funzione può anche non avere risultati

espliciti. In tal caso

● il tipo del risultato è void

● L'istruzione return non è necessaria, tranne che per

Array

● Gli array del C sono simili alle sequenze del

Python

● Hanno però una dimensione fissa, indicata al

momento della dichiarazione, e che deve

essere una costante (secondo lo standard C 89)

● Esempio di dichiarazione di una variabile array

int vettore[10]

Lavorare con gli array

● L'accesso all'i-esima componente di un array è

l'unica operazione supportata dal C e funziona come in Python: a[i]

● Tutte le altre operazioni sugli array

(assegnamento, input, output, ecc.) debbono essere svolte tramite dei cicli for

● Ad esempio per copiare l'array a di 10 int

sull'array b (sempre di 10 int) for(i=0;i<10;i++) {

Lavorare con gli array

● Per leggere da tastiera l'array a

for(i=0;i<10;i++) {

scanf("%d",&a[i]); }

● Per scrivere sullo schermo l'array a

for(i=0;i<10;i++) {

Dimensionamento di un array

● Dato che la dimensione di un array è fissa e

costante, deve essere determinata per

eccesso: la dimensione indica quanti elementi al massimo saranno utilizzati

● E' frequente usare come dimensione una

costante definita con #define #define N 10

int a[N];

● Nel programma si usa N al posto di 10, quando

si intende la dimensione di a

#define ha una sintassi particolare, non simile al C usuale

Caratteri e stringhe

● Il tipo di dato char consente di memorizzare un

singolo carattere

● Ad esempio per memorizzare il sesso di una

persona si usa M o F char sesso;

sesso='F';

in cui 'F' indica il carattere singolo F maiuscolo

● In generale le costanti char si scrivono tra

Stringhe

● Le stringhe in C sono particolari array di char

(quindi hanno una dimensione fissa), ad esempio char nome[20]

● Una variabile stringa può contenere una

sequenza di caratteri conclusa con un particolare carattere "nullo" \0

● Questo carattere non viene preso in

considerazione, ma serve per segnalare la fine della stringa

Stringhe

● Le costanti stringa sono delimitate dalle

virgolette e includono già il carattere \0

● Ad esempio

"Marco" costante stringa "M" costante stringa

Gestione delle stringhe

● Per lavorare con le stringhe è necessario usare

le funzioni di libreria (bisogna dare il comando #include <string.h>)

● Le principali funzioni sono

● strlen ● strcpy ● strcmp ● strcat

Operazioni sulle stringhe

● strcpy(s,t) copia la stringa t sulla variabile

stringa s (che deve avere almeno la stessa dimensione di t). Ad es. strcpy(nome,"Marco")

● strlen(s) calcola la lunghezza della stringa s

(senza contare il carattere \0)

● strcmp(s,t) confronta la stringa s con la stringa

t, restituendo 0 se sono uguali, un numero

positivo se s segue t nell'ordine lessicografico, un numero negativo altrimenti

Operazioni sulle stringhe

● strcmp(nome,"Marco") fa 0, mentre

strcmp(nome,"Mara") è un num. Positivo dato che "Marco" segue "Mara"

● strcat(s,t) concatena s con t, mettendo il

risultato in s. s deve avere una dimensione sufficiente.

Ad esempio

char s[100],t[40]; strcpy(s,"Infor"); strcpy(t,"matica");

Operazioni con le stringhe

● Per leggere da tastiera una stringa che può

contenere spazi usare gets gets(t);

● Se non contiene spazi si può usare scanf

Strutture

● Le strutture sono aggregazioni di dati non

omogenei ● Ad esempio struct persona { char nome[20]; char cognome[30]; int eta; char sesso; };

Strutture

● A questo punto è possibile dichiarare variabili di

tipo struct persona ed usarle, in modo simile a quanto avviene in Python

int main() { struct persona p; strcpy(p.cognome,”Rossi”); strcpy(p.nome,”Mario”); p.eta=50; p.sesso='M';

Strutture

● Non è possibile leggere da tastiera o scrivere

sullo schermo una struttura (come del resto per gli array)

● E' invece possibile assegnare una variabile

struttura ad un'altra (dello stesso tipo)

● struct persona p1,p2;

…

p1=p2;

● A differenza di Python, questo assegnamento

Puntatori

● Un puntatore è una variabile che può contenere

l'indirizzo di un'altra variabile

● L'indirizzo di una variabile si estrae con

l'operatore &

● Per dichiarare che una variabile è un puntatore

si mette l'asterisco davanti al nome nella dichiarazione

Puntatori

● Ad esempio int a; int *p; a=10; p=&a;

dichiara che p è un puntatore ad int e poi assegna a p l'indirizzo della variabile a

Collegamento puntatore-variabile

a p 10 indirizzo di a AB8910 AB8910

Puntatori e tipi

● Non è possibile assegnare ad un puntatore di

un certo tipo T l'indirizzo di una variabile di un tipo diverso da T

● Ad esempio

double x; int *p;

p=&x; è illegale

● E' possibile però dichiarare che p è un

puntatore “generico”, con void *p

Operatore di redirezione

● Se p è un puntatore (non di tipo void*) che

contiene l'indirizzo di una variabile v, allora è possibile accedere a v tramite p usando

l'operazione *p ● int *p; int a; p=&a; *p=5; printf(“%d %d”,a,*p);

Operatore di ridirezione

● Situazione attuale a p 10 indirizzo di a AB8910 AB8910

Operatore di ridirezione

● L'operazione *p in generale significa “entra

nella cella di memoria il cui indirizzo è contenuto in p” e

● modifica il contenuto della cella, se *p sta a sinistra

di un assegnamento, esempio *p=10;

● usa il contenuto della cella, se *p sta in

un'espressione, esempio printf(“%d”,*p);

● Si ha errore (forse...) se p non contiene un

Uso dei puntatori in C

● I puntatori hanno un uso abbastanza diffuso in C

● Servono per far sì che una funzione possa modificare

un argomento della chiamata

● Servono quando un parametro è di tipo array o

struttura

● Servono quando una funzione deve restituire più

risultati

● Servono a gestire variabili dinamiche (soprattutto

array)

● Servono ad implementare le strutture dati dinamiche

(liste, alberi, ecc.)

Passaggio per valore

● Questo esempio non funziona, come in Python

void scambia(int x,int y) { int temp; temp=x; x=y; y=temp; } int main() { int a=7, b=11; scambia(a,b); printf("a=%d b=%d\n",a,b); Il passaggio di a e b è per valore: x e y sono una

copia di tali dati

la funzione "scambia" è in grado solo di scambiare x con y, ma non a con b

Passaggio tramite i puntatori

● Con i puntatori funziona

void scambia(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; } int main() { int a=7, b=11; scambia(&a,&b);

Passaggio tramite puntatore

a b 7 11 indirizzi E2C344 E2C348 E2C344 E2C348 x y

Passaggio per puntatore

● temp=*x; a b 7 11 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 temp

Passaggio per puntatore

● *x=*y; a b 11 11 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 temp

Passaggio per puntatore

● *y=temp; a b 11 7 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 temp

Uso dei puntatori per ottenere più

risultati

● Una funzione C può restituire un solo risultato ● Supponiamo di voler risolvere un'equazione di

II grado

a x2_+bx+c=0

a partire dai tre coefficienti reali

● L'equazione potrebbe avere 0, 1, 2 soluzioni

distinte, le quali si ottengono con le note formule

● Vediamo come disegnare una funzione che

restituisce sia il numero di soluzioni, che i rispettivi valori

Schema

● L'idea è di passare alla funzione 3 indirizzi su

cui la funzione scriverà il numero di soluzioni e i rispettivi valori

● Lo schema è

a b c

risolvi_eq2grado

Soluzione equazione II grado

void risolvi_eq2grado(double a,double b,double c, int *ns, double *x1, double *x2) {

double delta, rdelta; delta=b*b-4*a*c; if(delta>0) { *ns=2; rdelta=sqrt(delta); *x1=(-b-rdelta)/(2*a); *x2=(-b+rdelta)/(2*a); } else if(delta==0) { *ns=1; *x1=-b/(2*a); } else { *ns=0; } }

Soluzione equazione II grado

int main() {

int n; double r1,r2;

risolvi_eq2grado(1,-6,7,&n,&r1,&r2); if(n==0) {

printf(“no soluzioni reali\n”); } else if(n==1) {

printf(“soluzioni reali coincidenti %lf\n”,r1); } else {

printf(“soluzioni reali %lf e %lf\n”,r1,r2); } }

Aritmetica dei puntatori

● Sia v un array di int

Sia p un puntatore a int int *p;

p=&v[4];

● Allora p+1 è un puntatore che si riferisce a v[5],

mentre p-1 si riferisce a v[3]

0 1 2 3 4 5 6 7 8 9

Aritmetica dei puntatori

● In generale p+i (ove i è un intero) si riferisce a i

celle dopo (o prima se i<0) rispetto a p

● Per esempio *(p+1) vale 2 (perché coincide con

v[5]), mentre *(p-2) vale 4 (perché coincide con v[2])

● E' una condizione di errore (non sempre

segnalata) uscire fuori dall'array, ad esempio con p+6

Indirizzi di v

Supponendo che un int occupa 4 byte Indirizzo di v[0] AA2800 Indirizzo di v[1] AA2804 Indirizzo di v[2] AA2808 Indirizzo di v[3] AA280C Indirizzo di v[4] AA2810 Indirizzo di v[5] AA2814 Indirizzo di v[6] AA2818 Indirizzo di v[7] AA281C Indirizzo di v[8] AA2820 Indirizzo di v[9] AA2804

Addizione puntatore numero

● In realtà quando si calcola p+i non viene

effettuata la somma vera e propria

● Se p=&v[4], allora p contiene l'indirizzo AA2810 ● Quindi p+1 contiene l'indirizzo AA2814, e non

AA2810+1=AA2811 !

● L'addizione puntatore numero avviene

“scalando” il numero, ovvero moltiplicando per il numero di byte occupati dal tipo degli elementi dell'array, in questo caso 4

Altre operazioni

● I puntatori (dello stesso tipo) si possono

sottrarre (si consulti un manuale per saperne di più)

● Due puntatori si possono anche confrontare

Dualismo array-puntatore

● L'operazione *(p+i) si può anche scrivere come

p[i]

● Ovvero si può trattare un puntatore (che punta

all'interno di un array) come se fosse un array e applicargli un indice

● D'altra parte se v è un array, si può scrivere

p=v;

● Ovvero v viene visto come l'indirizzo del primo

elemento dell'array (quindi un puntatore)

Passaggio di un array

Il passaggio di un array ad una funzione

avviene per “indirizzo”, ovvero il parametro contiene l'indirizzo del primo elemento

dell'array passato

● Il parametro si può indicare usando le parentesi

quadre, come nei due esempi seguenti

● E' indispensabile passare anche la dimensione

dell'array come parametro in più (non c'e' la funzione “len” in C)

Esempi

int somma(int v[ ], int n) { int s=0, i;

for(i=0;i<n;i++) s=s+v[i];

return s; }

void leggi(int v[ ], int n) { int s=0, i;

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

Esempi

int main() {

int a[10],sm;

printf(“inserisci gli elementi “); leggi(a,10);

sm=somma(a,10);

printf(“somma degli elementi %d\n”,sm); }

Passaggio per indirizzo

● L'array è passato per indirizzo (o per

riferimento)

● Una funzione non ha una copia dell'array

passato, può direttamente accedere all'array

originale e, come nel caso di “leggi”, modificare i suoi valori

● Il parametro v di entrambe le funzioni è una

specie di puntatore

● Infatti possiamo anche dichiarare che v è un

Esempi

int somma(int *v, int n) { int s=0, i;

for(i=0;i<n;i++) s=s+v[i];

return s; }

void leggi(int *v, int n) { int s=0, i;

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

scanf(“%d”,&v[i]); }

Variabili dinamiche

● Le variabili possono essere allocate

dinamicamente

● Non hanno un nome

● Possono essere utilizzate solo tramite un puntatore ● L'allocazione e la deallocazione sono eseguite

tramite delle funzioni apposite (malloc e free)

● Non hanno limiti di visibilità: una variabile dinamica

definita in una funzione può essere utilizzata in un'altra

Gestione della memoria

● Le variabili dinamiche sono allocate in una

zona della RAM chiamata heap

● All'inizio il heap è tutto libero

● La funzione malloc(n) cerca nello heap uno

spazio libero grande n byte e restituisce come risultato l'indirizzo di tale spazio (che ora

risulterà occupato)

● Il risultato di malloc deve essere memorizzato

malloc

● Per sapere quanti byte allocare si può usare

l'operatore sizeof, che calcola il numero di byte occupati da un determinato tipo di dato o da

una variabile

● Ad esempio

int *p;

p=malloc(sizeof(int));

trova nello heap uno spazio libero grande

abbastanza per occupare un int e mette in p l'indirizzo di tale spazio

malloc

● Ora tale variabile può essere usata, tramite p

*p=10; b=*p+2;

● Assegna ad una variabile int b il valore 12

p

10

AEFF90

cella di indirizzo AEFF90

Variabile dinamica

● La variabile puntata da p non ha nome !

● Può essere creata in una funzione ed essere

utilizzata in altre funzioni: supera lo schema rigido delle variabili locali, senza essere una variabile globale

● Può essere deallocata con

free(p);

● Elimina dallo heap la variabile dinamica creata

Gestione della memoria

● Allocazione e deallocazione sono a completo

carico del programmatore

● Bisogna stare a deallocare le variabili

dinamiche quando non servono più

● Una volta deallocate, ogni tentativo di accesso

mediante puntatore causa errore (non sempre segnalato...)

● Molti errori in esecuzione derivano da una non

Array dinamici

● E' possibile creare un array dinamico

semplicemente richiedendo uno spazio sufficiente

● int *v,n;

printf(“quanti elementi ? “); scanf(“%d”,&n);

v=malloc(n*sizeof(int));

● v si può usare, grazie all'aritmetica dei

puntatori, come un normale array, ad esempio for(i=0;i<n;i++)

Array dinamici

● Gli array dinamici consentono la creazione e la

gestione di array la cui dimensione, pur

essendo fissa, è stabilita durante l'esecuzione del programma (“a run-time”)

● Si supera così un limite degli array tradizionali ● Un array può essere deallocato con free

Puntatori e strutture dati dinamiche

● L'ultimo utilizzo dei puntatori è per

l'implementazione di strutture dati dinamiche in C

● Riprendiamo le strutture dati usate per

implementare le liste bidirezionali in Python e adattiamole al C

Implementazione di una lista

bidirezionale in C

struct nodo_lista { int key;

struct nodo_lista *prev, *next; };

struct lista {

struct nodo_lista *first,*last; };

Spiegazione

● prev, next, first e last sono indirizzi di nodi della

lista, perciò sono di tipo puntatore a nodo_lista

● key è la chiave, può essere di un tipo qualsiasi,

nell'esempio è int

● Si possono creare in modo agevole solo liste

omogenee (tutti gli elementi hanno chiavi dello stesso tipo)

● In Python non c'era questo vincolo, anche se

Notazione

● Il ruolo di None è assunto da NULL in C

(costante definita in stdio.h)

● Per accedere ai campi di nodo_lista partendo

da un puntatore a nodo_lista si può usare una notazione più comoda

● struct nodo_lista *p;

…

printf(“%d”, p->key)

Implementazione di una lista

bidirezionale in C

void crea_lista_vuota(struct lista *L ) { L->first=NULL;

L->last=NULL; }

void ins_inizio(struct lista *L,int x) { struct nodo_lista *n; n=malloc(sizeof(struct nodo_lista)); n->key=x; n->prev=NULL; n->next=L->first; if(L->last!=NULL) L->first->prev=n; else L->last=n; L->first=n;

Implementazione di una lista

bidirezionale in C

void scrivi_lista(struct lista *L) { struct nodo_lista *n; n=L->first; while(n!=NULL) { printf("%d ",n->key); n=n->next; } }

Implementazione di una lista

bidirezionale in C

Ricordando la sintassi del ciclo for generico si può scrivere in modo più compatto

void scrivi_lista(struct lista *L) { struct nodo_lista *n;

for(n=L->first; n!=NULL; n=n->next;) { printf("%d ",n->key);

} }

Esempio di utilizzo

int main() { struct lista L; crea_lista_vuota(&L); ins_inizio(&L,3); ins_inizio(&L,2); ins_inizio(&L,1); scrivi_lista(&L); }

Commenti

● ins_inizio e la prima versione di scrivi_lista

sono molto simili alle versioni in Python

● Definita su main la variabile L come struct lista,

si deve passare alle varie funzioni l'indirizzo di L

● La lista L andrebbe cancellata con delle

operazioni free opportunamente scritte

● In Python non ce n'era bisogno: questo

linguaggio cancella automaticamente tutti gli oggetti non più utilizzabili

Altre strutture dati dinamiche

● Pile, code ed alberi binari si possono

implementare in C in modo analogo

● In generale gli algoritmi di gestione delle

strutture dati dinamiche possono essere adattati al C con uno sforzo non difficile