juzhen.cpp

利用三元组完成距阵的基本运算,包括加法,减法,乘法.数据结构实习题目

#include <stdio.h>
#include <string.h>
#include<iostream.h>
#include<iomanip.h>
#include<math.h>
#include<malloc.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

#define Maxsize 20

typedef int Status;
typedef int ElemType;
typedef struct {
  int    i,j; // 行下标,列下标
  ElemType e; // 非零元素值
}Triple;
typedef struct  {
  Triple data[Maxsize+1]; // 非零元三元组表,data[0]未用
  int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;
Status CreateSMatrix(TSMatrix &M)
 { // 创建稀疏矩阵M
   int i,m,n;
   ElemType e;
   Status k;
   printf("请输入矩阵的行数,列数,非零元素数：");
   scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
   if(M.tu>Maxsize)
     return ERROR;
   M.data[0].i=0; // 为以下比较顺序做准备
   for(i=1;i<=M.tu;i++)
   {
     do
     {
       printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值:",i,M.mu,M.nu);
       scanf("%d,%d,%d",&m,&n,&e);
       k=0;
       if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围
         k=1;
       if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错
         k=1;
     }while(k);
     M.data[i].i=m;
     M.data[i].j=n;
     M.data[i].e=e;
   }
  return OK;
}
 void DestroySMatrix(TSMatrix &M)
 { // 销毁稀疏矩阵M
   M.mu=M.nu=M.tu=0;
 }
 void TransposeSMatrix(TSMatrix M,TSMatrix &T)
 { // 求稀疏矩阵M的转置矩阵T。
   int p,q,col;
   T.mu=M.nu;
   T.nu=M.mu;
   T.tu=M.tu;
   if(T.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;
         }
   }
 }
void PrintSMatrix(TSMatrix M)
{ // 输出稀疏矩阵M
   int i;
   printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
   printf("行   列    元素值\n");
   for(i=1;i<=M.tu;i++)
     printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
}
void PrintSMatrix1(TSMatrix M)
{ // 按矩阵形式输出M
   int i,j,k=1;
   Triple *p=M.data;
   p++; // p指向第1个非零元素
   for(i=1;i<=M.mu;i++)
   {
     for(j=1;j<=M.nu;j++)
       if(k<=M.tu&&p->i==i&&p->j==j) // p指向非零元，且p所指元素为当前处理元素
       {
         printf("%3d",p->e); // 输出p所指元素的值
         p++; // p指向下一个元素
         k++; // 计数器+1
       }
       else // p所指元素不是当前处理元素
         printf("%3d",0); // 输出0
     printf("\n");
   }
}
int comp(int c1,int c2)
{ // AddSMatrix函数要用到，另加
   if(c1<c2)
     return -1;
   if(c1==c2)
     return 0;
   return 1;
}
 Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
 { /* 求稀疏矩阵的和C=M+B */
   int m=1,n=1,q=0;
   if(A.mu!=B.mu||A.nu!=B.nu) /* A、B两稀疏矩阵行或列数不同 */
     return ERROR;
   C.mu=A.mu;
   C.nu=A.nu;
   while(m<=A.tu&&n<=B.tu) /* 矩阵A和B的元素都没处理完 */
   {
     switch(comp(A.data[m].i,B.data[n].i))
     {
       case -1: C.data[++q]=A.data[m++]; /* 将矩阵A的当前元素值赋给矩阵C */
		break;
       case  0: switch(comp(A.data[m].j,B.data[n].j)) /* A、B矩阵当前元素的行相等,继续比较列 */
		{
		  case -1: C.data[++q]=A.data[m++];
			   break;
		  case  0: C.data[++q]=A.data[m++]; /* A、B矩阵当前非零元素的行列均相等 */
			   C.data[q].e+=B.data[n++].e; /* 矩阵A、B的当前元素值求和并赋给矩阵C */
			   if(C.data[q].e==0) /* 元素值为0，不存入压缩矩阵 */
			     q--;
			   break;
		  case  1: C.data[++q]=B.data[n++];
		}
		break;
       case  1: C.data[++q]=B.data[n++]; /* 将矩阵B的当前元素值赋给矩阵C */
     }
   }
   while(m<=A.tu) /* 矩阵B的元素全部处理完毕 */
     C.data[++q]=A.data[m++];
   while(n<=B.tu) /* 矩阵A的元素全部处理完毕 */
     C.data[++q]=B.data[n++];
   C.tu=q; /* 矩阵C的非零元素个数 */
   if(q>Maxsize) /* 非零元素个数太多 */
     return ERROR;
   return OK;
 }

Status MulTSM(TSMatrix M,TSMatrix N,TSMatrix &Q)
 { // 求稀疏矩阵的乘积Q=M×N
   int i,j;
   ElemType *Nc,*Tc;
   TSMatrix T; // 临时矩阵
   if(M.nu!=N.mu)
     return ERROR;
   T.nu=M.mu; // 临时矩阵T是Q的转秩矩阵
   T.mu=N.nu;
   T.tu=0;
   Nc=(ElemType*)malloc((N.mu+1)*sizeof(ElemType)); // Nc为矩阵N一列的临时数组(非压缩,[0]不用)
   Tc=(ElemType*)malloc((M.nu+1)*sizeof(ElemType)); // Tc为矩阵T一行的临时数组(非压缩,[0]不用)
   if(!Nc||!Tc) // 创建临时数组不成功
     exit(ERROR);
   for(i=1;i<=N.nu;i++) // 对于N的每一列
   {
     for(j=1;j<=N.mu;j++)
       Nc[j]=0; // 矩阵Nc的初值为0
     for(j=1;j<=M.mu;j++)
       Tc[j]=0; // 临时数组Tc的初值为0，[0]不用
     for(j=1;j<=N.tu;j++) // 对于N的每一个非零元素
       if(N.data[j].j==i) // 属于第i列
	 Nc[N.data[j].i]=N.data[j].e; // 根据其所在行将其元素值赋给相应的Nc
     for(j=1;j<=M.tu;j++) // 对于M的每一个值
       Tc[M.data[j].i]+=M.data[j].e*Nc[M.data[j].j]; // Tc中存N的第i列与M相乘的结果
     for(j=1;j<=M.mu;j++)
       if(Tc[j]!=0)
       {
         T.data[++T.tu].e=Tc[j];
         T.data[T.tu].i=i;
         T.data[T.tu].j=j;
       }
   }
   if(T.tu>Maxsize) // 非零元素个数太多
     return ERROR;
   TransposeSMatrix(T,Q); // 将T的转秩赋给Q
   DestroySMatrix(T); // 销毁临时矩阵T
   free(Tc); // 释放动态数组Tc和Nc
   free(Nc);
   return OK;
 }

void PrintInterface()
{//打印用户办面
	cout<<"                  ====================================*"<<endl;
	cout<<"                  *  稀疏矩阵运算器                   *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  *         设计者；                  *"<<endl;
	cout<<"                  *         班级：                    *"<<endl;
	cout<<"                  *         学号：                    *"<<endl;
   	cout<<"                  *                                   *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  ====================================*"<<endl;
}
void PrintOperation()
{
	cout<<"   ====================================================================*"<<endl;
	cout<<"   * 请输入你需要的运算方式:                                           *"<<endl;
	cout<<"   *                                                                   *"<<endl;
	cout<<"   *    a:两稀疏矩阵相加。  　m:两稀疏矩阵相乘。　                     *"<<endl;
    cout<<"   *    s:两稀疏矩阵相减。　  q:退出                                   *"<<endl;
	cout<<"   ====================================================================*"<<endl;

}
main()
{
    PrintInterface();
	TSMatrix A,B,C;
    PrintOperation();
	char again='y',w;
	while(again=='y')
	{
		char ch;
		ch=getchar();
		switch(ch)
		{
		case 'a': 

				cout<<"创建第一个矩阵A:"<<endl;
				CreateSMatrix(A);
				
				PrintSMatrix1(A);
				cout<<"创建第一个矩阵B:"<<endl;
				CreateSMatrix(B);
			
				PrintSMatrix1(B);
				cout<<"矩阵A+B="<<endl;
				AddTSM(A,B,C);
				PrintSMatrix1(C);
				break;
		case 's':   cout<<"创建第一个矩阵A:"<<endl;
					CreateSMatrix(A);
					
					PrintSMatrix1(A);
					cout<<"创建第一个矩阵B:"<<endl;
					CreateSMatrix(B);
					
					PrintSMatrix1(B);
				int i;
				for(i=1;i<=B.tu;i++)
				{
					int c=0;
					c-=B.data[i].e;
					B.data[i].e=c;
				}
				cout<<"矩阵A-B="<<endl;
				AddTSM(A,B,C);
				PrintSMatrix1(C);
				
				break;
		case'm': 
					cout<<"创建第一个矩阵A:"<<endl;
				CreateSMatrix(A);
				
				PrintSMatrix1(A);
				cout<<"创建另一个矩阵B:"<<endl;
				CreateSMatrix(B);
				
				PrintSMatrix1(B);
				MulTSM(A,B,C);
				cout<<"矩阵A*B="<<endl;
				PrintSMatrix1(C);
				break;
		case 'q':return 0;
		default:
		printf("\n你需要进行其他运算吗？(y/n):");
		scanf("%c",&again);
		w=getchar();
		PrintOperation();
		}
	    
	}
  
	return OK;
}