1、矩陣的轉置2 本節主要內容本節主要內容 1. 1. 矩陣的轉置算法矩陣的轉置算法2. 2. 改進的快速轉置算法改進的快速轉置算法3稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲對于元素分布都有一定的規律，我們都將其壓縮存儲到一維數組中，并找到每個矩陣元素在數組中的對應關系。稀疏矩陣：若非零元很少，而且分布沒有一定的規律，如何來存儲呢？非零元較零元少，且分布沒有一定規律。稀疏因子: 假設假設 m 行行 n 列列的矩陣含的矩陣含 t 個非零元素個非零元素，則稱，則稱nmt通常認為 0.05 的矩陣為稀疏矩陣。非零元素個數總元素個數稀疏因子4稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲1、三元組順序表2、行邏輯鏈接的

2、順序表3、十字鏈表5稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲1、三元組順序表00070015000001800000240001400003000000000009120M可由三元組表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩陣維數（6,7）唯一確定 6稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲1、三元組順序表 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行標和列標 ElemType e; / 該非零元的值 Triple; / 三元組類型ty

3、pedef struct Triple dataMAXSIZE + 1; / data0未用 int mu, nu, tu; / 矩陣的行數、列數及非零元個數 TSMatrix; / 稀疏矩陣類型7稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲例如：00070015000001800000240001400003000000000009120Mstruct TSMatrix M;ije121213931-3361443245218611564-7M.mu=6;M.nu=7;M.tu=8;M.data4M.data5M.data6M.data7M.data8M.data0M.data1M.data2M.d

4、ata38稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲2、行邏輯鏈接的順序表為了便于對矩陣中任意一行非零元素進行操作，對三元組順序表結構進行修改，增加一個量來記錄每一行非零元在三元組表中的位置，這種“帶行鏈接信息”的三元組表稱為行邏輯鏈接的順序表。typedef struct Triple dataMAXSIZE + 1; int rposMAXRC + 1; / 各行第一個非零元的位置表 int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類型9稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲00070015000001800000240001400003000000000009120M例

5、如：ije121213931-3361443245218611564-7M.data4M.data5M.data6M.data7M.data8M.data0M.data1M.data2M.data3struct RLSMatrix M; 行行0123456rpos133567M.mu=6;M.nu=7;M.tu=8;10 矩陣的轉置矩陣的轉置00070015000001800000240001400003000000000009120M00000000014000000007000000024009018000121500300T如何實現？如果矩陣未采用壓縮存儲方式，采用二維數組作為存儲結構：

6、那么，轉置算法為：行，列元素相交換。 for (col=1; col=列數; +col) for (row=1; row=行數; +row) Tcolrow = Mrowcol;時間復雜度為：(行數*列數)11 矩陣的轉置矩陣的轉置 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行標和列標 ElemType e; / 該非零元的值 Triple; / 三元組類型typedef struct Triple dataMAXSIZE + 1; / data0未用 int mu, nu, tu; / 矩陣的行數、列數及非零元個數 TSMatr

7、ix; / 稀疏矩陣類型若矩陣采用壓縮存儲-三元組順序表作為存儲結構，如何實現矩陣的轉置？12 矩陣的轉置矩陣的轉置00070015000001800000240001400003000000000009120Mije121213931-3361443245218611564-7M.data4M.data5M.data6M.data7M.data8M.data0M.data1M.data2M.data3M.mu=6;M.nu=7;M.tu=8;struct TSMatrix M;13 矩陣的轉置矩陣的轉置ije121213931-3361443245218611564-7T.data8T.da

8、ta7T.data5T.data6T.data4T.data0T.data1T.data2T.data3M.data8M.data7M.data5M.data6M.data4M.data0M.data1M.data2M.data3ije211231913-3631434242518161546-7i和j相交換實現轉置，這樣實現是否正確？14 矩陣的轉置矩陣的轉置為了便于實現矩陣的各類算法，通常采用三元組順序表對矩陣進行存儲時，都將元素按照i值（行值）排列為非遞減序列。因此，矩陣的轉置（假設矩陣M轉置為矩陣T）：1、將矩陣M的行值賦給矩陣T的列值，M的列值賦給T的行值；2、將M的每個元素三元組中

9、的i值給T的每個元素三元組中的j值；M的每個元素三元組中的j值給T的每個元素三元組中的i值。3、應讓T的三元組元素按照i值（行值）重新排序。通常有兩種方法：1、壓縮轉置算法：核心思想：按照T.data中三元組的次序依次在M.data中找到相應的三元組進行轉置。2、壓縮快速轉置算法：核心思想：按照M.data中三元組的次序進行轉置，并將轉置后的三元組置入T中恰當的位置上。15 壓縮轉置算法壓縮轉置算法1、壓縮轉置算法：核心思想：按照T.data中三元組的次序依次在M.data中找到相應的三元組進行轉置。ije121213931-3361443245218611564-7M.data8M.data

10、7M.data5M.data6M.data4M.data0M.data1M.data2M.data3M.mu=6;M.nu=7;M.tu=8T.mu=7; T.nu=6;T.tu=8;ijeT.data8T.data7T.data5T.data6T.data4T.data0T.data1T.data2T.data3q=1按照從1到M.nu，反復查看M矩陣的三元組表中j值，按照遞增的順序重置入T中。col=1p=1M.datap.j=col;p=2p=313-3p=4q=2p=5p=6p=71615q=3p=8col=221122518319342446-7631416 壓縮轉置算法壓縮轉置算法

11、Status TransPoseSMatrix(TSMatrix M, TSMatrix &T) /用三元組表存放稀疏矩陣M，求M的轉置矩陣TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu; /nu是列數,mu是行數,tu是非零元素個數if (T.tu) q=1; /q是轉置矩陣T的結點編號 for(col=1; col=M.nu; col+) /對每個列值均掃描一次 for(p=1; p=M.tu; p+) /p是M三元表中結點編號 if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq

12、.e=M.datap.e; q+; return OK; /TranposeSMatrix算法描述：17 壓縮轉置算法壓縮轉置算法壓縮轉置算法時間復雜度：O(nu*tu)-即與M的列數及非零元的個數的乘積成正比。當非零元數量tu和mu*nu同數量級時，算法的時間復雜度就為O(mu*nu*nu)可見，比不壓縮存儲的矩陣轉置的時間復雜度O(mu*nu)還要高。雖然，節省了存儲空間，但時間復雜度提高了。壓縮轉置算法僅適于非零元很少（tumu*nu）的情況下。18 壓縮快速轉置算法壓縮快速轉置算法2、壓縮快速轉置算法：核心思想：按照M.data中三元組的次序進行轉置，并將轉置后的三元組置入T中恰當的位

13、置上。如果不用多次掃描M三元組表，而是在一次掃描中就將每個元素置入T中該元素所應該在的位置上，就可以大大提高時間復雜度了。關鍵問題在于如何確定每個元素在T中的位置。ije121213931-3361443245218611564-7ije p=1MT2112p=2319p=313-319 壓縮快速轉置算法壓縮快速轉置算法為了確定這些位置，在轉置前，應先求得M的每一列中非零元的個數，進而求得每一列的第一個非零元在T中應在的位置。需要附設兩個數組：numcol:表示矩陣M中第col列中非零元的個數。cpotcol:指示M中第col列的第一個非零元在T.data 中的恰當位置。顯然兩者的關系為： c

14、pot11cpotcol cpotcol-1 + numcol-120 壓縮快速轉置算法壓縮快速轉置算法00070015000001800000240001400003000000000009120Mije121213931-3361443245218611564-7 col1234567numcolcpotcolfor(col=1;col=M.nu;+col) numcol=0;0000000for(t=1;t=M.tu;+t) +numM.datat.j;111 22211 cpot11;for(col=2;col=M.nu;+col) cpotcol cpotcol-1 + numcol

15、-1135788921 壓縮快速轉置算法壓縮快速轉置算法ije121213931-3361443245218611564-7 col 1 2 3 4 5 6 7numcol2221010cpotcolijeMTfor(p=1;p=M.tu;+p)col=M.datap.j; q=cpotcol;M的p位置數據拷貝到T的q位置上； +cpotcol; p=1col=2q=3211213578894p=2col=3q=53916p=3col=1q=113-32p=4col=6q=863149p=5col=3q=6342401234567822 壓縮快速轉置算法壓縮快速轉置算法Status Fast

16、TransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; / 求求M中每列非零元素個數中每列非零元素個數 for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) 元素放入恰當位置; / if return OK; / FastTransposeSMatrix col =M.data p . j ; q =cpot col ; T.dataq.i = M.datap. j; T.dataq.j = M.datap. i; T.dataq.e = M.datap.e; 23 壓縮快速轉置算法壓縮快速轉置算法算法的效率分析：時間上： 算法中主要的基本操作為：該算法的時間