【数据结构C/C++】稀疏矩阵的压缩

什么是稀疏矩阵？

稀疏矩阵（Sparse Matrix）是一种矩阵，其中大多数元素都是零。与稠密矩阵相比，稀疏矩阵具有许多零元素，因此存储和处理它们可能会浪费大量的存储空间和计算资源。

为了优化稀疏矩阵的存储和处理，可以采用以下方法：

压缩存储：

1. 压缩稀疏矩阵（Compressed Sparse Matrix）：只存储非零元素及其位置信息，以减少存储空间的使用。通常需要存储非零元素的值、行索引和列索引。
   利用稀疏矩阵的特殊结构：如果稀疏矩阵具有特殊结构（如对角矩阵、三角矩阵、带状矩阵等），可以采用专门的存储方式，只存储非零元素及其特殊结构的相关信息，以进一步减少存储空间。
   稀疏矩阵算法：

2. 针对稀疏矩阵的特殊算法：一些算法可以针对稀疏矩阵的特性进行优化，以减少计算复杂度。
   避免对零元素进行不必要的操作：在处理稀疏矩阵时，可以跳过零元素，只处理非零元素，以节省计算资源。

3. 数据结构选择：
   使用适当的数据结构：选择合适的数据结构来表示稀疏矩阵，以便有效地存储和操作。常见的数据结构包括压缩行存储（Compressed Row Storage，CSR）、压缩列存储（Compressed Column Storage，CSC）等。

这里我是用的是第一种方法，也就是遍历稀疏数组，得到所有数据为1的索引，然后进行记录，存放到一个数组，然后将当前数组写入到文件即可。

使用C语实现对稀疏矩阵的压缩

#include 
#include 

// 定义稀疏数组结构
typedef struct {
    int row;
    int col;
    int val;
} SparseArray;

int main() {
    const int ROW = 5;
    const int COL = 5;
    int chess[ROW][COL];
    int sum = 0;

    // 初始化棋盘
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            chess[i][j] = 0;
        }
    }

    // 添加非零元素
    chess[1][2] = 1;
    chess[2][3] = 1;

    // 打印棋盘
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%5d", chess[i][j]);
            if (chess[i][j] != 0) {
                sum++;
            }
        }
        printf("\n");
    }

    // 创建稀疏数组
    SparseArray *sparseArr = (SparseArray *)malloc(sizeof(SparseArray) * (sum + 1));
    sparseArr[0].row = ROW;
    sparseArr[0].col = COL;
    sparseArr[0].val = sum;

    int index = 1;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (chess[i][j] != 0) {
                sparseArr[index].row = i;
                sparseArr[index].col = j;
                sparseArr[index].val = chess[i][j];
                index++;
            }
        }
    }

    // 将稀疏数组写入文件
    FILE *file = fopen("sparse_array.txt", "w");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    for (int i = 0; i <= sum; i++) {
        fprintf(file, "%d %d %d\n", sparseArr[i].row, sparseArr[i].col, sparseArr[i].val);
    }

    fclose(file);

    // 从文件中读取稀疏数组
    file = fopen("sparse_array.txt", "r");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    int numRows, numCols, numVals;
    fscanf(file, "%d %d %d", &numRows, &numCols, &numVals);
    SparseArray *readSparseArr = (SparseArray *)malloc(sizeof(SparseArray) * (numVals + 1));
    readSparseArr[0].row = numRows;
    readSparseArr[0].col = numCols;
    readSparseArr[0].val = numVals;

    for (int i = 1; i <= numVals; i++) {
        fscanf(file, "%d %d %d", &readSparseArr[i].row, &readSparseArr[i].col, &readSparseArr[i].val);
    }

    fclose(file);

    // 打印从文件中读取的稀疏数组
    printf("Sparse Array from File:\n");
    for (int i = 0; i <= numVals; i++) {
        printf("%d %d %d\n", readSparseArr[i].row, readSparseArr[i].col, readSparseArr[i].val);
    }

    free(sparseArr);
    free(readSparseArr);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。