注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

稀疏矩阵转置  

2012-09-29 12:57:18|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


介绍三种求稀疏矩阵的转置的矩阵算法。

typedef struct element
{
float val;
int row,col;
} elem;
elem b[M];

(1)简单复制法


for(int i = 0;i < t ;i ++)
{
c[i].row = b[i].col; //行号变列号
c[i].col = b[i].row; //列号变行号
c[i].val = b[i].val;
}



时间复杂度:O(t)。
缺点:转置结果不是按行顺序存储的,而是按列顺序存储的。

(2)逐行复制法
思想:按行号从小到大依次复制矩阵中的各行非0元素。即先在数组b中寻找列号为0(b[i].col == 0)的元素,将其逐一复制到数组c中;
          然后再在数组b中寻找序列号为1(b[i].col == 1)的元素,将其注意复制到数组c中。(复制时要调换行列域的值)



for(int k = 0,j = 0;j < n;j ++)
{
for(int i = 0;i < t;i ++)
{
if(b[i].col == j)
{
c[k].row = b[i].col;
c[k].col = b[i].row;
c[k ++].val = b[i].val;
}

}
}


时间复杂度:O(nt)。

(3)分段定位法
包括预处理阶段和转置阶段,时间复杂度:O(n+t)
1)预处理阶段
对数组b进行一遍扫描,统计出矩阵的各列(即转置后的矩形的各行)非0元素个数,并记录在数组num[n]中。
然后利用num[n]计算行定位数组pot[n]各元素pot[j](j = 0,1,2,3,4.....n - 1)的值
(行定位数组pot[n]的作用是将存储转置矩阵的数组c分成n段,以便将转置矩阵第j行上的num[j]个非0元素存储在第j段。具体的说,pot[j]用来指示转置矩阵第j行非0元素在数组c中的起始存储位置)
pot[0] = 0;
pot[j] = pot[j - 1] + num[j - 1];  (j = 1,2,3...n-1) 

预处理结果
 4 5
 num2221
 pot8
      
2) 转置阶段
对数组b进行第二次扫描。当扫描到b[i]时,取出其序列号 j = b[i].col,由j找到行定位指针k = pot[j],将该非0元素复制到c[k]。当然要交换行列号。


void transpose(elem b[],elem c,int n,int t)
{
//数组b[t]存储稀疏矩阵A(m*n)的t个元素,n是A的列数
//数组c[t]用于存储转置矩阵A的非0元素
int i,j,k,num[n],pot[n];
//预处理阶段
for(j = 0;j < n;j ++) num[j] = 0;
for(i = 0;i < t;i ++) num[b[i].col]++;
for(pot[0] = 0,j = 1;j < n;j ++) pot[j] = pot[j - 1] + num[j - 1];
//转置阶段
for(i = 0;i < t;i ++)
{
j = b[i].col; //取列号
k = pot[j]; //取行定位指针

c[k].row = j;
c[k].col = b[i].row;
c[k].val = b[i].val;

pot[j] ++; //修改定位指针为本行下一个非0元素的位置
}
}






  评论这张
 
阅读(1102)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018