文章目录
- 什么是稀疏矩阵？
- 使用C语实现对稀疏矩阵的压缩
- 408考研各数据结构C/C++代码（Continually updating）
什么是稀疏矩阵？
稀疏矩阵（Sparse Matrix）是一种矩阵，其中大多数元素都是零。与稠密矩阵相比，稀疏矩阵具有许多零元素，因此存储和处理它们可能会浪费大量的存储空间和计算资源。
为了优化稀疏矩阵的存储和处理，可以采用以下方法：
压缩存储：
-
压缩稀疏矩阵（Compressed Sparse Matrix）：只存储非零元素及其位置信息，以减少存储空间的使用。通常需要存储非零元素的值、行索引和列索引。
利用稀疏矩阵的特殊结构：如果稀疏矩阵具有特殊结构（如对角矩阵、三角矩阵、带状矩阵等），可以采用专门的存储方式，只存储非零元素及其特殊结构的相关信息，以进一步减少存储空间。
稀疏矩阵算法： -
针对稀疏矩阵的特殊算法：一些算法可以针对稀疏矩阵的特性进行优化，以减少计算复杂度。
避免对零元素进行不必要的操作：在处理稀疏矩阵时，可以跳过零元素，只处理非零元素，以节省计算资源。 -
数据结构选择：
使用适当的数据结构：选择合适的数据结构来表示稀疏矩阵，以便有效地存储和操作。常见的数据结构包括压缩行存储（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;
}
408考研各数据结构C/C++代码（Continually updating）
408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。
