#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node{
	int row;
	int col;
	int val;
};
struct TripletFormat{
	struct Node* elements;
	int rows;  // 矩阵的行数
	int cols;  // 矩阵的列数
	int total; // 非零元素的总数
};
/**
 * 矩阵转置：将稀疏矩阵的三元组表示转置
 * 
 * obj：指向原始三元组格式的稀疏矩阵
 * 返回值：指向转置后矩阵的三元组格式
 */
struct TripletFormat* tranTripletFormat(struct TripletFormat* obj){
	struct TripletFormat* tmp = (struct TripletFormat*)malloc(sizeof(struct TripletFormat));
	tmp->total = obj->total;
	tmp->rows = obj->cols;
	tmp->cols = obj->rows;
	tmp->elements = (struct Node*)malloc(obj->total*sizeof(struct Node));
	int cnt = 0;
	for(int i = 0; i < tmp->rows; i++){
		for(int j = 0; j < obj->total; j++){
			if(obj->elements[j].col == i){
				tmp->elements[cnt].val = obj->elements[j].val;
				tmp->elements[cnt].col = obj->elements[j].row;
				tmp->elements[cnt].row = i;
				cnt++;
			}
		}
	}
	return tmp;
}
/**
 * 打印稀疏矩阵
 * 
 * obj：指向稀疏矩阵的三元组格式
 */
void printTripletFormat(struct TripletFormat* obj){
	int matrix[obj->rows][obj->cols];
	memset(matrix, 0, sizeof(matrix));
	for(int i = 0; i < obj->total; i++){
		matrix[obj->elements[i].row][obj->elements[i].col] = obj->elements[i].val;
	}
	for(int i = 0; i < obj->rows; i++){
		for(int j = 0; j < obj->cols; j++){
			printf("%d ", matrix[i][j]);
		}
		printf("\n");
	}
}
int main(){
	int m, n;
	printf("请输入矩阵的行数和列数:");
	scanf("%d %d", &m, &n);
	
	struct TripletFormat* a = (struct TripletFormat*)malloc(sizeof(struct TripletFormat));
	a->rows = m, a->cols = n;
	a->total = 0;
	a->elements = (struct Node*)malloc(m*n*sizeof(Node));
	
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			int x;
			scanf("%d", &x);
			if(x == 0)continue;
			a->elements[a->total].val = x;
			a->elements[a->total].row = i;
			a->elements[a->total].col = j;
			a->total++;
		}
	}
	a = tranTripletFormat(a);
	printTripletFormat(a);
}
/*
3 5 
0 1 0 1 0
2 0 2 0 2
0 3 0 3 0
*/