2651 - 数据结构/稀疏矩阵/三元组实现

3 3 2
0 0 5
1 2 7
3 3 2
0 0 5
2 1 9

A'
3 3 2
(0,0)=5
(2,1)=7
A+B
3 3 3
(0,0)=10
(1,2)=7
(2,1)=9

Hint

	一、三元组实现


	struct Triple{
 int row,col;

 float data;

 Triple(){ row=0,col=0,data=0; }

 Triple(int r,int c,float d)

 {  row=r;col=c;data=d; }


&nbsp;void Show()<br />

 {  printf("(%d,%d)=%.0f\n",row,col,data); }


};



&nbsp;



二、稀疏矩阵接口和部分实现



#define MAX_SIZE 100&nbsp;<br />

struct SparseMatrix

{

 int rows,cols;

 int count;

 Triple elems[MAX_SIZE];


&nbsp;SparseMatrix(int r,int c)<br />

 {  rows=r;  cols=c;  count=0; }


&nbsp;void AddElement(Triple &amp;t)<br />

 {  elems[count++]=t; }


<br />

 void AddElement(int r,int c,float data)

 {  elems[count++]=Triple(r,c,data); }


&nbsp;



&nbsp;SparseMatrix&amp; Transpose()<br />

 {

  SparseMatrix* result=new SparseMatrix(cols,rows);

  //TODO:实现转置


&nbsp;&nbsp;return *result;<br />

 }


&nbsp;SparseMatrix&amp; Add(SparseMatrix &amp;other)<br />

 {

  SparseMatrix result=new SparseMatrix(rows,cols);

  //TODO:完成元素相加result=this+other

  return result;

 }

 void ShowTriple()

 {

  printf("%d %d %d\n",rows,cols,count);

  for (int i=0;i<count;i++)

   elems[i].Show();

 }


&nbsp;void ShowFull()<br />

 {

  int index=0;

  Triple triple=elems[index++];

  for (int r=0;r<rows;r++)

  {

   for (int c=0;c<cols;c++)

   {

    if (r==triple.row && c==triple.col)

    {

     printf("%.2f\t",triple.data);

     triple=elems[index++];

    }

    else

     printf("%d\t",triple.data);

   }

   printf("\n");

  }

  printf("\n");

 }

};


&nbsp;



三、主控部分：



int main()<br />

{

 int n,m,count;

 int r,c,d;

 while(scanf("%d%d%d",&n,&m,&count)==3)

 {

  SparseMatrix A(n,m);

  for (int i=0;i<count;i++)

  {

   scanf("%d%d%d",&r,&c,&d);

   A.AddElement(r,c,d);

  }

  scanf("%d%d%d",&n,&m,&count);

  SparseMatrix B(n,m);

  for (int i=0;i<count;i++)

  {

   scanf("%d%d%d",&r,&c,&d);

   B.AddElement(r,c,d);

  }

  printf("A'\n");

  A.Transpose().ShowTriple();

  printf("A+B\n");

  A.Add(B).ShowTriple();

 }


&nbsp;return 0;<br />

}


&nbsp;

Solution C++

// Matrix.cpp : 程欣宇2014年5月7日

#include "stdio.h"
#include "memory.h"

struct Triple{
	int row,col;
	float data;
	Triple(){row=0,col=0,data=0;}
	Triple(int r,int c,float d)
	{
		row=r;col=c;data=d;
	}
	void Show()
	{
		printf("(%d,%d)=%.0f\n",row,col,data);
	}
};

#define MAX_SIZE 100	
struct SparseMatrix
{
	int rows,cols;
	int count;
	Triple elems[MAX_SIZE];
	SparseMatrix(int r,int c)
	{
		rows=r;
		cols=c;
		count=0;
	}

	void AddElement(Triple &t)
	{
		elems[count++]=t;
	}
	void AddElement(int r,int c,float data)
	{
		elems[count++]=Triple(r,c,data);
	}

	SparseMatrix& Transpose()
	{
		SparseMatrix* result=new SparseMatrix(cols,rows);
		result->count=count;//转置前后元素数量不变
		int num[100];
		int cpos[100];
		memset(num,0,sizeof(num));
		memset(cpos,0,sizeof(cpos));
		//统计列的元素数量
		for (int i=0;i<count;i++)
			num[elems[i].col]++;
		//统计每行出现在数组中的开始位置
		for (int i=1;i<cols;i++)
			cpos[i]=cpos[i-1]+num[i-1];
		
		for (int i=0;i<count;i++)
		{
			Triple triple=elems[i];
			result->elems[cpos[triple.col]++]=Triple(triple.col,triple.row,triple.data);
		}
		

		return *result;
	}

	SparseMatrix& Add(SparseMatrix &other)
	{
		SparseMatrix* result=new SparseMatrix(rows,cols);
		//完成元素相加result=this+other
		int i=0,j=0;
		Triple a=elems[i++];
		Triple b=elems[j++];
		while(i<=count && j<=other.count)
		{
			if (a.row==b.row && a.col==b.col)
			{
				result->AddElement(a.row,a.col,a.data+b.data);
				a=elems[i++];
				b=other.elems[j++];
			}else if (a.row<b.row || a.row==b.row && a.col<b.col)
			{
				result->AddElement(a);
				a=elems[i++];
			}else
			{
				result->AddElement(b);
				b=other.elems[j++];
			}
		}
		while (i<=count)
		{
			result->AddElement(a);
			a=elems[i++];
		}
		while (j<=other.count)
		{
			result->AddElement(b);
			b=other.elems[j++];
		}
		return *result;
	}
	SparseMatrix& Sub(SparseMatrix &other)
	{
		SparseMatrix* result=new SparseMatrix(rows,cols);
		//完成元素相减result=this-other
		return *result;
	}

	void ShowTriple()
	{
		printf("%d %d %d\n",rows,cols,count);
		for (int i=0;i<count;i++)
			elems[i].Show();
	}

	void ShowFull()
	{
		int index=0;
		Triple triple=elems[index++];
		for (int r=0;r<rows;r++)
		{
			for (int c=0;c<cols;c++)
			{
				if (r==triple.row && c==triple.col)
				{
					printf("%.2f\t",triple.data);
					triple=elems[index++];
				}
				else
					printf("%d\t",triple.data);
			}
			printf("\n");
		}
		printf("\n");
	}
};

int main()
{
	int n,m,count;
	int r,c,d;
	while(scanf("%d%d%d",&n,&m,&count)==3)
	{
		SparseMatrix A(n,m);
		for (int i=0;i<count;i++)
		{
			scanf("%d%d%d",&r,&c,&d);
			A.AddElement(r,c,d);
		}
		scanf("%d%d%d",&n,&m,&count);
		SparseMatrix B(n,m);
		for (int i=0;i<count;i++)
		{
			scanf("%d%d%d",&r,&c,&d);
			B.AddElement(r,c,d);
		}
		printf("A'\n");
		A.Transpose().ShowTriple();
		printf("A+B\n");
		A.Add(B).ShowTriple();
	}

	return 0;
}