稀疏矩陣的三元組順序表存儲及矩陣相乘算法小結
巧若拙（歡迎轉載，但請注明出處：http://blog.csdn.net/qiaoruozhuo）
一：稀疏矩陣的三元組順序表數據結構
typedef int ElemType;
typedef struct
{
intx, y; //該非零元素的行下標和列下標
ElemTypee; //該非零元素的值
} Triple;
typedef struct
{
Tripledata[MAXSIZE]; //非零元素三元組順序表
intmu, nu, tu; //矩陣的行數，列數和非零元素的個數
} TSMatrix;
二：三元組順序表實現矩陣轉置
顯然，一個稀疏矩陣的轉置矩陣仍然是稀疏矩陣。假設a和b是TSMatrix型的變量，分別表示矩陣M和T。那麼，如何由a得到b呢？
從分析a和b之間的差異可見只要做到：1。將矩陣的行列值互換；2。將每個三元組中的i和j互換；3。重排三元組之間的次序便可以實現矩陣的轉置。
前兩條是容易做到的，關鍵是如何實現第三條，即如何使b.data中的三元組是以T的行序（M的列序）為主序依次排列的。
可以有兩種處理方法：
1， 按照b.data中三元組的次序依次在a.data中找到相應的三元組進行轉置。即按照M的列序來進行轉置。代碼如下：
TSMatrix TransposeSMatrix(TSMatrix M)//三元組順序表 轉置矩陣
{
intk, i, col;
TSMatrixT;
T.mu= M.nu;
T.nu= M.mu;
T.tu= M.tu;
if(T.tu > 0)
{
k= 0;
for(col=1; col<=M.nu; col++) //按照T的行序（M的列序）為主序依次排列
for(i=0; i if(M.data[i].y == col) { T.data[k].x= M.data[i].y; T.data[k].y= M.data[i].x; T.data[k++].e= M.data[i].e; } } returnT; } 2，按照a.data中三元組的次序進行轉置，並將轉置後的三元組置入b中恰當的位置。 即預先確定M中每一列（即T中的每一行）的第一個非零元素在b.data中應有的位置。在此，需要附設num和cpot兩個數組，num[col-1]表示矩陣M中第col列中非零元素的個數，cpot[col-1]指示M中第col列中第一個非零元素在b.data中的位置，顯然有： cpot[0] = 0； cpot[col] = cpot[col-1] + num[col-1] 0
TSMatrix FastTransposeSMatrix(TSMatrixM) //三元組順序表快速轉置矩陣
{
TSMatrixT;
intk, i, col;
intnum[N] = {0};
intcpot[N] = {0};
T.mu= M.nu;
T.nu= M.mu;
T.tu= M.tu;
if(T.tu > 0)
{
for(i=0; i num[M.data[i].y-1]++;//確定矩陣M每一列中非零元素的個數 cpot[0]= 0; for(col=1; col cpot[col]= cpot[col-1] + num[col-1];// 確定矩陣M第col列中第一個非零元素在b.data中的位置 for(i=0; i { col= M.data[i].y - 1; //標出該元素所在的列 k= cpot[col]; //k即矩陣M第col列（即T中的第col行）中第一個非零元素在b.data中的位置
T.data[k].x= M.data[i].y; T.data[k].y= M.data[i].x; T.data[k].e= M.data[i].e; cpot[col]++;//矩陣M第col列中第一個非零元素在b.data中的位置向前移動一位 } } returnT; } 三：三元組順序表實現矩陣相乘 壓縮存儲的矩陣與用二維數組存儲的矩陣在進行乘法運算時最大的不同是，在經典（二維數組存儲）算法中，不論M（i,k）和N（k,j）的值是否為零，都要進行一次乘法計算，這樣造成很大的浪費。而壓縮存儲則只需在M.data和N.data中找到相應的元素相乘即可。 這裡介紹三種算法。 第一種，通過給定的行號i和列號j找出原矩陣的對應的元素，設計一個函數Value()，當在三元組順序表中找到該元素時，返回其元素值，否則說明該位置元素值為0，返回0。然後利用該函數計算出C的行號i和列號j處元素的值，若該值不為0，則存入C，否則不存入。代碼如下： int Value(TSMatrix M, int i, int j) //計算出矩陣M的i行j列處元素的值 { intk = 0; while(k < M.tu && M.data[k].x <= i) //因為是按行序排列，故不必掃描行號比i大的元素 { if(M.data[k].x == i && M.data[k].y == j) returnM.data[k].e; k++; } return0; } TSMatrix MultSMatrix(TSMatrix A, TSMatrixB) //三元組順序表低效矩陣乘法 { TSMatrixC; inti, j, k, l, p, s; C.mu= A.mu; C.nu= B.nu; C.tu= 0; if(A.tu * B.tu != 0) { p= 0; for(i=1; i<=A.mu; i++) { for(j=1; j<=B.nu; j++) { s= 0; for(k=1; k<=A.nu; k++) s+= Value(A, i, k) * Value(B, k, j); if(s != 0) { C.data[p].x= i; C.data[p].y= j; C.data[p++].e= s; } } } C.tu= p; } returnC; } 這種算法的存儲空間雖然很少，但時間復雜度為O（A.mu*A.nu*B.nu*（A.tu+B.tu）），比經典的算法時間復雜度還高，因此是一種用時間換空間的方法。
如果我們預先確定矩陣的每一行的第一個非零元素在三元組順序表中的位置，則可以得到改進的算法。 基本操作是對於A中每個元素A.data[p]，找到N中所有滿足條件A.data[p].y==B.data[q].x的元素B.data[q]，求得A.data[p].e和B.data[q].e的乘積，當然這個乘積的值只是乘積矩陣C[i][j]中的一部分。 為了便於操作，我們可以對每個元素設置一個累計乘積值的變量，使其初值為0，然後掃描A，求得相應元素的乘積值並累積到相應的累計乘積值的變量中。 由於C中元素的行號和A中元素的行號一致，又都是以行序為主序排列的，因此可以對C進行逐行處理。代碼如下： void RPos(TSMatrix M, int rpos[])//確定矩陣的每一行的第一個非零元素在三元組順序表中的位置 { intnum[N] = {0}; inti, row; for(i=0; i num[M.data[i].x-1]++;//確定矩陣M每一行中非零元素的個數 rpos[0]= 0; for(row=1; row rpos[row]= rpos[row-1] + num[row-1];// 確定矩陣M第row行中第一個非零元素在M.data中的位置 } TSMatrix FastMultSMatrix_1(TSMatrix A,TSMatrix B)//三元組順序表快速矩陣乘法之一 { TSMatrixC; intArpos[N] = {0}, Brpos[N] = {0};//分別存儲矩陣A，B的每一行的第一個非零元素在三元組中的位置 intctemp[N] = {0};//存儲正在處理的該行中每一列的乘積值，是一個累積的和值，作為矩陣C在該位置處元素的值 intarow, brow, ccol; inti, p, q; intta, tb; C.mu= A.mu; C.nu= B.nu; C.tu= 0; if(A.tu * B.tu != 0)//若C是非零矩陣 { RPos(A,Arpos); //確定矩陣A的每一行的第一個非零元素在三元組順序表中的位置 RPos(B,Brpos); //確定矩陣B的每一行的第一個非零元素在三元組順序表中的位置 for(arow=1; arow<=A.mu; arow++)//對A進行逐行處理 ，即對C進行逐行處理 { for(i=0; i ctemp[i]= 0; if(arow < A.mu) //處理A中第arow行的每一個非零元素，ta指示下一行第一個非零元素的位置 ta= Arpos[arow]; else //最後一行的下一行第一個非零元素的位置 當然是 A.tu ta= A.tu; for(p=Arpos[arow-1]; p brow= A.data[p].y; //標出該元素的列號，在B中找到與它對應的行號 if(brow < B.mu) tb= Brpos[brow]; else tb= B.tu; for(q=Brpos[brow-1]; q { ccol= B.data[q].y - 1; ctemp[ccol]+= A.data[p].e * B.data[q].e; } } for(ccol=0; ccol { if(ctemp[ccol] != 0)//壓縮存儲該行非零元 { if(C.tu == MAXSIZE) { printf("三元組溢出！\n" ); exit(1); } C.data[C.tu].x= arow; //C的行數等於A的行數 C.data[C.tu].y=ccol + 1; //C的列數等於B的列數 C.data[C.tu++].e= ctemp[ccol]; //C的元素值等於A的行數ctemp[ccol]的累積值
} } } } returnC; } 分析上述算法的時間復雜度有如下結果：確定矩陣的每一行的第一個非零元素在三元組順序表中的位置的時間復雜度為O（A.tu+A.mu+B.tu+B.mu+），累加器ctemp初始化的時間復雜度為O（A.mu*B.nu），C的所有非零元素的時間復雜度為O（A.tu*B.tu/B.mu），進行壓縮存儲的時間復雜度為O（A.mu*B.tu），因此總的時間復雜度為O（A.mu*B.nu + A.tu*B.tu/B.mu）。當矩陣為稀疏矩陣時，這種算法的時間復雜度接近O（A.mu*B.nu），比經典算法要快。 還有一種快速矩陣乘法，它是先將矩陣B轉置，這樣矩陣A與B的列數就相同了，矩陣B的行數即矩陣C的列數。此種算法不需要設置數組ctemp[N]，只需直接計算該行對應列的元素乘積的總和即可得到矩陣C的值。此算法時間復雜度為O（A.mu*B.nu *MAX(ta,tb)），其中MAX(ta,tb)表示A矩陣和B的轉置矩陣中每行非零元素個數的最大值。 算法通俗易懂，代碼也很簡潔。代碼如下： TSMatrix FastMultSMatrix_2(TSMatrix A,TSMatrix B)//三元組順序表快速矩陣乘法之二 { TSMatrixC; intArpos[N] = {0}, Brpos[N] = {0};//分別存儲矩陣A，B的每一行的第一個非零元素在三元組中的位置 intarow, brow, ccol; inti, p, q, ta, tb; C.mu= A.mu; C.nu= B.nu; C.tu= 0; if(A.tu * B.tu != 0)//若C是非零矩陣 { B= FastTransposeSMatrix(B); //求矩陣B的轉置矩陣 RPos(A,Arpos); //確定矩陣A的每一行的第一個非零元素在三元組順序表中的位置 RPos(B,Brpos); //確定矩陣B的每一行的第一個非零元素在三元組順序表中的位置 for(arow=1; arow<=A.mu; arow++)//對A進行逐行處理 ，即對C進行逐行處理 { ta= (arow < A.mu) ? Arpos[arow] : A.tu; for(brow=1; brow<=B.mu; brow++) { C.data[C.tu].e= 0; p= Arpos[arow-1]; tb= (brow < B.mu) ? Brpos[brow] : B.tu; q= Brpos[brow-1]; while(p < ta && q < tb) { if(A.data[p].y < B.data[q].y) p++; elseif (A.data[p].y > B.data[q].y) q++; else C.data[C.tu].e+= A.data[p++].e * B.data[q++].e; //C的元素值等於該行對應列的元素乘積的總和 } if(C.data[C.tu].e != 0) { C.data[C.tu].x= arow; C.data[C.tu++].y= brow; } } } } returnC; }
