稀疏矩陣 c++編程.doc

#includeusing namespace std;const int DafaultSize=100;struct Tritupleint row,col;double value;Trituple& operator = (Trituple& x)row=x.row;col=x.col;value=x.value;return *this;class SparseMatrixfriend ostream& operator(istream& in,SparseMatrix& M);private:int Rows,Cols,Terms;Trituple *smArray;int maxTerms;public:SparseMatrix(int maxSz=DafaultSize);SparseMatrix(SparseMatrix& x);SparseMatrix()deletesmArray;SparseMatrix& operator = (SparseMatrix& x);SparseMatrix Transpose();SparseMatrix FastTranspose();SparseMatrix Add(SparseMatrix& b);SparseMatrix Multiply(SparseMatrix& b);SparseMatrix:SparseMatrix(int maxSz):maxTerms(maxSz)if(maxSz1)cerr矩陣初始化錯誤！endl;exit(1);smArray=new TrituplemaxSz;if(smArray=NULL)cerr儲存分配錯誤！endl;exit(1);Rows=Cols=Terms=0;SparseMatrix:SparseMatrix(SparseMatrix& x)Rows=x.Rows;Cols=x.Cols;Terms=x.Terms;maxTerms=x.maxTerms;smArray=new TrituplemaxTerms;if(smArray=NULL)cerr存儲分配錯誤！endl;exit(1);for(int i=0;iTerms;i+)smArrayi = x.smArrayi;ostream& operator(ostream& out,SparseMatrix& M)outrows = M.Rowsendl;outcols = M.Colsendl;outNonzero terms = M.Termsendl;for(int i=0;iM.Terms;i+)outMM.smArrayi.rowM.smArrayi.col=M.smArrayi.value(istream& in,SparseMatrix& M)cout請輸入稀疏矩陣的行數(shù)，列數(shù)及項數(shù)！M.RowsM.ColsM.Terms;if(M.TermsM.maxTerms)cerr項數(shù)太多！endl;exit(1);for(int i=0;iM.Terms;i+)cout請輸入項的行數(shù)，列數(shù)及其值：i+1M.smArrayi.rowM.smArrayi.colM.smArrayi.value;return in;SparseMatrix SparseMatrix:Transpose()SparseMatrix b(maxTerms);b.Cols=Rows;b.Rows=Cols;b.Terms=Terms;if(Terms0)int k,i,CurrentB=0;for(k=0;kCols;k+)for(i=0;i0)int i,j;for(i=0;iCols;i+) rowSizei=0;for(i=0;iTerms;i+) rowSizesmArrayi.col+;rowStart0=0;for(i=1;iCols;i+)rowStarti=rowStarti-1+rowStarti-1;for(i=0;iTerms;i+)j=rowStartsmArrayi.col;b.smArrayj.row=smArrayi.col;b.smArrayj.col=smArrayi.row;b.smArrayj.value=smArrayi.value;rowStartsmArrayi.col+;delete rowSize;delete rowStart;return b;SparseMatrix SparseMatrix:Add(SparseMatrix& b)SparseMatrix result(b);if(Rows!=b.Rows|Cols!=b.Cols)cerr兩?矩?陣規(guī)?格?不?同?！?endl;return result;int i=0,j=0,index_a,index_b;result.Terms=0;while(iTerms&jindex_b)result.smArrayresult.Terms=b.smArrayj;j+;else if(index_aindex_b)result.smArrayresult.Terms=smArrayi;i+;elseresult.smArrayresult.Terms=smArrayi;result.smArrayresult.Terms.value=smArrayi.value+b.smArrayj.value;if(result.smArrayresult.Terms.value=0)result.Terms-;i+,j+;result.Terms+;SparseMatrix SparseMatrix:Multiply(SparseMatrix& b)SparseMatrix result(*this);if(Rows!=b.Cols)cerrA的列數(shù)不等于的行數(shù)，不可相乘！endl;return result;if(Terms=maxTerms|b.Terms=maxTerms)cerr空間不足！endl;return result;int *rowSize=new intb.Rows;int *rowStart=new intb.Rows+1;double *temp=new doubleb.Cols;int i,Current,lastInResult,RowA,ColA,ColB;for(i=0;ib.Rows;i+)rowSizei=0;for(i=0;ib.Terms;i+)rowSizeb.smArrayi.row+;rowStart0=0;for(i=1;i=b.Rows;i+)rowStarti=rowStarti-1+rowSizei-1;Current=0;lastInResult=-1;while(CurrentTerms)RowA=smArrayCurrent.row; /當前行的行號?for(i=0;ib.Cols;i+)tempi=0;while(CurrentTerms&smArrayCurrent.row=RowA)ColA=smArrayCurrent.col; /矩陣當前掃描到元素的列號for(i=rowStartColA;irowStartColA+1;i+)ColB=b.smAr