xishujuzhen.cpp

稀疏矩阵程序

#include<stdio.h>
#include<malloc.h>

#define max 20
#define maxrc 20
#define exit 0
#define ok 1
typedef struct{
	int i,j;
	int e;
}Triple;
typedef struct{
	Triple data[max+1];
	int rpos[maxrc+1];
	int mu,nu,tu;
}RLSmatrix;
/*----------------------------------------------------------------------------*/
ScanfRLSMatrix(RLSmatrix *T)
{//矩阵输入函数，输入各行非零元及其在矩阵中的行列数
	int k;
	int record=T->mu;
	printf(" ***********************************************************\n");
	printf(" 请输入矩阵的行数，列数，非零元素个数 \n");
	printf(" ");
	scanf("%d,%d,%d",&(*T).mu,&(*T).nu,&(*T).tu);
	if((*T).tu>max){printf("非零个数超出定义范围！");exit(0);}
	for(k=1;k<=(*T).tu;k++){
		printf(" 按行存储请输入第%d个非零元素的行数,列数,其值:",k);
		scanf("%d,%d,%d",&(*T).data[k].i,&(*T).data[k].j,&(*T).data[k].e);
		if(!(*T).data[k].i||!(*T).data[k].j||(*T).data[k].i>(*T).mu||(*T).data[k].j>(*T).nu){
			printf("输入有误！");
			exit(0);
		}

}
	printf(" ************************************************************\n");
	//计算各行第一个非零元素在存储数组中的位置
	//若该行无非零元，则rpos[]值为零
	int *num=(int *)malloc(((*T).mu+1)*sizeof(int));
	int row;
	int *cpot=(int *)malloc(((*T).mu+1)*sizeof(int));
	cpot[1]=1;
	(*T).rpos[1]=1;
	for(k=1;k<=(*T).mu;k++)
		num[k]=0;
	for(k=1;k<=(*T).tu;k++)
		++num[(*T).data[k].i];
	for(row=2;row<=(*T).mu;row++)
		cpot[row]=cpot[row-1]+num[row-1];
	for(row=1;row<=(*T).mu;row++){
		(*T).rpos[row]=cpot[row];
	}
	for(k=T->tu+1;k<=record;k++){
		T->data[k].e=0;T->data[k].i=T->data[k].j=0;
	}
	return 0;
}

PrintRLSMatrix(RLSmatrix T)
{//矩阵输出函数，输出矩阵形式
	int a,b,m=0;
	printf(" -----------------------------------------\n");
	for(a=1;a<=(T).mu;a++){printf(" ");
	for(b=1;b<=(T).nu;b++){
		if((T).rpos[a]&&a==(T).data[(T).rpos[a]].i&&b==(T).data[(T).rpos[a]].j){
			//(T).rpos[a]不为零时，输出该行的非零元
			printf("%4d",(T).data[(T).rpos[a]].e);
			(T).rpos[a]++;
		}
		else
		{
			printf("%4d",m);}
	}
	printf("\n");
	}
	printf(" ----------------------------------------\n");
	return 0;
}
int ADD(RLSmatrix M,RLSmatrix N,RLSmatrix *Q){
	// 求稀疏矩阵的和Q=M+N 
	int k,p,q;
	if(M.mu!=N.mu||M.nu!=N.nu) exit;
	(*Q).mu=M.mu;
	(*Q).nu=M.nu;
	(*Q).tu=0;
	M.rpos[M.mu+1]=M.tu+1; // 为方便后面的while循环临时设置 
	N.rpos[N.mu+1]=N.tu+1;
	for(k=1;k<=M.mu;++k) // 对于每一行，k指示行号 
	{
		(*Q).rpos[k]=(*Q).tu+1;
		p=M.rpos[k]; // p指示M矩阵第k行当前元素的序号 
		q=N.rpos[k]; // q指示N矩阵第k行当前元素的序号 
		// 当某一行不存在非零元素时，它对应的非零位置表的值为下一个非零元素的位置
		while(p<M.rpos[k+1]&&q<N.rpos[k+1]) // 故当某行非零元位置等于下一行非零元位置时，它不存在非零元素
		{ // M,N矩阵均有第k行元素未处理 
			if(M.data[p].j==N.data[q].j) // M矩阵当前元素和N矩阵当前元素的列相同 
			{
				(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e; // 位置相同
				if((*Q).data[(*Q).tu+1].e!=0) //相加结果为0?
				{
					++(*Q).tu;
					(*Q).data[(*Q).tu].i=k;
					(*Q).data[(*Q).tu].j=M.data[p].j;
				}
				++p;
				++q;
			}
			else if(M.data[p].j<N.data[q].j)
			{ // M矩阵当前元素的列<N矩阵当前元素的列
				++(*Q).tu;
				(*Q).data[(*Q).tu].e=M.data[p].e;
				(*Q).data[(*Q).tu].i=k;
				(*Q).data[(*Q).tu].j=M.data[p].j;
				++p;
			}
			else // M矩阵当前元素的列>N矩阵当前元素的列 
			{
				++(*Q).tu;
				(*Q).data[(*Q).tu].e=N.data[q].e;
				(*Q).data[(*Q).tu].i=k;
				(*Q).data[(*Q).tu].j=N.data[q].j;
				++q;
			}
		}
		while(p<M.rpos[k+1]) // M矩阵还有k行的元素未处理 
		{
			++(*Q).tu;
			(*Q).data[(*Q).tu].e=M.data[p].e;
			(*Q).data[(*Q).tu].i=k;
			(*Q).data[(*Q).tu].j=M.data[p].j;
			++p;
		}
		while(q<N.rpos[k+1]) //N矩阵还有k行的元素未处理 
		{
			++(*Q).tu;
			(*Q).data[(*Q).tu].e=N.data[q].e;
			(*Q).data[(*Q).tu].i=k;
			(*Q).data[(*Q).tu].j=N.data[q].j;
			++q;
		}
	}
	return ok;
}
int SubtS(RLSmatrix M,RLSmatrix N,RLSmatrix *Q){ /* 求稀疏矩阵的差Q=M-N */
	int i;
	if(M.mu!=N.mu||M.nu!=N.nu) exit;
	for(i=1;i<=N.tu;++i) /* 对于N的每一元素,其值乘以-1 */
		N.data[i].e*=-1;
	ADD(M,N,Q); /* Q=M+(-N) */
	return ok;
}
int Mult(RLSmatrix M,RLSmatrix N,RLSmatrix *Q){
	if(M.nu!=N.mu)
		exit;
	int t,ccol,tp,brow;
	(*Q).mu=M.mu;
	(*Q).nu=N.nu;
	(*Q).tu=0;
	if(M.tu*N.tu!=0){
		for(int arow=1;arow<=M.mu;++arow){ 
			int T[max+1]={0};          
			(*Q).rpos[arow]=(*Q).tu+1; 
			if(arow<M.mu)
				tp=M.rpos[arow+1];
			else
				tp=M.tu+1;
			for(int p=M.rpos[arow];p<tp;++p){         //处理M的一行
				brow=M.data[p].j;  //对当前行中每一个非零元找到对应元在N中的行号
			//	if((N.rpos[brow]!=N.rpos[brow-1])||(N.rpos[brow]<N.tu)){
					if(brow<N.mu)
						t=N.rpos[brow+1];
					else
						t=N.tu+1;
					for(int q=N.rpos[brow];q<t;++q){
						ccol=N.data[q].j;
						T[ccol]+=M.data[p].e*N.data[q].e;
					}   //得到Q的一行，即M中一行和N中每一列分别累乘相加，结果存在数组T[ccol]中
			//	}
			}   //求得Q中第crow（=arow）行的非零元
			for(ccol=1;ccol<=(*Q).nu;++ccol)    //压缩存储该行非零元
				if(T[ccol]){
					if((*Q).tu>max+1)
						exit;
					(*Q).data[(*Q).tu+1].i=arow;
					(*Q).data[(*Q).tu+1].j=ccol;
					(*Q).data[(*Q).tu+1].e=T[ccol];   //(arow,ccol,T[ccol]);
					(*Q).tu++;
				}
		}
	}
	return ok;
}
/*--------------------------------------------------------------------------------*/
void main() 
{ 
	RLSmatrix M,N,Q; 
	char ch; 
	printf(" *************************** \n"); 
	printf(" ** ** \n"); 
    printf(" ** 稀疏矩阵运算器 ** \n"); 
    printf(" ** --------------------- ** \n"); 
    printf(" *************************** \n"); 
    printf(" _____________________________________________________________________ \n"); 
    printf(" | A.加法 B.减法 C.乘法  Y.继续运算 N.结束运算 | \n"); 
    printf(" |_____________________________________________________________________| \n\n"); 
    printf("\2 输入数字时请用逗号隔开！\n\n"); 
    printf(" ->"); 
    scanf("%c",&ch); 
	while(ch!='N'){//进行循环运算 
		switch(ch){//进行运算选择 
		case'A':{ printf(" 请输入要求和的两个矩阵：\n\n"); 
			printf(" 输入第一个矩阵：\n\n"); 
			ScanfRLSMatrix(&M); 
			printf(" 输入的第一个矩阵为：\n\n"); 
			PrintRLSMatrix(M); 
			printf(" 输入第二个矩阵：\n\n"); 
			ScanfRLSMatrix(&N); 
			printf(" 输入的第二个矩阵为：\n\n"); 
			PrintRLSMatrix(N); 
			ADD(M,N,&Q); 
			printf(" 两矩阵之和为：\n\n"); 
			PrintRLSMatrix(Q); 
			printf(" 是否继续运算（Y/N）？\n\n"); 
			printf(" ->"); 
			ch=getchar(); 
				};
			break; 
		case'B':{ printf(" 请按次序输入要求差的两个矩阵：\n\n"); 
			printf(" 输入第一个矩阵：\n\n"); 
			ScanfRLSMatrix(&M); 
			printf(" 输入的第一个矩阵为：\n\n"); 
			PrintRLSMatrix(M); 
			printf(" 输入第二个矩阵：\n\n"); 
			ScanfRLSMatrix(&N); 
			printf(" 输入的第二个矩阵为：\n\n"); 
			PrintRLSMatrix(N); 
			SubtS(M,N,&Q); 
            printf(" 两矩阵之差为：\n\n"); 
            PrintRLSMatrix(Q); 
            printf("是否继续运算（Y/N）？\n\n"); 
            printf(" ->"); 
            ch=getchar(); 
				}
			break; 
		case'C':{printf(" 请按次序输入要求积的两个矩阵：\n\n"); 
			printf(" 输入第一个矩阵：\n\n"); 
            ScanfRLSMatrix(&M); 
            printf(" 输入的第一个矩阵为：\n\n"); 
            PrintRLSMatrix(M); 
            printf(" 输入第二个矩阵：\n\n"); 
            ScanfRLSMatrix(&N); 
            printf(" 输入的第二个矩阵为：\n\n"); 
            PrintRLSMatrix(N); 
            Mult(M,N,&Q); 
            printf(" 两矩阵之积为：\n\n"); 
            PrintRLSMatrix(Q); 
            printf("是否继续运算（Y/N）？\n\n"); 
            printf(" ->"); 
            ch=getchar(); 
				}
			break; 

		case'Y':{
			printf("请选择运算\n"); 
			printf(" _____________________________________________________________________ \n"); 
			printf(" | A.加法 B.减法 C.乘法  Y.继续运算 N.结束运算 | \n"); 
			printf(" |_____________________________________________________________________| \n\n"); 
			printf("\2 输入数字时请用逗号隔开！\n\n");
            printf(" ->"); 
            ch=getchar(); 
				}
			break; 
		default:printf("->");ch=getchar();break; 
		} 
	} 
	printf(" 运算结束！\n\n"); 
	printf(" \1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1谢谢使用!\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\n\n");
}