稀疏矩阵.c

数据结构中关于稀疏矩阵的一个具体实现

#include<stdio.h>
#include<stdlib.h>
#define MAX 10;
typedef struct 
 {
	int i,j;
	int e;
}Triple1;
typedef struct
 {
    Triple1 data[11];//data[0]未用
	int rpos[11];
	int mu,nu,tu;
}TSMatrix1;
TSMatrix1 Creat()//创建三元组形式的矩阵
{
	TSMatrix1 *T1;

	int i=1,j=1,e=1,mu=0,nu=0,k=1,a[11]={0};
	T1=(TSMatrix1 *)malloc(sizeof(TSMatrix1));
	if(!T1) exit(0);
	printf("请输入矩阵的行数，列数:\n");
	scanf("%d%d",&mu,&nu);
    getchar();//接收回车
	T1->mu=mu;
	T1->nu=nu;
	printf("请输入矩阵的三元组，以0 0 0标志输入结束\n");//因为节点的值不可能为0，故以输入0 0 0为输入结束标志
	while(1)
	{
		scanf("%d%d%d",&i,&j,&e);
		getchar();
		if(e==0) break;//若输入值为0，则输入结束
		(*T1).data[k].i=i;
		(*T1).data[k].j=j;
		(*T1).data[k].e=e;
		++k;
	}//while 
	T1->tu=k-1;//T1含有k-1各非零元
    for(i=1;i<k;i++)
		a[T1->data[i].i]++;
	T1->rpos[1]=1;
	for(j=2;j<=T1->mu;j++)//求T1中每行起始元素的地址
		T1->rpos[j]=T1->rpos[j-1]+a[j-1];
	return (*T1);
}//Creat
TSMatrix1 Jiafa(TSMatrix1 A,TSMatrix1 B)//加法
{
   TSMatrix1 T;
   Triple1 *a,*b;
   int t=1,i=0,j=0,c[11]={0};
   if(A.mu!=B.mu || A.nu!=B.nu)
   {
	   printf("出错: 两个矩阵的行数或列数不相等!\n");
	   exit(1);
   }
   a=A.data;
   a++;
   b=B.data;
   b++;//这个算法就是让a，b代替A.data[n]和B.data[n]执行相加
   while(1)//内置循环结束条件，即其中一个矩阵已经遍历完成
   {
	   if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
	  
	   while(a->i==b->i)//行号相同
	   {
		   if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
		  
		   if(a->j < b->j)//a的列号小，则将a赋给T.data[]
		   {
			   T.data[t].i=a->i;
			   T.data[t].j=a->j;
			   T.data[t].e=a->e;
			   t++;
			   a++;
		   }//if
		   else if(a->j > b->j)//b的列号小，则将b赋给T.data[]
		   {
			   T.data[t].i=b->i;
			   T.data[t].j=b->j;
			   T.data[t].e=b->e;
			   t++;
			   b++;
		   }//else if
		   else//两者列号相同，则相加后的值不为零，则将相加后的值赋给T.data[]，否则继续
		   {
			   if(a->e+b->e)
			   {
			     T.data[t].i=a->i;
			     T.data[t].j=a->j;
			     T.data[t].e=a->e+b->e;
			     t++;
				 a++;
			     b++;
			   }
			   else
			   {
				   a++;
				   b++;
			   }

		   }//else
	   }//while =
	
	   
	   while(a->i < b->i)//若a的行号小，则将a赋给T.data[]
	   {
		  if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
          T.data[t].i=a->i;
		  T.data[t].j=a->j;
          T.data[t].e=a->e;
		  t++;
		  a++;
	   }//while <

	  
	  while(a->i > b->i)//b的行号小，则将b赋给T.data[]
	  {
		  if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
		  T.data[t].i=b->i;
		  T.data[t].j=b->j;
		  T.data[t].e=b->e;
		  t++;
		  b++;
	  }//while >


   }//while a b
   if(a!=&A.data[A.tu+1])//若矩阵A没有遍历完，则将剩下的赋给T.data[]
	   while(1)
	   {
		  if(a==&A.data[A.tu+1]) break;
		  T.data[t].i=a->i;
		  T.data[t].j=a->j;
		  T.data[t].e=a->e;
		  t++;
		  a++;
	   }//while 
   if(b!=&B.data[B.tu+1])//若矩阵B没有遍历完，则将剩下的赋给T.data[]
	   while(1)
	   {
		  if(b==&B.data[B.tu+1]) break;
		  
		    T.data[t].i=b->i;
		    T.data[t].j=b->j;
			T.data[t].e=b->e;
		    t++;
		    b++;
		  
	
	   }//while 
	T.mu=A.mu;
    T.nu=A.nu;
	T.tu=t-1;
	for(i=1;i<t;i++)//求出三元组矩阵的每行起始地址
		c[T.data[i].i]++;
	T.rpos[1]=1;
	for(j=2;j<=T.mu;j++)
		T.rpos[j]=T.rpos[j-1]+c[j-1];
	return T;
}//Jiafa
TSMatrix1 Jianfa(TSMatrix1 A,TSMatrix1 B)//减法，基本算法同加法一致
{
   TSMatrix1 T;
   Triple1 *a,*b;
   int t=1,i=0,j=0,c[11]={0};
   if(A.mu!=B.mu || A.nu!=B.nu)
   {
	   printf("出错: 两个矩阵的行数或列数不相等!\n");
	   exit(1);
   }
   a=A.data;
   a++;
   b=B.data;
   b++;
   while(1)
   {
	   if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
	  
	   while(a->i==b->i)
	   {
		   if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
		   if(a->j < b->j)
		   {
			   T.data[t].i=a->i;
			   T.data[t].j=a->j;
			   T.data[t].e=a->e;
			   t++;
			   a++;
		   }//if
		   else if(a->j > b->j)
		   {
			   T.data[t].i=b->i;
			   T.data[t].j=b->j;
			   T.data[t].e=-(b->e);
			   t++;
			   b++;
		   }//else if
		   else//若行号列号均相同
		   {
			   if(a->e-b->e)//此处判断条件为若相减后的值不为0，则赋给T.data[]
			   {
			     T.data[t].i=a->i;
			     T.data[t].j=a->j;
			     T.data[t].e=a->e-b->e;
			     t++;
				 a++;
			     b++;
			   }
			   else
			   {
				   a++;
				   b++;
			   }

		   }//else
	   }//while =
	
	   
	   while(a->i < b->i)
	   {
		  if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
          T.data[t].i=a->i;
		  T.data[t].j=a->j;
          T.data[t].e=a->e;
		  t++;
		  a++;
	   }//while <

	  
	  while(a->i > b->i)
	  {
		  if(a==&A.data[A.tu+1] || b==&B.data[B.tu+1]) break;
		  T.data[t].i=b->i;
		  T.data[t].j=b->j;
		  T.data[t].e=-(b->e);
		  t++;
		  b++;
	  }//while >


   }//while a b
   if(a!=&A.data[A.tu+1])
	   while(1)
	   {
		  if(a==&A.data[A.tu+1]) break;
		  T.data[t].i=a->i;
		  T.data[t].j=a->j;
		  T.data[t].e=a->e;
		  t++;
		  a++;
	   }//while 
   if(b!=&B.data[B.tu+1])
	   while(1)
	   {
		  if(b==&B.data[B.tu+1]) break;
		  
		    T.data[t].i=b->i;
		    T.data[t].j=b->j;
			T.data[t].e=-(b->e);
		    t++;
		    b++;
		  
	
	   }//while 
	T.mu=A.mu;
    T.nu=A.nu;
	T.tu=t-1;
	for(i=1;i<t;i++)
		c[T.data[i].i]++;
	T.rpos[1]=1;
	for(j=2;j<=T.mu;j++)
		T.rpos[j]=T.rpos[j-1]+c[j-1];
	return T;
}
TSMatrix1 Chengfa(TSMatrix1 A,TSMatrix1 B)//乘法
{
	TSMatrix1 T;//T 用来接收相乘后的矩阵
    int r=0,tp=1,t=0,c=0,tp2=0,q=0,c1=0;
	if(A.nu!=B.mu)//出错判断
	{
		printf("出错：第一个矩阵的行数不等于第二个矩阵的列数\n");
		exit(0);
	}
	T.mu=A.mu;
	T.nu=B.nu;
	T.tu=0;
	for(r=1;r<=A.mu;++r)//r作为矩阵的行
	{
		int ctemp[11]={0};//作为每行中第i列的累加器，每次先初始化为0
		T.rpos[r]=T.tu+1;//T中第r行的起始地址
		if(r<A.mu) tp=A.rpos[r+1];//tp为A下一行的起始地址
		else tp=A.tu+1;
		for(t=A.rpos[r];t<tp;t++)
		{
		    c=A.data[t].j;//第t个三元组的列号
			if(c<B.mu) tp2=B.rpos[c+1];//tp2为B中c行下一行的起始地址
			else tp2=B.tu+1;
			for(q=B.rpos[c];q<tp2;q++)//找出B中行号为c（即A中当前三元组的行号）的三元组，然后将每找到的
			{                         //三元组值与A中但前三元组的值相乘后的值暂时存放在ctemp[c1]中   
				c1=B.data[q].j;
				ctemp[c1]+=A.data[t].e*B.data[q].e;//累加
			}//for q
		}//for t
		for(c1=1;c1<=T.nu;c1++)//	ctemp[c1]赋给T矩阵第r行第r列元素
			if(ctemp[c1])
			{
				T.tu++;
				T.data[T.tu].i=r;
				T.data[T.tu].j=c1;
				T.data[T.tu].e=ctemp[c1];
			}
		
	}//for r
	return T;
}

TSMatrix1 Zhuanzhi(TSMatrix1 T1)//矩阵的转置
{
	TSMatrix1 T2;//接收转置后的矩阵
	int a[10]={0},b[10]={0},k=1,t,c,q=0;
	T2.mu=T1.nu;
	T2.nu =T1.mu;
	T2.tu =T1.tu;
	for(;k<T1.tu+1;k++)
	{
		a[T1.data[k].j]++;//求T1中每列含几个元素即为T2中每行有几个元素
	}//for i
	b[1]=1;
	for(t=2;t<T1.nu+1;t++)
	{
		b[t]=b[t-1]+a[t-1];//求出T2中每行起始位置 对应T1中每列起始位置
	}//for t
	for(c=1;c<=T1.tu;c++)//对于T1中第c个元素找到它在T2中的位置b[t],然后将这个元素写入T2
	{
		t=T1.data[c].j;
		q=b[t];
		T2.data[q].i=T1.data[c].j;
		T2.data[q].j=T1.data[c].i;
		T2.data[q].e=T1.data[c].e;
		b[t]++;//加1作为t行元素的下一个位置
	}//for c
	for(k=1;k<T1.nu+1;k++)
    T2.rpos[k]=b[k];
	return T2;
}//Zhuanzhi
void Printf_TSM(TSMatrix1 T)//输出矩阵
{
	int k=1,a=1,b=1,t=0;
	for(a=1;a<T.mu+1;a++)
	{
		for(b=1;b<T.nu+1;b++)
		{
			if(T.data[k].i==a && T.data[k].j==b)
			{
				printf("%-5d",T.data[k].e);
				k++;
			}//if
			else
				printf("%-5d", t);
		}
		putchar('\n');
	}
	return;
}//Printf_TSM
void main()
{
	TSMatrix1 M,N,Q;//构造三个矩阵
	int choose;//choose用来选择作何种运算
    while(1)//由 switch 中case 0 为结束标志
	{
		printf("请选择何种运算:\n1:加法\n2:减法\n3:乘法\n4:转置\n0:退出程序\n");
		scanf("%d",&choose);//选择做何种运算
		switch(choose)
		{
		case 1: printf("请输入第一个矩阵的相关信息:\n");//此为加法
			    M=Creat();
				printf("你输入的第一个矩阵为:\n");
                Printf_TSM(M);
				printf("请输入第二个矩阵的相关信息:\n");
				N=Creat();
				printf("你输入的第二个矩阵为:\n");
				Printf_TSM(N);
				Q=Jiafa(M,N);//相加函数，附给Q
				printf("相加后的矩阵为：\n");
				Printf_TSM(Q);//输出相加后的矩阵
				break;
		case 2: printf("请输入第一个矩阵的相关信息:\n");//此为减法
			    M=Creat();
				printf("你输入的第一个矩阵为:\n");
                Printf_TSM(M);
				printf("请输入第二个矩阵的相关信息:\n");
				N=Creat();
				printf("你输入的第二个矩阵为:\n");
                Printf_TSM(N);
				Q=Jianfa(M,N);//相减函数
				printf("相减后的矩阵为：\n");
				Printf_TSM(Q);
				break;
		case 3: printf("请输入第一个矩阵的相关信息:\n");//相乘
			    M=Creat();
				printf("你输入的第一个矩阵为:\n");
                Printf_TSM(M);
				printf("请输入第二个矩阵的相关信息:\n");
				N=Creat();
				printf("你输入的第二个矩阵为:\n");
                Printf_TSM(N);
				Q=Chengfa(M,N);//相乘函数
				printf("相乘后的矩阵为：\n");
				Printf_TSM(Q);
				break;
		case 4: printf("请输入矩阵的相关信息:\n");//转置
			    M=Creat();
				printf("你要转置的矩阵为:\n");
                Printf_TSM(M);
                Q=Zhuanzhi(M);//转置函数
				printf("转换后的矩阵为：\n");
				Printf_TSM(Q);
				break;
		case 0: 
			   printf("欢迎下次使用本程序———再见!\n");exit(0);//退出程序开关

		}//switch
	    
	}//while 1
   
}