僅儲存非零元素,每個元素用 (row, col, value) 三元組表示。結構定義:
struct Triple {
int row, col;
ElemType value; // 模板支援多型別
};
template <typename T>
class SparseMatrix {
public:
// 建構與複製
SparseMatrix(int rows, int cols, int maxTerms = 1000);
SparseMatrix(const SparseMatrix& other);
~SparseMatrix();
// 核心運算
SparseMatrix Transpose() const; // 轉置
SparseMatrix Add(const SparseMatrix& b) const; // 加法
SparseMatrix Multiply(const SparseMatrix& b) const; // 乘法
// 輔助
void Append(const Triple& t); // 尾部新增非零元
void Print() const; // 列印三元組表
private:
int rows_, cols_, terms_;
int maxTerms_;
Triple* data_; // 動態陣列
};
O(terms + cols)。C++ 成員函數完全可以返回物件(含 *this、臨時物件、智慧指標等)。現代 C++ (C++11 起) 配合移動語義,回傳大型物件開銷極低。若極度追求效能,可採用輸出參數:
void Add(const SparseMatrix& b, SparseMatrix& result) const;
std::vector<Triple> 替代原始指標,自動管理記憶體。operator+, operator* 提供直觀介面。std::invalid_argument)。