稀疏矩阵的C程序

1. 稀疏矩阵是什么？

稀疏矩阵（Sparse Matrix）是一种特殊的矩阵，它的元素中有大量的零元素。例如，一个1000\*1000的矩阵，如果只有100个非零元素，那么这个矩阵就是一个稀疏矩阵。

由于稀疏矩阵中有大量的零元素，因此存储这种矩阵会浪费大量的空间。而且，在矩阵的加、减、乘、转置等运算中，由于有大量的零元素，往往可以省略掉一些计算，从而提高计算效率。因此，对于稀疏矩阵的存储和运算有着独特的需求。

2. 稀疏矩阵的存储方式

2.1. 压缩存储法

压缩存储法是一种常见的稀疏矩阵存储方式。它将稀疏矩阵中的非零元素按照行或列的顺序进行存储，同时记录下它们在原始矩阵中的行列坐标。以压缩存储法存储的稀疏矩阵可以分为三个数组：val(存储非零值)、row_ptr(存储每个非零值所在行的位置)和col_idx(存储每个非零值所在列的位置)。

// 压缩存储法存储稀疏矩阵

struct sparse_matrix {
    double* val;
    int* row_ptr;
    int* col_idx;
    int nnz; // 非零元素的个数
    int rows; // 矩阵的行数
    int cols; // 矩阵的列数
};

例如一个3\*3的稀疏矩阵，它的非零元素、行列坐标和压缩存储对应的数组如下：

| 稀疏矩阵 | 非零元素 | 行坐标 | 列坐标 | | :--: | :--: | :--: | :--: | | 2 0 0 | 2 | 0 | 0 | | 0 3 1 | 3 | 1 | 1 | | 0 4 0 | 4 | 2 | 1 |

| :--------: | :--------: | :--------: | :--------: |

| val | 2 3 4 |

| row_ptr | 0 1 3 3 |

| col_idx | 0 1 1 |

2.2. 链式前向星存储法

链式前向星（Linked Forward Star）是另一种常见的稀疏矩阵存储方式。它在稀疏矩阵中找到每个非零元素，并将它们组织成一个链表。每个链表中的元素包含该元素的值、列坐标和一个指向下一个非零元素的指针。链式前向星存储法不需要预先知道非零元素的个数，因此能够适用于动态构建稀疏矩阵的场合。

// 链式前向星存储稀疏矩阵

struct sparse_matrix {
    struct node {
        double val;
        int col_idx;
        node* next;
    };
    node** heads;
    int rows; // 矩阵的行数
    int cols; // 矩阵的列数
    sparse_matrix(int rows_, int cols_) : rows(rows_), cols(cols_) {
        heads = new node*[rows];
        for (int i = 0; i < rows; ++i) {
            heads[i] = new node{-1, -1, nullptr};
        }
    }
};

例如一个3\*3的稀疏矩阵，它的非零元素、行列坐标和链式前向星存储对应的链表如下：

| 稀疏矩阵 | 非零元素 | 行坐标 | 列坐标 | | :--: | :--: | :--: | :--: | | 2 0 0 | 2 | 0 | 0 | | 0 3 1 | 3 | 1 | 1 | | 0 4 0 | 4 | 2 | 1 |

| :--------: | :--------: | :--------: | :--------: |

| heads | node->node->node | 图片证明 |

3. 稀疏矩阵乘法的实现

对于两个稀疏矩阵A和B，它们的乘积AB的每个元素可以表示为：

AB[i][j] = Sum(A[i][k]\*B[k][j]), k = 1,2,...,n

其中，A和B的维度分别为m\*n和n\*p，AB的维度为m\*p。

3.1. 压缩存储法实现

使用压缩存储法存储稀疏矩阵，可以通过设计三重循环来求解稀疏矩阵乘法。具体地，假设A和B是两个稀疏矩阵，它们存储在以下结构体中：

// 稀疏矩阵结构体

struct sparse_matrix {
    double* val;
    int* row_ptr;
    int* col_idx;
    int nnz;
    int rows;
    int cols;
};
// 稀疏矩阵乘法
sparse_matrix sparse_matrix_mult(sparse_matrix A, sparse_matrix B) {
    if (A.cols != B.rows) {
        throw std::runtime_error("Invalid matrix size for multiplication.");
    }
    sparse_matrix C;
    C.rows = A.rows;
    C.cols = B.cols;
    C.nnz = 0;
    C.val = new double[C.rows * C.cols]();
    C.row_ptr = new int[C.rows + 1]();
    C.col_idx = new int[2 * A.nnz]();
    for (int i = 0; i < A.rows; ++i) {
        intC.row_ptr[i] = C.nnz;
        for (int j = 0; j < B.cols; ++j) {
            double sum = 0;
            for (int k = A.row_ptr[i]; k < A.row_ptr[i + 1]; ++k) {
                int colA = A.col_idx[k];
                double valA = A.val[k];
                for (int l = B.row_ptr[colA]; l < B.row_ptr[colA + 1]; ++l) {
                    if (B.col_idx[l] == j) {
                        sum += valA * B.val[l];
                        break;
                    }
                }
            }
            if (sum != 0) {
                C.val[C.nnz] = sum;
                C.col_idx[C.nnz] = j;
                ++C.nnz;
            }
        }
    }
    C.row_ptr[C.rows] = C.nnz;
    return C;
}

3.2. 链式前向星实现

使用链式前向星存储稀疏矩阵，可以先将B矩阵进行转置，然后通过两重循环遍历A矩阵，并在B'矩阵中寻找可以乘法的元素。

// 稀疏矩阵结构体

struct sparse_matrix {
    struct node {
        double val;
        int col_idx;
        node* next;
    };
    node** heads;
    int rows;
    int cols;
    // 转置稀疏矩阵
    sparse_matrix transpose() const {
        sparse_matrix B(cols, rows);
        for (int i = 0; i < rows; ++i) {
            for (node* p = heads[i]->next; p != nullptr; p = p->next) {
                int j = p->col_idx;
                double val = p->val;
                node* node_new = new node{val, i, B.heads[j]->next};
                B.heads[j]->next = node_new;
            }
        }
        return B;
    }
};
// 稀疏矩阵乘法
sparse_matrix sparse_matrix_mult(sparse_matrix A, sparse_matrix B) {
    if (A.cols != B.rows) {
        throw std::runtime_error("Invalid matrix size for multiplication.");
    }
    B = B.transpose();
    sparse_matrix C(A.rows, B.rows);
    for (int i = 0; i < A.rows; ++i) {
        for (sparse_matrix::node* pA = A.heads[i]->next; pA != nullptr; pA = pA->next) {
            int colA = pA->col_idx;
            double valA = pA->val;
            for (sparse_matrix::node* pB = B.heads[colA]->next; pB != nullptr; pB = pB->next) {
                int colB = pB->col_idx;
                double valB = pB->val;
                double valC = valA * valB;
                sparse_matrix::node* pC = C.heads[i];
                while (pC->next != nullptr && pC->next->col_idx < colB) {
                    pC = pC->next;
                }
                if (pC->next == nullptr || pC->next->col_idx > colB) {
                    sparse_matrix::node* node_new = new sparse_matrix::node{valC, colB, pC->next};
                    pC->next = node_new;
                    ++C.nnz;
                }
                else {
                    pC->next->val += valC;
                    if (pC->next->val == 0) {
                        sparse_matrix::node* node_del = pC->next;
                        pC->next = node_del->next;
                        delete node_del;
                        --C.nnz;
                    }
                }
            }
        }
    }
    return C;
}

4. 总结

稀疏矩阵是计算机科学中的一个重要概念，在计算机科学中有着广泛的应用，包括图形学、计算机视觉、科学计算等领域。对于稀疏矩阵的存储和计算具有一定难度，但通过压缩存储法和链式前向星存储法等方式，可以高效地进行处理。