稀疏矩阵(SparseMatrix)稀疏矩阵(SparseMatrix)的抽象数据类型template<classType>classSparseMatrix{intRows,Cols,Terms;//行/列/非零元素数Trituple<Type>smArray[MaxTerms];public://三元组表SparseMatrix(intMaxRow,intMaxcol);SparseMatrix<Type>Transpose();//转置SparseMatrix<Type>//相加Add(SparseMatrix<Type>b);SparseMatrix<Type>//相乘Multiply(SparseMatrix<Type>b);}A的三元组顺序表图示三元组(Trituple)类的定义template<classType>classSparseMatrix<Type>;template<classType>classTrituple{friendclassSparseMatrix<Type>private:introw,col;//非零元素所在行号/列号Typevalue;//非零元素的值}用三元组表表示的稀疏矩阵及其转置稀疏矩阵转置算法思想稀疏矩阵的转置template<classType>SparseMatrix<Type>SparseMatrix<Type>::Transpose(){SparseMatrix<Type>b(Cols,Rows);b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;//转置矩阵的列数,行数和非零元素个数if(Terms>0){intCurrentB=0;//转置三元组表存放指针用三元组表表示的稀疏矩阵及其转置快速转置算法稀疏矩阵的快速转置template<classType>SparseMatrix<Type>SparseMatrix<Type>::FastTranspos(){int*rowSize=newint[Cols];int*rowStart=newint[Cols];SparseMatrix<Type>b(Cols,Rows);b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;if(Terms>0){for(inti=0;i<Cols;i++)rowSize[i]=0;for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;稀疏矩阵稀疏矩阵的结点稀疏矩阵的正交链表表示的示例稀疏矩阵的链表表示的类定义enumBoolean{False,True};structTriple{introw,col;floatvalue;};classMatrix;classMatrixNode{//矩阵结点定义friendclassMatrix;friendistream&operator>>(istream&,Matrix&);//矩阵输入重载函数private:MatrixNode*down,*right;//列/行链指针Booleanhead;//结点类型Union{Tripletriple;MatrixNode*next;}//矩阵元素结点(False)或链头结点(True)MatrixNode(Boolean,Triple*);//结点构造函数}MatrixNode::MatrixNode(Booleanb,Triple*t){//矩阵结点构造函数head=b;//结点类型if(b){right=next=this;}elsetriple=*t;}typedefMatrixNode*MatrixNodePtr;//一个指针数组,用于建立稀疏矩阵classMatrix{friendistream&operator>>(istream&,Matrix&);//矩阵输入public:~Matrix();//析构函数private:MatrixNode*headnode;//稀疏矩阵的表头};用正交链表表示的稀疏矩阵的建立istream&operator>>(istream&is,Matrix&matrix){Triples;intp;is>>s.row>>s.col>>s.value;//输入矩阵的行数,列数和非零元素个数if(s.row>s.col)p=s.row;elsep=s.col;//取行、列数大者matrix.headnode=//整个矩阵表头