Testo
Scrivere una funzione che riceve come parametro una lista, e restituisce un intero che indica il numero di volte in cui l'elemento di maggiore valore nella lista compare nella lista stessa.
Per esempio, se la lista passata è 4 1 3 5 3 3 5 3 4, allora la funzione deve restituire 2, dal momento che l'elemento di valore massimo è 5, che compare due volte nella lista.
Valutazione per questo esercizio:
Driver e file di prova
Programma driver: 8gen03-driver.c La soluzione va inserita dove appare il commento /* inserire qui la soluzione */, e deve avere il prototipo:int OccorrenzeMassimo(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 8gen03-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) | 0 |
| lista1.txt | 3 |
| lista2.txt | 1 |
| lista3.txt | 1 |
| lista4.txt | 1 |
| lista5.txt | 2 |
| lista6.txt | 1 |
Soluzione
La soluzione dell'esercizio richiede il calcolo del massimo elemento della lista, e il conteggio del numero di occorrenze di queto elemento. Il problema si può quindi facilmente risolvere trovando il massimo e poi contando le sue occorrenze nella lista:
trova il massimo elemento della lista conta quante volte appare nella lista
Trovare il massimo elemento in una lista si fa usando la solita tecnica di scandire la lista, memorizzando il valore del massimo trovato fino a questo momento. All'inizio, il massimo valore trovato sarà il primo; per ogni nuovo elemento che viene considerato, se è maggiore del massimo allora il massimo va aggiornato.
massimo=primo elemento della lista
per ogni altro elemento della lista
se e' maggiore del massimo
aggiorna il massimo
La funzione C si ottiene semplicemente traducendo la frase per ogni altro elemento della lista in un ciclo di scansione, in cui si può partire dal secondo elemento della lista invece che dal primo.
int MassimoLista(TipoLista l) {
TipoLista s;
int m;
if(l==NULL) {
printf("Tentativo di trovare il massimo di una lista vuota\n");
exit(1);
}
m=l->val;
s=l->next;
while(s!=NULL) {
if(s->val > m)
m=s->val;
s=s->next;
}
return m;
}
In questa funzione, si è anche fatto il controllo sulla lista vuota. Si tenga presente, infatti, che il massimo di una lista vuota non ò definito, per cui effettuare la chiamata di questa funzione passando NULL è un errore. Si tenga però anche presente che questo vale per la funzione di calcolo del massimo e non, per esempio, per il calcolo della somma, ecc.
Per contare le occorrenze di un elemento in una lista, basta fare la scansione della lista stessa incrementando un contatore ogni volta che l'elemento corrente della lista risulta uguale a quello da cercare. Il contatore contiene sempre il numero di volte che l'elemento da cercare è stato finora incontrato nella scansione della lista, per cui il valore iniziale è zero, e aumenta di uno ogni volta che l'elemento viene incontrato nella lista.
contatore=0
per ogni elemento della lista
se coincide con quello da cercare
contatore++
La traduzione di questo algoritmo in C è ovvia. In questo caso, il passaggio della lista vuota non è un errore. In questo caso, infatti, basta ritornare il valore zero (l'elemento da cercare appare zero volte nella lista).
int ContaOccorrenze(TipoLista l, int e) {
TipoLista s;
int conta;
s=l;
conta=0;
while(s!=NULL) {
if(s->val==e)
conta++;
s=s->next;
}
return conta;
}
La funzione da realizzare consiste semplicemente nella chiamata di queste due funzioni: prima si trova il valore del massimo, e poi si calcola quante volte appare nella lista.
int OccorrenzeMassimo(TipoLista l) {
int m;
if(l==NULL)
return 0;
m=MassimoLista(l);
return ContaOccorrenze(l, m);
}
Testo
Dire in quali casi è possibile effettuare la visita in preordine di un albero rappresentato come vettore facendo una semplice scansione lineare del vettore. Dire perchè questo non è possibile in generale. Punteggio massimo per questo esercizio: 6 punti.
Soluzione
La visita in preordine consiste nell'effettuare una operazione su di un nodo, e poi nel procedere ricorsivamente nei due sottoalberi. Nel caso della rappresentazione di array come vettori, gli elementi sono disposti ``per livelli'' all'interno del vettore, per cui la scansione non produce l'ordine di visita voluto. Inoltre, non è possibile comunque effettuare una visita in questo modo, dal momento che alcuni elementi del vettore potrebbero non rappresentare nessun nodo dell'albero anche se il campo esiste vale true: infatti, se un nodo di un albero non esiste, i valori dell'array che corrispondono ai successori hanno valori non determinati.
Nel caso della scansione in preordine, la scansione produce lo stesso ordine della visita in preordine quando l'albero ha, al massimo, la radice e i due figli. Nel caso in cui l'albero sia composto solo da radice-figlio-nipote, la scansione non funziona necessariamente per via del problema sul campo esiste.
Testo
Spiegare cosa fa la funzione riportata qui sotto. In altre parole, se si fa: cosafa(l) e poi si stampa la lista l, cosa viene stampato?
void cosafa(TipoLista l) {
if(l==NULL) {
l=malloc(sizeof(struct NodoLista));
l->val=10;
l->next=NULL;
}
while(l!=NULL) {
l->val=10;
l=l->next;
}
}
Il punteggio massimo per questo esercizio sarà di 6 punti.
Soluzione
Gli elementi della lista diventano tutti pari a 10
Motivazione (si tenga presente che risposte non motivate non vengono prese in considerazione in fase di correzione): quando si passa il valore di una variabile a una funzione, questo valore viene copiato nel parametro formale, che è una variabile visibile solo nella funzione. Eventuali modifiche a questa variabile non hanno quindi effetto nel programma/funzione che ha chiamato questa funzione.
Quindi, anche se la lista è vuota, l'operazione di creazione di un record con l=malloc(...) ecc. si limita a creare una struttura il cui indirizzo viene messo in l, che però è una variabile che viene distrutta quando si dealloca il record di attivazione di questa funzione. Quindi, questa modifica non ha effetti nel programma/funzione che ha chiamato questa funzione: se la lista con cui la funzione è stata chiamata è vuota, rimane vuota.
Nel caso in cui la lista non è vuota, si effettua un ciclo di scansione della lista, mettendo 10 in tutti gli elementi. Queste modifiche non vengono fatte al parametro formale l: sono modifiche che vengono fatte alla zona di memoria il cui indirizzo sta in l e a tutte le successive. Dal momento che l contiene lo stesso valore che contiene la lista su cui è stata chiamata la funzione, le modifiche risulteranno visibili all'esterno della funzione.
La risposta corretta è quindi: passando la lista vuota, questa lista non viene modificata (la stampa della lista passata non produce nessuna stampa); passando un lista non vuota, tutti i suoi elementi diventano 10