//* * * * * * * * * * * * * * * * * * * * * * * * * * * *
//数据结构课程实验	实验二  利用三元组表实现矩阵相加    *
//03计本3班										        *
// 樊海军 2B0324151138									*
//矩阵+矩阵=新矩阵，新矩阵-》三元组表			        *
//* * * * * * * * * * * * * * * * * * * * * * * * * * * *

#include <stdio.h>
#include <stdlib.h> 
#include <iostream.h>
#include <time.h>   
#define MAXSIZE 1000//非零元素个数的最大值
#define PAUSE 	cout<<"回车键继续……";cin.get()

typedef struct	
{
	int row,col;//非零元素的行下标和列下标
	int e;//非零元素的值
}Triple;

typedef struct
{
	Triple data[MAXSIZE+1];   //非零元素的三元组表，data[0]未用
	int mu,nu,tu;//矩阵的行数、列数和非零元素个数
} TSMatrix;

int in_row;			//全局变量：输入的矩阵行数
int in_col;			//全局变量：输入的矩阵列数
int na=0,nb=0,nc=0;		//三矩阵中非○元素个数

void CmdList()			//显示命令列表
{
	printf("_____________________________________________\n");
	printf("		请输入S运行,输入Q退出!\n");
	printf("______________________________________________\n");

}

int **init_Array(int l)				//此函数网上得来
{   int i=0,j=0;
	int **pp; 						//动态分配一个二维数组pp内存空间,其类型为int pp,指向该数组 

	srand (time (0));
	pp=new int *[in_row];			//动态分配in_row个类型为int *的内存空间,分配的是行地址空间 

	for(i=0;i<in_row;i++) 
		pp[i]= new int[in_col];		//动态分配in_col个类型为int的内存空间,分配的是某行的数值空间 

	for (i=0;i<in_row;i++)
		for (j=0;j<in_col;j++)
		{
			if (l==0)				//参数为0，则全置0，为第三个矩阵初值
			{
				pp[i][j]=0;
			}
				else
			{
				int aa=rand()*l%100;
				pp[i][j]=aa>=50?0:aa-25;	//生成的数据若大于50则将其改为0，否则减去25，
											//只是为了使0出现的次数多些，还有数值小些
			}
		}
		return(pp);
}

TSMatrix *init_T(int **ppa,int n)				//根据参数n指定的非0元素个数将pa指向的矩阵数组转换为三元组形式
{	
	TSMatrix *pt;
	pt=(TSMatrix *)malloc(sizeof(TSMatrix));
	for (int i=1;i<=n;)		//两矩阵中非0元素的个数
		for (int j=0;j<in_row;j++)				
			for (int k=0;k<in_col;k++)
			{
				if (ppa[j][k]!=0)
				{
					pt->data[i].row=j+1;						//因为两种数组表示不同：一个是从0开始，一个是从1开始
					pt->data[i].col=k+1;
					pt->data[i].e=ppa[j][k];
					i++;
				}
			}	
	pt->mu=in_row;
	pt->nu=in_col;
	pt->tu=n;
	return(pt);
}

void TSMatrixDisp(TSMatrix *pt,int n)				//显示三元组
{	
	printf("   i   j  data\n");
	printf("   ___________\n");
	for (int i=1;i<=n;i++)
	{
		printf("%4d%4d%5d\n",pt->data[i].row,pt->data[i].col,pt->data[i].e);
	}	
	printf("%4d%4d%5d\n",pt->mu,pt->nu,pt->tu);
	printf("   ___________\n");

}

void ArrayDisp(int **A)					//根据指向数组的指针将数组用矩阵形式显示出来
{   int i=0,j=0;
	for (i=0;i<in_row;i++)
		{
			for (j=0;j<in_col;j++)
				printf("%4d",A[i][j]);	
			printf("\n");
		}
}

void Add_M(int **pa,int **pb,int **pc)		//矩阵相加
{
	   int i=0,j=0;
	   for (i=0;i<in_row;i++)
		   for (j=0;j<in_col;j++)
		   {
			   pc[i][j]=pa[i][j]+pb[i][j];
		   }
}

void ReadCommand(char &c)
{
	do {c=getchar();}
	while (c!='q'&&c!='Q'&&c!='S'&&c!='s');
}

void Interpret(char &c)
{
	int **pa,**pb,**pc;	
	TSMatrix *pta,*ptb,*ptc;
	int l[2];
	int i=0,j=0;
	srand (time (0));
	for (i=0;i<2;i++)//生成随机参数
		l[i]=rand();
	switch(c)
	{
	case 'S':
	case 's':
		printf("请输入矩阵的行数(0--20):\n"); 
		scanf("%d",&in_row);
		while(in_row<=0 || in_row>20){
			printf("错误！请重新输入矩阵的行数(0--20):\n"); 
			scanf("%d",&in_row);
		}

		printf("请输入矩阵的列数(0--20):\n"); 
		scanf("%d",&in_col);
		while(in_col<=0 || in_col>20){
			printf("错误！请重新输入矩阵的列数(0--20):\n"); 
			scanf("%d",&in_col);
		}
		printf("新建矩阵行数：%d   列数:%d\n",in_row,in_col); 
		printf("______________________________________________\n");
		printf("第一步.随机产生可相加的两个矩阵\n\n"); 
		
		printf("	随机建立数组矩阵A…………\n");
		pa=init_Array(l[0]);//传入一个int型以随机得到矩阵A
		ArrayDisp(pa);

		PAUSE;


		printf("	随机建立数组矩阵B…………\n");
		pb=init_Array(l[1]);//传入一个int型以随机得到矩阵B
		ArrayDisp(pb);
		
		PAUSE;
		
		printf("	建立初值为0的数组矩阵C…………\n");
		pc=init_Array(0);//传入一个int型以随机得到矩阵B
		ArrayDisp(pc);
		
		PAUSE;
		printf("______________________________________________\n");
		printf("第二步.用三元组表存储矩阵\n\n");
		na=nb=nc=0;									//非0元素个数置0，否则下次运行时将累加而出现错误！
		for (i=0;i<in_row;i++)						//两矩阵中非0元素的个数
			for (j=0;j<in_col;j++)
			{
				if (pa[i][j]!=0)na++;
				if (pb[i][j]!=0)nb++;
			}

		pta=init_T(pa,na);
		ptb=init_T(pb,nb);
		ptc=init_T(pc,nc);
		printf("______________________________________________\n");

		printf("	矩阵A的三元组表示：\n");
		TSMatrixDisp(pta,na);
		printf("______________________________________________\n");		
		PAUSE;

		printf("	矩阵B的三元组表示：\n");
		TSMatrixDisp(ptb,nb);
		printf("______________________________________________\n");
		PAUSE;
		
		printf("	矩阵C的三元组表示：\n");
		TSMatrixDisp(ptc,nc);
		printf("______________________________________________\n");
		PAUSE;
		
		printf("______________________________________________\n");
		printf("第三步.矩阵相加，结果存储在新的三元组表中\n\n"); 
		printf("	相加后结果矩阵C…………\n");
		Add_M(pa,pb,pc);
		ArrayDisp(pc);
		PAUSE;

		printf("	相加后结果矩阵C的三元组表示：\n");
		for (i=0;i<in_row;i++)						//结果矩阵C中非0元素的个数
			for (j=0;j<in_col;j++)
			{
				if (pc[i][j]!=0)nc++;
			}		
		ptc=init_T(pc,nc);
		TSMatrixDisp(ptc,nc);
		printf("______________________________________________\n");
		PAUSE;		
				
		CmdList();
		break;
	case 'Q':
	case 'q': 
		printf("程序结束，按任意键退出!\n"); 
       }

}

void main() //主函数
{
	char cmd;
	system ("cls"); 


		printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");
		printf("实验二  利用三元组表实现矩阵相加\n");
		printf("03计本3班\n");
		printf("樊海军 2B0324151138\n");
		printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");
		printf("   本程序实现利用三元组表进行两个稀疏矩阵相加的算法。\n");
		printf("=================================================================\n");


		CmdList();

	do {
		ReadCommand(cmd);
		Interpret(cmd);
	}
	while (cmd!='q'&&cmd!='Q');
}