2014/47 §5.2矩阵的压缩存储 s5.2矩阵的压缩存储 void TransMatrix (TripleTable &a,TripleTable &b)(A=>B int p.q.col ①方法二：按A的行序转置。 if (a.t==0)Error(A is empty ) 若简单的变换a.data的行和列，则b.data为列主序存储， b.m=a.n:b.n=a.m;b.t=a.t:l行列数互换 要重排。但若预先确定A中每一列（即B中每一行）的 q=0:指示转置过的三元组 第一个非零元在b.data中应有的位置，则可正确转置。 for(cal=0:col<a.n;col++Yl对A的每一列号 位置向量： for(p=0:psa.tpt+)M扫描A的三元组表 f(a.data[p],.j=col{l找A的列号为col的三元组 [po0=0∥的第0列起址 b.data[gl.i=a.data[p].j: poffcol]=po4col-]+第col-1列非零元个数0≤col≤an-1 b.data[q].j=a.data[p].i: 时同0口)一般矩阵转 b.data[q]v=a.data[p].v 程时间Omm.面cm,款 时间一般大于普差转 q++: 置，当m时为0am) S5.2矩阵的压缩存储 §5.2矩阵的压缩存储 ■思想 void FastTransMatrix(TripleTable&a,Tripletable&b)/po[o..a.n，小比n多t if(a.t=0)Emor(代./lA全零 先求出A中每一列的非零元个数，可将第c0列 b.m =a.n;b.n a.n;b.t=a.t; 的非零元个数记入poco41]中。 for(col=0,col<=a.n:col++)potfcol]=0://step1初始化 for(p=0:p<a.tpt+)∥step2扫描a.data √step1:初始化将所有pot中元素清0. 1/O( pola.data[pl.j+1++:∥设a.datalp]」=col potfa.nj是哨兵 √step2:扫描adata,将列号为col的非零元个数累加到 for(col=1:col<a.n;col++)sep3.po叫a.nj抚用，但第二个循环须统计 pot[col41]中。 /o) pot[col]pot[col -1]+potfcol]: step3:potfcol]=pot[col-1]+pot[col]I<col<a.n-1 for (p=0:p<a.t:p++)(//step4 1O(n) cd=a.data[p小：/当前三元组列号 q=pot[col++; √step4:扫描a.data,.将(i,col,y)转置后放于b.data[pot co b.data[q]i=a.data[p] 中，pot[col]++. l0(D b.datalq]j=a.datalpli 时间Ontt),快速 b.data[q]-v=a.datalp].v. kcy:pot1a.n-第0-an-1列的非零元个数。 85.2矩阵的压缩存储 s5.2矩阵的压缩存储 以上图为例，A 3 十字链表 p时 0 ·前和列1个 上两种方式是顺序存储，若非零元位置或个数经常发生 变化，会引起结点移动，效率降低。此时宜用链式存储 2 2 埋元及领 例：A-A+B 篇1中零元个量 2 1 第1中军元个慧 3 稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表 0 第3列零元个 ·结点结构 第4列件半元个数（无用】 1 一行向品上下一半等元 带行表的三元组表。（顺序方式） 。存储结构 列上下一中零元 在行优先存储的三元组表中，加入一个行 分别设两个指针数组作为各行、列单链表的头指针。 表来记录稀疏矩阵压缩后每行非零元在三元组表 中的起始位置。2014/4/7 4 §5.2 矩阵的压缩存储 void TransMatrix（TripleTable &a, TripleTable &b) {//A=>B int p, q, col; if (a.t == 0) Error(“A is empty”); b.m = a.n; b.n = a.m; b.t = a.t ; //行列数互换 q=0; //指示转置过的三元组 for( col = 0; col < a.n ; col++)//对A的每一列号 f ( 0 )//扫描 的三元组表 19 for( p = 0; p < a.t; p++)//扫描A的三元组表 if (a.data[p].j == col) {//找A的列号为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++; } } §5.2 矩阵的压缩存储 ① 方法二：按A的行序转置。 若简单的变换a.data的行和列，则b.data为列主序存储， 要重排。但若预先确定A中每一列（即B中每一行）的 第一个非零元在b.data中应有的位置，则可正确转置。 位置向量： 20 §5.2 矩阵的压缩存储  思想 先求出A中每一列的非零元个数，可将第col列 的非零元个数记入pot[col+1]中。  step1：初始化将所有pot中元素清0. //O(n)  step2：扫描a.data，将列号为col的非零元个数累加到 pot[col+1]中。 //O(t) 21 pot[col+1]中。 //O(t)  step3：令pot[col]=pot[col-1]+pot[col] 1≤col≤a.n-1 //O(n)  step4：扫描a.data，将(i,col,v)转置后放于b.data[pot[col]] 中，pot[col]++. //O(t) 时间O(n+t)，快速。 key：pot[1..a.n]=第0~a.n-1列的非零元个数。 §5.2 矩阵的压缩存储 void FastTransMatrix(TripleTable &a , Tripletable &b) {//pot[0..a.n]，比n多1 if (a.t == 0) Error(“…”);//A全零 b.m = a.n; b.n = a.n; b.t = a.t; for ( col = 0; col<=a.n ; col++) pot[col] = 0; //step1初始化 for ( p = 0; p < a.t; p++) // step2扫描a.data pot[a.data[p].j + 1]++; //设a.data[p].j = col pot[a.n]是哨兵 for ( col = 1; col < a.n; col++)//step3. pot[a.n]无用，但第二个循环须统计 pot[col] = pot[col 1] + pot[col]; 22 pot[col] = pot[col – 1] + pot[col]; for ( p = 0; p < a.t; p++) {//step4 col = a.data[p].j; //当前三元组列号. q = pot[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; } } §5.2 矩阵的压缩存储 以上图为例， 23 2. 带行表的三元组表。（顺序方式） 在行优先存储的三元组表中，加入一个行 表来记录稀疏矩阵压缩后每行非零元在三元组表 中的起始位置。 §5.2 矩阵的压缩存储 3. 十字链表 上两种方式是顺序存储，若非零元位置或个数经常发生 变化，会引起结点移动，效率降低。此时宜用链式存储。 例：A←A+B 稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表  结点结构 24  存储结构 分别设两个指针数组作为各行、列单链表的头指针