數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組與廣義表課件(編輯修改稿)
2025-10-06 09:02 本頁面
【文章內(nèi)容簡介】 /*矩陣的行數(shù) */ int 。 /*矩陣的列數(shù) */ int tn。 /*矩陣的非 0元素個數(shù) */ tritype data[maxn]。 /*非 0元素的三元組表 */ }tmatrix。 ? 把 M壓縮后，存儲成： 行數(shù) rn 列數(shù) 非 0數(shù) tn 行號 列號 元素值 1 2 2 1 3 1 3 1 1 3 6 4 5 2 8 6 1 5 7 6 9 7 7 7 ? 例 : 求 M的轉(zhuǎn)置矩陣 . s: t: 1 2 2 1 3 1 3 1 1 3 6 4 5 2 8 6 1 5 7 6 9 7 7 7 7 7 7 1 3 1 1 6 5 2 1 2 2 5 8 3 1 1 6 3 4 6 7 9 ?基本思想： 把 S轉(zhuǎn)置成 T，就是把 S中的每一個三元組的行號和列號（ row 和 col）交換，并存儲在 T中。但是，這樣的結(jié)果是按列優(yōu)先存儲的稀疏矩陣 T，所以，還必須重新排列三元組的順序。 由于 S的列是 T的行，因此，應(yīng)按 S中列的順序掃描 ,即先掃描第 1列所有非 0元素，然后第2列所有非 0元素 ,…… ，最后得到的結(jié)果就是按行優(yōu)先順序存儲的。 ?算法如下： Inttrmatrix(tmatrix s, t) { int i, j, k。 =。 /*列數(shù)變行數(shù) */ =。 /*行數(shù)變列數(shù) */ =； /*非 0元素個數(shù)賦值 */ if (!=0) { j=0。 /*三元組 T（目的地）中的位置 for (i=1。 i=。 i++) /* for (k=0。 k。 k++) /* 0元素個數(shù) if([k].col==i) /*若列號為 I, 則置換 { [j].row=[k].col。 [j].col=[k].row。 [j].element=[k].element。 j++。 } }。 return(0)。 } ?稀疏矩陣的十字鏈表 當(dāng)矩陣的非零元素的位置和個數(shù)經(jīng)常變動時 , 三元組就不適用于稀疏矩陣的存儲了 . 例 : A=A+B 把矩陣 B加到 A上 , 則會產(chǎn)生大量的數(shù)據(jù)移動 , 此時 , 采用十字鏈表存儲更合適 . 對一個 m*n 的稀疏矩陣 , 對每一個非零元素 , 用一個結(jié)點(diǎn)表示 . 結(jié)點(diǎn)的結(jié)構(gòu)如下 : 其中 : row 非零元素所在行 col 非零元素所在行 value 非零元素的值
試題試卷相關(guān)推薦
鄂ICP備17016276號-1