稀疏矩阵运算.cpp

稀疏矩阵运算

// 稀疏矩阵.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include<malloc.h>
#include<iostream.h>
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define MAXSIZE 10000
#define MAXRC 100
typedef int ElemType;

typedef struct
{	
    int i;
	int j;
	ElemType e;
}Triple;

typedef struct
{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
	int mu;
	int nu;
	int tu;
}RLSMatrix;
//三元组的存储结构




void CreateSMatrix(RLSMatrix &M,int m,int n)
{
//按输入的矩阵非零元建立以三元组存储的稀疏矩阵
	
	cout<<"输入矩阵的值"<<endl;
	 M.tu=0;
	int k=1;
    int p=1;
	int num[100];
	int i,j;
	ElemType e;
	M.mu=m;				//传递矩阵的行列数
	M.nu=n;
    
	for(int z=1;z<=100;z++)num[z]=0;

	for(cin>>i>>j>>e;i!=0;cin>>i>>j>>e)
	{//按任意次序输入非零元

		M.data[k].j=j;
	
		M.data[k].i=i;
	
		M.data[k].e=e;
	
		k++;
		}//for
	M.tu=k-1;

    M.rpos[1]=1;

	for(int a=1;a<=M.tu;++a)++num[M.data[a].i];
	
	for(int b=2;b<=M.mu;++b)M.rpos[b]=M.rpos[b-1]+num[b-1];
//初始化矩阵的行链接信息


}//CreateSMatrix


bool MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
//进行两个矩阵相乘操作，并把结果压缩存入新矩阵Q
	int ctemp[100];

	int tp,t,ccol,brow,p,q,arow,lie;

	if(M.nu!=N.mu)return ERROR;

	Q.mu=M.mu;

	Q.nu=N.nu;

	Q.tu=0;
	//Q初始化

	if(M.tu*N.tu!=0)
	{
	for(arow=1;arow<=M.mu;++arow)
	{//处理M的每一行
       int w=arow;
            
		for(lie=1;lie<=N.nu;++lie)
			
			ctemp[lie]=0;			//当前行个元素累加器清零
	
		  Q.rpos[arow]=Q.tu+1;
	
		 
			  if(arow<M.mu)tp=M.rpos[arow+1];

		  
		  else {tp=M.tu+1;}

		  
        

		  for(p=M.rpos[arow];p<tp;++p)
		  {
		      //对当前行中的每一个非零元找到对应元在N中的行号
			  
			  brow=M.data[p].j;
		
	  
		   if(brow<N.mu)t=N.rpos[brow+1];
	
		      else {
				  t=N.tu+1;
			  }//else

	    for(q=N.rpos[brow];q<t;++q)
		{
		  ccol=N.data[q].j;			//乘积元素在Q中列号
	     
		  ctemp[ccol]+=M.data[p].e*N.data[q].e;
	
		}//for q;

			
	
		  }//for p;求得Q中第crow（＝arow）行的非零元

			  
		  
	//压缩存储存储该行的非零元
	for(ccol=1;ccol<=Q.nu;++ccol)

		if(ctemp[ccol])
		{
			Q.tu++;

			if(Q.tu>MAXSIZE)return ERROR;
		      
			   Q.data[Q.tu].i=arow;
		         
			     Q.data[Q.tu].j=ccol;

		           Q.data[Q.tu].e=ctemp[ccol];
		
		}//if

	
	
	}//for arow
	
	}//if

return OK;
}//MultSMatrix


void Rmove(RLSMatrix &M,int p)

{//矩阵中非零元后移
	for(int a=M.tu+1;a>=p;a--)

{
		M.data[a].e=M.data[a-1].e;

		M.data[a].i=M.data[a-1].i;

		M.data[a].j=M.data[a-1].j;

}

}


void Lmove(RLSMatrix &M,int p)

{//矩阵中非零元左移
	for(int a=p;a<M.tu;a++)

{
		M.data[a].e=M.data[a+1].e;

			M.data[a].i=M.data[a+1].i;

				M.data[a].j=M.data[a+1].j;

}
}



bool PlusSMatrix(RLSMatrix &M,RLSMatrix N)
{
//进行两个矩阵的相加，即把第二个矩阵加到第一个矩阵上，如果在对应项上没有元素则插入，
	//如果相加为零
	//则在第一个矩阵中删除原来的元素

	int tp,t,p,q,arow,e;

	if(M.mu!=N.mu&&M.nu!=N.nu)return ERROR;

	
	if(M.tu*N.tu!=0)				//两个矩阵都为非零矩阵
	{
	for(arow=1;arow<=M.mu;++arow)
	
	{//逐行计算
       	
		  if(arow<M.mu)
			  
		  {
		   tp=M.rpos[arow+1];
		  
		   t=N.rpos[arow+1];
		  
		  }

		  else 
		  {tp=M.tu+1;
		   
		  t=N.tu+1;
		  }

		  for(p=M.rpos[arow],q=M.rpos[arow];p<tp||q<t;)

		  {
			  if(p==tp)			//第一个矩阵当前行是否还存在非零元

				  {Rmove(M,p);

		  M.data[p].e=N.data[q].e;

		  M.data[p].i=N.data[q].i;

		  M.data[p].j=N.data[q].j;

		  M.tu++;q++;

		  }

			  if(q==t)p++;					//第二个矩阵当前行是否还存在非零元
			  
			  int a=M.data[p].j;

		  int b=N.data[q].j;

		  if(a<b)p++;

		  else if(a>b)

		  {Rmove(M,p);						//插入第二个矩阵对应位置上第一个矩阵没有的元素

		  M.data[p].e=N.data[q].e;

		  M.data[p].i=N.data[q].i;

		  M.data[p].j=N.data[q].j;

		  M.tu++;

		  }

		  else 
		  
		  {e=M.data[p].e+N.data[q].e;			//相加
		  
		  

		 
		  M.data[p].e=e;

		  p++;
		  
		  q++;}//else 

		  		 		  
		  }//for q,p

		 

		  }//for arow
	}//if
			
return OK;
}	

void PrintSMatrix(RLSMatrix M)
{   

//以阵列形式打印矩阵	
	ElemType Search(RLSMatrix ,int ,int);
	for(int i=1;i<=M.mu;i++)
	{for(int j=1;j<=M.nu;j++)
		{ElemType e=Search(M,i,j);
   printf("%d ",e);}
	cout<<endl;}

}


void SubN(RLSMatrix &N)
{
	for(int i=1;i<=N.tu;i++)

	  N.data[i].e=-N.data[i].e;
}


bool SubSMatrix(RLSMatrix &M,RLSMatrix N)
{//进行两个矩阵的相减，这个算法是把第二个矩阵的非零元都乘上-1后加到第一个矩阵上

	SubN(N); 
  
  if(PlusSMatrix(M,N))return 1;

  else return 0;

	
}	
		  





ElemType Search(RLSMatrix M,int i,int j)
{
//查找矩阵中的非零元	
	for(int k=1;k<=M.tu;k++)
		if(M.data[k].i==i&&M.data[k].j==j)
			return M.data[k].e;
		return 0;
}





	


void main(int argc, char* argv[])
{
	RLSMatrix M,N,Q;
	int m,n;
    char  d='y';
	cout<<"欢迎用本程序进行矩阵运算!"<<endl;
	
loop:
	{
		
	cout<<"请输入第一个矩阵，先输入行数m再输入列数n"<<endl;
	cout<<"m=";
	cin>>m;
	cout<<"n=";
	cin>>n;
	CreateSMatrix(M,m,n);
	//建立第一个矩阵
    cout<<"第一个矩阵如下，请校对："<<endl;
	PrintSMatrix(M);
	cout<<"请输入第二个矩阵，先输入行数m再输入列数n"<<endl;
	cout<<"m=";
	cin>>m;
	cout<<"n=";
	cin>>n;
	CreateSMatrix(N,m,n);			
	//建立第二个矩阵
	cout<<"第二个矩阵如下，请校对："<<endl;
	PrintSMatrix(N);
    cout<<"请选择矩阵运算的类型："<<endl;
	cout<<"(A)加法"<<endl<<"(B)减法"<<endl<<"(C)乘法"<<endl;
	char c;
	cin>>c;
	switch (c)
	{case 'a'://调用矩阵相加函数，并输出计算结果
	              if(PlusSMatrix(M,N))
				  {cout<<"M+N的结果为："<<endl;PrintSMatrix(M);}
				  else {cout<<"输入矩阵行列数不相等,请重新输入"<<endl;
				  goto loop;}break;
	case 'b'://调用矩阵相减函数，并输出计算结果
		if( SubSMatrix(M,N)){
			cout<<"M-N的结果为："<<endl;
	        
			PrintSMatrix(M);}
	 else {cout<<"输入矩阵行列数不相等,请重新输入"<<endl;
				  goto loop;}break;
	case 'c'://调用矩阵相乘函数，并输出计算结果
		if(	MultSMatrix(M,N,Q)){
	cout<<"运算结果为："<<endl;
    PrintSMatrix(Q);
		}
		else {cout<<"第一个矩阵的列数不等于第二个矩阵的行数,请重新输入"<<endl;
				  goto loop;}break;}
	cout<<"Do you want to continue(Y/N)?"<<endl;
	if(cin.get()=='Y'||cin.get()=='y') goto loop;
	}
    cout<<"press any key to contine:"<<endl;
    cin.get();
   
}