7. 矩阵的快速转置算法

7. 矩阵的快速转置算法

矩阵的快速转置算法

数据压缩是

提高传输、存储效率一种技术。


教材第


5


章介绍了两种简单的压缩存储方法。

本实验要求实现三元组顺序表表示下的矩阵快速转置算法

。

输入：

稀疏矩阵的行数、列数、非零元个数(三个数都大于0)

以行为主序输入稀疏矩阵三元组表

输出：

辅助数组


num[ ]

辅助数组


cpot[ ]

以行为主序输出对应的转置矩阵三元组表

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 6 7 8↵ 1 2 12↵ 1 3 9↵ 3 1 -3↵ 3 6 14↵ 4 3 24↵ 5 2 18↵ 6 1 15↵ 6 4 -7↵	以文本方式显示 num:2,2,2,1,0,1,0,↵ cpot:1,3,5,7,8,8,9,↵ 1,3,-3↵ 1,6,15↵ 2,1,12↵ 2,5,18↵ 3,1,9↵ 3,4,24↵ 4,6,-7↵ 6,3,14↵	1秒	256KB	0

#include<stdio.h>
typedef struct{
	int i, j;
	int e;
}Trip;
typedef struct{
	Trip data[1000];
	int mu, nu, tu;
}Matrix;
int num[100] = {0};
int cpot[100] = {0};
int main()
{
	int i;
	int col, t, p, q;
	Matrix M, T;
	scanf("%d%d%d", &M.mu, &M.nu, &M.tu);
	for (i = 1; i <= M.tu; i++)
		scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e);
	T.mu = M.mu;
	T.nu = M.nu;
	T.tu = M.tu;
	if (T.tu){
		for (col = 1; col <= M.nu; col++)
			num[col] = 0;
		for (t = 1; t <= M.tu; t++)
			num[M.data[t].j]++;
		cpot[0] = 1;
		cpot[1] = 1;
		for (col = 2; col <= M.nu; col++)
			cpot[col] = cpot[col - 1] + num[col - 1];
		for (p = 1; p <= M.tu; p++){
			col = M.data[p].j;
			q = cpot[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;
			cpot[col]++;
		}
	}
	printf("num:");
	for (i = 1; i <= M.nu; i++)
		printf("%d,", num[i]);
	printf("\n");
	printf("cpot:");
	for (i = 0; i < M.nu; i++)
		printf("%d,", cpot[i]);
	printf("\n");
	for (i = 1; i <= M.tu; i++)
		printf("%d,%d,%d\n", T.data[i].i, T.data[i].j, T.data[i].e);
	return 0;
}