稀疏矩阵转置

矩阵是线性代数中的一个知识,刚开始学习的时候可能感觉不到它有什么用处,最初的感觉就是对二维数据的操作。其实现实生活中矩阵的用处太大了,设计领域相当的广泛。在此只讨论稀疏矩阵的转置问题;

可能看到矩阵就会想到二维数组,比如这样一个矩阵:

你可能会想到用二维数组来存放此矩阵中的元素,就像这样:int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}};

这样好像也没有什么不好。我们再来看看这个矩阵,五行五列,可以包含二十五个元素,但是此矩阵只有七个元素。但是我们在存放数据的时候分配了二十五块int单元。这样是不是有点太浪费了。如果我们只存储这七个元素我想会节省一部分内存空间。但是如果我们只存储矩阵中的元素还是不行的,因为只有元素我们就无法还原矩阵,我们还需要此元素的行列值。这样就好办了。我们声明一个结构体来表示一个元素。就像这样:

这样存储一个元素就会用到三个存储单元,七个就是二十一个存储单元,可能与二十五个没多大差别,但是如果矩阵的行列是一个很大的值,而且又是稀疏矩阵,这样做就可以节省很大的空间。这种存储结构只限于稀疏矩阵。

解决了存储结构,就开始矩阵的转置吧!!!

首先我们需要一个矩阵,就按照上图给的矩阵好了,按照此矩阵做一个二维数组:

就像这样;我们需要定义一个数组来表示稀疏矩阵,并赋值;

在初始化矩阵数组的时候为了方便转置矩阵时的操作,我们把数组的第一个元素设置为矩阵的列数,行数和元素总数;

矩阵有了,存放矩阵元素的数组也有了。接下来就是转置矩阵的函数了。

我们在转置矩阵的时候会需要一个数组来保存转置后的矩阵,定义为:

主要思想,两层循环,第一层循环控制矩阵的行,第二层循环控制数组a的行。由于转置矩阵即把矩阵中元素的列行对换一下,并且按照行排序;所以我们在第二层循环中做一个判断,if(a[j].col == i) 【i控制第一层循环,j控制第二层循环】 如果为真值则执行:

整个函数如下:

用此方法可以有效的转置矩阵,我们来看一下此函数的时间复杂度:O(cols * elements)——矩阵的列*矩阵的元素总和;

如果元素很多就会浪费很多的时间。有没有办法让两层循环变成一层循环呢?付出空间上的代价,换取时间效率;

我们只用一层循环来遍历数组a中所有元素,并把该元素放到指定的位置。这样我们就需要一个数组star来存放第i个元素所在位置。在定义这个数组之前,我们还需要一个数组term来实现统计矩阵第i行元素的数量。这样我们才能更方便的知道第i个元素应该存放的位置。

第一个循环初始化term,每个元素都为零。第二个循环是为了统计第i行元素的数量。第三个循环是设置第i个元素所在的位置。因为数组a的第一个元素是存放行列和元素的总数,因此第三个循环要从k = 1开始。此时两个数组的元素为:

下一步就是遍历a中的所有元素,然后根据a[i].col的值来把a[i].value放到指定的位置。

需要注意的是b的第一个元素与a中的第一个元素是同样的。b_star = star[a[i].col]++;因为当term[1] = 2;而star[1] = 3;就是a[i].col = 1时有两个元素,第一个元素的位置是star[a[i].col];而第二个元素的位置就是star[a[i].col] + 1所以在此用star[a[i].col]++。为下一个元素设置相应的位置;

完整函数:

此函数每个循环体的执行次数分别为cols cols elements elements 时间复杂度为O(cols + elements)和O(cols * elements)相差好多,尤其是clos 和 elements很大的时候;

完整的测试程序:

1 3 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部