Informatica 2 – modulo CMassimo Callisto De Donato

massimo.callisto@unicam.it

www.cs.unicam.it/massimo.callisto

LEZIONE 8 – LE STRUTTURE

Università degli studi di CamerinoScuola di scienze e tecnologia - Sezione Informatica

Le strutture

• Abbiamo visto tipi di dati base (int, char, ...) ed il tipo derivato array per manipolare gruppi omogenei di dati.

• Capita spesso di dover aggregare elementi di tipo diverso (non omogenei).

• Esempio: – scrivere un programma che memorizzi le date di

assunzione (es. 23 febbraio 2006) di n dipendenti (identificati da nome e cognome) con relativo stipendio. Si deve poter ricercare, a partire da un nome o stipendio, la relativa data di assunzione.

Strutture

• Soluzione:• 3 vettori per le date: int* gg, char *mese, int* anno

• 2 vettore per i dipendenti: char *nome, char* cognome

• 1 vettore per lo stipendio: int *stipendio

• La connessione tra i vettori è data dalla relativa posizione

• Funzione di ricerca che ritorni l’indice relativo al dipendente trovato (per nome o stipendio):

int ricerca(char* nome, char* cognome);

int ricerca_x_stipendio(int stipendio);

• Implementiamo la soluzione (esercizio).

• Abbastanza laborioso il tutto

Strutture

• Sfruttiamo un nuovo tipo di dato derivato che il C mette a disposizione: le strutture (struct)

• Una struct ci permette di organizzare in modo efficiente gruppi di dati di diverso tipo.

• Esempio: questa è la struttura che può modellare il concetto di data di assunzione

struct data {

int giorno;

char* mese;

int anno;

};

Strutture: schema

• Una serie di campi (campo1,…,campon) eterogenei:

• Ogni campo può essere di tipo base (int, float, ... ) o derivato (array, strutture, …).

• nome_struct identifica la struct nel programma.

struct nome_struct {

tipo_a campo1;

tipo_b campo2;

…

tipo_? campo1;

};

Strutture: esempi di definizione#define LEN 150

struct data {

int giorno;

char* mese;

int anno;

};

struct persona{

char nome[LEN];

char cognome[LEN];

char codice_fiscale[LEN];

int eta;

};

struct punto_vendita{

char nome[LEN];

char *citta;

int dipendenti;

};

struct punto{

int coordinata_x;

int coordinata_y;

};

Strutture: definizione variabili

• Le istruzioni di prima hanno solo detto al compilatore lo schema generale.

• Il passo successivo è definire una variabile:• di tipo struttura;

• il tipo deve seguire uno schema definito prima.

• Sintassi generale:struct nome_struct nome_variabile;

• Con le strutture di pima:struct data oggi; // n.b.: i dati in „oggi‟ sono ancora ??

struct punto_vendita alimentari;

struct punto punto_a, punto_b;

Strutture: definizione alternativa

• Spesso si usa una sintassi alternativa e più compatta per definire i tipi strutture.

• Usiamo la parola chiave typedef che funziona da alias per un tipo di dato:typedef nome_tipo mio_nuovo_nome;

• Esempio: i due modi sotto sono equivalenti:

struct data {

int giorno;

char* mese;

int anno;

};

struct data oggi;

typedef struct {

int giorno;

char* mese;

int anno;

} data;

data oggi;

Lo possiamo applicare a casi generali oltre che alle struct!

Strutture: accesso alla variabile

• Definito lo schema di una struct ed una variabile che segue quello schema, accediamo ai campi della variabile con

l’operatore punto ‘.’: variabile.membro;• Esempio:

typedef struct {

int giorno;

char* mese;

int anno;

} data;

data oggi;

oggi.giorno = 20;

oggi.mese = “maggio”;

oggi.anno = 2011;

Esempiotypedef struct{

float _x;

float _y;

} punto;

float powerOf(float);

float dst(punto, punto);

int main() {

char c;

punto pt_a, pt_b;

do{

printf(“Punto A: ");

scanf("%f%f", &pt_a._x, &pt_a._y);

printf(“Punto B: ");

scanf("%f%f", &pt_b._x, &pt_b._y);

printf("Distanza: %3.4f\n", dst(pt_a, pt_b));

}while((c=getchar()) != 'N');

return 0;

}

float powerOf(float value){

return (value*value);

}

float dst(punto a, punto b) {

float distanza, dx, dy;

dx = powerOf(a._x - b._x);

dy = powerOf(a._y - b._y);

distanza = sqrt(dx + dy);

return distanza;

}

Ci vuole sempre la &

Strutture: funzioni e strutture

• Il passaggio delle strutture come parametro formale

avviene sempre per valore.

• Le strutture possono essere ritornate come un qualsiasi

tipo di dato.

• Esercizio: aggiungere al programma precedente una

funzione per calcolare il punto medio tra gli estremi.

– Prototipo: punto punto_medio(punto a, punto b);

– Formula matematica PM = ((x1+x2)/2, (y1+y2)/2)

Strutture: assegnazione• Possiamo assegnare strutture ad altre strutture, ovviamente se il tipo è

uguale:

typedef struct {

int giorno;

char *mese;

int anno;

}data;

data oggi domani;

oggi.giorno = 23;

oggi.mese = "febbraio";

oggi.anno = 2006;

domani = oggi; // ora domani ha gli stessi valori di oggi

domani.giorno++;

Strutture: assegnazione/* abbiamo usato su new_data un modo equivalente per dichiarare una

struttura. Di conseguenza, la dichiarazione della variabile di quel tipo

è leggermente diversa. */

typedef struct{

int giorno;

char mese[10];

int anno;

} data;

struct new_data{

int giorno;

char mese[10];

int anno;

};

data oggi;

struct new_data domani;

domani = oggi; //errore - tipi non compatibili

Strutture: equivalenze

• Non ha senso relazionare direttamente due strutture, i membri si.

typedef struct{

float x;

float y;

} punto;

punto a; a.x = 10.2; a.y = 20.1;

punto b; b.x = 13; b.y = 27.4;

if(a < b) {…} // errore

if(a.x < b.x & a.y < b.y) {…} // ok

Strutture: inizializzazione

• L’inizializzazione avviene come per gl array.

typedef struct{

float x;

float y;

} punto;

punto a = {10.2, 20.1};

punto b = {13, 27.4};

a.x = b.x - 5.2;

a.y = ++b.y - 4; // a.y==23.4, b.y==28.4

Strutture: array di strutture• Stessa sintassi degli array.

#define LEN 100

typedef struct {

char nome[LEN];

char citta[LEN];

int dipendenti;

} shop;

shop negozio[5];

int i;

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

scanf("%s%s%d", negozio[i].nome, negozio[i].citta,

&negozio[i].dipendenti);

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

printf("%s,%s,%d\n", negozio[i].nome, negozio[i].citta,

negozio[i].dipendenti);

Esempio: passaggio di array di strutture#include <stdio.h>

#define LEN 100

#define N 3

typedef struct {

char nome[LEN];

char cognome[LEN];

} worker;

worker add(void);

void stampa_lista(worker *);

int main() {

worker persona[N];

int i;

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

persona[i] = add();

stampa_lista(persona);

return 0;

}

worker add(void){

worker tmp;

scanf("%s%s", tmp.nome, tmp.cognome);

return tmp;

}

void stampa_lista(worker *lista){

int i;

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

printf("%s,%s\n", lista[i].nome,

lista[i].cognome);

}

Strutture: membri eterogenei

• Una struttura può aggregare altre strutture.

• Questo permette di rappresentare schemi di dati avanzati.

• Esempio: rappresentiamo un insieme di persone con un array persona anagrafe[4000];

typedef struct{

int giorno;

char mese[10];

int anno;

} data;

typedef struct{

char via[35];

int numero;

char citta[30];

char provincia[2];

} indirizzo;

typedef struct{

char nome[30];

char cognome[30];

data nascita;

char comune[30];

char telefono[20];

indirizzo ind;

} persona;

Strutture: puntatori a strutture

• E’ possibile dichiarare puntatori a strutture ed ottenere gli effetti già visti (es.: pass. per rif. di strutture, allocazione dinamica di strutture).

• Usiamo sempre:

– & per l’indirizzamento;

– L’operatore * per accedere al contenuto della struttura puntata.

typedef struct{

int giorno;

char* mese;

int anno;

} data;

data oggi, *pts;

pts = &oggi;

(*pts).giorno = 12;

(*pts).mese = "Giugno";

(*pts).anno = 2011;

N.b.: (*pts).anno è diverso da *pts.anno

L’operatore . ha precedenza su *

Precedenza tra operatori (aggiornata)

Precedenze fra Operatori

Operatori Associativita'

() [] -> . da sinistra a destra

! ~ ++ -- + - & * (tipo) sizeof da destra a sinistra

* / % da sinistra a destra

+ - da sinistra a destra

<< >> da sinistra a destra

< <= > >= da sinistra a destra

== != da sinistra a destra

& da sinistra a destra

^ da sinistra a destra

| da sinistra a destra

&& da sinistra a destra

|| da sinistra a destra

?: da destra a sinistra

= += -= *= /= %= &= ^= |= <<= >>= da destra a sinistra

, da sinistra a destra

Strutture: puntatori a… scrittura compatta ->

• Con i puntatori a strutture possiamo usare l’operatore ‘->’ al posto degli operatori * e .

typedef struct{

int giorno;

char* mese;

int anno;

} data;

data oggi, *pt;

pt = &oggi;

pt->giorno = 23; // (*pt).giorno=23;

pt->mese = “Marzo”; // (*pt).mese=“Marzo”;

pt->anno = 2011; // (*pt).anno=2006;

Esempio#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

typedef struct {

int ora, min, sec;

} clock;

void _initc(clock *pt);

void _updatec(clock *pt);

void _stampc(const clock *pt);

int main(int argc, char *argv[])

{

clock ora;

clock *pts = &ora;

_initc(pts);

printf("Timer started. Ctrl+C to

stop\n");

while(1){

_updatec(pts);

sleep(1000);

}

return 0;

}

void _initc(clock *pt){

pt->ora = pt->min = pt->sec =

0;

}

void _updatec(clock *pt){

pt->sec = ++pt->sec % 60;

if(!pt->sec){

pt->min = ++pt->min % 60;

if(!pt->min){

pt->ora++;

}

}

_stampc(pt);

}

void _stampc(const clock *pt){

printf("[%dh %dm %ds]\r", pt-

>ora, pt->min, pt->sec);

}

N.b.: Non sempre otteniamo gli stessi risultati su piattaforme diverse.

Esercizio

• Implementare l’esercizio proposto all’inizio con i vettori utilizzando le strutture.

• La struttura che identifica il dipendente contiene un campo key per l’identificazione univoca.

• Lo stipendio lo possiamo aggregare al dipendente.

Strutture: allocazione dinamica

• L’allocazione dinamica di strutture fa affidamento su sizeof(). Senza non possiamo sapere quanta memoria occupa una struttura.

typedef struct{

int giorno;

char* mese;

int anno;

} data;

data *new_day;

new_day = (data *) malloc(sizeof(data));

if(new_day == NULL) {/* out of memory */}

new_day->giorno = 23;

new_day->mese = "Marzo";

new_day->anno = 2011;

Strutture: esempio di liste

• Le strutture rivestono un ruolo fondamentale nell’implementazione delle liste, ovvero elementi uguali connessi in sequenza.

DATI DATI DATI Null

Testa Coda

I dati possono essere di tipo arbitrario

I puntatori puntano allo stesso tipo dell’elemento della lista

• Rispetto ad un array, una lista ha un lunghezza variabile dato che gli elementi vengono generati, allacciati e rimossi a run-time.

Esempio complesso: anagrafe (1)#include <stdio.h>

#include <stdlib.h>

typedef struct {

char nome[100];

char cognome[100];

} persona;

typedef struct {

persona *corrente;

struct anagrafe *prossimo;

} anagrafe;

persona* aggiungi_persona(void);

anagrafe* aggiungi_anagrafe(void);

void stampa_anagrafe(anagrafe*);

void accoda(anagrafe*, anagrafe*);

N.b.: Ancora non abbiamo terminato il typedef per anagrafe . Quindi dobbiamo mettere la parola chiave struct

Esempio complesso: anagrafe (2)persona* aggiungi_persona(void){

persona *tmp = (persona *) malloc(sizeof(persona));

if(tmp == NULL){

printf("Out of memory!");

exit(-1);

}

printf("Insericni cognome e nome separati da spazio:");

scanf("%s%s", tmp->cognome, tmp->nome);

return tmp;

}

anagrafe* aggiungi_anagrafe(void){

anagrafe *tmp = (anagrafe *) malloc(sizeof(anagrafe));

if(tmp == NULL){

printf("Out of memory!");

exit(-1);

}

tmp->corrente = aggiungi_persona();

tmp->prossimo = NULL;

return tmp;

}

Esempio complesso: anagrafe (3)void accoda(anagrafe* lista, anagrafe* elemento){

if(lista->prossimo == NULL)

lista->prossimo = (struct anagrafe *) elemento;

else accoda(lista->prossimo, elemento); // chiamata ricorsiva

}

void stampa_anagrafe(anagrafe* ang){

printf("[%s, %s]\n", ang->corrente->cognome, ang->corrente->nome);

if(ang->prossimo != NULL)

stampa_anagrafe((anagrafe *) ang->prossimo); // chiamata ricorsiva

}

Esempio complesso: anagrafe (4)

/* mettiamo tutto insieme */

/* potevamo pensare a schemi di input migliori */

int main(int argc, char *argv[])

{

int i = 10;

anagrafe *elemento;

anagrafe *mia_lista = aggiungi_anagrafe();

stampa_anagrafe(mia_lista);

while(i--){

accoda(mia_lista, aggiungi_anagrafe());

stampa_anagrafe(mia_lista);

}

return 0;

}