网站备案去哪,福田公司网站建设,做爰的细节描述和过程网站,教育机构代理平台1.压缩存储的目标
值相同的元素只存储一次
压缩掉对零元的存储#xff0c;只存储非零元
特殊形状矩阵#xff1a;
是指非零元#xff08;如值相同的元素#xff09;或零元素分布具有一定规律性的矩阵。
如#xff1a; 对称矩阵 上三角矩阵 下三角矩阵 对角矩阵 准…1.压缩存储的目标
值相同的元素只存储一次
压缩掉对零元的存储只存储非零元
特殊形状矩阵
是指非零元如值相同的元素或零元素分布具有一定规律性的矩阵。
如 对称矩阵 上三角矩阵 下三角矩阵 对角矩阵 准对角矩阵
2.三角矩阵
三角矩阵大体分为三类下三角矩阵、上三角矩阵和对称矩阵。
对于一个n阶矩阵A来说若当ij时有aij0则称此矩阵为下三角矩阵
若当ij时有aij0则称此矩阵为上三角矩阵
若矩阵中的所有元素均满足aijaji则称此矩阵为对称矩阵。 对于下三角矩阵的压缩存储我们只存储下三角的非零元素对于零元素则不存。我们按“行序为主序”进行存储得到的序列是a11, a21, a22, a31, a32, a33, …, an1, an2, …, ann。由于下三角矩阵的元素个数为n(n1)/2即 所以可压缩存储到一个大小为n(n1)/2的一维数组C中 下三角矩阵中元素aij(ij)在一维数组A中的位置为
Loci, jLoc1, 1前i-1行非零元素个数第i行中aij前非零元素个数
前i-1行元素个数1234…i-1i(i-1)/2所以有 Loci, jLoc1, 1i(i-1)/2j-1
同样对于上三角矩阵也可以将其压缩存储到一个大小为n(n1)/2的一维数组C中。其中元素aij(ij)在数组C中的存储位置为 Loci, jLoc1, 1j(j-1)/2i-1
对于对称矩阵因其元素满足aijaji我们可以为每一对相等的元素分配一个存储空间即只存下三角或上三角矩阵从而将n2个元素压缩到n(n1)/2个空间中。
3.带状矩阵 三对角带状矩阵有如下特点
i1, j1, 2
1in, ji-1, i, i1;
in, jn-1, n;
时aij非零其它元素均为零。 1确定存储该矩阵所需的一维向量空间的大小
在这里我们假设每个非零元素所占空间的大小为1个单元。 从图中观察得知三对角带状矩阵中除了第一行和最后一行只有2个非零元素外其余各行均有3个非零元素。由此得到 所需一维向量空间的大小为 223n-2)3n-2 2确定非零元素在一维数组空间中的位置
Loci , j Loc1, 1前i-1行非零元素个数第i行中aij前非零元素个数
前i-1行元素个数3×i-1-1因为第1行只有2个非零元素
第i行中aij前非零元素个数j-i1其中 由此得到
Loci, jLoc1, 13(i-1)-1j-i1 Loc1, 12(i-1)j-1
4.稀疏矩阵
是指非零元比零元少得多且非零元在矩阵中的分布不具有一定规律性的矩阵。 假设 m 行 n 列的矩阵含 t 个非零元素则称 为稀疏因子。 通常认为 小于等于0.05 的矩阵为稀疏矩阵。
1稀疏矩阵的三元组表表示法
对于矩阵中的每个非零元可以用三个属性来惟一确定它所在的行、所在的例以及它的值。因此可以用一个三元组(行, 列, 值)来惟一确定矩阵中的一个非零元。 稀疏矩阵的三元组表表示法虽然节约了存储空间 但比起矩阵正常的存储方式来讲其实现相同操作要耗费较多的时间 同时也增加了算法的难度, 即以耗费更多时间为代价来换取空间的节省。
define MAXSIZE 1000 /*非零元素的个数最多为1000*/ typedef struct {int row, col; /*该非零元素的行下标和列下标*/ElementType e /*该非零元素的值*/ }Triple; typedef struct {Triple dataMAXSIZE1; /* 非零元素的三元组表data0未用*/int m, n, len; /*矩阵的行数、 列数和非零元素的个数*/
}TSMatrix 1) 用三元组表实现稀疏矩阵的转置运算
下面首先以稀疏矩阵的转置运算为例介绍采用三元组表时的实现方法。
所谓的矩阵转置是指变换元素的位置把位于rowcol位置上的元素换到colrow位置上也就是说 把元素的行列互换。
采用矩阵的正常存储方式时 实现矩阵转置的经典算法如下
void TransMatrixElementType sourcenm, ElementType destmn
{/*source和dest分别为被转置的矩阵和转置以后的矩阵用二维数组表示*/ int i, j; for(i0; im; i)for (j0; j n; j) desti jsourcej i ; }采用矩阵的三元组存储方式实现转置
① 矩阵source的三元组表A的行、 列互换就可以得到B中的元素 ② 为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放则需要对行、列互换后的三元组表B按B的行下标即A的列下标大小重新排序 方法一 我们附设一个位置计数器j用于指向当前转置后元素应放入三元组表B中的位置。 处理完一个元素后j加1 j的初值为1。 具体转置算法如下
Void TransposeTSMatrix(TSMatrix A, TSMatrix *B)
{ /*把矩阵A转置到B所指向的矩阵中去 矩阵用三元组表表示 */int i , j, k ; B-m A.n ; B-n A.m ; B-len A.len ; if(B-len0){
j1; for(k1; kA.n; k) for(i1; iA.len; i) if(A.datai.colk) { B-dataj.rowA.datai.col B-dataj.colA.datai.row; B-dataj.eA.datai.e; j; }}
} 算法的时间耗费主要是在双重循环中其时间复杂度为OA.n×A.len, 最坏情况下当A.lenA.m×A.n时时间复杂度为OA.m×A.n2。采用正常方式实现矩阵转置的算法时间复杂度为OA.m×A.n。
方法二 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上需要预先计算以下数据 (1) 待转置矩阵source每一列中非零元素的个数即转置后矩阵dest每一行中非零元素的个数。
(2) 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置即转置后矩阵dest每一行中第一个非零元素在三元组B中的正确位置)。 为此 需要设两个数组num 和position 其中numcol用来存放三元组表A中第col列中非零元素个数三元组表B中第col行非零元素的个数positioncol用来存放转置前三元组表A中第col列转置后三元组表B中第col行中第一个非零元素在三元组表B中的正确位置。
numcol的计算方法 将三元组表A扫描一遍对于其中列号为k的元素给相应的numk加1。
positioncol的计算方法 position11 positioncolpositioncol-1numcol-1 其中2≤col≤A.n。 将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法
positioncol的初值为三元组表A中第col列三元组表B的第col行中第一个非零元素的正确位置当三元组表A中第col列有一个元素加入到三元组表B时则positioncolpositioncol1即 使positioncol始终指向三元组表A中第col列中下一个非零元素的正确位置。
具体算法如下
FastTransposeTSMatrix (TSMatrix A, TSMatrix * B)
{ /*基于矩阵的三元组表示 采用快速转置法 将矩阵A转置为B所指的矩阵*/
int col, t, p q;
int numMAXSIZE, positionMAXSIZE;
B-lenA.len; B-nA.m; B-mA.n;
if(B-len){
for(col1; colA.n; col) numcol0; for(t1; tA.len; t) numA.datat.col; /*计算每一列的非零元素的个数*/position11; for(col2; colA.n; col) /*求col列中第一个非零元素在B.data 中的正
确位置 */positioncolpositioncol-1numcol-1; for(p1; pA.len.p) { colA.datap.col; qpositioncol; B-dataq.rowA.datap.col; B-dataq.colA.datap.row; B-dataq.eA.datap.epositioncol; }
}
} 快速转置算法的时间主要耗费在四个并列的单循环上这四个并列的单循环分别执行了A.nA.lenA.n-1A.len次因而总的时间复杂度为O(A.n)O(A.len)O(A.n)O(A.len)即为OA.nA.len。 当待转置矩阵M中非零元素个数接近于A.m×A.n 时其时间复杂度接近于经典算法的时间复杂度O(A.m×A.n)。
快速转置算法在空间耗费上除了三元组表所占用的空间外还需要两个辅助向量空间即num1..A.nposition1..A.n。可见算法在时间上的节省是以更多的存储空间为代价的。
2稀疏矩阵的链式存储结构: 十字链表
与用二维数组存储稀疏矩阵比较用三元组表表示的稀疏矩阵节约了空间但是在进行矩阵加法、减法和乘法等运算时有时矩阵中的非零元素的位置和个数会发生很大的变化。如AAB 将矩阵B加到矩阵A上此时若还用三元组表表示法势必会为了保持三元组表“以行序为主序”而大量移动元素。
在十字链表中矩阵的每一个非零元素用一个结点表示 该结点除了rowcolvalue以外还要有以下两个链域 right 用于链接同一行中的下一个非零元素
down 用于链接同一列中的下一个非零元素。 用两个一维的指针数组分别存放各行链表的头指针和各列链表的头指针从而得到了矩阵的十字链表存储结构。 结构类型
建十字链表的算法的时间复杂度为Ot×ssmaxmn。
typedef struct OLNode{int row, col; /* 非零元素的行和列下标 */ ElementType value; struct OLNode * right, *down; /* 非零元素所在行表、列表的后继链域 */}OLNode; *OLink; typedef struct { OLink * row-head, *col-head; /* 行、 列链表的头指针向量 */ int m, n, len; /* 稀疏矩阵的行数、 列数、 非
零元素的个数 */}CrossList; CreateCrossList (CrossList * M){/* 采用十字链表存储结构 创建稀疏矩阵M */if(M!NULL) free(M); scanf(m, n, t); /* 输入M的行数, 列数和非零元素的个数 */M-mm; M-nn; M-lent; If(!(M-row-head(OLink * )malloc((m1)sizeof(OLink)))) exit(OVERFLOW); If(!(M-col-head(OLink * )malloc((n1)sizeof(OLink)))) exit(OVERFLOW); M-row-head M-col-head NULL;/* 初始化行、 列头指针向量 各行、 列链表为空的链表 */for(scanf(i, j, e); i!0; scanf(i, j, e)) { if(!(p(OLNode *) malloc(sizeof(OLNode)))) exit(OVERFLOW); p-rowi; p-colj; p-valuee; /* 生成结点 */ if(M-row-headiNULL) M-row-headip;
else{ /* 寻找行表中的插入位置 */for(qM-row-headi; q-rightq-right-colj; qq-right)p-rightq-right; q-rightp; /* 完成插入 */ } if(M-col-headjNULL) M-col-headjp; else{ /*寻找列表中的插入位置*/for(qM-col-headj; q-downq-down-rowi; qq-down) p-downq-down; q-downp; /* 完成插入 */ }}}
