|
https://m./group/6712258385510662667/?app=news_article×tamp=1562855219&req_id=201907112226580100230300187166DEA&group_id=6712258385510662667 （1）稀疏矩陣的特點(diǎn) 在一個(gè)m×n的矩陣中，設(shè)矩陣中有i個(gè)元素不為零，并令△=i/(m×n)，稱(chēng)△為稀疏因子。通常當(dāng)△≤0.05時(shí)。認(rèn)為該矩陣為稀疏矩陣。 對(duì)這類(lèi)矩陣實(shí)現(xiàn)壓縮存儲(chǔ)的基本思路是只需要存儲(chǔ)其非零元素，但由于稀疏矩陣中零元素的分布沒(méi)有一定規(guī)律，所以必須同時(shí)記下零元素所在的行和列。才能對(duì)矩陣有效的縮壓，并能正確的恢復(fù)它。 （2）稀疏矩陣的壓縮存儲(chǔ)原理 只存儲(chǔ)非零元素ai，j和相應(yīng)的行、列序號(hào)i、j。具體方法：對(duì)稀疏矩陣中每一個(gè)非零元素設(shè)定一個(gè)三元組（i,j,ai,j），將所有三元組按行優(yōu)先排列，組成一個(gè)三元組表（線(xiàn)性表）。只要存儲(chǔ)三元組表和該矩陣的行、列數(shù)，就能唯一確定該矩陣。 例5.8 按稀疏矩陣的壓縮存儲(chǔ)方法，求矩陣A的存儲(chǔ)信息。 稀疏矩陣A 分析：設(shè)左上角的元素所在位置為第1行第1列，矩陣的行、列及非零元素個(gè)數(shù)為：（5，6，6）相應(yīng)的三元組表為：（1,2,12）（1,3,9)（3,1,3）（3,6,14）（4,3,24）（5,2,16）。 （3）存儲(chǔ)方法 通過(guò)上述轉(zhuǎn)換，對(duì)稀疏矩陣的壓縮存儲(chǔ)，化為對(duì)其三元組表和相關(guān)信息的存儲(chǔ)。 用結(jié)構(gòu)體類(lèi)型描述三元組 typedef struct { int i , j ; detetype e; }triple d; /* 三元組類(lèi)型 */ 結(jié)構(gòu)體triple的成員i，j分別是非零元素的行、列下標(biāo)，成員e是非零元素。 triple d 說(shuō)明了triple類(lèi)型的結(jié)構(gòu)體變量d，并分配了存儲(chǔ)單元，如圖5-9(a)所示。triple data [10]說(shuō)明了triple類(lèi)型的有10個(gè)數(shù)組元素的結(jié)構(gòu)體數(shù)組，如圖5-9(b)所示。 三元組類(lèi)型的變量和數(shù)組的結(jié)構(gòu)圖 用結(jié)構(gòu)體類(lèi)型描述三元組表和相關(guān)信息 typedef struct { int mu, nu, tu ; triple data [ max+1] ; /*max+1是最多的元素個(gè)數(shù)*/ }triplegrupe; /*三元組表類(lèi)型*/ triplegrupe a;說(shuō)明了三元組表類(lèi)型的變量a，有4個(gè)成員項(xiàng)，mu﹑nu分別表示稀疏矩陣的行﹑列數(shù)，tu表示稀疏矩陣中的非零元素的個(gè)數(shù)；data表示非零元素的三元組表。 例5.9 矩陣 稀疏矩陣a的存儲(chǔ)結(jié)構(gòu) （4）算法舉例 例5.10 如圖5-12所示，求壓縮存儲(chǔ)的稀疏矩陣A的轉(zhuǎn)置矩陣AT。 A與其轉(zhuǎn)置矩陣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）） 存在問(wèn)題：按上述方法得到的轉(zhuǎn)置后矩陣AT的新三元組表沒(méi)有能按行序?yàn)橹餍虼鎯?chǔ)。 為了使新三元組表要按行序?yàn)橹餍虼鎯?chǔ)，就要按原表的列為主序排列。而原三元組表是按行序?yàn)橹鞔鎯?chǔ)的，所以同一列中的各行已按行序由小到大順序排列。 方法如下： 按第1，2，3，…n列的順序，逐次掃描A相應(yīng)的三元組表，依次把得到的第1，2，…，n列的三元組中的行、列互換，存入新三元組表。每次掃描中，因?yàn)橄嗤械娜M按掃描的先后順序存入。這保證了新三元組表以行序?yàn)橹麽槍?duì)A的三元組表： 以第1列掃描，找到：（1，1，1），（2，1，7），（3，1，3）。 交換行和列的坐標(biāo)存入新表。 以第2列掃描，未找到。 以第3列掃描，找到：（1，3，5），（3，3，6）。 交換行和列的坐標(biāo)存入新表。 以第4列掃描，未找到。 以第5列掃描，找到：（1，5，2）。 交換行和列的坐標(biāo)存入新表。 新表為： （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是轉(zhuǎn)置矩陣的三元組表； p是稀疏矩陣的三元組數(shù)組下標(biāo).q是轉(zhuǎn)置矩陣的三元組數(shù)組下標(biāo)； a.mu是稀疏矩陣的行數(shù)，a.nu是稀疏矩陣的列數(shù)； a.tu是稀疏矩陣三元組數(shù)元素的個(gè)數(shù)； col是循環(huán)變量。 在稀疏矩陣三元組中從第1列掃描到a.nu列，若找到相應(yīng)列的三元組，則把行﹑列互換存入轉(zhuǎn)置矩陣的三元組。 存儲(chǔ)變化示意圖 轉(zhuǎn)置前：如圖5-13（a）、圖5-13（b）、圖5-13（c）所示。 轉(zhuǎn)置后：如圖5-13（d）、圖5-13（e）、圖5-13（f）所示。 程序運(yùn)行前后存儲(chǔ)變化示意圖（a）矩陣A；（b）矩陣A的行﹑列信息；（C）矩陣A的三元組數(shù)組 |
|
|
