【文章內容簡介】 ++。 /*計算每一列的非零元素的個數 */ position[1]=1。 for(col=2。col。col++) /*求 col列中第一個非零元素在 [ ]中的正確位置 */ position[col]=position[col1]+num[col1]。 for(p=1。p++) { col=[p].col。 q=position[col]。 Bdata[q].row=[p].col。 Bdata[q]..col=[p].row。 Bdata[q].e=[p].e position[col]++。 }} } 用三元組表實現稀疏矩陣的乘法運算 設矩陣 M是 m1 n1矩陣， N是 m2 n2矩陣；若可以相乘，則必須滿足矩陣 M的列數 n1與矩陣 N的行數m2相等，才能得到結果矩陣 Q=M N（一個 m1 n2的矩陣）。 數學中矩陣 Q中的元素的計算方法如下： Q[i][j] = ? M[i][k] N[k][j] n1 k=1 其中： 1≤i≤m1， 1≤j≤n2 根據數學上矩陣相乘的原理，我們可以得到矩陣相乘的經典算法： for(i=1。i=m1。i++) for(j=1。j=n2。j++) { Q[i][j]=0。 for(k=1。k=n1。k++) Q[i][j]= Q[i][j]+M[i][k]*N[k][j]。 } 經典算法中，不論 M[i][k]， N[k][j]是否為零，都要進行一次乘法運算，而實際上，這是沒有不必要的。采用三元組表的方法來實現時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組 a中元素（ i， k， Mik）（ 1≤i≤m1，1≤k≤n1），在三元組 b中找所有行號為 k的的對應元素（ k， j，Nkj）（ 1≤k≤m2， 1≤j≤n2）進行相乘、累加從而得到 Q[i][j]。即：以三元組 a中的元素為基準，依次求出其與三元組 b的有效乘積。 相乘基本操作： 對于三元組 a中每個元素 [p]（ p=1， 2，3， … ），找出三元組 b中所有滿足條件[p].col=[q].row的元素 [q]，求得 [p].e與 [q].e的乘積，而這個乘積只是 Q[i， j]的一部分，應對每個元素設一個累計和變量，其初值為 0。掃描完三元組 a，求得相應元素的乘積并累加到適當的累計和的變量上。 注意： 兩個稀疏矩陣相乘的結果 不一定 是稀疏矩陣。反之，相乘的每個分量 M[i， k] N[k， j]不為零，但累加的結果 Q[i， j]可能是零。 例如： 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 = 1 1 1 1 1 1 1 1 1 define MAXSIZE 1000 /*非零元素的個數最多為 1000*/ define MAXROW 1000 /*矩陣最大行數為 1000*/ typedef struct {int row, col。 /*該非零元素的行下標和列下標 */ ElementType e； /*該非零元素的值 */ }Triple。 typedef struct { Triple data[MAXSIZE+1]。 /* 非零元素的三元組表 ， data[0]未用 */ int first[MAXROW+1]。 /*三元組表中各行第一個非零元素所在的位置 。 */ int m, n, len。 /*矩陣的行數 、 列數和非零元素的個數 */ }TriSparMatrix； 為方便實現 ， 將三元組表的類型說明修改如下： 具體算法如下： int MulSMatrix(TriSparMatrix M, TriSparMatrix N, TriSparMatrix *Q) {/*采用改進的三元組表表示法 ， 求矩陣乘積 Q＝ M N*/ int arow , brow , p。 int ctemp[MAXSIZE]。 if(!=) return FALSE。 /*返回 FALSE表示求矩陣乘積失敗 */ Qm=。 Qn=。 Qlen=0。 if(*!=0) {for(arow=1。 arow=。 arow++) /*逐行處理 M*/ {for(p=1。p=。p++) ctemp[p]=0 。 /* 當前行各元素的累加器清零 */ Qfirst[arow]=Qlen+1。 for(p=[arow]。p[arow+1]。p++) /*p指向 M當前行中每一個非零元素 */ {brow=[p].col。 /* M中的列號應與 N中的行號相等 */ if(brow) t=[brow+1]。 else t=+1。 for(q=[brow]。qt。q++) {ccol=[q].col。 /*乘積元素在 Q中列號 */ ctemp[ccol]+=[p].e*[q].e。 } /* for q */ } /*求得 Q中第 crow行的非零元 */ for(ccol=1。ccolQn； col++) /*壓縮存儲該非零元 */ if(ctemp[ccol]) {if(++QlenMAXSIZE) return 0。 Qdata[Qlen]={arow, ccol, ctemp[ccol]}。 }/* if */ }/* for arow */ }/*if*/ return(TRUE)。 /*返回 TRUE表示求矩陣乘積成功 */ } 2. 稀疏矩陣的鏈式存儲結構：十字鏈表 優(yōu)點： 它能夠靈活地插入因運算而產生的新的非零元素，刪除因運算而產生的新的零元素，實現矩陣的各種運算。 在十字鏈表中，矩陣的每一個非零元素用一個結點表示，該結點除了（ row， col， value）以外，還要有兩個域： right： 用于鏈接同一行中的下一個非零元素； down：用以鏈接同一列中的下一個非零元素。 row col value down right 十字鏈表中結點的結構示意圖： 返回主目錄 十字鏈表的結構類型說明如下： typedef struct OLNode { int row, col。 /*非零元素的行和列下標 */ ElementType value。 struct OLNode * right,*down。 /*非零元素所在行表列表的后繼鏈域 */ }OLNode。 *OLink。 typedef struct { OLink * row_head, *col_head。 /*行 、 列鏈表的頭指針向量 */ int m, n, len。 /*稀疏矩陣的行數 、 列數 、 非零元素的個數 */ }CrossList。 建立稀疏矩陣的十字鏈表算法： CreateCrossList (CrossList * M) {/*采用十字鏈表存儲結構 ， 創(chuàng)建稀疏矩陣 M*/ if(M!=NULL) free(M)。 scanf(amp。m,amp。n,amp。t)。 /*輸入 M的行數 ,列數和非零元素的個數 */ Mm=m。Mn=n。Mlen=t。 If(!(Mrow_head=(Olink*)malloc((m+1)sizeof(OLink)))) exit(OVERFLOW)。 If(!(Mcol_head=(OLink * )malloc((n+1)sizeof(OLink)))) exit(OVERFLOW)。 Mrow_head[ ]=Mcol_head[ ]=NULL。 /*初