数据结构（超详细讲解！！）第二十一节 特殊矩阵的压缩存储

1.压缩存储的目标

值相同的元素只存储一次

压缩掉对零元的存储，只存储非零元

特殊形状矩阵：

是指非零元（如值相同的元素）或零元素分布具有一定规律性的矩阵。

如： 对称矩阵 上三角矩阵   下三角矩阵 对角矩阵   准对角矩阵

2.三角矩阵

三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。

对于一个n阶矩阵A来说，若当i<j时，有aij=0，则称此矩阵为下三角矩阵；

若当i>j时，有aij=0，则称此矩阵为上三角矩阵；

若矩阵中的所有元素均满足aij=aji，则称此矩阵为对称矩阵。

 对于下三角矩阵的压缩存储，我们只存储下三角的非零元素，对于零元素则不存。我们按“行序为主序”进行存储，得到的序列是a11, a21, a22, a31, a32, a33, …, an1, an2, …, ann。由于下三角矩阵的元素个数为n(n+1)/2，即：

所以可压缩存储到一个大小为n(n+1)/2的一维数组C中

下三角矩阵中元素aij(i>j)在一维数组A中的位置为：        

Loc［i, j］=Loc［1, 1］+前i-1行非零元素个数+第i行中aij前非零元素个数        

前i-1行元素个数=1+2+3+4+…+（i-1）=i(i-1)/2，所以有 Loc［i, j］=Loc［1, 1］+i(i-1)/2+j-1        

同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(i<j)在数组C中的存储位置为： Loc［i, j］=Loc［1, 1］+j(j-1)/2+i-1      

对于对称矩阵，因其元素满足aij=aji，我们可以为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将n2个元素压缩到n(n+1)/2个空间中。

3.带状矩阵

 三对角带状矩阵有如下特点：            

i=1, j=1, 2                  

1<i<n, j=i-1, i, i+1;            

i=n, j=n-1, n;

时，aij非零，其它元素均为零。

（1）确定存储该矩阵所需的一维向量空间的大小        

在这里我们假设每个非零元素所占空间的大小为1个单元。 从图中观察得知，三对角带状矩阵中，除了第一行和最后一行只有2个非零元素外，其余各行均有3个非零元素。由此得到， 所需一维向量空间的大小为 2+2+3（n-2)=3n-2

（2）确定非零元素在一维数组空间中的位置        

Loc［i ,  j］ = Loc［1, 1］+前i-1行非零元素个数+第i行中aij前非零元素个数；        

前i-1行元素个数=3×（i-1）-1（因为第1行只有2个非零元素）；        

第i行中aij前非零元素个数=j-i+1，其中

由此得到：

Loc［i,  j］=Loc［1, 1］+3(i-1)-1+j-i+1 =Loc［1, 1］+2(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   data［MAXSIZE+1］;     /* 非零元素的三元组表，data［0］未用*/int      m,   n,   len;           /*矩阵的行数、 列数和非零元素的个数*/ 
}TSMatrix； 

 1) 用三元组表实现稀疏矩阵的转置运算        

下面首先以稀疏矩阵的转置运算为例，介绍采用三元组表时的实现方法。        

所谓的矩阵转置，是指变换元素的位置，把位于（row，col）位置上的元素换到（col，row）位置上，也就是说， 把元素的行列互换。

采用矩阵的正常存储方式时， 实现矩阵转置的经典算法如下：

void  TransMatrix（ElementType source［n］［m］,  ElementType dest［m］［n］）
{/*source和dest分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/ int i,  j;  for(i=0; i<m; i++)for (j=0; j< n; j++) dest［i］［ j］=source［j］ ［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->len>0){ 
j=1;  for(k=1;  k<=A.n;  k++)   for(i=1;  i<=A.len;  i++)  if(A.data［i］.col==k)   {   B->data［j］.row=A.data［i］.col    B->data［j］.col=A.data［i］.row;     B->data［j］.e=A.data［i］.e;     j++;    }}
} 

  算法的时间耗费主要是在双重循环中，其时间复杂度为O（A.n×A.len）, 最坏情况下，当A.len=A.m×A.n时，时间复杂度为O（A.m×A.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.m×A.n）。

方法二：

 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：

  (1) 待转置矩阵source每一列中非零元素的个数（即转置后矩阵dest每一行中非零元素的个数）。

(2) 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置（即转置后矩阵dest每一行中第一个非零元素在三元组B中的正确位置)。

 为此， 需要设两个数组num［ ］和position［ ］，其中num［col］用来存放三元组表A中第col列中非零元素个数（三元组表B中第col行非零元素的个数），position［col］用来存放转置前三元组表A中第col列（转置后三元组表B中第col行）中第一个非零元素在三元组表B中的正确位置。

num［col］的计算方法： 将三元组表A扫描一遍，对于其中列号为k的元素，给相应的num［k］加1。

position［col］的计算方法： position［1］=1， position［col］=position［col-1］+num［col-1］，  其中2≤col≤A.n。

  将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法：        

position［col］的初值为三元组表A中第col列（三元组表B的第col行）中第一个非零元素的正确位置，当三元组表A中第col列有一个元素加入到三元组表B时，则position［col］=position［col］+1，即： 使position［col］始终指向三元组表A中第col列中下一个非零元素的正确位置。        

具体算法如下：

FastTransposeTSMatrix (TSMatrix  A,   TSMatrix * B)
{ /*基于矩阵的三元组表示， 采用快速转置法， 将矩阵A转置为B所指的矩阵*/
int col,  t,  p， q; 
int num［MAXSIZE］,  position［MAXSIZE］; 
B->len=A.len;  B->n=A.m;  B->m=A.n; 
if(B->len){
for(col=1; col<=A.n; col++) num［col］=0;   for(t=1; t<=A.len; t++) num［A.data［t］.col］++;   /*计算每一列的非零元素的个数*/position［1］=1; for(col=2; col<A.n; col++)   /*求col列中第一个非零元素在B.data［ ］中的正
确位置 */position［col］=position［col-1］+num［col-1］;  for(p=1; p<A.len.p++) {  col=A.data［p］.col;   q=position［col］;  B->data［q］.row=A.data［p］.col;   B->data［q］.col=A.data［p］.row;   B->data［q］.e=A.data［p］.eposition［col］++;  } 
}
} 

 快速转置算法的时间主要耗费在四个并列的单循环上，这四个并列的单循环分别执行了A.n，A.len，A.n-1，A.len次，因而总的时间复杂度为O(A.n)+O(A.len)+O(A.n)+O(A.len)，即为O（A.n+A.len）。 当待转置矩阵M中非零元素个数接近于A.m×A.n 时，其时间复杂度接近于经典算法的时间复杂度O(A.m×A.n)。          

快速转置算法在空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num［1..A.n］，position［1..A.n］。可见，算法在时间上的节省，是以更多的存储空间为代价的。

（2）稀疏矩阵的链式存储结构: 十字链表

与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵节约了空间，但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B， 将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。

在十字链表中，矩阵的每一个非零元素用一个结点表示， 该结点除了（row，col，value）以外，还要有以下两个链域：       

 right：  用于链接同一行中的下一个非零元素；        

down： 用于链接同一列中的下一个非零元素。

用两个一维的指针数组分别存放各行链表的头指针和各列链表的头指针，从而得到了矩阵的十字链表存储结构。

结构类型：

建十字链表的算法的时间复杂度为O（t×s），s=max（m，n）。

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->m=m; M->n=n; M->len=t; If(!(M->row-head=(OLink * )malloc((m+1)sizeof(OLink)))) exit(OVERFLOW); If(!(M->col-head=(OLink * )malloc((n+1)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->row=i; p->col=j; p->value=e;    /* 生成结点 */ if(M->row-head［i］==NULL)   M->row-head［i］=p; 
else{  /* 寻找行表中的插入位置 */for(q=M->row-head［i］;   q->right&&q->right->col<j;   q=q->right)p->right=q->right;  q->right=p;    /* 完成插入 */ } if(M->col-head［j］==NULL)   M->col-head［j］=p;  else{  /*寻找列表中的插入位置*/for(q=M->col-head［j］;   q->down&&q->down->row<i;   q=q->down) p->down=q->down;  q->down=p;     /* 完成插入 */         }}}