稀疏矩阵转置多种算法详解

大家好，又见面了，我是你们的朋友全栈君。

这次博文写的有点长，因为我得构思，所以今天晚上（11.10）写一点，另外还有个重要的任务，因为再过40分钟就是剁手节了，过了今晚我不止是一个光棍，更是一个穷光棍、、、、我该怎么办。。。求拦截。

不扯了正题，今天就先写写矩阵转置吧，现实中转置么，不就区区一个转置么，那有什么，瞅一眼就转过来了。计算机就是计算机，他没有相发也没有眼睛，那么我们就来告诉他怎么思考，怎么走路吧。

方法一：一般转置（简单）

转置矩阵： 一个 m×n 的矩阵 M，它的转置 T 是一个 n×m 的矩阵，且 T (i, j) = M[ j, i]， 1≤i≤n， 1≤j≤m， 即 M 的行是 T 的列， M 的列是 T 的行。

这里写图片描述

M：原矩阵 T：转置之后的矩阵

PS：讲转置之前需要介绍一下稀疏矩阵的三元组压缩存储方式,就是将稀疏矩阵的非零元素的 （行坐标，列坐标，元素值） 例如：M数组的第一行第二列的12在三元组里的表示为 （1,2，12）

三元组顺序表存储结构：

这里写图片描述

这个结构就是一个数组 Triple： 申明了一个类型，包含了 i（行）、j（列）、e（元素数据） TSMatrix：定义了Triple类型的数组保存行列数据元素信息，mu(总行数)、nu（总列数）tu（非零元素个数）

下面是保存之后的结果

这里写图片描述

Triple类型的data数组长度在定义的时候长度是MAXSIZE+1是为了在data[0]空出来一个位置使 数组小标与矩阵的行列下标对应，图中data[0]的位置 6 7 8 是为了方便讲解写的，实际上是空

问题描述：

这里写图片描述

下图是简单转置的解题思路

这里写图片描述

解析： 1）将mu、nu互换 2）将data数组中 i，j对应的元素位置互换 3）把新的三元组T按行顺序排列，所以以i从小到大按顺序将三元组 排序 简单写法 for (col = 1; col <= M.nu; ++ col) for (p = 1; p <= M.tu; ++ p) if ( M.data[p].j == col ) { T.data[q].i = M.data[p].j ; T.data[q].e = M.data[p].e; ++ q； } 下面把完整的算法用图片弄上来，这样看着更清楚些。

这里写图片描述

时间复杂度： 两次循环，三元组多长需要遍历多长，这效率可想而知。 所以牛人们相除了了非常6的一个算法，我在下面加一个方法一的优缺点，明天写吧，，，我要准备抢衣服啦哈哈哈哈哈哈

这里写图片描述

来，继续。。。

方法二：按 M 的行序转置 —— 快速转置

这个方法简单，是因为算法中包含了两个有特殊用法的数组，保存了非常重要的信息，简单说下算法的步骤

1）确定 M 的第 1 列的第 1 个非零元在 T.data 中的位置。 1 2）确定 M 的第 col -1 列的非零元个数。 存入数组 num[M.nu] 3）确定 M 的第 col 列的第一个非零元在T.data 中的位置。 存入数组 cpot[M.nu] cpot[1] = 1; cpot[col]=cpot[col–1]+num[col–1] 2≤col≤a.nu

num数组保存的是 上一列非零元素个数 cpot数组保存的数字依据上面的等式

可以参考下图来验证这个等式是否正确

这里写图片描述

其实 cpot[]内数据成员就是 T数组内 该元素前面有多少个非零元素+1，例如12（第一行第二列），在cpot里对应的数字就是2+1

两个数组的保存数据情况

这里写图片描述

下面是高效率算法的代码（有点不清晰，最下面有清晰地高亮的代码） Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T ) { // 采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵 T //T 的行列最大值交换 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; // if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0;

// 求 M 中各列非零元的个数 for (t=1; t<=M.tu; ++t) ++ num[M.data[t].j]; cpot[1] = 1; // T里第二个位置也是数组起始位置

// 求 M 中各列的第一个非零元在 T.data 中的序号 for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col -1] + num[col -1];

//将数据存储到T for(p=1;p<=M.tu;++p){ col = M.data[p].j; q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=Mdata[p].e; ++col[col]; //指向T的下一个位置 }//for }//if return OK; }//FastTransposeSMatrix

这里写图片描述

存储结束，cpot col两个数组存储情况

这里写图片描述

好了，就写到这里吧，博文有什么问题希望大家给指出。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/151214.html原文链接：https://javaforall.cn