稀疏矩阵乘法_稀疏矩阵的快速转置题目

稀疏矩阵乘法_稀疏矩阵的快速转置题目稀疏矩阵三元组顺序表用于储存压缩后的稀疏矩阵顺序存储表示#defineMAXSIZE125000//设置非零元素的最大个数为125000typedefstruct{ inti;//元素行号intj;//元素列号Elem

稀疏矩阵

三元组顺序表用于储存压缩后的稀疏矩阵

  • 顺序存储表示
#define MAXSIZE 125000//设置非零元素的最大个数为125000
typedef struct{ 
   
	int i;//元素行号
    int j;//元素列号
    Element  e;//元素值
}Tripe;
typedef struct { 
   
	Tripe data[MAXSIZE+1];
	int mu;//总行数
	int nu;//总列数
	int tu;//非零元个数
}TsMatrix;

在这里插入图片描述

三元组表的顺序存储结构

typedef struct { 
   
	Tripe data[Maxsize+1];
	int nu;//矩阵总列数
	int mu;//矩阵总行数
	int tu;//矩阵中非零元素的个数
}TSMatrix
typedef struct{ 
   
    int i;
    int j;
    Elementtype e;
}Tripe;

带辅助向量的三元组

主要用途

  • 便于高效访问稀疏矩阵中任一非零元素
i 1 2 3 4 5 6
NUM(i)
POS(i)
  • 其中NUM用于存储每列非零元的个数
  • POS用来记录每列第一个非零元素在新三元组中的位置
    pos(1)=1
    pos(i)=pos(i-1)+NUM(i-1)
//稀疏矩阵的转置
算法思路:
1.将每个三元组中i和j互相调换,再排序,但排序的时间复杂度
至少为o(tu^2)
2.依次从小到大找到最小的i,再转置
3.利用三元组的辅助向量精确放置转置后的元素

辅助元素的求解

NUM[i]表示第i列中的非零元素的个数
POS[i]表示第i列第一非零元素在新的三元组中行数
//求解过程如下 
POS[1]=1;
for(int i=1;i<=M.tu;i++)
	num[M.data[i].j]++;//求解列的NUM值
for(int i=2;i<=M.nu;i++)
POS[i]=POS[i-1]+NUM[i-1];//求解POS的值

全部算法展示

int FastTransposeSMatrx(TSMatirx M,TSMatirx *T)
{ 
   
  int col;
  int *NUM,*POS;
  NUM=(int *)malloc((M.nu+1)*sizeof(int));
  POS=(int *)malloc((M.nu+1)*sizeof(int));//动态数组
  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;
 	for(int i=1;i<=M.tu;i++)NUM[M.data[i].j]++;
  }//这里实际是在判断了T.tu非空
  POS[1]=1;
  for(int i=2;i<=M.nu;i++)
  POS[i]=POS[i-1]+NUM[i-1];
  for(int p=1;p<=M.tu;P++)
  { 
   
     col=M.data[p].j;
     q=POS[col];
     T.data[q].i=M.data[p].j;
     T.data[q].j=M.data[p].i;
     T.data[q].e=M.data[p].e
     POS[col]++;
  }
  return 0;
}

矩阵的相乘

矩阵相乘的经典算法

for(i = 0;i < rows_a;i++)
	for(j=0;j<col_b;j++)
	{ 
   
		sum=0;
	   for(k = 0;k < col_a;k++)
	   sum+=(a[i][k]*b[k][j]);
	   d[i][j]=sum;
	}
	//时间复杂度O(rows_a*cols_b*col__a)

稀疏矩阵相乘的高效方法

  • 思路如下

设有两个矩阵A,B相乘,C为相乘后的矩阵,由于aij和bjk相乘的积是需要累加到C矩阵中的cik中的,所以对于每一行的C元素的计算,只需要从A矩阵的每一行开始,每一个非零元aij去与B中第j行的非零元相乘再累加到对应的cik中去就可以了

  • 代码实现如下
#define MAXMN 500
typedef struct{ 
   
 Triple data[MAXSIZE + 1];//矩阵元素
 int rpos[MAXMN + 1];//各行第一个非零元素的位置表
 int mu,nu,tu;//总行数,总列数,非零元素个数
}RLSMatrix;//行逻辑链接顺序表类型

int MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{ 
   
	if(M.nu != N.mu) { 
   
	printf("error!");
	return -1 ;
    }
    Q.mu = M.mu; Q.nu = N.nu;Q.tu = 0;
    if(M.tu*N.tu != 0){ 
   
    //若为0矩阵则没必要进行计算了
      for(arow = 1;arow <= M.mu ; arow ++)
      { 
   
      	int count_arry[M.mu + 1] ={ 
   0};//各元素累加器定义并清零
        Q.rpos[arrow] = Q.tu + 1;//计算新矩阵的非零元素 的位置表
        if(arrow < M.tu )
        { 
   
        	tp = M.rpos[arow + 1];
        }
        else tp = M.tu + 1;
         //利用辅助元素记录稀疏矩阵每行首个非零元素的位
         //置,在运用时需要特别注意最后一个量,他不能直
         //接由后一个值来推出该行的总非零元素,而应该通 
         //过M.tu来获取信息
        for (p = M.rpos[arrow];p < tp;p++ ) { 
   
        	brow = M.data[p].j;
        	if (brow < N.mu) t = N.rpos[brow + 1];
        	else { 
    
        	  t = N.tu + 1;//这里是处理N矩阵在最后一个辅助元素的情况
        	}
        for (q = N.rpos[brow]; q < t; q++){ 
   
            ccol = N.data[q].j;
            count_arry[ccol] +=M.data[p].e*N.data[q].e;
        }//q
        }//p
      for(ccol = 1; ccol<=Q.nu;ccol++)
      { 
   
         if(++Q.tu > MAXSIZE)return -1;
         Q.data[Q.tu] = { 
   arow,ccol,count_arry[ccol]}
      }//for
      }//arow for
    
    }//if
return 0;
}

今天的文章稀疏矩阵乘法_稀疏矩阵的快速转置题目分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67012.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注