稀疏矩阵计算器.cpp

这是数据结构的课程设计。简单明了

#include "iostream.h"
#include "iomanip.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;           // i为行下标,j为列下标
  ElemType e;          //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 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 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 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 main()
{
inp: while(1)
 {  //system("cls");
	cout<<endl;
	cout<<"                              稀疏矩阵运算器                            \n"<<endl;
	cout<<"  ======================================================================"<<endl;
	cout<<"        加法—1    减法—2   乘法—3    退出—0      "<<endl;
	cout<<"  ======================================================================"<<endl;
   	char choice;
	cout<<endl<<"请选择要进行的操作(0-3):";
	cin>>choice;
	TSMatrix A,B,C;
  switch(choice)
  {  
	 case '1':
		    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 '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;}
			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 '3':
		    cout<<"创建矩阵A"<<endl;
	        create(A);
	        cout<<"创建矩阵B"<<endl;
	        create(B);
			if(A.mu!=B.nu&&A.nu!=B.mu)
			{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 '0':
		    cout<<" 谢谢您的使用!再见!"<<endl<<endl;
		    return ;
	 default:
		    cout<<" 错误的命令!"<<endl<<endl;
		    cout<<" Press any key to continue!"<<endl<<endl;
            getche();system("cls");		
  }
 }
}