稀疏矩阵的运算实现快速转置

Question

用三元组存储稀疏矩阵，实现其快速转置及矩阵相乘。可在输入矩阵的过程中建立三元组表及rpos（或cpot）数组。思路简洁

Answer 1

附上代码示例，便于你理解

#include <iostream>
using namespace std;

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

// 稀疏矩阵结构体
struct SparseMatrix {
    int m; // 行数
    int n; // 列数
    int num; // 非零元个数
    Triple *data; // 三元组数组
    int *rpos; // 行指针,rpos[i]表示第i行第一个非零元在data中的位置 
};

// 快速转置 
SparseMatrix transpose(SparseMatrix M) {
    SparseMatrix T;
    T.m = M.n; T.n = M.m;
    T.num = M.num; 
    T.data = new Triple[T.num];
    T.rpos = new int[T.m+1];
    
    // 构造T的rpos[]数组
    for (int i = 0; i <= M.m; i++) T.rpos[i] = 0;
    for (int i = 0; i < M.num; i++) T.rpos[M.data[i].col+1]++;
    for (int i = 1; i <= M.n; i++) T.rpos[i] += T.rpos[i-1];
    
    // 构造T的data[]数组
    for (int i = 0; i < M.num; i++) {
        int j = M.data[i].col;
        int k = T.rpos[j];
        T.data[k].row = M.data[i].col;
        T.data[k].col = M.data[i].row;
        T.data[k++].val = M.data[i].val;
        T.rpos[j] = k;
    }
    return T;
}

// 矩阵乘法
SparseMatrix multiply(SparseMatrix A, SparseMatrix B) {
    //  ommitted 
}

int main() {
    //测试用例...
}