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

===== Esercizio 1: Sequenze di double (discusso a lezione) =====
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>
e utilizza le funzioni 
<code>
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>
per inserire nella lista. La scelta del tipo di inserizione viene richiesta all'utente una volta per tutte prima di inserire i valoro.
Inoltre, si utilizza una funzione ''stampa_lista()'' per stampare la lista inserita prima di terminare.



===== Esercizio 2: 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 3: Verifica di proprietà su liste (ricorsivamente)  =====
Definire una funzione ricorsiva che verifica che per ogni elemento di una lista valga la proprietà
\[
l(i + 1) = 2*l(i)
\]
dove $l(i)$ indica l'i-esimo elemento della lista a partire dalla testa. La funzione restituisce ''true'' se la proprietà è verificata e ''false'' altrimenti. I valori booleani sono definiti con un opportuno tipo enumerato.

===== Esercizio 4: Liste con doppio puntatore  =====
Realizzare le funzioni dell'esercizio 1 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 complessiva puo' essere definita ad esempio come 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: (avanzato) 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>