【文章內容簡介】 an1,n1 an1,n 0 0 … … an,n1 ann 0 a32 a33 a34 0 ……… 0 …………………………… Loc(aij)=Loc(a11)+[2(i1)+(j1)]*L 按行序為主序： a11 a12 a21 a22 a23 ann1 ann …... …... k=0 1 2 3 4 3*n3 sa[k]和 a[i,j]的一一對應關系 : sa[k], k = 3*(i1) + ji, a[i, j] = 當 |i j|=1 0 當 |i j|1 a11 a12 0 0 ... 0 a21 a22 a23 0 ... 0 Anxn = 0 a32 a33 a34 ... 0 ...... 0 0 0 ... ann1 ann 例 對角矩陣 4 3 0 0 0 5 2 2 0 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 0 9 5 一維數組 SA[0..3*53]作為數組 A的存儲結構 : SA=(4 3 5 2 2 1 0 4 2 8 7 9 5) 如 : a[5,4] = 9 k = 3*(51) + 45= 11 故 :sa[11] = 9 稀疏矩陣 假設 m 行 n 列 的矩陣含 t 個非零元素 ，則稱 為 稀疏因子 。 通常認為 ? ? 的矩陣為稀疏矩陣。 nm t???稀疏矩陣的壓縮存儲方法 : 一、三元組順序表 二、行邏輯鏈接的順序表 三、 十字鏈表 define MAXSIZE 12500 typedef struct { int i, j。 //該非零元的行下標和列下標 ElemType e。 // 該非零元的值 } Triple。 // 三元組類型 一、三元組順序表 typedef struct { Triple data[MAXSIZE + 1]。 int mu, nu, tu。 } TSMatrix。 // 稀疏矩陣類型 6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 i j e 0 1 2 3 4 5 6 7 8 7600070015000001800000240001400003000000000009120????????????????????????M7600070015000001800000240001400003000000000009120????????????????????????M6700000000014000000007000000024009018000121500300????????????????????????????NT 如何求轉置矩陣？ 用常規(guī)的二維數組表示時的算法 其時間復雜度為 : O(mu nu) for (col=1。 col=nu。 ++col) for (row=1。 row=mu。 ++row) T[col][row] = M[row][col]。 6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 i j e 0 1 2 3 4 5 6 7 8 i j e 7 6 8 1 3 3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 0 1 2 3 4 5 6 7 8 ? 解決思路： 只要做到 ?將矩陣行、列值互換； ?將每個三元組中的 i和 j相互調換； ?重排三元組次序，使 元素以 N的行 (M的列 )為主序 方法一：按 M的列序轉置 按 ，即按照矩陣 M的列序 來進行置換。 為找到 M中每一列所有非零元素，需對其三元組表 描一遍。由于 M行序為主序，所以由此得到的恰是 有的順序 。 6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 i j e 0 1 2 3 4 5 6 7 8 7 6 8 1 3 3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 i j e 0 1 2 3 4 5 6 7 8 q p p p p p p p p q q q q p p p p p p p p col=1 col=2 Status TransposeSMatix(TSMatrix M,TSMatrix T){ //采用三元組表存儲表示，求稀疏矩陣 M的轉置矩陣 T。 =。 =。 =。 If () { q=1。 for (col=1。 col=。 ++col) for (p=1。 p=。 ++p) If ([p].j == col){