本文将阐述我是如何理解严蔚敏老师«数据结构»中的稀疏矩阵及其相关的三元组定义方式，以及与之相关的快速转置算法。
稀疏矩阵
假设在的矩阵中，有个不为零的元素。令，称为稀疏因子。通常认为时，该矩阵则可以被称作稀疏矩阵。
数据结构
通常使用三元组顺序表的形式来压缩表示一个稀疏矩阵，每个三元组包括的信息有：
i非零元素的行下标j非零元素的列下标e元素值
三元组顺序表又将和一些元信息一起保存在一个联合结构（书中写的是union但我认为应该使用 struct，否则mu,nu,tu的数据会被覆盖）中以表示一个稀疏矩阵，这些基础信息包括：
mu矩阵的行数nu矩阵的列数tu矩阵非零元素的总个数
若使用~~伪~~C语言，可以有具体的如下定义。
# define MAXSIZE 12500 // 最大的非零元素个数
typedef struct{
int i,j; // 分别表示非零元素的行下标和列下标
ElemType e; // 元素值
}Triple;
typedef union{
Triple data[MAXSIZE + 1]; // 所有的非零元素， data[0]弃用
int mu, nu, tu; // 矩阵的行数、列数和总共的非零元素个数
}TSMatrix;
其实还有一个隐性的要求（虽然书中并没有明确说明）：data中的数据以行为主序存储（从第一行起依次存储）。
转置
根据上述的数据结构，若要将TSMatrix before转置成TSMatrix after，则务必需要经历如下三个步骤：
- 将
TSMatrix中的元信息mu、nu互换。 - 将
data中每个Triple的i和j互换。 - 重新整理
data使其满足行主序。（难以实现）
普通算法
最直观的想法是：因为转置后行列互换，转置后需要确保行主序，因此直接从before的第一列开始以列遍历处理。
对于具体的某一列，遍历所有的非零元素，判断每个元素的列值是否等于当前列。又因为，data是按照行值排列的，可以确保在after.data中的每行元素也一定可以按照列值从小到大排列。
Status TransposeSMatrix(TSMatrix before, TSMatrix &after){
after.mu = before.nu; after.nu = before.mu; after.tu = before.tu;
if(after.tu){
q = 1; // after.data的写入指针
for(col = 1; col <= before.nu; ++col){
// 遍历列
for(p = 1; p <= before.tu; ++p){
// 遍历before.data
if(before.data[p].j == col){
// 元素的列正好是当前被遍历的列
after.data[q].i = before.data[p].j;
after.data[q].j = before.data[p].i;
after.data[q].e = before.data[p].e;
++q;
}
}
}
}
return OK;
}
该算法的时间复杂度为，又因为和同数量级，因此实际复杂度为，相比于非压缩情况的转置算法的时间复杂度要耗时很多，除非。所以我们需要探究一个时间复杂度更低的转置算法，用空间换取时间。
快速转置算法
和KMP相似的，我们可以通过预处理before获取一些提炼出一些额外的信息，从而避免嵌套的循环。目标如下：只遍历一次before.data，将每个元素行列互换后填入after.data的合适的位置。
那么需要预处理出哪些信息才能在遍历时直接得出合适的位置呢？可以做如下的思考：
- 转置的实质是行列互换。
- 因此如果知道
before.data中某列的第1个非0元素在after.data中的位置（某行的第1个非0元素），那么这一列的下一个非0元素在after.data中的位置一定为，因为data是行主序的。
- 因此如果知道
- 又
before.data是行主序的- 又因为，遍历
before.data时是可以必然确保对于特定的列，遍历的次序一定是按照行号从低到高进行的。- 例如：本例中（列数为1）的第3个元素行号是3，第7个元素行号是6，行号随着遍历是从低到高的。
- 因此如果知道
before.data中每列的第1个非0元素在after.data中的位置，只需要遍历一遍before.data就可以把after.data计算出来。
- 又因为，遍历
- 如何计算
before.data中每列的第1个非0元素在after.data中的位置?- 递推：上一列的第1个非0元素在
after.data中的位置 + 上一列非0元素的总个数
- 递推：上一列的第1个非0元素在
- 如何求
before.data中每列非0元素的总个数？- 遍历before.data(tu)就行
所以总的算法过程就应该是：
- 遍历
before.data，求出before.data中每列非0元素的总个数num[]。 - 初始化
before.data中第1列的第1个非0元素在after.data中的位置为1。 - 遍历
before.data中所有的列，配合num[]递推出，before.data中每列的第1个非0元素在after.data中的位置cpot[]。 - 遍历
before.data(tu)，遇到的每一个元素都视作它所在列的第一个元素，根据cpot[col]填入after.data中，再把cpot[col]自增1。
Status FastTransposeSMatrix(TSMatrix before, TSMatrix &after){
after.mu = before.nu; after.nu = before.mu; after.tu = before.tu;
if(after.tu){
for(col = 1; col <= before.nu; ++col){
num[col] = 0;
}
for(t = 1; t < before.tu; ++t){
// 通过每一个before.data中的元素计数，得出每列非0元素数量
++num[before.data[t].j];
}
// 递推计算before.data中每列的第1个非0元素在after.data中的位置,初始化
cpot[1] = 1;
for(col = 2; col <= before.nu; ++col){
cpot[col] = cpot[col - 1] + num[col - 1];
}
// 填入after.data
for(p = 1; p <= before.tu; ++p){
// 每个被遍历到的非0元素都被视作，它所在列的第1个非0元素
col = before.data[p].j; q = cpot[col];
after.data[q].i = before.data[p].j;
after.data[q].j = before.data[p].i;
after.data[q].e = before.data[p].e;
// 当该列下一个元素被遍历到时，正好需要后移一位
++cpot[col];
}
}
return OK;
}
综上可以分析出其时间复杂度为 即 即 。