matrix.h

稀疏矩阵加法的另类算法

#include "stdafx.h"
#include <iostream.h>

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
///////////////////////Matrix realize///////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
enum Boolean { True, False };
struct Triple { int row, col, value; };

class Matrix;

//MatrixNode
class MatrixNode {
	friend class Matrix;
	friend istream &operator >> ( istream &, Matrix & );
private:
	Boolean head;
	MatrixNode *down, *right;
	union { Triple triple; MatrixNode *next; };
	MatrixNode ( Boolean b, Triple * t);
};

MatrixNode::MatrixNode ( Boolean b, Triple * t ){
	head=b;
	if( b==True ){
		right = down = next = this;
	}
	else triple = *t;
}

typedef MatrixNode * MatrixNodePtr;

//Matrix
class Matrix{
	friend istream &operator >> ( istream & , Matrix & );	
public:
	Matrix ( ){}
	void Add(Matrix*);
	~Matrix ( ){}	//haven't built
private:
	char Compare(const int x,  const int y) const;
	MatrixNode *headnode;
};

//Over realize input(operator >>)
istream &operator >> ( istream & is , Matrix & matrix ){
	Triple s;
	s.col = s.row = s.value = 0;
	int p = 0;
	is >> s.row >> s.col >> s.value ;
	//cout << s.row << s.col << s.value ;
	//is >> s.value ;
	p=( s.row > s.col) ? s.row : s.col;
	matrix.headnode = new MatrixNode( False, &s );
	if( !p ){
		matrix.headnode->right = matrix.headnode;//point
		return is;
	}
	MatrixNodePtr * H = new MatrixNodePtr [ p ];
	for ( int i=0; i<p; i++ )	H[i] = new MatrixNode ( True, 0 );
	int CurrentRow = 0;
	MatrixNode * last = H[0];
	for ( i=0; i<s.value; i++ ){
		Triple t;
		t.col = t.row = t.value = 0;
		is >> t.row >>t.col >> t.value;
		if ( t.row > CurrentRow){	//should input in order
			last->right = H[CurrentRow];
			CurrentRow = t.row;
			last = H[CurrentRow];
		}
		last = last->right = new MatrixNode ( False , & t );
		H[t.col]->next = H[t.col]->next->down = last;
	}
	last->right = H[CurrentRow];
	for ( i = 0; i<s.col; i++ )	H[i]->next->down=H[i];
	for ( i = 0; i<p-1; i++ )	H[i]->next = H[i+1];
	H[p-1]->next = matrix.headnode;	
	matrix.headnode->right = H[0];
	delete []H;
	return is;
}

//Compare 
char Matrix::Compare(const int x, const int y) const{
	if( x == y )	return '=';
	else if( x < y )	return '<';
	else if( x > y )	return '>';
	else return '*';
}

//////////////////////////////////////////////////////////////////////
////////////////////////////Add///////////////////////////////////////
//////////////////////////////////////////////////////////////////////
void Matrix::Add(Matrix * y ){
	if( this->headnode->triple.row != y->headnode->triple.row 
		|| this->headnode->triple.col != y->headnode->triple.col )
		cout << "Error!The sizes of both matrixes art different."<<endl;
	else {
		MatrixNode * pheadl, * pheadr, * prowl, * prowr;
		int iter = 0;
		int row_num = 0;
		//Traverse all column
		for ( pheadl = this->headnode->right, pheadr = y->headnode->right;
			  pheadl != this->headnode && row_num<this->headnode->triple.row;
			  pheadl = pheadl->next, pheadr = pheadr->next,row_num++ ){ 
				iter = 0;
				prowl = pheadl->right;
				prowr = pheadr->right;
				while ( prowl != pheadl && prowr != pheadr ){	//Traverse the rows
					switch ( Compare( prowl->triple.col, prowr->triple.col )){
					case '=':
						if ( iter == prowl->triple.col ) { 
							cout << prowl->triple.value + prowr->triple.value << ' ';
							prowl = prowl->right;
							prowr = prowr->right;
							iter++;
						}
						else{
							for ( ; iter<prowl->triple.col; iter++ )
								cout << "0 ";
							iter++;
							cout << prowl->triple.value + prowr->triple.value << ' ';
							prowl = prowl->right;
							prowr = prowr->right;
						}
						break;
					case '>':
						if ( prowr->triple.col == iter ){
							cout << prowr->triple.value << ' ';
							prowr = prowr->right;
							iter++;
						}
						else {
							for ( ; iter<prowr->triple.col; iter++ )
								cout << "0 ";
							iter++;
							cout << prowr->triple.value << ' ';
							prowr = prowr->right;
						}
						break;
					case '<':
						if ( prowl->triple.col == iter ){
							cout << prowl->triple.value << ' ';
							prowl = prowl->right;
							iter++;
						}
						else {
							for ( ; iter<prowl->triple.col; iter++ )
								cout << "0 ";
							iter++;
							cout << prowl->triple.value << ' ';
							prowl = prowl->right;
						}
						break;
					}
				}
				if ( prowl == pheadl ){
					while( prowr != pheadr ){
						if ( iter == prowr->triple.col){
							cout << prowr->triple.value << ' ';
							prowr = prowr->right;
							iter++;
						}
						else {
							for ( ; iter<prowr->triple.col; iter++ )
								cout << "0 ";
							cout << prowr->triple.value << ' ';
						prowr = prowr->right;
							}
					}
					if ( iter != y->headnode->triple.col )//
						for ( ; iter<y->headnode->triple.col; iter++)
							cout << "0 ";
						cout <<endl;
				}
				else {
					while( prowl != pheadl ){
						if ( iter == prowl->triple.col){
							cout << prowl->triple.value << ' ';
							prowl = prowl->right;
							iter++;
						}
						else {
							for ( ; iter<prowl->triple.col; iter++ )
								cout << "0 ";
							cout << prowl->triple.value << ' ';
							prowl = prowl->right;
						}
					}
				if ( iter != this->headnode->triple.col-1 )
						for ( ; iter<this->headnode->triple.col; iter++)
							cout << "0 ";
						cout <<endl;
					}
			  }
	}
}
//////////////////////////////////////////////////////////////////////
////////////////////////////Add///////////////////////////////////////
//////////////////////////////////////////////////////////////////////