备案控制台
开发者社区 人工智能 文章 正文

稀疏矩阵算法

2011-05-03 709
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 1、稀疏矩阵的压缩存储    　为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。

1、稀疏矩阵的压缩存储
    　为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
    　其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
    　稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法。

2、三元组表
    　将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。
  注意：
　    以下的讨论中，均假定三元组是按行优先顺序排列的。
　　　　　　
（1）三元组表的类型说明
　    为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：
  #define MaxSize 10000 //由用户定义
  typedef int DataType； //由用户定义
  typedef struct { //三元组
    int i，j；//非零元的行、列号
    DataType v； //非零元的值
   }TriTupleNode；

  typedef struct{ //三元组表
    TriTupleNode data[MaxSize]； //三元组表空间
    int m,n，t； //矩阵的行数、列数及非零元个数
  }TriTupleTable； 
    
(2) 压缩存储结构上矩阵的转置运算
    一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
         A[i][j]=B[j][i]，0≤i<m，0≤j<n，
    即A的行是B的列，A的列是B的行。

①三元组表表示的矩阵转置的思想方法
　　第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
　　第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data。

②三元组表的转置
    　方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
    　方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
    　按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。

下面是完整的稀疏矩阵算法，包括加法，转置，乘法等

#include <stdio.h>
#include <stdlib.h>
#define A 6
#define B 7
#define A1 3
#define B1 4
#define A2 4
#define B2 2
#define OK 1
#define ERROR -1;
#define MAXSIZE 1000

typedef int Status;
typedef int ElemType;
typedef struct {
  int i,j;
  ElemType e;
}Triple;       
typedef struct {
  Triple data[MAXSIZE+1];
  int rpos[MAXSIZE+1];
  int mu,nu,tu;
}TSMatrix;       

void CreatTripleTable (int array_a[A][B],TSMatrix *a)
/*array_aÊÇÒ»¸öÏ¡Êè¾ØÕó,aÊDzúÉúµÄÏà¶ÔÓ¦µÄÈýÔª×é´æ´¢*/
{                                                    
  int i,j,k=1;
  //a->data=(Triple *)malloc((MAXSIZE+1)*sizeof(Triple));
  for (i=0;i<A;i++) /*°´ÐÐÓÅÏÈ˳ÐòɨÃèarray_aµÄÔªËØ,²»Îª0Õß´æÈëBÖÐ*/
    for (j=0;j<B;j++)
      if (array_a[i][j]!=0)
      {      
        a->data[k].i=i+1;
        a->data[k].j=j+1;
        a->data[k].e = array_a[i][j];
        //printf("i=%d\n",a->data[k].i);
        //printf("j=%d\n",a->data[k].j);
        //printf("e=%d\n",a->data[k].e);
        //printf("k=%d\n",k);
        //printf("\n");
        k++;
      }
  a->mu=A;
  a->nu=B;
 // data[0][1]=N;
  a->tu=k-1;/*´æÈë·Ç0ÔªËظöÊý*/
}/*CreatTripleTable*/

void CreatTripleTable1 (int array_a[A1][B1],TSMatrix *a)
/*array_aÊÇÒ»¸öÏ¡Êè¾ØÕó,aÊDzúÉúµÄÏà¶ÔÓ¦µÄÈýÔª×é´æ´¢*/
{                                                    
  int i,j,k=1;
  //a->data=(Triple *)malloc((MAXSIZE+1)*sizeof(Triple));
  for (i=0;i<A1;i++) /*°´ÐÐÓÅÏÈ˳ÐòɨÃèarray_aµÄÔªËØ,²»Îª0Õß´æÈëBÖÐ*/
    for (j=0;j<B1;j++)
      if (array_a[i][j]!=0)
      {      
        a->data[k].i=i+1;
        a->data[k].j=j+1;
        a->data[k].e = array_a[i][j];
        k++;
      }
  a->mu=A1;
  a->nu=B1;
  a->tu=k-1;/*´æÈë·Ç0ÔªËظöÊý*/
}

void CreatTripleTable2 (int array_a[A2][B2],TSMatrix *a)
/*array_aÊÇÒ»¸öÏ¡Êè¾ØÕó,aÊDzúÉúµÄÏà¶ÔÓ¦µÄÈýÔª×é´æ´¢*/
{                                                    
  int i,j,k=1;
  //a->data=(Triple *)malloc((MAXSIZE+1)*sizeof(Triple));
  for (i=0;i<A2;i++) /*°´ÐÐÓÅÏÈ˳ÐòɨÃèarray_aµÄÔªËØ,²»Îª0Õß´æÈëBÖÐ*/
    for (j=0;j<B2;j++)
      if (array_a[i][j]!=0)
      {      
        a->data[k].i=i+1;
        a->data[k].j=j+1;
        a->data[k].e = array_a[i][j];
        k++;
      }
  a->mu=A2;
  a->nu=B2;
  a->tu=k-1;/*´æÈë·Ç0ÔªËظöÊý*/
}

Status TransposeSMatrix(TSMatrix *M,TSMatrix *T)
{
  int p,q,col;     
  T->mu=M->nu;  T->nu=M->mu;  T->tu=M->tu;
  if (T->tu) {
    q=1;
    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].j=M->data[p].i; 
          T->data[q].e=M->data[p].e;    ++q;
        }   
  }         
  return OK;
}

Status FastTransposeSMatrix(TSMatrix *M,TSMatrix *T)
{
  int t,p,q,col,num[A],cpot[M->nu];     
  T->mu=M->mu;  T->nu=M->mu;  T->tu=M->tu;
  if (T->tu) {
    for (col=1;col<=M->nu;++col) num[col]=0;
    for (t=1;t<=M->tu;++t) ++num[M->data[t].j];
    cpot[1]=1;
    for (col=2;col<=M->nu;++col) cpot[col]=cpot[col-1]+num[col-1];
    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=M->data[p].e;    ++cpot[col];
    }   
  }               
  return OK;
}  

Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *C)//ÈýÔª×é±íʾµÄÏ¡Êè¾ØÕó¼Ó·¨
{
  int i,j,x,ce,pa,pb,pc;  
  if (M.mu!=N.mu || M.nu!=N.nu) return ERROR;
  C->mu=M.mu;C->nu=M.nu;C->tu=0;
  pa=1;pb=1;pc=1;
  for(x=1;x<=M.mu;x++) //¶Ô¾ØÕóµÄÿһÐнøÐмӷ¨
  {
    while(M.data[pa].i<x) pa++;
    while(M.data[pb].i<x) pb++;
    while(M.data[pa].i==x&&N.data[pb].i==x)//ÐÐÁÐÖµ¶¼ÏàµÈµÄÔªËØ
    {
      if(M.data[pa].j==N.data[pb].j)
      {
        ce=M.data[pa].e+N.data[pb].e;
        if(ce) //ºÍ²»Îª0
        {
          C->data[pc].i=x;
          C->data[pc].j=M.data[pa].j;
          C->data[pc].e=ce;
          pa++;pb++;pc++;
        }
      }//if
      else if(M.data[pa].j>N.data[pb].j)
      {
        C->data[pc].i=x;
        C->data[pc].j=N.data[pb].j;
        C->data[pc].e=N.data[pb].e;
        pb++;pc++;
      }
      else
      {
        C->data[pc].i=x;
        C->data[pc].j=M.data[pa].j;
        C->data[pc].e=M.data[pa].e;
        pa++;pc++;
      }
    }//while
    while(M.data[pa].i==x) //²åÈëAÖÐÊ£ÓàµÄÔªËØ(µÚxÐÐ)
    {
      C->data[pc].i=x;
      C->data[pc].j=M.data[pa].j;
      C->data[pc].e=M.data[pa].e;
      pa++;pc++;
    }
    while(N.data[pb].i==x) //²åÈëBÖÐÊ£ÓàµÄÔªËØ(µÚxÐÐ)
    {
      C->data[pc].i=x;
      C->data[pc].j=N.data[pb].j;
      C->data[pc].e=N.data[pb].e;
      pb++;pc++;
    }
  }//for
  C->tu=pc;
  return OK;
}//TSMatrix_Add  

void PrintSMatrix(TSMatrix M)
{
  int i,j,pa; 
  int a[M.mu][M.nu];
  pa=1;
  for (i=0;i<M.mu;i++)  
    for (j=0;j<M.nu;j++)
      a[i][j]=0;
  for (pa=1;pa<=M.tu;pa++) {   
    //printf("%d\n",M.data[pa].i);
    //printf("%d\n",M.data[pa].j);
    //printf("%d\n",M.data[pa].e);
    a[M.data[pa].i-1][M.data[pa].j-1]=M.data[pa].e;
  } 
  for (i=0;i<M.mu;i++) {  
    for (j=0;j<M.nu;j++)
      printf("%6d",a[i][j]);            
      printf("\n");
  } 
  printf("\n");
}   

void GetRpos(TSMatrix *M) {
  int row,t,j,num[M->mu],cpot[M->nu];
  for (row=1;row<=M->mu;++row) num[row]=0; 
  for (t=1;t<=M->tu;++t) ++num[M->data[t].i];
  M->rpos[1]=1;
  for (row=2;row<=M->mu;++row) M->rpos[row]=M->rpos[row-1]+num[row-1];
  for (t=1;t<=M->mu;++t) printf("%d\n",M->rpos[t]);
}                

Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) {
  int arrow,brow,tp,p,q,t,ccol,ctemp[Q->nu];    
  if (M.nu!=N.mu) return ERROR;
  Q->mu=M.mu;  Q->nu=N.nu;  Q->tu=0;
  if (M.tu*N.tu!=0) {   
    for (arrow=1;arrow<=M.mu;++arrow) {
      for (p=1;p<=N.nu;p++) ctemp[p]=0; 
      Q->rpos[arrow]=Q->tu+1;
      if (arrow<M.mu) tp=M.rpos[arrow+1];
      else tp=M.tu+1;
      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;} 
        for (q=N.rpos[brow]; q<t; ++q) {
          ccol=N.data[q].j;        
          //printf("ctemp[ccol]=%d\n",ctemp[ccol]);
          ctemp[ccol]+=M.data[p].e * N.data[q].e;
          //printf("ccol=%d\n",ccol);
          //printf("M.data[p].e * N.data[q].e=%d * %d\n",M.data[p].e,N.data[q].e);
          //printf("ctemp[ccol]=%d\n",ctemp[ccol]);
          //printf("")
        }   
      }   
      for (ccol=1; ccol<=Q->nu;++ccol)
        if (ctemp[ccol]){
          if (++Q->tu>MAXSIZE) return ERROR;
          Q->data[Q->tu].i=arrow;
          Q->data[Q->tu].j=ccol;
          Q->data[Q->tu].e=ctemp[ccol];
        }  
    }      
  }  
}      

void DestroySMatrix(TSMatrix M)
{
  M.mu=0;  M.nu=0;  M.tu=0;  
}    
                 
int main(int argc, char *argv[])
{
  TSMatrix a,b,c,d,e;  //Èç¹ûдΪ*a£¬Ôò±ØÐë¼ÓÉÏa=(TSMatrix *)malloc(sizeof(TSMatrix)),»ò¼ÓÒ»TSMatrix b,a=&b;
  TSMatrix aa,bb,cc;
  int array[A][B]={{0,12,9,0,0,0,0},{0,0,0,0,0,0,0},{-3,0,0,0,0,14,0},{0,0,24,0,0,0,0},{0,18,0,0,0,0,0},{15,0,0,-7,0,0,0}};
  int array1[A][B]={{0,12,3,4,0,0,0},{0,0,0,3,0,0,0},{-3,0,0,0,0,14,0},{0,0,24,0,0,0,0},{0,18,0,0,0,0,0},{15,0,0,-7,0,0,0}};
 
  int array2[A1][B1]={{3,0,0,5},{0,-1,0,0},{2,0,0,0}};
  int array3[A2][B2]={{0,2},{1,0},{-2,4},{0,0}};
 
  //a=(TSMatrix *)malloc(sizeof(TSMatrix)); 
  CreatTripleTable(array,&a);
  PrintSMatrix(a);
  printf("Transpose\n");
  TransposeSMatrix(&a,&c);
  PrintSMatrix(c);
  printf("Fast Transpose\n");
  FastTransposeSMatrix(&a,&d);
  PrintSMatrix(d);   
 
  printf("Add Transpose\n");
  CreatTripleTable(array1,&b); 
  TSMatrix_Add(a,b,&e);
  PrintSMatrix(e);
   
  CreatTripleTable1(array2,&aa);
  PrintSMatrix(aa);
  CreatTripleTable2(array3,&bb);
  PrintSMatrix(bb);
  GetRpos(&aa);
  GetRpos(&bb);
  MultSMatrix(aa,bb,&cc);
  PrintSMatrix(cc);

  DestroySMatrix(a);
  DestroySMatrix(b);               
  DestroySMatrix(c);
  DestroySMatrix(aa);
  DestroySMatrix(bb);               
  DestroySMatrix(cc);
  system("PAUSE"); 
  return 0;
}

文章标签：
存储
算法
人工智能
Java
Windows
孤独的猫董
目录
相关文章
算精通
|
7月前
|
存储 机器学习/深度学习 计算机视觉
稠密矩阵
稠密矩阵是一种特殊形式的矩阵，其中所有元素都是非零的。与稀疏矩阵相比，稠密矩阵在存储和计算时需要更多的空间和计算资源，因为它的所有元素都需要被存储和计算。
算精通
134 7
jerrywangsap
|
7月前
|
存储 人工智能 自然语言处理
什么是数据结构中的特殊矩阵和稀疏矩阵
什么是数据结构中的特殊矩阵和稀疏矩阵
jerrywangsap
117 0
拓端数据部落
|
6天前
|
机器学习/深度学习 搜索推荐 数据挖掘
R语言矩阵特征值分解(谱分解)和奇异值分解(SVD)特征向量分析有价证券数据
R语言矩阵特征值分解(谱分解)和奇异值分解(SVD)特征向量分析有价证券数据
拓端数据部落
25 6
算精通
|
6月前
|
存储 机器学习/深度学习 算法
稀疏矩阵
稀疏矩阵是一种特殊形式的矩阵，其中大部分元素都是零。与密集矩阵相比，稀疏矩阵在存储和计算时可以采用特殊的算法和数据结构，以提高计算效率和节省存储空间。
算精通
78 3
闻缺陷则喜何志丹
|
6天前
|
算法 测试技术 C++
【动态规划】【数学】【C++算法】805 数组的均值分割
【动态规划】【数学】【C++算法】805 数组的均值分割
闻缺陷则喜何志丹
32 0
阿芒96
|
10月前
7.1 向量及其线性运算
7.1 向量及其线性运算
阿芒96
63 0
软件开发架构
|
8月前
|
存储 NoSQL
第3章 数组与矩阵——3.5 稀疏矩阵
第3章 数组与矩阵——3.5 稀疏矩阵
软件开发架构
84 0
断墨寻径
|
8月前
|
人工智能
矩阵乘法和逆
矩阵乘法和逆
断墨寻径
44 0
软件开发架构
|
8月前
|
机器学习/深度学习 前端开发 rax
第3章 数组与矩阵——3.4 矩阵运算(1)
第3章 数组与矩阵——3.4 矩阵运算(1)
软件开发架构
48 0
软件开发架构
|
8月前
|
机器学习/深度学习 资源调度 算法
第3章 数组与矩阵——3.4 矩阵运算(2)
第3章 数组与矩阵——3.4 矩阵运算(2)
软件开发架构
100 0

热门文章

最新文章

  • 1
    袋鼠云数据中台专栏（五）：数栈，企业级一站式数据中台PaaS
  • 2
    利用Serverless Kubernetes和Kaniko快速自动化构建容器镜像
  • 3
    阿里云oss收费标准
  • 4
    SpringBoot开发案例之整合Kafka实现消息队列
  • 5
    LINQ 图解
  • 6
    keepalived高可用LVS与Nginx
  • 7
    beyondhedefang的意义
  • 8
    v-on 指令
  • 9
    Java 8的一些常见用法
  • 10
    LLVM每日谈之十六 LLVM的学习感悟
  • 1
    构建高效可靠的微服务架构：后端开发的新趋势
    24
  • 2
    Kubernetes 集群的监控与日志管理最佳实践
    32
  • 3
    苹果app开发apple-app-site-association文件配置
    20
  • 4
    阿里云MaxCompute携手华大基因打造精准医疗应用云平台，十万基因组计算成本降低至1000美金以内
    610
  • 5
    构建高效自动化运维系统：DevOps与AI的融合
    26
  • 6
    深入理解PHP中的命名空间
    16
  • 7
    深度学习在图像识别中的应用及其挑战
    18
  • 8
    提升软件测试效率：智能化测试工具的应用与展望
    19
  • 9
    阿里云容器服务
    30
  • 10
    为什么是容器编排技术
    19

    • 相关课程

    更多
  • 【算法实战】15. 利用SVD来简化数据
  • 【算法实战】10. 树回归算法
  • 【算法实战】2. K近邻算法
  • 【算法实战】5. Logistic回归算法
  • 【算法实战】9. 线性回归算法
  • 【算法实战】11. K-Means（K-均值）聚类算法

    • 相关电子书

    更多
  • ADMM
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考