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

小咪咪 2024-02-23 07:32 20阅读 0赞

#### 文章目录 ####

*  什么是稀疏矩阵？
 *  使用C语实现对稀疏矩阵的压缩
 *  408考研各数据结构C/C++代码（Continually updating）

## 什么是稀疏矩阵？ ##

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

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

压缩存储：

1.  压缩稀疏矩阵（Compressed Sparse Matrix）：只存储非零元素及其位置信息，以减少存储空间的使用。通常需要存储非零元素的值、行索引和列索引。  
    利用稀疏矩阵的特殊结构：如果稀疏矩阵具有特殊结构（如对角矩阵、三角矩阵、带状矩阵等），可以采用专门的存储方式，只存储非零元素及其特殊结构的相关信息，以进一步减少存储空间。  
    稀疏矩阵算法：
2.  针对稀疏矩阵的特殊算法：一些算法可以针对稀疏矩阵的特性进行优化，以减少计算复杂度。  
    避免对零元素进行不必要的操作：在处理稀疏矩阵时，可以跳过零元素，只处理非零元素，以节省计算资源。
3.  数据结构选择：  
    使用适当的数据结构：选择合适的数据结构来表示稀疏矩阵，以便有效地存储和操作。常见的数据结构包括压缩行存储（Compressed Row Storage，CSR）、压缩列存储（Compressed Column Storage，CSC）等。

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

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

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义稀疏数组结构
    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;
    }

![在这里插入图片描述][656a3166b876443cb747acc9c6d9f0cc.png]

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

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

[656a3166b876443cb747acc9c6d9f0cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/7d22bcb3e4ca443eae12a1dbe2384d9d.png
[408_C_C_Continually updating]: https://blog.csdn.net/Zhangsama1/article/details/133676491?spm=1001.2014.3001.5502