Sparse Matrix (เมทริกซ์ละลาย) ในภาษา C

ตัวอย่าง

3×3 Matrix:
1  0  0
0  2  0
0  0  0

Zeros = 7/9 > 50% → Sparse Matrix

การจัดเก็บ Sparse Matrix (Space Efficient)

แทนที่จะเก็บทั้งเมทริกซ์ เก็บแค่ Non-Zero Elements:

// Format: (Row, Col, Value)
(0, 0, 1)
(1, 1, 2)

โครงสร้างข้อมูลแนะนำ

typedef struct {
    int row;
    int col;
    int value;
} Element;

typedef struct {
    int rows;
    int cols;
    int count;      // จำนวน non-zero
    Element *data;  // Dynamic Array
} SparseMatrix;

ตัวอย่างโปรแกรม: ตรวจสอบ Sparse Matrix

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

int main() {
    int rows, cols;
    int matrix[10][10];
    int zeroCount = 0;
    
    printf("Enter rows: ");
    scanf("%d", &rows);
    printf("Enter cols: ");
    scanf("%d", &cols);
    
    printf("Enter matrix elements:\n");
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            scanf("%d", &matrix[i][j]);
            if(matrix[i][j] == 0) zeroCount++;
        }
    }
    
    printf("\nMatrix:\n");
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++)
            printf("%d\t", matrix[i][j]);
        printf("\n");
    }
    
    int total = rows * cols;
    printf("\nTotal elements: %d\n", total);
    printf("Zero count: %d\n", zeroCount);
    printf("Non-zero count: %d\n", total - zeroCount);
    
    if(zeroCount > total / 2)
        printf("→ This is a SPARSE MATRIX\n");
    else
        printf("→ This is a DENSE MATRIX\n");
    
    return 0;
}

ผลลัพธ์

Run 1:
Enter rows: 3
Enter cols: 2
Enter matrix elements:
1 0
2 0
2 0
Matrix:
1       0
2       0
2       0
Total elements: 6
Zero count: 3
Non-zero count: 3
→ This is a DENSE MATRIX (3 not > 3)

Run 2:
Enter rows: 3
Enter cols: 2
Enter matrix elements:
1 0
0 0
0 0
Matrix:
1       0
0       0
0       0
Total elements: 6
Zero count: 5
Non-zero count: 1
→ This is a SPARSE MATRIX (5 > 3)

การดำเนินการกับ Sparse Matrix

การบวก (Addition)

Merge สอง List ของ Non-Zero Elements (คล้าย Merge Arrays)

การคูณ (Multiplication)

ใช้ Transpose ของ Matrix ตัวที่ 2 เพื่อเข้าถึง Column ได้เร็ว

ตัวอย่าง: โครงสร้าง Sparse Matrix แบบสมบูรณ์

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

typedef struct {
    int row, col, val;
} Triple;

typedef struct {
    int rows, cols, terms;
    Triple *data;
} SparseMatrix;

SparseMatrix* createSparse(int rows, int cols, int maxTerms) {
    SparseMatrix *sm = malloc(sizeof(SparseMatrix));
    sm->rows = rows;
    sm->cols = cols;
    sm->terms = 0;
    sm->data = malloc(maxTerms * sizeof(Triple));
    return sm;
}

void insert(SparseMatrix *sm, int r, int c, int v) {
    if(v != 0 && sm->terms < 100) {
        sm->data[sm->terms++] = (Triple){r, c, v};
    }
}

void printSparse(SparseMatrix *sm) {
    printf("Rows: %d, Cols: %d, Non-zero: %d\n", sm->rows, sm->cols, sm->terms);
    printf("Row\tCol\tVal\n");
    for(int i = 0; i < sm->terms; i++)
        printf("%d\t%d\t%d\n", sm->data[i].row, sm->data[i].col, sm->data[i].val);
}

int main() {
    SparseMatrix *sm = createSparse(4, 4, 10);
    insert(sm, 0, 0, 5);
    insert(sm, 1, 2, 8);
    insert(sm, 3, 3, 2);
    printSparse(sm);
    free(sm->data);
    free(sm);
    return 0;
}

ผลลัพธ์

Rows: 4, Cols: 4, Non-zero: 3
Row Col Val
0   0   5
1   2   8
3   3   2