Quattro Esercizi su File e Liste
1
A) Ecopass
•
•
Si consideri la seguente definizione:
typedef struct Elem { char * targa; struct Elem * next; } Auto;
typedef Auto * Lista;
Il sistema di controllo del traffico di una città registra gli accessi delle auto al centro.
Ad ogni passaggio rilevato, il software invoca una funzione di prototipo int
ingresso(char * targa) con la targa del veicolo come parametro. La funzione:
–
–
–
–
–
–
•
•
Inserisce la targa nella lista dinamica autoInCentro, che è una variabile globale di tipo Lista
Se la targa risulta già nel centro storico, stampa a video un messaggio di errore
Verifica che la targa appartenga a un veicolo registrato nel file pra.txt
Se non è registrato (auto straniera, targa falsa, …) interrompe la ricerca
Controlla se la targa appartiene a uno dei veicoli autorizzati, registrati nel file permessi.txt
Se la targa è registrata e non autorizzata, la inserisce la nel file multe.txt
Si codifichi la funzione ingresso().
I file hanno il formato indicato qui sotto.
pra.txt
permessi.txt
multe.txt
AB234XF
Luigi Verdi
Panda Turbo
BB154TR
Mario Rossi
Cayenne S
BB154TR
Mario Neri
Cayenne S
AB234XF
Luigi Verdi
Panda Turbo ...
BB331FT
Luca Mori
...
BB154TR
AG677SY
2
B) "Salvare/ripristinare" una lista tramite file
• Supponiamo di avere in memoria una generica
lista dinamica, definita nel modo "consueto":
typedef struct Elem {
Tipo dato;
struct Elem * next;
} Nodo;
• Vogliamo scrivere due funzioni
– void saveList( Nodo * lista, FILE * fp );
– Nodo * loadList( FILE * fp );
che salvano su file il contenuto della lista e
ricostruiscono una lista analoga a quella salvata
Così la lista sopravvive al tempo di vita del programma
3
Strategia di soluzione (1)
Prima possibilità (file testuale)
• Scrittura
– Scriviamo sul file, in forma di sequenza di stringhe, il
contenuto di tutti i nodi, elencando separatamente campi
e/o elementi di Tipo (se si tratta di un tipo struct e/o array)
• Operiamo le eventuali conversioni necessarie dai generici tipi
base in stringhe (interi, float, … convertiti in opportune stringhe)
• Lettura
– Leggiamo uno alla volta i valori dal file, riempiendo i nodi
di una lista via via allocati per accogliere tali valori
• Operiamo le conversioni opposte, in base alla corrispondenza
posizionale tra i valori e i campi (il primo valore nel primo campo,
il secondo nel secondo, … convertendo stringhe  interi, float, …)
• Con questa strategia il file generato è ragionevolmente leggibile (e modificabile)
da parte dell'occhio umano, intervenendo con un normale editor di testo
4
Strategia di soluzione (2)
Seconda possibilità (file binario)
• Scrittura
– Scriviamo sul file una sequenza di "blocchi di byte" che
siano ognuno la "immagine fedele" (bit a bit) del
contenuto della memoria occupata dai dati (di tipo Tipo),
senza conversioni
• In questo modo un intero di valore 35 non sarà rappresentato dai
caratteri consecutivi '3' e '5', ma dai byte della sua codifica in
complemento a due (00000000 00000000 00000000 00100011)
• Ogni blocco scritto "misura" esattamente sizeof(Tipo) byte
• Lettura
– Leggiamo i blocchi di byte dal file a ritmo di sizeof(Tipo),
riempiendo progressivamente i nodi di una lista
• La corrispondenza è ancora posizionale, ma direttamente sui byte
delle celle di memoria, "riempite" nell'ordine in cui erano state
"svuotate"
•
Il file così generato è di norma illeggibile per l'occhio umano
5
Attenzione
• Non possiamo salvare su file i valori dei puntatori e sperare che, in
futuro, alla loro lettura (da parte di un altro programma, magari su
altro elaboratore) essi siano ancora validamente dereferenziabili
• I dati si possono salvare su file nell'ordine in cui compaiono nella
lista, ma la "infrastruttura di collegamento" di elementi e puntatori
deve essere ricreata ogni volta che la lista è caricata
testa
Nodo
Nodo
Nodo
Nodo
Tipo
Tipo
Tipo
Tipo
RAM
Disco
FILE
6
void saveList ( Nodo * lista, FILE * fp ) {
while ( lista != NULL ) {
stampa( lista->dato, fp ); /* Dipende da come è */
lista = lista->next;
/* strutturato il tipo Tipo */
}
}
Nodo * loadList ( FILE * fp ) { /* Ignoriamo per brevità i problemi */
Nodo * lista = NULL;
/* dovuti a indisponibilità di memoria */
Tipo t;
int ok;
Nodo * InsCoda(Nodo * lista, Tipo t) {
t = leggi( fp, &ok );
Nodo * p;
if ( lista == NULL ) {
while ( ok ) {
p = (Nodo *) malloc( sizeof( Nodo ) );
lista = InsCoda ( lista, t );
p–>next = NULL;
p–>dato = t;
t = leggi( fp, &ok );
return p;
}
}
return lista;
else {
lista->next = InsCoda( lista–>next, t );
}
return lista;
}
}
7
void stampa ( Tipo d, FILE * fp ) {
int i;
fprintf( fp, "%d %d %d\n", d.data.day, d.data.month, d.data.year);
fprintf( fp, "%f\n", d.temperature);
fprintf( fp, "%s\n", d.description);
/* ESEMPIO */
for ( i=0; i<SIZE_V; i++ )
fprintf( fp, "%d ", d.vettore[i]);
typedef struct t_el {
struct { int day;
fprintf( fp, "\n");
int month;
}
int year; } data;
float temperature;
char description[SIZE_D];
int vettore[SIZE_V];
} Tipo;
Tipo leggi ( FILE * fp, int * ok ) {
int i;
char c = 'a';
Tipo d;
*ok = 1;
c = fscanf( fp, "%d%d%d", &(d.data.day), &(d.data.month), &(d.data.year));
if ( c == EOF ) { *ok = 0; /* Omettiamo per brevità il controllo */
CONSUMA
return d; } /* che il file non termini a metà */
il '\n' dopo
fscanf( fp, "%f\n", &(d.temperature));
il numero
/* fscanf( fp, "%s", d.description); //Se ci sono spazi non funziona */
for( i=0; i<SIZE_D && c!='\n'; i++ ) /* Ma possiamo procedere a caratteri */
{ c = fgetc(fp); d.description[i] = c; }
d.description[i-1] = '\0';
for ( i=0; i<SIZE_V; i++ )
fscanf( fp, "%d", &(d.vettore[i])); /* O anche… d.vettore + i */
return d;
}
8
Versione con file binario
• Usare fread e fwrite
– con sizeof(Tipo)
• Lasciata come esercizio!
• N.B. Attenzione al contenuto dei dati…
– Nell'esempio che abbiamo visto i dati contenuti nei
nodi (cioè le struct di tipo Tipo) sono interamente
costituite da aggregati di dati direttamente contenuti
nella struct, senza puntatori ad altre parti (stringhe o
altri dati dinamici).
– Ma se il dato contenesse puntatori ad altri dati
(ovviamente) quei puntatori messi su file
perderebbero significato
• Occorre recuperare i dati puntati e salvare su file anche
quelli, per poter poi ricostruire la lista
9
C) Indice delle parole di un testo
text.txt
amìala ch'â l'arìa, amìa
cumm'â l'é, cumm'â l'é!
amìala cumm'â l'arìa, amìa
ch'â l'è lê, ch'â l'è lê!
amìala cumm'â l'arìa, amìa,
amìa cumm'â l'è!
amìala ch'â l'arìa, amìa ch'â
l'è lê, ch'â l'è lê!
nera che porta via, che porta
via la via,
nera che non...
index.txt
amìa (5)
amìala (4)
arìa (4)
che (3)
cumm (5)
nera (2)
non (1)
porta (2)
via (3)
Dolcenera – F.De André – Anime Salve –1996
10
Specifica del problema
• Il programma da realizzare analizza un file
ASCII, contenente un testo generico su più
righe, e genera in un secondo file ASCII un
indice delle parole contenute nel primo
(considerando solo quelle di 3 o più lettere),
specificando di ognuna il numero di occorrenze.
• Delle parole non devono (ovviamente) far parte i
segni di interpunzione, i caratteri di spaziatura,
gli apostrofi…
• Nell'indice le parole compaiono in ordine
alfabetico
11
Strategia di soluzione
• L'indice si rappresenta bene con una lista dinamica
– È estremamente difficile, infatti, stimarne a priori la dimensione
• Il file deve essere scandito in modo da estrarre le singole
parole e ignorare numerosi separatori
– ' ' '.' ',' ';' ':' '+' '*' '-' '/' '!' '?'
'\'' '(' ')' '\t' '\n' '\\' '<' '>'
– Ci sono molti modi di estrarre le parole durante la scansione del
file:
• Un carattere alla volta, costruendo le parole selezionando i soli
caratteri validi consecutivi
• Con fscanf + %s e "ripulendo" poi le parole dai caratteri indesiderati
• Leggendo una linea alla volta e facendo la scansione della linea
• Con la funzione strtok() della libreria string.h (string tokenizer)
12
Strategia di soluzione
• Le parole estratte dal file sono via via inserite nella lista
in modo tale che la lista resti ordinata (alfabeticamente):
– allocando un nuovo elemento se la parola non è nella lista
– contando una occorrenza in più se la parola c'è già
– N.B.: si tratta di un particolare tipo di “inserimento ordinato”
• Terminata la scansione della lista, si apre il file di output
e si scrive una linea per ogni nodo
• Spunti per arricchire la soluzione
– Si può introdurre alla fine una fase di filtro per selezionare solo le
parole con una frequenza superiore a una data soglia
– Si può generare una seconda lista (ed eventualmente un
secondo file) in cui le parole compaiono in ordine di frequenza
– Si può rendere parametrica la scelta dei separatori (in un file!)
– Si può decidere di considerare uguali o diverse le maiuscole
13
Struttura dell'indice
typedef struct Element {
char wor[30];
int occ;
struct Element * next;
} Node;
Spreco di spazio!
Le parole mediamente
sono assai più corte
L'ideale sarebbe allocare via via
delle stringhe dinamiche…
Tale variante è lasciata per
esercizio
14
Node * ins_ord_cont(Node * head, char w[])
{
Node *cur = head, *prev = NULL; /* Puntatori di supporto
Node *t;
while ( cur != NULL && strcmp(cur->wor, w) <= 0 ) {
prev = cur;
cur = cur->next;
/* Cerco la posizione di w
}
if ( prev != NULL && strcmp(prev->wor, w) == 0 ) {
prev->occ += 1;
return head;
/* Se w c'è già, è nel precedente
}
t = (Node *) malloc(sizeof(Node));
strcpy( t->wor, w );
t->occ = 1;
/* Se w non c'è, alloco un nodo per lei
t->next = cur;
/* cur punta alla "coda" della lista
if ( prev == NULL )
return t;
/* prev è NULL se w è la prima parola
else {
prev->next = t;
/* altrimenti attacchiamo il nodo che
return head;
/* contiene w a quello che c'è prima
}
}
*/
*/
*/
*/
*/
*/
*/
*/
15
int main () {
FILE * fp;
Node * index = NULL;
if ( (fp = fopen("text.txt", "r")) == NULL ) {
printf("\n\n ERRORE APERTURA FILE IN LETTURA\n\n");
return -1; /* codice errore */
}
generaCHARWISE( &index, fp ); /* Strategia 1 char x volta */
fclose(fp);
if ( !(fp = fopen("index.txt", "w")) ) {
printf ("\n\n ERRORE APERTURA FILE IN SCRITTURA\n\n");
return -2; /* altro codice errore */
}
writeIndexToFile( index, fp );
writeIndexToFile( index, stdout ); /* Scrive… a video */
dealloca( index );
return 0;
}
16
void generaCHARWISE( Node * *head, FILE * fp ) {
char c, parola[30], *tmp;
int i = 0
while( (c = fgetc(fp)) != EOF ) {
if ( !isSeparator(c) )
parola[i++] = c;
else {
parola[i++] = '\0';
i = 0;
if ( strlen(parola) > 2 )
*head = ins_ord_cont(*head, parola);
}
}
}
int isSeparator( char c ) {
char *s = " .,;:+*-/!?'()\t\n\"\\<>";
int is = 0;
while ( !is && *s != '\0' )
is = *(s++) == c;
return is;
}
17
void writeToFile( Node * h, FILE * fp )
{
if( h == NULL )
fprintf(fp, "INDICE VUOTO\n");
while( h != NULL ) {
fprintf(fp, "%s (%d)\n", h->wor, h->occ);
h = h->next;
}
/* Si noti che per scrivere su */
return;
/* stdout (a video) basta passare */
}
/* come argomento tale file speciale */
void dealloca( Node * p )
{
if ( p != NULL ) {
dealloca ( p->next );
free( p );
}
return;
}
18
void generaSTRTOK( Node * *head, FILE * fp ) {
char buff[500], *z, *sep = " .,;:+*-/!?'()\t\n\"\\<>";
while( fgets(buff, 100, fp) != NULL ) {
z = strtok(buff, sep);
while (z != NULL) {
if (strlen(z) > 2)
*head = ins_ord(*head, z);
z = strtok(NULL, sep);
/* Estrazione da buff */
}
/* del token successivo */
} /* NB: strtok restituisce NULL alla fine della stringa */
}
char * strtok( char * stringa , char * separatori );
La funzione strtok riceve come 1° argomento una stringa da "tokenizzare" e come 2° argomento
un'altra stringa che contiene tutti i caratteri da considerare "separatori di token". Tokenizzare
significa suddividere in token, definiti come tutte le (massime) sottosequenze di caratteri diversi
dai separatori (token è il nome in gergo di un elemento di un linguaggio artificiale).
La funzione ha una particolarità: conserva come static il riferimento alla linea da tokenizzare
che riceve alla sua prima chiamata, e non lo sostituisce finché non sia invocata con un NULL
come primo argomento. In questo modo può restituire ad ogni invocazione un nuovo token (il
"successivo" nella linea), finché non ha esaurito la linea (al che restituisce NULL).
Si noti che il set di separatori può cambiare anche durante la tokenizzazione di una stessa linea.
19
D) Il crucipuzzle
O
I
S
O
I
S
A
C
D
V
S
R
A
I
A
O
M
E
C
M
R
R
A
S
A
M
O
E
AMO
ARCO
ARMADIO
CASA
IVA
ORCO
OSSO
RAI
SCI
20
Specifica (un esercizio “di riepilogo”)
• Vogliamo mettere tutto assieme, scrivendo un
“risolutore di puzzle generici” che:
• Legge da file lo schema
– Alloca una matrice dinamica che lo rappresenta
• Legge da file la lista di parole
– Eventualmente: le memorizza in una lista dinamica
(non è strettamente necessario…)
• “Cancella” dallo schema le parole della lista
• Visualizza i caratteri rimanenti, che formano la
“chiave” del puzzle
21
Il file di input
• Un file a caratteri
• Struttura:
–
–
–
–
Numero di righe dello schema (rows)
Numero di colonne dello schema (cols)
Caratteri (una riga di char su ogni linea)
Parole (una parola per linea)
• Così il file di testo è comodo
da leggere e scrivere anche
per l’occhio umano
4
7
ARMADIO
MRPIVSA
ORCASAI
GSIORCO
AMO
ARCO
ARMADIO
CASA
IVA
ORCO
OSSO
SCI
22
Struttura
int main( int argc, char * argv[] ) {
Apertura del file
Allocazione dello schema
Scansione/creazione della lista di parole
Ricerca parole e marcatura dello schema
Visualizzazione della chiave
}
23
Quali funzioni?
• Scomposizione in “moduli”
– Riuso di parti di codice
– Minimalità delle interfacce…
• Ci sono molte possibilità!
– Si può creare un TDA "puzzle" che preveda vari modi di leggere
schema e parole, incapsulando il fatto che la schema si trovi su
file in una funzione "opaca"
– Non è necessario memorizzare in RAM la lista di parole, che
possono essere lette una alla volta e "cancellate", mentre è
irragionevole non creare in memoria la matrice dello schema
• Anche se in teoria si potrebbe scandire il file "simulando" l'accesso
in verticale e diagonale (si ricordi che un file è visto come uno
"stream" di caratteri in successione)
24
Quali problemi?
Uno, soprattutto: allocazione di una matrice dinamica…
• Ricordando che le matrici statiche sono allocate dal compilatore come
una successione di vettori contigui, posso pensare di allocare un unico
"vettorone dinamico" di dimensione equivalente, nel modo seguente:
char * m = (char *) malloc( rows * cols * sizeof(char) ) /* funziona? */
Sì, in teoria funziona, ma… facendo così se provo ad accedere con la
notazione m[i][j] … non funziona!!
Perché?
25
RIPASSO array multidimensionali
Per gli array multi-dimensionali
• Il calcolo dello spiazzamento richiede di
conoscere le dimensioni intermedie
– Tipo m[R][C]; /*N.B.: R righe, C colonne*/
– m[i][j]  accesso al j-esimo elemento della iesima colonna
– m[i][j]  *( *(m + i) + j )  m + C·i + j
• serve conoscere sia la dimensione del tipo sia il numero
di colonne ( sizeof(Tipo) e C; R non serve)
– Tipo p[X][Y][Z]
– p[i][j][k]  *(*(*(p+i)+j)+k)  p + Y·Z·i + Z·j + k
• serve conoscere dimensione del tipo, altezza e larghezza
( sizeof(Tipo), Y e Z; la "profondità" X non serve)
26
m[i][j] non funziona perché…
…abbiamo allocato un vettore, non una matrice! Nelle dichiarazioni
statiche, il nome di un vettore bidimensionale è una costante simbolica
equivalente a un doppio puntatore, non a un puntatore semplice, e
La dimensione C della slide precedente è nota al compilatore, a tempo di
compilazione. Qui la dimensione cols è una variabile che assume valore a
runtime
Possiamo aggirare il problema ricordando come è strutturata la memoria, e
operare “a basso livello” simulando l'accesso per righe/colonne nel vettore
monodimensionale allocato… come se fosse una matrice:
Scriveremo *( m + (i*cols) + j ) per “intendere” m[i][j]…
laddove invece equivale a m[ (i*cols) + j ]
Per non appesantire troppo il codice si può definire una funzione di accesso (o
sfruttare una macro!!) che ci permetta di accedere con la notazione acc(m, i, j)…
ad esempio:
#define acc(x,y,z) ( *( (x) + ((y)*cols) + (z) ) )
27
Ma come fare per poter scrivere m[i][j]?
Si dichiara un vettore dinamico di puntatori a vettori dinamici:
int r, rows, cols; /* contatore, num. righe, num. colonne */
/* lettura di rows e cols dal file - omessa per brevità */
char ** p;
p = (char **) malloc( rows * sizeof(char *) );
for ( r = 0; r < rows; r++ )
p[r] = (char *) malloc( cols * sizeof(char) );
Così possiamo accedere agli elementi direttamente con la notazione
p[i][j]
che è “risolta” dal compilatore automaticamente nel seguente modo:
*( *(p + i) + j )
dereferenziando dapprima una sola volta il doppio puntatore,
incrementato di i, per poi dereferenziare nuovamente il risultato, questa
volta incrementato di j
28
Una matrice dinamica nello heap
p
cols
p è una
variabile
statica
A R
rows
p[0]
p[1]
p[2]
p[3]
M A D
M R P
I
O R C A
I O
V S
S
G S I O R
A
A I
C O
p[3][2]
heap
Attenzione:
Dichiarando matrici statiche NON si alloca il vettore intermedio di puntatori.
Il vettore intermedio "deve" essere allocato per poter accedere alla matrice
dinamica con il consueto accesso a doppio indice ( p[i][j] ).
Inoltre, nello heap gli elementi della matrice non sono allocati in un solo
blocco contiguo, ma in tanti blocchi contigui quante sono le chiamate a malloc.
29