c++定义行逻辑连接的三元组顺序表,完成稀疏矩阵的基本操作:输入、输出、转置、乘

以下是使用三元组顺序表实现稀疏矩阵的基本操作的代码：

#include <iostream>
using namespace std;

const int MAXSIZE = 1000;  // 三元组顺序表的最大长度

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

// 三元组顺序表定义
struct TSMatrix {
    Triple data[MAXSIZE + 1];  // 三元组顺序表的存储空间
    int rows, cols, nums;      // 稀疏矩阵的行数、列数、非零元素个数
};

// 稀疏矩阵的输入函数
void input(TSMatrix& M) {
    cout << "请输入稀疏矩阵的行数、列数和非零元素个数：" << endl;
    cin >> M.rows >> M.cols >> M.nums;

    cout << "请输入稀疏矩阵的" << M.nums << "个非零元素的行、列和值：" << endl;
    for (int i = 1; i <= M.nums; i++) {
        cin >> M.data[i].row >> M.data[i].col >> M.data[i].value;
    }
}

// 稀疏矩阵的输出函数
void output(TSMatrix M) {
    cout << "稀疏矩阵的三元组表示：" << endl;
    cout << "行 列 值" << endl;
    for (int i = 1; i <= M.nums; i++) {
        cout << M.data[i].row << " " << M.data[i].col << " " << M.data[i].value << endl;
    }
}

// 稀疏矩阵的转置函数
void transpose(TSMatrix M, TSMatrix& T) {
    T.rows = M.cols;
    T.cols = M.rows;
    T.nums = M.nums;

    if (T.nums == 0) {
        return;
    }

    int q = 1;  // T.data[] 的下标
    for (int col = 1; col <= M.cols; col++) {
        for (int p = 1; p <= M.nums; p++) {
            if (M.data[p].col == col) {
                T.data[q].row = M.data[p].col;
                T.data[q].col = M.data[p].row;
                T.data[q].value = M.data[p].value;
                q++;
            }
        }
    }
}

// 稀疏矩阵的乘法函数
void multiply(TSMatrix M1, TSMatrix M2, TSMatrix& M) {
    if (M1.cols != M2.rows) {
        cout << "矩阵无法相乘！" << endl;
        return;
    }

    int rowCnt[MAXSIZE + 1] = {0};  // 存储每一行非零元素个数的数组
    int rowPos[MAXSIZE + 1] = {0};  // 存储每一行第一个非零元素在 data[] 中的下标的数组

    M.rows = M1.rows;
    M.cols = M2.cols;
    M.nums = 0;

    if (M.rows == 0 || M.cols == 0) {
        return;
    }

    // 计算每一行非零元素个数
    for (int p = 1; p <= M1.nums; p++) {
        rowCnt[M1.data[p].row]++;
    }

    // 计算每一行第一个非零元素在 data[] 中的下标
    rowPos[1] = 1;
    for (int i = 2; i <= M1.rows; i++) {
        rowPos[i] = rowPos[i - 1] + rowCnt[i - 1];
    }

    // 逐个计算乘积矩阵的非零元素
    for (int i = 1; i <= M1.rows; i++) {
        int j;
        for (j = 1; j <= M2.cols; j++) {
            int sum = 0;
            for (int p = rowPos[i]; p < rowPos[i] + rowCnt[i]; p++) {
                for (int q = 1; q <= M2.nums; q++) {
                    if (M1.data[p].col == M2.data[q].row && M1.data[p].col == j) {
                        sum += M1.data[p].value * M2.data[q].value;
                        break;
                    }
                }
            }
            if (sum != 0) {
                M.nums++;
                M.data[M.nums].row = i;
                M.data[M.nums].col = j;
                M.data[M.nums].value = sum;
            }
        }
    }
}

int main() {
    TSMatrix M, T, P;

    input(M);
    output(M);

    transpose(M, T);
    output(T);

    multiply(M, T, P);
    output(P);

    return 0;
}

在上述代码中，我们使用了三个函数分别实现稀疏矩阵的输入、输出、转置和乘法操作。其中，稀疏矩阵的转置和乘法操作需要对三元组顺序表的存储结构有一定的理解。在转置操作中，我们逐列扫描原矩阵，将非零元素的行列互换后，按照行优先的顺序存入新的三元组顺序表中。在乘法操作中，我们使用了一个辅助数组 `rowCnt[]` 来存储每一行非零元素的个数，以及一个辅助数组 `rowPos[]` 来存储每一行第一个非零元素在 `data[]` 中的下标，这样可以避免重复扫描 `data[]` 数组。