[工學(xué)]西北大學(xué)：數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組和廣義表-文庫(kù)吧資料
2024-10-19 19:55本頁(yè)面
【正文】 返回主目錄 l D=（） 空表；其長(zhǎng)度為零。 在 GL中， d1是 GL的表頭，其余部分組成的表（ d2， d3， … ， dn） 稱為 GL的表尾。 n是廣義表的長(zhǎng)度。廣義表也是 n個(gè)數(shù)據(jù)元素（ d1， d2， d3， … ， dn）的有限序列，但不同的是，廣義表中的 di既可以是單個(gè)元素，還可以是一個(gè)廣義表， 通常記作： GL=（ d1， d2， d3， … ， dn）。 qdown=p。qdownrowi。 qdownamp。 /*完成插入 */ } if(Mcol_head[j]==NULL) Mcol_head[j]=p。 q=qright) pright=qright。amp。 else{ /*尋找行表中的插入位置 */ for(q=Mrow_head[i]。pvalue=e。 prow=i。j,amp。 scanf(amp。e)。i,amp。 Mrow_head[ ]=Mcol_head[ ]=NULL。 If(!(Mrow_head=(Olink*)malloc((m+1)sizeof(OLink)))) exit(OVERFLOW)。Mn=n。t)。m,amp。 返回主目錄 建立稀疏矩陣的十字鏈表算法： CreateCrossList (CrossList * M) {/*采用十字鏈表存儲(chǔ)結(jié)構(gòu) ， 創(chuàng)建稀疏矩陣 M*/ if(M!=NULL) free(M)。 /*行 、 列鏈表的頭指針向量 */ int m, n, len。 *OLink。 struct OLNode * right,*down。 row col value down right 十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)示意圖： 返回主目錄 十字鏈表的結(jié)構(gòu)類型說明如下： typedef struct OLNode { int row, col。 /*返回 TRUE表示求矩陣乘積成功 */ } 返回主目錄 2. 稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：十字鏈表 優(yōu)點(diǎn)： 它能夠靈活地插入因運(yùn)算而產(chǎn)生的新的非零元素，刪除因運(yùn)算而產(chǎn)生的新的零元素，實(shí)現(xiàn)矩陣的各種運(yùn)算。 Qdata[Qlen]={arow, ccol, ctemp[ccol]}。 } /* for q */ } /*求得 Q中第 crow行的非零元 */ for(ccol=1。q++) {ccol=[q].col。 for(q=[brow]。 /* M中的列號(hào)應(yīng)與 N中的行號(hào)相等 */ if(brow) t=[brow+1]。p[arow+1]。 /* 當(dāng)前行各元素的累加器清零 */ Qfirst[arow]=Qlen+1。p=。 arow=。 Qlen=0。 /*返回 FALSE表示求矩陣乘積失敗 */ Qm=。 int ctemp[MAXSIZE]。 */ int m, n, len。 /* 非零元素的三元組表 ， data[0]未用 */ int first[MAXROW+1]。 /*該非零元素的行下標(biāo)和列下標(biāo) */ ElementType e； /*該非零元素的值 */ }Triple。反之，相乘的每個(gè)分量 M[i， k] N[k， j]不為零，但累加的結(jié)果 Q[i， j]可能是零。掃描完三元組 a，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)睦塾?jì)和的變量上。即：以三元組 a中的元素為基準(zhǔn)，依次求出其與三元組 b的有效乘積。 } 返回主目錄 經(jīng)典算法中，不論 M[i][k]， N[k][j]是否為零，都要進(jìn)行一次乘法運(yùn)算，而實(shí)際上，這是沒有不必要的。k=n1。j++) { Q[i][j]=0。i++) for(j=1。 數(shù)學(xué)中矩陣 Q中的元素的計(jì)算方法如下： 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。 Bdata[q].e=[p].e position[col]++。 Bdata[q].
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1