稀疏矩阵运算器.cpp

三元组表示的稀疏矩阵的加法,减法,乘法运算器

//设计用三元组表示的稀疏矩阵的加法,减法和乘法,初步设定最大行数为20行,非零元素的最大个数
//为400个.
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 400//假设非零元素个数的最大值为400
#define MAXRC 20	//假设矩阵的最大行数为20
typedef int ElemType;
typedef struct{
	int i,j;	//非零元的行下标和列下标
	ElemType e;//非零元的值
}Triple;
typedef struct{
	Triple data[MAXSIZE+1];//非零元三元组表,data[0]未使用
	int rpos[MAXRC+1];//各行第一个非零元的位置表
	int mu,nu,tu;//矩阵的行数,列数各非零元个数
}TSMatrix,*Matrix;

void CreatSMatrix(TSMatrix &M){
//创建一个三元组来表示矩阵M,同时做出各行第一个非零元的位置表
	int i,k;
	for(i=1;i<=MAXRC+1;i++)//M.rpos的初始化
		M.rpos[i]=0;
	printf("请输入矩阵的行数，列数和非零元个数（以空格隔开）:");
	scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
	for(i=1;i<=M.tu;i++){//输入三元组的元素
		printf("请输入三元组形式的矩阵元素(行 列 非零元素):");
		scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
	}
	for(i=1,k=1;i<=M.mu;i++){//各行第一个非零元的位置表
		M.rpos[i]=k;
		while(M.data[k].i<=i && k<=M.tu)//查找同一行的元素,并使计数k累加
			k++;		
		} 
}

void AddSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C){
//实现C=A+B的功能,在主函数里已经判定A与B的行列是相等的
	int k1,k2,temp,l;
	C.mu=A.mu;//C的行初始化
	C.nu=A.nu;//C的列初始化
	k1=k2=l=1;//用l表示C非零元的个数
	while(k1<=A.tu && k2<=B.tu){//A与B的非零元都没有遍历完
			if(A.data[k1].i==B.data[k2].i){//A与B的行标相等
				if(A.data[k1].j<B.data[k2].j)//A的列标小于B的列标,刚把A的当前元素插到C中
					C.data[l++]=A.data[k1++];
				else if(A.data[k1].j>B.data[k2].j)//A的列标大于B的列标,刚把B的当前元素插到C中
					C.data[l++]=B.data[k2++];
				else{//A的列标和B的列标相等,则把两矩阵的当前的值相加,再判断相加后的值是否为0
					//相加后不为0则插入到C中,否则就不插入C中
					temp=A.data[k1].e+B.data[k2].e;
					if(temp){//相加后的值不为0
						C.data[l].i=A.data[k1].i;
						C.data[l].j=A.data[k1].j;
						C.data[l].e=temp;
						l++;
					}
					k1++;k2++;
				}
			}
			else if(A.data[k1].i<B.data[k2].i)//A的行标小于B的行标,刚把A当前元素插入到C中
				C.data[l++]=A.data[k1++];
			else//A的行标大于B的行标,刚把B当前元素插入到C中
				C.data[l++]=B.data[k2++];
	}
	while(k1<=A.tu)//A还有非零元,则把A剩下的全部插入到C中
		C.data[l++]=A.data[k1++];
	while(k2<=B.tu)//B还有非零元,则把B剩下的全部插入到C中
		C.data[l++]=B.data[k2++];
	C.tu=l-1;
}

void ReverseSMatrix(TSMatrix A,TSMatrix &W){//实现W=-A即W为A的负矩阵
	int k;
	W.mu=A.mu;
	W.nu=A.nu;
	W.tu=A.tu;
	k=1;
	while(k<=A.tu){
		W.data[k].i=A.data[k].i;
		W.data[k].j=A.data[k].j;
		W.data[k].e=-A.data[k].e;
		k++;
	}
}
void SubSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C){
//实现C=A-B,先做B的负矩阵N=-B,再利用加法实现C=A+N=A-B
	TSMatrix N;
	ReverseSMatrix(B,N);
	AddSMatrix(A,N,C);
}
int MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &Q){
//实现Q=A*B,返回1表示是正常的矩阵乘法,返回0表示出错,不正确的乘法
	int arow,brow,ccol,tp,p,q,t;
	int ctemp[MAXRC+1];
	if(A.nu!=B.mu)		return 0;
	Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;//Q的初始化
	if(A.tu*B.tu){//Q为非零元
		for(arow=1;arow<=A.mu;arow++){//处理A的每一行
			for(ccol=1;ccol<=Q.nu;ccol++)//当前行各元素累加器清零
				ctemp[ccol]=0;
			Q.rpos[arow]=Q.tu+1;//处理Q的第arow行的第一个非零元
			if(arow<A.mu)	tp=A.rpos[arow+1];//用tp指示A的第arow+1行的第一个非零元的位置
			else	tp=A.tu+1;//当arow不小于A.mu时,tp表示A的全部非零元个数加1
			for(p=A.rpos[arow];p<tp;p++){//对当前行arow中每一个非零元
				brow=A.data[p].j;//找到对应元在B中对应的行号
				if(brow<B.mu)	t=B.rpos[brow+1];//用t指示B的第brow+1行的第一个非零元的位置
				else	t=B.tu+1;//当brow不小于B.mu时,t表示B的全部非零元个数加1
				for(q=B.rpos[brow];q<t;q++){//处理B的brow行的所有非零元
					ccol=B.data[q].j;//乘积元素在B中的列号
					ctemp[ccol]+=A.data[p].e*B.data[q].e;
				}//for q
			}//for p
			for(ccol=1;ccol<=Q.nu;ccol++){//压缩存储该行的非零元
				if(ctemp[ccol]){
					if(++Q.tu>MAXSIZE)	return 0;
					Q.data[Q.tu].i=arow;
					Q.data[Q.tu].j=ccol;
					Q.data[Q.tu].e=ctemp[ccol];
				}//if
			}//for ccol
		}//for arow
	}//if
	return 1;
}//MultSMatrix


void Print_SMatrix(TSMatrix M){
//输出用三元组表示的矩阵,零元用0输出.
	int k,l,n;
	Matrix p;
	p=&M;
	if(M.tu==0){
		printf("%5d\n",0);
		return;
	}
	for(k=1,n=1;k<=p->mu;k++){
		for(l=1;l<=p->nu;l++){
			if(p->data[n].i==k && p->data[n].j==l){//行和列对应的相等
				printf("%5d",p->data[n].e);
				n++;
			}
			else 
				printf("%5d",0);
		}
		printf("\n");
	}
	printf("\n");
}

void Destory_SMatrix(TSMatrix &M){
//销毁稀疏矩阵M(使M为0行0列0个非零元素的矩阵)
	M.mu=M.nu=M.tu=0;
}
void main(){
	TSMatrix A,B,C;
	int flag,n;
	while(1){
		printf("0:退出\n1:加法\n2:减法\n3:乘法:\n");
		printf("请选择(0~3):");
		scanf("%d",&flag);
		if(flag==0)	break;
		CreatSMatrix(A);
		CreatSMatrix(B);
		printf("矩阵A:\n");
		Print_SMatrix(A);
		printf("矩阵B:\n");
		Print_SMatrix(B);
		switch(flag){
		case 1:		if(A.mu==B.mu  && A.nu==B.nu){
					printf("A+B:\n");
					AddSMatrix(A,B,C);
					Print_SMatrix(C);
					}
					else	printf("错误!行列不一致\n");
					break;
		case 2:		if(A.mu==B.mu  && A.nu==B.nu){
					printf("A-B:\n");
					SubSMatrix(A,B,C);
					Print_SMatrix(C);
					}
					else	printf("错误!行列不一致\n");
					break;
		case 3:		printf("A*B:\n");
					n=MultSMatrix(A,B,C);
					if(!n)	printf("错误!行列不匹配\n");
					else	Print_SMatrix(C);	
					break;
		default:	printf("输入错误!\n");
		}
		Destory_SMatrix(A);
		Destory_SMatrix(B);
		Destory_SMatrix(C);
	}
	fflush(stdin);
	getchar();
}