Laboratorio di Calcolatori 1

(1)

Laboratorio di Calcolatori 1

Corso di Laurea in Fisica A.A. 2007/2008

Dott.Davide Di Ruscio

Dipartimento di Informatica Università degli Studi di L’Aquila

(2)

Nota

Questi lucidi sono tratti dal materiale

distribuito dalla McGraw-Hill e basati su del

materiale fornito dal Prof. Flammini Michele

(3)

Sommario (II parte)

Il Linguaggio C

 Caratteristiche generali

 Un linguaggio C semplificato ed esempi di semplici programmi

 Struttura di un programma C

 Direttive del pre-processore

 Parte dichiarativa:

 tipi

 definizioni di tipi

 definizioni di variabili

 Parte esecutiiva

 istruzione di assegnamento

 istruzioni (funzioni) di input-output

 istruzioni di selezione

 istruzioni iterative

 Vettori mono e multidimensionali

 Funzioni e procedure

 File

 Allocazione dinamica di memoria

 Suddivisione dei programmi in piu' file e

 Algoritmi elementari

 ricerca sequenziale e binaria

 ordinamento di un vettore: per selezione, per inserimento, per fusione e a bolle

 Aspetti avanzati di programmazione

 ricorsione

 strutture dati dinamiche

RIFERIMENTI

Ceri, Mandrioli, Sbattella Informatica arte e mestiere McGraw-Hill

(4)

Allocazione e cancellazione di memoria

 malloc (sizeof (TipoDato));

 Crea in memoria una variabile di tipo TipoDato, e restituisce come risultato l’indirizzo della variabile creata

 Se P è una variabile di tipo puntatore a TipoDato, l’istruzione:

P = malloc(sizeof(TipoDato));

assegna l’indirizzo restituito dalla funzione malloc a P

 free(P)

 Rilascia lo spazio di memoria puntato da P

 Richiedono l’inclusione del file header stdlib.h tramite la direttiva

#include <stdlib.h>

(5)

Esempio: allocazione dinamica di vettori

#include <stdio.h>

main() {

int *a,n,i,imin;

scanf("%d",&n);

if (n > 0) {

a=(int *) malloc(n*sizeof(int));

for (i=0; i<n; i++) scanf("%d",&a[i]);

imin = 0;

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

if (a[i]<a[imin]) imin=i;

printf("%d",imin);

}

else

printf("Vettore vuoto");

(6)

… Proc ( …) ..int *Punt1;

int **Punt2;

…

Record di attivazione di Proc

5

3

Punt1 Punt2

...

Stack e Heap

(7)

Rischi della gestione dinamica della memoria

 produzione di garbage :

 P = malloc(sizeof(TipoDato));

 P = Q;

 “riferimenti fluttuanti” (dangling references):

 P = Q;

 free(Q);

(8)

• Costruzione e gestione della struttura dinamica (pseudotipo astratto) lista mediante puntatori:

Lista

e1 e2 en

Ultimo elemento

Lista dinamica

Puntatore alla

“testa di lista”“testa di lista”

Elemento 1 della lista

Puntatore a elemento 2 Puntatore NULL

(9)

 Invece di dichiarare il tipo lista, si dichiarano i suoi elementi^:

struct EL {

TipoInfo Info;

struct EL *Prox;

};

typedef struct EL TipoElemLista;

typedef TipoElemLista *TipoLista;

 Oppure

typedef struct EL {

TipoInfo Info;

struct EL *Prox;

} TipoElemLista, *TipoLista;

Dichiarazione lista dinamica (1)

(10)

 Dichiarazione standard; mette in evidenza il tipo della lista:

TipoLista Lista1, Lista2, Lista3;

 Dichiarazioni abbreviate:

TipoElemLista *Lista1;

se non interessa mettere in evidenza il tipo della lista, ma si vuole indicare esplicitamente il tipo dei suoi elementi.

struct EL *Lista1;

può sostituire entrambe le typedef se non è necessario nominare esplicitamente né il tipo della lista né il tipo dei suoi elementi.

Dichiarazione lista dinamica (2)

(11)

/* Lista è la variabile locale che punta alla "testa di lista". La funzione assegna alla “testa di lista" il valore NULL corrispondente al valore di lista vuota */

void Inizializza (TipoLista *Lista) {

*Lista = NULL;

}

Lista1 Lista

Operazioni sulle liste:

Inizializzazione

 L’istruzione

Inizializza(&Lista1);

produce:

 Al termine dell’esecuzione, il parametro formale Lista viene eliminato

(12)

int ListaVuota (TipoLista Lista)

/* Produce il valore vero (1) se la lista passata come

parametro è vuota, falso (0) in caso contrario, a Lista viene passato il valore contenuto nella variabile testa di lista. Lista punta pertanto al primo elemento della lista considerata */

{

if (Lista == NULL) return 1;

else

return 0;

}

Controllo di lista vuota

La chiamata sarà:

ListaVuota (Lista1)

(13)

int Ricerca (TipoLista Lista, TipoInfo Info) {

TipoLista Cursore;

Cursore=Lista;

while (Cursore != NULL && Cursore–>Info != Info) Cursore = Cursore–>Prox;

/* In questa maniera Cursore viene fatto puntare all'elemento successivo della lista */

if (Cursore== NULL) return 0;

else return 1;

}

Ricerca di un elemento nella lista

(14)

int Ricerca (TipoLista Lista, TipoInfo Info) {

if (Lista == NULL) return 0;

else

if (Lista–>Info == Info) return 1;

else

return Ricerca(Lista–>Prox, Info);

}

Ricerca di un elemento nella lista,

versione ricorsiva

(15)

Inserimento di un nuovo elemento in testa alla lista (1)

Punt = malloc(sizeof(TipoElemLista));

Punt–>Info = Info;

Lista

e1 e2 en

Punt

Lista

e1 e2 en

Punt

Info

(16)

• Infine si collega il nuovo elemento al precedente primo elemento della lista e la testa della lista viene fatta puntare al nuovo elemento:

Lista

e1 e2 en

Punt

Info

Inserimento di un nuovo elemento

in testa alla lista (2)

(17)

void InsercisciInTesta (TipoLista *Lista, TipoInfo Info) {

TipoLista Punt;

/* Allocazione dello spazio necessario per la memorizzazione del nuovo elemento e inizializzazione del puntatore */

Punt = malloc(sizeof(TipoElemLista));

Punt–>Prox = *Lista;

*Lista = Punt;

}

e1 e2 en

Punt

Info

Inserimento di un nuovo elemento

in testa alla lista (3)

(18)

void InserisciInCoda (TipoLista *Lista, TipoInfo Info) {

TipoLista Cursore, Punt;

Punt–>Prox = NULL;

if (ListaVuota (*Lista))

*Lista = Punt;

else {

Cursore=Lista;

while (Cursore->prox != NULL) Cursore=Cursore->prox;

Cursore->prox= Punt;

}

Inserimento di un nuovo elemento

in coda alla lista

(19)

Inserimento di un nuovo elemento in coda alla lista, versione

ricorsiva

void InserisciInCoda (TipoLista *Lista, TipoInfo Info) {

Tipolista Punt;

if (ListaVuota (*Lista)) {

Punt–>Prox = NULL;

*Lista = Punt;

}

else InserisciIncoda(&((*Lista)–>Prox), Info);

}

(20)

Stampa Lista

void StampaLista(TipoLista Lista){

TipoLista Cursore;

Cursore=Lista;

while (Cursore!=NULL){

printf("|%d|->",Cursore->Info);

Cursore=Cursore->Prox;

}

printf("NULL\n");

}

(21)

(22)

Gestione file



Il file system in C



Principali operazioni sui file (dalla Standard Library)



Esempi

(23)

File System in C

 Un programma C prima di poter utilizzare un file deve aprire un flusso di comunicazione.

 Al termine dell’utilizzo di un file il flusso di comunicazione viene chiuso

 Informazioni sul file ed il suo stato:

 Posizione del file

 Tipo del file (di testo o binario)

 Operationi possibili

 Posizione corrente del cursore nel file

 Indicatore di end of file (EOF)

 Indicatore di errore (ERROR)

(24)

File system in C

 Queste informazioni sono contenute in una

struttura. Il suo tipo è FILE, ed è definita nell’header file stdio.h

FILE *ifp, *ofp; /*pointers for input and output file*/

 Non abbiamo bisogno di conoscere nel dettaglio questa struttura, in quanto viene creata e gestita automaticamente dalle librerie di input/output del C

 Nel linguaggio C un file è semplicemente una

sequenza di byte, ogni dispositivo fisico viene visto

(25)

Tabella file aperti

nomefile:

modouso:

poscorr:

….nomefile:

modouso:

poscorr:

….nomefile:

modouso:

poscorr:

nomefile: FileTre modouso:

poscorr:

nomefile: FileUno modouso:

poscorr:

nomefile:

FileDue modouso:

poscorr:

Variabili puntatore stdin

Tabella dei file aperti

File

StandardInput

stdout

stderr

f1

f2

f3

StandardOutput

StandardError

FileUno

FileDue

FileTre

(26)

Operazioni di gestione dei file in ANSI C



fopen, fclose;



fgetc, fputc;



fgets, fputs;



fprintf, fscanf;



fread, fwrite;



fseek, fsetpos;



ftell, fgetpos;



...

Contenute nella libreria: stdio.h

(27)

 FILE *fopen(nomefile, modalità)

 "apre" un file ovvero inizializza una area di memoria attraverso la quale vengono scambiati i dati tra

memoria principale e secondaria

 Deve essere effettuata sempre prima di ogni tipo di elaborazione sul file

 Se l'apertura del file non ha successo la funzione restituisce NULL.

 int fclose (FILE *fp)

 "chiude" un file chiudendo il relativo canale di comunicazione

 Se la chiusura del file non ha successo la funzione restituisce NULL

 Deve essere effettuata sempre alla fine delle elaborazione sul file

Apertura e chiusura di file

(28)

Apertura e chiusura di file

int main(void)

{ int a, sum = 0;

FILE *ifp, *ofp /* input file pointer, output file pointer */

ifp = fopen(“my_file”, “r”); /* aperto in lettura */

ofp = fopen(“outfile”, “w”); /* aperto in scrittura */

...

fclose(ifp);

Come aprire e chiudere i files.

Puntatori a strutture di tipo FILE

(29)

Modalità di apertura dei files

“r” - Lettura (testo)

“w” - Scrittura (testo)

“a” - Scrittura a fine file (testo)

“rb” - Lettura (binario)

“wb” - Scrittura (binario)

“ab” - Scrittura a fine file (binario)

“r+”, “w+”, “a+” – Lettura e Scrittura (testo)

“rb+”, “wb+”, “ab+” – Lettura e Scrittura (binario) FILE *ifp;

ifp = fopen(“filename”, “r”);

(30)

Per scrivere su file: funzione fprintf() analoga a printf() Per leggere da file: funzione fscanf() analoga a scanf()

Lettura e scrittura formattata

esempio: “%s %12.2f\n”

fprintf(ifp, string_controllo,lista_arg);

fscanf (ifp, string_controllo, lista_var);

Deve essere specificato un puntatore a FILE:

Esistono tre speciali puntatori predefiniti stdin punta a: tastiera stdout punta a: schermo stderr ^puntaa: schermo

(31)

 int fprintf(FILE *pf, str_cont, elementi)

 scrive caratteri in un file secondo il formato specificato

 Restituisce il numero di caratteri scritti se l'operazione è andata a buon fine, altrimenti restituisce un valore negativo

 int fscanf(FILE *pf, str_cont, ind_elementi)

 legge caratteri da un file secondo il formato specificato e assegna i valori letti ai suoi successivi argomenti

 Restituisce il numero di caratteri letti se l'operazione é andata a buon fine, altrimenti restituisce EOF

Lettura e scrittura formattata

(32)

 int fputc(int c, FILE *pf)

 scrive un singolo carattere in un file

 Restituisce il carattere stesso se l'operazione è andata a buon fine, altrimenti restituisce EOF

 int fgetc(FILE * pf)

 legge un carattere dal file specificato

 Restituisce il carattere letto (come intero) se

l'operazione è andata a buon fine, altrimenti restituisce EOF se si é raggiunta la fine del file

Lettura e scrittura di caratteri

(33)

 char * fgets(char *s, int n, FILE *fp)

 legge un numero specificato di caratteri da un file e li memorizza in una stringa aggiungendo il carattere di fine stringa

 Restituisce la stringa se l'operazione é andata a buon fine, altrimenti restituisce NULL

 int fputs(char *s, FILE *fp)

 Scrive una stringa nel file specificato senza aggiungere il carattere di fine stringa

 Restituisce 0 se l'operazione é andata a buon fine, altrimenti restituisce EOF .

Lettura e scrittura di stringhe

(34)

 int remove(<nomefile>)

 Cancella il file identificato da <nome file>

 int rename(<vecchionome>,<nuovonome>)

 Modifica il nome del file identificato da <vecchionome> a

 Le funzioni restituiscono 0 se le operazioni avvengono

correttamente, altrimenti restituiscono un valore diverso da zero

remove e rename di file

(35)

Gestione indicatori di stato

 Quando si rileva un errore in una operazione di

accesso a file, vengono aggiornati degli "indicatori di stato“

 int ferror(FILE *fp)

 Restituisce un valore diverso da 0 se si è verificato un errore sul file, altrimenti restituisce 0

 int feof(FILE *fp)

 Restituisce un valore diverso da 0 se é stata raggiunta la fine del file, altrimenti restituisce 0

 void clearerr(FILE *fp)

 Resetta gli indicatori di stato

 In caso di errore la variabile interna errno (in

<errno.h> ) registra un numero che da indicazioni sul tipo di errore

(36)

Funzioni di posizionamento su

file

^ Quando leggiamo o scriviamo in un file, il sistema che tiene traccia della posizione corrente nel file effettua l’operazione di lettura /scrittura a

partire da quella posizione (e quindi in modo sequenziale).

 Abbiamo a disposizione delle funzioni che ci permettono di accedere in una posizione specifica del file:

int rewind(FILE *fp);

 setta la posizione corrente all’inizio del file

int ftell(FILE *fp);

 restituisce il valore della posizione corrente

int fseek (FILE *fp, long offset, int place);

 sposta la posizione corrente di offset bytes rispetto a place, dove place può essere SEEK_SET, SEEK_CUR or SEEK_END

rispettivamente per l’inizio, la posizione corrente o la fine del file

 L’offset può essere anche negativo.

(37)

/* Legge un file al contrario */

#define MAXSTRING 100 main()

{ char fname[MAXSTRING];

int c;

FILE *ifp;

fprintf(stdout, "\nInput a filename: ");

scanf("%s", fname);

ifp = fopen(fname, "r");

fseek(ifp, 0, SEEK_END);

fseek(ifp, -1, SEEK_CUR);

while (ftell(ifp) > 0) {

c = fgetc(ifp);

putchar(c);

fseek(ifp, -2, SEEK_CUR); } fclose(ifp);

} Dobbiamo spostare la posizione corrente

indietro di 2 caratteri, poiché il fgetc l’aveva

Esempio

(38)

/*Legge e mostra sul video il contenuto del file di testo filechar*/

/* Contiene la definizione di EOF, del tipo FILE e le testate delle funzioni che operano su file */

#include <stddef.h>

/* Contiene la definizione di NULL */

main() {

FILE *fp;

int c;

fp = fopen("filechar", "r");

if (fp != NULL)

/* Il file viene aperto in lettura con modalità testo */

{

while ((c = fgetc(fp)) != EOF)

/* Viene letto e stampato un carattere per volta sino a fine file */

putchar(c);

fclose(fp);

}

Altri esempi

(39)

/*Lettura e scrittura di stringhe (1)*/

#include <stdio.h>

#include <stddef.h>

#include <string.h>

#define OK 1

#define ERROR 0

#define MAXLINE 100 int copiaselettiva(char refstr[]) {

char line[MAXLINE];

FILE *fin, *fout;

fin = fopen("filein", "r");

/* filein viene aperto in lettura con modalità testo */

fout = fopen("fileout", "w);

/* fileout viene aperto in scrittura con modalità testo */

If (fin == NULL || fout == NULL) return ERROR;

else {

Altri esempi (2)

(40)

…

while (fgets(line,MAXLINE,fin) != NULL)

/* fgets legge da filein al più MAXLINE–1 caratteri e assegna al vettore line i caratteri letti, incluso l'eventuale carattere di newline, e termina la stringa con il carattere \0 */

if (strstr (line,refstr) != NULL)

/* La funzione strstr restituisce la posizione della prima occorrenza della stringa puntata da refstr nella stringa puntata da line; se la seconda stringa non è contenuta nella prima viene restituito il valore NULL */

fputs(line,fout);

fclose(fin);

fclose(fout);

return OK;

Altri esempi (3)

(41)

File binari

Principali caratteristiche:

 I file binari sono comprensibile all’elaboratore, ma non hanno un formato leggibile dall’uomo come quello testuale

 Un file binario è in grado di memorizzare strutture

 Sono più efficienti dei file testuali in quanto non deve avvenire alcuna conversione tra il formato binario (presente in memoria centrale) e quello testuale

 Non possono essere letti facilmente da altri programmi non sviluppati in C

(42)

Lettura e scrittura di strutture

 int fread(void *ptr,dimelemento,numelementi, FILE *fp);

Legge dal file fp, numelementi strutture di dimensione dimelemento e le memorizza nell’array ptr.

 int fwrite(void *ptr, dimelemento, numelementi, FILE *fp);

Scrive sul file fp, numelementi strutture di dimensione dimelemento presenti nell’array ptr.

 Anche nei file binari è possibile usare la funzione fseek.

Naturalmente l’offset rappresenta lo scostamento in bytes, e

(43)

Files binari: esempio (1)

typedef struct { int x,y,z;} rec;

main()

{ int i,j;

FILE *f;

rec r;

/* crea il file di 10 strutture */

f=fopen(“pippo","wb");

if (f!=NULL)

for (i=1;i<=10; i++)

{ r.x=i; r.y=i*2; r.z = i*3;

fwrite(&r,sizeof(rec),1,f); } fclose(f);

(44)

Files binari: esempio (2)

/* legge le 10 strutture */

f=fopen(“pippo","rb");

if (f==NULL) return 1;

for (i=1;i<=10; i++) {

fread(&r,sizeof(rec),1,f);

printf("%d\n",r.x);

}

fclose(f);

(45)

Files binari: esempio (3)

/* usiamo fseek per leggere

le 10 strutture in ordine inverso */

f=fopen(“pippo","rb");

if (f!=NULL)

for (i=9; i>=0; i--)

{ fseek(f,sizeof(rec)*i,SEEK_SET);

fread(&r,sizeof(rec),1,f);

printf("%d\n",r.x); } fclose(f);

}