当前位置:C++技术网 > 资讯 > 数据结构笔记分享:3 稀疏矩阵

数据结构笔记分享:3 稀疏矩阵

更新时间:2015-11-06 16:38:34浏览次数:1+次

定义:大多数元素为零的矩阵称为稀疏矩阵。
目的:为了节省空间,对于稀疏矩阵可只存非零元素。
在稀疏矩阵上执行的操作本质上是普通矩阵的操作,下面的ADT 定义了包括建立、加法、乘法和转置操作的抽象数据类型。
ADT SparseMatrix {
  数据:
    绝大多数元素为零的矩阵。
  运算:
    Create();   建立一个稀疏矩阵。
    Destroy();撤消一个稀疏矩阵。
    Add(B,C):当前矩阵对象与B相加,C中返回相加和。
    Multiply(B,C): 当前矩阵对象与B相乘,C中返回相乘积。
    Transpose(B): B中返回当前矩阵对象的转置矩阵。
} 
稀疏矩阵的C++类
template <class T>
class SparseMatrix {
public:
    SparseMatrix(int maxRowSize, int maxColSize){};
    ~SparseMatrix(){};
    virtual void Add(const SparseMatrix <T> &B,
                    SparseMatrix <T> &C) const;
    virtual void Mul(const SparseMatrix <T> &B,
                    SparseMatrix <T> &C) const;
    virtual void Transpose(SparseMatrix <T> &B)
                    const;   
 private:
          int maxRows, maxCols;
};

三元组表示法

按照压缩存储的思想,稀疏矩阵Am×n中的每一个非零元素 aij 的行号、列号和值可以用一个三元组( i, j, v)表示。三元组可以按行或按列的顺序存储。

//Term类
template <class T>
struct Terms                     
{
   int row,col;  
   T value;
};
行三元组表示的稀疏矩阵的C++类
template <class T>
class SeqTriple {
public:
    SeqTriple(int maxLengthSize);
    void Add(const SeqTriple<T> &B,  SeqTriple<T> & C) const;
    void Mul(const SeqTriple<T> &B,  SeqTriple<T> & C) const;
    SeqTriple<T>  Transpose(SeqTriple<T> &B) const;
    friend istream &operator >>(istream &input, SeqTriple<T> &);
    friend ostream &operator <<(istream &output, const SeqTriple<T> &);
 private:
    int maxSize; //最大个数
    int m, n , t;   //行数,列数,非零元素个数
    Terms<T> * trip;  //动态一维数组的指针
};