首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> 更多程式語言 >> 程式設計綜合問答

C++ 稀疏矩陣類設計:三元組表示法實現加法、轉置與乘法

     編輯:程式設計綜合問答

稀疏矩陣儲存策略:三元組

僅儲存非零元素,每個元素用 (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_; // 動態陣列
};

關鍵演算法要點

1. 轉置

  • 快速轉置:先統計每列非零個數,計算起始位置,一次掃描完成,時間複雜度 O(terms + cols)。

2. 加法

  • 雙指標合併兩有序三元組表(按行優先、列次之),相同位置相加,結果為零則捨棄。
  • 維度不符拋出異常。

3. 乘法

  • 將右矩陣預先轉置(或建立列索引),便於按行×列高效計算內積。
  • 使用暫存陣列累加同一位置的乘積,最後壓縮為三元組。

關於「類裡不能有 return」的誤區

C++ 成員函數完全可以返回物件(含 *this、臨時物件、智慧指標等)。現代 C++ (C++11 起) 配合移動語義,回傳大型物件開銷極低。若極度追求效能,可採用輸出參數:
void Add(const SparseMatrix& b, SparseMatrix& result) const;

學習資源推薦

實作建議

  1. 使用 std::vector<Triple> 替代原始指標,自動管理記憶體。
  2. 重載 operator+, operator* 提供直觀介面。
  3. 加入邊界檢查與異常處理(std::invalid_argument)。
  4. 編寫單元測試驗證:隨機生成稀疏矩陣,對比稠密矩陣運算結果。
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved