C++ 稀疏矩陣類設計與實現：基於三元組壓縮存儲

題目需求分析

• 實現 Sparse 類繼承 Matrix 接口
• 構造函數初始化全零矩陣
• 重載 operator+ 實現稀疏矩陣加法
• 輸出非零元素三元組 (row, col, value)

核心數據結構：三元組順序表

struct Triple {
    int row, col;
    double value;
};

class Sparse : public Matrix {
private:
    int rows_, cols_;
    vector data_;  // 動態數組存儲非零元素
    // 或固定大小: Triple data_[MAX_SIZE]; int len_ = 0;

public:
    Sparse(int rows, int cols) : rows_(rows), cols_(cols) {}

    // 設置元素：若值為0則刪除，否則插入/更新
    void set(int row, int col, double value) override {
        if (value == 0) { remove(row, col); return; }
        
        // 查找是否存在
        for (auto& t : data_) {
            if (t.row == row && t.col == col) {
                t.value = value;
                return;
            }
        }
        // 新增非零元素
        data_.push_back({row, col, value});
    }

    double get(int row, int col) const override {
        for (const auto& t : data_)
            if (t.row == row && t.col == col) return t.value;
        return 0;
    }

    // 稀疏矩陣加法：合並非零元素
    Sparse operator+(const Sparse& other) const {
        Sparse result(rows_, cols_);
        // 複製當前矩陣非零元素
        for (const auto& t : data_) result.set(t.row, t.col, t.value);
        // 累加另一矩陣非零元素
        for (const auto& t : other.data_) 
            result.set(t.row, t.col, result.get(t.row, t.col) + t.value);
        return result;
    }

    void print() override {
        for (const auto& t : data_)
            cout << "(" << t.row << "," << t.col << "," << t.value << ")" << endl;
    }
    
    int size(int dim) const override { 
        return dim == 0 ? rows_ : cols_; 
    }
};

示例驗證

輸入:
1000000 1000000
1 1 10
1 1000000 50
1000000 1000000 20
1 1000000 30
1000000 1 40
1 1 -10

輸出:
(1,1000000,80)
(1000000,1,40)
(1000000,1000000,20)

說明：(1,1) 位置 10 + (-10) = 0，不輸出零元素；其他位置正常累加。

優化方向

• 使用 std::map<pair<int,int>, double> 自動排序、查找 O(log N)
• 大規模矩陣採用 CSR/CSC 格式，支持高效矩陣運算
• 並行化加法運算 (OpenMP)