数据结构-稀疏矩阵转置 （C语言代码）

解题思路:

    练习一下快速转置，只遍历三元组表一次，根据辅助数组确定入表位置。

注意事项:

    辅助数组的生成：遍历一次三元组表，记录原矩阵每列非0元素的个数，即可知道转置后每行非0元素个数和起始位置，则可一次遍历确定转置后元素的相应入表位置。

参考代码:

#include<stdio.h>
#include<string.h>
#include<malloc.h>

typedef struct Triple {
	int i; // 所在行
	int j; // 所在列
	int data; // 数值
} Triple;

typedef struct TSMatrix {
	Triple *data;
	int mu; // 总行数
	int nu; // 总列数
	int tu; // 非0数据个数
} TSMatrix;

int CreateTSMatrix(TSMatrix *M, int **num);
void CreateNumArray(int *num, int col);
void TransposeTSMatrix(TSMatrix *M, TSMatrix *T, int *num);
void DisplayTSMatrix(TSMatrix *T);

int main()
{
	TSMatrix M, T;
	int *num = NULL; // 辅助数组，完成快速转置
	int col;
	M.data = NULL;
	T.data = NULL;
	col = CreateTSMatrix(&M, &num);
	CreateNumArray(num, col);
	TransposeTSMatrix(&M, &T, num);
	DisplayTSMatrix(&T);
	free(T.data);
	free(M.data);
	return 0;
}

int CreateTSMatrix(TSMatrix *M, int **num) {
	int i, j, data, size;
	scanf("%d%d", &M->mu, &M->nu);
	M->tu = 0;
	*num = (int *)malloc(sizeof(int) * (M->nu + 1));
	memset(*num, 0, sizeof(int) * (M->nu + 1));
	M->data = (Triple *)malloc(sizeof(Triple) * M->nu * 2);
	size = M->nu * 2;
	for (i = 1; i <= M->mu; i++) {
		for (j = 1; j <= M->nu; j++) {
			scanf("%d", &data);
			if (data) { // 只存放非0数据
				M->data[M->tu].i = i;
				M->data[M->tu].j = j;
				M->data[M->tu++].data = data; // M->tu记得++
				(*num)[j]++; // 暂时存放每列非0数据个数
			}
		}
		if (size - M->tu < M->nu) {
			M->data = (Triple *)realloc(M->data, sizeof(Triple) * (size + M->nu));
			size += M->nu;
		}
	}
	return M->nu;
}

// 将num转成记录每列首个非0数据的转置后入表位置
void CreateNumArray(int *num, int col) {
	int j, t1, t2;
	t1 = num[1];
	num[1] = 0;
	for (j = 2; j <= col; j++) {
		t2 = num[j]; // t2记录当前列非0数据个数
		num[j] = num[j - 1] + t1; // 替换为转置后的位置
		t1 = t2; // t1记录前一列非0数据个数，t1更新
	}
}

void TransposeTSMatrix(TSMatrix *M, TSMatrix *T, int *num) {
	int i, j, p;
	T->data = (Triple *)malloc(sizeof(Triple) * M->tu);
	T->mu = M->nu;
	T->nu = M->mu;
	T->tu = M->tu;
	for (i = 0; i < M->tu; i++) {
		j = M->data[i].j; // 获取列数
		p = num[j]; // 查询入表位置
		T->data[p].i = M->data[i].j;
		T->data[p].j = M->data[i].i;
		T->data[p].data = M->data[i].data;
		num[j]++; // 当前列下一个非0数据入表位置++
	}
}

void DisplayTSMatrix(TSMatrix *T) {
	int i, j, t = 0;
	for (i = 1; i <= T->mu; i++) {
		for (j = 1; j <= T->nu; j++) {
			if (T->data[t].i == i && T->data[t].j == j) {
				printf("%d ", T->data[t].data);
				t++;
			}
			else {
				printf("0 ");
			}
		}
		printf("\n");
	}
}