稀疏矩阵（三元组顺序表实现）

定义了一个稀疏矩阵类，有转置和相乘，相加三个功能，主要是熟悉稀疏矩阵的三元组顺序表存储的一些操作，和一般的矩阵不同的地方，两个转置的算法，第一个是较容易想到的，书上管它叫“按需点菜”法，就是按一开始列的顺序，一个个转为新矩阵中行的顺序。第二个叫作“按位就坐”法，就是条件两个辅助数组，确定每一列中第一个非零元在稀疏矩阵中存储的位置，从而可以在操作时，更为容易地实现矩阵转置后可以按行递增的顺序排列整齐。

稀疏矩阵的乘法，我自己觉得确实有难度，研究了一天才研究清楚这个东西，如果按和一般矩阵那样去做的话，虽然会浪费多一点时间，但是代码量和思考量就相对少得多，但是这也是算法的特别之处吧。 下面是代码，有较为清楚的解释

文件"dingyi.h"

#define maxtemr 100
class SparseMatrix; //向前声明

class MatrixTerm//矩阵元素类
{
public:
	int row;//行
	int col;//列
	int value;//值
	friend SparseMatrix;
};

class SparseMatrix
{
private:
	int Rows;//行数
	int Cols;//列数
	int Terms;//非零项个数
	MatrixTerm smArray[maxtemr];//maxterm是常数，maxterm<<Rows*Cols
	int cpot[20];
public:
	void InitMatrix();
	SparseMatrix Transpose1(); //矩阵转置算法1
	SparseMatrix Transpose2();//矩阵转置算法2
	bool Multiply(SparseMatrix b,SparseMatrix &q);//矩阵相乘
	bool Add(SparseMatrix b,SparseMatrix &c);//矩阵相加
	void print();
};

文件"shixian.cpp"

#include"dingyi.h"
#include<iostream>
using namespace std;

void SparseMatrix::InitMatrix()
{
	Terms=0;
	int r,c,s=0,val;
	cout<<"输入要创建的矩阵的行数和列数：";
	cin>>r>>c;
	Rows=r;
	Cols=c;
	
	cout<<"请输入矩阵中各元素的值，请输入"<<r*c<<"个整数"<<endl;
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			cin>>val;
			if(val!=0)
			{
				smArray[s].row=i;
				smArray[s].col=j;
				smArray[s].value=val;
				s++;
			}
		}
	}
	Terms=s;
	int *num=new int[r];

	for(int m=0;m<Rows;m++)
		num[m]=0;

	for(m=0;m<Terms;m++)
		++num[smArray[m].row];
	
	cpot[0]=0;

	for(m=1;m<Rows;m++)
		cpot[m]=cpot[m-1]+num[m-1];
}

SparseMatrix SparseMatrix::Transpose1()
{
	SparseMatrix b;
	b.Rows=Cols;
	b.Cols=Rows;
	b.Terms=Terms;
	if(b.Terms)
	{
		int currentB=0;
		for(int c=0;c<Cols;c++)
			for(int i=0;i<Terms;i++)
				if(smArray[i].col==c)//找到c列中的元素
				{
					b.smArray[currentB].row=c;
					b.smArray[currentB].col=smArray[i].row;
					b.smArray[currentB].value=smArray[i].value;
					currentB++;
				}
	}
	return b;
}

SparseMatrix SparseMatrix::Transpose2()
{
	SparseMatrix b;
	b.Rows=Cols;
	b.Cols=Rows;
	b.Terms=Terms;
	
	int *num;
	int *cpot;
	num=new int[Cols];
	cpot=new int[Cols];

	if(b.Terms)
	{
		for(int c=0;c<Cols;c++)
			num[c]=0;
	
		for(c=0;c<b.Terms;c++)
			++num[smArray[c].col];
		cpot[0]=0;
		
		for(c=1;c<Cols;c++)
			cpot[c]=cpot[c-1]+num[c-1];
		
		for(int p=0;p<b.Terms;p++)
		{
			int j=smArray[p].col;
			int q=cpot[j];
			b.smArray[q].row=smArray[p].col;
			b.smArray[q].col=smArray[p].row;
			b.smArray[q].value=smArray[p].value;
			++cpot[j];
		}
	}
	return b;
}


bool SparseMatrix::Multiply(SparseMatrix b,SparseMatrix &q)
{
	/*
	返回两个矩阵的乘积，用C来装
	采用与第二种转置的算法一样的做法，给每个矩阵增加一个数组，用来记录每一行第一个非零值在
	在矩阵smArray[]中的位置，这个数组就是cpot[],有这样结构的稀疏矩阵叫做行逻辑连接顺序表
	计算过程如下：  
	1.    由于矩阵a和Q的行数相等并且C语言以行为主序进行存储，所以以a进行逐行的扫描。  
	2.    使Q的此行逻辑表的序号等于其非零元个数Q.terms+1，以表示其行的首个元素的序号。  
	3.    从行中找到a的非零元，并以它的列值为b的行号，对b进行行的扫描，若存在，
		  则依次计算它们，并把其值累加到一个以b中这个对应非零元的列值为序号的临时数组q_sum[q_col]中。  
	4.    在a的当前行完成扫描后，将q_sum[q_col]不为0的值，压入到Q矩阵的三元组，累加Q.Terms
	*/
	
	int t1,t2,q_col;
	int *q_sum;//用于存放结果的临时数组
	
	if(this->Cols!=b.Rows)
		return false;
	
	q.Rows=this->Rows;
	q.Cols=b.Cols;
	q.Terms=0;
	q_sum=new int[b.Cols];
	if(this->Terms*b.Terms!=0)
	{
		for(int a_row=0;a_row<this->Rows;a_row++)//以a的每一行为标准，进行运算
		{
			for(int i=0;i<b.Cols;i++)
				q_sum[i]=0;
			
			q.cpot[a_row]=q.Terms;
			
			if(a_row<this->Rows-1)
				t1=this->cpot[a_row+1];
			else
				t1=this->Terms;
			
			for(int p=this->cpot[a_row];p<t1;p++)
			{
				int b_row=this->smArray[p].col;
				
				if(b_row<b.Rows-1)
					t2=b.cpot[b_row+1];
				else
					t2=b.Terms;
				
				for(int q=b.cpot[b_row];q<t2;q++)
				{
					q_col=b.smArray[q].col;
					q_sum[q_col]+=this->smArray[p].value*b.smArray[q].value;
				}
			}
			
			for(q_col=0;q_col<q.Cols;q_col++)
				if(q_sum[q_col])
				{
					q.smArray[q.Terms].row=a_row;
					q.smArray[q.Terms].col=q_col;
					q.smArray[q.Terms].value=q_sum[q_col];
					++q.Terms;
				}
		}
	}

	return true;
}

bool SparseMatrix::Add(SparseMatrix b,SparseMatrix &c)
{
	/*
	计算过程是这样的，一次扫描两个矩阵a,b的smArray[]中的每个数据，
	比较两个数据，如果行号相同，则比较列号，若列号不想等则将列号小的存入矩阵c
	的smArray[]中，若列号相等，则计算，计算完非零，再存入c中；
	如果a的当前项行号小于b的当前项行号，那么就将a的项存入c，反之，存b
	*/
	if(this->Rows!=b.Rows||this->Cols!=b.Cols)
		return false;
	int sum=0;
	int p=0;//指向a的当前项
	int t=0;//指向b的当前项
	int k=0;//指向c的当前项
	while( p<this->Terms && t<b.Terms)
	{
		if(this->smArray[p].row==b.smArray[t].row)
		{
			if(this->smArray[p].col==b.smArray[t].col)
			{
				sum=this->smArray[p].value+b.smArray[t].value;
				if(sum)
				{
					c.smArray[k].row=b.smArray[t].row;
					c.smArray[k].col=b.smArray[t].col;
					c.smArray[k].value=sum;
					k++;p++;t++;
				}
			}
			else if(this->smArray[p].col<b.smArray[t].col)
			{
				c.smArray[k].row=this->smArray[p].row;
				c.smArray[k].col=this->smArray[p].col;
				c.smArray[k].value=this->smArray[p].value;
				k++;p++;
			}
			else
			{
				c.smArray[k].row=b.smArray[t].row;
				c.smArray[k].col=b.smArray[t].col;
				c.smArray[k].value=b.smArray[t].value;
				k++;t++;
			}
		}
		else if(this->smArray[p].row<b.smArray[t].row)
		{
			c.smArray[k].row=this->smArray[p].row;
			c.smArray[k].col=this->smArray[p].col;
			c.smArray[k].value=this->smArray[p].value;
			k++;p++;
		}
		else
		{
			c.smArray[k].row=b.smArray[t].row;
			c.smArray[k].col=b.smArray[t].col;
			c.smArray[k].value=b.smArray[t].value;
			k++;t++;
		}
	}
	while(p<this->Terms)
	{
		c.smArray[k].row=this->smArray[p].row;
		c.smArray[k].col=this->smArray[p].col;
		c.smArray[k].value=this->smArray[p].value;
		k++;p++;
	}
	while(t<b.Terms)
	{
		c.smArray[k].row=b.smArray[t].row;
		c.smArray[k].col=b.smArray[t].col;
		c.smArray[k].value=b.smArray[t].value;
		k++;t++;
	}
	c.Rows=b.Rows;
	c.Cols=b.Cols;
	c.Terms=k;
	return true;
}

void SparseMatrix::print()
{
	int p=Terms;
	for(int i=0;i<p;i++)
		cout<<"smArray["<<smArray[i].row<<"]["<<smArray[i].col<<"]= "<<smArray[i].value<<endl;
	cout<<endl;
}

测试函数"main.cpp"

#include"dingyi.h"

#include<iostream.h>

int main()
{
	SparseMatrix sm,T,F;
	sm.InitMatrix();
	cout<<"矩阵sm 为："<<endl;
	sm.print();
	T=sm.Transpose2();
	//T=sm.Transpose1();
	cout<<"矩阵sm的转置为: "<<endl;
	T.print();

	SparseMatrix M;
	M.InitMatrix();
	cout<<"矩阵M为："<<endl;
	M.print();

	if(sm.Multiply(M,F))
	{
		cout<<"矩阵M与矩阵sm 相乘为："<<endl;
		F.print();
	}
	
	SparseMatrix N,P;
	N.InitMatrix();
	if(sm.Add(N,P))
	{
		cout<<"矩阵sm和N相加的矩阵为："<<endl;
		P.print();
	}
	return 0;
}