稀疏矩阵C++语言实现.doc

#include #include using namespace std;template/三元组struct Tritupleint row;int col;T val;/稀疏矩阵声明templateclass SparseMatrixpublic:SparseMatrix(int maxt=100);SparseMatrix();bool TransposeTo(SparseMatrix &);bool AddTo(const SparseMatrix&);bool TransposeTo_Faster(SparseMatrix&);void Input();void Output();private:Trituple* data;int rows,cols,terms;int maxterms;templateSparseMatrix:SparseMatrix(int maxt)maxterms=maxt;data=new Trituplemaxterms;terms=rows=cols=0;templateSparseMatrix:SparseMatrix()if (data!=NULL)delete data;/普通转置templatebool SparseMatrix:TransposeTo(SparseMatrix &B)if (termsB.maxterms)return false;B.rows=cols;B.cols=rows;B.terms=terms;if (terms0)int p=0;for (int j=1;j=cols;j+)for (int k=0;kterms;k+)if (datak.col=j)B.datap.row=j;B.datap.col=datak.row;B.datap.val=datak.val;p+;return true;/快速转置templatebool SparseMatrix:TransposeTo_Faster(SparseMatrix& B)if (termsB.maxterms)return false;B.rows=cols;B.cols=rows;B.terms=terms;if (terms0)int *num,*cpot;num=new intcols;cpot=new intcols;for (int j=0;jcols;j+)numj=0;for (int k=0;kterms;k+)numdatak.col-1+;/求出B中每一行的起始下标cpotcpot0=0;for (int j=1;jcols;j+)cpotj=cpotj-1+numj-1;/执行转置操作for (int p,k=0;kterms;k+)p=cpotdatak.col-1+;B.datap.row=datak.col;B.datap.col=datak.row;B.datap.val=datak.val;delete num;delete cpot;return true;templatevoid SparseMatrix:Input()coutrow1;coutcol1;coutinput row1*col1 matrixendl;int number;rows=row1;cols=col1;for (int i=0;irows;i+)for (int j=0;jnumber;if (number!=0)dataterms.row=i+1;dataterms.col=j+1;dataterms.val=number;terms+;template /输出好看，但是违背了最初的原则void SparseMatrix:Output()T *tempArray=new T*rows;for (int i1=0;i1rows;i1+)tempArrayi1=new intcols;for (int j=0;jrows;j+)for (int k=0;kcols;k+)tempArrayjk=0;for (int i=0;iterms;i+)tempArraydatai.row-1datai.col-1=datai.val;for (int j=0;jrows;j+)for (int k=0;kcols;k+)coutsetw(4)tempArrayjk;coutendl;for (int l=0;lrows;l+)delete tempArrayl;delete tempArray;coutendl;templatebool SparseMatrix:AddTo(const SparseMatrix& B)if (rows!=B.rows|cols!=B.cols)return false;bool flag=false;int tempTerms=terms;for (int i=0;iB.terms;i+)flag=false;for (int j=0;jtempTerms;j+)if (dataj.col=B.datai.col&dataj.row=B.datai.row)dataj.val+=B.datai.val;flag=true;if (flag=false)data+terms-1.col=B.datai.col; /数组下标操作注意事项dataterms-1.row=B.datai.row;dataterms-1.val=B.datai.val;return true;int main()cout此程序演示稀疏矩阵的普通转置和快速转置操作endl;SparseMatrix sm(50);SparseMatrix sm1(50);SparseMatrix sm2(50);sm.Input();coutsm isendl;sm.Output();sm.TransposeTo(sm1);coutTransposition of sm is endl;sm1.Output();sm.TransposeTo_Faster(sm2);coutTransposition of sm is endl;sm2.Output();SparseMatrix sm3;coutinput a new matrixendl;sm3.Input();coutsm3 isendl;sm3.Output