#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* fasttranTripletFormat(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;
	int num[obj->cols];
	memset(num, 0, sizeof(num));
	for(int i = 0; i < obj->total; i++){
		num[obj->elements[i].col]++;
	}
	int start[obj->cols];
	start[0] = 0;
	for(int i = 1; i < obj->cols; i++){
		start[i] = start[i - 1] + num[i - 1];
	}
	for(int i = 0; i < obj->total; i++){
		int col = obj->elements[i].col;
		int pos = start[col];
		start[col] ++;
				
		tmp->elements[pos].row = obj->elements[i].col;
		tmp->elements[pos].col = obj->elements[i].row;
		tmp->elements[pos].val = obj->elements[i].val;
	}
	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 = fasttranTripletFormat(a);
	printTripletFormat(a);
}
/*
3 5 
0 1 0 1 0
2 0 2 0 2
0 3 0 3 0
*/