area dati globali

X    Y Z

? ? ?

3

Dati locali a main

Dati locali sum

Risultato ?

Ret_adr ?

parameter1 ?

parameter2 ?

temp

Macchina main

. scanf("%d",X);

. scanf("%d",Y);

Z = sum(X,Y);

Printf( . .);

-

Macchina sum

int sum(int parameter1,

int parameter2)

MOV X, parameter1 MOV temp, Risultato

MOV Y, parameter2 MOV ret_adr, PC

MOV Rit, Ret_adr Next fetch

MOV indirizzo

(prima istruzione sum), PC

Next fetch

Rit:MOV Risultato, Z

I parametri

I parametri formali definiscono l'interfaccia della funzione

tiporis nomefunction([tipo1 nome1, . tipon nomen]_op);

numero parametri formali:

- non limitato;

- uguale al numero di quelli attuali in ogni attivazione;

tipo dei parametri formali: identificatore del tipo e NON la sua definizione e può essere un tipo base, una struct, un puntatore (NO array);

corrispondenza tra parametro formale e attuale: posizionale;

ogni coppia parametro attuale/formale rispetta le regole di compatibilità e di conversione definite per le espressioni;

modalità di passaggio parametri: per valore:

la funzione riceve un valore, lo può modificare e utilizzare;

il valore ricevuto non è più restituito;

il parametro attuale può essere una variabile, costante o espressione;

la funzione ritorna un risultato;

tipo del risultato: tipo base, struct, puntatore, void (NO array).

I sottoprogrammi procedurali

Una funzione invocata come un'istruzione si chiama procedura

Esempio:

Insert();

l'invocazione procedurale implica la perdita del valore prodotto dalla funzione;

utilizzo del tipo void se non interessa il valore ritornato (es. void main()..)

una procedura può evitare il return (la procedura termina quando incontra la "}" che chiude la funzione.

Passaggio parametri per indirizzo simulato

parametro formale: tipo puntatore (*P) al tipo di struttura ricevuta;

parametro attuale di tipo indirizzo (&) alla struttura dati passata;

obbligatoria per gli array;

utilizzata anche per risparmiare memoria nel passaggio di una struttura dati di grandi dimensioni.

Esempio 3:

#include <stdio.h>

typedef int Tarray[8];

Tarray A;

void S1(Tarray a) s void S1(int a[]) /* primo elemento

void S2(int *a)

void main()

esecuzione:

inizio stampa  

Regole di visibilità degli identificatori

Concetto di blocco

Block ::=

block_declarative_part ::= declarative_part

una funzione è un blocco speciale con nome e parametri;

un blocco può dichiarare un altro blocco all'interno

una funzione può contenere più blocchi

Esempio 4:

#include <stdio.h>

typedef struct T;

void main()

void F1(int x)

}

x=3; /*istruzione 1*/

T=4; /*istruzione 2*/

J=5; /*istruzione 3*/

F1(4); /*istruzione 4*/

}

Definizioni:

identificatori di un programma s nomi assegnati a variabili, costanti, tipi e funzioni;

identificatori globali sidentificatori definiti nella global_declarative_part;

identificatori locali di una funzione s identificatori definiti nella function_declarative_part e nei parametri formali;

identificatori locali di un blocco s identificatori definiti nella block_declarative_part;

Campo di validità di un identificatore (scope)

Istruzioni del programma nelle quali un identificatore è visibile e manipolabile.

Campo di validità "teorico" (scope rules):

il blocco coincide con il campo di validità dei suoi identificatori locali;

la funzione coincide con il campo di validità dei suoi identificatori locali;

se un blocco/funzione contiene altri blocchi, il campo di validità degli identificatori del blocco/funzione più esterno si estende ai blocchi innestati;

il campo di validità degli identificatori globali coincide con l'intero programma.

Ancora l'esempio 4.

La rappresentazione gerarchica delle dichiarazioni

(derivata in modo statico)

unità    Identificatori definiti campo validità (teorico)

programma T, F1, main il programma

main   a main, blocco1,blocco2

blocco1 b blocco1

blocco2 c blocco2

F1   x,d F1, blocco3, blocco4

blocco3 e blocco3, blocco4

blocco4 f blocco4

Domanda: le istruzioni della funzione F1sono corrette?

SI locale a F1

2. NO improper use of typedef

3. NO undefined symbol

SI globale

Conflitto tra campi di validità

/*Program*/

int i;

void main()

Algoritmo di risoluzione dei conflitti (campo di validità reale):

Dato un identificatore ID presente in un'istruzione I:

si cerca l'identificatore ID tra quelli locali al blocco/funzione S a cui appartiene l'istruzione I;

se non lo trova e siamo in un blocco, allora cerca negli identificatori locali al blocco/funzione nel quale è stato dichiarato il blocco S; la navigazione può proseguire sino agli identificatori locali di una funzione;

se non lo trova e siamo in una funzione, allora cerca negli identificatori globali;

la ricerca termina con successo quando l'identificatore è individuato o con errore di compilazione se non è trovato.

Allocazione e tempo di vita delle variabili

le variabili globali (statiche):

allocate a inizio esecuzione programma;

tempo di vita s tempo di esecuzione del programma;

le variabili locali di un blocco/funzione (automatiche - RDA):

allocate a inizio esecuzione del blocco/funzione;

tempo di vita s tempo di esecuzione del blocco/funzione

- inizializzazione ad ogni invocazione;

- RDA allocato nello stack.

Funzioni ed effetti collaterali

Esempio 5:

/* P */

int b,c;

int sum(int x)

void main()

Esempio 6

/* P */

int b,c;

int sum(int x)

void main()

PRINCIPIO

Una funzione DEVE utilizzare SOLO variabili e costanti dichiarate nei parametri o nella function_declarative_part.

Sviluppo strutturato e incrementale di un'applicazione

Il problema

Memorizzare i risultati di un test sostenuto da N studenti e visualizzare la media dei punteggi ottenuti dagli studenti suddivisi nelle tre classi di appartenenza (prima, seconda,terza).

Predisporre inoltre una operazione che permetta di ordinare i dati in base al numero di matricola.

Il programma contiene un menù con le seguenti voci: 1 per memorizzare i dati, 2 per la media, 3 per terminare l'esecuzione.

Impostazione

progetto delle strutture dati globali;

suddivizione del problema in sottoproblemi e identificazione dei componenti del programma;

raffinamenti incrementali.

Lo schema del programma:

una struttura dati globale;

una funzione per il caricamento dati;

una funzione per il calcolo della media;

una funzione per l'ordinamento;

la funzione main col menù.

Alcuni suggerimenti

semplicità, chiarezza, niente trucchi (indice di ingenuità), massimizzare l'uso di parametri e dati locali;

buona documentazione:

commenti all'inizio del programma per identificare nome del programmatore, data e versione del programma (vers. x.y), per descrivere obiettivi, strutture dati globali, algoritmi, funzioni utilizzate;

commenti nelle funzioni per descrivere obiettivi, algoritmi e strutture dati;

stile:

nomi significativi per gli identificatori (ad esempio: ImportoSalario);

separare le istruzioni su linee diverse;

utilizzare l'indentazione;

spazi tra operandi di istruzioni/espressioni, linee bianche di separazione tra segmenti diversi di codice.

La struttura dati:

#define N 100  /*max numero di studenti */

typedef struct T_studente;

typedef T_studente T_arc[N];

T_arc archivio;

int ultimo; /*gestione dinamica del vettore archivio*/

La funzione main (struttura di base):

/* Program: . Responsabile: . data: . vers.

#include <stdio.h>

typedef enum boolean;

void main()

}

Sviluppo funzioni come stubs:

void MemorizzaDati(T_studente *s, int *u)

int CalcoloMedia(T_studente *s, int u),

void Ordina(T_studente *s, int u),

Raffinamento funzioni:

void MemorizzaDati(T_studente *s, int *u, int MAX)

}

while (!ok);

/*2. per ogni studente legge i dati*/

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

/*3. restituisce il vettore e l'indice dell'ultimo elemento caricato

*u = quanti -l;

float CalcoloMedia(T_studente *s, int u)

La verifica dell'applicazione (funzionale o prestazionale?)

Verifica funzionale:

Verificare le singole funzioni del programma; un programma non sempre utilizza tutte le funzionalità offerte (ad esempio, la funzione Ordina);

il test:

Si procede al test supportati da eventuale funzione di stampa;

/*Procedura di test*/

void Stampa (T_studente *s, int u)

identificare il tipo di ingresso da verificare: grandi o piccoli insiemi, valori limite, dati errati, particolari ordinamenti dei dati; ad esempio, inserire 0, N e N+1 elementi nel vettore, errori di tipo, violazione di range o overflow in lettura);

- identificare le sequenze di attivazione delle procedure (ordinamento sequenziale o casuale nelle menù driven);

- identificare il tratto critico da sottoporre a verifica (ad esempio, calcoli nei quali si può generare overflow i++, N/0); identificare le variabili da verificare, copertura delle istruzioni;

- definire lo strumento di controllo (debugger o istruzioni di write).

LA PROGRAMMAZIONE IN GRANDE

Lo sviluppo di sistemi di programmi di grandi dimensioni, sviluppati da molte persone e che continuano a evolvere nel tempo

Ciclo di vita di un'applicazione

studio di fattibilità (costi/benefici alternative);

raccolta/analisi requisiti;

progettazione e realizzazione dei programmi);

verifica (test di sistema, alfa test: uso reale nell'azienda produttrice, beta test: uso reale da clienti particolari);

manutenzione: correttiva (20%) ed evolutiva (80%) - può superare il 50% dei costi complessivi.

La progettazione e la realizzazione

si pone degli obiettivi di qualità

esterne del prodotto (utente):

correttezza

efficienza (risorse e tempo) --> valutazione complessità

robustezza ai malfunzionamenti

usabilità dell'interfaccia

interne del prodotto (produttore):

riusabilità in future applicazioni

modularità

estendibilità per future esigenze

portabilità su piattaforme diverse

compatibilità con programmi di terze parti

leggibilità intesa come correlazione del codice con le scelte effettuate

completezza ed efficacia della documentazione

adotta dei principi:

distinzione tra livello concettuale (cosa voglio) e livello realizzativo (come lo realizzo);

astrazione (evidenziare gli aspetti rilevanti tralasciando i particolari);

decomposizione (strutturazione di un sistema in parti - top/down, bottom/up - stabilendo le relazioni tra di esse).

sceglie le tecniche/strumenti opportuni:

tecniche di programmazione (programmazione strutturata, ricorsiva, ad oggetti);

modularizzazione;

tecniche di progettazione di algoritmi e strutture dati.

i linguaggi per la programmazione (C, C++, Java, ).

La modularizzazione

Programmi composti da parti indipendenti (moduli) e interagenti tramite opportune interfacce.

Obiettivo:

sviluppo di un programma

l'architettura globale (decomposizione programma in moduli con relative interconnessioni)

realizzazione del singolo modulo (raffinamento incrementale, sviluppo strutturato).

Effetti:

correttezza di un programma ricondotta alla correttezza dei singoli moduli;

integrazione naturale con moduli precedentemente realizzati;

facilità nel riuso;

compilazione separata.

Criteri di modularizzazione:

coesione: massimizzare l'uniformità e l'omogeneità dei componenti incapsulati in un modulo (strutture dati con le proprie funzioni);

information hiding: esportare da un modulo solo quanto necessario (massimizzare dati e funzioni locali);

accoppiamento: minimizzare il grado di interrelazione tra oggetti di moduli diversi (limitare l'esportazione di variabili globali);

l'interfacciamento esplicito: esplicitare le modalità di comunicazione tra i moduli.

Criteri aggiuntivi:

peso equivalente dei moduli definiti;

incapsulare in moduli parti dipendenti dall'hardware e/o software di base oppure legate a frequenti o previsti cambiamenti delle esigenze (approccio per cambiamento);

incapsulare in moduli parti che potranno trovare un riutilizzo futuro: generalizzazione di funzioni, utilizzo dell'astrazione (approccio per il riuso).

Tipi di modularizzazione

funzionale: insieme omogeneo di funzionalità rispetto ad un obiettivo (es. funzioni di stampa per più dispositivi, manipolazione stringhe, funzioni di conversione);

per oggetto: gestione di un particolare oggetto offrendo all'esterno un insieme di operazioni per utilizzare correttamente l'oggetto, nascondendo le porzioni dello stato interno dell'oggetto che non hanno rilevanza rispetto ai servizi offerti (es. funzioni gestione di un video o di un particolare archivio);

per tipo astratto: offre un tipo sul quale è possibile definire oggetti (istanze) e delle operazioni per manipolare le istanze del tipo. Nasconde la struttura del tipo (es. gestione file).

La modularizzazione in C

Limiti della nozione di function

la testata della function non definisce l'interfaccia: identificatori impliciti

indipendenza reciproca limitata: monomodulo

Dal programma monomodulare al programma composto da più file: un file è principale e gli altri di servizio.

ciclicità di importazione non permessa.

Realizzazione di un modulo/FILE di servizio

un file di servizio è costruito con le regole descritte per il file principale;

nei file di servizio non è possibile distinguere l'interfaccia dall'implementazione (definition e implementation module)

Import di variabili, variabili costanti e funzioni

1. Realizzazione senza header file.

Nel file xx.c che deve importare da altri file inserire le dichiarazioni:

1. extern const int MAX; per import di una costante variabile

2. extern int V[MAX]; per import di una variabile

3. extern int f(int *p); per import di una funzione

- non si precisa da quale file importare

- controllo tipologia a compile time

- 1. e 2. non allocano spazio e 3. non riporta il contenuto

Esempio;

/*file export.c*/

const int MAX =3;

int V[10]=;

int f(int *p)

/*file import.c*/

#include <stdio.h>

extern const int MAX;

extern int V[10];

extern int f(int *p);

void main()

2. Realizzazione con header file

- file di interfaccia (estensione .h) con le dichiarazioni di esportazione;

- file di implementazione (estensione .c) con il codice

- include del file .h nei file utilizzatori e nel file .c

- espansione macro

Esempio:

/*file export.h*/

extern const int MAX;

extern int V[10];

extern int f(int *p);

/* file export.c*/

#include 'export.h' /* per la congruenza*/

const int MAX =3;

int V[10] =;

int f(int *p)

/*file import.c*/

#include <stdio.h>

#include 'export.h'

void main()

3. Una variante nel file.h

Esempio:

/*file export.h*/

#if defined export

const int MAX;

int V[10] =;

extern int f(int *p);

#else

extern const int MAX;

extern int V[10];

extern int f(int *p);

#endif

/* file export.c*/

#define export

#include 'export.h' /* per la congruenza*/

int f(int *p)

/*file import.c*/

#include <stdio.h>

#include 'export.h'

void main()

4. le regole sugli identificatori

Unione degli identificatori globali di tutti i file del programma costituiscono gli identificatori globali del programma.

=> due identificatori globali in file diversi non possono avere lo stesso nome (main());

il campo di validità di un identificatore globale ID coincide col file che lo definisce e con tutti i file nei quali è dichiarato (extern ID);

=> tutti gli identificatori definiti in un file sono automaticamente esportati.

un identificatore da non esportare va dichiarato come static

=> identificatore globale al solo file nel quale è definito.

Esempio:

/* file export.c*/

#define export

#include 'export.h' /* per la congruenza*/

int f(int *p)

static void stampa(int *p);

Le classi di memoria per variabili (incluso variabili costanti)

il tempo di vita delle variabili globali (anche static) coincide col tempo di esecuzione dell'intero programma .

Import di costanti e tipi (typedef, define, tipi)

Non esiste la nozione di identificatore globale del programma e di dichiarazione, ma solo di identificatore globale del file

=> le definizioni valgono solo per il file nel quale sono riportate e non sono esportate

1. Simulazione interfaccia con header file

/*file export1.h*/

#define MAX 10

struct C ;

typedef struct C D[MAX];

extern D vettore;

extern void f(struct C *p);

/*file export1.c*/

#include 'export1.h'

#include <stdio.h>

D vettore

void f(struct C *p);

/*file import1.c*/

#include <stdio.h>

#include 'export1.h'

void main()

Osservazioni:

Violazione information hiding;

Il C non supporta il tipo di dato astratto;

La definizione di un identificatore è duplicata (file export e file import);

Problema:

/*file export.c*/

struct C ;

struct C var1 = ;

/*file import.c*/

struct C ;

extern struct C var1;

main();

CATENA DI PROGRAMMAZIONE

Problema

analisi e progettazione

algoritmo risolvente

EDITOR

file .c    file .c file.h

(codice sorgente)  

COMPILATORE

codice oggetto codice oggetto codice oggetto

(librerie)

__________ ________________

COLLEGATORE

codice eseguibile

LA MODULARIZZAZIONE PER OGGETTO

Esempio di modularizzazione per oggetto

/*file export2.h*/

extern void insert ();

extern void visualizza();

/*file export2.c*/

#include <stdlib.h>

#include 'export2.h'

struct T_elem ;

typedef struct T_elem elemento;

static elemento *lista=NULL;

static elemento *creael ()

return(elem);

}

void visualizza()

}

void insert ()

}

/*file import2.c*/

#include <stdio.h>

#include 'export2.h'

void main()

Esempio di modularizzazione per astrazione

/*file export3.h*/

struct T_elem ;

typedef struct T_elem elemento;

extern elemento *insert (elemento *lista);

extern void visualizza(elemento *lista);

/*file export3.c*/

#include <stdlib.h>

#include 'export3.h'

static elemento *creael ()

return(elem);

}

void visualizza(elemento *lista)

elemento *insert (elemento *lista)

return(lista);

}

/*file import3.c*/

#include <stdio.h>

#include 'export3.h'

static elemento *lista=NULL;

void main()

Verso la programmazione ad oggetti

Definire due tipi di dato astratto linea e poligono. Le operazioni disponibili sono:

- Crea: riceve le coordinate e genera un oggetto del tipo associato.

- Intersect: ritorna TRUE se una linea interseca un poligono.

boolean intersect (poligono x, linea t);

I FILE

La gerarchia della memoria

Nastro: struttura sequenziale

bot <------> eot

Disco: struttura non sequenziale

La memoria centrale come sequenza di parole fisiche.

La memoria secondaria come sequenza di contenitori di dati, chiamati file.

Il file è una struttura dati persistente di arbitraria dimensione contenente dati correlati di tipo strutturato o di tipo testo.

Struttura e metodi di accesso

struttura sequenziale;

accesso sequenziale (scansione degli elementi) e diretto (accesso ad un elemento tramite la sua posizione nel file).

Modalità di accesso

memoria centrale: diretto A[I], X.a

memoria di massa indiretto

Concetto di stato esistente e vuoto

I FILE in C

Le strutture dati persistenti, e in generale i dispositivi di I/O, sono gestiti sono gestiti da opportune librerie fornite con il linguaggio

Le funzionalità del modulo <stdio>

Tipi di file

file di testo;

file binari (occupazione e portabilità);

Tipo di accesso

sequenziale -----> <------> diretto

1 ..

Il descrittore del file

La tabella dei file aperti (per utente, per il sistema)

stdin descrittore 1 tastiera scanf, .

stdout descrittore 2 video printf, .

stderror descrittore 3 video

fd1 descrittore 4 file

fd2 descrittore 5 file

Definizioni e funzioni C preliminari

#include <stdio.h>

FILE *fp; descrittore del file

fp = fopen(filename, mode);

filename: stringa tra " " o pointer to string

mode operazione tipo operazione

ammessa file eseguita

------ -------- ---- -----------

"r" lettura testo bof su file esistente

"w" scrittura testo bof dopo (rewrite o creazione)

"a" append testo eof dopo (posizion. o creazione)

"rb" lettura binario bof come sopra

"wb" scrittura binario bof "

"ab" append binario eof "

varianti:

"r+" "rb+" lettura e scrittura

"w+" "wb+" scrittura e lettura

"a+" "ab+" append e lettura

fp =NULL se esito è negativo   

concorrenza nell'uso dei file

int fclose(fp)

esito positivo T fp=NULL; return (0)

esito negativo T return(EOF)

int remove(filename); int rename(oldname,newname);

Indicatori di errore (riportano l'esito dell'ultima read/write)

int=feof(fp);

eof T return (!0)

non eof T return(0)

int ferror (fp);

errore T return (!0) Es.: write dopo close

corretto T return(0)

int clearerr(fp);

- indicatori di error e eof T

Funzioni C di manipolazione dei dati

Manipolazione file testo formattata

int fscanf(fp, stringa controllo, adr(variabili));

lettura con conversione implicita;

legge a partire dalla posizione corrente;

sposta la posizione corrente del numero di caratteri letti;

corretta T return(numero elementi letti >0, escluso eof)

errore T return(<0) T controllo se feof o ferror

int fprintf(*fp, stringacontrollo, variabili);

scrittura con conversione implicita;

scrive a partire dalla posizione corrente;

sposta la posizione corrente del numero di caratteri scritti

corretta T return(numero elementi scritti

errore T return(<0)

Esempio:

/*programma manipolazione formattata senza controllo errori*/

file.txt

#include <stdio.h>

#include <string.h>

typedef struct

T_persona;

FILE *fp;

char filename[20]='file.txt';

T_persona p1;

void main()

else

if ((fp = fopen(filename, 'r')) == NULL)

else

Manipolazione file testo per carattere

int getc(fp); macro

int fgetc(fp); funzione

legge a partire dalla posizione corrente;

sposta la posizione corrente di un carattere;

corretta T return(codifica numerica ASCII del carattere letto)

errore T return(EOF) T ferror, feof

int putc(c, fp); macro

int fputc(c, fp); funzione

scrive a partire dalla posizione corrente;

sposta la posizione corrente di un carattere;

scrive il carattere c espresso come numero;

- corretta T return(carattere scritto)

- errore T return(EOF)

Manipolazione file testo per stringhe

char *fgets(char *str, int n, fp);

Lettura di n-l chars (se non incontra eof, <ret>) dalla posizione corrente del file e li carica in str con 0.

sposta la posizione corrente di n caratteri;

Corretta T return (str)

Errata T return(NULL) T ferror, feof

char *gets (char *str); per stdin

int *fputs(char *str, fp);

scrive str sino a 0 (escluso) sul file a partire dalla posizione corrente

sposta la posizione corrente di n caratteri;

corretta T return(0)

errata T return(EOF)

int *gets (char *str); per stdout

Manipolazione file binario

int=fread(adr(var), sizeof(elemento), numelementi, fp)

legge a partire dalla posizione corrente;

sposta la posizione corrente di numero bytes letti;

return (numelementi letti)

numelementi letti < numelementi T errore T feof, ferror)

int=fwrite(adr(var), sizeof(elemento), numelementi, fp)

scrive a partire dalla posizione corrente;

sposta la posizione corrente di numero bytes scritti;

return (numelementi scritti)

numelementi scritti < numelementi T errore)

Accesso diretto

int fseek(fp, long offset, int origine)

origine = SEEK_SET T posizione = bof + offset

SEEK_CUR T posizione = pos.corr. + offset

SEEK_END T posizione = eof + offset

corretta T return(0)

errore T return(<0)

long ftell(fp)

corretta T return (posizione corrente)

errore T return(<0)

rewind (fp);

- posizione = bof

Esempio:

/*Programma che genera il file itinerari*/

#include <stdio.h>

#include <string.h>

typedef struct

T_record;

T_record record;

FILE *id;

void main()

fclose(id);

/*Programma per legger un itinerario*/

#include <stdio.h>

#include <string.h>

typedef struct

T_record;

typedef enum BOOLEAN;

T_record record; int pos;

FILE *id; char citta[30]; BOOLEAN trovato= false;

void main()

else

fclose(id);

}

La gestione del buffer

int fflush(fp) forza buffer write

- write ->buffer ->disco

File e applicazioni

Le applicazioni:

memorizzano i dati in file in base a:

- struttura logica dei dati;

- tipo di operazioni previste;

definiscono strutture di memoria centrale di supporto.

I gestori di sistema devono salvare periodicamente i file (backup).

Gestione del file:

file passivo: le strutture dati persistenti sono lette interamente all'inizio dell'esecuzione dell'applicazione e riscritte interamente alla fine dell'esecuzione; durante l'esecuzione il file non è utilizzato.

file attivo: l'applicazione accede ai dati durante l'esecuzione.

Esempi:

Ipotesi: ininfluente il costo della manipolazione in memoria centrale.

Esempio 1: Applicazione per la gestione di due archivi: fornitori e società; una società può avere un solo fornitore, mentre un fornitore può fornire più società.

Ipotesi: file come struttura attiva dell'applicazione.

Struttura dei file:

Operazioni e loro valutazione:

1. Trovare il fornitore con codice = xx;

a) Algoritmo di scansione sequenziale:

typedef enum BOOLEAN;

typedef struct T_FORN;

T_FORN fornitore; BOOLEAN fine = false;

LeggiForn(file, fornitore);

while (!fine && !eof(file))

LeggiForn(file, fornitore);

}

costo (equiprobabilità): (Nf / 2)*sizeof(fornitore);

costo (ricerca su valore non chiave): Nf * sizeof(fornitore)

b) Algoritmo di scansione sequenziale via indice:

typedef enum BOOLEAN;

typedef struct T_FORN;

typedef struct T_INDEX;

T_FORN fornitore; BOOLEAN fine = false;

T_INDEX indice;

LeggiIndex(fileindice, indice);

while (!fine && !eof(fileindice))

LeggiForn(fileindice, indice);

}

}

costo (equiprobabilità): (Nf / 2)*sizeof(indice) + 1* sizeof(fornitore)

raffinamenti possibili: ricerca binaria su indice ordinato, indice in memoria.

2. Stampare i dati di ogni fornitore inclusi i dati delle società fornite:

a) Algoritmo di scansione sequenziale dei due file con memoria minima:

typedef struct T_FORN;

typedef struct T_COMP;

T_FORN fornitore;

T_COMP società;

LeggiForn(filefornitore, fornitore);

while (!eof(filefornitore))

LeggiForn(filefornitore, fornitore);

costo: Nf * sizeof(fornitore) + Nf * Ns * sizeof(societa)

b) Algoritmo di scansione sequenziale dei due file con utilizzo di memoria (si suppone Nf =K * B):

#define B 10

typedef struct T_FORN[B];

typedef struct T_COMP;

T_FORN fornitore;

T_COMP società; int i;

while (!eof(filefornitore))

costo: Nf * sizeof(fornitore) + (Nf /B) * Ns * sizeof(societa);

Osservazione:

il secondo algoritmo ottimizza l'accesso al file, ma richiede una quantità di memoria di supporto maggiore e una maggiore complessità algoritmica;

3. aggiornamenti sui file

insert;

delete;

update;

Esempio 2. Gioco del labirinto.

Il file passivo: soluzione che ottimizza l'efficienza durante il gioco, ma limita le dimensioni del labirinto;

file attivo: dalla lettura di una riga/colonna ad ogni movimento nel labirinto alla lettura periodica di una porzione del labirinto (finestra).

Esempio 3. Gestione di una rete stradale.

Esempi di operazioni:

1. Controllare che il grafo stradale sia connesso

2. Calcolo del percorso minimo tra due città:

3. Aggiornamenti dei dati della rete

a) il file passivo T tutto in memoria

b) il file attivo

1. Controllare che il grafo stradale sia connesso

Algoritmo basato sulla matrice di adiacenza:

BOOLEAN adiacenza [N,N];

arco i adiacente a arco j

implica che adiacenza[i,j] = adiacenza[j,i] = TRUE

2. Calcolo del percorso minimo tra due città:

una matrice che riporta in ogni elemento <i,j> se esiste un arco orientato tra i e j: la lunghezza (la minima per più archi);

una struttura dinamica per la rappresentazione del grafo.

3. Aggiornamenti dei dati della rete

L'aggiornamento è tipicamente un'operazione che coinvolge un arco alla volta.

Osservazioni conclusive:

File passivo: strutture dati e applicazioni semplici e con file di piccole dimensioni;

File attivo: strutture dati e applicazioni più complesse e con esigenze di performance.

VARIABILI DINAMICHE

globali (statiche)

locali (automatiche)

dinamiche:

a struttura nota a compile-time;

allocate e deallocate dal programmatore.

Una variabile dinamica non ha nome:

definizione della struttura (definizione del tipo);

referenza tramite indirizzo;

Esempio:

typedef struct rec; /* struttura */

rec p= NULL;  /* puntatore */

Creazione e distruzione variabili dinamiche

import dal modulo di libreria #include <stdlib.h>

void malloc(int num);

- alloca num caratteri e ritorna il puntatore

(NULL s problemi);

- il risultato void e il casting:

p = (rec *) malloc(size(rec));

- l'allocazione avviene nell'area di Heap

- heap overflow

- no calloc

void free(void *nome pointer);

free(p);

- la variabile è deallocata

- p assume il valore NULL ??

Operatori ammessi sulle variabili di tipo puntatore

p=q; p=NULL;   assegnamenti

if (p==q) o (p==NULL)    confronti (<>, ==)

*p dereferenziazione

aritmetica dei puntatori

Esempi e problemi

a) int a,b;

a=b;

b) int *p, *q;

c) effetto collaterale: modifica di *p si ripercuote su *q

p = (int *) malloc(size(int));

q=p;

if (p==q) .    SI

if (*p==*q). SI

d) q = (int *) malloc(size(int)); . .

if (p==q) . NO

if (*p==*q) .    ?

e) *p=3; *q=3;

if (p==q) .    NO

IF (*p==*q)..  SI

f) produzione di garbage: una variabile dinamica diventa irraggiungibile.

p = (int *) malloc(size(int));

q = (int *) malloc(size(int));

p=q;

void P()

g) dangling reference: una variabile puntatore con indirizzo non valido

p = q;

free(q);

*p= 2; errore in esecuzione

Costruttore di tipo ricorsivo (autoreferenza)

Strutture dati che coinvolgono più variabili dinamiche.

#include <stdlib.h>

struct T_elem ;

typedef struct T_elem elemento;

elemento *lista=NULL, *elem;

Creazione di un elemento dinamico:

elemento *creael ()

return(elem);

}

Strutture definibili attraverso l'uso del tipo ricorsivo

LA CODA - Politica di gestione: FIFO (First In First Out)

Operazioni principali (ipotesi: la coda non esiste inizialmente - può essere vuota/piena):

Visualizza coda

Inserisci elemento come ultimo elemento

Estrai il primo elemento

void visualizza(elemento *lista)

void visualizza(elemento *lista)

elemento *insert (elemento *elem, elemento *lista)

return(lista)}

void main()

Altri esempi

LA PILA - Politica di gestione: LIFO (Last In First Out)

Operazioni principali (ipotesi: la pila esiste sempre - può essere vuota/piena - vuota all'inizio):

Push (inserisci elemento come primo elemento della sequenza)

Pop (estrai il primo elemento dalla sequenza)

Errori comuni nella gestione di strutture a lista

i casi limite (coda vuota, coda con un elemento,.) non considerati;

la scansione oltre la fine sequenza:

void stampa(int *p) (*non gestita la coda vuota e la sua fine*)

rottura di una coda:

elemento *insert (elemento *elem, elemento *lista)

/* 2 */

Confronto array e liste di puntatori.

Svantaggi dell'ARRAY:

dimensione statica,

difficoltà negli inserimenti o nelle cancellazioni effettuate in posizioni intermedie in una sequenza ordinata;.

Vantaggi dell'array:

accesso diretto e non sequenziale agli elementi,

algoritmi migliori di ricerca (binaria) se la sequenza è ordinata.

PROCEDURE RICORSIVE

/* Program P1*/

void funct()

(*ricorsione diretta*)

void main()

/* Program P2*/

extern void funct2();

int a=1;

void funct1()

void funct2()

void main()

Permesse dalle regole sul campo di validità.

Formulazione ricorsiva di algoritmi:

identificare uno o più sottocasi che definiscono la terminazione;

determinare il passo ricorsivo: sottocaso del problema tale per cui la soluzione del sottocaso s alla soluzione del problema, ma su un insieme ridotto di dati.

Esempio: Calcolo N!

Algoritmo risolvente:

N=0 N!=1  N>0 N!=N*(N-l)!

/*Soluzione non ricorsiva*

#include <stdio.h>

int N;

int fatt(int n)

return (tot);

void main()

/*Soluzione ricorsiva*

#include <stdio.h>

int N;

int fatt(int n)

void main()

Esecuzione N=3

3*fatt(2)

2*fatt(1)

1*fatt(0)

Quali modifiche se n è grande?

- long int e %ld

Il record di attivazione (RDA)

area per il risultato di una funzione;

area per i parametri della funzione;

indirizzo di ritorno;

area per le variabili locali (escluso le dinamiche);

RDA(fatt)

Record blocco

area per le variabili locali (escluso le dinamiche);

RDA e stack

una funzione può avere nello stack zero o più RDA;

lo stack può essere vuoto o essere pieno;

Esempi:

© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta