稀疏矩阵运算器加减乘.cpp

以十字链表表示稀疏矩阵,实现两个矩阵的相加,相减,和相乘的运算.

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
#define OVERFLOW -1
#define OK 1
#define ERROR -2

typedef struct OLNode{
       int row,col;
       int e;
       struct OLNode *right,*down;}OLNode,*OLink;

typedef struct{
       OLink *rhead,*chead;
       int mu,nu,tu;}CrossList;


void CreateSMatrix(CrossList &R)
{
   int m,n,t,i,j,k,a;
   OLink p,q;
   if(R.rhead)
   {
	R.rhead=NULL;
	R.chead=NULL;
	R.mu=0;
	R.nu=0;
	R.tu=0;
   }
   printf("\n请输入稀疏矩阵的行数  列数  非零元个数:");
   
   scanf("%d %d %d",&m,&n,&t);
   R.mu=m;
   R.nu=n;
   R.tu=t;

   if(!(R.rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) exit(OVERFLOW);
   if(!(R.chead=(OLink *)malloc((n+1)*sizeof(OLink)))) exit(OVERFLOW);
   for(i=1;i<=R.mu+1;i++)
   {
	 R.rhead[i]=NULL;
     }
    for(i=1;i<=R.nu+1;i++)
   {
	 R.chead[i]=NULL;
     }

   for(k=1;k<=R.tu;k++)
   {
      printf("\n请输入第%d个非零元的行号 列号 非零元素值:",k);
     
      scanf("%d %d %d",&i,&j,&a);
      if(!(p=(OLNode *)malloc(sizeof(OLNode)))) exit(OVERFLOW);
      p->row=i;
      p->col=j;
      p->e=a;
      if(R.rhead[i]==NULL||R.rhead[i]->col>j)
      {
	  p->right=R.rhead[i];
	  R.rhead[i]=p;
      }
      else
      {
	 for(q=R.rhead[i];(q->right)&&q->right->col<j;q=q->right);
	 p->right=q->right;
	 q->right=p;
      }

      if(R.chead[j]==NULL||R.chead[j]->row>i)
      {
	 p->down=R.chead[j];
	 R.chead[j]=p;
      }
      else
      {
	  for(q=R.chead[j];(q->down)&&q->down->row<i;q=q->down);
	  p->down=q->down;
	  q->down=p;
      }
   }
}

void PrintSMatrix(CrossList R)
{
   int i,j;
   int b=0;
   OLink p;
   for(i=1;i<=R.mu;i++)
   {
      p=R.rhead[i];
      printf("\t\t\t\t|");
      for(j=1;j<=R.nu;j++)
	  {    if(p!=NULL){
	          if(j==p->col)
			  {
	            printf("%4d",p->e);
		        //if(p->right!=NULL)
	           p=p->right;
			  }//if
			  else
				  printf("%4d",b);}//if
	  
	 
	       else
	          printf("%4d",b);
	
        }//for
      printf("   |\n");
    
   }//for
}//printsmatrix

void AddSMatrix(CrossList &M,CrossList N)
{
       int i,j;
       OLink pm,pn,p,q;

       if(M.mu!=N.mu||M.nu!=N.nu)
       {
	   printf("这两个矩阵不能相加!\n");
	   exit(OVERFLOW);
       }
       for(i=1;i<=M.mu;i++)
       {
	    pm=M.rhead[i];
	    pn=N.rhead[i];
	    for(j=1;(pm||pn)&&j<=M.nu;j++)
	    {
	       if((pm||pn)&&((pm!=NULL&&j==pm->col)||(pn!=NULL&&j==pn->col)))
	       {
		     if((pm&&pn)&&(pm->col==pn->col))
			 {

			   pm->e+=pn->e;
			   if(pm->right!=NULL) pm=pm->right;
			   else pm=NULL;
			   if(pn->right!=NULL) pn=pn->right;
			   else pn=NULL;			    
			 }
			 else if((pn!=NULL)&&(pm==NULL||(j==pn->col&&j!=pm->col)))
			 {
		       if(!(p=(OLNode *)malloc(sizeof(OLNode)))) exit(OVERFLOW);
		       p->row=pn->row;
		       p->col=pn->col;
		       p->e=pn->e;
		       if(M.rhead[i]==NULL||M.rhead[i]->col>j)
		       {
			      p->right=M.rhead[i];
			      M.rhead[i]=p;
		       }
		       else
		       {
			      for(q=M.rhead[i];(q->right)&&q->right->col<j;q=q->right);
			      p->right=q->right;
			      q->right=p;
		       }

		       if(M.chead[j]==NULL||M.chead[j]->row>i)
		       {
			      p->down=M.chead[j];
			      M.chead[j]=p;
		       }
		       else
		       {
			      for(q=M.chead[j];(q->down)&&q->down->row<i;q=q->down);
			      p->down=q->down;
			      q->down=p;
		       }
                if(pn->right!=NULL)
		          pn=pn->right;
                else   pn=NULL;
		        M.tu++;
		   }
		   else if(pm->right!=NULL)
			   pm=pm->right;
		   else  pm=NULL;
	       }//if
	    }//for
       }//for
}//add

void SubSMatrix(CrossList &M,CrossList N)
{
       int i,j;
       OLink pm,pn,p,q;

       if(M.mu!=N.mu||M.nu!=N.nu)
       {
	   printf("这两个矩阵不能相减!\n");
	   exit(OVERFLOW);
       }
       for(i=1;i<=M.mu;i++)
       {
	    pm=M.rhead[i];
	    pn=N.rhead[i];
	    for(j=1;(pm||pn)&&j<=M.nu;j++)
	    {
	       if((pm||pn)&&((pm!=NULL&&j==pm->col)||(pn!=NULL&&j==pn->col)))
	       {
		     if((pm&&pn)&&(pm->col==pn->col))
			 {

			   pm->e-=pn->e;
			   if(pm->right!=NULL) pm=pm->right;
			   else pm=NULL;
			   if(pn->right!=NULL) pn=pn->right;else pn=NULL;			    
			 }
			 else if((pn!=NULL)&&(pm==NULL||(j==pn->col&&j!=pm->col)))
			 {
		       if(!(p=(OLNode *)malloc(sizeof(OLNode)))) exit(OVERFLOW);
		       p->row=pn->row;
		       p->col=pn->col;
		       p->e=0-(pn->e);
		       if(M.rhead[i]==NULL||M.rhead[i]->col>j)
		       {
			      p->right=M.rhead[i];
			      M.rhead[i]=p;
		       }
		       else
		       {
			      for(q=M.rhead[i];(q->right)&&q->right->col<j;q=q->right);
			      p->right=q->right;
			      q->right=p;
		       }

		       if(M.chead[j]==NULL||M.chead[j]->row>i)
		       {
			      p->down=M.chead[j];
			      M.chead[j]=p;
		       }
		       else
		       {
			      for(q=M.chead[j];(q->down)&&q->down->row<i;q=q->down);
			      p->down=q->down;
			      q->down=p;
		       }
                if(pn->right!=NULL)
		          pn=pn->right;
                else   pn=NULL;
		        M.tu++;
		   }
		   else if(pm->right!=NULL)
			   pm=pm->right;
		   else  pm=NULL;
	       }//if
	    }//for
       }//for
}//add


void MultSMatrix(CrossList M,CrossList N,CrossList &Q)
{
    int i,j,temp=0;
    OLink p,q,pm,pn,pq;
    Q.mu=M.mu;
    Q.nu=N.nu;
    Q.tu=0;

    if(M.nu!=N.mu)
    {
	printf("这两个矩阵不能相乘!");
	exit(OVERFLOW);
    }
    if(M.tu*N.tu!=0)
    {
	 for(i=1;i<=M.mu;i++)
	 {
	     for(j=1;j<=N.nu;j++)
	     {
		 temp=0;
		 pm=M.rhead[i];
		 pn=N.chead[j];

		 while(pm)
		 {
		     while(pn&&pm&&(pm->col>pn->row))
			 {if(pn->down!=NULL)
			  pn=pn->down;
			 else pn=NULL;
		     }

		     if((pm&&pn&&pm->col==pn->row))
		     {
			  temp+=(pm->e)*(pn->e);
			  if(pm->right!=NULL) pm=pm->right;
			          else pm=NULL;
			   if(pn->down!=NULL) pn=pn->down;
			   else pn=NULL;
		     }
		     else
			 {if(pm->right!=NULL) pm=pm->right;
			 else pm=NULL;}
			        
		 }//while(pm)
		 if(temp)
		 {
			if(!(pq=(OLNode *)malloc(sizeof(OLNode))))exit(OVERFLOW);

			pq->row=i;
			pq->col=j;
			pq->e=temp;
			if(Q.rhead[i]==NULL||Q.rhead[i]->col>j)
			{
			   pq->right=Q.rhead[i];
			   Q.rhead[i]=pq;
			}
			else
			{
			   for(q=Q.rhead[i];(q->right)&&q->col<j;q=q->right);
			   pq->right=q->right;
			   q->right=pq;
			}

			if(Q.chead[j]==NULL||Q.chead[j]->row>i)
			{
			   pq->down=Q.chead[j];
			   Q.chead[j]=pq;
			}
			else
			{
			   for(q=Q.chead[j];(q->down)&&q->row<i;q=q->down);
			   pq->down=q->down;
			   q->down=pq;
			}
			(Q.tu)++;
		 }//if temp
	     }//for j
	 }//for i
    }//for if
}//MultSMatrix()

void mainbody()
{
  
   int choi,m,i,n;
   CrossList M,N,Q;
   printf("\n\t\t\t***** 欢迎使用 !****\n\n");

   printf("*** 创建稀疏矩阵 M  ***\n");
   CreateSMatrix(M);
   printf("\t*** 稀疏矩阵M的通常阵列形式为:\n");
   PrintSMatrix(M);

   printf("\n\t*** 创建稀疏矩阵 N ***\n\n");
   CreateSMatrix(N);
   printf("\t*** 稀疏矩阵N的通常阵列形式为:\n");
   PrintSMatrix(N);

   printf("\n\t*********************************************************\n");
   printf("\t*\t1.加法\t2.减法\t3.乘法\t*\n");
   printf("\t*********************************************************\n");
   printf("\n请输入您所需的运算功能:\t");
   scanf("%d",&choi);
   printf("\n运算结果是:\n\n");
   switch(choi)
   {
      case 1:
      {
	  AddSMatrix(M,N);
	  PrintSMatrix(M);
	  break;
      }
      case 2:
      {
	  SubSMatrix(M,N);
	  PrintSMatrix(M);
	  break;
      }
      case 3:
      {
	  m=M.mu;
	  n=N.nu;

	  if(!(Q.rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) exit(OVERFLOW);
	  if(!(Q.chead=(OLink *)malloc((n+1)*sizeof(OLink)))) exit(OVERFLOW);

	  for(i=1;i<=((M.mu>N.nu)?(M.mu+1):(N.nu+1));i++)
	  {
		Q.rhead[i]=NULL;
		Q.chead[i]=NULL;
	  }

	  Q.mu=M.mu;
	  Q.nu=N.nu;
	  Q.tu=0;
	  MultSMatrix(M,N,Q);
	  PrintSMatrix(Q);
	  break;
      }
   }//switch
   
}//main
void main(){
    
    char c;
    do{
       mainbody();
       c=getchar();
       printf("是否继续/?(Y/N)");
       scanf("%c",&c);
      }while((c=='Y'||c=='y')&& (c=getchar()) );
}