matrix.cpp

采用十字链表的稀疏矩阵运算器

#include <iostream.h>
#include <iomanip.h>
#define MAX_TRIPLE 12500            //定义非零元素最多个数
enum Boolean {False,True};			//十字链表，用来区分是表头结点还是链表中非零元素结点

//-------------------------三元组类定义-----------------------

struct Triple
{
	int row,col;
	float value;
	
};

//---------------------------稀疏矩阵类定义------------------------

struct SparseMatrix
{
	int mu,nu;
	float tu;
	Triple data[MAX_TRIPLE];
	//sMatrix SMatix[2];
};
SparseMatrix SMatrix[2];							//申请两个矩阵的空间

//-----------------------矩阵结点类定义--------------------

class Matrix;
class MatrixNode
{
	friend class Matrix;
	friend void AddMatrix(int n);					//矩阵的读入
private:
	MatrixNode *down;								//行列链表指针
	MatrixNode *right;
	Boolean head;									//结点类型
	union{Triple triple;MatrixNode *next;};			//无名联合
	MatrixNode(Boolean b,Triple *t);				//构造函数
};

MatrixNode::MatrixNode(Boolean b,Triple *t)
{
													//构造函数
	head=b;											//结点类型
	if(b){right=next=this;}							//各行列表头结点
	else triple=* t;								//头结点链表的表头或非零元素结点
}

typedef MatrixNode *MatrixNodePtr;					//一个指针数组



class Matrix
{
													//稀疏矩阵的类定义
	friend void AddMatrix(int n);
public:
	MatrixNode * headnode;							//稀疏矩阵的表头
	//~Matrix();
};

//-----------------------------添加并建立十字链表矩阵-------------------------

void AddMatrix(int n);
void AddMatrixInfo()
{
	
	int n;
	cout<<"你要将信息添加到哪个稀疏矩阵：1或2"<<endl;
	cin>>n;
	if(n>2||n<1)
	{
		cout<<"输入有误，请确认输入数字1或2!"<<endl;
		return;
	}
	AddMatrix(n);
}

void AddMatrix(int n)
{
													//读入稀疏矩阵，用十字链表表示
	Triple s;int p;
	Matrix matrix;

	
	cout<<"请输入第"<<n<<"个稀疏矩阵的行数|列数|非零元数个数："<<endl;
	
	cin>>s.row>>s.col>>s.value;						//读入稀疏矩阵的行数、列数和非零元素个数
	if(s.value>s.row*s.col)
	{
		cout<<"输入非法，请确认非零元素的个数!"<<endl;
		return;
	}
	SMatrix[n].mu=s.row;							//给对应矩阵赋值						
	SMatrix[n].nu=s.col;
	SMatrix[n].tu=s.value;
	
	
	if(s.row>s.col)p=s.row;							//确定行/列链表表头结点个数p
	else p=s.col;

	matrix.headnode=new MatrixNode(False,&s);		//创建表头结点
	if(!p){matrix.headnode->right=matrix.headnode;return;}//至少一行或一列
	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];							//last为当前行的最后结点指针
	
	for(i=0;i<s.value;i++)
	{
		//输入三元数组，s.value给出三元组个数
		Triple t;
		cout<<"请输入稀疏矩阵第"<<i+1<<"个非零元素的行--列--值："<<endl;
		cin>>t.row>>t.col>>t.value;					//输入三元组
		if(t.row>CurrentRow)
		{
			//行号大于当前行号，闭合当前行
			last->right=H[CurrentRow];				//在行的方向向表头结点拉链
			CurrentRow=t.row;						//当前行改为新的一行
			last=H[CurrentRow];
		}
		last=last->right=new MatrixNode(False,& t);	//新结点链入链表，last跟上
		H[t.col]->next=H[t.col]->next->down=last;
	
		SMatrix[n].data[i].row=t.row;
	
		SMatrix[n].data[i].col=t.col;
	
		SMatrix[n].data[i].value=t.value;
	}
	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];

	cout<<"你输入的第"<<n<<"稀疏矩阵是："<<endl;
	for(i=0;i<s.value;i++)
	{
		//打印输出所输入的非零元素
		cout<<SMatrix[n].data[i].row<<"    "<<SMatrix[n].data[i].col<<"    "<<SMatrix[n].data[i].value<<endl;
	}
	
	delete [] H;
	return;
}

//------------------------------------矩阵加法-------------------------------------

void Plus()
{
	//判断两个矩阵是否合法，非法就打印输出提示信息
	if(SMatrix[1].mu!=SMatrix[2].mu || SMatrix[1].nu!=SMatrix[1].nu)
	{
		cout<<"你输入的两个稀疏矩阵不能做加法!--两个矩阵的行列值需一样!"<<endl;
		return;
	}
	if(SMatrix[1].mu==SMatrix[2].mu && SMatrix[1].nu==SMatrix[1].nu)
	{
		int j,k;
		float *m=new float[SMatrix[1].mu*SMatrix[1].nu*sizeof(int)];//申请一个空间
		if(!m)return;
		for(j=0;j<SMatrix[1].mu*SMatrix[1].nu;j++)
		{
		m[j]=0;													//初始化m
		}
	
		//对应m取值，并做加法运算
		for(j=0;j<SMatrix[1].tu;j++)
		{
		
			m[SMatrix[1].data[j].col+SMatrix[1].data[j].row*SMatrix[1].nu]+=SMatrix[1].data[j].value;
		}
		for(k=0;k<SMatrix[2].tu;k++)
		{
		m[SMatrix[2].data[k].col+SMatrix[2].data[k].row*SMatrix[2].nu]+=SMatrix[2].data[k].value;
		}
		int x=0;
	
		//以直观方式打印出相加后的矩阵
		for(j=0;j<SMatrix[1].mu;j++)
		{
			for(k=0;k<SMatrix[1].nu;k++)
			{
				cout<<m[x++]<<"   ";
			}
			cout<<endl;
		}
		delete [] m ;
	}
}

//---------------------------------------矩阵减法-----------------------

void Subtract()
{
	if(SMatrix[1].mu!=SMatrix[2].mu || SMatrix[1].nu!=SMatrix[1].nu)
	{
		cout<<"你输入的两个稀疏矩阵不能做减法!--两个矩阵的行列值需一样!"<<endl;
		return;
	}
	if(SMatrix[1].mu==SMatrix[2].mu && SMatrix[1].nu==SMatrix[1].nu)
	{
		int j,k;
		float *m=new float[SMatrix[1].mu*SMatrix[1].nu*sizeof(int)];
		if(!m)return;
		for(j=0;j<SMatrix[1].mu*SMatrix[1].nu;j++)
		{
			m[j]=0;
		}

		for(j=0;j<SMatrix[1].tu;j++)
		{
			m[SMatrix[1].data[j].col+SMatrix[1].data[j].row*SMatrix[1].nu]+=SMatrix[1].data[j].value;
		}
		for(k=0;k<SMatrix[2].tu;k++)
		{
			m[SMatrix[2].data[k].col+SMatrix[2].data[k].row*SMatrix[2].nu]-=SMatrix[2].data[k].value;
		}
		int x=0;
		for(j=0;j<SMatrix[1].mu;j++)
		{
			for(k=0;k<SMatrix[1].nu;k++)
			{
				cout<<m[x++]<<"   ";
			}
			cout<<endl;
		}
		delete [] m;
	}
}

//----------------------------矩阵乘法-----------------------------------------

void Multi()
{
	if(SMatrix[1].nu!=SMatrix[2].mu)
	{
		cout<<"你输入的两个稀疏矩阵不能做乘法!--要求第一个矩阵的列和第二个矩阵的行一样!"<<endl;
		return;
	}
	
	int i,j,k;
	
										//声明三个辅助二维数组m1,m2,q
	float m1[30][30];
	float m2[30][30];
	float q[30][30];
	
										//初始化m1和m2这2个辅助矩阵
	for(i=0;i<SMatrix[1].mu ;i++)
	{
		for(j=0;j<SMatrix[1].nu ;j++)
		{
			m1[i][j]=0;
		}
	}
	for(i=0;i<SMatrix[2].mu ;i++)
	{
		for(j=0;j<SMatrix[2].nu ;j++)
		{
			m2[i][j]=0;
		}
	}
	
										//m1、m2对应元素赋值
	for(i=0;i<SMatrix[1].tu ;i++)
	{
		m1[SMatrix[1].data[i].row][SMatrix[1].data[i].col]=SMatrix[1].data[i].value;
	}
		for(i=0;i<SMatrix[2].tu ;i++)
	{
		m2[SMatrix[2].data[i].row][SMatrix[2].data[i].col]=SMatrix[2].data[i].value;
	}
	
										//将m1和m2相乘后放入q矩阵中	
		for(i=0;i<SMatrix[1].mu ;i++)
	{
		for(j=0;j<SMatrix[2].nu ;j++)
		{
			q[i][j]=0;
			for(k=0;k<SMatrix[1].nu ;k++)
			{
				q[i][j]+=m1[i][k]*m2[k][j];
			}
		}
	}
		for(i=0;i<SMatrix[1].mu ;i++)
	{
		for(j=0;j<SMatrix[2].nu ;j++)
		{
		cout<<q[i][j]<<"   ";
		}
		cout<<endl;
	}

}

//--------------------------------main()函数------------------------------
void main()
{
	cout<<"---------------------"<<"欢迎使用稀疏矩阵(Sparse Matrix)运算器1.0"<<"-------------------"<<endl;
	cout<<setw(60)<<"by 彭玉新"<<endl;
	cout<<"--------------------------------------------------------------------------------"<<endl;
	//Matrix s;
	while(1)
	{
		cout<<setw(10)<<"[1]--选择进行添加矩阵信息"<<endl;
		cout<<setw(10)<<"[2]--选择进行矩阵加法运算"<<endl;
		cout<<setw(10)<<"[3]--选择进行矩阵减法运算"<<endl;
		cout<<setw(10)<<"[4]--选择进行矩阵乘法运算"<<endl;
		cout<<setw(10)<<"[5]--退出"<<endl;
		int Select;
		cin>>Select;
		switch(Select)
		{
			case 1:AddMatrixInfo();break;   //调用进行矩阵信息的添加
			case 2:Plus();break;			//调用做加法
			case 3:Subtract();break;		//调用做减法
			case 4:Multi();break;			//调用做乘法
			case 5:return;					//退出
		}
	}
	return;
}