游客 注册 | 登录
中文 | En

1353 - 算法5-1：稀疏矩阵转置

通过次数

0

提交次数

0

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

稀疏矩阵的存储不宜用二维数组存储每个元素，那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组，由非零元素在该稀疏矩阵中的位置（行号和列号对）以及该元组的值构成。

矩阵转置就是将矩阵行和列上的元素对换。

现在就请你对一个稀疏矩阵进行转置。以下是稀疏矩阵转置的算法描述： 

<!--[if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0<![endif]-->


<span style="font-size:10.5000pt;font-family:'宋体';">图：</span><span style="font-size:10.5000pt;font-family:'宋体';">稀疏矩阵转置的算法描述</span>

题目输入

输入的第一行是两个整数r和c（r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，表示这个稀疏矩阵的各个元素。

题目输出

输出c行，每行有r个整数，每个整数后跟一个空格。该结果为输入稀疏矩阵的转置矩阵。

输入/输出样例

输入格式

6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0

输出格式

0 0 -3 0 0 15 
12 0 0 0 18 0 
9 0 0 24 0 0 
0 0 0 0 0 -7 
0 0 0 0 0 0 
0 0 14 0 0 0 
0 0 0 0 0 0

C语言解答

#include <stdio.h>
typedef struct va{
	int row;
	int col;
	int v;
}va;
int main(){
	int r,c,tmp,i,j,cnt,k;
	va v[12501];
//	freopen("1.txt","r",stdin);
	while (scanf("%d %d",&r,&c)==2)
	{
		cnt=0;
		for (i=0;i<r;i++)
		{
			for (j=0;j<c;j++)
			{
				scanf("%d",&tmp);
				if (tmp)
				{
					v[cnt].row=j;
					v[cnt].col=i;
					v[cnt].v=tmp;
					cnt++;
				}
			}
		}
		for (i=0;i<c;i++)
		{
			for (j=0;j<r;j++)
			{
				for (k=0;k<cnt;k++)
				{
					if (v[k].row==i&&v[k].col==j)
					{
						printf("%d ",v[k].v);
						break;
					}
				}
				if (k==cnt)
				{
					printf("0 ");
				}
			}
			printf("\n");
		}
	}
//	fclose(stdin);
	return 0;
}

C++解答

#include <stdio.h>
#define MAXSIZE 12500		// 假设非零元个数的最大值为12500
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;		// 定义基本元素的类型为 int 型
typedef struct{
	int i, j;				// 该非零元的行下标和列下标
	ElemType e;
}Triple;

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

void InputMatrix(TSMatrix &M){
	// 读入矩阵 M，r、c为该矩阵的行和列数
	int i, j;
	int data;	// 用来存储临时读取近来的数据
	M.tu = 0;	// 先将非零元地数目初始化为0
	for(i=1; i<=M.mu; i++){
		for(j=1; j<=M.nu; j++){
			scanf("%d", &data);			// 读入元素
			if(data){					// 如果 data 为非零元
				M.tu++;					// 先对非零元地数目加1，因为data[0]未用
				M.data[M.tu].e = data;	// 储存非零元
				M.data[M.tu].i = i;		// 记录当前元素的行号
				M.data[M.tu].j = j;		// 记录当前元素的列号
			}
		}
	}
}

void OutputMatrix(TSMatrix M){
	// 输出矩阵
	int i, j;		// 定义迭代变量
	int t = 1;			// 定位需要输出矩阵中的位置
	for(i=1; i<=M.mu; i++){
		for(j=1; j<=M.nu; j++){
			if(i==M.data[t].i && j==M.data[t].j){	// 需要输出非零元
				printf("%d ", M.data[t].e);
				t++;		// 定位下次需要输出的元素
			}else{
				printf("0 ");	// 输出零元
			}
		}
		putchar('\n');			// 换行
	}
}

Status TransposeSMatrix(TSMatrix M, TSMatrix &T) { // 算法5.1
	// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
	int p, q, col;
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	if (T.tu) {
		q = 1;
		for (col = 1; col <= M.nu; ++col)
			for (p = 1; p <= M.tu; ++p)
				if (M.data[p].j == 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;
					++q;
				}
	}
	return OK;
} // TransposeSMatrix

int main(){

	TSMatrix M, T;	// 定义存储矩阵的变量
	scanf("%d%d", &M.mu, &M.nu);
	InputMatrix(M);
	TransposeSMatrix(M, T);
	OutputMatrix(T);

	return 0;
}

Java解答



import java.util.Scanner;

public class Main {
   private static Scanner s = new Scanner(System.in) ;
   
   public static void main(String[] args) {
	  int n = s.nextInt() ;
	  int m = s.nextInt() ;
	  
	  int a[][] = new int[n][m] ;
	  
	  for (int i = 0; i < a.length; i++) {
		for (int j = 0; j < a[0].length; j++) {
			a[i][j] = s.nextInt() ;
		}
	  }
	  
	  for (int i = 0; i < a[0].length; i++) {
			for (int j = 0; j < a.length; j++) {
               System.out.print(a[j][i]+" ");
			}
			System.out.println();
		  }
   }
}
请先登陆