设矩阵A中有s个非零元素。令e=S(m×m), 称e为矩阵的稀疏因子。 有人认为e≤0.05时称之为稀疏矩阵。 在存储稀疏矩阵时,为节省存储空间,应只 存储非零元素。但由于非零元素的分布一般 没有规律,故在存储非零元素时,必须记下 它所在的行和列的位置(ij) 每一个三元组(,叫)唯一确定了矩阵A的 个非零元素。因此,稀疏矩阵可由表示非零 元素的一系列三元组及其行列数唯一确定
• 设矩阵 A 中有 s 个非零元素。令 e = s/(m×n), 称 e 为矩阵的稀疏因子。 • 有人认为 e≤0.05 时称之为稀疏矩阵。 • 在存储稀疏矩阵时，为节省存储空间，应只 存储非零元素。但由于非零元素的分布一般 没有规律，故在存储非零元素时，必须记下 它所在的行和列的位置 ( i, j )。 • 每一个三元组 (i, j, aij) 唯一确定了矩阵A的一 个非零元素。因此，稀疏矩阵可由表示非零 元素的一系列三元组及其行列数唯一确定。 26
稀跪矩阵的定义 const int drows=6. dcols =7. dterms =9 template<class e> struct Triple i ∥/元组 int row, col; ∥非零元素行号/列号 E value, ∥零元素的值 void operator=( Triple<e>&R)赋值 irow =R row; col =R col; value=R value; j };
稀疏矩阵的定义 const int drows = 6, dcols = 7, dterms = 9; template<class E> struct Triple { //三元组 int row, col; //非零元素行号/列号 E value; //非零元素的值 void operator = (Triple<E>& R) //赋值 { row = R.row; col = R.col; value = R.value; } }; 27
template <class e> class SparseMatrix i public SparseMatrix(int rw= drows, int Cl- dcols int Tm= dterms ) /构造函数 void Transpose( SparseMatrix<E>&b);∥转置 void Add sparseMatrix<e>& a SparseMatrix<E>& b) N/a= a+b void Multiply (sparseMatrix<E>& a, SparseMatrix<E>& b) la= a*b private int rows,Cols, Terms;∥行/列/非零元素数 Triple<e> *sm Array /元组表
template <class E> class SparseMatrix { public: SparseMatrix (int Rw = drows, int Cl = dcols, int Tm = dterms); //构造函数 void Transpose(SparseMatrix<E>& b); //转置 void Add (SparseMatrix<E>& a, SparseMatrix<E>& b); //a = a+b void Multiply (SparseMatrix<E>& a, SparseMatrix<E>& b); //a = a*b pvivate: int Rows, Cols, Terms; //行／列／非零元素数 Triple<E> *smArray; //三元组表 }; 28
稀跪矩阵的构造函数 template <class e> parseMatrix<E>: SparseMatrix(int Rw, int Cl, int Tm)i Rows= Rwe Cols = Cl: Terms= Tm sm array =new TripleTerms]; /元组表 if (sm Array == NULL)& cerr≤<“存储分配失败!”<< end:;exit(1);
稀疏矩阵的构造函数 template <class E> SparseMatrix<E>::SparseMatrix (int Rw, int Cl, int Tm) { Rows = Rw; Cols = Cl; Terms = Tm; smArray = new Triple[Terms]; //三元组表 if (smArray == NULL) { cerr << “存储分配失败！” << endl; exit(1); } }; 29
稀跪矩阵的转置 个m×n的矩阵A,它的转置矩阵B是一 个nm的矩阵,且A[i机=BU[即 ◆矩阵A的行成为矩阵B的列 ◆矩阵A的列成为矩阵B的行。 在稀疏矩阵的三元组表中,非零矩阵元素按 行存放。当行号相同时,按列号递增的顺序 存放。 稀疏矩阵的转置运算要转化为对应三元组表 的转置
稀疏矩阵的转置 • 一个 mn 的矩阵 A，它的转置矩阵 B 是一 个 nm 的矩阵，且 A[i][j] = B[j][i]。即 ◆ 矩阵 A 的行成为矩阵 B 的列 ◆ 矩阵 A 的列成为矩阵 B 的行。 • 在稀疏矩阵的三元组表中，非零矩阵元素按 行存放。当行号相同时，按列号递增的顺序 存放。 • 稀疏矩阵的转置运算要转化为对应三元组表 的转置。 30