三元表稀疏矩阵转置[^foot_note]

• 三元表稀疏矩阵转置1
  • 三元组顺序表

三元表稀疏矩阵转置¹

如何在茫茫人海中用最少空间标记你的女友，前女友，前前女友……的位置？

相对于普通矩阵还要保存其他人的信息，很明显，我们只需关注我的女友，前女友，前前女友的位置，其他人的位置我都不需要关注，因此我们建立一个顺序表，表中记录第几号女友和她的具体位置，这样我们可以节约大量空间。 这种记录方法就是传说中的三元组顺序表

三元组顺序表

三元组法是对于稀疏矩阵的一个有效记录方法，对于每一个非零元，我们分别记录下它的行坐标、列坐标和它的值。

#define MAXSIZE 12500
typedef struct{
    int i, j;       //该非零元的行列坐标
    ElemType e;     //非零元信息
}Triple;
typedef struct{
    Triple data[MAXSIZE];
    int mu, nu, tu; //行，列，非零元个数
}

在这里默认三元组以行序为主序顺序排列

##矩阵转置 $M(i, j)^T =M(j, i)$ 首先介绍个最容易想到的方法： ##方法一：

1. 元素互调：矩阵的行列值交换，如把元素行列值i=1,j=2换成i=2,j=1
2. 重建三元组：重新将三元组以行序为主序排序

这个算法的时间复杂度为 O(tu*log(tu))

这个方法已经比数据结构书上的方法一好很多，但是本着做一个宇宙好公民，延缓宇宙熵增，我们要努力探究更好的方法

##方法二 如果在对i, j互调的过程中同时确定每一列第一个非零元的应有的位置，那么在重建三元组时就不需要排序。

num[col]        //记录第col列非零元素的个数
cpot[col]       //第col列第一个非零元在新三元组中的位置

易知num[col]和cpot[col]的关系式是

cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1];

时间复杂度就将为令人惊讶的 O(tu)

###灵感分析 在稀疏矩阵中有一种表示方法，它只记录每一行的个数和每一行开始的位置，在实现过程中的思路跟方法二一样

1. 本文在清华出版社出版的数据结构基础上结合个人经验完成 ↩