Esercizi su File e Liste
1
Esercizio
•
•
•
•
Si progetti e codifichi un programma C che apre il file di testo input.txt e genera il file
di testo output.txt, che contiene, in ordine inverso ma inalterate, le sole linee di
input.txt che hanno lunghezza compresa tra 10 e 20 caratteri (ignorando le altre
linee). A tale scopo, il programma alloca una lista dinamica che contiene le linee da
trasferire, genera il file scandendo la lista e la dealloca prima di terminare.
Si usi la seguente definizione della lista:
typedef struct EL { char linea[21]; struct EL * next; } Nodo;
typedef Nodo * Lista;
Si provi a costruire la lista nel modo più semplice che permetta poi di generare
facilmente l'output
Si può assumere che l'ultima linea di input.txt termini con '\n' e che nessuna linea
superi i 255 caratteri
2
Essendo chiaramente assai più complicato (e inutile) scandire il file un carattere alla volta, scandisco il file di input
una linea per volta con fgets() o con fscanf(…”%s”…), controllo subito se ogni linea è da trasferire, e nel caso la
inserisco in testa alla lista dinamica, in un nodo appositamente allocato. Così facendo, al termine del file di input
la lista in memoria contiene le linee già in ordine inverso: il file di output si genera con una semplice scansione
lineare, durante la quale si dealloca la lista.
int main () {
FILE * fp;
char buffer[256];
Lista lis = NULL, tmp;
// max 255 caratteri + 1 per il '\0'
if ( (fp=fopen("input.txt","r")) == NULL ) // Selezione linee da tenere
return -1;
while( fgets( buffer, 256, fp ) != NULL )
if ( strlen(buffer) >= 10 && strlen(buffer) <= 20 )
insTesta(&lis, buffer);
close(fp);
if ( (fp=fopen("output.txt","w")) == NULL )
return -2;
while ( lis != NULL ) {
// Man mano che trascrivo, dealloco
fputs( lis->linea , fp );
tmp = lis;
lis = lis->next;
free(tmp);
}
close(fp);
return 0;
}
void insTesta( Lista *lista, char * line ) { // Normale inserimento in
Lista tmp = *lista;
// testa con assegnamento
*lista = (Lista) malloc(sizeof(Nodo));
// del "dato" con strcpy
strcpy( (*lista)->linea, line );
(*lista)->next = tmp;
}
3
Esercizio (tde 14-9-2010)
• Le telecamere di un parcheggio multilivello
riconoscono le targhe di ogni auto in
ingresso. Se la targa è contenuta nel file
credito.txt (formattato come nel riquadro) e
il credito è di almeno 2,50 €, la funzione
int checkin(char * targa) restituisce 1,
altrimenti restituisce 0 (e una botola
risucchia l’auto in un pozzo senza fondo).
• Si codifichi in C la funzione checkin
int checkin(char * targa) {
FILE * f;
char line[100], plaque[8];
float credit;
if( (f = fopen("credito.txt", "r")) == NULL )
return -1;
while( fgets(line, 100, f) != NULL ) {
sscanf(line, "%s%f", plaque, &credit);
if( strcmp(targa,plaque) == 0 && credit >= 2.50 ) {
fclose(f);
return 1;
}
}
fclose(f);
return 0;
}
Esercizio (continua)
• Le auto ammesse leggono su un display il piano a cui devono
recarsi, che è calcolato automaticamente dal sistema come il primo
che abbia almeno un posto libero. La struttura dati del sistema è la
seguente
typedef struct Car { char * targa; struct Car * next; } Auto;
typedef Auto * Lista;
typedef struct Level { int postiliberi; Lista macchine;
struct Level * next; } Piano;
typedef Piano * ListaDiListe;
• dove ogni piano è pieno se il suo attributo postiliberi vale 0 e vuoto
se la sua lista macchine è vuota.
• Si codifichi in C la funzione int assegnapiano(ListaDiListe L, char
* targa), che restituisce il numero del piano oppure -1 se non c’è
posto. La funzione alloca anche il nodo corrispondente all’auto
entrata
Vediamo prima una semplice soluzione iterativa
int assegnapiano(ListaDiListe L, char * targa) {
int p = 1;
while( L != NULL && L->postiliberi == 0 ) {
L = L->next;
p++;
}
if( L == NULL )
return -1;
L->macchine = instesta(L->macchine, targa);
(L->postiliberi)--;
return p;
}
Lista instesta(Lista L, char * targa) {
Lista punt;
punt = (Lista)malloc(sizeof(Auto));
punt->targa = (char *)malloc(8); // 7 caratteri per la targa, uno per /0
strcpy(punt->targa,targa);
punt->next = L;
return punt;
}
E anche una semplice soluzione ricorsiva, usando la stessa funzione di servizio
int assegnapiano(ListaDiListe L, char * targa) {
int p;
if( L == NULL ) return -1;
if( L->postiliberi <= 0 ) {
if( (p = assegnapiano(L->next, targa)) < 0 ) return -1;
else return p + 1;
}
L->macchine = instesta(L->macchine, targa);
(L->postiliberi)--;
return 1;
}
Esercizio (continua)
• Si gestisca con la funzione ...checkout( ... ) l’uscita di un’auto dal
parcheggio, in modo da lasciare la struttura dati in uno stato
consistente. La funzione non si occupa dell’addebito del costo del
parcheggio. Le soluzioni sostanzialmente ricorsive ricevono un
punto di bonus
Possiamo definire due funzioni di servizio (ricorsive) direttamente ispirate a quelle
viste a lezione per trovare e cancellare un’auto in una lista semplice (la lista
macchine di ogni piano).
int find(Lista cars, char * targa) {
if( cars == NULL ) return 0;
if( strcmp(cars->targa, targa) == 0 ) return 1;
return find(cars->next, targa);
}
Lista remove(Lista cars, char * targa) {
Lista punt;
if( Lista != NULL )
if( strcmp(cars->targa, targa) == 0 ) {
punt = cars->next;
free(cars->targa); // era stata allocata una stringa dinamica
free(cars);
return punt;
}
else {
cars–>next = remove(cars->next, targa);
return cars;
}
else
return cars;
}
E usarle in una funzione (ricorsiva) che in ogni piano del parcheggio prima
verifica se c’è la macchina, e se la trova la dealloca e aggiorna il contatore dei
posti liberi in quel piano.
void checkout(ListaDiListe L, char * targa) {
Lista cars;
if( L == NULL )
printf("\n Nessuna traccia della macchina!\n");
else if( find(L, targa) ) {
L->macchine = remove(L->macchine, targa);
(L->numeroposti)++;
}
else
checkout(L->next, targa);
}