Liste 3 

52) Dato un insieme finito X, un multinsieme su X e' una funzione m: X->N 
che associa a ogni elemento di X la molteplicita' con cui compare 
nel multinsieme. Si vuole rappresentare un multinsieme m di caratteri 
come una lista contenente un nodo per ogni carattere che ha 
molteplicita' non nulla in m. Ogni nodo contiene un carattere e la sua 
molteplicita', oltre al puntatore al nodo successivo. 
N.B.: Si considerino diversi i caratteri minuscoli e maiuscoli. 

(a) Si definiscano i tipi di dati necessari per implementare in C la 
rappresentazione indicata. Si chiami MSet il tipo di dati principale.

Si definiscano quindi le seguenti funzioni o procedure C che operano su 
oggetti di tipo MSet, rispettando il prototipo proposto: 

(b) int mult (MSet m, char c);
Restituisce la molteplicita' del carattere c nel multinsieme m. Questa 
funzione deve essere definita in modo ricorsivo. 

(c) void insert (MSet *p, char c, int k);
Inserisce il carattere c con molteplicita' k nel multinsieme puntato da 
p. Quindi se il carattere era gia' presente in un nodo, ne aumenta la 
molteplicita' di k, altrimenti inserisce un nuovo nodo nella lista con 
il carattere c e con molteplicita' k. La procedura non modifica il 
multinsieme se k <=0. 

(d) void minus (MSet *m1, MSet m2);
Modifica il multinsieme m1 sottraendo m2, senza modificare m2. Dopo 
l'esecuzione della procedura, m1 sara' il multinsieme definito come 
(m1 - m2)(x) = m1(x)-m2(x)   se m2(x)>m1(x),  0 altrimenti

(e) MSet add (MSet m1, MSet m2);
Senza modificare i multinsiemi m1 e m2, questa funzione restituisce il 
multinsieme ottenuto come somma dei due argomenti, cioe' il multinsieme 
in cui ogni carattere c ha come molteplicita' la somma delle 
molteplicita' in m1 e m2. 


53) Il grafico di una funzione definita sugli interi e a valori reali e' 
rappresentato da una lista ordinata di punti, cioe' di record aventi tre 
campi: un intero x (ascissa), un double y (ordinata), e un campo next 
che punta al prossimo punto. Nel grafico i punti sono ordinati per 
ascissa crescente, e non ci possono essere due punti aventi la stessa 
ascissa. Se fun e' la funzione rappresentata dal grafico gr, la presenza 
del punto (x; y; p) in gr indica che fun(x) = y. 

(a) Si definiscano i tipi di dati necessari per implementare in C la 
rappresentazione indicata. Si chiami Grafico il tipo di dati principale. 

Si definiscano quindi le seguenti funzioni o procedure C che operano su 
oggetti di tipo Grafico, rispettando il prototipo proposto: 

(b) void update(Grafico * fun, int argx, double argy);
Aggiorna il grafico passato per argomento aggiungendo un punto con 
ascissa argx e ordinata argy. Se fun aveva gia' un punto con ascissa 
argx, ne viene solo modificato il campo y con il nuovo valore. 
Altrimenti si inserisce un nuovo punto nel grafico, preservando 
l'ordinamento. 

(c) double simpleEval(Grafico fun, int arg);
Restituisce il valore della funzione rappresentata da fun per 
l'argomento intero arg. Restituisce 0 se non esiste in fun un punto con 
ascissa arg. Questa funzione DEVE essere definita in modo ricorsivo. 

(d) double length(Grafico fun);
Restituisce la lunghezza del grafico, visto come una linea spezzata 
passante per i punti indicati. 

(e) double eval(Grafico fun, int arg);
Come simpleEval, ma considera la funzione definita su tutti gli interi 
compresi tra l'ascissa del primo punto e quella dell'ultimo. Quindi: 
 - Se arg cade fuori dall'intervallo indicato, restituisce 0.
 - Se fun ha un punto con ascissa x, restituisce la corrispondente ordinata.
 - Altrimenti restituisce il valore ottenuto interpolando linearmente i 
valori assunti dalla funzione per i valori immediatamente minore e 
immediatamente maggiore di arg. 
 
(f) Grafico saturate(Grafico fun);
Crea e restituisce un nuovo grafico ottenuto da quello passato per 
argomento "riempiendo i buchi", cioe' inserendo un punto per ogni valore 
delle ascisse compreso nell'intervallo di definizione della funzione per 
cui non esisteva, con il valore che si sarebbe ottenuto dalla funzione 
eval in quel punto. Il grafico restituito non deve avere alcun struct in 
comune con quello passato per argomento.