Testo
Scrivere una funzione che riceva come parametro una lista, e costruisca una nuova lista composta dai soli elementi pari della prima, nello stesso ordine in cui si trovano nella lista. Si vedano gli esempi qui sotto.
| Parametro | Lista ritornata |
|---|---|
| (1 3 5 8 9 10 2) | (8 10 2) |
| () | () |
| (2 4 2 6) | (2 4 2 6) |
| (1 9 3 5) | () |
| (2 1 1 1 2) | (2 2) |
Si noti che la lista di partenza non deve essere modificata: la funzione riceve come parametro una lista, e ne restituisce una nuova come valore di ritorno.
Valutazione per questo esercizio:
Driver e file di prova
Programma driver: 16set02-driver.c La soluzione va inserita dove appare il commento /* inserire qui la soluzione */, e deve avere il prototipo:
TipoLista SoloPari(TipoLista);
Il nome del file che contiene la lista che viene passata alla funzione va dato da linea di comando (da prompt dei comandi, si fa 16set02-driver nomefile, mentre dal TurboC si può impostare il nome del fil nel menu Run->Arguments). Alcuni possibili file di prova, con i valori che devono risultare, sono i seguenti:
| File lista | Risultato funzione |
|---|---|
| lista0.txt (lista vuota) | (lista vuota) |
| lista1.txt | 12 |
| lista2.txt | 4 4 2 |
| lista3.txt | 8 2 8 4 |
| lista4.txt | (lista vuota) |
| lista5.txt | 2 4 2 |
| lista6.txt | 0 2 8 2 |
Soluzione
Il primo livello di raffinamento dell'algoritmo indica soltanto che ogni elemento pari della lista va messo in una nuova lista.
per ogni elemento della vecchia lista
se e' pari
inseriscilo nella nuova lista
A questo punto, va precisato che la lista vecchia va scandita in ordine, e che gli elementi vanno inseriti nella nuova lista in ordine. Quindi, l'inserimeno va fatto in coda alla lista nuova.
nuova_lista=lista vuota
per ogni elemento della vecchia lista
se e' pari
inseriscilo in coda alla nuova lista
A questo punto, la traduzione in codice è ovvia, usando la funzione InserisciCodaLista che inserisce un elemento in coda a una lista:
TipoLista SoloPari(TipoLista l) {
TipoLista s;
s=NULL;
while(l!=NULL) {
if(l->val%2==0)
InserisciCodaLista(&s,l->val);
l=l->next;
}
return s;
}
Per completare la soluzione occorre anche riportare il testo della funzione InserisciCodaLista, che inserisce un elemento in coda a una lista. Si può anche usare la stessa funzione che è riportata nel resto del materiale didattico, e che viene copiata qui sotto.
void InserisciCodaLista(TipoLista *pl, int e) {
TipoLista t;
/* caso lista inizialmente vuota */
if(*pl==NULL) {
*pl=malloc(sizeof(struct NodoLista));
(*pl)->val=e;
(*pl)->next=NULL;
return;
}
/* caso lista con almeno un elemento */
t=*pl;
/* vado avanti fino alla fine della lista */
while(t->next!=NULL)
t=t->next;
/* qui t punta all'ultima struttura della lista: ne
creo una nuova e sposto il puntatore in avanti */
t->next=malloc(sizeof(struct NodoLista));
t=t->next;
/* metto i valori nell'ultima struttura */
t->val=e;
t->next=NULL;
}
Testo
Descrivere i due metodi di rappresentazione in memoria degli alberi n-ari (punteggio massimo per questo esercizio: 6 punti).
Soluzione
Vanno descritti i file binari, che sono spiegati nelle relative pagine delle dispense.
Testo
Si vogliono memorizzare i dati relativi agli articoli in vendita in un negozio usando un file.
I dati da memorizzare sono in particolare i seguenti: nel negozio sono presenti differenti tipi di prodotti, e ogni prodotto è caratterizzato da un codice (un numero intero). Il file deve contenere esclusivamente le seguenti informazioni: per ogni prodotto, va memorizzato il numero di articoli attualmente presenti nel negozio. Dal momento che anche questo è un intero, il file deve contenere, per ogni prodotto, il suo codice e il numero di articoli (non deve quindi contenere una descrizione a lettere del prodotto, o altri dati).
Dire quale tipo di file è migliore per rappresentare questi dati, tenendo presente che il numero di articoli viene aggiornato ogni volta che un prodotto viene venduto. Scrivere l'algoritmo e la funzione che aggiorna il file quando un articolo viene venduto (ossia il numero di articoli presenti per un certo prodotto va diminuito di uno).
Il punteggio massimo per questo esercizio sarà di 6 punti.
Soluzione
Il tipo di file viene deciso in base alle operazioni possibili e alla comodità di uso, mentre la dimensione del file è di solito un problema secondario. In particolare, i criteri di scelta sono:
In questo caso, abbiamo bisogno dei file binari per il semplice motivo che il dato che rappresenta il numero di articoli di un certo prodotto si trova (di solito) in mezzo al file, e quindi sono necessarie modifiche all'interno del file.
Mentre nei file di testo una modifica comporta la completa riscrittura del file, in quelli binari è sufficiente posizionarsi nel punto in cui si trova il dato da modificare e riscriverlo.
Nel nostro caso, si può quindi usare usare la seguente disposizione. Per ogni prodotto, si memorizzano due interi: il primo è il codice, il secondo il numero di articoli.
Per effettuare la modifica si procede nel seguente modo: si fa una scansione del file finchè non si trova il codice del prodotto. Si legge poi il numero di articoli presenti, si diminuisce di uno, e si scrive il nuovo numero. Da notare che il numero diminuito va scritto al posto del vecchio. Quindi, prima di riscriverlo, occorre posizionarsi indietro nel file.
leggi il file a coppie di interi
se il codice prodotto è quello da modificare
decrementa il numero prodotto
torna indietro nel file di sizeof(int)
scrivi il numero prodotto
Il codice (facoltativo) è quindi quello che segue:
while(1) {
res=fread(&codice, sizeof(int), 1, fd);
if(res!=1)
break;
res=fread(&numero, sizeof(int), 1, fd);
if(res!=1)
break;
if(codice=codice_da_cercare) {
numero++;
fseek(fd, -sizeof(int), SEEK_CUR);
fwrite(&numero, sizeof(int), 1, fd);
}
}
I punti fondamentali da dire per la soluzione di questo esercizio erano: si usano file binari perchè vanno modificati elementi in mezzo; per fare le modifiche occorre leggere il file fino a trovare l'elemento da modificare, tornare indietro con fseek e modificarlo.