Esercizio Una matrice di interi sparsa e' una matrice in cui la maggior parte degli elementi ha valore zero. La memorizzazione di queste matrici con il metodo classico, cioe' come matrici di interi, non e' conveniente dal punto di vista della memoria utilizzata. Lo scopo di questo esercizio e' fornire una implementazione che permetta di memorizzare in modo efficiente matrici di interi sparse e di effettuare alcune operazioni su di esse. Si definisce la seguente struttura dati rappresentante una matrice sparsa: typedef struct sparse_matrix{ int row; int col; int_elem_list ** matrix; }sparse_matrix; Dove row e' il numero di righe, col e' il numero di colonne, e matrix e' un vettore di puntatori ad elementi di tipo int_elem_list, definiti come segue: typedef struct int_elem_list { int key; int pos; struct int_elem_list *next; } int_elem_list; Il vettore matrix ha lunghezza pari a row, l'i-esimo elemento di matrix punta ad una lista contenente gli elementi con valore diverso da zero contenuti nella i-esima riga della matrice. Tale lista e' costituita da strutture di tipo int_elem_list, dove il campo key contiene il valore dell'elemento della matrice mentre il campo pos la sua posizione nella riga i-esima. Il valore di pos e' compreso tra 0 e col-1, ed ovviamente per ogni valore di pos puo' essereci al piu' un elemento nella lista. Si memorizzano quindi nella matrice solamente gli elementi con valore diverso da zero, inserendoli nella riga opportuna e ricordando la loro colonna attraverso il campo pos della struttura int_elem_list. Si devono implementare le seguenti funzioni: 1) sparse_matrix * init_sparse_matrix(int n, int m) La funzione deve allocare la memoria per la struttura dati sparse_matrix, impostare il campo row pari ad n e col pari m, allocare il vettore matrix di lunghezza pari a row ad inizializzare tutti i puntatori a NULL. La funzione restituisce la struttura allocata. 2) void insert(sparse_matrix * sm, int i, int j, int key) La funzione deve inserire l'elemento con valore key in posizione [i,j] della matrice. Notare che si possono verificare quattro casi: 2.1) key != 0 e l'elemento in posizione j non e' presente nella lista: si deve creare un nuovo elemento di tipo int_elem_list ed inserirlo nella lista puntata da matrix[i]. 2.2) key != 0 e l'elemento in posizione j e' presente nella lista: si deve solo aggiornare il valore dell'elemento 2.3) key = 0 e l'elemento e' presente nella lista: si deve rimuovere tale elemento dalla lista. 2.3) key = 0 e l'elemento non e' presente nella lista: non si deve far nulla. 3) int * get_row(sparse_matrix * sm, int i) Restituisce un vettore A di interi di dimensione sm->col t.c. A[j] sia pari al valore dell'elemento in posizione [i,j] della matrice. 4) int * get_col(sparse_matrix * sm, int j) Restituisce un vettore A di interi di dimensione sm->row t.c. A[i] sia pari al valore dell'elemento in posizione [i,j] della matrice. 5) sparse_matrix * transpose(sparse_matrix *sm) Restituisce una nuova matrice sparsa pari alla trasposta della matrice sm. La funzione quindi deve inizializzare una nuova matrice sparsa, inserire gli elementi in modo opportuno e ritornare la matrice trasposta. 6) void free_sparse_matrix(sparse_matrix *sm) La funzione dealloca tutta la struttura sm, quindi: per ogni riga i dealloca tutti gli elementi della lista puntata da sm->matrix[i], dealloca poi il vettore matrix ed in fine dealloca la struttura sm. Il main prende in input tre valori: a, n ed m e successivamente una lista di terne del tipo val i j. Il valore a e' utilizzato per testare le diverse parti del programma, come spiegato piu' avanti. I valori n ed m rappresentano il numero di righe e di colonne della matrice sparsa. Le terne di valori val i j indicano che si deve inserire in posizione [i][j] della matrice il valore val chiamando la funzione insert(). Si acquisiscono valori finche' non si introduce una terna dove il valore di val e' negativo (la matrice conterra' quindi solo valori positivi per come e' scritto il main). L'homework e' suddiviso in tre parti. Nella prima parte (a = 1) si testeranno solamente le funzioni init_sparse_matrix() e insert(). Nella seconda parte si verificheranno le funzioni get_row() e get_col(). Nella terza parte le funzioni traspose() e free_sparse_matrix(). Si deve comunque consegnare un unico file con estensione .1.c. La correzione verra' poi effettuata come se si trattasse di esercizi distinti. Lo scheletro del programma e' disponibile QUI. Esempio (a = 1) Si inseriscono i valori: 1 5 6 1 1 1 3 2 1 4 0 0 5 1 1 0 2 1 9 2 2 3 4 4 5 4 5 2 1 3 9 2 4 7 1 4 -1 0 0 Il programma deve inizializzare la matrice sparsa di dimensione 5x6 ed inserire i valori. Notare che in questo esempio: - Si sovrascrivono alcuni elementi: l'elemento 1 1 1 (valore 1 in posizione [1,1]), viene sostituito da 5 1 1 (valore 5 in posizione [1,1]) - Si eliminano alcuni elementi: dopo l'inserimento di 3 2 1 (valore 3 in posizione [2,1]), si inserisce 0 2 1 (valore 0 in posizione [2,1]). Siccome gli elementi con valore zero non sono salvati nella matrice, questo corrisponde all'eliminazione dell'elemento con val = 3 e pos = 1 nella lista sm->matrix[2]. Il main stampa prima la matrice inizializzata, che non contiene nessun elemento: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 E successivamente la matrice con gli elementi inseriti: 4 0 0 0 0 0 0 5 0 2 7 0 0 0 9 0 9 0 0 0 0 0 0 0 0 0 0 0 3 5 Esempio (a = 2) Si inseriscono i valori: 2 5 6 1 1 1 3 2 1 4 0 0 5 1 1 0 2 1 9 2 2 3 4 4 5 4 5 2 1 3 9 2 4 7 1 4 -1 0 0 Il main ottiene i vettori rappresentati le righe della matrice con la funzione get_row e li stampa. 4 0 0 0 0 0 0 5 0 2 7 0 0 0 9 0 9 0 0 0 0 0 0 0 0 0 0 0 3 5 Successivamente, il main ottiene i vettori rappresentanti le colonne della matrice e li stampa. 4 0 0 0 0 0 5 0 0 0 0 0 9 0 0 0 2 0 0 0 0 7 9 0 3 0 0 0 0 5 Esempio (a = 3) Si inseriscono i valori: 3 5 6 1 1 1 3 2 1 4 0 0 5 1 1 0 2 1 9 2 2 3 4 4 5 4 5 2 1 3 9 2 4 7 1 4 -1 0 0 Il main calcola la matrice trasposta attraverso la funzione transpose() e la stampa. 4 0 0 0 0 0 5 0 0 0 0 0 9 0 0 0 2 0 0 0 0 7 9 0 3 0 0 0 0 5 Successivamente, dealloca tutta la struttura rappresentante la matrice sparsa. Tale operazione non genera stampe, ma se male effettuata puo' causare segmentation fault che saranno rilevati durante la correzione.