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

（1）稀疏矩陣的特點

在一個m×n的矩陣中，設矩陣中有i個元素不為零，并令△=i/(m×n)，稱△為稀疏因子。通常當△≤0.05時。認為該矩陣為稀疏矩陣。

對這類矩陣實現(xiàn)壓縮存儲的基本思路是只需要存儲其非零元素，但由于稀疏矩陣中零元素的分布沒有一定規(guī)律，所以必須同時記下零元素所在的行和列。才能對矩陣有效的縮壓，并能正確的恢復它。

（2）稀疏矩陣的壓縮存儲原理

只存儲非零元素a_i，j和相應的行、列序號i、j。具體方法：對稀疏矩陣中每一個非零元素設定一個三元組（i,j,a_i,j），將所有三元組按行優(yōu)先排列，組成一個三元組表（線性表）。只要存儲三元組表和該矩陣的行、列數(shù)，就能唯一確定該矩陣。

例5.8 按稀疏矩陣的壓縮存儲方法，求矩陣A的存儲信息。

分析：設左上角的元素所在位置為第1行第1列，矩陣的行、列及非零元素個數(shù)為：（5，6，6）相應的三元組表為：（1,2,12）（1,3,9)（3,1,3）（3,6,14）（4,3,24）（5,2,16）。

（3）存儲方法

通過上述轉(zhuǎn)換，對稀疏矩陣的壓縮存儲，化為對其三元組表和相關信息的存儲。

用結構體類型描述三元組

結構體triple的成員i，j分別是非零元素的行、列下標，成員e是非零元素。 triple d 說明了triple類型的結構體變量d，并分配了存儲單元，如圖5-9(a)所示。triple data [10]說明了triple類型的有10個數(shù)組元素的結構體數(shù)組，如圖5-9(b)所示。

用結構體類型描述三元組表和相關信息

	typedef struct	{ int mu, nu, tu ;	triple data [ max+1] ; /*max+1是最多的元素個數(shù)*/	}triplegrupe; /*三元組表類型*/	triplegrupe a;

說明了三元組表類型的變量a，有4個成員項，mu﹑nu分別表示稀疏矩陣的行﹑列數(shù)，tu表示稀疏矩陣中的非零元素的個數(shù)；data表示非零元素的三元組表。

例5.9

（4）算法舉例

例5.10 如圖5-12所示，求壓縮存儲的稀疏矩陣A的轉(zhuǎn)置矩陣A^T。

分析：

由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））

存在問題：按上述方法得到的轉(zhuǎn)置后矩陣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）

程序

其中：

a是稀疏矩陣的三元組表，b是轉(zhuǎn)置矩陣的三元組表；

p是稀疏矩陣的三元組數(shù)組下標.q是轉(zhuǎn)置矩陣的三元組數(shù)組下標；

a.mu是稀疏矩陣的行數(shù)，a.nu是稀疏矩陣的列數(shù)；

a.tu是稀疏矩陣三元組數(shù)元素的個數(shù)；

col是循環(huán)變量。

在稀疏矩陣三元組中從第1列掃描到a.nu列，若找到相應列的三元組，則把行﹑列互換存入轉(zhuǎn)置矩陣的三元組。

存儲變化示意圖

轉(zhuǎn)置前：如圖5-13（a）、圖5-13（b）、圖5-13（c）所示。

轉(zhuǎn)置后：如圖5-13（d）、圖5-13（e）、圖5-13（f）所示。