====== Esercizi liste ======

===== Esercizio 1: Sequenze di double =====
Consideriamo il problema di leggere da standard input una sequenza di valori reali terminata da 0.0 creando la lista corrispondente di tipo
<code c>
typedef struct lista_d {
  double val;
  struct lista_d * next;
} lista_d_t ; 
</code>
  * sviluppare un programma C che legge un singolo elemento dallo standard input usando una funzione
<code c>
double leggi_nuovo_valore(void);
</code>
dopo aver letto un nuovo valore il programma lo inserisce in testa alla lista. Quando la sequenza e' terminata il programma stampa la lista risultante sullo standard output
    * Modificare il precedente programma in modo da inserire ogni nuovo valore in coda alla lista stampando la lista risultante sullo standard output


===== Esercizio 2: Funzioni di inserzione su liste di double =====
Consideriamo le funzioni
<code c>
lista_d_t * inserisci_testa ( lista_d_t * l, double v);
lista_d_t * inserisci_coda ( lista_d_t * l, double v);
lista_d_t * inserisci_ord ( lista_d_t * l, double v);
</code>
discusse nella lezione sulle liste.
  * implementare le funzioni in modo iterativo sviluppando un programma main le utilizza per leggere una lista dallo standard input e stamparla ordinata sullo standard output
  * implementare le funzioni in modo ricorsivo e verificare che il main sviluppato nel punto precedente continui a funzionare corerttamente

===== Esercizio 3: Altre funzioni su liste di double =====
Implementare le seguenti funzioni in modo iterativo e ricorsivo:
<code c>
/** calcola e restituisce il massimo della lista l */
double max ( lista_d_t * l);
/** calcola e restituisce la somma di tutti gli elementi della lista l*/
double somma ( lista_d_t * l);
/** libera la memoria occupata dalla lista */
void free_list( lista_d_t * l);
/** cancella, se presente, l'elemento che contiene la prima occorrenza 
del valore v dalla lista l (liberando la memoria) 
e restituisce la nuova lista */
lista_d_t * cancella_uno ( lista_d_t * l, double v);
/** cancella tutti gli elementi di valore
del valore v dalla lista l (liberando la memoria) 
e restituisce la nuova lista */
lista_d_t * cancella_tutti ( lista_d_t * l, double v);
</code>

e sviluppare un main() che ne testa il funzionamento.

===== Esercizio 4: Liste con doppio puntatore  =====
Realissare le funzioni degli esercizi precedenti utilizzando liste con puntatore al precedente e al successivo
<code>
typedef struct elem_d {
  double val;
  struct elem_d * prec;
  struct elem_d * next;
} elem_d_t ; 
</code>
in questo caso la lista puo' essere definita ad esempiocome una struttura con due puntatori, uno alla testa ed uno alla coda 
<code>
typedef struct lista_d {
  struct elem_d * head;
  struct elem_d * tail;
} lista_d_t ;
</code>
come si modificano gli algoritmi sviluppati precedentemente ?

===== Esercizio 5: Array sparsi (//a la Python//) implementati come liste  =====
Vogliamo realizzare degli array di double di grandi dimensioni che contengono solo una piccola percentuale di elementi diversi da 0 come liste concatenate definite come
<code>
typedef struct sparse_d {
  double val;
  unsigned index;
  struct elem_d * next;
} sparse_d_t ; 
</code>
nella lista sono presenti solo gli elementi diversi da zero e per ogni elemento e' indicato l'indice a cui corrisponde. La Lista e' mantenuta ordinata rispetto al campo indice.
Realizzare le funzioni ''put'' e ''get'' che permettono di leggere il valore dell'elemento di un certo indice ''i'' (''get'') e di modificarne il valore (''put''), un possibile prototipo per queste funzioni e':
<code>
double put (sparse_d_T * a, unsigned indice);
sparse_d_t * put (sparse_d_T * a, double x, unsigned indice);
</code>

===== Esercizio 6: (avanzato) Verificare i memory leak con ''mtrace'' (solo per chi ha mcheck.h/mtrace già installato) =====
Con riferimento al main sviluppato per l'esercizio precedente verificare che tutta la memoria allocata venga deallocata prima dell'uscita dal main().

Per la verifica si utilizzi la funzione ''mtrace'' e l'utility ''mtrace'', questi strumenti tracciano le azioni di allocazione e deallocazione di memoria compiute dal programma per verificare la presenza di //memory leak// cioe' memoria non deallocata. 

Per fare questo procedere come segue:
  * leggere le informazioni in ''man 3 mtrace''
  * includere l'header ''mcheck.h''
  * inserire la chiamata alla funzione di libreria mtrace() all'inizio della parte del programma C che vogliamo verificare
  * inserire la chiamata alla funzione di libreria muntrace() alla fine della parte del programma C che vogliamo verificare
  * compilare il file da verificare con opzione ''-g'' per includere le informazioni di debugging. Ad esempio se il mio file si chiama ''main.c'' posso compilare con
<code bash>
bash$ gcc -Wall -pedantic -g -o prova main.c 
</code>
  * settare la variabile di ambiente ''MALLOC_TRACE'' al path del file in cui vogliamo che la ''mtrace()'' registri le informazioni sugli accessi di memoria. Ad esempio se voglio registrare le informazioni nel file ''./mtrace.out'' devo usare il comando
<code bash>
bash$ export MALLOC_TRACE=./mtrace.out
</code>
  * eseguire, nel nostro esempio con:
<code bash>
bash$ ./prova
</code>
  * dopo l'esecuzione nel file ''./mtrace.out'' sono registrati gli accessi in formato testuale non facilmente comprensibile. Interpretarlo con l'utility mtrace. Ad esempio sempre riferendosi al nostro esempio invocare
<code bash>
bash$ mtrace ./prova ./mtrace.out 
</code>
questo rispondera' ''No memory leaks'' se tutta la memoria e' stata deallocata o fornira' indicazioni su dove e' stata allocata la mamoria rimasta da deallocare.

===== Esercizio 7: (avanzato) verificare gli accessi in memoria: valgrind =====

Verificare la correttezza degli accessi ai puntatori dello heap compiuti dalle funzioni su liste sviluppate negli esercizi precedenti utilizzando ''valgrind''. 
Questo strumento permette fra l'altro di capire se tutte le variabili sono inizializzate prima del loro uso, se accediamo a memoria gia' deallocata o mai allocata e situazioni similari


Per fare questo procedere come segue:  
  * compilare il file da verificare con opzione ''-g'' per includere le informazioni di debugging. Ad esempio se il mio file si chiama ''main.c'' posso compilare con
<code bash>
bash$ gcc -Wall -pedantic -g -o prova main.c
</code>
  * eseguire
<code bash>
bash$ valgrind ./prova
</code>
in questo modo, a schermo verranno riportare le infrazioni rilevate. Ad esempio, //invalid read// o //invalid write// sono accessi in lettura o scrittura a memoria non allocata o gia' deallocata.

''valgrind'' contiene moltissime opzioni, invitiamo gli studenti interessati ad esplorarle partendo dal[[http://valgrind.org/|sito]].