//Test is T55_59.cpp#include <iostream.h>const int MaxTerms = 100;template <class Type>	class SparseMatrix;			//稀疏矩陣的類聲明template <class Type>	class Trituple {			//三元組類Trituplefriend class SparseMatrix<Type> ;friend istream & operator >> ( istream & , SparseMatrix<Type> & );friend ostream & operator << ( ostream & , SparseMatrix<Type> & );private:   int row, col;							//非零元素的行號、列號   Type value;							//非零元素的值};template <class Type>	class SparseMatrix {	//對象: 是一個三元組<row, column, value>的集合。其中, row和column是整數(shù), 記憶矩陣	//元素所在的行號和列號，而value是矩陣元素的值。friend istream & operator >> ( istream & , SparseMatrix<Type> & );friend ostream & operator << ( ostream & , SparseMatrix<Type> & );public:   SparseMatrix ();   SparseMatrix ( int MaxRow, int MaxCol ): Rows( MaxRow ), Cols( MaxCol ){};   	//構(gòu)造函數(shù)	//建立一個MaxRow行, Maxcol列的稀疏矩陣。   SparseMatrix<Type> Transpose ( );	//對*this指示的三元組數(shù)組中各個三元組交換其行、列的值, 得到其轉(zhuǎn)置矩陣。   SparseMatrix<Type> Add ( SparseMatrix<Type> b );	//當矩陣a(*this指示)與矩陣b的行、列數(shù)相同時, 將這兩個矩陣的對應(yīng)項相加。   SparseMatrix<Type> Multiply ( SparseMatrix<Type> b );	//按公式 c[i][j]=∑(a[i][k]*b[k][j]) 實現(xiàn)矩陣a與b相乘。k=0, 1, …, a的列數(shù)-1。   SparseMatrix<Type> FastTranspose ( );   SparseMatrix<Type> EmptyMatrix ( );private:   int Rows, Cols, Terms ;   Trituple<Type> smArray[MaxTerms];};template <class Type> SparseMatrix<Type> SparseMatrix<Type>::Transpose ( ) {	//將稀疏矩陣a(*this指示)轉(zhuǎn)置, 結(jié)果在稀疏矩陣b中。	   SparseMatrix<Type> b ( Cols, Rows );					//創(chuàng)建一個稀疏矩陣類的對象b	   b.Rows = Cols;							//矩陣b的行數(shù)=矩陣a的列數(shù)	   b.Cols = Rows;							//矩陣b的列數(shù)=矩陣a的行數(shù)	   b.Terms = Terms;						//矩陣b的非零元素數(shù)=矩陣a的非零元素數(shù)	   if ( Terms > 0 ) {							//非零元素個數(shù)不為零	      int CurrentB = 0;						//存放位置指針	      for ( int k=0; k<Cols; k++ )					//按列號做掃描，做Cols趟	   for ( int i=0; i<Terms; i++ ) 					//在數(shù)組中找列號為k的三元組		  if ( smArray[i].col == k ) {				//第i個三元組中元素的列號為k			b.smArray[CurrentB].row = k;			//新三元組的行號			b.smArray[CurrentB].col = smArray[i].row;	//新三元組的列號			b.smArray[CurrentB].value = smArray[i].value;	//新三元組的值			CurrentB++;						//存放指針進1		  }	   }	   return b;}template <class Type> SparseMatrix<Type> SparseMatrix<Type>::FastTranspose ( ) {	//對稀疏矩陣a(*this指示)做快速轉(zhuǎn)置, 結(jié)果放在b中, 時間代價為O(Terms+Columns)	   int *rowSize = new int[Cols];					//輔助數(shù)組, 統(tǒng)計各列非零元素個數(shù)	   int *rowStart = new int[Cols];					//輔助數(shù)組, 預(yù)計轉(zhuǎn)置后各行存放位置	   SparseMatrix<Type> b ( Cols, Rows );					 //存放轉(zhuǎn)置結(jié)果	   b.Rows = Cols;  b.Cols = Rows;  b.Terms = Terms;	   if ( Terms > 0 ) {		 for ( int i=0; i<Cols; i++ ) rowSize[i] = 0; 		//統(tǒng)計矩陣b中第i行非零元素個數(shù)		 for ( i=0; i<Terms; i++ ) rowSize[smArray[i].col]++;	      //根據(jù)矩陣a中第i個非零元素的列號, 將rowSize相當該列的計數(shù)加1		 rowStart[0] = 0;						//計算矩陣b第i行非零元素的開始存放位置		 for ( i=1; i <Cols; i++ )					//rowStart[i] = 矩陣b的第i行的開始存放位置		   rowStart[i] = rowStart[i-1]+rowSize[i-1];		 for ( i=0; i<Terms; i++ ) {					//從a向b傳送		   int j = rowStart[smArray[i].col];			// j為第i個非零元素在b中應(yīng)存放的位置		   b.smArray[j].row = smArray[i].col;		   b.smArray[j].col = smArray[i].row;		   b.smArray[j].value = smArray[i].value;		   rowStart[smArray[i].col]++;				//矩陣b第i行非零元素的存放位置加一		 }	   }	   delete [ ] rowSize;   delete [ ] rowStart;	   return b;}template <class Type> SparseMatrix<Type> SparseMatrix<Type>::Multiply(SparseMatrix<Type> b)	//兩個稀疏矩陣A (*this指示) 與B (參數(shù)表中的b) 相乘, 結(jié)果在Result中{    if ( Cols != b.Rows ) {	 cout << "Incompatible matrices" << endl;			//A矩陣列數(shù)與B矩陣行數(shù)不等	 return EmptyMatrix ( );					//不能做乘法的矩陣，返回空矩陣    }    if ( Terms == MaxTerms || b.Terms == MaxTerms ) {		//有一個矩陣的項數(shù)達到最大       cout << "One additional space in a or b needed" << endl;	 return EmptyMatrix ( );					//空間不足，返回空矩陣    }    int *rowSize = new int[b.Rows];		 		//輔助數(shù)組, 矩陣B各行非零元素個數(shù)    int *rowStart = new int[b.Rows+1]; 				//輔助數(shù)組, 矩陣B各行在三元組開始位置    Type * temp = new Type[b.Cols];				//臨時數(shù)組, 暫存每一行計算結(jié)果    SparseMatrix<Type> result ( Rows, b.Cols );			//結(jié)果矩陣的三元組表result    for ( int i=0; i<b.Cols; i++ ) rowSize[i] = 0; 		//統(tǒng)計矩陣B中第i行非零元素個數(shù)    for ( i=0; i<b.Terms; i++ ) rowSize[smArray[i].row]++;    rowStart[0] = 0;							//計算矩陣B第i行非零元素的開始位置    for ( i=1; i <=b.Cols; i++ ) rowStart[i] = rowStart[i-1] + rowSize[i-1];    int Current = 0,  lastInResult = -1;				//a.smArray掃描指針及result存放指針    while ( Current < Terms ) {					//生成result的當前行temp	  int RowA = smArray[Current].row;			//當前行的行號	  for ( i=0; i<b.Cols; i++ ) temp[i] = 0;			//temp初始化	  while ( Current < Terms && smArray[Current].row == RowA ) {	     int ColA = smArray[Current].col;			//矩陣A當前掃描到元素的列號	     for ( i=rowStart[ColA]; i<rowStart[ColA+1]; i++ ) {		  int ColB = b.smArray[i].col;			//矩陣B中相乘元素的列號		  temp[ColB] = temp[ColB] + smArray[Current].value * b.smArray[i].value;	     }								//A的RowA行與B的ColB列相乘	    Current++;	  }	  for ( i=0; i<b.Cols; i++ )	    if ( temp[i] != 0 ) {					//將temp中的非零元素壓縮到result中去		 lastInResult++;		 result.smArray[lastInResult].row = RowA;		 result.smArray[lastInResult].col = i;		 result.smArray[lastInResult].value = temp[i];	    }    }    result.Rows = Rows;  result.Cols = b.Cols;  result.Terms = lastInResult+1;    delete [ ] rowSize;  delete [ ] rowStart;  delete [ ] temp;    return result;}template <class Type>  SparseMatrix<Type> SparseMatrix<Type>:: EmptyMatrix ( ) {    SparseMatrix<Type> b(0,0);    return b;}template <class Type> istream & operator >> ( istream & is , SparseMatrix<Type> & matrix) {    cout << "Rows and Cols: " << endl;    is >> matrix.Rows >> matrix.Cols;    cout << "row col value : ( ended by row = -1 ) " << endl;    matrix.Terms = -1 ;    do {	matrix.Terms ++;	is >> matrix.smArray[matrix.Terms].row	   >> matrix.smArray[matrix.Terms].col	   >> matrix.smArray[matrix.Terms].value;    } while ( matrix.smArray[matrix.Terms].row != -1 );    return is;}template <class Type> ostream & operator << ( ostream & os , SparseMatrix<Type> & matrix) {    if ( matrix.Terms == 0 ) { os << "It is empty."; return os}    os << "Rows: " << matrix.Rows << endl;    os << "Cols: " << matrix.Cols << endl;    os << "col row value: " << endl;    for (int i=0; i<matrix.Terms; i++) {	os << matrix.smArray[i].row << " "	   << matrix.smArray[i].col << " "	   << matrix.smArray[i].value << endl;    }    return os;}