【文章內(nèi)容簡介】 的列序，依次在 。 ? 步驟：從 k=1開始依次掃描找尋所有列號為 k的項，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。 ? 其時間復雜度為 O ( * )。 ? 例：若矩陣有 200行， 200列， 10,000個非零元素，總共有2,000,000次處理。 稀疏矩陣的轉(zhuǎn)置 (算法 ) Status TransposeSMatrix(TSMatrix M,TSMatrix amp。T) { int q,col,p。 =。 =。 =。 if () { q=1。 for (col=1。col=。++col) for(p=1。p=。++p) if ([p].j==col) { [q].i=[p].j。 [q].j=[p].i。 [q].e=[p].e。 ++q。 } } return OK。 } 快速轉(zhuǎn)置算法 ? 方法：按 ，并將轉(zhuǎn)置后的三元組置入 b中恰當?shù)奈恢谩? ? 建立輔助數(shù)組 num和 cpot， num[col]表示矩陣第 col列中非零元的個數(shù)， cpot[col]指示第 col列的第一個非零元素在。 ? 按行掃描矩陣三元組表，根據(jù)某項的列號，確定它轉(zhuǎn)置后的行號，查 cpot表，按查到的位置直接將該項存入轉(zhuǎn)置三元組表中。 ? 轉(zhuǎn)置時間復雜度為 O(nu+tu+nu+tu)=O(tu)。若矩陣有 200列， 10000個非零元素，總共需 10000次處理。 ? cpot[1]=1 ? cpot[col]=cpot[col1]+num[col1] col 1 2 3 4 5 6 7 語 義 num [col] 2 2 2 1 0 1 0 矩陣 A 各列非零元素個數(shù) cpot [col] 1 3 5 7 8 8 9 矩陣 B 各行開始存放位置 稀疏矩陣的快速轉(zhuǎn)置 (算法 ) Status FastTransposeSMatrix(TSMatrix M,TSMatrix amp。T) { =。 =。 =。 if () { for (col=1。col=。++col) num[col]=0。 for (t=1。t=。++t) ++num[[t].j]。 cpot[1]=1。 for (col=2。col=。++col) cpot[col]=cpot[col1]+num[col1]。 for (p=1。p=。++p) { col=[p].j。 q=cpot[col]。 [q].i=[p].j。 [q].j=[p].i。 [q].e=[p].e。 ++cpot[col]。 } } return OK。 } 用三元組表實現(xiàn)稀疏矩陣的乘法運算 設(shè)矩陣 M是 m1 n1矩陣， N是 m2 n2矩陣；若可以相乘，則必須滿足矩陣 M的列數(shù) n1與矩陣 N的行數(shù)m2相等，才能得到結(jié)果矩陣 Q=M N（一個 m1 n2的矩陣）。 數(shù)學中矩陣 Q中的元素的計算方法如下： Q[i][j] = ? M[i][k] N[k][j] n1 k=1 其中： 1≤i≤m1， 1≤j≤n2 根據(jù)數(shù)學上矩陣相乘的原理，我們可以得到矩陣相乘的經(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]是否為零，都要進行一次乘法運算，而實際上，這是沒有不必要的。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組 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]的一部分，應對每個元素設(shè)一個累計和變量，其初值為 0。掃描完三元組 a，求得相應元素的乘積并累加到適當?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 2. 稀疏矩陣的鏈式存儲結(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é)點 ? right——指向同一行中下一個非零元素的指針（向右域） ? down——指向同一列中下一個非零元素的指針（向下域） ? 表頭結(jié)點 ? 行表頭結(jié)點 ? 列表頭結(jié)點 ? next用于表示頭結(jié)點的鏈接 row col val down right col=0 next right row=0 next down ? 由于行、列表頭結(jié)點互相不沖突，所以可以合并起來： ? 總表頭結(jié)點： row=0 col=0 next down right row col next ? 每一非零元 結(jié)點 ? 每一行非零元 一行循環(huán)鏈表 …right ? 每一行非零元 一列循環(huán)鏈表 …down ? 設(shè)頭結(jié)點：行： right 列： down 共用表頭結(jié)點 m行、 n列 max{m,n}個表頭結(jié)點 ? 設(shè)總頭結(jié)點：通過 next域連接所有的頭結(jié)點 總共需要頭結(jié)點個數(shù)： max{m,n}+t+1 (t:非零元素個數(shù) 1：頭結(jié)點 ) 建立十字鏈表： While {申請一非零元素結(jié)點 插入行表 { } 插入列表 { } scanf(r,c,v) }跳出循環(huán)， p插入 q之后 類型定義： typedef struct node{ int row,col。 //非零元的行下標和列下標 struct node *down,*right。 union v_next {datatype v。 struct node *next。 } }MNode,*MLink。 因為非零元素結(jié)點的值域是 datatype類型，在表頭結(jié)點中需要一個指針類型，為了整個結(jié)構(gòu)結(jié)點的一致，我們規(guī)定表頭結(jié)點和其它結(jié)點有同樣的結(jié)構(gòu)，因此該域用一個聯(lián)合表示。 稀疏矩陣的十字鏈表表示的示例 稀疏矩陣的十字鏈表建立 算法思想： ? 首先建立每行（每列）只有頭結(jié)點的空鏈表，并建立