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=30giorni=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) DefinizioneTipi 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 AB8910Puntatori 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 AB8910Operatore 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 yPassaggio per puntatore
● temp=*x; a b 7 11 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 tempPassaggio per puntatore
● *x=*y; a b 11 11 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 tempPassaggio per puntatore
● *y=temp; a b 11 7 indirizzi E2C344 E2C348 E2C344 E2C348 x y 7 tempUso 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