Argomento di Programmazione 1. Fatto a lezione a ottobre, deck 6.2, parte centrale ed esercizi finali: slide 91-108 (comunicazione fra chiamante e chiamato, passaggio per valore e per riferimento, swap), slide 109-119 (struct come parametri, procedure, mescolare un mazzo), slide 120-131 (array come parametri, const nei puntatori, pro e contro), slide 136-137 (effetti collaterali con un puntatore), slide 150-154 (riga più lunga, cifrario di Cesare). Definizione, chiamata, pila e visibilità sono in Funzioni. Prima: Funzioni, Puntatori. Dopo: Ricorsione.
Il filo del deck:
comunicazione chiamante <-> chiamato: ingresso, uscita, ingresso/uscita
|
per valore search(vector, val): il record di search ha una copia di vector
|
il problema valoreFiltro(v) modifica la copia, v resta com'era
|
per riferimento parametro puntatore, &x nella chiamata, *p nel corpo
|
swap la versione sbagliata (per valore) e quella giusta (puntatori)
|
struct, procedure struct per valore o per indirizzo; più risultati con i puntatori
|
shuffle random + swap: mescolare un mazzo
|
array si passa l'indirizzo di base: gli elementi non si copiano
|
const privilegio minimo: quattro modi di passare un puntatore
|
riepilogo in C sempre per valore; pro e contro
1Definizioni
Comunicazione fra chiamante e chiamato (slide 91-93). Il chiamante e il sottoprogramma asservito si scambiano dati. Tre tipi di comunicazione:
- in ingresso: il chiamante fornisce valori alla funzione (gli operandi di
power); - in uscita: la funzione fornisce valori al chiamante (il risultato di
return, o una variabile del chiamante riempita dalla funzione); - in ingresso/uscita: la funzione riceve un valore e lo modifica (i due interi di
swap).
La modalità di passaggio è la tecnica con cui un linguaggio realizza questa comunicazione. Il deck guarda il C.
Passaggio per valore (o per copia, slide 97). In C i parametri passano per valore da un ambiente all’altro: all’invocazione, il valore di ogni parametro effettivo viene copiato nel parametro formale, che è una variabile del record del chiamato. Da lì in poi le due variabili sono indipendenti: se la funzione modifica il formale, l’effettivo non cambia.
int x = 5; main f
f(x); x [ 5 ] --> a [ 5 ] copia
void f(int a) { a = 99; } x [ 5 ] a [ 99 ] cambia solo la copia
Passaggio per riferimento (slide 100-103). Quando la funzione deve modificare un oggetto del chiamante non basta una copia: serve un riferimento all’oggetto. In C si realizza con un parametro formale di tipo puntatore:
- nella chiamata si passa l’indirizzo della variabile:
fun(&x). L’argomento di&deve essere una variabile, non un’espressione generica (&(x + 1)non compila); - nel corpo si usa l’operatore di dereferenziazione
*per accedere al contenuto della variabile, cioè al parametro effettivo vero e proprio:*y = 5;scrive nella cella puntata day.
È quello che fa scanf("%d", &x) fin dalla prima lezione: scanf è una funzione, e per scrivere in x deve sapere dove sta. La figura della slide: int x all’indirizzo 3500 contiene 30; int *y = &x; all’indirizzo 4152 contiene 3500. Tramite y si accede al right value di x.
In C il passaggio è sempre per valore (slide 130). Anche il “passaggio per riferimento” copia un valore: l’indirizzo. Il puntatore formale è una copia del puntatore effettivo, e se la funzione lo sposta (p++) il chiamante non se ne accorge; quello che la funzione può cambiare è la cella puntata. Il riferimento si costruisce con tre pezzi:
- il costruttore di puntatore
*nella definizione della funzione (void f(int *p)); - l’operatore di indirizzo
&nell’invocazione (f(&x)); - l’operatore di dereferenziazione
*nel corpo (*p = ...).
Struct come parametri (slide 109). Si possono passare sia per valore sia per riferimento, e una struct può essere il risultato di una funzione (Razionale prodotto(...) in Funzioni). Se la struct è passata per valore l’intero contenuto viene copiato, compresi gli eventuali campi array, copiati interamente.
Procedure e risultati (slide 114-115). Il passaggio per indirizzo permette di restituire uno o più risultati al chiamante. Ogni funzione si trasforma in procedura rappresentando il risultato come un parametro in più, passato per riferimento:
int f(int p1) { void f(int p1, int *p2) {
... ...
return risultato; *p2 = risultato;
} }
... ...
y = f(x); f(x, &y);
Array come parametri (slide 120-121). Gli array vengono trattati in modo particolare quando sono parametri effettivi: viene passato per valore l’indirizzo di base dell’array, cioè l’indirizzo del primo elemento. Il parametro formale è trattato come un puntatore al primo elemento. Gli elementi non vengono copiati: la funzione lavora sull’array del chiamante, e l’accesso si scrive come al solito (a[3]++). È la stessa regola di Puntatori: il nome di un array, in un’espressione, vale l’indirizzo di a[0].
int TemperatureOrarie[OreInGiorno];
ModificaArray(TemperatureOrarie, OreInGiorno); si passano nome e dimensione
void ModificaArray(int b[], int size); intestazione
La dimensione fra le quadre del parametro non serve: se c’è ed è maggiore di zero viene ignorata. Per questo la dimensione si passa come parametro a parte (size): la funzione non ha altro modo di saperla. int b[] e int *b come parametri sono la stessa cosa.
const e privilegio minimo (slide 123-125). Le prime versioni del C non avevano const; usarlo nei parametri migliora il codice. Ci sono quattro modi di passare un puntatore a una funzione:
- puntatore non costante a dati non costanti;
- puntatore non costante a dati costanti;
- puntatore costante a dati non costanti;
- puntatore costante a dati costanti.
La scelta segue il principio del privilegio minimo: dare alla funzione, tramite i parametri, l’accesso ai dati sufficiente per il suo compito e nient’altro.
| tipo | dichiarazione | *ptr = 100 | ptr = &a |
|---|---|---|---|
| puntatore a variabile | int * ptr | sì | sì |
| puntatore a costante | const int * ptr oppure int const * ptr | no | sì |
| puntatore costante a variabile | int * const ptr | sì | no |
| puntatore costante a costante | const int * const ptr | no | no |
Si legge da destra a sinistra partendo dal nome: const int * ptr è “ptr è un puntatore a int costante” (i dati non si toccano), int * const ptr è “ptr è un puntatore costante a int” (il puntatore non si sposta). Il caso che conta nei parametri è il 2: const int v[] o const char *s dice “questa funzione legge l’array e non lo modifica”, e il compilatore lo fa rispettare.
Pro e contro (slide 131).
| per valore | per indirizzo | |
|---|---|---|
| cosa si copia | il valore intero (inefficiente se il parametro è ingombrante, per esempio una struct con un array) | solo l’indirizzo della variabile (semplice o strutturata) |
| memoria | effettivo e formale occupano zone distinte | il formale punta alla zona dell’effettivo |
| uso | fornisce valori di ingresso | permette di modificare il parametro effettivo |
| rischio | nessuno sul chiamante | possibili effetti collaterali |
2Concetti
2.1Per valore e per indirizzo: swap
L’esempio che decide tutto il capitolo (slide 105-108): scrivere una funzione swap che scambia il valore (right value) di due variabili int, stampando le variabili prima e dopo la chiamata.
Prima versione, per valore (slide 106). Cosa viene stampato alle righe 15 e 18 (i due printf con k e m)?
#include <stdio.h>
void swap(int x, int y);
int main(void)
{
int k = 5;
int m = 8;
printf("k=%d, m=%d\n", k, m);
printf("DOPO lo scambio\n");
swap(k, m);
printf("k=%d, m=%d\n", k, m);
return 0;
}
void swap(int x, int y)
{
int temp;
temp = x;
x = y;
y = temp;
}
| istruzione | k (main) | m (main) | x (swap) | y (swap) | temp (swap) |
|---|---|---|---|---|---|
int k = 5; int m = 8; | 5 | 8 | |||
swap(k, m); entra | 5 | 8 | 5 | 8 | ? |
temp = x; | 5 | 8 | 5 | 8 | 5 |
x = y; | 5 | 8 | 8 | 8 | 5 |
y = temp; | 5 | 8 | 8 | 5 | 5 |
}: record eliminato | 5 | 8 |
Output (verificato):
k=5, m=8
DOPO lo scambio
k=5, m=8
Lo scambio avviene, ma fra x e y, le copie, e sparisce con il record di swap. La slide 107 lo timbra “ERRATO”.
Seconda versione, per indirizzo (slide 108, “Corretto”):
#include <stdio.h>
void swap(int *i, int *j);
int main(void)
{
int k = 5;
int m = 8;
printf("k=%d, m=%d\n", k, m);
printf("DOPO lo scambio\n");
swap(&k, &m);
printf("k=%d, m=%d\n", k, m);
return 0;
}
void swap(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}
Con k all’indirizzo 1000 e m all’indirizzo 1004 (indirizzi di esempio):
| istruzione | k (1000) | m (1004) | i | j | temp | nota |
|---|---|---|---|---|---|---|
swap(&k, &m); entra | 5 | 8 | 1000 | 1004 | ? | si copiano gli indirizzi |
temp = *i; | 5 | 8 | 1000 | 1004 | 5 | *i è k |
*i = *j; | 8 | 8 | 1000 | 1004 | 5 | scrive in k il valore di m |
*j = temp; | 8 | 5 | 1000 | 1004 | 5 | scrive in m |
}: record eliminato | 8 | 5 |
Output (verificato):
k=5, m=8
DOPO lo scambio
k=8, m=5
Anche qui il record di swap sparisce, ma le scritture *i = ... e *j = ... sono andate nelle celle di main. Le tre modifiche rispetto alla versione sbagliata: int * nella testata (e nel prototipo), & nella chiamata, * davanti a ogni uso di i e j nel corpo.
Controesempio, scambiare i puntatori invece dei valori:
void scambia_puntatori(int *a, int *b)
{
int *t;
t = a; a = b; b = t;
}
Non scambia niente nel chiamante: a e b sono copie degli indirizzi, e scambiare le copie è come la swap per valore, un livello più su. Serve l’asterisco: si scambiano *a e *b, le celle puntate (vedi Passaggio dei parametri (esercizi), esercizio 3).
2.2Struct per valore e per riferimento
(slide 98-100, slide 110) Il prof parte da una struct Vettore con un array dentro e da una funzione valoreFiltro che deve modificare la cella di indice 1 dell’array contents. La versione per valore riceve Vettore A, cioè una copia di tutta la struct; quella per riferimento riceve Vettore *A e accede ai campi con ->. Le metto nello stesso programma; alla versione per valore aggiungo un printf dentro la funzione per vedere che la modifica avviene, ma nella copia:
#include <stdio.h>
#define DMAX 20
typedef int array[DMAX];
typedef struct {
int actualSize;
array contents;
} Vettore;
void valoreFiltro(Vettore A)
{
A.contents[1] = 10;
printf("%d DENTRO valoreFiltro\n", A.contents[1]);
}
void valoreFiltroRif(Vettore *A)
{
A->contents[1] = 10;
}
int main(void)
{
Vettore v;
v.contents[1] = 7;
printf("%d PRIMA CHIAMATA FUNZIONE\n", v.contents[1]);
valoreFiltro(v);
printf("%d DOPO CHIAMATA FUNZIONE\n", v.contents[1]);
valoreFiltroRif(&v);
printf("%d DOPO valoreFiltroRif(&v)\n", v.contents[1]);
return 0;
}
| istruzione | v.contents[1] (main) | A.contents[1] (copia) | nota |
|---|---|---|---|
v.contents[1] = 7; | 7 | ||
valoreFiltro(v); entra | 7 | 7 | si copiano tutti i 20 int di contents e actualSize |
A.contents[1] = 10; | 7 | 10 | modifica la copia |
| ritorno | 7 | copia eliminata | |
valoreFiltroRif(&v); | 10 | A vale &v, A->contents[1] è v.contents[1] |
Output (verificato):
7 PRIMA CHIAMATA FUNZIONE
10 DENTRO valoreFiltro
7 DOPO CHIAMATA FUNZIONE
10 DOPO valoreFiltroRif(&v)
La domanda della slide 99 (“dove sbaglio qui?”, accanto a valoreFiltro(v);) ha questa risposta: la struct passa per valore, e anche il campo array viene copiato per intero. Nota la differenza con gli array passati da soli (sotto): un array dentro una struct si copia, un array passato direttamente no. Senza il printf dentro, gcc con -Wextra avvisa parameter 'A' set but not used (verificato): è il compilatore che dice che quella modifica non serve a niente.
Quando si passa una struct per indirizzo anche se non va modificata: quando è grande. Copiare Vettore vuol dire copiare 21 int; un puntatore è 8 byte. In quel caso si scrive const Vettore *A: niente copia e niente modifiche.
2.3Array passati a funzione
L’esempio della slide 122: modifyArray moltiplica per 3 tutti gli elementi dell’array ricevuto.
#include <stdio.h>
#define SIZE 5
void modifyArray(int b[], int size);
int main(void)
{
int a[SIZE] = {0, 1, 2, 3, 4};
int i;
printf("Array originale:\n");
for (i = 0; i < SIZE; i++) {
printf(" a[%d]= %d", i, a[i]);
}
printf("\n");
modifyArray(a, SIZE);
printf("Array dopo invocazione funzione e':\n");
for (i = 0; i < SIZE; i++) {
printf(" a[%d]= %d", i, a[i]);
}
printf("\n");
return 0;
}
void modifyArray(int b[], int size)
{
for (int j = 0; j < size; j++) {
b[j] *= 3;
}
}
j | b[j] prima | b[j] *= 3 | cella di main toccata |
|---|---|---|---|
| 0 | 0 | 0 | a[0] |
| 1 | 1 | 3 | a[1] |
| 2 | 2 | 6 | a[2] |
| 3 | 3 | 9 | a[3] |
| 4 | 4 | 12 | a[4] |
Output (verificato):
Array originale:
a[0]= 0 a[1]= 1 a[2]= 2 a[3]= 3 a[4]= 4
Array dopo invocazione funzione e':
a[0]= 0 a[1]= 3 a[2]= 6 a[3]= 9 a[4]= 12
Nella chiamata si scrive a, senza & e senza quadre: a vale già l’indirizzo di a[0]. Il commento della slide dice “passaggio di a per riferimento”: l’effetto è quello, il meccanismo è la copia dell’indirizzo.
Esempio 2, perché serve size. Dentro la funzione b è un puntatore, quindi sizeof(b) dà la dimensione di un puntatore e non dell’array:
void f(int b[]) { printf("in f: %zu\n", sizeof(b)); }
int a[5]; printf("in main: %zu\n", sizeof(a)); f(a);
Stampa in main: 20 e in f: 8 (verificato su Linux a 64 bit); gcc avvisa 'sizeof' on array function parameter 'b' will return size of 'int *'. La funzione non può sapere quanti elementi ha l’array: glielo dice il chiamante. Per le stringhe c’è un’eccezione pratica, il '\0' finale che segna la fine (vedi convertToUppercase sotto).
Esempio 3, passare un pezzo di array. Dato che si passa un indirizzo, si può passare quello di un elemento qualsiasi: modifyArray(a + 2, 3) (o modifyArray(&a[2], 3)) moltiplica per 3 solo a[2], a[3], a[4]. Per la funzione, b[0] è a[2].
La dimensione fra le quadre del parametro (slide 120): void f(int b[3]) e void f(int b[100]) compilano tutte e due e si comportano come int b[] (verificato; con [100] e un array di 5 elementi gcc avvisa che la funzione potrebbe accedere a 400 byte in una zona di 20). Con dimensione negativa è errore (size of array 'b' is negative). Con 0 la slide dice errore; gcc dà un warning con -Wpedantic (ISO C forbids zero-size array).
2.4Più risultati con i parametri puntatore
return restituisce un solo valore. Se una funzione deve produrne due, il chiamante le passa gli indirizzi di due variabili da riempire. Esempio 1, la trasformazione funzione → procedura della slide 115, e quoziente e resto insieme:
#include <stdio.h>
int quadrato(int x)
{
return x * x;
}
void quadratoP(int x, int *ris)
{
*ris = x * x;
}
void divisione(int a, int b, int *q, int *r)
{
*q = a / b;
*r = a % b;
}
int main(void)
{
int y;
int quoz;
int resto;
y = quadrato(7);
printf("y=%d\n", y);
quadratoP(6, &y);
printf("y=%d\n", y);
divisione(17, 5, &quoz, &resto);
printf("17 = %d * 5 + %d\n", quoz, resto);
return 0;
}
| chiamata | parametri | effetto nel chiamante |
|---|---|---|
y = quadrato(7); | x = 7 | return 49, poi y = 49 |
quadratoP(6, &y); | x = 6, ris = &y | *ris = 36 scrive in y |
divisione(17, 5, &quoz, &resto); | a = 17, b = 5, q = &quoz, r = &resto | quoz = 17 / 5 = 3, resto = 17 % 5 = 2 |
Output (verificato): y=49, y=36, 17 = 3 * 5 + 2. a e b sono solo in ingresso e passano per valore; q e r sono in uscita e passano per indirizzo. È lo schema di newX(TX *x) all’esame: la funzione riceve l’indirizzo di una struct vuota e la riempie.
Esempio 2: scanf restituisce con return il numero di valori letti, e con i parametri puntatore i valori stessi. Due risultati, due canali.
2.5const nei parametri
Gli esempi delle slide 127 e 129, caso 1 e caso 2, nello stesso programma:
#include <stdio.h>
#include <ctype.h>
void convertToUppercase(char *sPtr);
void printCharacters(const char *sPtr);
int main(void)
{
char string[] = "cHaRaCters and $32.98";
printf("The string before conversion is: %s", string);
convertToUppercase(string);
printf("\nThe string after conversion is: %s\n", string);
puts("The string is:");
printCharacters(string);
puts("");
return 0;
}
void convertToUppercase(char *sPtr)
{
while (*sPtr != '\0') {
*sPtr = toupper(*sPtr);
++sPtr;
}
}
void printCharacters(const char *sPtr)
{
for (; *sPtr != '\0'; ++sPtr) {
printf("%c", *sPtr);
}
}
Output (verificato):
The string before conversion is: cHaRaCters and $32.98
The string after conversion is: CHARACTERS AND $32.98
The string is:
CHARACTERS AND $32.98
convertToUppercase(char *sPtr), caso 1: puntatore non costante a dati non costanti, il livello di accesso più alto. La funzione modifica i caratteri (*sPtr = toupper(*sPtr), dactype.h) e sposta il puntatore (++sPtr) per scorrere la stringa fino al'\0'.toupperlascia com’è tutto quello che non è una lettera minuscola: spazio,$, cifre, punto.printCharacters(const char *sPtr), caso 2: puntatore non costante a dati costanti. Il puntatore si sposta (++sPtr), i caratteri si leggono soltanto: è un puntatore “di sola lettura”. Se nel corpo scrivessi*sPtr = 'x';gcc si fermerebbe conassignment of read-only location '*sPtr'(verificato).
++sPtr sposta la copia del puntatore: in main, string continua a indicare il primo carattere, ed è per questo che dopo la conversione il printf stampa la stringa intera.
Casi 3 e 4 (le slide non hanno l’esempio): con char * const s il corpo può scrivere *s ma non può fare s++ (increment of read-only parameter 's'); con const char * const s nessuna delle due (verificato). Nei parametri il caso 3 serve poco: il puntatore è già una copia, spostarlo non disturba il chiamante.
Una conseguenza utile: se un array è const (o la funzione chiamante lo ha ricevuto come const), passarlo a una funzione con parametro non const produce il warning discards 'const' qualifier (verificato). Chi scrive funzioni che leggono soltanto le dichiara const, così si possono chiamare su qualunque array.
3Metodo
Tracciare una chiamata con puntatori.
- Dai un indirizzo di esempio a ogni variabile del chiamante che compare con
&(1000, 1004, …). - Alla chiamata copia nei formali: i valori per i parametri normali, gli indirizzi per i parametri puntatore, l’indirizzo di
a[0]per gli array. - Nel corpo: un’assegnazione a
p(senza asterisco) cambia la copia del puntatore, e nel chiamante non succede niente; un’assegnazione a*p,p->campoop[i]cambia la variabile del chiamante. Scrivi la modifica nella colonna del chiamante. - Al ritorno cancella il record e rileggi le variabili del chiamante.
Scegliere come passare un parametro.
la funzione deve modificare la variabile del chiamante?
no -> è un int, float, char, enum? per valore int x
è una struct piccola? per valore Tdato d
è una struct grande? per indirizzo const Tdato *d
è un array? sempre indirizzo, con const: const int v[], int n
sì -> variabile semplice o struct per indirizzo int *x, Tdato *d (chiamata con &)
array int v[], int n (chiamata col nome)
Scrivere una funzione su un array. Parametri tipo v[] (o const tipo v[] se si legge soltanto) e int n; ciclo for (i = 0; i < n; i++); mai sizeof(v) dentro la funzione. Per un array di struct l’elemento è v[i] e il campo v[i].campo.
4Esempi svolti a lezione
Ricerca in un vettore (slide 94-97). Una struct Vettore (dimensione effettiva e array contents) e una funzione che cerca un valore:
#include <stdio.h>
#define DMAX 20
typedef int array[DMAX];
typedef struct {
int actualSize;
array contents;
} Vettore;
int search(Vettore v, int k)
{
int n;
int result = -1;
for (n = 0; n < v.actualSize; n++) {
if (v.contents[n] == k) {
result = n;
}
}
return result;
}
int main(void)
{
Vettore vector = {5, {4, 7, 1, 7, 2}};
printf("%d %d %d\n", search(vector, 7), search(vector, 4), search(vector, 9));
return 0;
}
Qual è l’effetto di pos = search(vector, val);? Si crea la macchina asservita con l’ambiente di search (slide 95), e i valori passano per copia (slide 97): vector (con actualSize e tutto l’array contents) viene copiato in v, val in k; result e n sono locali di search. Il risultato torna in pos.
Tracing di search(vector, 7) con i miei valori {4, 7, 1, 7, 2}:
n | v.contents[n] | uguale a 7 | result |
|---|---|---|---|
| -1 | |||
| 0 | 4 | no | -1 |
| 1 | 7 | sì | 1 |
| 2 | 1 | no | 1 |
| 3 | 7 | sì | 3 |
| 4 | 2 | no | 3 |
Output (verificato): 3 0 -1. La funzione non si ferma alla prima occorrenza: restituisce l’indice dell’ultima, e -1 se il valore non c’è. Per fermarsi alla prima basterebbe return n; dentro l’if e return -1; dopo il ciclo. Nella slide 104 il prof ridisegna lo stesso schema “per riferimento”, con v che punta a vector invece di esserne una copia: è la versione int search(const Vettore *v, int k), che evita di copiare 21 int a ogni ricerca.
valoreFiltro, per valore e per riferimento (slide 99-100, slide 110). Svolto sopra in Struct per valore e per riferimento. La slide 100 chiede: cosa succede con valoreFiltro(v);? Come si modifica v.contents[1] nel chiamante? Il problema è che nell’ambiente del chiamato ne viene fatta una copia; serve un riferimento all’oggetto da modificare, cioè valoreFiltro(&v) con void valoreFiltro(Vettore *A) e A->contents[1]=10;. Il programma della slide 110 stampa 7 PRIMA CHIAMATA FUNZIONE e 10 DOPO CHIAMATA FUNZIONE.
swap (slide 105-108). Svolto sopra in Per valore e per indirizzo.
power con una variabile locale in meno (slide 111-113). Il passaggio per valore non limita (se serve si usano i puntatori) e anzi può ridurre le variabili locali: il parametro n è già una copia, quindi lo si può consumare come contatore. Svolto in Funzioni, sezione I parametri sono variabili locali.
Mischiare un mazzo di carte (slide 116-119). Descrivere un algoritmo per mischiare un mazzo di carte: un array cards di carte distinte con valori fra 1 e .
Il primo tentativo è for(i=0;i<N;i++) cards[i]=random(1,N). Non è corretto: c’è una probabilità non nulla che random restituisca lo stesso numero due volte, e allora due carte sono uguali e un’altra manca. Con la probabilità che i 7 numeri siano tutti diversi è : quasi sempre il mazzo esce sbagliato.
L’idea corretta (slide 118): si parte dal mazzo ordinato 1 2 3 ... N e si scambiano le carte. Si scorre l’array dall’ultima posizione alla seconda; per ogni posizione i si sceglie a caso una posizione j fra 0 e i e si scambiano array[i] e array[j]. Così si usano solo scambi, e uno scambio non può né duplicare né perdere una carta. È l’algoritmo di Fisher-Yates.
void shuffle(int *array, int n) {
int j, temp;
for (int i = n - 1; i > 0; i--) {
j=random(0,i);
swap(&array[i], &array[j]);
}
}
shuffle riceve l’array come int *array (equivale a int array[]) e lo modifica sul posto. swap(&array[i], &array[j]) passa gli indirizzi di due elementi: è la swap per indirizzo applicata a celle di un array. La variabile temp della slide non serve, lo scambio lo fa swap.
Tracing con e con una sequenza di valori casuali fissata per poterla seguire (j = 1, 3, 0, 1):
i | j = random(0, i) | scambio | array dopo |
|---|---|---|---|
| 1 2 3 4 5 | |||
| 4 | 1 | array[4] con array[1] | 1 5 3 4 2 |
| 3 | 3 | array[3] con sé stesso | 1 5 3 4 2 |
| 2 | 0 | array[2] con array[0] | 3 5 1 4 2 |
| 1 | 1 | array[1] con sé stesso | 3 5 1 4 2 |
Risultato 3 5 1 4 2 (verificato sostituendo random con la sequenza fissa): ancora tutte e cinque le carte, una volta ciascuna. j può valere i (la carta resta dov’è), ed è giusto così: altrimenti l’ultima carta non potrebbe mai restare in fondo. Il ciclo si ferma a i > 0 perché con i = 0 l’unica scelta sarebbe j = 0.
Il programma completo della slide 119, compilabile (con casuale al posto di random, motivo in Funzioni, e un array di 100 elementi al posto dell’array a lunghezza variabile int cards[N] della slide):
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int casuale(int min, int max);
void swap(int *i, int *j);
void shuffle(int *array, int n);
int main(void)
{
int N;
time_t t;
printf("Enter total number of cards (N): ");
if (scanf("%d", &N) != 1 || N < 1 || N > 100) {
return 1;
}
int cards[100];
for (int i = 0; i < N; i++) {
cards[i] = i + 1;
}
srand((unsigned) time(&t));
shuffle(cards, N);
printf("\nRandom distribution of cards:\n");
for (int i = 0; i < N; i++) {
printf("%d ", cards[i]);
}
printf("\n");
return 0;
}
int casuale(int min, int max)
{
return rand() % (max - min + 1) + min;
}
void swap(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}
void shuffle(int *array, int n)
{
int j;
for (int i = n - 1; i > 0; i--) {
j = casuale(0, i);
swap(&array[i], &array[j]);
}
}
Con input 7 ha stampato 5 4 2 3 1 7 6 (cambia a ogni esecuzione); ordinando l’output si riottiene 1 2 3 4 5 6 7 (verificato).
Effetti collaterali con un puntatore (slide 136-137). Una variabile globale y, una locale z di main, due funzioni che ricevono l’indirizzo di z. Viene modificato z? Viene modificato y?
#include <stdio.h>
int y = 0;
int SecondoEsempio(int *par)
{
(*par)++;
return (*par);
}
int TerzoEsempio(int *par)
{
*par = *par + 1;
return (*par);
}
int main(void)
{
int z = 0;
printf("y=%d\n", y);
printf("z=%d\n\n", z);
y = SecondoEsempio(&z);
printf("y=%d\n", y);
printf("z=%d\n\n", z);
y = TerzoEsempio(&z);
printf("y=%d\n", y);
printf("z=%d\n", z);
return 0;
}
| istruzione | y (globale) | z (main) | par |
|---|---|---|---|
| inizio | 0 | 0 | |
SecondoEsempio(&z): (*par)++ | 0 | 1 | &z |
return (*par) = 1, y = 1 | 1 | 1 | |
TerzoEsempio(&z): *par = *par + 1 | 1 | 2 | &z |
return (*par) = 2, y = 2 | 2 | 2 |
Output (verificato):
y=0
z=0
y=1
z=1
y=2
z=2
Vengono modificati tutti e due: z dentro la funzione, tramite il puntatore; y nel chiamante, con il valore restituito. Il commento del prof su (*par)++: “le parentesi sono importanti”. Senza, *par++ si legge *(par++) (il ++ postfisso lega più di *, vedi Puntatori): sposta il puntatore sulla cella dopo z e non incrementa niente; gcc avvisa value computed is not used, e il return *par leggerebbe una cella che non appartiene a nessuna variabile. (*par)++ e *par = *par + 1 sono equivalenti.
Riga più lunga (slide 150-152). Data una sequenza di righe delimitate da newline, selezionare la più lunga, usando due funzioni: getline legge una riga in un array e ne restituisce la lunghezza, copy copia una stringa in un’altra. È l’esempio del libro di Kernighan e Ritchie. Riscritto con leggi_riga al posto di getline (che su Linux va in conflitto con quella di stdio.h):
#include <stdio.h>
#define MAXLINE 1000
int leggi_riga(char line[], int maxline);
void copy(char to[], char from[]);
int main(void)
{
int len;
int max;
char line[MAXLINE];
char longest[MAXLINE];
max = 0;
while ((len = leggi_riga(line, MAXLINE)) > 0) {
if (len > max) {
max = len;
copy(longest, line);
}
}
if (max > 0) {
printf("\nThe longest line is: %s", longest);
}
return 0;
}
int leggi_riga(char s[], int lim)
{
int c;
int i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++) {
s[i] = c;
}
if (c == '\n') {
s[i] = c;
i++;
}
s[i] = '\0';
return i;
}
void copy(char to[], char from[])
{
int i;
i = 0;
while ((to[i] = from[i]) != '\0') {
i++;
}
}
Come lavorano i parametri:
leggi_riga(line, MAXLINE):linepassa come indirizzo, quindi i caratteri scritti ins[i]finiscono inlinedimain;limpassa per valore. Il risultato (la lunghezza) torna conreturn: due canali di uscita, comescanf.- Il
forsi ferma per tre motivi: spazio finito (i < lim - 1, si lascia posto al'\0'), fine dell’input (EOF), fine della riga ('\n'). Il cortocircuito di&&(Espressioni, operatori e costanti) garantisce chegetchar()non venga chiamata quando lo spazio è finito. - Il
'\n'se c’è viene tenuto nella stringa e contato. Una riga vuota vale quindi 1, e 0 vuol dire solo “input finito”: per questo ilwhiledimainsi ferma alen > 0. copy(longest, line): tutti e due gli array passano per indirizzo;copyscrive inlongestdimain. Il ciclowhile ((to[i] = from[i]) != '\0')copia un carattere e controlla se era il terminatore: il'\0'viene copiato anche lui, poi il ciclo esce.
Con input ciao, programmazione uno, C (tre righe):
| chiamata | len | len > max | max | longest |
|---|---|---|---|---|
| 1 | 5 (ciao + \n) | sì | 5 | ciao\n |
| 2 | 19 | sì | 19 | programmazione uno\n |
| 3 | 2 | no | 19 | invariato |
| 4 | 0 (EOF) | esce |
Output (verificato): una riga vuota e poi The longest line is: programmazione uno.
Cosa succede con una riga più lunga del limite: con MAXLINE 10, leggi_riga legge al massimo 9 caratteri, e il resto della riga resta nell’input per la chiamata successiva. La riga programmazione uno viene vista come tre righe: programma (9), zione uno (9), e il solo \n (1) (verificato). È il problema dell’esercizio della slide 153, svolto in Passaggio dei parametri (esercizi), esercizio 11.
Esercizi lasciati per casa (slide 153-154): la riga più lunga con righe oltre il limite, e il cifrario di Cesare con void shift(char *c, int chiave). Svolti in Passaggio dei parametri (esercizi), esercizi 11 e 12.
5Esercizi tipo esame
In una pagina a parte, dal più facile al livello del 30: Passaggio dei parametri (esercizi).
6Errori tipici
swap(int x, int y): scambia le copie, il chiamante non vede niente.- Parametro puntatore ma chiamata senza
&:f(x)convoid f(int *p)non compila con gcc 16 (makes pointer from integer without a cast); con compilatori vecchi è un warning e il programma scrive a un indirizzo a caso. - Nel corpo
p = ...invece di*p = ...: si cambia la copia del puntatore. *p++al posto di(*p)++: sposta il puntatore invece di incrementare la variabile.&(x + 1)o&5:&si applica solo a variabili.- Credere che un array passato a funzione venga copiato: la funzione modifica l’array del chiamante.
- Credere che una struct passata per valore venga modificata: si copia tutto, anche l’array che contiene.
sizeof(v)dentro la funzione per sapere quanti elementi ha l’array: dà la dimensione del puntatore. La lunghezza va passata.- Dimenticare
constsui parametri che si leggono soltanto, o metterlo su un parametro che va scritto (assignment of read-only location). - Mischiare un mazzo assegnando a ogni carta un numero casuale: escono duplicati. Si scambia.
p->camposu una struct passata per valore, op.camposu un puntatore a struct:.con la struct,->con il puntatore.
7Domande
-
Quali sono i tre tipi di comunicazione fra chiamante e chiamato?
-
Cosa vuol dire che in C il passaggio dei parametri è per valore? Cosa succede se la funzione modifica un suo parametro?
-
Come si realizza in C il passaggio per riferimento? Quali sono i tre pezzi e dove va ognuno?
-
Perché
void swap(int x, int y)non scambiakem? Cosa stampa il programma della slide 106? -
Scrivi la
swapcorretta e la sua chiamata. -
Perché si dice che anche il passaggio per riferimento in C è per valore?
-
Cosa succede quando si passa una struct per valore? E un campo array dentro la struct?
-
Cosa viene passato quando un array è parametro effettivo? Gli elementi vengono copiati?
-
Perché a una funzione che riceve un array si passa anche la dimensione? Cosa succede alla dimensione scritta fra le quadre del parametro?
-
Come si trasforma una funzione
int f(int p1)in una procedura? Come si restituiscono due risultati? -
Quali sono i quattro modi di passare un puntatore a una funzione? Cosa permette ognuno?
-
Cos’è il principio del privilegio minimo, e come si applica con
const? -
Perché assegnare
cards[i] = random(1, N)non mischia correttamente un mazzo? Come si fa? -
Quali sono pro e contro del passaggio per valore e per indirizzo?
-
Nel programma delle slide 136-137, quali variabili vengono modificate da
y = SecondoEsempio(&z);? Perché in(*par)++le parentesi sono importanti? -
In
leggi_riga(line, MAXLINE), come arrivano amaini caratteri letti e la lunghezza?