C语言：数据结构-稀疏矩阵的压缩存储

https://m./group/6712258385510662667/?app=news_article&timestamp=1562855219&req_id=201907112226580100230300187166DEA&group_id=6712258385510662667

（1）稀疏矩阵的特点

在一个m×n的矩阵中，设矩阵中有i个元素不为零，并令△=i/(m×n)，称△为稀疏因子。通常当△≤0.05时。认为该矩阵为稀疏矩阵。

对这类矩阵实现压缩存储的基本思路是只需要存储其非零元素，但由于稀疏矩阵中零元素的分布没有一定规律，所以必须同时记下零元素所在的行和列。才能对矩阵有效的缩压，并能正确的恢复它。

（2）稀疏矩阵的压缩存储原理

只存储非零元素a_i，j和相应的行、列序号i、j。具体方法：对稀疏矩阵中每一个非零元素设定一个三元组（i,j,a_i,j），将所有三元组按行优先排列，组成一个三元组表（线性表）。只要存储三元组表和该矩阵的行、列数，就能唯一确定该矩阵。

例5.8 按稀疏矩阵的压缩存储方法，求矩阵A的存储信息。

稀疏矩阵A

分析：设左上角的元素所在位置为第1行第1列，矩阵的行、列及非零元素个数为：（5，6，6）相应的三元组表为：（1,2,12）（1,3,9)（3,1,3）（3,6,14）（4,3,24）（5,2,16）。

（3）存储方法

通过上述转换，对稀疏矩阵的压缩存储，化为对其三元组表和相关信息的存储。

用结构体类型描述三元组

typedef struct { int i , j ; detetype e; }triple d; /* 三元组类型 */

结构体triple的成员i，j分别是非零元素的行、列下标，成员e是非零元素。 triple d 说明了triple类型的结构体变量d，并分配了存储单元，如图5-9(a)所示。triple data [10]说明了triple类型的有10个数组元素的结构体数组，如图5-9(b)所示。

三元组类型的变量和数组的结构图

用结构体类型描述三元组表和相关信息

	typedef struct	{ int mu, nu, tu ;	triple data [ max+1] ; /*max+1是最多的元素个数*/	}triplegrupe; /*三元组表类型*/	triplegrupe a;

说明了三元组表类型的变量a，有4个成员项，mu﹑nu分别表示稀疏矩阵的行﹑列数，tu表示稀疏矩阵中的非零元素的个数；data表示非零元素的三元组表。

例5.9

矩阵

稀疏矩阵a的存储结构

（4）算法举例

例5.10 如图5-12所示，求压缩存储的稀疏矩阵A的转置矩阵A^T。

A与其转置矩阵AT

分析：

由A得到三元组表：

（（1，1，1），（1，3，5），（1，5，2），（2，1，7），(3，1，3），（3，3，6））

把上述三元组表中的各三元组的行﹑列互换得到的A^T的三元组表为：

（（1，1，1），（3，1，5），（5，1，2），（1，2，7），(1，3，3），（3，3，6））

存在问题：按上述方法得到的转置后矩阵A^T的新三元组表没有能按行序为主序存储。

为了使新三元组表要按行序为主序存储，就要按原表的列为主序排列。而原三元组表是按行序为主存储的，所以同一列中的各行已按行序由小到大顺序排列。

方法如下：

按第1，2，3，…n列的顺序，逐次扫描A相应的三元组表，依次把得到的第1，2，…，n列的三元组中的行、列互换，存入新三元组表。每次扫描中，因为相同列的三元组按扫描的先后顺序存入。这保证了新三元组表以行序为主针对A的三元组表：

以第1列扫描，找到：（1，1，1），（2，1，7），（3，1，3）。

交换行和列的坐标存入新表。

以第2列扫描，未找到。

以第3列扫描，找到：（1，3，5），（3，3，6）。

交换行和列的坐标存入新表。

以第4列扫描，未找到。

以第5列扫描，找到：（1，5，2）。

交换行和列的坐标存入新表。

新表为：

（1，1，1），（1，2，7），（1，3，3），（3，1，5），（3，3，6），（5，1，2）

程序

void transpose (triplegrupe a, tripletgrupe b) { int p,q,col; b.mu=a.nu; b.nu =a.mu; b.tu =a.tu; if(b.tu) { q=1; for(col=1 ; col≤a.nu; col++) for(p=1 ; p≤a.tu; p++) if(a.data[p].j==col) { b.data[q].i=a.data[p].j; b.data[q].j= a.data[p].i; b.data[q].v=a.data[p].e； q++; } } }

其中：

a是稀疏矩阵的三元组表，b是转置矩阵的三元组表；

p是稀疏矩阵的三元组数组下标.q是转置矩阵的三元组数组下标；

a.mu是稀疏矩阵的行数，a.nu是稀疏矩阵的列数；

a.tu是稀疏矩阵三元组数元素的个数；

col是循环变量。

在稀疏矩阵三元组中从第1列扫描到a.nu列，若找到相应列的三元组，则把行﹑列互换存入转置矩阵的三元组。

存储变化示意图

转置前：如图5-13（a）、图5-13（b）、图5-13（c）所示。

转置后：如图5-13（d）、图5-13（e）、图5-13（f）所示。

程序运行前后存储变化示意图（a）矩阵A；（b）矩阵A的行﹑列信息；（C）矩阵A的三元组数组