smatrix.cpp

稀疏矩阵运算器 本程序要求用“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 400
#define MAXRC 20

typedef struct{
int i,j;
int e;
}Triple;//定义三元组

typedef struct{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];
int mu,nu,tu;
}RLSMatrix;//定义矩阵


void PrintSMatrix(RLSMatrix &M){
//以通常形式打印矩阵
int T[MAXRC][MAXRC];
int i,j,k;
for(i=1;i<=M.mu;++i)
   for(j=1;j<=M.nu;++j)
	   T[i][j]=0;
for(k=1;k<=M.tu;++k)
T[M.data[k].i][M.data[k].j]=M.data[k].e;
for(i=1;i<=M.mu;++i){
   for(j=1;j<=M.nu;++j)
	   printf("%-7d",T[i][j]);
   printf("\n");
}//for
}//PrintSMatrix


void CreateSMatrix(RLSMatrix &M,int &r,int &c){
//提示输入三元组并且建立相应的矩阵，
//本程序要求输入三元组的顺序是在行号小的优先的条件下，列号小的输入！
int i,j,k,row;
int e;
int num[21];
k=1;
M.mu=r;M.nu=c;M.tu=0;
printf("Please input the row number,colume number and value\nof a number in order(small row first,then small colume first):\n");
//要求输入三元组的顺序是在行号小的优先的条件下，列号小的输入！
do{
    scanf("%d%d%d",&i,&j,&e);
	M.data[k].i=i;
	M.data[k].j=j;
	M.data[k].e=e;
	++k;++M.tu;
}while(i!=0);//以i等于零作为结束输入标志，此时输入为"0 0 0"
--M.tu;
for(row=1;row<=M.mu;++row)
num[row]=0;
for(k=1;k<=M.tu;++k)
++num[M.data[k].i];
M.rpos[1]=1;//M.rpos[1]定义为1
for(row=2;row<=M.mu;++row)
M.rpos[row]=M.rpos[row-1]+num[row-1];//求得行逻辑
printf("The Matrix you input is:\n");
PrintSMatrix(M);
}//CreateSMatrix


int cmp(int &a,int &b){
if(a>b)return 1;
else if(a==b)return 0;
else return -1;
}//比较函数cmp


void AddSMatrix(RLSMatrix &M,RLSMatrix &N){
//矩阵相加。比较两个矩阵的三元组的行号与列号，自小而大，建立矩阵Q
//采用switch语句来实现
RLSMatrix Q; int p,q,r,row,k;
int num[21];
Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;
p=q=r=1;
while(p<=M.tu&&q<=N.tu){
	switch(cmp(M.data[p].i,N.data[q].i)){
	    case 1:Q.data[r].i=N.data[q].i;
		       Q.data[r].j=N.data[q].j;
		       Q.data[r].e=N.data[q].e;
		       ++q; break;
	    case 0:switch(cmp(M.data[p].j,N.data[q].j)){
	              case 1:Q.data[r].i=N.data[q].i;
		                 Q.data[r].j=N.data[q].j;
                         Q.data[r].e=N.data[q].e;
						 ++q; break;
				  case 0:Q.data[r].i=N.data[q].i;
		                 Q.data[r].j=N.data[q].j;
			             Q.data[r].e=M.data[p].e+N.data[q].e;
			             ++p; ++q;
						 break;
				  case -1:Q.data[r].i=M.data[p].i;
					      Q.data[r].j=M.data[p].j;
						  Q.data[r].e=M.data[p].e;
						  ++p; break;
               }//switch  
               break;
		case -1:Q.data[r].i=M.data[p].i;
		        Q.data[r].j=M.data[p].j;
		        Q.data[r].e=M.data[p].e;
		        ++p; break;
	}//switch
++r;
++Q.tu;
}//while
if(p<=M.tu)
for(;p<=M.tu;++p,++r){
Q.data[r].i=M.data[p].i;
Q.data[r].j=M.data[p].j;
Q.data[r].e=M.data[p].e;
++Q.tu;
}//for
if(q<=N.tu)
for(;q<=N.tu;++q,++r){
Q.data[r].i=N.data[q].i;
Q.data[r].j=N.data[q].j;
Q.data[r].e=N.data[q].e;
++Q.tu;
}//for
for(row=1;row<=Q.mu;++row)
num[row]=0;
for(k=1;k<=Q.tu;++k)
++num[Q.data[k].i];
Q.rpos[1]=1;
for(row=2;row<=Q.mu;++row)
Q.rpos[row]=Q.rpos[row-1]+num[row-1];
printf("The Matrix Add expression result is:\n");
PrintSMatrix(M);
printf("+");
printf("\n");
PrintSMatrix(N);
printf("=");
printf("\n");
PrintSMatrix(Q);
}//AddSMatrix


void Add2(RLSMatrix &M,RLSMatrix &N,RLSMatrix &Q){
//除没有最后的结果打印外，其他的与AddSMatrix()均相同，主要为了供SubSMatrix调用
int p,q,r,row,k;
int num[21];
Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;
p=q=r=1;
while(p<=M.tu&&q<=N.tu){
	switch(cmp(M.data[p].i,N.data[q].i)){
	    case 1:Q.data[r].i=N.data[q].i;
		       Q.data[r].j=N.data[q].j;
		       Q.data[r].e=N.data[q].e;
		       ++q; break;
	    case 0:switch(cmp(M.data[p].j,N.data[q].j)){
	              case 1:Q.data[r].i=N.data[q].i;
		                 Q.data[r].j=N.data[q].j;
                         Q.data[r].e=N.data[q].e;
						 ++q; break;
				  case 0:Q.data[r].i=N.data[q].i;
		                 Q.data[r].j=N.data[q].j;
			             Q.data[r].e=M.data[p].e+N.data[q].e;
			             ++p; ++q;
						 break;
				  case -1:Q.data[r].i=M.data[p].i;
					      Q.data[r].j=M.data[p].j;
						  Q.data[r].e=M.data[p].e;
						  ++p; break;
               }//switch  
               break;
		case -1:Q.data[r].i=M.data[p].i;
		        Q.data[r].j=M.data[p].j;
		        Q.data[r].e=M.data[p].e;
		        ++p; break;
	}//switch
++r;
++Q.tu;
}//while
if(p<=M.tu)
for(;p<=M.tu;++p,++r){
Q.data[r].i=M.data[p].i;
Q.data[r].j=M.data[p].j;
Q.data[r].e=M.data[p].e;
++Q.tu;
}//for
if(q<=N.tu)
for(;q<=N.tu;++q,++r){
Q.data[r].i=N.data[q].i;
Q.data[r].j=N.data[q].j;
Q.data[r].e=N.data[q].e;
++Q.tu;
}//for
for(row=1;row<=Q.mu;++row)
num[row]=0;
for(k=1;k<=Q.tu;++k)
++num[Q.data[k].i];
Q.rpos[1]=1;
for(row=2;row<=Q.mu;++row)
Q.rpos[row]=Q.rpos[row-1]+num[row-1];
}//Add2


void SubSMatrix(RLSMatrix &M,RLSMatrix &N){
//将作为减数的矩阵每个元素的值乘上-1，再调用AddSMatrix()，就能实现减法运算
int k;
RLSMatrix Q;
printf("The Matrix Sub expression result is:\n");
PrintSMatrix(M);
printf("-");
printf("\n");
PrintSMatrix(N);
printf("=");
printf("\n");
for(k=1;k<=N.tu;++k)
N.data[k].e*=-1;
Add2(M,N,Q);
PrintSMatrix(Q);
}//SubSMatrix


void MultSMatrix(RLSMatrix &M,RLSMatrix &N){
int tp,t,p,q,i,arow,brow,ccol;
int ctemp[21];//作累加器
RLSMatrix Q;
Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;
if(M.tu*N.tu!=0){
	for(arow=1;arow<=M.mu;++arow){//逐行处理M
		for(i=1;i<=20;i++)ctemp[i]=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){
			brow=M.data[p].j;//找到N中相应的行
			if(brow<N.mu) t=N.rpos[brow+1];
			else t=N.tu+1;
			for(q=N.rpos[brow];q<t;++q){
			   ccol=N.data[q].j;
			   ctemp[ccol]+=M.data[p].e*N.data[q].e;
			}//for q
		}//for p
		for(ccol=1;ccol<=Q.nu;++ccol)//压缩存储Q的一行（第arow行）
			if(ctemp[ccol]!=0){
				++Q.tu;
				Q.data[Q.tu].i=arow;
                Q.data[Q.tu].j=ccol;
				Q.data[Q.tu].e=ctemp[ccol];
			}//if
	}//for arow
}//if
printf("The Matrix Multi expression result is:\n");
PrintSMatrix(M);
printf("*");
printf("\n");
PrintSMatrix(N);
printf("=");
printf("\n");
PrintSMatrix(Q);
}//MultSMatrix


void main(){
int i,r1,c1,r2,c2;
RLSMatrix M,N;

do{
	printf("1.Matrix Add\n2.Matrix Sub\n3.Matrix Multi\n4.quit\n");
	printf("Please choose 1~4!\n");
	scanf("%d",&i);
	if(i>4||i<1){
	   printf("Please choose 1~4!\n");
	   continue;
	}//if
	if(i==4)break;
	//输入相应的行数与列数，并且要求输入的行数与列数不大于20
	printf("Please input the total row number(<=20)\nand total colume number(<=20)of first Matrix:\n");
	scanf("%d%d",&r1,&c1);
    printf("Please input the total row number(<=20)\nand total colume number(<=20)of second Matrix:\n");
    scanf("%d%d",&r2,&c2); 
	if(r1>20||r2>20||c1>20||c2>20){
	   printf("row number and total number should not more than 20!\n");
	   continue;
	}//if
	switch(i){
	   case 1:if(r1!=r2||c1!=c2)
				  printf("input error!\n");
		      else{
				  printf("First Matrix->");
				  CreateSMatrix(M,r1,c1);
				  printf("Second Matrix->");
				  CreateSMatrix(N,r2,c2);
				  AddSMatrix(M,N);
			  }
			  break;
	   case 2:if(r1!=r2||c1!=c2)
				  printf("input error!\n");
		      else{
				  printf("First Matrix->");
				  CreateSMatrix(M,r1,c1);
				  printf("Second Matrix->");
				  CreateSMatrix(N,r2,c2);
				  SubSMatrix(M,N);
			  }
			  break;
	   case 3:if(c1!=r2)printf("input error!\n");
		      else{
				  printf("First Matrix->");
				  CreateSMatrix(M,r1,c1);
				  printf("Second Matrix->");
				  CreateSMatrix(N,r2,c2);
				  MultSMatrix(M,N);
			  }
			  break;
	   case 4:break;
	}//switch
}while(i>=1&&i<=3);
}//main