多维数组-矩阵的压缩存储- 稀疏矩阵(一)

 我来答
舒适还明净的海鸥i
2022-10-08 · TA获得超过1.7万个赞
知道小有建树答主
回答量:380
采纳率:0%
帮助的人:69.3万
展开全部

  稀疏矩阵

  设矩阵A mn 中有s个非零元素 若s远远小于矩阵元素的总数(即s< <m×n),则称a为稀疏矩阵。 p=""> </m×n),则称a为稀疏矩阵。>

  1、稀疏矩阵的压缩存储

  为了节省存储单元,可只存储非零元素。由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须存储非零

  元素所在的行号、列号,才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。

  其中每一个非零元素所在的行号、列号和值组成一个三元组(i,j,a ij ),并由此三元组惟一确定。

  稀疏矩阵进行压缩存储通常有两类方法:顺序存储和链式存储。链式存储方法【参见参考书目】。

  2、三元组表

  将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素),并依次存放在向量中,这种稀疏矩阵的顺序

  存储结构称为三元组表。

  注意:

  以下的讨论中,均假定三元组是按行优先顺序排列的。

  【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)

  

  (1)三元组表的类型说明

  为了运算方便,将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。.WINGwIT.其类型描述为:

  #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, p=""> </m,0≤j<n,>

  即A的行是B的列,A的列是B的行。

  【例】下图中的B和上图中的A互为转置矩阵。

  

  ①三元组表表示的矩阵转置的思想方法

  第一步:根据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的按行优先的压缩存贮表示。具体实现参见

  【 动画演示 】

  ③具体算法:

  void TransMatrix(TriTupleTable *b,TriTupleTable *a)

  {//*a,*b是矩阵A、B的三元组表表示,求A转置为B

  int p,q,col;

  b->m=a->n; b->n=a->m; //A和B的行列总数互换

  b->t=a->t; //非零元总数

  if(b->t<=0)

  Error("A=0"); //A中无非零元,退出

  q=0;

  for(col=0;coln;col++) //对A的每一列

  for(p=0;pt;p++) //扫描A的三元组表

  if(a->data[p].j==col){ //找列号为col的三元组

  b->data[q).i=a->data[p].j;

  b->data[q].j=a->data[p].i;

  b->data[q].v=a->data[p].v;

  q++;

  }

  } //TransMatrix

  ④算法分析

  该算法的时间主要耗费在col和p的二重循环上:

  若A的列数为n,非零元素个数t,则执行时间为O(n×t),即与A的列数和非零元素个数的乘积成正比。

  通常用二维数组表示矩阵时,其转置算法的执行时间是O(m×n),它正比于行数和列数的乘积。

  由于非零元素个数一般远远大于行数,因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。

lishixinzhi/Article/program/sjjg/201311/23897

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式