第一章 矩陣 一、矩陣的轉置   問題描述： 編寫函數，把給定的任意一個二維整型矩陣轉換為其轉置矩陣。 輸入：       1 2 3       4 5 6 輸出：       1 4       2 5       3 6     分析     題目要求編寫一個能轉置任意二維矩陣的函數，顯然這個函數需要得到一個二維數組的參數，還應該有一個作為輸出的二維數組，我們可以將這個數組也傳遞給函數，然後函數交換行列的下標賦值給輸出數組（即b[j][i] = a[i][j]）即可。這樣看似問題可以得到解決了，但是，二維數組作為參數時必須指定列數，也就是第二維的大小，比如：void transpose ( int a[][3], int b[][2]),那麼這個函數就只能將=轉置2行3列的矩陣，無法達到題目中轉置任意矩陣的要求。     如何讓函數具有通用性呢？我們考慮到數組在內存中的存放方式是按行線性連續排列的，比如： 數組 a[2][3] = {       { 1,2, 3 },       { 4,5, 6 }    };   b[3][2] = {       { 1,2 },       { 3,4 },       { 5,6 }    };     看起來這兩個數組的布局不一樣但是它們在內存中的排列方式是相同的： a： a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] 1 2 3 4 5 6   b： b[0][0] b[0][1] b[1][0] b[1][1] b[2][0] b[2][1] 1 2 3 4 5 6     這樣看來，一維數組在某些時候可以代替二維數組，並且最重要的是，一維數組作為參數傳遞給函數時，不用指定長度，這個正好符合題意。我們能不能使用一維數組完成題目的要求呢？     首先看一下在二維數組中，轉置是如何發生的： 1 2 3 4 5 6     轉置    →    1 4 2 5 3 6       很明顯，在二維視角下，矩陣的轉置就是交換行標和列標，即：b[j][i] =a[i][j]，而2X3的二維數組中的元素a[i][j],在一維視角下就變為a[i*3+j],轉置後的3X2二維數組中對應的元素b[j][i]變為b[j*2+i]。如此a[i*3+j]= b[j*2+i]就可以實現轉置了。     至此，我們已經找到了使用一維數組實現二維數組轉置的方法，現在看看如何將一個二維數組變成一維數組參數。由於一維數組在作為函數參數時就是一個指向int類型的指針，而二維數組名a是一個指向以為數組的指針，因此*a就是一個一維數組，使用它作為函數參數時也是一個指向int類型的指針。       下面是完整的程序：  

/* 
 * 轉置矩陣的通用函數 
 */  
void transpose ( int *m1, int *m2, int x, int y );  //轉置函數  
static int m2[3][2];        //自動初始化  
  
int main ( void )  
{  
    int m1[2][3] = {  
        {1, 2, 3},  
        {4, 5, 6},  
    };  
      
    int i;  
    int j;  
  
    transpose ( *m1, *m2, 2, 3 );   //使用參數*m1、*m2  
  
    for ( i=0; i<3; i++ )  
    {  
        for ( j=0; j<2; j++ )  
            printf ( "%3d", m2[i][j] );  
        printf ( "\n" );  
    }  
  
    return 0;  
}  
  
  
void transpose ( int *m1, int *m2, int x, int y )  
{  
    int i;  
    int j;  
  
    for ( i=0; i<x; i++ )  
        for ( j=0; j<y; j++ )  
            m2[j*x+i] = m1[i*y+j];  
}  

 

     小結：利用二維數組的內存分布特點，可以用一維數組來處理二維數組的問題，並且這種方法還具有通用性。   二、矩陣的乘法   問題描述：編寫一個實現兩個任意矩陣乘法的函數（兩個矩陣中一個的行數和另一個的列數相同） 輸入：      m1:       2   -6       3    5       1   -1        m2:       4    -2   -4   -5       -7   -3    6    7   輸出：      r:       50    14   -44   -52      -23   -21    18    20       11    1    -10   -12         分析：     我們首先考慮矩陣乘法的法則：     就以上這個例子而言，顯然有：       r[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];       r[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];     ......     觀察發現：以上等式中，所有m1的行標都與r的行標一致，所有m2的列標都與r的列標一致，而m1中和m2中剩下的沒有確定的下標都是在遍歷，更巧的是，這兩個沒有確定的下標的遍歷范圍是一致的。     我們假設m1的大小為x*y，m2的為y*z，m3自然就應該是x*z，分別用i、j、k遍歷x、y、z。那麼，對於一個給定了具體下標值的元素r[i][k]（假定r中所有元素的初始值為0），在計算此元素的表達式中，所有m1的行標都已經確定為i，所有m2的列標也確定為k，此時只需要使用j來遍歷y，並將j作為m1和m2中那個還沒有確定的下標值，可以通過遍歷i和k來實現遍歷所有r的元素，偽代碼如下：     i: 0 → x         k: 0 → z             j: 0 → y                 r[i][k] += m1[i][j] * m2[j][k];       最後，我們仍然要使用一維數組來解決通用性的問題：     m1[i][j] = m1[i*y+j];     m2[j][k] = m2[j*z+k];     r[i][k] = r[i*z+k];       最終的函數和測試程序如下：  

/* 
 * 矩陣乘法 
 */  
#include <stdio.h>  
void multiply ( int *m1, int *m2, int *r, int x, int y, int z );  
  
static int r[3][4];  
  
int main ( void )  
{  
    int m1[3][2] = {  
        {2, -6},  
        {3, 5},  
        {1, -1}  
    };  
  
    int m2[2][4] = {  
        {4, -2, -4, -5},  
        {-7, -3, 6, 7}  
    };  
  
    int i,j;  
  
    multiply ( *m1, *m2, *r, 3, 2, 4 );  
  
    for ( i=0; i<3; i++ )  
    {  
        for ( j=0; j<4; j++ )  
            printf ( "%5d", r[i][j] );  
        printf ( "\n" );  
    }  
  
    return 0;  
}  
  
  
void multiply ( int *m1, int *m2, int *r, int x, int y, int z )  
{  
    int i, j, k;  
  
    for ( i=0; i<x; i++ )  
        for ( j=0; j<y; j++ )  
            for ( k=0; k<z; k++ )  
                r[i*z+k] += m1[i*y+j] * m2[j*z+k];  
}  
  
  

 

  /*   *  測試結果：   *   *  50   14  -44  -52   * -23  -21   18   20   *  11    1  -10  -12   *   */           小結：注意分析乘法法則，得到下標值之間的關系。