读取文件（使用稀疏矩阵）并生成 CSR

Question

我需要读取 .txt 文件中的方阵并将其存储为 CSR 格式。我知道如何阅读矩阵，但我无法想出如何制作 CSR.

这是读取矩阵的代码：

#include<stdio.h>
#include<string.h>
int main(){
  FILE *f;
  int i,j,n;
  float x;
  f=fopen("file.txt","r");
  if(f=NULL){
  printf(\n No file found \n");
  }
  fscanf(f,"%d",&n);
  for(i=0;i<n;i++){
     for(j=0;j<n;j++){
        fscan(f,"%f",&x);
        printf("\n element (%d,%d) = %f",i,j,x); //this is just to see that the matrix looks like I want it to be, it's not part of CSR problem
     }
  }
  return 0;
}

有什么建议吗？

Answer 1

让我们将 CSR（或 CRS，"compressed row storage"）结构解释为三个数组的结构：

struct csr {
    size_t row_count;
    size_t *row_indices;
    float *values;
    size_t *column_indices;
};

此处，values 和 column_indices 应指向相同大小的数组（或者，您可以将它们构造为 int-double 对的一个数组） , 和 row_indices 应该指向这两个数组中的索引数组。 （实际上，我们将对 row_indices 采取一些自由；而不是指向一行的第一个 column/value，我们将指向最后一个 [=行的 70=]。）

您的 *.txt 文件格式似乎包含方阵，并以大小参数 (n) 开头。

struct csr your_csr;
size_t n;

fscanf(f, "%d", &n);
your_csr.row_count = n;

读完这个n，我们可以分配row_indices。不幸的是，我们不知道矩阵中会有多少非零值。目前，这个简单的实现将只分配 n x n 个元素，更保守的方法留给 reader.

作为练习。

your_csr.row_indices     = calloc(n, sizeof(your_csr.row_indices[0]));
your_csr.values          = calloc(n * n, sizeof(your_csr.values[0]));
your_csr.column_indices  = calloc(n * n, sizeof(your_csr.column_indices[0]));

现在我们有了内存，让我们处理矩阵数据。

size_t pair_index = 0;

for (size_t row_index = 0; row_index < n; row_index++) {
    for (size_t column_index = 0; column_index < n; column_index++) {
        float value;
        fscanf(f, "%f", &value);

对于您读取的每个非零值，您将把您知道的内容写入您的 values 和 column_indices 数组

        if (value != 0.0) {
            your_csr.values[pair_index] = value;
            your_csr.column_indices[pair_index] = column_index;
            pair_index++;
        }
    }

读完一行后，您要记下该行结束的位置。

    your_csr.row_indices[row_index] = pair_index;
}

现在，your_csr 包含您需要了解的有关矩阵的所有数据：

your_csr.row_count 包含矩阵中的行数。
另外两个数组的长度是your_csr.row_indices[your_csr.row_count - 1].
如果您想知道 your_csr.values[x] 属于哪一列，请查看 your_csr.column_indices[x]。
可以在 your_csr.values[x] 中找到第一行的（非零）值（我们称之为第 0 行；数学家会不同意，但基于零的索引非常适合编程），其中 0 <= x && x < your_csr.row_indices[0].
可以找到任何其他行 r 的值 your_csr.values[x]，其中 your_csr.values[r - 1] <= x && x < your_csr.row_indices[r]。

读取文件（使用稀疏矩阵）并生成 CSR

Read a file (with a sparse matrix) and generate CSR

c

sparse-matrix

numerical-methods