Consideriamo il problema di leggere da standard input una sequenza di valori reali terminata da 0.0 creando la lista corrispondente di tipo

typedef struct lista_d {
  double val;
  struct lista_d * next;
} lista_d_t ; 

• sviluppare un programma C che legge un singolo elemento dallo standard input usando una funzione

double leggi_nuovo_valore(void);

e utilizza le funzioni

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);

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.

Implementare le seguenti funzioni in modo iterativo e ricorsivo:

/** 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);

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

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.

Realizzare le funzioni dell'esercizio 1 utilizzando liste con puntatore al precedente e al successivo

typedef struct elem_d {
  double val;
  struct elem_d * prec;
  struct elem_d * next;
} elem_d_t ; 

in questo caso la lista complessiva puo' essere definita ad esempio come una struttura con due puntatori, uno alla testa ed uno alla coda

typedef struct lista_d {
  struct elem_d * head;
  struct elem_d * tail;
} lista_d_t ;

come si modificano gli algoritmi sviluppati precedentemente ?

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

typedef struct sparse_d {
  double val;
  unsigned index;
  struct elem_d * next;
} sparse_d_t ; 

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':

double put (sparse_d_T * a, unsigned indice);
sparse_d_t * put (sparse_d_T * a, double x, unsigned indice);