矩阵快速转置算法

当稀疏矩阵以三元组形式存储在计算机中时，转置会破坏掉原有矩阵的顺序性，比如原来矩阵的存储中，依次是：第一行第一个非零元素、第一行第二个非零元素~~~但是简单的交换行和列会破坏掉这些结构。矩阵的快速转置算法可以解决上述问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#define MAXSIZE 100 //最多的个数


//三元组结构体定义
typedef struct {
	int i, j; //行标和列标
	float e; //假设是单精度浮点型变量构成的矩阵
}Triple;
//矩阵结构体定义
typedef struct {
	Triple data[MAXSIZE + 1];  //第一个元素不用，矩阵的下标从1开始
	int rowNum, colNum, allNum;  //分别是行数、列数和非零元素个数
}TSMatrix;


//快速转置算法
TSMatrix* FastTransposeSMatrix(TSMatrix M, TSMatrix *T) { //两个参数分别是原来的矩阵和转置后的指针
	int num[MAXSIZE] = {0};  //每一行的非零元素个数，初始化为0
	int cpot[MAXSIZE];  //原始矩阵的某一列的第一个非零元素在结果中的下标位置。
	//统计原始矩阵中每一列的非零元素个数
	for (int i = 1; i <= M.allNum; i++) { 
		num[M.data[i].j]++;  
	}
	cpot[1] = 1; //初始化，第一个非零元素的位置是1

	//确定原始矩阵的每一个列的第一个非零元素的位置
	for (int i = 2; i <= M.colNum; i++) {
		cpot[i] = num[i - 1] + cpot[i - 1];
	}

	//转置后矩阵的行数、列数、总元素个数等信息
	T->rowNum = M.colNum;
	T->colNum = M.rowNum;
	T->allNum = M.allNum;

	//遍历原来的矩阵，根据构建的对应关系转置
	for (int elem = 1; elem <= M.allNum; elem++) {
		int col = M.data[elem].j; //确定这个元素在原来矩阵中的列
		int row = M.data[elem].i; //确定这个元素在原来矩阵中的行

		T->data[cpot[col]].e = M.data[elem].e; //将原来矩阵的这个位置的值复制到合适的位置
		T->data[cpot[col]].i = col; //原来的列变成行
		T->data[cpot[col]].j = row; //原来的行变成列
		cpot[col]++;  //非零元素的位置+1，以便下一个元素进行操作
	}


	return T;
}


//打印矩阵
void PrintMatrix(TSMatrix M) {
	printf("行数: %d, 列数: %d, 非零元素个数: %d\n", M.rowNum, M.colNum, M.allNum);
	for (int i = 1; i <= M.allNum; i++) {
		printf("(%d, %d) : %.2f\n", M.data[i].i, M.data[i].j, M.data[i].e);
	}
}	

// 检查是否存在相同位置的元素
int Exists(TSMatrix M, int row, int col) {
	for (int i = 1; i <= M.allNum; i++) {
		if (M.data[i].i == row && M.data[i].j == col) {
			return 1;
		}
	}
	return 0;
}

int main() {
	srand(time(NULL)); // 设置随机数种子

	TSMatrix M;
	M.rowNum = 5; // 行数
	M.colNum = 5; // 列数
	M.allNum = 0; // 非零元素个数

	// 生成随机稀疏矩阵
	for (int i = 1; i <= 10; i++) { // 假设最多有10个非零元素
		int row, col;
		do {
			row = rand() % M.rowNum + 1; // 随机行
			col = rand() % M.colNum + 1; // 随机列
		} while (Exists(M, row, col)); // 检查是否已经存在该位置的元素
		float value = (float)(rand() % 100) / 10; // 随机值
		M.allNum++;
		M.data[M.allNum].i = row;
		M.data[M.allNum].j = col;
		M.data[M.allNum].e = value;
	}

	printf("原始矩阵:\n");
	PrintMatrix(M);

	TSMatrix T; // 转置后的矩阵
	FastTransposeSMatrix(M, &T);

	printf("\n转置后的矩阵:\n");
	PrintMatrix(T);

	return 0;
}