（1）稀疏矩阵的特点

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

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

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

只存储非零元素ai，j和相应的行、列序号i、j。具体方法：对稀疏矩阵中每一个非零元素设定一个三元组（i,j,ai,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的转置矩阵AT。

A与其转置矩阵AT

分析：

由A得到三元组表：

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

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

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

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

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

方法如下：

按第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的三元组数组