《The C Programming Language》經典習題精講：矩陣轉置與乘法的一維數組統一實現

習題一：任意尺寸矩陣轉置

難點

C 語言二維數組作為參數需指定列數（void f(int a[][3])），失去通用性。

破解鍵：內存佈局同構性

二維數組在內存中按行主序連續存放：
a[2][3] = {{1,2,3},{4,5,6}} → 內存：1 2 3 4 5 6
轉置後 b[3][2] = {{1,4},{2,5},{3,6}} → 內存：1 4 2 5 3 6

若視為一維數組：
a[i][j] → a[i*cols + j]
b[j][i] → b[j*rows + i]
轉置賦值：b[j*rows + i] = a[i*cols + j]

通用函數簽名

void transpose(int* m1, int* m2, int rows, int cols);

調用時傳 *a（退化為 int*），實現任意尺寸轉置。

完整代碼

void transpose(int* m1, int* m2, int x, int y) { 
    for (int i = 0; i < x; ++i) 
        for (int j = 0; j < y; ++j) 
            m2[j*x + i] = m1[i*y + j]; 
} 

int main() { 
    int m1[2][3] = {{1,2,3},{4,5,6}}; 
    int m2[3][2]; 
    transpose(*m1, *m2, 2, 3); 
    // m2 = {{1,4},{2,5},{3,6}} 
    return 0; 
}

習題二：任意尺寸矩陣乘法

數學規律

m1[x][y] × m2[y][z] → r[x][z]
r[i][k] = Σ (m1[i][j] * m2[j][k]) , j=0..y-1

一維映射：
m1[i][j] → m1[i*y + j]
m2[j][k] → m2[j*z + k]
r[i][k] → r[i*z + k]

三重循環實現

void multiply(int* m1, int* m2, int* r, int x, int y, int z) { 
    for (int i = 0; i < x; ++i) 
        for (int j = 0; j < y; ++j) 
            for (int k = 0; k < z; ++k) 
                r[i*z + k] += m1[i*y + j] * m2[j*z + k]; 
}

核心洞見

1. 一維數組統一二維操作：利用行主序連續存儲特性，用線性索引替代雙下標，獲取通用性。
2. 下標映射公式：index = row * COLS + col 是所有二維轉一維的核心。
3. 參數退化利用：*matrix 將 int[][COLS] 退化為 int*，配合運行時傳入維度，實現泛型效果。

總結

K&R 經典習題揭示了 C 語言處理矩陣運算的底層邏輯：內存佈局決定訪問模式。一維化技巧不僅解決參數傳遞限制，更是高性能計算（BLAS、圖像處理）中優化緩存訪問的基石。本文整理自《The C Programming Language》習題研究筆記。