稀疏矩阵的转置详解（三元组表）

实验题目

          实验题目：稀疏矩阵的应用：设计算法并编程实现用三元组顺序表解决稀疏矩阵的转置问题，用2种方法实现并分析比较2种算法的时间和空间复杂性。

        实验说明：在m×n 的矩阵中，有t个非零元。令δ= t/(m*n),称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组顺序表实现稀疏矩阵的转置通常有2种方法，顺序存和顺序取直接存。

顺序取直接存方法：

引入两个数组作为辅助数据结构：

   num[nu]：表示矩阵A中某列的非零元素的个数；

   cpot[nu]：初始值表示矩阵A中某列的第一个非零元素在B中的位置。 

num与cpot递推关系：

三元组表实现稀疏矩阵的转置（顺序取直接存）算法伪代码如下：

问题分析

这一题的目标是使用三元组表实现对稀疏矩阵的转置

          转置后矩阵B的行数为转置前矩阵A的列数

          转置后矩阵B的列数为转置前矩阵A的行数

          非零元素个数转置前后均相同

  进行这个矩阵的转置，难点在于，转置前三元组表从上到下行数不断增加，转置后也应当是从上到下行数不断增加

转置过程如上图 

  我的解决方法是使用朴实无华的暴力思路，

1.先找到原始三元组表里最小的j（在进行转置后它会变为最小的i）

2.难点，将原始三元组表里j最小的那组数据存入转置后的那个三元组表，随着循环不断进行，转置后的三元组表就完成了，具体过程可以看我的代码（有详细注释）

	int k = 0;
	
	
	for(int i = 1; i <= a.num; i++) {
		//第一个循环用于找到原始三元组表里列号j最小的(交换后行数i最小放在转置后的矩阵上面)
		int min = 1e9;
		for(int m = 0; m < a.num; m++) {
			if(a.data[m].j < min)
				min = a.data[m].j;
			//朴实无华的暴力
		}
		
		for(int m = 0; m < a.num; m++) {
			if(a.data[m].j == min) {
				//找到最小值，进行转置
				b.data[k].zhi = a.data[m].zhi;
				b.data[k].i = a.data[m].j;
				b.data[k].j = a.data[m].i;
				k++;
				
				a.data[m].j = 1e9;
				//再将a里面的这个值改为最大避免下次for循环时干扰
				break;
			}
		}
	}

完整程序代码

#include<bits/stdc++.h>
using namespace std;

struct minitable {
	int i;
	int j;
	int zhi;
	//表示三元组表里的一个非0元素的行号，列号，值
};

struct table {
	minitable data[100];
	//三元组表里的元素个数
	int hangnum;
	int lienum;
	int num;
	//行数，列数，非0元素个数
};

table transpose(table a) {
	table b;
	b.hangnum = a.lienum;
	b.lienum = a.hangnum;
	b.num = a.num;
	//这里就是b的行数为a的列数，b的列数为a的行数，因为矩阵进行了转置，行列数目交换
	//交换后仍然要保证行数从上到下递增
	int k = 0;
	
	
	for(int i = 1; i <= a.num; i++) {
		//第一个循环用于找到原始三元组表里列号j最小的(交换后行数i最小放在转置后的矩阵上面)
		int min = 1e9;
		for(int m = 0; m < a.num; m++) {
			if(a.data[m].j < min)
				min = a.data[m].j;
			//朴实无华的暴力
		}
		
		for(int m = 0; m < a.num; m++) {
			if(a.data[m].j == min) {
				//找到最小值，进行转置
				b.data[k].zhi = a.data[m].zhi;
				b.data[k].i = a.data[m].j;
				b.data[k].j = a.data[m].i;
				k++;
				
				a.data[m].j = 1e9;
				//再将a里面的这个值改为最大避免下次for循环时干扰
				break;
			}
		}
	}
	return b;
}

int main() {
	//设置初始矩阵为A，转置后的矩阵为B
	
	//初始化矩阵A
	//如果要使用用户自主输入的话，使用for循环即可，再直接使用for循环
	//求出行数，列数，元素个数
	//这里就直接采用我自己造的一个三元矩阵了
	table A;
	A.hangnum = 5,A.lienum = 5,A.num = 6;
	A.data[0].i = 0,A.data[0].j = 1,A.data[0].zhi = 8;
	A.data[1].i = 3,A.data[1].j = 2,A.data[1].zhi = 3;
	A.data[2].i = 4,A.data[2].j = 5,A.data[2].zhi = 6;
	A.data[3].i = 5,A.data[3].j = 0,A.data[3].zhi = 7;
	A.data[4].i = 5,A.data[4].j = 4,A.data[4].zhi = 9;
	A.data[5].i = 5,A.data[5].j = 5,A.data[5].zhi = 5;
	
	cout << "转置前的三元组表A为：" << endl;
	for(int m = 0; m < A.num; m++) {
		cout << A.data[m].i << ' ' << A.data[m].j << ' ' << A.data[m].zhi << endl;
	}
	
	table B = transpose(A);
	
	cout << "转置后的三元组表B为：" << endl;
	for(int m = 0; m < B.num; m++) {
		cout << B.data[m].i << ' ' << B.data[m].j << ' ' << B.data[m].zhi << endl;
	}
	
	return 0;
}

运行结果

由于题目没有给与样例，我自己造了一组数据：