關于矩陣及其基本算法第一頁，共三十三頁，編輯于2023年，星期二矩陣及其基本算法矩陣的表示矩陣的基本運算小結(jié)和應用舉例第二頁，共三十三頁，編輯于2023年，星期二一、矩陣的表示三角矩陣的壓縮表示法稀疏矩陣的三元組表示法稀疏矩陣的十字鏈表表示法矩陣在形式上最直接的表示是一個二維數(shù)組，但是在一些特殊的場合中，我們需要引入一些特殊的方法來表示一些特殊的矩陣。在本節(jié)中，大家還將了解到以下幾種表示方法:第三頁，共三十三頁，編輯于2023年，星期二矩陣的二維數(shù)組表示法structTMatrix{intn,m;intnumbers[MAXN+1][MAXN+1];};我們用二維數(shù)組很容易表示一個矩陣。加上矩陣的維數(shù)M和N，我們可以定義一個TMatrix結(jié)構(gòu):這就是矩陣的二維數(shù)組表示法。怎么樣，容易吧？第四頁，共三十三頁，編輯于2023年，星期二三角矩陣的壓縮表示(1)N階上三角矩陣，對稱矩陣和反對稱矩陣都只需要儲存主對角線以上的共(N+1)*N/2個元素。因此，我們可以用一個大小為(N+1)*N/2的一維數(shù)組來表示。不過，我們需要一個公式，把每個元素原來的位置(i,j)映射到一維數(shù)組的下標k。第五頁，共三十三頁，編輯于2023年，星期二三角矩陣的壓縮表示(2)我們從上到下，從左到右地儲存各個元素，如下圖：Aij前面的數(shù)的個數(shù)為：計算得:第六頁，共三十三頁，編輯于2023年，星期二稀疏矩陣在前面的二維數(shù)組表示法中，我們表示一個N*M的矩陣需要N*M個內(nèi)存單元。如果已知矩陣中存在著大量的0元素，那么這種表示方法是很浪費空間的。由于非零元素的個數(shù)L十分有限，我們可以只儲存下這L個元素的位置和大小，占用的空間便會少得多。第七頁，共三十三頁，編輯于2023年，星期二稀疏矩陣的三元組表示法顯然，表示稀疏矩陣最直接的方法就是僅記錄下非零元素的個數(shù)L和這L個元素的位置(row,col)和大小(value)，即下面這個結(jié)構(gòu)：structTMatrix2{intl;introw[MAXL],col[MAXL],value[MAXL];};第八頁，共三十三頁，編輯于2023年，星期二稀疏矩陣的十字鏈表表示(1)三元組表示法比較好的解決了稀疏矩陣的空間存儲問題，卻忽視了稀疏矩陣可能進行了一些基本操作。考慮兩個稀疏矩陣A和B相加的問題。對于運算結(jié)果矩陣C來說，可能會因為正負抵消而產(chǎn)生出很多新的零元素和非零元素，導致三元組需要進行一些插入和刪除操作。當這些操作很頻繁的時候，程序的速度會明顯變慢。在某些特定情況下，我們需要對元素進行檢索，由于三元組的元素之間聯(lián)系并不緊密，所以檢索很不方便。第九頁，共三十三頁，編輯于2023年，星期二稀疏矩陣的十字鏈表表示(2)為了加強同一行和同一列之間元素的聯(lián)系，我們把每一行分別做成一個鏈表，把每一列也分別做成一個鏈表。通過對鏈表的遍歷，我們可以很方便的按順序訪問到某一特定行或列的所有元素。插入和刪除操作也很方便。這樣，我們了建立一種十字型的鏈表結(jié)構(gòu)，每個結(jié)點有上，下，左，右四個指針和自身的位置坐標，大小共7個域。第十頁，共三十三頁，編輯于2023年，星期二稀疏矩陣的十字鏈表表示(3)結(jié)點類型如下定義：structTnode{introw,col;intvalue;Tnode*left,*right,*up,*down;};row,col分別為該非零元素的位置，value為它的值。left,right,up,down分別為指向四個方向的后繼元素。第十一頁，共三十三頁，編輯于2023年，星期二稀疏矩陣的十字鏈表表示(4)為了方便的找到每一個包含非零元素的行和列，我們把所有行串在一起，組成一個行鏈表，把所有列也串在一起，組成一個列鏈表。像這樣：structTRow{intRowNo;TNode*firstnode;};structTCol{intColNo;TNode*firstnode;};第十二頁，共三十三頁，編輯于2023年，星期二矩陣表示方法小結(jié)矩陣的表示方法和應用是分不開的。我們衡量一種表示方法的優(yōu)劣，需要從不同的角度進行分析。適用范圍空間需求量基本操作的時間消耗實現(xiàn)的難易程度以上幾種方法都在某些方面表現(xiàn)良好而其他方面不夠理想，因此我們需要根據(jù)實際需要的側(cè)重點不同，選擇合適的表示方法第十三頁，共三十三頁，編輯于2023年，星期二二、矩陣的基本運算矩陣的判重矩陣的線性運算矩陣的轉(zhuǎn)置矩陣乘法第十四頁，共三十三頁，編輯于2023年，星期二矩陣的判重在二維數(shù)組表示法中，我們可以用一個二重循環(huán)判斷兩個矩陣是否相等。在三元組表示方法中，我們?nèi)绻ＷC非零元素是按照從上到下，從左到右的順序儲存的，則可以用一個循環(huán)直接判斷。但如果不能保證，則需要二重循環(huán)。因此在未加說明的情況下，三元組表示法均需要按順序保存各個元素。在十字鏈表表示方法中，我們需要依次遍歷每一個非零行（或者列）。第十五頁，共三十三頁，編輯于2023年，星期二矩陣的線性運算矩陣的數(shù)乘:B=kA在任何一種表示法中，我們都可以通過遍歷所有元素的方法完成數(shù)乘運算。矩陣的加法:C=A+B在二維數(shù)組表示法中，我們可以通過二重循環(huán)來進行矩陣加法在稀疏矩陣中，注意到結(jié)果中的非零元素所在的位置必對應A或B中的一個非零元素，所以加法運算不會在A和B中原非零元素之外的其他位置上生成新的非零元素。第十六頁，共三十三頁，編輯于2023年，星期二矩陣的線性運算(2)考慮三元組表示法中的矩陣加法。由于都需要按順序儲存各個元素，我們應當按順序?qū)γ總€A或B中非零的位置做加法。下面有一個例子：第十七頁，共三十三頁，編輯于2023年，星期二矩陣的線性運算(3)我們記錄兩個矩陣A，B的當前非零元素序號pA和pB。為了保證結(jié)果的有序性，我們每次比較這兩個當前元素的位置。如果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中。第十八頁，共三十三頁，編輯于2023年，星期二矩陣的線性運算(4)十字鏈表表示法下的加法可以一行行的做。即：如果A的當前行號比B小，把A的當前行整個復制到C中。如果B的當前行號比A小，把B的當前行整個復制到C中。否則把A的當前行和B的當前行的合并結(jié)果加入C中。第三種情況和三元組表示下的加法很類似，只是下標pA,pB換成了指針。同樣的，需要注意兩個非零元素之和可能等于零，從而不能插入到結(jié)果中第十九頁，共三十三頁，編輯于2023年，星期二矩陣的轉(zhuǎn)置(1)矩陣的轉(zhuǎn)置在二維數(shù)組中，轉(zhuǎn)置可以通過簡單的坐標變換得到在三元組表示法中，在對每個元素進行坐標變換后還需要進行一次排序，以維持元素位置的有序性。在十字鏈表表示法中，我們不僅需要對每個結(jié)點進行坐標變換，還需要交換行鏈表和列鏈表，以及更改每個結(jié)點四個方向的指針，實現(xiàn)比較麻煩。第二十頁，共三十三頁，編輯于2023年，星期二矩陣的轉(zhuǎn)置(2)二維數(shù)組的轉(zhuǎn)置可以通過下列代碼來實現(xiàn)：voidMatrixT(TMatrixA){TMatrixB;B.m=A.n;B.n=A.m;for(inti=1;i<=A.n;i++)for(intj=1;j<=A.m;j++)B.numbers[j][i]=A.numbers[i][j];returnB;}對代碼稍作修改，我們可以對矩陣進行旋轉(zhuǎn)和鏡像變換生成8個新矩陣第二十一頁，共三十三頁，編輯于2023年，星期二矩陣的轉(zhuǎn)置(3)前面提到過，三元組表示法中，矩陣的轉(zhuǎn)置可以通過坐標變換后排序來實現(xiàn)。不過，我們通常使用的是另外一種方法。這種方法不用排序，而速度也更快?？焖俎D(zhuǎn)置算法：直接寫到正確的位置。首先，求出每一列第一非零元素轉(zhuǎn)置后的序號。這一步只需要統(tǒng)計一下每列的非零元素的個數(shù)就可以了。由于每一列的元素在轉(zhuǎn)置以后的先后次序保持不變，每個元素就可以直接寫到該行的下一個空閑位置。第二十二頁，共三十三頁，編輯于2023年，星期二矩陣的轉(zhuǎn)置(4)請看下面的例子：各列非零元素個數(shù)為：2,3,0,1各列第一個元素序號：0,2,5,5012345123456第二十三頁，共三十三頁，編輯于2023年，星期二矩陣乘法(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時，如果Cik并不存在，就需要對矩陣進行插入操作。在十字鏈表上的插入操作比三元組快得多。第二十四頁，共三十三頁，編輯于2023年，星期二矩陣乘法(2)Strassen矩陣乘法下面，我們來介紹基于二維數(shù)組的矩陣相乘算法?？紤]兩個2*2矩陣A和B相乘。普通的方法需要進行8次乘法。第二十五頁，共三十三頁，編輯于2023年，星期二矩陣乘法(3)Strassen的新方法如下：只需要7次乘法!!!第二十六頁，共三十三頁，編輯于2023年，星期二矩陣乘法(3)當矩陣為2N*2N時，我們可以利用分塊矩陣，分成2*2個2N-1*2N-1矩陣，遞歸求解。當N=1時可以直接利用公式得出結(jié)果。分析指出，Strassen乘法比常規(guī)乘法的加法和乘法運算量都有減少，但存儲量增加，是一種用空間換時間的方法。此方法還可以推廣到矩陣的求逆運算。第二十七頁，共三十三頁，編輯于2023年，星期二三、小結(jié)與應用舉例矩陣表示小結(jié)矩陣運算小結(jié)結(jié)束語鳴謝第二十八頁，共三十三頁，編輯于2023年，星期二小結(jié)–矩陣的表示矩陣的表示矩陣有三種常用的表示方法：二維數(shù)組，三元組和十字鏈表。二維數(shù)組適合稠密矩陣，表示直觀，操作方便三元組是稀疏矩陣最省空間的表示方法之一，它可以很好的支持線性運算和乘法運算，且編程復雜度低，是稀疏矩陣表示法的首選。十字鏈表比三元組占用空間大些，不過仍適合稀疏矩陣的表示，尤其適用于非零元素個數(shù)變化較大的場合，但不適合轉(zhuǎn)置操作，且編程實現(xiàn)難度較大。第二十九頁，共三十三頁，編輯于2023年，星期二小結(jié)–矩陣的運算矩陣的運算三種方法都可以通過遍歷表的方式判定兩個矩陣是否相同。三種表示方法都能較好的支持線性運算。數(shù)乘運算只需要遍歷一次所有元素，而稀疏矩陣的加法運算需要進行類似有序表合并的操作。二維數(shù)組的轉(zhuǎn)置只需要進行坐標變換，三元組還需要排序，而十字鏈表需要更新多個指針域。轉(zhuǎn)置可以推廣到平面點陣圖象的變換，這時一般采用數(shù)組來表示矩陣。矩陣乘法的算法有很多種。基于數(shù)組的算法中，Strassen算法是一種以空間換時間的算法。稀疏的乘法不是依次計算結(jié)果的每個元素，而是依次考慮A和B的每對元素對結(jié)果的貢獻。第三十頁，共三十三頁，編輯于2023年，星期二結(jié)束語在前面的內(nèi)容中，我們討論了矩陣的表示和基本運算。希望這些內(nèi)容能開闊大家的眼界，啟發(fā)大家的思維，激發(fā)大家進一步學習的興趣。這些內(nèi)容只是矩陣中最最基本的東西。像初等變換，矩陣求逆，求特征值等方面并為涉及到。但是如果能熟練的掌握以上內(nèi)容，相信各位