宁波网站制作费用_宿迁房产网商铺_活动推广方案策划_百度sem竞价托管公司

#include <iostream>
#include <vector>

using namespace std;

// 定义三元组结构，用于存储非零元素的行号、列号和值
struct Triple {
    int row, col, value;
};

// 定义稀疏矩阵结构
struct SparseMatrix {
    int rows, cols, nums;
    vector<Triple> data;
};

// 从键盘读取稀疏矩阵
SparseMatrix readSparseMatrix() {
    SparseMatrix matrix;
    cin >> matrix.rows >> matrix.cols >> matrix.nums;
    matrix.data.resize(matrix.nums);
    for (int i = 0; i < matrix.nums; ++i) {
        cin >> matrix.data[i].row >> matrix.data[i].col >> matrix.data[i].value;
    }
    return matrix;
}

// 输出稀疏矩阵
void printSparseMatrix(const SparseMatrix& matrix) {
    cout << matrix.rows << " " << matrix.cols << " " << matrix.nums << endl;
    for (const auto& triple : matrix.data) {
        cout << triple.row << " " << triple.col << " " << triple.value << endl;
    }
}

// 稀疏矩阵加法
SparseMatrix addSparseMatrices(const SparseMatrix& a, const SparseMatrix& b) {
    if (a.rows != b.rows || a.cols != b.cols) {
        cout << "Matrices dimensions do not match!" << endl;
        exit(1);
    }

    SparseMatrix c = {a.rows, a.cols, 0};
    vector<int> rowEnd(a.rows + 1, 0);

    // 计算非零元素个数
    for (int i = 0; i < a.nums; ++i) {
        rowEnd[a.data[i].row + 1]++;
    }
    for (int i = 0; i < b.nums; ++i) {
        rowEnd[b.data[i].row + 1]++;
    }

    // 计算行的起始位置
    for (int i = 1; i <= a.rows; ++i) {
        rowEnd[i] += rowEnd[i - 1];
    }

    // 创建临时数组存储结果
    vector<Triple> temp(rowEnd[a.rows]);

    // 合并两个稀疏矩阵
    for (int i = 0, k = 0; i < a.nums; ++i) {
        while (k < rowEnd[a.data[i].row + 1] && temp[k].row < a.data[i].row) {
            k++;
        }
        if (k < rowEnd[a.data[i].row + 1] && temp[k].row == a.data[i].row && temp[k].col == a.data[i].col) {
            temp[k].value += a.data[i].value;
            if (temp[k].value == 0) { // 移除值为0的元素
                temp[k] = temp[rowEnd[a.rows] - 1];
                rowEnd[a.data[i].row]++;
                rowEnd[a.data[i].row]--;
                k--;
            }
        } else {
            temp[k] = a.data[i];
            rowEnd[a.data[i].row]++;
            k++;
        }
    }

    for (int i = 0, k = 0; i < b.nums; ++i) {
        while (k < rowEnd[b.data[i].row + 1] && temp[k].row < b.data[i].row) {
            k++;
        }
        if (k < rowEnd[b.data[i].row + 1] && temp[k].row == b.data[i].row && temp[k].col == b.data[i].col) {
            temp[k].value += b.data[i].value;
            if (temp[k].value == 0) { // 移除值为0的元素
                temp[k] = temp[rowEnd[a.rows] - 1];
                rowEnd[b.data[i].row]++;
                rowEnd[b.data[i].row]--;
                k--;
            }
        } else {
            temp[k] = b.data[i];
            rowEnd[b.data[i].row]++;
            k++;
        }
    }

    // 计算非零元素个数
    c.nums = 0;
    for (int i = 0; i <= a.rows; ++i) {
        c.nums += rowEnd[i] - rowEnd[i - 1];
    }

    // 复制临时数组到结果矩阵
    c.data.resize(c.nums);
    for (int i = 0, k = 0; i < a.rows; ++i) {
        for (int j = rowEnd[i]; j < rowEnd[i + 1]; ++j, ++k) {
            c.data[k] = temp[j];
        }
    }

    return c;
}

int main() {
    cout << "Enter the dimensions and elements of matrix A:" << endl;
    SparseMatrix A = readSparseMatrix();

    cout << "Enter the dimensions and elements of matrix B:" << endl;
    SparseMatrix B = readSparseMatrix();

    SparseMatrix C = addSparseMatrices(A, B);

    cout << "The result of A + B is:" << endl;
    printSparseMatrix(C);

    return 0;
}