稀疏矩阵计算器.cpp

用三元组表示稀疏矩阵,可以转置 加法

#include "iomanip.h"
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"

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

typedef int Status ;
typedef int ElemType;

#define MAXSIZE 100 // 非零元个数的最大值
#define SIZENUM 10
typedef struct {
  int    i,j; // 行下标,列下标
  ElemType e; // 非零元素值
}Triple;
 
typedef struct  {
  Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
  int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;

void create(TSMatrix &TM);
     //创建矩阵
void disp(TSMatrix TM);
     //通常形式输出稀疏矩阵
Status LocateELem(TSMatrix M,int i,int j,int e);
     //三元组表中是否存在非零元素A[i][j]，若存在返回e
void InsertSortMatrix(TSMatrix &TM);
     //根据对矩阵的行列，三元组TM作直接插入排序
Status TransposeSMatrix(TSMatrix M,TSMatrix &T);
     //矩阵转置的算法
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);
     //矩阵的加法运算:C=A+B
Status SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C);
     //矩阵的减法运算:C=A-B
Status MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);
     //矩阵的乘法运算:C=A×B
void NiMatrix(TSMatrix &TM);
     //矩阵求逆


//--------------------创建矩阵----------------//
void create(TSMatrix &TM)
{ int i,j,i1,j1,n,e;
  cout<<"矩阵的行数、列数、非零元个数(mu,nu,tu)：";
  cin>>i>>j>>n;
  TM.mu=i;TM.nu=j;TM.tu=0;
 if(TM.mu<1||TM.nu<1)
	 cout<<"输入有误!!!!"<<endl; 
 for(int k=1;k<=n;k++)
	{
	 cout<<"第"<<k<<"个元素行、列、值(i,j,e):";
	 cin>>i1>>j1>>e;
     
     if(i1>TM.mu||j1>TM.nu||e==0)
	 {cout<<"输入有误!!!!"<<endl; k--;}
	 
	 else if(LocateELem(TM,i1,j1,e)==1)
	 {cout<<"元素已经存在!"<<endl; k--;;
	 }
	 else
	 {
	 TM.data[k].i=i1;TM.data[k].j=j1;TM.data[k].e=e;TM.tu++;
	 }
	}

 InsertSortMatrix(TM);    
}

Status LocateELem(TSMatrix M,int i,int j,int e)
//三元组表中是否存在非零元素A[i][j]，若存在返回e
{int k;
 for(k=1;k<=M.tu;k++)
  if(M.data[k].i==i&&M.data[k].j==j)
   {e=M.data[k].e; return TRUE;}

 return FALSE;   
}

void InsertSortMatrix(TSMatrix &TM)
//根据对矩阵的行列，三元组TM作直接插入排序
{
int i,j;
for(i=2;i<=TM.tu;i++)
 if(TM.data[i].i<TM.data[i-1].i||TM.data[i].i==TM.data[i-1].i&&TM.data[i].j<TM.data[i-1].j)
  {TM.data[0].i=TM.data[i].i;
   TM.data[0].j=TM.data[i].j;
   TM.data[0].e=TM.data[i].e;
 for(j=i-1;TM.data[0].i<TM.data[j].i||TM.data[0].i==TM.data[j].i&&TM.data[0].j<TM.data[j].j;--j)
	{TM.data[j+1].i=TM.data[j].i;
     TM.data[j+1].j=TM.data[j].j;
     TM.data[j+1].e=TM.data[j].e;
	 }
   TM.data[j+1].i=TM.data[0].i;
   TM.data[j+1].j=TM.data[0].j;
   TM.data[j+1].e=TM.data[0].e;
 }		 

}


//----------------通常形式输出稀疏矩阵----------------//
void disp(TSMatrix TM)
{ int i,j,k,flag=1;
  for(i=1;i<=TM.mu;i++)
  { cout<<setw(6);
    for(j=1;j<=TM.nu;j++)
	{for(k=1;k<=TM.tu;k++)
		   if(i==TM.data[k].i&&j==TM.data[k].j)
		   {cout<<TM.data[k].e<<setw(6);flag=0;}
	if(flag) cout<<"0"<<setw(6);
	flag=1;
	}
	cout<<endl;
  }
}

  //--------------矩阵转置的算法---------------//
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ int col,p,q;
  T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
  if(M.tu)
  {q=1;
    for(col=1;col<=M.nu;col++)
		for(p=1;p<=M.tu;p++)
			if(M.data[p].j==col)
			{ T.data[q].i=M.data[p].j;
			  T.data[q].j=M.data[p].i;
			  T.data[q].e=M.data[p].e; 
			  ++q;
			}
  }
  return OK;
}

//-------------------矩阵加算法----------------/
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵加法: C=A+B */
{
    int n=1,m=1,k=1;
  ElemType  temp;
  if(A.mu==B.mu&&A.nu==B.nu)
  {
  while(m<=A.tu&&n<=B.tu)
//若A当前元素的行号等于B当前元素的行号，则比较其列号，将较小列的元素
//存入C中，如果列号也相等，则将对应的元素值相加后存入C中
    if(A.data[m].i==B.data[n].i)
        {   if(A.data[m].j<B.data[n].j)
            {C.data[k].i=A.data[m].i;
                 C.data[k].j=A.data[m].j;
                 C.data[k].e=A.data[m].e;
                 k++;m++;
                }
             else if(A.data[m].j>B.data[n].j)
        {C.data[k].i=B.data[n].i;
         C.data[k].j=B.data[n].j;
         C.data[k].e=B.data[n].e;
         k++;n++;
        } 
         else 
        { temp=A.data[m].e+B.data[n].e;
          if(temp!=0)//不为0才添加到C中
         {C.data[k].i=A.data[m].i;
          C.data[k].j=A.data[m].j;
          C.data[k].e=temp;
                  k++;
          }
         m++;n++;
        }
    }
//若A当前元素的行号小于B当前元素的行号，则将A的元素存入C中
   else if(A.data[m].i<B.data[n].i)
      {C.data[k].i=A.data[m].i;
       C.data[k].j=A.data[m].j;
       C.data[k].e=A.data[m].e;
       k++;m++;
      }
//若A当前元素的行号大于B当前元素的行号，则将B的元素存入C中
   else
     {C.data[k].i=B.data[n].i;
      C.data[k].j=B.data[n].j;
      C.data[k].e=B.data[n].e;
      k++;n++;
     }
//把剩余部分元素存入C中
if(m>A.tu&&n<=B.tu)
  for( ;n<=B.tu;n++)
    {C.data[k].i=B.data[n].i;
     C.data[k].j=B.data[n].j;
     C.data[k].e=B.data[n].e;
     k++;
    }
if(n>B.tu&&m<=A.tu)
  for( ;m<=A.tu;m++)
    {C.data[k].i=A.data[m].i;
     C.data[k].j=A.data[m].j;
     C.data[k].e=A.data[m].e;
      k++;
    }   
C.mu=A.mu;
C.nu=A.nu;
C.tu=k-1;
return OK;
  }
  else return ERROR;
}

//------------------矩阵的减法运算----------------//
Status SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵减法: C=A+B */
{
  int n=1,m=1,k=1;
  ElemType  temp;
  if(A.mu==B.mu&&A.nu==B.nu)
  {
  while(m<=A.tu&&n<=B.tu)
//若A当前元素的行号等于B当前元素的行号，则比较其列号，将较小列的元素
//存入C中，如果列号也相等，则将对应的元素值相减后存入C中
  { if(A.data[m].i==B.data[n].i)
        {if(A.data[m].j<B.data[n].j)
           {C.data[k].i=A.data[m].i;
                 C.data[k].j=A.data[m].j;
                 C.data[k].e=A.data[m].e;
                 k++;m++;
                }
        else if(A.data[m].j>B.data[n].j)
		{C.data[k].i=B.data[n].i;
         C.data[k].j=B.data[n].j;
         C.data[k].e=-B.data[n].e;
         k++;n++;
        } 
         else 
        { temp=A.data[m].e-B.data[n].e;
          if(temp!=0)//不为0才添加到C中
         {C.data[k].i=A.data[m].i;
          C.data[k].j=A.data[m].j;
          C.data[k].e=temp;
                  k++;
          }
         m++;n++;
        }
      }
//若A当前元素的行号小于B当前元素的行号，则将A的元素存入C中
   else if(A.data[m].i<B.data[n].i)
      {C.data[k].i=A.data[m].i;
       C.data[k].j=A.data[m].j;
       C.data[k].e=A.data[m].e;
       k++;m++;
      }
//若A当前元素的行号大于B当前元素的行号，则将B的元素存入C中
   else
     {C.data[k].i=B.data[n].i;
      C.data[k].j=B.data[n].j;
      C.data[k].e=-B.data[n].e;
      k++;n++;
     }
  }
//把剩余部分元素存入C中
if(m<=A.tu)
  for( ;m<=A.tu;m++)
    {C.data[k].i=A.data[m].i;
     C.data[k].j=A.data[m].j;
     C.data[k].e=A.data[m].e;
      k++;
    }  

if(n<=B.tu)
  for( ;n<=B.tu;n++)
    {C.data[k].i=B.data[n].i;
     C.data[k].j=B.data[n].j;
     C.data[k].e=-B.data[n].e;
     k++;
    }
 
C.mu=A.mu;
C.nu=A.nu;
C.tu=k-1;
return OK;
  }
  else return ERROR;
}


int value(TSMatrix T,int i,int j)
//得到T[i][j]的值
{ int k;
 for(k=1;k<=T.tu;k++)
	 if(T.data[k].i==i&&T.data[k].j==j)
		 return T.data[k].e;
return 0;
}
//-------------------矩阵乘法运算的算法-------------//
Status MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)
{ int i,j,k,sum,p=1;
	for(i=1;i<=A.mu;i++)
		for(j=1;j<=B.nu;j++)
		{ sum=0;
		   for(k=1;k<=A.nu;k++)
			   sum+=value(A,i,k)*value(B,k,j);
		   if(sum!=0)
		   { C.data[p].i=i;
		     C.data[p].j=j;
			 C.data[p].e=sum;
			 p++;
		   }
		}
  C.mu=A.mu;
  C.nu=B.nu;
  C.tu=p-1;
 return OK;
}

//JsMatrix()函数用于计算行列式,通过递归算法实现
int JsMatrix(int s[][SIZENUM],int n) 
{ int z,j,k,r,total=0; 
  int b[SIZENUM][SIZENUM];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/ 
  if(n>2) 
  {	 for(z=0;z<n;z++) 
	  {for(j=0;j<n-1;j++) 
         for(k=0;k<n-1;k++) 
           if(k>=z) b[j][k]=s[j+1][k+1]; 
           else b[j][k]=s[j+1][k]; 
           if(z%2==0) r=s[0][z]*JsMatrix(b,n-1);  /*递归调用*/ 
           else  r=(-1)*s[0][z]*JsMatrix(b,n-1); 
        total=total+r; 
  } 
  } 
 else if(n==2) total=s[0][0]*s[1][1]-s[0][1]*s[1][0]; 
 return total; 
} 


void N1Matrix(int s[][SIZENUM],float b[][SIZENUM],int n) 
//N1Matrix()函数用于求原矩阵各元素对应的余子式，存放在数组b[n][n]中，定义为float型
{int z,j,k,l,m,g,a[SIZENUM][SIZENUM]; 
 for(z=0;z<n;z++) 
   {l=z; 
    for(j=0;j<n;j++) 
	{ m=j; 
     for(k=0;k<n-1;k++) 
      for(g=0;g<n-1;g++) 
	  { if(g>=m&&k<l) a[k][g]=s[k][g+1]; 
        else if(k>=l&&g<m)  a[k][g]=s[k+1][g]; 
        else if(k>=l&&g>=m) a[k][g]=s[k+1][g+1]; 
        else a[k][g]=s[k][g]; 
	  } 
      b[z][j]=JsMatrix(a,n-1); 
	} 
   } 
} 


//-------------------矩阵求逆------------------------//
void NiMatrix(TSMatrix &TM)
{ int i,j,n,k; n=TM.mu;
  float temp; 
  int a[SIZENUM][SIZENUM];
  float b[SIZENUM][SIZENUM],c[SIZENUM][SIZENUM];

  for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
		  a[i][j]=0;
  for(i=1;i<=TM.tu;i++)
	  a[TM.data[i].i-1][TM.data[i].j-1]=TM.data[i].e;

  k=JsMatrix(a,n);
  cout<<"矩阵的行列式的值: |A|="<<k<<endl;

  if(k==0) cout<<"行列式的值|A|=0,原矩阵无逆矩阵!!"<<endl;
  else
  { N1Matrix(a, b,n);
   //调用N1Matrix()函数，得到原矩阵各元素对应的"余子式",存放在数组b[n][n]中

    for(i=0;i<n;i++) //求代数余子式，此时b[n][n中存放的为原矩阵各元素对应的"代数余子式"
     for(j=0;j<n;j++) 
          if((i+j)%2!=0 && b[i][j]!=0) b[i][j]=-b[i][j]; 

	for(i=0;i<n;i++) //对b[N][N]转置,此时b[n][n]中存放的为原矩阵的伴随矩阵
     for(j=i+1;j<n;j++) 
	 {temp=b[i][j]; 
      b[i][j]=b[j][i]; 
      b[j][i]=temp; 
	 }

   cout<<"伴随矩阵A*:"<<endl;
   for(i=0;i<n;i++)// 打印伴随矩阵A* 
   {cout<<setw(6);
    for(j=0;j<n;j++) 
     cout<<b[i][j]<<setw(6);
	cout<<endl;
   }

  for(i=0;i<n;i++)   //求逆矩阵，此时c[n][n]中存放的是原矩阵的逆矩阵
   for(j=0;j<n;j++) 
     c[i][j]=b[i][j]/k;

  cout<<"逆矩阵(A*)/|A|:"<<endl;
  for(i=0;i<n;i++)// 打印逆矩阵 
   {cout<<setw(6);
    for(j=0;j<n;j++) 
    cout<<c[i][j]<<setw(6);
	cout<<endl;
   }	
 }//else
 
}
     


void main()
{
inp: while(1)
 {  //system("cls");
	cout<<endl;
	cout<<"                              稀疏矩阵计算器                            \n"<<endl;
	cout<<"    班级：计算机科学与技术02（8）班   学生：陈 堪   学号：200209124204     "<<endl;
	cout<<"  ======================================================================"<<endl;
	cout<<"     转置—1    加法—2     减法—3    乘法—4   求逆—5   退出—0      "<<endl;
	cout<<"  ======================================================================"<<endl;
    cout<<"测试数据为:A:(1,3,4),(2,2,4),(2,4,3),(3,3,9) A.mu=5,A.nu=5,A.tu=4."<<endl;
	cout<<"           B:(2,3,4),(2,4,5)                 B.mu=5,B.nu=5,B.tu=2."<<endl;


	char choice;
	cout<<endl<<"请选择操作(0-5):";
	cin>>choice;
	TSMatrix A,B,C;
  switch(choice)
  {  case '1':
            cout<<"创建矩阵A"<<endl;
	        create(A);
	        TransposeSMatrix(A,B);
	        cout<<"矩阵A:"<<endl;disp(A);
			cout<<"转置矩阵A:"<<endl;disp(B);
			cout<<" Press any key to continue!"<<endl<<endl;
            getche();system("cls");
	        goto inp;
	
	 case '2':
		    cout<<"创建矩阵A"<<endl;
	        create(A);
	        cout<<"创建矩阵B"<<endl;
	        create(B);
			if(A.mu!=B.mu||A.nu!=B.nu)
			{	cout<<"两个矩阵的行、列数不匹配运算规则"<<endl;
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;}
			AddTSM(A,B,C);
			cout<<"矩阵A:"<<endl;disp(A);
			cout<<"矩阵B:"<<endl;disp(B);
            cout<<"矩阵C=A+B:"<<endl;disp(C);
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;
		
	 case '3':
		    cout<<"创建矩阵A"<<endl;
	        create(A);
	        cout<<"创建矩阵B"<<endl;
	        create(B);
			if(A.mu!=B.mu||A.nu!=B.nu)
			{cout<<"两个矩阵的行、列数不匹配运算规则"<<endl;
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;}
			SubTSM(A,B,C);
			cout<<"矩阵A:"<<endl;disp(A);
			cout<<"矩阵B:"<<endl;disp(B);
            cout<<"矩阵C=A-B:"<<endl;disp(C);
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;
		
	 case '4':
		    cout<<"创建矩阵A"<<endl;
	        create(A);
	        cout<<"创建矩阵B"<<endl;
	        create(B);
			if(A.mu!=B.nu)
			{cout<<"两个矩阵的行、列数不匹配运算规则"<<endl;
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;}
			MultSMatrix(A,B,C);
			cout<<"矩阵A:"<<endl;disp(A);
			cout<<"矩阵B:"<<endl;disp(B);
            cout<<"矩阵C=A*B:"<<endl;disp(C);
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;
		
	 case '5':
		    cout<<"创建矩阵A"<<endl;
	        create(A);
			cout<<"矩阵A:"<<endl;disp(A);
			if(A.mu!=A.nu)
			{cout<<"两个矩阵的行、列数不匹配运算规则"<<endl;
			cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;}

            NiMatrix(A);
		    cout<<" Press any key to continue!"<<endl<<endl;
			getche();system("cls");
	        goto inp;
	 case '0':
		    cout<<" 谢谢使用!再见!"<<endl<<endl;
		    return ;
	 default:
		    cout<<" 错误命令!"<<endl<<endl;
		    cout<<" Press any key to continue!"<<endl<<endl;
            getche();system("cls");		
  }
 }
}