Linguaggio C Aggregati di dati

Limiti delle variabili semplici Come elaborare e salvare grandi quantità di dati?

Ad esempio, un sensore invia un dato ogni intervallo di tempo, la sequenza va poi conservata per un certo tempo per essere elaborata Occorre definire tante variabili diverse ad esempio numerate?

Come descrivere dati strutturati anagrafici?

Ad esempio dati anagrafici di un comune molte variabili scollegate, nome, cognome, data nascita, residenza, etc? Ripetute per ogni cittadino?

Strutture

La struttura è una collezione di variabili (di solito non dello stesso tipo) raggruppate sotto lo stesso nome.

struct tempo {!int ore;!int minuti;!int secondi;!

} orologio1, orologio2;!

struct tempo {!int ore;!int minuti;!int secondi;!

};!struct tempo orologio1, orologio2;!

Nuovi tipi di dati: typedef L'istruzione typedef definisce un sinonimo per un tipo.

typedef int intero; intero x = 3;!

Con le strutture, typedef serve a definire un sinonimo per strutture complesse

typedef struct tempo{...} orologio;!orologio swatch, sector;!

typedef è un sinonimo per la dichiarazione di istanze di strutture

/*dichiarazione con typedef*/!typedef struct {int x; int y;} coord;!/*istanza*/!coord punto1, punto2;!/*dichiarazione senza typedef*/!struct coord {int x; int y;};!/*istanza*/!struct coord punto1, punto2;!

Operatori per strutture

l'operatore punto (".") è lo strumento per accedere ai singoli campi delle variabili struct orologio1.ore = 18;!orologio1.minuti = 21;!orologio1.secondi = 22;!

Le strutture si possono nidificare (cioè si può inserire una struttura dentro un'altra struttura)

struct nascita {!struct tempo ora;!struct data data;!

};!

Esempio concorso # include <stdio.h> /* definizione di tipo globale*/!struct concorso {!

int serie;!char organizzatore;!int partecipanti;!

};!main()!{! struct concorso c0, c1;!

c0.serie = 2; c0.organizzatore = 'F';!c0.partecipanti = 482;!c1.serie = 0; c1.organizzatore = 'G';!c1.partecipanti = 33;!

printf("Serie della concorso 0: %d\n", c0.serie);!printf("Organizzatore della concorso 1: %c\n",!

c1.organizzatore);!}!

/*Programma distanza con variabili singole*/!….!double lato1, lato2, distanza, x1=1, y1=5, x2=4,!

y2=7;!lato1= x2-x1; lato2= y2-y1;!distanza=sqrt(lato1*lato1 + lato2*lato2);!/* visualizzazione */!printf (“la distanza fra i due punti è”!“%5.2lf\n”, distanza);!}!

•un punto nel piano cartesiano può essere visto come struct o come array

/* Programma distanza con struct per punto*/!….!double lato1, lato2, distanza;!struct punto {!

double x;!double y;!

} p1, p2;!

p1.x = 1; p1.y = 5;!p2.x = 4; p2.y = 7;!lato1= p2.x - p1.x; lato2= p2.y - p1.y;!distanza=sqrt(lato1*lato1 + lato2*lato2);!/* visualizzazione! */!printf (“la distanza fra i due punti = %5.2lf\n”,!

distanza);!

}!

Molti dati dello stesso tipo Occorre un costruttore che permette di usare lo stesso nome per tante variabili dello stesso tipo

Nella notazione matematica (serie, etc) si usano i pedici In C si usano indici

Questi dati saranno memorizzati in memoria di lavoro in posizioni contigue L’area per memorizzarli sarà statica

array Tutti gli elementi!hanno lo stesso!nome c)!La struttura dati che naturalmente

si adatta ai costrutti for è l’array, cioè la sequenza di valori c[0]! -45!

c[1]! 6!organizzati insieme ed c[2]! 0!

c[3]! 72!individuabili con un unico nome. c[4]! 1543!

c[5]! -89!Il nome dell’array è un c[6]! 0!

identificatore, ed è possibile c[7]! 62!

c[8]! -3!

accedere ad ognuno degli c[9]! 1!

c[10]! 6453!elementi usando un indice c[11]! 78!

(indirizzamento mediante registro indice) che parte da 0 Posizione!

dell’elemento!nella array c!

array 12 24 31 101 55 71

a[0] a[1] un array è un insieme di locazioni di memoria con lo stesso nome e distinte da un numero detto indice (in inglese subscript). Gli array si dichiarano come le variabili ma sono seguiti da [n], dove n è una costante ed indica la dimensione!dell'array

int a[6];!char testo[20];!

Le singole locazioni di memoria si indicano con i simboli a[0],a[1],a[2],..., a[5]!

Memoria per array contenuti

int pippo[3] indirizzi

9, cioè1001

pippo 00000000

& pippo[0] 00000010 00000010

pippo[0] = 0 pippo[1] =2 pippo[2] = 2

Dichiarazioni e assegnamenti array Es di dichiarazione: int s[6];!double t[4];!

Es. di inizializzazione contestuale: int s[6] = {5, 0, -1, 2, 15, 2};!

double t[4] = {0.0, 0.1, 0.2, 0.8};!int s[6] = {0}; assegna 0 a tutti gli elementi!

int s[ ] = {5, 0, -1, 2, 15, 2}; calcola!

la dimensione dai dati di inizializzazione

Inizializzare mediante cicli

Per inizializzare in modo regolare: int k; double gi[21];!

for (k=0; k<= 20; k++)!

gi[k] = k * 0.5;!se k supera 20 accede a posizioni di memoria fuori dell’array

Per inizializzare mediante lettura : int k; double gi[21];!

for (k=0; k<= 20; k++)!

scanf (“%lf”, &gi[k]);!

esempio #include <stdio.h>!/* programma che acquisisce 5 numeri in array e la stampa*/!main()!{ int lista[5];!

int contavolte = 0, letto = 0;!printf("Inserire 5 numeri tra 1 e 10\n");!

/* questo ciclo while controlla la gestione dei 5 valori */!while ( contavolte < 5 )!{ letto = 0;!

/* questo ciclo while aspetta un numero fra 1 e 10*/!while (letto < 1 || letto > 10)!{ printf("\n Inserisci il num. %d: ", contavolte + 1 );!

scanf("%d", &letto );!}!lista[contavolte] = letto;!contavolte++;!

}!for (contavolte = 0; contavolte < 5; contavolte++)!

printf("\nVal. %d=%d", contavolte + 1, lista[contavolte]!);!}!

/* Programma distanza - ogni punto è un array di due*/!….!double lato1, lato2, distanza;!double punto1[2], punto2[2];!punto1[0] = 1; punto1[1] = 5;!punto2[0] = 4; punto2[1] = 7;!lato1= punto2[0] - punto1[0] ;!lato2= punto2[1] - punto1[1] ;!distanza=sqrt(lato1*lato1 + lato2*lato2);!/* visualizzazione! */!printf (“la distanza fra i due punti = %5.2lf\n”, distanza);!}!

Estendere al caso 3D?!Ogni punto è array di 3 posizioni!Estendere a più punti?!Fare array rettangolare: ogni linea è un punto, ogni!

colonna i valori di un asse!

Esempio: stampa un istogramma

#include <stdio.h>!

#define SIZE 10!

main()!{!

int n[ SIZE ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 };!

int i, j;!

printf( "%s%13s%17s\n", "Elemento", "Valore", “Istogramma!

for ( i = 0; i <= SIZE - 1; i++ ) {!

printf( "%7d%13d! ", i, n[ i ]) ;!

for ( j = 1; j <= n[ i ]; j++ )! /* stampa una barra */!

printf( "%c", '*' );!

printf( "\n" );!

}!}

Output del programma

Elemento! Valore! Istogramma!0! 19! *******************!1! 3! ***!2! 15! ***************!3! 7! *******!4! 11! ***********!5! 9! *********!6! 13! *************!7! 5! *****!8! 17! *****************!9! 1! *!

massimo rivisto: Trovare il massimo di un array di 5 valori naturali, prendendo il primo come max provvisorio

int max, i, corrente, valori[5];!/* lettura*/!for (i = 0; i<5; i++)!

scanf ("%6d \n", &valori[i]);!/* calcolo */!max = valori[0];!for (i = 1; i<5; i++)!

{ if (valori[i] > max) max = valori[i]; }!

printf ("il massimo è' %d \n", max);!….!

Esempio calcolo vettoriale Scrivere un programma che chiede all’utente di inserire due vettori e ne stampa il prodotto scalare e vettoriale.

Vettore r, con componenti r1, r2, r3 Vettore s con componenti s1, s2, s3 Prodotto scalare r.s = r1*s1 + r2*s2 +r3*s3 Prodotto vettoriale c è un vettore c1, c2, c3

c1 = r2*s3 – r3*s2 c2 = r3*s1 – r1*s3 c3 = r1*s2 – r2*s1

calcolo vettoriale: pezzi della soluzione /* dichiarazioni*/!

int comp; double scalare; float r[3], s[3], c[3] = {0.0};!

/* lettura dati mediante ciclo for*/!

/* calcolo prodotto scalare*/!

scalare = 0.0;!

for(comp=0;comp<3;comp++)!

scalare = scalare + r[comp]*s[comp];!

/* calcolo prodotto vettoriale modo diretto*/!

c[0] = r[1]*s[2] – r[2]*s[1]!

c[1] = r[2]*s[0] – r[0]*s[2]!

c[2] = r[0]*s[1] – r[1]*s[0]!

/* calcolo prodotto vettoriale: for e indici modulo3*/!

for(comp=0;comp<3;comp++)!

[comp]=!r[(comp+1)%3]*s[(comp+2)%3]-r[(comp+2)%3]*s[(comp+1)%3];!

Array a più dimensioni c0! c1! c2! c3!

a[ 0 ][ 0 ] a[ 0 ][ 1 ] a[ 0 ][ 2 ] a[ 0 ][ 3 ]!r0!r1! a[ 1 ][ 0 ] a[ 1 ][ 1 ] a[ 1 ][ 2 ] a[ 1 ][ 3 ]!r2! a[ 2 ][ 0 ] a[ 2 ][ 1 ] a[ 2 ][ 2 ] a[ 2 ][ 3 ]!

Indice colonna!Nome array!

Indice riga!

int a[ 3 ][ 4]!Inizializzare

int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } };!Quello non specificato va a 0

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

Richiamare un elemento Prima indice di riga, poi di colonna printf( "%d", b[ 0 ][ 1 ] );!

Array a più dimensioni

/* esempio: immagine*/!

const int height = 256;!const int width = 256;!int i, j, image [height][width];!/* inizializzazione con 2 for: uno!

per righe e l’interno per colonne*/!for(i=0;i< width;i++)!

{!for(j=0;j<height;j++)!

image[i][j] = i*j;!}!

stringhe Stringhe sono array di caratteri

“first” - array di char – costanti fra due apici!Dichiarazione e inizializzazione

char string1[] = "first";!'\0' termina la stringa!string1 ha quindi 6 elementi!

Equivalente a char string1[6] = { 'f', 'i', 'r', 's', 't', '\0' };!

Per accedere al singolo carattere string1[ 3 ] is character ‘s’!

Il nome dell’array è il suo indirizzo. & non si usa in scanf scanf( "%s", string1 );!

esercizio: Media, mediana, modo su array

Media – somma valori divisa per il numero occorrenze

1, 2, 3, 4 => la media è 2,5 Mediana – il numero nel mezzo di un insieme ordinato

1, 2, 3, 4, 5 => la mediana è 3 Modo – il numero che compare più spesso

1, 1, 1, 2, 3, 3, 4, 5 => 1 è il modo

Array di strutture

come gestire diversi concorsi? array di strutture struct concorso c[3];!

Ogni elemento dell’array è una struttura conforme al template concorso l'array ha nome c, 3 elementi del tipo “struct concorso” Per accedere ai singoli elementi dell'array

specificare il nome dell'array seguito dall'indice, tra quadre, dell'elemento da referenziare;

usare l'operatore punto per accedere al campo voluto.

#include <stdio.h>!struct concorso { int serie;!

char organizzatore;!int partecipanti;};!

main()!{ int i; struct concorso c[3];!

c[0].serie = 2; c[0].organizzatore = 'F';!c[0].partecipanti = 482;!c[1].serie = 0; c[1].organizzatore = 'G';!c[1].partecipanti = 33;!c[2].serie = 3; c[2].organizzatore = 'E';!c[2].partecipanti = 107;!for(i = 0; i < 3; i++)!

printf("%d %c %d\n",c[i].serie,!c[i].organizzatore,c[i].partecipanti);}!

Array come campo di struttura /*globale – stato del concorso*/! serie struct concorso { int serie;!

char organizzatore;! organizzatore int partecipanti;!

partecipanti char stato [2];};!main()!

s0 { int i; struct concorso mio;! s1 mio.serie = 2;!mio.organizzatore = ’A';!mio.partecipanti = 15;!mio.stato[0] = ’T';!mio.stato[1] = ’F';!

printf("%d %c %d\n",mio.serie,!mio.organizzatore,mio.partecipanti);}!

for(i = 0; i < 2; i++)!printf("%s",mio.stato[i]);!

}!

Array come campo di struttura

/*locale – stato del concorso*/!main()!{struct concorso { int serie;!

char organizzatore;!int partecipanti;!char stato [2];};!

int i; struct concorso mio;!mio.serie = 2;!mio.organizzatore = ’A';!

mio.partecipanti = 15;!mio.stato[0] = ’T';!mio.stato[1] = ’F';!

printf("%d %c %d\n",mio.serie,!mio.organizzatore,mio.partecipanti);}!

for(i = 0; i < 2; i++)!printf("%s",mio.stato[i]);!

@}

Problemi di ricerca Esiste un certo dato in un array?

Ricerca sequenziale (dall’inizio o dalla fine, l’unica se i dati non sono ordinati) Ricerca dicotomica (dal mezzo, su dati ordinati)

Ricerca sequenziale #include <stdio.h>!#define MAXDIM 100 /* dimensione massima del!

vettore */!main()!{int i,K,N;!int V[MAXDIM];!do{!printf("\n Inserire la dimensione del vettore!non superiore a %d\n",MAXDIM);!scanf("%d",&N);!}while(N>MAXDIM);!

/* inserimento vettore */!for (i=0;i<N;i++)!{!

printf("Inserire l'elemento %d : ",i+1);!scanf("%d",&V[i]);!

}!/* Inserimento del valore da cercare ( chiave K!

)*/!printf("Inserire l'elemento da cercare : ");!scanf("%d",&K);!

/* scandire gli elementi del vettore partendo dal!primo V[0] e fermandosi se si trova K o se si!finisce l’array*/!

i=0;!while( K != V[i] && i<N )!

i = i + 1;!/*il risultato della ricerca dipende da quale!

condizione di uscita è stata verificata*/!if ( i<N ) printf("Elemento trovato in posizione!

%d\n", i+1);!else printf("Elemento non trovato\n");!

}!

Ricerca dicotomica 1) Si individua l’elemento che sta a metà del vettore; 2) Si confronta la chiave K con tale elemento. Se l’elemento

individuato non è uguale a quello cercato : • se K > elemento mediano la ricerca continua solo nel

semivettore superiore • se K < elemento mediano la ricerca continua solo nel

semivettore inferiore 3) Il procedimento continua suddividendo i semivettori via via

individuati.

Esempio: 2 4 5 6 8 9 14 trovare 9 Confronto 9 con 6 - ripeti sul vettore 8 9 14 Confronta 9 con 9 - trovato

Ricerca dicotomica #include <stdio.h>!#define MAXDIM 100!main()!{!int i,inf,sup,med,K,N; int V[MAXDIM];!do{!printf("\n Inserire la dimensione del vettore non!superiore a %d\n",MAXDIM);!

scanf("%d",&N);!}while(N>MAXDIM);!

/* inserimento del vettore ordinato */!for (i=0;i<N;i++)!{!

printf("Inserire l'elemento %d : ",i+1);!scanf("%d",&V[i]);!

}!

/* Inserimento del valore da cercare K */!printf("Inserire l'elemento da cercare : ");!scanf("%d",&K);!/*inizializzazione degli indici */!inf = 0; sup = N-1; med = (inf + sup)/2;!/*accedi al mediano del vettore a ciascun passo */!while ( K != V[med] && inf<sup )!{!

if ( K > V[med] ) /*vai nella parte alta*/!inf = med+1;!

else!sup = med-1; /*vai nella parte bassa*/!

med = (inf + sup)/2;!}!/*risultato della ricerca */!if ( V[med]== K )!

printf("Elemento trovato in posizione %d\n", med+1);!else printf("Elemento non trovato\n");!}!

Quale preferire? La Ricerca Sequenziale

ricerca con successo:Nel caso migliore ho un solo confronto e in quello peggiore N

Il numero medio di confronti risulta (N+1)/2 ricerca senza successo: L’algoritmo esamina sempre tutto il vettore, quindi il numero di confronti è sempre N

La Ricerca dicotomica Ad ogni iterazione l'insieme è dimezzato, il numero

di confronti è pari a quante volte N può essere diviso per 2 fino a ridurlo a 0.

in un vettore di dimensione N = 2h, l’algoritmo deve compiere circa h = log2(N) passi (e quindi confronti) per la ricerca senza successo, nel caso medio il numero è leggermente inferiore mentre nel caso migliore è 1.

Esempio : per cercare un elemento in un insieme di 1.000.000 elementi, nel caso pessimo con la Ricerca Sequenziale dovremmo eseguire circa 1.000.000 confronti, mentre con la Ricerca Binaria ne dobbiamo effettuare al massimo 21.

Problemi di ordinamento 3 metodi:

Selection Insertion Exchange Si parte da array iniziale con i valori disordinati, e si ordina nell’array stessa

Una passata per ordinare ogni posizione 32 24 31 101 55 71 Una passata per cercare il valore da mettere in quella

posizione

Selection sort Trovo il minimo fra gli N; poi il minimo fra gli N-1; etc e lo metto nella

posizione da ordinare

#define N 100!….!main ()!{! int i, j, min, temp; int dati[N];!/*acquisisci gli N valori*/!……!

for (i = 0; i < N-1; i++) {!min = i;!for (j = i+1; j < N; j++) {!/* trovo l’indice in cui si trova il minimo */!

if(dati[j]<dati[min])!min=j;!

temp = dati[i];!dati[i]=dati[min]; /*metto il minimo a posto*/!dati[min]= temp;!

}!}!

Esempio selection 67345 inizio 37645 dopo for i=0 34675 dopo for i =1 34576 dopo for i=2 34567 dopo for i = 3

Insertion sort ..{ int i, j; int dati[N];!

for (i = 1; i <N; i++)!for (j = i; j > 0; j--)!if (dati[j]<dati[j-1])!

{/*scambia*/;!temp = dati[j-1];!dati[j-1]=dati[j];!dati[j]= temp;!

}}!

Esempio insertion 67345 inizio 37645 dopo for i=0 34675 dopo for i =1 34576 dopo for i=2 34567 dopo for i = 3

sort Bubble sort su array

N passate Confronta un elemento con il successivo

Se il primo è minore o uguale, nulla Se maggiore, scambia

Repeat esempio:

originale: 34267 passata 1: 32467 passata 2: 23467 passata 3: 23467

Bubblesort – ordinare array a #include <stdio.h>!

# define! N 10!

main ()!{

int pass, j, temp, a[N];!/* lettura di a*/!

/* bubblesort a*/!for (pass = 1; pass <N; pass++)!

for (j = 0; j <N-1; j++)!if a[j] > a[j+1]!{/* scambio*/!temp = a[j] ; a[j] = a[j+1] ; a[j+1]=temp;!}

/* stampa di a*/!….!

}

esercizi Calcolare la somma dei primi N numeri interi

N(N+1)/2 N =1 Somma = 2/2 =1 N=2 Somma = 2(3)/2 = 3 cioè 1+2

Calcolare la somma dei primi N numeri pari N*N+N

Es: N = 1 Somma=2 N=2 Somma = 2*2+2 = 6 cioè 2+4