稀疏矩阵乘法三元顺序表代码

下面是稀疏矩阵乘法的三元顺序表代码，使用了稀疏矩阵的压缩存储方式：

#include <iostream>
#include <vector>

using namespace std;

// 三元组结构体
struct Triple
{
    int row;
    int col;
    int value;
};

// 稀疏矩阵类
class SparseMatrix
{
public:
    SparseMatrix(int row, int col, int count)
    {
        this->row = row;
        this->col = col;
        this->count = count;
        data.resize(count);
    }

    // 获取三元组
    Triple& operator[](int index)
    {
        return data[index];
    }

    // 获取三元组数量
    int size()
    {
        return count;
    }

    // 获取行数
    int getRowCount()
    {
        return row;
    }

    // 获取列数
    int getColCount()
    {
        return col;
    }

private:
    int row;            // 行数
    int col;            // 列数
    int count;          // 非零元素个数
    vector<Triple> data;    // 三元组数组
};

// 稀疏矩阵乘法函数
SparseMatrix multiply(SparseMatrix& A, SparseMatrix& B)
{
    if (A.getColCount() != B.getRowCount()) {
        throw "Invalid matrix size";
    }

    int n = A.size();
    int m = B.size();

    SparseMatrix C(A.getRowCount(), B.getColCount(), 0);

    int p = 0, q = 0;
    while (p < n && q < m) {
        int i = A[p].row;
        int j = B[q].col;

        int sum = 0;
        int k1 = p, k2 = q;
        while (k1 < n && A[k1].row == i && k2 < m && B[k2].col == j) {
            if (A[k1].col == B[k2].row) {
                sum += A[k1].value * B[k2].value;
                k1++;
                k2++;
            } else if (A[k1].col < B[k2].row) {
                k1++;
            } else {
                k2++;
            }
        }

        if (sum != 0) {
            C[C.size()] = { i, j, sum };
        }

        while (p < n && A[p].row == i) {
            p++;
        }

        while (q < m && B[q].col == j) {
            q++;
        }
    }

    return C;
}

int main()
{
    // 示例矩阵 A
    SparseMatrix A(3, 3, 3);
    A[0] = { 0, 0, 1 };
    A[1] = { 1, 1, 1 };
    A[2] = { 2, 2, 1 };

    // 示例矩阵 B
    SparseMatrix B(3, 2, 4);
    B[0] = { 0, 0, 1 };
    B[1] = { 0, 1, 1 };
    B[2] = { 1, 0, 1 };
    B[3] = { 2, 1, 1 };

    // 计算矩阵乘积
    SparseMatrix C = multiply(A, B);

    // 输出结果矩阵 C
    for (int i = 0; i < C.size(); i++) {
        cout << C[i].row << " " << C[i].col << " " << C[i].value << endl;
    }

    return 0;
}

该代码中，稀疏矩阵类 `SparseMatrix` 包含三个成员变量 `row`、`col` 和 `count`，分别表示稀疏矩阵的行数、列数和非零元素个数，以及一个三元组数组 `data`，用于存储稀疏矩阵的非零元素。

稀疏矩阵乘法函数 `multiply` 的参数为两个稀疏矩阵 `A` 和 `B`，返回它们的乘积矩阵 `C`。在函数中，使用两个指针 `p` 和 `q` 分别遍历稀疏矩阵 `A` 和 `B` 的非零元素，对于每个非零元素 `(i, j)`，计算矩阵乘积中 `(i, j)` 位置的值，并将其添加到结果矩阵 `C` 中。在计算矩阵乘积时，使用两个指针 `k1` 和 `k2` 分别遍历稀疏矩阵 `A` 和 `B` 中 `(i, j)` 位置的非零元素，找到它们的乘积并累加到 `sum` 变量中。如果 `sum` 不为零，则将其添加到结果矩阵 `C` 中。最后返回结果矩阵 `C`。