游客 注册 | 登录
中文 | En

2815 - 三元组

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

题目描述：

在计算机中存储矩阵时，考虑到有一种矩阵叫做稀疏矩阵，因此对于这种矩阵，我们通常用三元组压缩存储。

稀疏矩阵：如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩阵

三元组：形如(x,y,z)的集合，x,y为矩阵中非零元素的行，列。z为非零值。

例如：1 1 3  表示1行1列非零值为3

  1 4 5  表示1行4列非零值为5

步骤：

1、先构建稀疏矩阵的三元组顺序表存储表示；

2、分别构造输入，输出三元组的函数；

3、构造转置函数；

4、主函数实现。

题目输入

输入格式：

含多组测试数据。

输入第一行为N，表示有N组测试数据。

输入第二行为稀疏矩阵的正整数 行(1<=i<=10)，列(1<=j<=10)，非零元个数(1<=n<=20)

接下来有n行输入，每行输入为正整数 x(1<=x<i)  y(1<=y<=j) z(1<=z<=100)，x代表非零元所在行，y代表非零元所在列，z代表非零元的值。

题目输出

输出格式：

输出转置矩阵之后的三元组

每组输出数据开头以空行隔开

输入/输出样例

输入格式

1
3 4 4
1 1 3
1 4 5
2 2 1
3 1 2

输出格式

1 1 3
1 3 2
2 2 1
4 1 5

C语言解答

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 12500//矩阵的最大值
#define MAXRC 100//行或列的最大值

//定义三元组矩阵存储元素类型
typedef struct
{
	int x, y;//x为行号，y为列号
	int e;//e为数值
}Triple;

void zhuanzhi()
{
	Triple san[100];
	Triple san1[100];
	int tu, nu, mu;//tu代表行数，nu代表列数，mu代表非零元个数

	scanf("%d%d%d", &tu, &nu, &mu);

	for (int i = 0; i < mu; i++)
		scanf("%d%d%d", &san[i].x, &san[i].y, &san[i].e);

	int k = 0;
	for (int i = 1; i <= nu; i++)
	{
		for (int j = 0; j < mu; j++)
		{
			if (san[j].y == i)
			{
				san1[k].x = san[j].y;
				san1[k].y = san[j].x;
				san1[k].e = san[j].e;
				k++;
			}
		}
		
	}
	for (int k = 0; k < mu; k++)
	{
		printf("%d %d %d\n", san1[k].x, san1[k].y, san1[k].e);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n;i++)
	{
		zhuanzhi();
		if (i < n - 1)
			printf("\n");
	}
	return 0;
}

C++解答

#include<stdio.h>
#include <algorithm>
using namespace std; 
typedef struct node
{
	int x,y,wei;
};
int cmp(const node& a,const node & b)
{
	return (a.x<b.x||(a.x==b.x&&a.y<b.y));
}
int main()
{
	int t;scanf("%d",&t);
	int dd=0;
	while(t--)
	{
		if (dd==1) printf("\n");
		else dd=1;
		node k[20];
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		for (int i=0;i<c;i++)
			scanf("%d%d%d",&k[i].y,&k[i].x,&k[i].wei);
		sort(k,k+c,cmp);
		for (int i=0;i<c;i++)
			printf("%d %d %d\n",k[i].x,k[i].y,k[i].wei);
	}
	return 0;
}
请先登陆