【正文】 i和 j相互調(diào)換； 。 T(n)=O(m?n) 對于一個 m n的矩陣 M，它的轉置矩陣 T是一個 n m矩陣，且 T(i, j) = M(j, i)， 1≤ i≤ n， 1≤ j≤ m。rowm。coln。 JD ma[M]。 int v。 矩陣的壓縮存儲 矩陣是很多科學與工程計算問題中研究的數(shù)學對象 ,本節(jié)討論如何存儲矩陣的元 ,從而對矩陣進行各種有效運算；對一些特殊矩陣我們可以用很少的空間來存儲以達到壓縮的目的。 數(shù)組的定義和特點 ?定義 ??????????????????mnmmnnnmaaaaaaaaaA.................................212222111211?數(shù)組特點 ?數(shù)組結構固定 ?數(shù)據(jù)元素同構 ?數(shù)組運算 ?給定一組下標，存取相應的數(shù)據(jù)元素 ?給定一組下標，修改數(shù)據(jù)元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 167。第 5章 數(shù)組 數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個線性表。 167。 數(shù)組的順序表示和實現(xiàn) ?次序約定 ?以行序為主序 ?以列序為主序 a11 a12 …….. a 1n a21 a22 …….. a 2n am1 am2 …….. a mn …………………. Loc( aij)=Loc(a11)+[(i1)*n+j1]*l 按行序為主序存放 amn …….. am2 am1 ………. a2n …….. a22 a21 a1n ……. a12 a11 0 1 n1 m*n1 n 按列序為主序存放 1 m m*n1 m ……..2n 1n ……….m2 …….. 12 m1 …….21 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j1)*m+i1)]*l 167。 特殊矩陣 ?對稱矩陣（相同元素取一次，實現(xiàn)了壓縮） ????????????jiijjjijiik,12/)1(12/)1( ， a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n an1 an2 …….. ann …………………. a11 a21 a22 a31 a32 an1 ann …... …...k=0 1 2 3 4 n(n1)/2 n(n+1)/21 按行序為主序： ?三角矩陣 a11 0 0 …….. 0 a21 a22 0 …….. 0 an1 an2 an3…….. ann …………………. 0 Loc(aij)=Loc(a11)+[( +(j1)]*l i(i1) 2 a11 a21 a22 a31 a32 an1 ann …... …...k=0 1 2 3 4 n(n1)/2 n(n+1)/21 按行序為主序： ?對角矩陣 a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0 0 0 … an1,n2 an1,n1 an1,n 0 0 … … an,n1 ann. 0 a32 a33 a34 0 ……… 0 …………………………… Loc(aij)=Loc(a11)+2(i1)+(j1) a11 a12 a21 a22 a23 ann1 ann …... …... k=0 1 2 3 4 n(n1)/2 n(n+1)/21 按行序為主序： 7600070015000001800000240001400003000000000009120????????????????????????MM由 {(1,2,12), (1,3,9), (3,1,3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,7) } 和矩陣維數(shù)（ 6,7）唯一確定 稀疏矩陣 ?定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣 ?壓縮存儲原則：只存矩陣的行列維數(shù)和每個非零元的行列下標及其值 ?稀疏程度的計算： )( 為非零元個數(shù)tnm t????稀疏矩陣的壓縮存儲方法 ?順序存儲結構 ?三元組表 define M 20 typedef struct node { int i,j。 }JD。 三元組表所需存儲單元個數(shù)為 3(t+1) 其中 t為非零元個數(shù) 利用三元組表求稀疏矩陣的轉置（ 1） P98~99 6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 ma i j v 0 1 2 3 4 5 6 7 8 ma[0].i,ma[0].j,ma[0].v分別存放 矩陣行列維數(shù)和非零元個數(shù) 行列下標 非零元值 76000700150