Matrice Sparsa in C

Le matrici sparse sono matrici in cui la maggior parte degli elementi sono zero o vuoti. Rappresentarle in memoria utilizzando una struttura tradizionale come un array bidimensionale può risultare inefficiente in termini di memoria. Per questo motivo, si utilizzano tecniche specifiche per rappresentare le matrici sparse in modo da ottimizzare l’uso della memoria. In questa guida, esploreremo come implementare e gestire una matrice sparsa in C.

Cos’è una Matrice Sparsa?

Una matrice sparsa è una matrice in cui un numero significativo di elementi sono zero o privi di valore. La rappresentazione delle matrici sparse richiede solo di memorizzare i valori non zero e le loro posizioni, risparmiando così memoria rispetto a una rappresentazione tradizionale.

Esempio di Matrice Sparsa

Consideriamo una matrice 4x5 con la maggior parte degli elementi pari a zero:

	0	1	2	3	4
0	0	0	0	5	0
1	0	0	8	0	0
2	0	0	0	0	0
3	0	6	0	0	0

In una rappresentazione tradizionale, occorrerebbero 20 elementi per memorizzare la matrice, ma con una rappresentazione sparsa, possiamo memorizzare solo i valori non zero e le loro posizioni.

Rappresentazione di una Matrice Sparsa

Tripla (Valore, Riga, Colonna)

Uno dei metodi più comuni per rappresentare una matrice sparsa è utilizzare una lista di triple, dove ogni tripla contiene:

• Valore: Il valore non zero.
• Riga: L’indice della riga in cui si trova il valore.
• Colonna: L’indice della colonna in cui si trova il valore.

Definizione della Struttura

#include <stdio.h>
#include <stdlib.h>

struct ElementoSparso {
    int riga;
    int colonna;
    int valore;
};

struct MatriceSparsa {
    int righe;
    int colonne;
    int non_zero; // Numero di elementi non zero
    struct ElementoSparso* elementi;
};

Creazione di una Matrice Sparsa

Per creare una matrice sparsa, è necessario inizializzare la struttura e allocare la memoria per memorizzare i valori non zero.

struct MatriceSparsa* crea_matrice_sparsa(int righe, int colonne, int non_zero) {
    struct MatriceSparsa* matrice = (struct MatriceSparsa*)malloc(sizeof(struct MatriceSparsa));
    matrice->righe = righe;
    matrice->colonne = colonne;
    matrice->non_zero = non_zero;
    matrice->elementi = (struct ElementoSparso*)malloc(non_zero * sizeof(struct ElementoSparso));
    return matrice;
}

Inserimento di Elementi nella Matrice Sparsa

Gli elementi non zero possono essere inseriti nella struttura specificando la riga, la colonna e il valore.

void inserisci_elemento(struct MatriceSparsa* matrice, int indice, int riga, int colonna, int valore) {
    matrice->elementi[indice].riga = riga;
    matrice->elementi[indice].colonna = colonna;
    matrice->elementi[indice].valore = valore;
}

Stampa della Matrice Sparsa

Una funzione per stampare la matrice sparsa nel formato tradizionale.

void stampa_matrice_sparsa(struct MatriceSparsa* matrice) {
    int k = 0;
    for (int i = 0; i < matrice->righe; i++) {
        for (int j = 0; j < matrice->colonne; j++) {
            if (k < matrice->non_zero && matrice->elementi[k].riga == i && matrice->elementi[k].colonna == j) {
                printf("%d ", matrice->elementi[k].valore);
                k++;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}

Esempio Completo di Utilizzo

int main() {
    int righe = 4, colonne = 5, non_zero = 3;
    struct MatriceSparsa* matrice = crea_matrice_sparsa(righe, colonne, non_zero);

    inserisci_elemento(matrice, 0, 0, 3, 5);
    inserisci_elemento(matrice, 1, 1, 2, 8);
    inserisci_elemento(matrice, 2, 3, 1, 6);

    printf("Matrice Sparsa:\n");
    stampa_matrice_sparsa(matrice);

    free(matrice->elementi);
    free(matrice);

    return 0;
}

Uscita:

Matrice Sparsa:
0 0 0 5 0
0 0 8 0 0
0 0 0 0 0
0 6 0 0 0

Applicazioni delle Matrici Sparse

Le matrici sparse sono utilizzate in molte applicazioni pratiche, tra cui:

• Grafi Rappresentati come Matrici di Adiacenza: In cui solo una piccola parte dei nodi sono collegati tra loro.
• Analisi di Dati e Machine Learning: Per rappresentare grandi dataset in cui la maggior parte dei dati è mancante o zero.
• Simulazioni e Modellazioni: Per sistemi fisici in cui solo pochi elementi sono attivi in un dato momento.

Considerazioni sull’Uso delle Matrici Sparse

• Efficienza di Memoria: Le matrici sparse offrono un uso più efficiente della memoria quando la matrice contiene una grande quantità di zeri.
• Operazioni Matematiche: Le operazioni su matrici sparse, come la moltiplicazione, richiedono algoritmi specializzati per mantenere l’efficienza.
• Accesso ai Dati: L’accesso agli elementi di una matrice sparsa può essere più complesso rispetto a una matrice densa, richiedendo un’attenta gestione degli indici.

Conclusioni

Le matrici sparse in C sono una soluzione efficace per rappresentare e gestire grandi quantità di dati in cui la maggior parte degli elementi è zero. Comprendere come implementare e utilizzare queste strutture dati può portare a significativi risparmi di memoria e miglioramenti delle prestazioni in molte applicazioni reali. Con l’uso appropriato delle matrici sparse, è possibile gestire dataset complessi in modo efficiente e scalabile.