Testo
Scrivere una funzione che ha come parametro una lista e restituisce un intero che indica la posizione della lista in cui appare per la prima volta un elemento uguale all'ultimo.
Per esempio, se la lista è 3 9 2 4 2 3 5 2 2 allora la funzione deve restituire 3, dal momento che l'ultimo elemento della lista è 2, e la prima posizione in cui appare il 2 è la terza.
Valutazione per questo esercizio:
Driver e file di prova
Programma driver: 9lug02-driver.c La soluzione va inserita dove appare il commento /* inserire qui la soluzione */, e deve avere il prototipo:
int PrimaPosizioneUltimo(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 9lug02-driver nomefile, mentre dal TurboC si può impostare il nome del file 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) | 0 |
| lista1.txt | 1 |
| lista2.txt | 1 |
| lista3.txt | 6 |
| lista4.txt | 1 |
| lista5.txt | 2 |
| lista6.txt | 4 |
Soluzione
La soluzione di questo esercizio richiede esplicitamente di costruire l'algoritmo in raffinamenti successivi. In ogni caso, questa operazione è suggerita, perchè in genere consente di ottenere l'algoritmo più semplice, e al tempo stesso costituisce una documentazione della soluzione. La parte due (spiegazione a parole) è una spiegazione degli algoritmi e del codice. Quanto scritto qui sotto è un possibile esempio di spiegazione a parole della soluzione.
L'esercizio richiede di trovare la posizione del primo elemento che coincide con l'ultimo. Possiamo quindi pensare di scomporre l'algoritmo in due parti.
trova il valore dell'ultimo elemento trova la posizione in cui questo elemento appare
Quello riportato qui sopra è il primo livello di raffinamento dell'algoritmo. A questo manca ancora la considerazione del caso particolare di lista vuota (in questo caso, va restituito il valore 0). Va quindi aggiunto un if iniziale.
Per quello che riguarda lo sviluppo dei due punti (trovare l'ultimo elemento e trovare la posizione di un elemento in una lista), possiamo pensare di sviluppare entrambe la parti all'interno di una sola funzione, oppure di realizzare una funzione per ognuna di esse. In questo caso, entrambi i passi consistono nella realizzazione di una funzionalità ben precisa, per cui è opportuno realizzare una funzione separata per ognuna delle due fasi. Si ricordi che una regola empirica per capire quando è bene fare una funzione è:
se si riesce a descrivere ciò che una parte di codice fa in poche parole, allora è opportuno realizzare una funzione
Nel nostro caso, la prima parte dell'algoritmo consiste nel ``trovare l'ultimo elemento di una lista''. A parte il fatto che questa funzione è già nota, la sua semplice descrizione ci fa capire che è opportuno realizzare una funzione. La seconda parte si descrive come ``trovare la prima posizione in cui appare un elemento''. La semplicità della descrizione fa capire che è bene realizzare una funzione.
Iniziamo quindi a sviluppare la prima funzione. In questo caso, il successivo livello di raffinamento dell'algoritmo coincide quasi con il codice finale: per trovare l'ultimo elemento di una lista, si fa una scansione fino alla fine.
scansione della lista fino all'ultimo elemento restituzione ultimo elemento
La scansione della lista fino all'ultimo elemento è stata già vista, e consiste nel portare avanti un puntatore finchè il campo next della struttura puntata non vale NULL (si vedano le pagine sulle liste). Abbiamo quindi il seguente codice finale:
int UltimoLista(TipoLista l) {
while(l->next != NULL)
l=l->next;
return l->val;
}
Si tenga presente che la funzione va in errore se la lista è vuota. Prima di chiamare questa funzione, quindi, è necessario controllare che la lista passata non sia vuota.
Passiamo ora alla seconda funzione ausiliaria, ossia quella in cui si trova la prima posizione in cui un elemento appare. È opportuno relizzare la funzione in base alla sua specifica, e non in base all'uso che ne facciamo. In questo caso, la funzione deve trovare la prima occorrenza di un elemento, quindi possiamo anche pensare che l'elemento non sia presente, anche se nel caso specifico in cui usiamo questa funzione questo caso non si può presentare. L'algoritmo risolutivo è il seguente: inizializziamo un contatore; per ogni elemento della lista, se è quello da trovare ritorniamo il contatore, altrimenti lo aumentiamo di uno. Se alla fine non si è trovato l'elemento, possiamo ritornare 0 oppure -1 per indicare che l'elemento non è stato trovato.
contatore=1;
per ogni elemento della lista {
se è quello da cercare
return contatore
contatore++
}
return -1
Il codice finale si ottiene semplicemente convertendo la frase ``per ogni elemento della lista'' in una scansione lineare della lista.
int PrimaPosizioneElemento(TipoLista l, int e) {
int cont=1;
while(l!=NULL) {
if(l->val==e)
return cont;
cont++;
l=l->next;
}
return -1;
}
La funzione complessiva consiste nella chiamata di queste due funzioni, preceduta dal controllo di lista vuota.
int PrimaPosizioneUltimo(TipoLista l) {
int ultimo;
if(l==NULL)
return 0;
ultimo=UltimoLista(l);
return PrimaPosizioneElemento(l, ultimo);
}
Si può facilmente verificare che la funzione è corretta anche nei casi limite (lista di un solo elemento, lista in cui l'ultimo elemento appare per la prima volta in prima posizione, lista in cui l'ultimo elemento appare solo in ultima posizione).
Testo
Un albero di interi viene memorizzato in un file binario, usando lo stesso metodo che si usa per rappresentare gli alberi con vettori.
Soluzione
Le prime due parti consistono nella descrizione di argomenti svolti a lezione (i file binari sono anche descritti nelle pagine web sui file binari).
La terza parte richede di capire in che modo gli interi e i booleani sono rappresentati su file binario. L'idea è che, sul file, abbiamo gli stessi dati che andrebbero messi nel vettore. Possiamo quindi mettere nel file, sequenzialmente, le strutture che starebbero nel vettore. In alternativa, possiamo memorizzare nel file prima l'intero e poi il booelano, poi il secondo intero e il secondo booleano, ecc.
Consideriamo quindi questa seconda soluzione: il file contiene gli stessi elementi del vettore, nello stesso ordine; l'unica differenza è che il file binario è un file ``piatto'', con la sequenza intero-booleano-intero-booleano- invece delle strutture. A parte questo, l'ordine è lo stesso.
Per quello che riguarda la visita: l'algoritmo di visita, quello indipendente dalla rappresentazione, è il seguente:
visita(albero) {
se l'albero è vuoto
termina la visita
analizza radice
visita(sottoalbero sinistro)
visita(sottoalbero destro)
}
Si noti che l'uso di espressioni come a->sinistro e a->destro è errato per due motivi: primo, siamo a un livello di raffinamento dell'algoritmo in cui non abbiamo ancora specificato la rappresentazione dei dati; secondo, stiamo usando una rappresentazione degli alberi in cui non usiamo le strutture (quindi i campi sinistro e destro non esistono.
La visita di un albero rappresentato come vettore si fa passando la posizione dell'elemento da visitare (radice del sottoalbero da visitare). Nel nostro caso facciamo lo stesso, ossia aggiungiamo un argomento che indica il numero d'ordine dell'elemento da visitare.
visita(albero, pos) {
se l'albero è vuoto
termina la visita
analizza elemento pos
visita(albero, 2*pos+1)
visita(albero, 2*pos+2)
}
L'unico problema che rimane, a questo punto, è come trovare l'elemento di indice pos. Questo si ottiene facilmente dalla considerazione che ogni nodo, che nel vettore occupa una posizione, sul file binario occupa 2*sizeof(int) byte, dato che abbiamo un intero più un booleano (che viene sempre rappresentato come intero). Per questa ragione, l'elemento in posizione pos, che nel vettore era semplicemente a[pos], si ottiene ora facendo una fseek in posizione pos*2*sizeof(int) seguita da una fread di un intero. Una successiva fread legge il campo booleano.
La minima risposta che era necessario dare per questo esercizio era la seguente: sul file binario si memorizza la sequenza intero-booleano-intero-booleano- nello stesso ordine in cui questi elementi starebbero in un vettore; la funzione ricorsiva di visita prende come parametro l'indice dell'elemento da visitare, come per i vettori; dato questo indice pos, l'intero e il booleano stanno nel file binario in posizione pos*2*sizeof(int), e si possono quindi leggere facendo prima una fseek e poi due fread.