#include<iostream.h>
#include<stdio.h>
int const N=4;
int const MaxSize=100;
typedef int ElemType;
typedef struct
{
	int r;//行號
	int c;//列號
	ElemType d;//元素值
}TupNode;//三元組定義
typedef struct
{
	int rows;
	int cols;
	int nums;//非零元素個數
	TupNode data[MaxSize];
}TsMatrix;//三元組存儲結構

void CreatMat(TsMatrix &t,ElemType A[N][N])//三元組表示稀疏矩陣
{
	int i,j;
	t.rows=N;t.cols=N;t.nums=0;
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
			if(A[i][j]!=0)
			{
				t.data[t.nums].r=i;
				t.data[t.nums].c=j;
				t.data[t.nums].d=A[i][j];
				t.nums++;
			}
	}
}
void DispMat(TsMatrix t)//輸出三元組
{
	int i;
	if(t.nums<1)
		return ;
	printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
	printf("\t--------------------------------\n");
	for(i=0;i<t.nums;i++)
		printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
}
/*void TranMat(TsMatrix t,TsMatrix &tb)//傳統轉置方法
{
	int p,q=0,v;//q為tb.data的下標
	tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;
	if(t.nums!=0)
	{
		for(v=0;v<t.cols;v++)
			for(p=0;p<t.nums;p++)
				if(t.data[p].c==v)
				{
					tb.data[q].r=t.data[p].c;
					tb.data[q].c=t.data[p].r;
					tb.data[q].d=t.data[p].d;
					q++;
				}
	}
}

*/
void FastTranMat(TsMatrix t,TsMatrix &tb)//快速轉置
{
	int col,p,q,s,num[N],cpot[N];
	tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;
	if(t.nums)
	{
		  for(col=0;col<t.nums;++col) num[col] = 0;
		   //先置t矩陣每列非0元個數均為0
          for(s=0;s<t.nums;++s)  ++num[t.data[s].c];
		      //求t中每一列非0元個數
		    cpot[0]=0; //t中第一列第一個非元在tb中的序號為1
		  for(col=1;col<t.nums;++col)
		  cpot[col]=cpot[col-1]+num[col-1];
		      //求t中第col列中第一個非0元在T中的序號
		   for(p=0;p<t.nums;++p)
		   {
			  col=t.data[p].c; //記下t中第p個元素的列號
			   q=cpot[col];    //該列中第一個非0元在tb中的序號
			  tb.data[q].r=t.data[p].c;
			  tb.data[q].c=t.data[p].r;
			  tb.data[q].d=t.data[p].d;
			  ++cpot[col];
		   }
	}
}
int MatAdd(TsMatrix a,TsMatrix b,TsMatrix &c)
{
	int i=0,j=0,k=0;
	ElemType v;
	if(a.rows!=b.rows||a.cols!=b.cols)
		return 0;//行數或列數不相等時不能進行相加
	c.rows=a.rows;c.cols=a.rows;//c的行數和列數與a的相同
	while(i<a.nums&&j<b.nums)//處理a和b中的每個元素
	{
		if(a.data[i].r==b.data[j].r)
		{
			if(a.data[i].c<b.data[j].c)//a元素列號小于b元素列號
			{
				c.data[k].r=a.data[i].r;/*將a元素添加到c中*/
				c.data[k].c=a.data[i].c;
				c.data[k].d=a.data[i].d;
			    k++;i++;
			}
			else if(a.data[i].c>b.data[j].c)
			{
				c.data[k].r=b.data[j].r;
				c.data[k].c=b.data[j].c;
				c.data[k].d=b.data[j].d;
				k++;j++;
			}
			else
			{
				v=a.data[i].d+b.data[j].d;
				if(v!=0)
				{
					c.data[k].r=a.data[i].r;
					c.data[k].c=a.data[i].c;
					c.data[k].d=v;
				    k++;
				}
				i++;j++;
			}
		}
		else if(a.data[i].r<b.data[j].r)//a元素行號小于b元素行號
		{
			c.data[k].r=a.data[i].r;//將a元素加到c中
			c.data[k].c=a.data[i].c;
			c.data[k].d=a.data[i].d;
			k++;i++;
		}
		else
		{
			c.data[k].r=b.data[j].r;
			c.data[k].c=b.data[j].c;//將b元素加到c中
			c.data[k].d=b.data[j].d;
			k++;j++;
		}
		c.nums=k;
	}
	return 1;
}
int value(TsMatrix c,int i,int j)
{
	int k=0;
	while(k<c.nums&&(c.data[k].r!=i||c.data[k].c!=j))
		k++;
	if(k<c.nums)
		return c.data[k].d;
	else return 0;
}
int MatMul(TsMatrix a,TsMatrix b,TsMatrix &c)
{
	int i,j,k,p=0;
	ElemType s;
	if(a.cols!=b.rows)
		return 0;//a的列數不等于b的行數時候不能進行相乘
    for(i=0;i<a.rows;i++)
		for(j=0;j<b.cols;j++)
		{
			s=0;
			for(k=0;k<a.cols;k++)
				s+=value(a,i,k)*value(b,k,j);
			if(s!=0)
			{
				c.data[p].r=i;
				c.data[p].c=j;
				c.data[p].d=s;
			    p++;
			}
		}
		c.rows=a.rows;
		c.cols=b.cols;
		c.nums=p;
		return 1;
}
extern void CreatMat(TsMatrix &t,ElemType A[N][N]);//三元組表示稀疏矩陣
extern void DispMat(TsMatrix t);//輸出三元組
extern void TranMat(TsMatrix t,TsMatrix &tb);//傳統轉置方法
extern void FastTranMat(TsMatrix t,TsMatrix &tb);//快速轉置
extern int MatAdd(TsMatrix a,TsMatrix b,TsMatrix &c);
extern int value(TsMatrix c,int i,int j);
extern int MatMul(TsMatrix a,TsMatrix b,TsMatrix &c);
void main()
{
	ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};
	ElemType b1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};
	TsMatrix a,b,c;
	CreatMat(a,a1);
	CreatMat(b,b1);
	cout<<"a的三元組:"<<endl;
	DispMat(a);
	/*cout<<"a的轉置(傳統方法轉置)為c"<<endl;
	TranMat(a,c);
	cout<<"c的三元組:"<<endl;
	DispMat(c);
	cout<<endl;*/
	cout<<"a的轉置(快速方法轉置)為c"<<endl;
	FastTranMat(a,c);
	cout<<"c的三元組:"<<endl;DispMat(c);
	cout<<"c=a+b"<<endl;
	MatAdd(a,b,c);
	cout<<"c的三元組:"<<endl;DispMat(c);
	cout<<"c=a*b"<<endl;
	MatMul(a,b,c);
	cout<<"c的三元組:"<<endl;DispMat(c);
}