#include <stdio.h>
#include <stdlib.h>
#define Max 100

//三元組結(jié)構(gòu)體的定義 
typedef struct{
	// 非零元所在行、所在列 
	int row, col;
	// 非零元的值 
	int value;		
}Triple;
 
//三元組容器的定義 
typedef struct{
	// data[0] 未使用 
	Triple data[Max];
	// 矩陣為 m行、n列 ?
	int m, n;
	// 矩陣非零元個(gè)數(shù)
	int len; 
}TSMatrix;
 
// 三元組 快速轉(zhuǎn)置
// 時(shí)間復(fù)雜度：O(矩陣 A 的列數(shù) + 矩陣 A 的非零元的個(gè)數(shù)) 
void FastTransposeSMatrix(TSMatrix A, TSMatrix &B){
	
	int i, position, col;
	// 矩陣 A m行、n列 ?轉(zhuǎn)置為 矩陣 B n行、m列 
	B.m = A.n;
	B.n = A.m;
	B.len = A.len;
	// 非零元個(gè)數(shù) 不為 0 
	if(A.len != 0){ 
		// num數(shù)組：記錄 矩陣 A 中 每一列非零元個(gè)數(shù) 
		int num[Max];
		// cpot數(shù)組：記錄 矩陣 B 中 每一列首非零元的下標(biāo) 
		int cpot[Max];
		// num 數(shù)組 初始化 
		for(i = 1; i <= A.n; i++){
			num[i] = 0;
		}
		// num[2] = 5：表示 矩陣 A 中，第 2 列 有 5 個(gè)非零元 
		for(i = 1; i <= A.len; i++){
			++num[A.data[i].col]; 
		}
		
		// 第 1 個(gè)非零元 在 三元組數(shù)組中的下標(biāo)為 1 
		cpot[1] = 1;
		for(col = 2; col <= A.n; col++){
			// cpot[5] = cpot[4] + num[4]; 
			// 第五列的第一個(gè)非零元的下標(biāo) = 第四列的第一個(gè)非零元下標(biāo) + 第四列非零元個(gè)數(shù) 
			cpot[col] = cpot[col - 1] + num[col - 1];	
		}
		
		// i 遍歷的是 三元組個(gè)數(shù) 
		for(i = 1; i <= A.len; i++){
			// 獲取 當(dāng)前元素的列標(biāo) 
			col = A.data[i].col;
			// 獲取 當(dāng)前列 首非零元的下標(biāo) 
			position = cpot[col];
			
			// ?當(dāng)前列 首非零元 進(jìn)行賦值 
			B.data[position].row = A.data[i].col;
			B.data[position].col = A.data[i].row;
			B.data[position].value = A.data[i].value;
			// 更改 當(dāng)前列的 首非零元的 下標(biāo) 
			++cpot[col]; 
		}
	} 
}

// 三元組輸入 
void inputTSMatrix(TSMatrix &T){
	int i, j, value, k; 
	printf("請(qǐng)輸入矩陣行數(shù)、列數(shù)：");
	scanf("%d %d", &T.m, &T.n);
	printf("請(qǐng)輸入三元組 非零元個(gè)數(shù)：");
	scanf("%d", &T.len);
	for(k = 1; k <= T.len; k++){
		printf("請(qǐng)輸入第 %d 個(gè)非零元：行 列 值：", k);
		scanf("%d %d %d", &i, &j, &value);
		T.data[k].row = i;
		T.data[k].col = j;
		T.data[k].value = value;
	}
}

// 打印三元組 
void printTSMatrix(TSMatrix T){
	for(int i = 1; i <= T.len; ++i ){
		printf("%d	%d	%d\n", T.data[i].row, T.data[i].col, T.data[i].value);
	}
}
 
int main(){

	TSMatrix A, B;
	inputTSMatrix(A);

	FastTransposeSMatrix(A, B);

	printf("\n原始三元組為:\n");
	printTSMatrix(A);
	
	printf("\n轉(zhuǎn)置后:\n");
	printTSMatrix(B);
	
	return 0;
}