sparsematrix final.cpp

稀疏矩阵运算器 对稀疏矩阵采用三元组存储

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

#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define INFEASIBLE   -1
#define OVERFLOW     -2

#define MAXSIZE 12500
#define MAXRC 5	          //注意rpos不要越界

typedef int Status;
typedef int ElemType;

typedef struct
{
	int i,j;
	ElemType e;

}Triple;

typedef struct
{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
	int mu,nu,tu;

}RLSMatrix;

Status InitSMatrix(RLSMatrix &M,RLSMatrix &N)
{
	int p,q,row,n[10],k,s;
	printf("输入第一个稀疏矩阵的非零元个数：");
	scanf("%d",&M.tu);
	printf("\n");
	printf("输入第一个稀疏矩阵的行数：");
	scanf("%d",&M.mu);
	printf("\n");
	printf("输入第一个稀疏矩阵的列数：");
	scanf("%d",&M.nu);
	printf("\n");
	printf("输入第一个稀疏矩阵:\n");
	for(p=1;p<=M.tu;p++)
	{
		printf("输入行号：");
	    scanf("%d",&M.data[p].i);
	    printf("输入列号：");
	    scanf("%d",&M.data[p].j);
	    printf("输入元素值：");
	    scanf("%d",&M.data[p].e);
	}
	printf("\n");
	printf("输入第二个稀疏矩阵的非零元个数：");
	scanf("%d",&N.tu);
	printf("\n");
	fflush(stdin);
	printf("输入第二个稀疏矩阵的行数：");
	scanf("%d",&N.mu);
	printf("\n");
	fflush(stdin);
	printf("输入第二个稀疏矩阵的列数：");
	scanf("%d",&N.nu);
	printf("\n");
	fflush(stdin);
	printf("输入第二个稀疏矩阵:\n");
	for(q=1;q<=N.tu;q++)
	{
		printf("输入行号：");
	    scanf("%d",&N.data[q].i);
	    printf("输入列号：");
	    scanf("%d",&N.data[q].j);
	    printf("输入元素值：");
	    scanf("%d",&N.data[q].e);
	}
	printf("\n");

	for(p=1;p<=M.mu;p++)
	{
	  n[p]=0;
	}
	for(p=1,s=1;p<=M.mu;p++)
	{
		if(M.data[s].i==p)
		{
			n[p]++;
		    if(s<=M.tu)
			{
				k=1;
			    while(k<=M.tu-s)
				{
					if(M.data[s].i==M.data[s+k].i)
					{
						n[p]++;  //记录i的重复次数
			 
					}
				  k++;
		  
				}	
				s+=n[p]; //s是每一次的开始计数位置
			}
		}
	}
	for(p=1;p<=M.mu;p++)
	{
		printf("%d ",n[p]);
	}	
	printf("\n");
	for(row=1,p=1;row<=M.mu;row++)
	{
		if(M.data[p].i==row)        //该行有非零元素
		{
			M.rpos[row]=p;
			p=p+n[row];
		}
	    else if(M.data[p].i!=row)
		{
		    p=p+n[row];
		    M.rpos[row]=p;
		}
		else if(M.data[p].i!=row && M.data[p-1].i!=row-1)  // 连续2行是0
		{
			p=p-1;
		}

	}
	M.rpos[1]=1;
	for(p=1;p<=M.mu;p++)
	{
		printf("%d ",M.rpos[p]);
	}
	printf("\n");

	for(q=1;q<=N.mu;q++)
	{
	    n[q]=0;
	}

	for(q=1,s=1;q<=N.mu;q++)
	{
		if(N.data[s].i==q)
		{
			n[q]++;
		    if(s<=N.tu)
			{
				k=1;
			    while(k<=N.tu-s)
				{
					if(N.data[s].i==N.data[s+k].i)
					{
						n[q]++;  //记录i的重复次数
					}
					k++;
				}	
				s+=n[q];        //s是每一次的开始计数位置
			}
		}
	}
	for(q=1;q<=N.mu;q++)
	{
	    printf("%d ",n[q]);
	}	
	printf("\n");
	
	for(row=1,q=1;row<=N.mu;row++)
	{
		if(N.data[q].i==row)        //该行有非零元素
		{
			N.rpos[row]=q;
		    q=q+n[row];
		}
	    else if(N.data[q].i!=row)
		{
		    q=q+n[row]; 
		    N.rpos[row]=q;
		}
	    else if(N.data[q].i!=row && N.data[q-1].i!=row-1)  // 连续2行是0
		{
		    q=q-1;
		}

	}
	N.rpos[1]=1;
	for(q=1;q<=N.mu;q++)
	{
		printf("%d ",N.rpos[q]);
	} 
	printf("\n");

	return OK;
}

Status PlusSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
	//稀疏矩阵相加
	int p,q=1;
	int arow,brow,ctemp[30],l,ccol,tp,t;
	if (M.nu != N.mu) 
	{
	  return ERROR;
	}
	Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0 ; // Q初始化
	if(M.tu*N.tu != 0) 
	{   
	// Q是非零矩阵
    for (arow=1; arow<=Q.mu; ++arow) 
	{ 
	  // 处理M的每一行
      for (l=1; l<=M.nu; ++l) 
	  {
		  ctemp[l] = 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) 
	  {   
		  ccol = M.data[p].j;            // 和元素在Q中列号
		  ctemp[ccol]+=M.data[p].e;
		  brow=M.data[p].i;              //找到对应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]+=N.data[q].e;

		  }
	  }
      for (ccol=1; ccol<=Q.nu; ++ccol) // 压缩存储该行非零元
	  {
		  if (ctemp[ccol]) 
		  { 
			  if (++Q.tu > MAXSIZE) return ERROR;
              Q.data[Q.tu].i=arow;
              Q.data[Q.tu].j=ccol;
              Q.data[Q.tu].e=ctemp[ccol];
		  } // if
	  }
    } // for arow
  } // if   
  return OK;
}

Status SubstractSMatrix(RLSMatrix M, RLSMatrix N,RLSMatrix &Q)
{
	//稀疏矩阵相减
	int p,q=1;
	int arow,brow,ctemp[30],l,ccol,tp,t;
	Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0 ; // Q初始化
	if (M.tu*N.tu != 0) 
	{   
	// Q是非零矩阵
    for (arow=1; arow<=Q.mu; ++arow) 
	{ 
	  // 处理M的每一行
      for (l=1; l<=M.nu; ++l) 
	  {
		  ctemp[l] = 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) 
	  {   
		  ccol = M.data[p].j;            // 和元素在Q中列号
		  ctemp[ccol]+=M.data[p].e;      //与加法的相同
		  brow=M.data[p].i;              //找到对应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]-=N.data[q].e;  //相比加法加号改为减号

		  }
	  }
      for (ccol=1; ccol<=Q.nu; ++ccol) // 压缩存储该行非零元
	  {
		  if (ctemp[ccol]) 
		  { 
			  if (++Q.tu > MAXSIZE) return ERROR;
              Q.data[Q.tu].i=arow;
              Q.data[Q.tu].j=ccol;
              Q.data[Q.tu].e=ctemp[ccol];
		  } // if
	  }
    } // for arow
  } // if   
  return OK;
}

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) 
{  

  // 求矩阵乘积Q=M*N，采用行逻辑链接存储表示
  int arow,brow,p,q,t,ctemp[30],l,ccol,tp;
  if (M.nu != N.mu) 
  {
	  return ERROR;
  }
  Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化
  if (M.tu*N.tu != 0) 
  {   
	// Q是非零矩阵
    for (arow=1; arow<=M.mu; ++arow) 
	{ 
	  // 处理M的每一行
      for (l=1; l<=M.nu; ++l) 
	  {
		  ctemp[l] = 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;            // 乘积元素在Q中列号
          ctemp[ccol] += M.data[p].e * N.data[q].e;
        } // for q
      } // 求得Q中第crow( =arow)行的非零元
      for (ccol=1; ccol<=Q.nu; ++ccol) // 压缩存储该行非零元
		if (ctemp[ccol]) 
		{ 
          if (++Q.tu > MAXSIZE) return ERROR;
          Q.data[Q.tu].i=arow;
          Q.data[Q.tu].j=ccol;
          Q.data[Q.tu].e=ctemp[ccol];

        } // if
    } // for arow
  } // if   
  return OK;
} // MultSMatrix



void SMatrixTraverse(RLSMatrix Q)
{
	int m,k,t,a[10][10];
	printf("Q的稀疏矩阵表示形式如下:\n");
	for(m=1;m<=Q.tu;m++)
	{
		printf("%d ",Q.data[m].e);
		printf("i:%d j:%d. \n",Q.data[m].i,Q.data[m].j);

	}
	printf("\n");
	//存入二维数组中
	for(k=1,m=1;k<=Q.mu;k++)
	{
		for(t=1;t<=Q.nu;t++)
		{
			if(k==Q.data[m].i && t==Q.data[m].j)
			{
				a[k][t]=Q.data[m].e;
				m++;
			}
			else 
			{
				a[k][t]=0;
			}
		
		}
	}
	printf("实际矩阵如下:\n");
	for(k=1;k<=Q.mu;k++)
	{
		for(t=1;t<=Q.nu;t++)
		{
			printf("%d ",a[k][t]);
		}
		printf("\n");
	}
	printf("\n");
	return;

}
void Choose()
{
	printf("功能选项:\n");
	printf("1.稀疏矩阵加法。\n");
	printf("2.稀疏矩阵减法。\n");
	printf("3.稀疏矩阵乘法。\n");
	printf("4.退出。\n");
	printf("请输入你选择执行的选项:"); 

}


void main()
{
	int i=-1;
	RLSMatrix M,N,Q;
	Choose();
	while(i!=0)
	{
		scanf("%d",&i);
		getchar();    //输入到缓冲区
		switch(i)
		{
		case 1: 
			InitSMatrix(M,N);
		    PlusSMatrix(M,N,Q);
    	    SMatrixTraverse(Q);
		    Choose();
		    break;
	    case 2:
		    InitSMatrix(M,N);
		    SubstractSMatrix(M,N,Q);
		    SMatrixTraverse(Q);
		    Choose();
		    break;
	    case 3:
		    InitSMatrix(M,N);
		    MultSMatrix(M,N,Q);
		    SMatrixTraverse(Q);
		    Choose();
		    break;
	    case 4:
		    return;  
	    default:                                        
            printf("\n对不起!你的输入结果不正确!请重新输入!\n");
		    printf("\n");
		}
	}
}