【正文】 / typedef struct GLNode { ElemTag tag。} htp。 lC=（ a， C） 長度為 2遞歸定義的廣義表， C相當于無窮表 C=（ a，（ a，（ a，（ … ））））。 else{ /*尋找列表中的插入位置 */ for(q=Mcol_head[j]。i!=0。 /*稀疏矩陣的行數(shù) 、 列數(shù) 、 非零元素的個數(shù) */ }CrossList。qt。 if(!=) return FALSE。k++) Q[i][j]= Q[i][j]+M[i][k]*N[k][j]。col。 i++) if([i].col==k) { Bdata[j].row=[i].col Bdata[j].col=[i].row。 for(i=0。 當 1in， j=i1, i, i+1 i=n, j=n1, n。另一種是 按列序 存儲，如高級語言中的 FORTRAN語言就是以列序為主。二維數(shù)組可以看成是線性表的線性表。 對于ｎ維數(shù)組 A(c1:d1,c2:d2， …,c n,dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素 aj1j2…jn 的存儲地址的計算公式。 2. 確定非零元素在一維數(shù)組空間中的位置 LOC[i , j] = LOC[1,1]+3 （ i1） 1+ji+1 =LOC[1,1]+2(i1)+j1 返回主目錄 稀疏矩陣 稀疏矩陣 ：指矩陣中大多數(shù)元素為零的矩陣。 } 返回主目錄 實現(xiàn)轉(zhuǎn)置的簡單方法： ① 矩陣 source的三元組表 A的行、列互換就可以得到B中的元素，如圖 ： ② 為了保證轉(zhuǎn)置后的矩陣的三元組表 B也是以 “ 行序為主序 ” 進行存放，則需要對行、列互換后的三元組 B，按 B的行下標（即 A的列下標）大小重新排序。 Blen= 。 Bdata[q].row=[p].col。掃描完三元組 a，求得相應(yīng)元素的乘積并累加到適當?shù)睦塾嫼偷淖兞可稀?arow=。 Qdata[Qlen]={arow, ccol, ctemp[ccol]}。t)。 prow=i。 qdown=p。如：廣義表 B就共享表 A。 union {AtomType atom。 /*原子結(jié)點的值域 atom*/ struct { struct GLNode * hp, *tp。 lB=（ A， A， D）長度為 3的廣義表，其前兩個元素為表 A，第三個元素為空表 D。 /*完成插入 */ } if(Mcol_head[j]==NULL) Mcol_head[j]=p。e)。 /*行 、 列鏈表的頭指針向量 */ int m, n, len。 for(q=[brow]。 int ctemp[MAXSIZE]。k=n1。 for(col=2。 i=。 采用矩陣的正常存儲方式時，實現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下： Void TransMatrix（ ElementType source[n][m], ElementType dest[m][n]） {/*Source和 dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置后的矩陣（用二維數(shù)組表示） */ int i, j。 An n = a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 … … … … … 特點 : i=1, j=1,2。 數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是 按行序 存儲，如高級語言 BASIC、 COBOL和 PASCAL語言都是以行序為主。例如： Am n= a12 a12 ┅ a1j ┅ a1n a21 a22 ┅ a2j ┅ a2n ┇ ┇ ai1 ai2 ┅ aij ┅ ain ┇ ┇ am1 am2 ┅ amj ┅ amn 返回主目錄 Am n= a12 a12 ┅ a1j ┅ a1n a21 a22 ┅ a2j ┅ a2n ┇ ┇ ai1 ai2 ┅ aij ┅ ain ┇ ┇ am1 am2 ┅ amj ┅ amn A=（ ? 1 ? 2 ┅ ?j ┅ ?n) 我們可以把二維數(shù)組看成一個線性表： A=(? 1 ? 2 … ?j … ?n)，其中 ?j（ 1≤j ≤n）本身也是一個線性表，稱為 列向量 。 Loc[j1， j2， …j n]=Loc[c1， c2， … ， ]+? αi (jici) i=1 n 其中 αi =l ? (dkck+1) （ 1≤i≤n） k=i+1 n 返回主目錄 特殊矩陣的壓縮存儲 特殊矩陣壓縮存儲的壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲單元，對于零元素不分配空間。一般地，當非零元素個數(shù)只占矩陣元素總數(shù)的 25%—30%,或低于這個百分數(shù)時，我們稱這樣的矩陣為稀疏矩陣。 B （ i， j， x） ———— （ j， i， x） A 兩種處理轉(zhuǎn)置算法如下： 返回主目錄 算法一、 void TransposeTSMatrix(TSMatrix A, TSMatrix * B) { /*把矩陣 A轉(zhuǎn)置到 B所指向的矩陣中去 。 Bn= 。 Bdata[q]..col=[p].row。 返回主目錄 注意： 兩個稀疏矩陣相乘的結(jié)果 不一定 是稀疏矩陣。 arow++) /*逐行處理 M*/ {for(p=1。 }/* if */ }/* for arow */ }/*if*/ return(TRUE)。 /*輸入 M的行數(shù) ,列數(shù)和非零元素的個數(shù) */ Mm=m。pcol=j。 /*完成插入 */ } } } 返回主目錄 廣義表 廣義表 也是線性表的一種推廣。在表 B中不必列出表 A的內(nèi)容，只要通過子表的名稱就可以引用該表。 struct GLNode * hp。 /*標志位 tag用來區(qū)別原子結(jié)點和表結(jié)點 */ union { AtomType atom。 lA=(a， (b， c))表長度為 2的廣義表，其中第一個元素是單個數(shù)據(jù) a，第二個元素是一個子表（ b， c）。 qright=p。j,amp。 typedef struct { OLink * row_head, *col_head。 else t=+1。 /*矩陣的行數(shù) 、 列數(shù)和非零元素的個數(shù) */ }TriSparMatrix； 為方便實現(xiàn) ， 將三元組表的類型說明修改如下： 返回主目錄 具體算法如下： int MulSMatrix(TriSparMatrix M, TriSparMatrix N, TriSparMatrix *Q)