📄 6830.cpp

📁 介绍有关稀疏矩阵的相关算法
💻 CPP
字号:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <values.h>

#define TRUE   1
#define FALSE  0
#define OK     1
#define ERROR  0

/*稀疏矩阵的三元组顺序表类型TSMatrix的定义*/
#define MAXSIZE 20    /*非零元个数最大值*/
#define MAXRC 10
typedef int Status;
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;

Status CreateSMatrix(TSMatrix &M)  /*创建一个稀疏矩阵*/
{int p=1,a,b,c,d;
printf("Please input number of rows,number of columns,element:");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
if(M.tu>MAXSIZE||M.tu<=0||M.tu>M.mu*M.nu)
  {printf("-----Input ERROR!!\n");return ERROR;}
while(p<=M.tu)
     {printf("Please input all information of number %d :",p);
     scanf("%d,%d,%d",&a,&b,&c);
     M.data[0].i=0;M.data[0].j=0;
     if(a<=M.mu&&b<=M.nu&&c!=0)
       {if(a>M.data[p-1].i||(a==M.data[p-1].i&&b>M.data[p-1].j))
	      {M.data[p].i=a;M.data[p].j=b;M.data[p].e=c;p++;}
	    else printf("-----Input ERROR\n");
       }
     else printf("-----Input ERROR\n");
     if(a==M.mu&&b==M.nu&&p<=M.tu){printf("-----Input ERROR\n");p=1;}
     }
printf("-----Input succeed!!\n");
return OK;
}


Status DestroySMatrix(TSMatrix &M)     /*销毁稀疏矩阵M*/
{M.mu=M.nu=M.tu=0;
printf("-----Destroy succeed!!\n");
return OK;
}

Status PrintMatrix(TSMatrix M)   /*输出一个矩阵*/
{int i,j,p=1;
if(M.tu==0){printf("-----Cannot find the matrix!!\n" );return ERROR;}
printf("---%d * %d---%d---\n",M.mu,M.nu,M.tu);
for(i=1;i<=M.mu;i++)
   {for(j=1;j<M.nu;j++)
       {if(i==M.data[p].i&&j==M.data[p].j)
	  {printf("%d     ",M.data[p].e);p++;}
	else printf("%d     ",0);
       }
    if(i==M.data[p].i&&j==M.data[p].j)
	  {printf("%d\n",M.data[p].e);p++;}
	else printf("%d\n",0);
   }
return OK;
}

Status CopySMatrix(TSMatrix M,TSMatrix &T)   /*由稀疏矩阵M复制得到矩阵T*/
{int p;
if(M.tu==0){printf("-----Cannot find the matrix!!\n" );return ERROR;}
for(p=1;p<=M.tu;p++)
   {T.data[p].i=M.data[p].i;
    T.data[p].j=M.data[p].j;
    T.data[p].e=M.data[p].e;
   }
T.mu=M.mu;T.nu=M.nu;T.tu=M.tu;
printf("-----Copy succeed!!\n");
return OK;
}


Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)    /*求稀疏矩阵的和Q=M+N*/
{int p=1,q=1,k=1;
if(M.tu==0||N.tu==0){printf("-----Cannot find matrix!!\n" );return ERROR;}
if(M.mu!=N.mu||M.nu!=N.nu){printf("-----Cannot calculate!!\n");return ERROR;}
while(p<=M.tu&&q<=N.tu)
     {if(M.data[p].i<N.data[q].i)
	{Q.data[k].i=M.data[p].i;
	 Q.data[k].j=M.data[p].j;
	 Q.data[k].e=M.data[p].e;
	 k++;p++;}
      else if(M.data[p].i>N.data[q].i)
	     {Q.data[k].i=N.data[q].i;
	      Q.data[k].j=N.data[q].j;
	      Q.data[k].e=N.data[q].e;
	      k++;q++;}
	    else if(M.data[p].j<N.data[q].j)
		    {Q.data[k].i=M.data[p].i;
		     Q.data[k].j=M.data[p].j;
		     Q.data[k].e=M.data[p].e;
		     k++;p++;}
		  else if(M.data[p].j>N.data[q].j)
			 {Q.data[k].i=N.data[q].i;
			  Q.data[k].j=N.data[q].j;
			  Q.data[k].e=N.data[q].e;
			  k++;q++;}
			else  {if(N.data[q].e+M.data[p].e==0){p++;q++;}
			       else {Q.data[k].i=N.data[q].i;
				     Q.data[k].j=N.data[q].j;
				     Q.data[k].e=N.data[q].e+M.data[p].e;
				     k++;p++;q++;}}
     }
while(p<=M.tu)
     {Q.data[k].i=M.data[p].i;
      Q.data[k].j=M.data[p].j;
      Q.data[k].e=M.data[p].e;
      k++;p++;}
while(q<=N.tu)
     {Q.data[k].i=N.data[q].i;
      Q.data[k].j=N.data[q].j;
      Q.data[k].e=N.data[q].e;
      k++;q++;}
Q.mu=M.mu;Q.nu=M.nu;Q.tu=k-1;
printf("-----Addition succeed!!\n");
return OK;
}


Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)        /*求稀疏矩阵的差Q=M-N*/
{int p=1,q=1,k=1;
if(M.tu==0||N.tu==0){printf("-----Cannot find matrix!!\n" );return ERROR;}
if(M.mu!=N.mu||M.nu!=N.nu){printf("-----Cannot calculate!!\n");return ERROR;}
while(p<=M.tu&&q<=N.tu)
     {if(M.data[p].i<N.data[q].i)
	{Q.data[k].i=M.data[p].i;
	 Q.data[k].j=M.data[p].j;
	 Q.data[k].e=M.data[p].e;
	 k++;p++;}
      else if(M.data[p].i>N.data[q].i)
	     {Q.data[k].i=N.data[q].i;
	      Q.data[k].j=N.data[q].j;
	      Q.data[k].e=-1*N.data[q].e;
	      k++;q++;}
	    else if(M.data[p].j<N.data[q].j)
		    {Q.data[k].i=M.data[p].i;
		     Q.data[k].j=M.data[p].j;
		     Q.data[k].e=M.data[p].e;
		     k++;p++;}
		  else if(M.data[p].j>N.data[q].j)
			 {Q.data[k].i=N.data[q].i;
			  Q.data[k].j=N.data[q].j;
			  Q.data[k].e=-1*N.data[q].e;
			  k++;q++;}
			else  {if(M.data[p].e-N.data[q].e==0){p++;q++;}
			       else {Q.data[k].i=N.data[q].i;
				     Q.data[k].j=N.data[q].j;
				     Q.data[k].e=M.data[p].e-N.data[q].e;
				     k++;p++;q++;}}
     }
while(p<=M.tu)
     {Q.data[k].i=M.data[p].i;
      Q.data[k].j=M.data[p].j;
      Q.data[k].e=M.data[p].e;
      k++;p++;}
while(q<=N.tu)
     {Q.data[k].i=N.data[q].i;
      Q.data[k].j=N.data[q].j;
      Q.data[k].e=-1*N.data[q].e;
      k++;q++;}
Q.mu=M.mu;Q.nu=M.nu;Q.tu=k-1;
printf("-----Subtration succeed!!\n");
return OK;
}


Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)    /*求稀疏矩阵的积Q=M*N  */
{ int arow,brow,p,q,ccol,ctemp[MAXRC+1],t,tp,k=1;
  if(M.tu==0||N.tu==0){printf("-----Cannot find matrix!!\n" );return ERROR;}
  if(M.nu!=N.mu) {printf("-----Cannot multiplication!!\n" );return ERROR;}
for(p=1;p<=M.tu;p++)         /*为M.rpos[]	赋值*/ 
   {if(M.data[p].i==k)
	    {M.rpos[k]=p;
	    k++;}
	  else if(M.data[p].i>k)
	    {M.rpos[k]=p--;
	    k++;}
	}
for(;k<=M.mu;k++)M.rpos[k]=M.tu;
k=1;
for(q=1;q<=N.tu;q++)       /* 为N.rpos[]赋值*/
	 {if(N.data[q].i==k)
	    {N.rpos[k]=q;k++;}
	  else if(N.data[q].i>k)
	    {N.rpos[k]=p--;k++;}
	 }
for(;k<=N.mu;k++)N.rpos[k]=N.tu;
  Q.mu=M.mu;               /*初始化Q*/
  Q.nu=N.nu;
  Q.tu=0;
  for(arow=1;arow<=M.mu;++arow)
     {for(ccol=1;ccol<=N.nu;ccol++)
	 ctemp[ccol]=0;
      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;
	  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]+=M.data[p].e*N.data[q].e;
	     }
	 }
     for(ccol=1;ccol<=Q.nu;++ccol)      /*将数组的值压缩储存到Q*/
	    {if(ctemp[ccol]!=0)      
	    {Q.tu++;
	    if(Q.tu>MAXSIZE) {printf("-----ERROR!!\n");return ERROR;}
		Q.data[Q.tu].i=arow;
		Q.data[Q.tu].j=ccol;
		Q.data[Q.tu].e=ctemp[ccol];}
	 }
  }
  printf("-----Multiplication succeed!!\n");
  return OK;
}



Status TransposeSMatrix(TSMatrix M,TSMatrix &T)    /*求稀疏矩阵M的转置矩阵T*/
{int p,q,k=1;
if(M.tu==0){printf("-----Cannot find the matrix!!\n" );return ERROR;}
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
for(p=1;p<=M.nu;p++)
   {for(q=1;q<=M.tu;q++)
       {if(M.data[q].j==p)
	  {T.data[k].i=M.data[q].j;
	   T.data[k].j=M.data[q].i;
	   T.data[k].e=M.data[q].e;
	   k++;}
       }
   }
printf("-----Transpose succeed!!\n");
return OK;
}

void Show()
{printf("*****************************************************************\n");
printf("============>>1.Create SMatrix A\n");
printf("============>>2.Create SMatrix B\n");
printf("============>>3.Print Matrix A\n");
printf("============>>4.Print Matrix A\n");
printf("============>>5.Print Matrix C\n");
printf("============>>6.Copy SMatrix A->B\n");
printf("============>>7.SMatrix A+B=C\n");
printf("============>>8.SMatrix A-B=C\n");
printf("============>>9.Transpose SMatrix A->B\n");
printf("============>>10.Destroy SMatrix A\n");
printf("============>>11.SMatrix A*B=C\n");
printf("*****************************************************************\n");
}

void main()
{int select;
TSMatrix A,B,C;
A.tu=0;B.tu=0;C.tu=0;
Show();
while(1)
{
printf("Input your choose: ");
      scanf("%d",&select);
if(select==0)break;
switch(select) {
    
	 case 1: CreateSMatrix(A);
	      break;
	 case 2: CreateSMatrix(B);
	      break;
	 case 3: PrintMatrix(A);
	      break;
     case 4: PrintMatrix(B);
	      break;
     case 5: PrintMatrix(C);
          break;
     case 6: CopySMatrix(A,B);
          break;     
     case 7: AddSMatrix(A,B,C);
          break;
     case 8: SubtSMatrix(A,B,C);
          break;
     case 9: TransposeSMatrix(A,B);
          break;
     case 10: DestroySMatrix(A);
          break;
     case 11: MultSMatrix(A,B,C);
          break;
     default:printf("Input ERROR!!\n");
          break;
		}
}
 }
💿 文件大小 3 K
👤 上传用户 jipigu
📂 所属分类数值算法/人工智能
🏷️ 相关标签

#稀疏 #矩阵 #算法
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -