//設(shè)計用三元組表示的稀疏矩陣的加法,減法和乘法,初步設(shè)定最大行數(shù)為20行,非零元素的最大個數(shù)
//為400個.
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 400//假設(shè)非零元素個數(shù)的最大值為400
#define MAXRC 20	//假設(shè)矩陣的最大行數(shù)為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;//矩陣的行數(shù),列數(shù)各非零元個數(shù)
}TSMatrix,*Matrix;

void CreatSMatrix(TSMatrix &M){
//創(chuàng)建一個三元組來表示矩陣M,同時做出各行第一個非零元的位置表
	int i,k;
	for(i=1;i<=MAXRC+1;i++)//M.rpos的初始化
		M.rpos[i]=0;
	printf("請輸入矩陣的行數(shù)，列數(shù)和非零元個數(shù)（以空格隔開）:");
	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)//查找同一行的元素,并使計數(shù)k累加
			k++;		
		} 
}

void AddSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C){
//實現(xiàn)C=A+B的功能,在主函數(shù)里已經(jīng)判定A與B的行列是相等的
	int k1,k2,temp,l;
	C.mu=A.mu;//C的行初始化
	C.nu=A.nu;//C的列初始化
	k1=k2=l=1;//用l表示C非零元的個數(shù)
	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的當(dāng)前元素插到C中
					C.data[l++]=A.data[k1++];
				else if(A.data[k1].j>B.data[k2].j)//A的列標大于B的列標,剛把B的當(dāng)前元素插到C中
					C.data[l++]=B.data[k2++];
				else{//A的列標和B的列標相等,則把兩矩陣的當(dāng)前的值相加,再判斷相加后的值是否為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當(dāng)前元素插入到C中
				C.data[l++]=A.data[k1++];
			else//A的行標大于B的行標,剛把B當(dāng)前元素插入到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){//實現(xiàn)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){
//實現(xiàn)C=A-B,先做B的負矩陣N=-B,再利用加法實現(xiàn)C=A+N=A-B
	TSMatrix N;
	ReverseSMatrix(B,N);
	AddSMatrix(A,N,C);
}
int MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &Q){
//實現(xiàn)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++)//當(dāng)前行各元素累加器清零
				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;//當(dāng)arow不小于A.mu時,tp表示A的全部非零元個數(shù)加1
			for(p=A.rpos[arow];p<tp;p++){//對當(dāng)前行arow中每一個非零元
				brow=A.data[p].j;//找到對應(yīng)元在B中對應(yīng)的行號
				if(brow<B.mu)	t=B.rpos[brow+1];//用t指示B的第brow+1行的第一個非零元的位置
				else	t=B.tu+1;//當(dāng)brow不小于B.mu時,t表示B的全部非零元個數(shù)加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){//行和列對應(yīng)的相等
				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();
}