sparsematrix.cpp

稀疏矩阵的类定义

#include "iostream.h"
#include "SparseMatrix.h"

SparseMatrix::SparseMatrix(int Maxrow,int Maxcol,int Maxterm,Trituple Array[])  //构造函数，建立一个Maxrow行，Maxcol列，共Maxterm，三元组表（非零元素）为Array的稀疏矩阵
{
	Rows=Maxrow;
	Cols=Maxcol;
	Terms=Maxterm;
	for(int i=0;i<Terms;i++)
	{
		smArray[i].row=Array[i].row;
		smArray[i].col=Array[i].col;
		smArray[i].value=Array[i].value;
	}
}
SparseMatrix SparseMatrix::EmptyMatrix()   //返回空矩阵
{
	SparseMatrix b(0,0,0,NULL);
	return b;
}
SparseMatrix SparseMatrix::Transpose()    //对*this指示的三元组数组中各个三元组交换其行、列的值，得到其转置矩阵
{
	int *rowSize=new int[Cols];  //辅助数组，统计各列（转置后各行）非零元素个数
	int *rowStart=new int[Cols]; //辅助数组，预计转置后各行存放位置
	SparseMatrix b(Cols,Rows,Terms,smArray); //存放转置结果
	b.Rows=Cols;
	b.Cols=Rows;
	b.Terms=Terms;
	if(Terms>0)
	{
		for(int i=0;i<Cols;i++)
		{
			rowSize[i]=0;  
		}
		for(i=0;i<Terms;i++)       //统计矩阵b中第i行非零元素个数
		{
			rowSize[smArray[i].col]++;  //根据矩阵a中第i个非零元素的列号，将rowSize相当该列的计数加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中应存放的位置
			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行非零元素的存放位置加1
		}
	}
	delete []rowSize;
	delete []rowStart;
	return b;
}
SparseMatrix SparseMatrix::Add(SparseMatrix b)  //当矩阵a(*this指示)与矩阵b的行、列数相同时，将这两个矩阵的对应项相加
{
	if(Rows!=b.Rows||Cols!=b.Cols) //不能做加法的矩阵，返回空矩阵
	{
		cout<<"Incompatible matrices"<<endl;
		return EmptyMatrix();
	}
	SparseMatrix result(Rows,Cols,Terms,smArray);
	int CurrentA=0,CurrentB=0;
	int last=-1;
	while(CurrentA<Terms&&CurrentB<b.Terms)
	{
		if(smArray[CurrentA].row==b.smArray[CurrentB].row)  //两个矩阵行号相符
		{
			if(smArray[CurrentA].col==b.smArray[CurrentB].col)  //同一行同一列
			{
				int temp=smArray[CurrentA].value+b.smArray[CurrentB].value;
				if(temp)
				{
					last++;
					result.smArray[last].row=smArray[CurrentA].row;
					result.smArray[last].col=smArray[CurrentA].col;
					result.smArray[last].value=temp;
				}
				CurrentA++;
				CurrentB++;
			}
			else if(smArray[CurrentA].col<b.smArray[CurrentB].col)  //同一行，但A的列号较小
			{
				last++;
				result.smArray[last].row=smArray[CurrentA].row;
				result.smArray[last].col=smArray[CurrentA].col;
				result.smArray[last].value=smArray[CurrentA].value;
				CurrentA++;
			}
			else if(smArray[CurrentA].col>b.smArray[CurrentB].col)  //同一行，但B的列号较小
			{
				last++;
				result.smArray[last].row=b.smArray[CurrentB].row;
				result.smArray[last].col=b.smArray[CurrentB].col;
				result.smArray[last].value=b.smArray[CurrentB].value;
				CurrentB++;
			}
		}
		else if(smArray[CurrentA].row<b.smArray[CurrentB].row)  //A的行号较小
		{
			while(smArray[CurrentA].row<b.smArray[CurrentB].row)
			{
				last++;
				result.smArray[last].row=smArray[CurrentA].row;
				result.smArray[last].col=smArray[CurrentA].col;
				result.smArray[last].value=smArray[CurrentA].value;
				CurrentA++;
			}
		}
		else                                                 //B的行号较小
		{
			while(b.smArray[CurrentB].row<smArray[CurrentA].row)
			{
				last++;
				result.smArray[last].row=b.smArray[CurrentB].row;
				result.smArray[last].col=b.smArray[CurrentB].col;
				result.smArray[last].value=b.smArray[CurrentB].value;
				CurrentB++;
			}
		}
	}
	while(CurrentA<Terms)
	{
		last++;
		result.smArray[last].row=smArray[CurrentA].row;
		result.smArray[last].col=smArray[CurrentA].col;
		result.smArray[last].value=smArray[CurrentA].value;
		CurrentA++;
	}
	while(CurrentB<b.Terms)
	{
		last++;
		result.smArray[last].row=b.smArray[CurrentB].row;
		result.smArray[last].col=b.smArray[CurrentB].col;
		result.smArray[last].value=b.smArray[CurrentB].value;
		CurrentB++;
	}
	result.Rows=Rows;
	result.Cols=b.Cols;
	result.Terms=last+1;
	return result;
}
SparseMatrix SparseMatrix::Multiply(SparseMatrix b) //实现矩阵a与b相乘，结果在result中
{
	if(Cols!=b.Rows)       //A矩阵列数与B矩阵行数不等
	{
		cout<<"Incompatible matrices"<<endl;
		return EmptyMatrix();       //不能做乘法的矩阵，返回空矩阵
	}
	if(Terms==MaxTerms||b.Terms==MaxTerms)   //有一个矩阵的项数达到最大
	{
		cout<<"One additional space in a or b needed"<<endl;
		return EmptyMatrix();         //空间不足，返回空矩阵
	}
	int *rowSize=new int[b.Rows];   //辅助数组，矩阵B各行非零元素个数
	int *rowStart=new int[b.Rows+1];  //辅助数组，矩阵B各行在三元组开始位置
	int *temp=new int[b.Cols];    //临时数组，暂存每一行计算结果
	SparseMatrix result(Rows,b.Cols,Terms,smArray);  //结果矩阵的三元组表result
	for(int i=0;i<b.Rows;i++)  
	{
		rowSize[i]=0;
	}
	for(i=0;i<b.Terms;i++)     //统计矩阵B中第i行非零元素个数
	{
		rowSize[b.smArray[i].row]++;  
	}
	for(i=1;i<=b.Rows;i++)    //计算矩阵B中第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初始化
		{
			temp[i]=0;
		}
		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++)    //将temp中的非零元素压缩到result中去
		{
			if(temp[i]!=0)
			{
				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;
}