【文章內(nèi)容簡介】 +) num[col]=0。 for(t=1。t=。t++) num[[t].col]++。 /*計算每一列的非零元素的個數(shù) */ 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]++。 }} } 返回主目錄 用三元組表實現(xiàn)稀疏矩陣的乘法運算 設(shè)矩陣 M是 m1 n1矩陣， N是 m2 n2矩陣；若可以相乘，則必須滿足矩陣 M的列數(shù) n1與矩陣 N的行數(shù)m2相等，才能得到結(jié)果矩陣 Q=M N（一個 m1 n2的矩陣）。 數(shù)學(xué)中矩陣 Q中的元素的計算方法如下： Q[i][j] = ? M[i][k] N[k][j] n1 k=1 其中： 1≤i≤m1， 1≤j≤n2 返回主目錄 根據(jù)數(shù)學(xué)上矩陣相乘的原理，我們可以得到矩陣相乘的經(jīng)典算法： 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]。 } 返回主目錄 經(jīng)典算法中，不論 M[i][k]， N[k][j]是否為零，都要進(jìn)行一次乘法運算，而實際上，這是沒有不必要的。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組 a中元素（ i， k， Mik）（ 1≤i≤m1，1≤k≤n1），在三元組 b中找所有行號為 k的的對應(yīng)元素（ k， j，Nkj）（ 1≤k≤m2， 1≤j≤n2）進(jìn)行相乘、累加從而得到 Q[i][j]。即：以三元組 a中的元素為基準(zhǔn)，依次求出其與三元組 b的有效乘積。 相乘基本操作： 對于三元組 a中每個元素 [p]（ p=1， 2，3， … ），找出三元組 b中所有滿足條件[p].col=[q].row的元素 [q]，求得 [p].e與 [q].e的乘積，而這個乘積只是 Q[i， j]的一部分，應(yīng)對每個元素設(shè)一個累計和變量，其初值為 0。掃描完三元組 a，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)睦塾嫼偷淖兞可稀? 返回主目錄 注意： 兩個稀疏矩陣相乘的結(jié)果 不一定 是稀疏矩陣。反之，相乘的每個分量 M[i， k] N[k， j]不為零，但累加的結(jié)果 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 /*非零元素的個數(shù)最多為 1000*/ define MAXROW 1000 /*矩陣最大行數(shù)為 1000*/ typedef struct {int row, col。 /*該非零元素的行下標(biāo)和列下標(biāo) */ ElementType e； /*該非零元素的值 */ }Triple。 typedef struct { Triple data[MAXSIZE+1]。 /* 非零元素的三元組表 ， data[0]未用 */ int first[MAXROW+1]。 /*三元組表中各行第一個非零元素所在的位置 。 */ int m, n, len。 /*矩陣的行數(shù) 、 列數(shù)和非零元素的個數(shù) */ }TriSparMatrix； 為方便實現(xiàn) ， 將三元組表的類型說明修改如下： 返回主目錄 具體算法如下： int MulSMatrix(TriSparMatrix M, TriSparMatrix N, TriSparMatrix *Q) {/*采用改進(jìn)的三元組表表示法 ， 求矩陣乘積 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 。 /* 當(dāng)前行各元素的累加器清零 */ Qfirst[arow]=Qlen+1。 for(p=[arow]。p[arow+1]。p++) /*p指向 M當(dāng)前行中每一個非零元素 */ 返回主目錄 {brow=[p].col。 /* M中的列號應(yīng)與 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. 稀疏矩陣的鏈?zhǔn)酱鎯Y(jié)構(gòu)：十字鏈表 優(yōu)點： 它能夠靈活地插入因運算而產(chǎn)生的新的非零元素，刪除因運算而產(chǎn)生的新的零元素，實現(xiàn)矩陣的各種運算。 在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（ row， col， value）以外，還要有兩個域： right： 用于鏈接同一行中的下一個非零元素； down：用以鏈接同一列中的下一個非零元素。 row col value down right 十字鏈表中結(jié)點的結(jié)構(gòu)示意圖： 返回主目錄 十字鏈表的結(jié)構(gòu)類型說明如下： typedef struct OLNode { int row, col。 /*非零元素的行和列下標(biāo) */ ElementType value。 struct OLNode * right,*down。 /*非零元素所在行表列表的后繼鏈域 */ }OLNode。 *OLink。 typedef struct { OLink * row_head, *col_head。 /*行 、 列鏈表的頭指針向量 */ int m, n, len。 /*稀疏矩陣的行數(shù) 、 列數(shù) 、 非零元素的個數(shù) */ }CrossList。 返回主目錄 建立稀疏矩陣的十字鏈表算法： CreateCrossList (CrossList * M) {/*采用十字鏈表存儲結(jié)構(gòu) ， 創(chuàng)建稀疏矩陣 M*/ if(M!=NULL) free(M)。 scanf(amp。m,amp。n,amp。t)。 /*輸入 M的行數(shù) ,列數(shù)和非零元素的個數(shù) */ 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)))