數(shù)據(jù)結(jié)構(gòu)-稀疏矩陣的三元組表存儲方法

1、 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 三元組表三元組表一、什么是稀疏矩陣一、什么是稀疏矩陣(sparse matrix) 如果矩陣如果矩陣M中的大多數(shù)元素均中的大多數(shù)元素均為零元素，則稱矩陣為零元素，則稱矩陣M為稀疏矩為稀疏矩陣陣 。一般地，當(dāng)非零元素個數(shù)。一般地，當(dāng)非零元素個數(shù)只占矩陣元素總數(shù)的只占矩陣元素總數(shù)的25%30%,或低于這個百分?jǐn)?shù)時，我們稱這樣或低于這個百分?jǐn)?shù)時，我們稱這樣的矩陣為稀疏矩陣。的矩陣為稀疏矩陣。 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0

2、0 0M=例如：例如：一、什么是稀疏矩陣一、什么是稀疏矩陣(sparse matrix) 如果矩陣如果矩陣M中的大多數(shù)元素均中的大多數(shù)元素均為零元素，則稱矩陣為零元素，則稱矩陣M為稀疏矩陣。為稀疏矩陣。 用一個三元組（用一個三元組（tupel3）存放矩陣中的存放矩陣中的一個非零元素的行號、列號及該非零元素一個非零元素的行號、列號及該非零元素的值。的值。 一個三元組的形式為：（一個三元組的形式為：（i , j, e） 一般情況下，一個稀疏矩陣中有若干個一般情況下，一個稀疏矩陣中有若干個非零元素，所以要用一個非零元素，所以要用一個“三元組線性表三元組線性表”來存放一個稀疏矩陣。來存放一個稀疏矩陣。

3、1.中心思想：僅存儲矩陣中的非零元素中心思想：僅存儲矩陣中的非零元素2.用順序存儲結(jié)構(gòu)存放三元組線性表用順序存儲結(jié)構(gòu)存放三元組線性表M=原矩陣原矩陣:存放形式存放形式: （按行順序存放）（按行順序存放）data p i j edata 1 1 2 12data 2 1 3 9data 3 3 1 -3data 4 3 6 14data 5 4 3 24data 6 5 2 18data 7 6 1 15data 8 6 4 -7 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7

4、0 0 0mu=6 nu=7 tu=8注意：注意：為了保存矩陣的行數(shù)、列為了保存矩陣的行數(shù)、列數(shù)和非零元素個數(shù)，還需數(shù)和非零元素個數(shù)，還需增設(shè)三個量：增設(shè)三個量：mu nu tu3.三元組線性表的數(shù)據(jù)類型描述三元組線性表的數(shù)據(jù)類型描述#define MAXSIZE 12500 /非零元素個數(shù)的最大值typedef struct int i, j; ElemType e; Triple;typedef struct Triple data MAXSIZE+1; /三元組表，data0不用 int mu , nu , tu ; /矩陣的行數(shù)、列數(shù)、非0元素個數(shù)TSMatrix /sparsenes

5、s(稀疏)TSMatrix M ； 用變量用變量 a 存放矩陣存放矩陣 M 的形式如下：的形式如下： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8注意：注意： 引用引用i ,j ,e i ,j ,e 時的格式應(yīng)為：時的格式應(yīng)為： a .data p .ia .data p .i a .data

6、 p .j a .data p .j a .data p .e a .data p .e例如例如 x= x=a adata6.jdata6.j 則則 x=2x=2三、實現(xiàn)矩陣的運算三、實現(xiàn)矩陣的運算:矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置1.實例實例:求矩陣求矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣N:三、實現(xiàn)矩陣的運算三、實現(xiàn)矩陣的運算:矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置1.實例實例:求矩陣求矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣N: 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 M= 0 0 -3 0 0 15 12 0

7、0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 N=求解求解注意注意:用變量用變量a和和 b分別存放矩陣分別存放矩陣M和和N (TSMatrix a, TSMatrix b),即要從已知變量即要從已知變量a來求得變量來求得變量b的的值。值。也既要完成如下求解工作：也既要完成如下求解工作： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .dat

8、a 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 b. mu=7 b. nu=6 b. tu=8求解求解2.求解步驟分析：求解步驟分析：p=1:8, q的值的值=1,2 a . data p i j e a

9、.data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 b .data 2 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8 求得求得1Col=1注注:p=1:8,尋找尋找 j=col 的的a.data p1 1 3 -3 1

10、 6 152.求解步驟分析：求解步驟分析：p=1:8, q的值的值=3,4 a . data p i j e a .data 1 1 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 b .data 4 b .data 5 b .data 6

11、 b .data 7 b .data 8 求得求得22注注:p=1:8,尋找尋找 j=col 的的a.data pCol=2 2 1 12 2 5 182.求解步驟分析：求解步驟分析：p=1:8, q的值的值=5,6 a . data p i j e a .data 1 1 2 12 a .data 2 1 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b

12、.data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 b .data 6 b .data 7 b .data 8 求得求得33Col=3注注:p=1:8,尋找尋找 j=col 的的a.data p 3 1 9 3 4 242.求解步驟分析：求解步驟分析：p=1:8, q的值的值=7 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data

13、6 5 2 18 a .data 7 6 1 15 a .data 8 6 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 b .data 8 求得求得Col=4注注:p=1:8,尋找尋找 j=col 的的a.data p4 4 6 -7 2.求解步驟分析：求解步驟分析：p=1:8, q的值的值=7 a . data p i j e a

14、 .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data

15、 8 求得求得Col=5注注:p=1:8,尋找尋找 j=col 的的a.data p無無!2.求解步驟分析：求解步驟分析：p=1:8, q的值的值=8 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15

16、 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 求得求得Col=6注注:p=1:8,尋找尋找 j=col 的的a.data p6 6 3 14 2.求解步驟分析：求解步驟分析：p=1:8, q的值的值=8 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data

17、7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 求得求得Col=7注注:p=1:8,尋找尋找 j=col 的的a.data p無無!2.求解步驟分析：求解步驟分析： a . data p i j e a .data 1 1 2 12 a .da

18、ta 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 求得求得b. Mu=7 b.nu=6 b.tu=83.算法描述算法描述status TransposeSMatrix(TSMatrix a, TSMatrix *b) (*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.datap .j = =col) b.dataq.i=a.datap .j; b.dataq.j=a.datap .i;