第二节矩阵的压缩存储

真题选解

2．三角矩阵

下三角矩阵的主对角线上方均为常数c或零；上三角矩阵是指矩阵的下三角(不包括对角线)中的元素均为常数c或是零的n阶方阵。一般情况下，三角矩阵的常数c均为零。

三角矩阵可压缩存储到数组M[n（n+1）/2+1]中。

上三角矩阵中，主对角线上的第i行有n-i+1个元素，以行序为主序存放，M[k]和a_ij的对应关系是：

下三角矩阵中，以行序为主序存放，与对称矩阵类是，M[k]和a_ij的对应关系是：

真题选解

二、稀疏矩阵

含有大量的零元素且零元素分布没有规律矩阵称为稀疏矩阵。

2、三元组表

（1）三元组表的含义：一个稀疏矩阵可用一个三元组线性表表示，每个三元组元素对应稀疏矩阵中的一个非零元素，包含有该元素的行号、列号和元素值。每个三元组元素在线性表中是按照行号值的升序为主序、列号值的升序为辅序（即行号值相同再按列号值顺序）排列的。

【例】画出下列稀疏矩阵对应的三元组表

【解析】根据前面三元组的含义很容易画出该矩阵的三元组表。

【答案】

（2）三元组表的类型定义

#define Maxsize 1000 //假设非零元素个数的最大为1000个

typedef 　struct

｛ int i，j； //非零元素的行号、列号(下标)

　 DataType v； //非零元素值

　}TriTupleNode；

typedef 　struct

　{ TriTupleNode data[Maxsize]；//存储三元组的数组

　　int m，n，t; //矩阵的行数、列数和非零元素个数

　}TSMatrix； //稀疏矩阵类型

【例】试写一个算法，建立顺序存储稀疏矩阵的三元组表。

【分析】假设A为一个稀疏矩阵，其数据存储在二维数组a中，b为一个存放对应于A矩阵生成的三元组表。在这个算法中，要进行二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入b中。

【算法描述】

void CreateTriTable(TSMatrix *b，int a[][5]，int m，int n)

{ //建立稀疏矩阵的三元组表

int i，j，k=0；

for(i=0；i<m；i++)

　for(j=0；j<n；j++)

　　if(a[i][j]!=0) 　　　　　　　　　　//找出非零元素

　　　 { b->data[k]．i=i； 　　　　　//记录非零元素行下标

　　　　b->data[k]．j=j; 　　　　　　//记录非零元素列下标

　　　　b->data[k]．v=a[i][j]；　　　//保存非零值

　　　　k++;　　　　　　　　　　 //统计非零元素个数

　　　}

b->m=m；b->n=n；　　　　　　　　 //记录矩阵行列数

b->t=k：　　　　　　　　　　　　 //保存非零个数

}

【例】试写一个算法，实现以三元组表结构存储的稀疏矩阵的转置运算。

【分析】对于一个m×n的矩阵M，它的转置矩阵T是一个n×m的矩阵，而且M_ij=T_ji (0≤i<m，0≤j<n)，即M的行是T的列，M的列是T的行。

稀疏矩阵M和它的转置矩阵T

（1）一般的转置算法

【算法思想】对M中的每一列col(0≤col≤a.n-1)从头至尾依次扫描三元组表，找出所有列号等col的那些三元组，并将它们的行号和列号互换后再依次存入b->data中，这样就可得到T的按行优先的三元组表。

【算法描述】

void TransMatrix(TSMatrix a，TSMatrix*b)

{ //a和*b是矩阵M、T的三元组表表示，求稀疏矩阵M的转置T

　int p，q，col；

　b->m=a.n；b->n=a.m; 　　　　　　　　//M和T行列数互换

　b->t=a.t； 　　　　　　　　　　　　　//赋值非零元素个数

　if(b->t<=0)

　　printf("M中无非零元素!")；

　e1se

　　{ q=0;

　　　for(col=0;col<a.n;++col)

　　　　for(p=0；p<a.t；++p) 　　　　　//扫描M的三元组表

　　　　　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;

　　　　　　}

　　　}

}

【算法分析】该算法的时间复杂度为O(n×t)，即与稀疏矩阵M的列数和非零元素个数的乘积成正比。一般的矩阵转置算法的时间复杂度为O(m×n)。该算法仅适用于非零元素个数t远远小于矩阵元素个数m×n的情况。

（2）快速转置算法

【算法思想】创建两个数组num和rownext。num[j]存放矩阵第j列上非零元素个数，rownext[i]代表转置矩阵第i行的下一个非零元素在b中的位置。

【算法描述】

void FaStTran(TSMatfix a，TSMatrix*b)

{ 　int col，p，t，q;

　　int *num，*rownext;

　　num=(int*)calloc(a.n+1，4); 　　　　　　// 分配n+1个长度为4的连续空间

　　rownext=(int*)calloc(a.m+1，4)； 　　　　// 分配m+1个长度为4的连续空间

　　b->m=a.n；b->n=a.m;b->t=a.t;

　　if(b->t)

　　　{ for(col=0；col<a.n；++col)

　　　　　num[col]=0; 　　　　　　　　　//初始化

　　　　for(t=0；t<a.t；++t)

　　　　　++num[a.data[t].j]; 　　　　　　　//计算每列非零元素数

　　　　rownext[0]=0；

　　　　for(col=1; col<a.n;++col)　　　　　　 //给出b中每一行的起始点

　　　　　rownext[col]=rownext[col-1]+num[col-1]；

　　　　for(p=0；p<a.t;++p) 　　　　　　　//执行转置操作

　　　　　{ col=a.data[p].j；

　　　　　　q=rownext[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；

　　　　　　++rownext[col]；　　　　　　　　 //下一次再有该行元素，起始点就比上一个加了1

　　　　　}

　　　}

}

【算法分析】算法的时间复杂度为O(t)

3、带行表的三元组表

带行表的三元组表：又称为行逻辑链接的顺序表。在按行优先存储的三元组表中，增加一个存储每一行的第一个非零元素在三元组表中位置的数组。

【类型描述】

typedef struct

{ TriTupleNode data[MaxSize]；

　int RowTab[MaxRow]; 　　　　　　　　//每行第一个非零元素的位置表

　int m，n，t；

}RLSMatrix；

带行表的三元组表的特点：

① 对于任给行号i(0≤i≤m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i]

② RowTab[i](0≤i≤m-1)表示第i行之前的所有行的非零元数。

③ 第i行上的非零元数目为RowTab[i+1]-RowTab[i](0≤i≤m-2)

④ 最后一行(即第m-l行)的非零元数目为t-RowTab[m-1](t为矩阵的非零元总数)

注意：

若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便些，且t可省略。

带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考书】。

真题选解