1、矩陣及其基本算法,計13 劉汝佳,矩陣及其基本算法,矩陣的表示 矩陣的基本運算 小結(jié)和應(yīng)用舉例,一、矩陣的表示,三角矩陣的壓縮表示法 稀疏矩陣的三元組表示法 稀疏矩陣的十字鏈表表示法,矩陣在形式上最直接的表示是一個二維數(shù)組，但是在一些特殊的場合中，我們需要引入一些特殊的方法來表示一些特殊的矩陣。在本節(jié)中，大家還將了解到以下幾種表示方法:,矩陣的二維數(shù)組表示法,struct TMatrix int n,m; int numbersMAXN+1MAXN+1; ;,我們用二維數(shù)組很容易表示一個矩陣。加上矩陣的維數(shù)M和N，我們可以定義一個TMatrix結(jié)構(gòu):,這就是矩陣的二維數(shù)組表示法。怎么樣，容易吧

2、？,三角矩陣的壓縮表示(1),N階上三角矩陣，對稱矩陣和反對稱矩陣都只需要儲存主對角線以上的共(N+1)*N/2個元素。 因此，我們可以用一個大小為(N+1)*N/2的一維數(shù)組來表示。 不過，我們需要一個公式，把每個元素原來的位置(i,j)映射到一維數(shù)組的下標k。,三角矩陣的壓縮表示(2),我們從上到下，從左到右地儲存各個元素，如下圖：,Aij前面的數(shù)的個數(shù)為：,計算得:,稀疏矩陣,在前面的二維數(shù)組表示法中，我們表示一個N*M的矩陣需要N*M個內(nèi)存單元。 如果已知矩陣中存在著大量的0元素，那么這種表示方法是很浪費空間的。 由于非零元素的個數(shù)L十分有限，我們可以只儲存下這L個元素的位置和大小，占

3、用的空間便會少得多。,稀疏矩陣的三元組表示法,顯然，表示稀疏矩陣最直接的方法就是僅記錄下非零元素的個數(shù)L和這L個元素的位置(row,col)和大小(value)，即下面這個結(jié)構(gòu)：,struct TMatrix2 int l; int rowMAXL,colMAXL,valueMAXL; ;,稀疏矩陣的十字鏈表表示(1),三元組表示法比較好的解決了稀疏矩陣的空間存儲問題，卻忽視了稀疏矩陣可能進行了一些基本操作。 考慮兩個稀疏矩陣A和B相加的問題。對于運算結(jié)果矩陣C來說，可能會因為正負抵消而產(chǎn)生出很多新的零元素和非零元素，導致三元組需要進行一些插入和刪除操作。當這些操作很頻繁的時候，程序的速度會明

4、顯變慢。 在某些特定情況下，我們需要對元素進行檢索，由于三元組的元素之間聯(lián)系并不緊密，所以檢索很不方便。,稀疏矩陣的十字鏈表表示(2),為了加強同一行和同一列之間元素的聯(lián)系，我們把每一行分別做成一個鏈表，把每一列也分別做成一個鏈表。 通過對鏈表的遍歷，我們可以很方便的按順序訪問到某一特定行或列的所有元素。插入和刪除操作也很方便。 這樣，我們了建立一種十字型的鏈表結(jié)構(gòu)，每個結(jié)點有上，下，左，右四個指針和自身的位置坐標，大小共7個域。,稀疏矩陣的十字鏈表表示(3),結(jié)點類型如下定義：,struct Tnode int row, col; int value; Tnode *left, *right

5、, *up, *down; ;,row,col分別為該非零元素的位置，value為它的值。,left,right,up,down分別為指向四個方向的后繼元素。,稀疏矩陣的十字鏈表表示(4),為了方便的找到每一個包含非零元素的行和列，我們把所有行串在一起，組成一個行鏈表，把所有列也串在一起，組成一個列鏈表。像這樣：,struct TRow int RowNo; TNode * firstnode; ;,struct TCol int ColNo; TNode * firstnode; ;,矩陣表示方法小結(jié),矩陣的表示方法和應(yīng)用是分不開的。 我們衡量一種表示方法的優(yōu)劣，需要從不同的角度進行分析。

6、適用范圍 空間需求量 基本操作的時間消耗 實現(xiàn)的難易程度 以上幾種方法都在某些方面表現(xiàn)良好而其他方面不夠理想，因此我們需要根據(jù)實際需要的側(cè)重點不同，選擇合適的表示方法,二、矩陣的基本運算,矩陣的判重 矩陣的線性運算 矩陣的轉(zhuǎn)置 矩陣乘法,矩陣的判重,在二維數(shù)組表示法中，我們可以用一個二重循環(huán)判斷兩個矩陣是否相等。 在三元組表示方法中，我們?nèi)绻ＷC非零元素是按照從上到下，從左到右的順序儲存的，則可以用一個循環(huán)直接判斷。但如果不能保證，則需要二重循環(huán)。因此在未加說明的情況下，三元組表示法均需要按順序保存各個元素。 在十字鏈表表示方法中，我們需要依次遍歷每一個非零行（或者列）。,矩陣的線性運算,矩陣

7、的數(shù)乘: B=kA 在任何一種表示法中，我們都可以通過遍歷所有元素的方法完成數(shù)乘運算。 矩陣的加法: C=A+B 在二維數(shù)組表示法中，我們可以通過二重循環(huán)來進行矩陣加法 在稀疏矩陣中，注意到結(jié)果中的非零元素所在的位置必對應(yīng)A或B中的一個非零元素，所以加法運算不會在A和B中原非零元素之外的其他位置上生成新的非零元素。,矩陣的線性運算(2),考慮三元組表示法中的矩陣加法。由于都需要按順序儲存各個元素，我們應(yīng)當按順序?qū)γ總€A或B中非零的位置做加法。 下面有一個例子：,矩陣的線性運算(3),我們記錄兩個矩陣A，B的當前非零元素序號pA和pB。為了保證結(jié)果的有序性，我們每次比較這兩個當前元素的位置。 如

8、果A的當前位置靠前，則把A的第pA個元素加入矩陣C，并使pA=pA+1 如果B的當前位置靠前，則把B的第pB個元素加入矩陣C，并使pB=pB+1 如果當前位置相同，則先使pA=pA+1, pB=pB+1。如果A的第pA-1個元素和B的第pB-1個元素的和不為零，則把它加到矩陣C中。,矩陣的線性運算(4),十字鏈表表示法下的加法可以一行行的做。即： 如果A的當前行號比B小，把A的當前行整個復(fù)制到C中。 如果B的當前行號比A小，把B的當前行整個復(fù)制到C中。 否則把A的當前行和B的當前行的合并結(jié)果加入C中。 第三種情況和三元組表示下的加法很類似，只是下標pA,pB換成了指針。 同樣的，需要注意兩個非

9、零元素之和可能等于零，從而不能插入到結(jié)果中,矩陣的轉(zhuǎn)置(1),矩陣的轉(zhuǎn)置 在二維數(shù)組中，轉(zhuǎn)置可以通過簡單的坐標變換得到 在三元組表示法中，在對每個元素進行坐標變換后還需要進行一次排序，以維持元素位置的有序性。 在十字鏈表表示法中，我們不僅需要對每個結(jié)點進行坐標變換，還需要交換行鏈表和列鏈表，以及更改每個結(jié)點四個方向的指針，實現(xiàn)比較麻煩。,矩陣的轉(zhuǎn)置(2),二維數(shù)組的轉(zhuǎn)置可以通過下列代碼來實現(xiàn)：,void MatrixT(TMatrix A) TMatrix B; B.m=A.n; B.n=A.m; for(int i=1;i=A.n;i+) for(int j=1;j=A.m;j+) B.nu

10、mbersji=A.numbersij; return B; ,對代碼稍作修改，我們可以對矩陣進行旋轉(zhuǎn)和鏡像變換生成8個新矩陣,矩陣的轉(zhuǎn)置(3),前面提到過，三元組表示法中，矩陣的轉(zhuǎn)置可以通過坐標變換后排序來實現(xiàn)。 不過，我們通常使用的是另外一種方法。這種方法不用排序，而速度也更快。 快速轉(zhuǎn)置算法：直接寫到正確的位置。 首先，求出每一列第一非零元素轉(zhuǎn)置后的序號。這一步只需要統(tǒng)計一下每列的非零元素的個數(shù)就可以了。 由于每一列的元素在轉(zhuǎn)置以后的先后次序保持不變，每個元素就可以直接寫到該行的下一個空閑位置。,矩陣的轉(zhuǎn)置(4),請看下面的例子：,各列非零元素個數(shù)為：2,3,0,1,各列第一個元素序號：

11、0,2,5,5,0 1 2 3 4 5,1,2,3,4,5,6,矩陣乘法(1),矩陣乘法 在二維數(shù)組表示中，最簡單的方法就是對每個元素用循環(huán)累加出結(jié)果，二重循環(huán)枚舉每個元素，共三層循環(huán)。 在三元組表示中，對于A中的一個元素Aij，我們只需要訪問B中第j行所有元素Bjk，把每個乘積Aij Bjk加到Cik中。這樣，每遍歷A的一行元素，就計算出了C的一行元素。和快速轉(zhuǎn)置算法類似，我們可以事先算出B的每行元素的下標范圍，再用一個循環(huán)依次考慮A中的每個元素就可以了。 十字鏈表在本質(zhì)上是三元組的鏈式存儲，所以乘法和三元組差別不大，但是實現(xiàn)卻麻煩得多。該方法的好處在于，把中間結(jié)果Aij Bjk 加到Cik

12、時，如果Cik并不存在，就需要對矩陣進行插入操作。在十字鏈表上的插入操作比三元組快得多。,矩陣乘法(2),Strassen矩陣乘法 下面，我們來介紹基于二維數(shù)組的矩陣相乘算法。 考慮兩個2*2矩陣A和B相乘。,普通的方法需要進行8次乘法。,矩陣乘法(3),Strassen的新方法如下：,只需要7次乘法!,矩陣乘法(3),當矩陣為2N*2N時，我們可以利用分塊矩陣，分成2*2個2N-1*2N-1矩陣，遞歸求解。當N=1時可以直接利用公式得出結(jié)果。 分析指出，Strassen乘法比常規(guī)乘法的加法和乘法運算量都有減少，但存儲量增加，是一種用空間換時間的方法。 此方法還可以推廣到矩陣的求逆運算。,三、

13、小結(jié)與應(yīng)用舉例,矩陣表示小結(jié) 矩陣運算小結(jié) 結(jié)束語 鳴謝,小結(jié) 矩陣的表示,矩陣的表示 矩陣有三種常用的表示方法：二維數(shù)組，三元組和十字鏈表。 二維數(shù)組適合稠密矩陣，表示直觀，操作方便 三元組是稀疏矩陣最省空間的表示方法之一，它可以很好的支持線性運算和乘法運算，且編程復(fù)雜度低，是稀疏矩陣表示法的首選。 十字鏈表比三元組占用空間大些，不過仍適合稀疏矩陣的表示，尤其適用于非零元素個數(shù)變化較大的場合，但不適合轉(zhuǎn)置操作，且編程實現(xiàn)難度較大。,小結(jié) 矩陣的運算,矩陣的運算 三種方法都可以通過遍歷表的方式判定兩個矩陣是否相同。 三種表示方法都能較好的支持線性運算。數(shù)乘運算只需要遍歷一次所有元素，而稀疏矩陣的加法運算需要進行類似有序表合并的操作。 二維數(shù)組的轉(zhuǎn)置只需要進行坐標變換，三元組還需要排序，而十字鏈表需要更新多個指針域。轉(zhuǎn)置可以推廣到平面點陣圖象的變換，這時一般采用數(shù)組來表示矩陣。 矩陣乘法的算法有很多種?；跀?shù)組的算法中，Strassen算法是一種以空間換時間的算法。稀疏的乘法不是依次計算結(jié)果的每個元素，而是依次考慮A和B的每對元素對結(jié)果的貢獻。,結(jié)束語,在前面的內(nèi)容中，我們討論了矩陣的表示和基本運算。希望這些內(nèi)容能開闊大家的眼界，啟發(fā)大家的思維，激發(fā)大家進一步學習的興趣。 這些內(nèi)容只是矩陣中最最基本的東西。像初等變換，矩