⑴ 矩阵的压缩存储例子
稀疏矩阵压缩存储
一般来讲,零元素多到了一定程度并且没有规律分布的矩阵叫做稀疏矩阵。对稀疏矩阵的压缩存储必须充分考虑以下三个问题:
① 尽可能减少或者不存储零元素以节省空间,降低空间复杂度。
② 尽可能快地实现数据元素的存储位置与原有位置之间的转换。
③ 尽可能不与零元素进行运算,以降低时间复杂度。
稀疏矩阵的压缩存储有三种最常见的方法,分别是三元组顺序表、行逻辑链接顺序表和十字链表。
⑵ 矩阵的压缩存储
可以看出,我们仅需声明一个长度为(1+n)n/2的一维数组array即可,剩余的都是重复的元素。
假设一维数组存储的是下三角部分,并且我们现在找的a[i][j]也是在下三角,则:
写成完整的公式,如下所示
此时我们可以声明一个长度为(1 + n) * n / 2 + 1的一维数组来存储这个三角矩阵,+1是增加一个存储常数的空间。
线代里的对角矩阵,除对角线外,其余元素都是0:
我们这里说的是非零元素都集中在对角线上下若干条对角线的对角矩阵。
n阶对角矩阵的存储有些困难,假设a条对角线是非0元,则一维数组array的大小为:
给定 i j,找对应的 k
如何压缩?我们只需要存储非0元即可,我们可以定义一个结构体:
进行压缩后的存储方式:
第一行表明原矩阵是5 * 5,并且有3个非0元
⑶ 多维数组-矩阵的压缩存储- 稀疏矩阵(一)
稀疏矩阵
设矩阵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),它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数,因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
lishixin/Article/program/sjjg/201311/23897
⑷ 特殊矩阵的压缩存储:上三角、对称、下三角存储,有三个问题。求大侠们解答~亲一个~这个图能看清吗
1.k=n*(n+1)/2的原因是:对于三角矩阵,从1到N的总和是这么多,也就是说整个矩阵有这么多元素。另外正三角阵对应正方形。
对称矩阵满足A的转置也就是自身的特点,元素上,a[i,j] = a[j,i]。实际上的存储可以利用三角阵。所以老实说我对于他对称阵算法为什么少一个元素也有疑惑。
可能是三角阵可以对应不等长的矩阵,所以造成了k值不一样。
2.上三角阵,存在的元素是满足[1<= j <=n, i >= j]的关系[这里用i表横坐标j表纵坐标],如果是长3宽4的当然不能和长4宽3的相提并论,试着画画就明白了。
3.对称阵不会出现像三角阵那样有一小角还是其他数字的情况。这个其他数字就是(6+1)-1=6。
4.压缩存储,只是将部分符合条件的矩阵减少一部分的存储空间。老实说我也感觉不很有用,除非他处理的数据本身必然具备此类特点。
5.固定的,多试几次自己记下来然后找找就好。如果没记错的话,在矩阵上画画就可以看出来。
6.stdlib.h是标准的输入输出库,最为常用,至少里面包括了scanf等函数,只要你需要printf你就不能扔掉它。否则会出现函数未定义的问题。毕竟语言本身不提供函数类库,类库需要另行引用。
⑸ 什么是压缩矩阵
在这里分开来给你解释
矩阵是许多科学计算、工程数学尤其是数值分析中经常研究的对象,矩阵也就是二维数组,所以它可以采用顺
序存储是来存储其中的元素。但有时矩阵的阶数很高,同时在矩阵中游很多值相同的元素,或大多数元素的值为
零,这时再采用严格的顺序存储显然是很浪费空间的,因为存储零元素或许多值相同的元素是没有意义的,因此为
了节省存储空间,对这类矩阵通常采用压缩存储。
压缩存储:为多个值相同的元素值分配一个存储空间,对零元素不分配存储空间。
特殊矩阵:各个元素的分布有一定规律
系数矩阵:矩阵中多数元素值为零。
⑹ 上三角矩阵的压缩存储原则是怎样的
上三角矩阵的压缩存储原则:对于三角矩阵,从1到N的总和是这么多,也就是说整个矩阵有这么多元素。另外正三角阵对应正方形。
经常出现一些阶数很高的矩阵,同时在矩阵中非零元素呈某种规律分布或者矩阵中有大量的零元素,若仍然用常规方法存储,可能存储重复的非零元素或零元素,这将造成存储空间的大量浪费。因此对这类矩阵进行压缩存储,从而合理地利用存储空间。
简正模式:
矩阵在物理学中的另一类泛应用是描述线性耦合调和系统。这类系统的运动方程可以用矩阵的形式来表示,即用一个质量矩阵乘以一个广义速度来给出运动项,用力矩阵乘以位移向量来刻画相互作用。求系统的解的最优方法是将矩阵的特征向量求出(通过对角化等方式)。
称为系统的简正模式。这种求解方式在研究分子内部动力学模式时十分重要:系统内部由化学键结合的原子的振动可以表示成简正振动模式的叠加。描述力学振动或电路振荡时,也需要使用简正模式求解。
⑺ 怎样压缩矩阵元素的存储空间
AC
稀疏矩阵(SparseMatrix):是矩阵中的一种特殊情况,其非零元素的个数远小于零元素的个数.
压缩存储:为多个值相同的元素只分配一个存储空间;对0元素不分配空间.目的是节省大量存储空间.
当使用三元组顺序表(又称有序的双下标法)压缩存储稀疏矩阵时,对矩阵中的每个非零元素用三个域分别表示其所在的行号,列号和元素值.它的特点是,非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算.当矩阵中的非0元素少于1/3时即可节省存储空间.
⑻ 数据结构-特殊矩阵的压缩存储
本文介绍对称矩阵、三角矩阵、对角矩阵和稀疏矩阵的压缩存储方法。
在一个n阶矩阵A中,若元素满足aij=aji,0<=i,j<=n-1,则称矩阵A为对称矩阵。
按行优先顺序将这些元素存放在一个一维数组s[n(n+1)/2]中,元素aij在s中对应的下标为k:
以主对角线划分,三角矩阵分为上三角和下三角两种,上三角矩阵的下三角所有元素均为常数c,下三角矩阵正好相反。
按行优先顺序将三角矩阵存放在一维数组s[n(n+1)/2+1],其中常数c存放在数组的最后一个分量中。
上三角矩阵元素aij在s中对应的下标为k:
下三角矩阵元素aij在s中对应的下标为k:
对角矩阵是指矩阵中所有的非零元素集中在以主对角线为中心的带状区域中。一个k对角矩阵(k为奇数)A满足若|i-j|>(k-1)/2则元素aij=0。
将三对角矩阵A中的非零元素按行优先顺序存放到数组s[3n-2]中,在三对角矩阵A中,除第一行和最后一行只有两个非零元素外,其他每行中均有三个非零元素。三对角矩阵中的元素aij在s中对应的下标为 k=3×i-1+j-(i-1)=2×i+j .
设矩阵Amn中有s个非零元素,若s远远小于矩阵元素的总数,即s<<mxn,则称A为稀疏矩阵。
对于稀疏矩阵的压缩存储方法通常有两种,分别是三元组顺序表和十字链表。
1. 三元组顺序表
每个元素是一个结构体,包括该元素在矩阵中的行数、列数和数值,所有元素存在一个向量vector中,并同时记录矩阵的行数、列数及非零元素个数等信息。
2. 十字链表
为了克服顺序表中对非零元素插入和删除操作带来的不便,采用链接存储结构存储稀疏矩阵。
十字链表将每个元素存储为一个结构体,除了包括元素的行号、列号、数值外,还包括一个向右指针域用于指向同一行中的下一个非零元素和一个向下指针域用于指向同一列中的下一个非零元素。所有结构体通过两个一维指针数组分别存储各个行链表的头指针和各个列链表的头指针组织成一个整体。
目标是将每个元素的行号列号交换,并按照新的行列号按序存放。关键在于如何高效地进行按序存放。
方法一:朴素转置算法
按照原列号分别从头至尾扫描,依次放入新的矩阵中。对于一个m行n列且非零元素个数为t的稀疏矩阵而言,该算法的时间复杂度为O(t×n)。
方法二:快速转置算法
采用一个数组cnum[cols]记录每一列中的元素个数,一个数组cpot[cols]记录每一列的第一个非零元素在转置矩阵顺序表中的下标。cnum和cpot各采用一次遍历得到,其中cpot[0]=0,cpot[col]=cpot[col-1]+cnum[col-1]。